Prove scritte 2021

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;
  }
}

Es G1

consegna

Sia dato l'algoritmo di rimpiazzamento modulo che data una memoria di NF frame , se avviene un page fault in corrispondenza dell'i-mo elemento della stringa di riferimenti modulo sceglie come pagina vittima quella che occupa il frame i % NF. Es. se NF fosse 3, la prima pagina viene messa nel frame 1 perché 1 % 3 = 1, se l'undicesimo elemento della stringa causa un page fault, si elimina la pagina nel frame 2 (11 % 3 = 2). A) Considerare la stringa di riferimenti seguente e mostrare il funzionamento di modulo nei casi NF = 3 e NF = 4: 1 2 3 4 5 3 3 3 1 5 B) modulo è un algoritmo a stack?

Soluzione proposta (da controllare)

Flecart (talk) 14:44, 4 May 2023 (CEST)

Caso in cui NF=3
allora
1 X X   1
1 2 X   2
1 2 3   3
4 2 3   4
4 5 3   5
4 5 3   3
4 5 3   3
4 5 3   3
1 5 3   1
1 5 3   5

Caso in cui NF=4
1 X X X 1
1 2 X X 2
1 2 3 X 3
1 2 3 4 4
5 2 3 4 5
5 2 3 4 3
5 2 3 4 3
5 2 3 4 3
1 2 3 4 1
5 2 3 4 5

Allora, l'algoritmo non è a stack perché nella penultima accesso al frame ho nel caso NF=3 che
{1, 5, 3}, ma questo non è contenuto in {1, 2, 3, 4}.

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();
	}
}
}

2. Soluzione proposta

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)
  }
}

Soluzione proposta 3 (da controllare)

Proposta da SpookyWiki (talk) 11:41, 25 May 2023 (CEST)

monitor alrv {
	int maxindex;
	Map<int, int> waiting4[];
	Map<int, condition> ok2go[]

	alrv() {
		maxindex = 0;
		waiting4 = new Map<int, int>();
		ok2go = new Map<int, condition>();
	}
	
	procedure int check() { //procedura che controlla che i processi in attesa fino n possano essere sbloccati o meno
		int sum = 0;
		int m = 0;
		do {
			m++
			sum += waiting4[m];
		} while(m < maxindex && sum >= m)
		return sum >= m ? m : m - 1;
	} 

	procedure entry void at_least(int n) {
		if(waiting4[n] == null) {
			waiting4.add(n);
			waiting4[n]++;
			ok2.add(n);
		}
		if (n > maxindex)
			maxindex = n;
		int m;
		if ((m = check(n)) > 0) {
			for(int i = 1; i <= m; i++) {
				ok2[i].signal();
				waiting4[i] = 0;
			}
		} else {
			ok2go[n].wait();
			ok2go[n].signal();
		}
	}
}

Esercizio C2

Dato un servizio di message passing sincrono scrivere, senza fare uso di processi server, un servizio di message passing sincrono concatenato che abbia le seguenti primitive:

 void chained_send (T msg, list_of_pids dests)
 T chained_recv(void)

La funzione chained_send deve fare in modo che tutti i processi indicati nella lista dests ricevano il messaggio. Il processo che chiama la chained_send si blocca solo fino a quando il primo processo della lista dests non chiama una chained_recv, il primo si sblocca quando il secondo chiama la chained_recv e così via. ( la funzione chained_recv riceve messaggi provenienti da qualsiasi mittente)

Soluzione proposta 1 (da controllare)

• proposta da Flecart (talk) 18:37, 16 January 2023 (CET)

void chained_send(T msg, list_of_pids dests) {
	if (dests.len() < 1) return ERROR;
	else if (dests.len() == 1) {
		pid head = dests[0];
		ssend(<msg, NULL>, head);
	} else {
		<head, rest> = dests[0], dests[1:];
		ssend(<msg, rest>, head);
	}
}


T chained_recv(void) {
	<msg, rest> = srecv(ANY);
	if (rest == NULL) return msg;

	if (rest.len() == 1) {
		pid head = rest[0];
		ssend(<msg, NULL>, head);
	} else if (rest.len() > 1) {
		<head, rest2> = rest[0], rest[1:];
		ssend(<msg, rest2>, head);
	}

	return msg;
}

Soluzione proposta 2 (da controllare)

Proposta da SpookyWiki (talk) 12:20, 23 May 2023 (CEST)

void chained_send(T msg, list_of_pids dests) {
	if ( dests.length() < 1)
		return;
	pid_t dest = dests.pop(0); //rimuovo e prendo il primo destinatario
	ssend(<msg, dests>, dest);
}

T chained_recv(void) {
	<msg, dests> == srecv(ANY);
	if(dests.length() > 0) { //il messaggio deve essere ancora inviato ad altri
		pid_t dest = dests.pop(0);
		ssend(<msg, dests>, dest);
	}
	return msg;
}

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;
  }
}

Soluzione proposta 3 (da controllare)

Proposta da SpookyWiki (talk) 12:05, 25 May 2023 (CEST)

Si assume una politica FIFO delle condition, NDELAY non variabile d'ambiente ma parametro passato all'inizializzazione.

monitor delayvalue {
	int ndelay;
	int in;
	int lastvalue;
	condition ok2return;

	delay(int NDELAY) {
		ndelay = NDELAY;
		in = 0;
		lastvalue = 0;
	}

	procedure entry int delay(int value) {
		if (in >= ndelay) {
			lastvalue = value;
			ok2return.signal();
		} else 
			in++;
		ok2return.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:

• Gio (talk) 17:45, 16 January 2023 (CET)

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;
  }
}

Soluzione proposta 3

Soluzione proposta da zBarba (talk) 14:47, 20 January 2024 (CET)

monitor bss:
list<T> buffer
int nget
condition ok2put
condition ok2get

procedure entry void put(T value){
    buffer.add(value)
    if(nget==0){
        ok2put.wait()
        ok2put.signal() //cascata di signal
    }else if(nget>0){
        ok2get.signal()
        buffer.clear()
    }
}

procedure entry list<T> get(void){
    ok2put.signal()
    if(buffer.isEmpty()){
        nget++
        ok2get.wait()
        ok2get.signal() //cascata di signal
        nget--
    }
    return buffer
}

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);
	}
}

Soluzione proposta 2

Soluzione proposta da Flecart (talk) 13:05, 7 March 2023 (CET) dovrebbe essere più semplice della precedente.

sasend(message, destination) {
	pid t = getpid();
	asend(<message, t>, destination);
}

extern int MAX_PID;

// storerà tutti i messaggi che ricevo che non riesco a utilizzare subito
queue<message> msgs[MAX_PID];
sarecv(senders) {
	if (senders == NULL) {
		senders = {0, 1, ..., MAX_PID};
	}
	
	for (pid_t sender : senders) {
		if (msgs[sender].size() > 0) {
			message_t msg = msgs[sender].dequeue();
			return msg;
		}
	}
	
	while (True) {
		msg, pid = arecv(ANY);
		if (pid in senders) {
			return msg;
		} else {
			msgs[pid].enqueue(msg);
		}
	}
}