Prova teorica 2014.07.16
Jump to navigation
Jump to search
Testo: [1]
Esercizio c.1
Soluzione di S.G
/*
* Esercizio c.1: scrivere il monitor mMbb che realizzi un meccanismo di un minmax bounded buffer.
* Dopo le prime MIN operazioni di scrittura, un minmax bounded buffer deve sempre avere almeno MIN elementi e mai piu' di MAX
* elementi (e' quindi limitato sia nell'ampiezza massima, sia nell'ampiezza minima).
* Le funzioni (procedure entry) read e write del minmax bounded buffer hanno gli stessi argomenti e valori di ritorno di quelle del
* producer/consumer o del bounded buffer ordinario.
*/
#define MIN
#define MAX
#define SIZE // con SIZE >= MAX
monitor mMbb{
generic_type bb[];
int front, rear, count;
condition R, W;
void mMbb(void){
bb = new generic_type[SIZE];
front = rear = count = 0;
}
procedure_entry generic_type read(){
while(count < MIN) // Controllo che il buffer abbia MIN elementi per poter leggere
R.wait();
generic_type ret = bb[rear];
count--;
rear = (rear + 1) % SIZE;
W.signal();
return ret;
}
procedure_entry write(generic_type c){
while(count >= MAX) // Controllo che il buffer non abbia MAX elementi per poter scrivere
W.wait();
bb[front] = c;
count++;
front = (front + 1) % SIZE;
R.signal();
}
}
S.G (talk) 17:21, 2 December 2016 (CET)
Non è fifo. Perché? Renzo (talk) 07:43, 3 December 2016 (CET)
Nel caso in cui MIN vale 3 e arrivino tre processi lettori nel seguente ordine, L1, L2, L3, avremmo che la coda di R è la seguente:
R: L1, L2, L3
Ora arriva un processo scrittore S1, viene eseguito liberando un lettore (R.signal) cioè L1. A questo punto L1 riprende la sua esecuzione, riesegue il ciclo e rientra nello stato di attesa. Quindi ora la coda di R è la seguente:
R: L2, L3, L1
Si potrebbe risolvere il problema modificando le funzioni write e read nel seguente modo:
procedure_entry generic_type read(){
if(count < MIN) // Controllo che il buffer abbia MIN elementi per poter leggere
R.wait();
generic_type ret = bb[rear];
count--;
rear = (rear + 1) % SIZE;
if(count < MAX)
W.signal();
return ret;
}
procedure_entry write(generic_type c){
if(count >= MAX) // Controllo che il buffer non abbia MAX elementi per poter scrivere
W.wait();
bb[front] = c;
count++;
front = (front + 1) % SIZE;
if(count > MIN)
R.signal();
}
S.G (talk) 10:37, 3 December 2016 (CET)
Soluzione di Stefano Zaniboni
/*esercizio 1*/
monitor mMbb{
object[] buffer; //spazio di memorizzazione
final int MAXELEM; // numero massimo di elementi che ci possono essere nel buffer
final int MINELEM; //numero minimo di elementi --> numero di scritture minime
condition okW; // dove mi fermo se non posso scrivere
condition okR; // dove mi fermo se non posso leggere
int count; // elementi presenti nel buffer
int front; // contatore al elemento prodotto
int rear; // contatore al elemento consumato
mMbb(){
buffer = new Object[MAXELEM];
count = rear = front = 0;
}
procedure entry object read(){
if ((count < MINELEM)) //se il buffer e' pieno oppure non ci sono min elem chiamo la wait
okR.wait();
eltype val = buffer[rear]; // assegno al val l'elemento che ho letto e poi aggiorno rear
rear = ((rear + 1) % (MAXELEM -1 )); // aggiorno rear;
count--; // decremento count per dire che ho consumato un elemento
okW.signal(); // qui faccio signal sui produttori che adesso possono scrivere
return retval;
}
procedure entry void write(int val){
if (count == buffer.length) //se il buffer e' pieno mi fermo
okW.wait();
buffer[front] = val; //scrivo elemento
count++; //aggiorno i prodotti disponibili
front = ((front+1)%(MAXELEM - 1)); // aggiorno il contatore front a puntare nella prossima posizione
okR.signal();
}
}
Soluzione di Sav
monitor mMbb {
condition oktowrite, oktoread
int waitingW = 0, waitingR = 0
buffer buffermM
procedure entry write(val) {
if ( buffermM.len()>= MAX)
waitingW++;
oktowrite.wait();
waitingW--;
buffermM.enqueue(val);
buffermM.enqueue(val);
while(buffermM.len()>= MIN)
oktoread.signal(); }
procedure entry read() {
if (buffermM.len()< MIN)
waitingR++;
oktoread.wait();
waitingR--;
buffermM.dequeue();
oktowrite.signal();
buffemM.dequeue();
oktowrite.signal();
}
Esercizio c.2
Soluzione di S.G
/*
* Esercizio c.2: Facendo uso di semafori scrivere la funzione rendezvous che consenta ai processi di sincronizzarsi secondo le
* seguenti specifiche:
* – Ogni processo indica come parametro della funzione rendezvous con quanti altri processi vuole sincronizzarsi.
* – M processi che chiamano la rendezvous con parametro N rimangono bloccati se M<N.
* – Quando l'N-mo processo richiama la rendezvous specificando N come parametro, lui e gli N-1 sospesi devono proseguire
* nelle propria esecuzione
*/
struct S {
Semaphore sem;
int N; // parametro della funzione rendezvous con quanti altri processi vuole sincronizzarsi
int I; // Contatore dei processi che richiamano rendezvous con paramentro N
}
List<S> listS = new List[]; // Lista di possibili semafori
Semaphore mutex = new Semaphore(1); // Variabile che consente la mutua esclusione
rendevouz(int n){
mutex.P(); // Ottengo la mutua esclusione
find = FALSE;
for(s in listS){ // Cerco il semaforo nella lista
if(s.N == n){
find = TRUE;
break;
}
}
if(find == FALSE){ // se non è presente nella lista lo creo
struct S s;
s.sem = new semaphore(0);
s.N = n;
s.I = 0;
listS.insert(s);
}
s.I++;
if(s.I == s.N){ // Quando l'N-mo processo richiama la rendezvous specificando N come parametro
while(s.I--) // lui e gli N-1 sospesi devono proseguire nelle propria esecuzione
s.sem.V();
}
else if(s.I < s.N){ // M processi che chiamano la rendezvous con parametro N rimangono bloccati se M<N
s.sem.P();
}
mutex.V(); // Rilascio la mutua esclusione
}
Ho qualche dubbio su questa soluzione, riguardo la linea presente l'istruzione s.sem.P(), il processo viene immediatamente bloccato? Se si dovrei rilasciare la mutua esclusione prima quindi? S.G (talk) 16:43, 3 December 2016 (CET)
Si, la mutua esclusione va, in linea di principio, sempre rilasaciata prima di un' operazione P() poichè il processo che la chiama potrebbe bloccarsi tenendo con se la mutua esclusione e causando quindi deadlock.--FedericoP (talk) 10:37, 15 January 2017 (CET)
Soluzione di MV
// ------------------------- SOLUZIONE DI MV -------------------------
void rendezvous(int N)
{
struct S { Semaphore sem; int N; int M };
static List<struct S> L = new List<struct S>();
static Semaphore mutex = new Semaphore(1);
if(N <= 1) // se N==1 significa che non vuole sincronizzarsi
return; // se N<1 non ha senso => esce dalla funzione
bool trovato = false;
mutex.P(); // prende la mutua esclusione per evitare incoerenze
// scorre la lista in cerca di un semaforo per N
for(List<struct S> el = L.head(); !L.last(el) && !trovato; el = L.next(el) )
if(el.content.N == N) // se esiste
{
trovato = true;
if(el.content.M == N-1) // se è l'N-esimo processo
{
while(el.content.M) // sblocca tutti gli altri
{
el.content.sem.V();
el.content.M--;
}
mutex.V();
}
else // altrimenti si mette in attesa
{
el.content.M++;
mutex.V();
el.content.sem.P();
}
break;
}
if(!trovato) // se non esiste lo crea
{
// NB: ho ancora la mutua esclusione
struct S s;
s.N = N;
s.M = 1;
s.sem = new Semaphore(0);
L.insert_tail(S) // inserisce nella lista (in coda)
mutex.V():
// si mette in attesa sul semaforo appena creato (NB: N!=1)
L.tail().content.sem.P();
}
}
/* NOTA: gli elementi della lista non vengono deallocati una volta liberato
il semaforo; questo perchè è ancora possibile una race condition (rara)
nel caso in cui un processo P1 stia per inserirsi su un semaforo già esistente
(ha appena fatto mutex.V() ) e un altro P2 riesca ad entrare nel ciclo e
liberare tutti => P2 effettua una V in più e P1 esce subito dalla P
*/
Soluzione di Alexp
List<Queue<Semaphore>> waiting; //Lista di code di semafori
Semaphore mutex = 1; //Semaforo per modificare la lista delle code
void rendezvous(int N){
if(N >= 2){
//semaforo da accodare(e su cui si dovrà bloccare il thread nel caso waiting[N].size() < N)
Semaphore s = 0;
int i;
//entriamo nella critical section per modificare una struttura condivisa
mutex.P();
//se il chiamante non è l'N-esimo thread
if(waiting[N].size()+1 < N){
//accodiamo il semaforo nel caso non ci siano esattamente N thread con cui sincronizzarsi
waiting[N].enqueue(s);
//usciamo dalla critical section per non causare deadlock
mutex.V();
//fermiamo il thread sul semaforo accodato prima, nel caso in cui debba aspettare
//questo thread verrà risvegliato dall'N-esimo thread che si sincronizzerà
s.P();
}
//se il thread chiamante è proprio l'N-esimo(quindi dovrà sbloccare tutti)
else{
//per ogni thread accodato sulla coda in cui si sincronizzano N thread
/*
(in realtà nella coda ci sono N-1 semafori dei thread fermi
mentre il thread che entra in questo ramo else sarà l'N-esimo)
*/
for(i = 0; i < N-1; i++){
//togliamo dalla coda il semaforo e risvegliamo il thread che lo aspettava
waiting[N].dequeue().V();
}
//struttura condivisa modificata, usciamo dalla critical section
mutex.V();
}
}
}