Difference between revisions of "Prove scritte 2021"
m (→Esercizio c2) |
|||
| Line 250: | Line 250: | ||
== Esercizio c2 == | == Esercizio c2 == | ||
| − | + | Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che | |
| − | |||
| − | |||
| − | |||
| − | |||
fornisca le seguenti primitive: | fornisca le seguenti primitive: | ||
void PLP(int prio); | void PLP(int prio); | ||
Revision as of 18:10, 16 January 2023
Prova 21/07/2021
Es C1 (da correggere)
Soluzione proposta da Flecart friend,regalo a flecart la proprietà intellettuale di questa soluzione
class node{
node parent;
sq sq1;
cond c;
}
class BinTree{
vector<node> base;
void create(int N){
base=new vector<node>(2^N);
for(int i=0;i<2^N;i++)
base[i]=new node(null,0,new cond);
for(int i=1;i<=N;i++){
for(int j=0;j<2^(N-i);j++){
get(j,i-1).parent=get(j+i,i-1).parent=new node(null,0,new cond);
}
}
}
node get(int i,int level){
return get(base[i],level);
}
node get(node n,int level){
if(level==0){
return node;
}
return get(node.parent,level-1);
}
}
class Torneo{
BinTree bin(N);
int forma[2^N];
bool win;
bool gioca(int i,int turno,int forma){
forma[i]=forma;
if null==bin.get(i,turno).sq1{
bin.get(i,turno).sq1=i;
bin.get(i,turno).c.wait();
return !win;
}else{
sq1= bin.get(i,turno).sq1;
if(forma[sq1]==forma[i]){
win=random();
}else{
win=forma[sq1]<forma[i];
}
bin.get(i,turno).signal();
}
return win;
}
}
Prova 2021/09/15
Esercizio C1
Consegna
Esercizio c.1: Scrivere il monitor alrv (at least rendez-vous) che fornisce una sola procedure entry: procedure entry void at_least(int n) Quando un processo chiama la funzione at_least vuol dire che vuole sincronizzarsi con un insieme di almeno n processi (incluso il chiamante). Esempi: Se un processo chiama at_least(1) non si blocca. Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(2) oppure at_least(1) si sbloccano sia p sia q (la richiesta di p è soddisfatta, ne aspettava almeno 2, p e q) Se il processo p chiama at_least(2) si blocca, se poi il processo q chiama at_least(3) si blocca anch'esso perché sebbene la richiesta di p possa essere soddisfatta, q non può ancora sbloccarsi: ci sono solo 2 processi in attesa mentre q ne vuole 3. Un terzo processo che chiami at_least(x) con x=1,2,3 li sblocca tutti. Hint: sia w[k ] il numero dei processi in attesa di essere in almeno k (quelli che hanno chiamato at_least(k) e non hanno completato l'esecuzione della funzione). Sia s[n]=∑ k=1 n w[k ] (rappresenta il numero di processi soddisfacibili: e.g. se ci sono 4 processi in attesa, potrebbero essere soddisfatte le richieste dei processi che ne aspettano almeno 2, almeno 3 o almeno 4). Preso, se esiste, il massimo indice m tale che s[m]≥m tutti i processi in attesa di essere in n, per n≤m possono essere sbloccati.
1. Soluzione proposta
Soluzione proposta da Flecart
extern int MAX; // il massimo numero di attesa
monitor alrv {
int w[MAX];
int s[MAX];
condition c[MAX];
init() {
for (int i = 0; i < MAX; i++) {
w[i] = s[i] = 0;
}
}
procedure entry void at_least(int n) {
if (n >= MAX || n <= 0) raise error;
int i;
for (i = n; i < MAX; i++) s[i]++;
for (i = MAX - 1; i > 0; i--) {
if (s[i] >= i) break;
}
if (i > 0) {
for (int j = 0; j <= i; j++) {
while (w[j] > 0) {
c[j].signal();
w[j]--;
}
}
s[0] = 0;
for (int i = 1; i < MAX; i++) {
s[i] = w[i] + s[i - 1];
}
} else {
w[n]++;
c[n].wait();
}
}
}
Soluzione proposta da Flecart friend,regalo a flecart la proprietà intellettuale di questa soluzione
class Monitor{
min_heap<(int,cond)> h;
void at_least(int n){
int sum=0;
int max_to_sblock= -INF;
cond c = new cond(n);
h.push((n,c));
// la heap viene visitata in maniera crescente
for(auto f=h.begin_iter();null!=f.next();f++) {
sum++;
if(f.0<=sum){
max_to_sblock =f.0;
}
}
for(auto f=h.begin_iter();null!=f.next();f++) {
if(f.0<=max_to_sblock){
f.1.signal();
h.remove(c);
}
}
if(n>max_to_sblock){
c.wait();
}
free(c)
}
}
Prova 2021/06/23
Esercizio C1
Consegna
Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:
int delay(int value);
Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:
P1: delay(44) -> P1 si sospende P2: delay(40) -> P2 si sospende P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende
Soluzione proposta 1
Soluzione proposta da Flecart
// variabile definita altrove.
extern int NDELAY;
class Monitor {
Queue<condition> stopped;
int curr_value;
Monitor {
stopped = Queue<condition>();
curr_value = 0;
}
int delay(int value) {
curr_value = value;
if (stopped.size() == NDELAY) {
condition first = stopped.dequeue();
first.signal();
}
condition c = new condition();
stopped.enqueue(c);
c.wait();
free(c);
return curr_value;
}
}
Soluzione proposta 2
Soluzione proposta da Flecart friend, regalo la proprietà intellettuale a flecart.
- Controllato da Flecart (talk) 18:10, 16 January 2023 (CET), corretto se si assume la FIFO interna della condition.
monitor dalayvalue{
#define NDELAY 22
int blocked=0;
int lastvalue=0;
cond c;
int dalay(int value){
lastvalue=value;
if(blocked<NDELAY){
blocked++;
c.wait();
}else if(blocked==NDELAY){
c.signal();
c.wait();
}
return lastvalue;
}
}
Esercizio c2
Implementare usando semafori ordinari (fair, fifo) un servizio di semafori a priorità lifo che fornisca le seguenti primitive:
void PLP(int prio); void PLV()
PLP e PLV si devono comportare rispettivamente come P e V. Quando la PLV deve riattivare un processo sceglie fra quelli in attesa quello a priorità massima, nel caso siano presenti più processi a priorità massima sceglie quello in attesa da meno tempo.
Soluzione proposta 1
Esercizio c2 da Flecart.
controllato:
Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);
void PLP(int prio) {
mutex.P();
if (num_V > 0) {
num_V--;
mutex.V();
return;
}
semaphore sem = semaphore(0);
stack[prio].push(sem);
mutex.V();
sem.P();
mutex.V();
}
void PLV() {
mutex.P();
for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
if (stack[i].size() > 0) {
sem = stack[i].pop();
sem.V();
return;
}
}
num_V++;
mutex.V();
}
Prova 2021/05/26
Consegna c1
Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry: void put(T value) list of T get(void) La entry put viene utilizzata per aggiungere un elemento e la entry get per leggere tutti quelli disponibili. Se più processi chiamano la put quando nessun processo è in attesa per una get, rimangono tutti bloccati. Quando successivamente un processo chiama la get riceve la lista di tutti gli elementi inseriti con le put e tutti i processi vengono sbloccati. Se il buffer è vuoto tutti i processi che chiamano la get rimangono bloccati. quando un processo chiama successivamente la put tutti i processi in attesa per la get si sbloccano e ricevono lo stesso valore di ritorno: una lista contenente il solo valore passato come parametro alla put.
Soluzione proposta 1
Soluzione proposta da Flecart
int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
semaphore semput(0);
semaphore semget(0);
semaphore mutex(1);
list<T> global_list;
void put(T value) {
//< await(num > 0) --> global_list.add(value) >
mutex.P();
if (num <= 0) {
num--;
mutex.V();
semput.P();
num++;
}
global_list.add(value);
if (num < 0)
semput.V();
else
semget.V();
return;
}
list of T get() {
list<T> local_list;
mutex.P();
if (num >= 0) {
num++;
mutex.V();
semget.P();
num--;
} else {
semput.V();
semget.P();
}
local_list = global_list; // fa deep copy
if (num > 0) {
semget.V();
} else {
global_list = list<T>();
mutex.V();
}
return local_list;
}
Soluzione proposta 2
Soluzione proposta da Gio
class bss{
int waiting_put=0;
int waiting_get=0;
cond cw,cg;
queue<T> q;
void put(T value){
q.push(T);
if(waiting_get>0){
cg.signal()
}else{
waiting_put++;
cw.wait();
waiting_put--;
}
}
list<T> get(){
if(waiting_put>0){
while(waiting_put>0){
cw.signal();
}
}else{
waiting_get++;
cg.wait();
waiting_get--;
}
list<T> p= q.tolist();
if(waiting_get>0){
cg.signal();
}
q.removeAll();
return p;
}
}
esercizio c2
Dato un servizio di message passing asincrono implementare un servizio di message passing asincrono a selezione di mittenti (samp) senza fare uso di processi server. Il servizio samp ha due primitive: sasend(message , destination) sarecv(senders) dove senders è un insieme. la sarecv restituisce il primo messaggio che uno dei processi in senders ha spedito al processo ricevente usando la sasend (o spedito da qualsiasi processo se senders è vuoto).
Soluzione proposta 1
Soluzione proposta da Flecart (talk) 15:29, 15 January 2023 (CET)
sasend(message, destination) {
pid t = getpid();
asend(<message, t>, destination);
}
// variabile privata di sarecv
queue all_messages[MAX_PROC];
// stora tutti i messaggi ricevuti, lo utilizziamo come queue per tutti, con
// anche la possibilità di rimuovere in un punto a scelta.
vector<<messages, pid>> msg;
sarecv(senders) {
if (senders.len() == 0) {
if (msg.len() == 0) {
<message, sender> = arecv(ANY);
return message;
} else {
<message, sender> = msg.pop_back();
return message;
}
} else {
do {
for (idx in senders) {
if (all_messages[idx].size() > 0) {
message = all_messages[idx].dequeue();
// rimuove il singolo messaggio dal vector, non tutti quelli uguali.
msg.remove(<message, idx>);
return message;
}
}
<message, sender> = arecv(ANY);
msg.push_back(<message, sender>);
all_messages[sender].enqueue(<message>);
} while(true);
}
}