[semafori] Imbuto

Si devono sincronizzare un certo numero di thread “pallina” in modo che entrino in un imbuto solo a gruppi di una dimensione prefissata. Il thread principale sblocca un numero preciso di thread pallina che entrano e, dopo un certo tempo, escono dall’imbuto. Solo nel momento in cui sono usciti tutti, il thread principale sblocca il successivo gruppo.

Lo schema del thread principale è il seguente:

inizializza_sem(); // inizializza i semafori

while(ci sono ancora palline) {
    sblocca(N); // sblocca N palline, che entreranno nell'imbuto
    attendi(N); // attendi che N palline siano uscite dall'imbuto
}

distruggi_sem(); // distruggi i semafori

Lo schema del thread “pallina” è il seguente:

entra_imbuto(); // attende di entrare nell'imbuto

// entra nell'imbuto e percorri tutta la strada verso il fondo

esci_imbuto(); // esce dall'imbuto

L’obiettivo della verifica è di implementare le 4 funzioni di sincronizzazione tramite semafori (più le 2 funzioni per inizializzare e eliminare i semafori) in modo da realizzare il comportamento richiesto. Le funzioni da implementare sono nel file soluzione.c che viene incluso da imbuto.c (scarica lo zip).

Soluzione

Ecco una possibile soluzione commentata della verifica:

[sourcecode lang=”C”]
/*
* COMMENTO GENERALE:
*
* Utilizziamo due semafori. Immaginiamo che ogni semaforo
* corrisponda a una risorsa e il suo valore alla disponibilità
* di tale risorsa:
*
* – sem_imbuto: corrisponde alla risorsa imbuto, che le palline
* richiedono per poter accedervi. Inizialmente vale 0
* (rosso) in quanto le palline devono attendere che il
* thread principale conceda loro l’accesso;
*
* – sem_pallina: corrisponde alla risorsa pallina che ha percorso
* l’imbuto fino all’uscita. Inizialmente vale 0 perché
* nessuna pallina è ancora transitata. Il thread principale
* attende la fuoriuscita delle palline su questo semaforo.
*
* Sincronizzazione:
*
* Thread pallina: per accedere all’imbuto la pallina effettua
* una wait sul semaforo sem_imbuto (funzione entra_imbuto) che
* ne regola, appunto, l’accesso. Quando esce dall’imbuto
* segnala la sua presenza facendo una post sul semaforo
* sem_pallina (funzione esci_imbuto), che conta quante palline
* sono transitate attraverso l’imbuto.
*
* Thread principale: il thread principale sblocca n palline
* effettuando n post sul semaforo sem_imbuto (fun. sblocca(n)).
* Intuitivamente è come se concedesse n risorse imbuto alle
* palline che le stanno richiedendo. Poiché ogni pallina fa
* una singola wait (chiede una risorsa imbuto), ogni post
* sbloccherà esattamente un thread pallina in attesa. Quindi
* le n post sbloccheranno n palline, come richiesto.
* Il thread principale, in seguito, attende la fuoriuscita
* di n palline effettuando n wait sul semaforo sem_pallina
* (funzione attendi(n)). Poiché il semaforo è inizializzato
* a 0 il thread si sbloccherà dalle n wait solo quando n
* thread pallina effettueranno le relative post, ovvero
* quando usciranno dall’imbuto (funzione esci_imbuto), come
* richiesto.
*
* Riconduzione a un problema standard: la soluzione è, di
* fatto, una variante del produttore-consumatore in cui
* i thread pallina consumano una risorsa imbuto, prodotta
* a "lotti" di n dal thread principale, e il thread principale
* consuma la risorsa pallina, prodotte dagli n thread pallina
* che fuoriescono dall’imbuto. Come per le celle piene e
* vuote del buffer nel produttore-consumatore, si utilizzano
* due semafori contatori. La sincronizzazione, però, è
* alternativamente:
*
* – uno a molti: il thread principale che sblocca n thread
* pallina (effettuando n post, che concedono n risorse)
*
* – molti a uno: gli n thread pallina che sbloccano il thread
* principale (in attesa su n wait, che allocano n risorse)
*/

// dichiarazione semafori
sem_t sem_imbuto, // regola l’accesso all’imbuto
sem_pallina; // regola la fuoriuscita dall’imbuto

// inizializza i semafori
void inizializza_sem() {
// i semafori sono inizializzato a 0 in quanto, inizialmente,
// non ci sono risorse imbuto o pallina disponibili:
// tutte le wait saranno bloccanti.
sem_init(&sem_imbuto,0,0); // nessun accesso all’imbuto
sem_init(&sem_pallina,0,0); // nessuna pallina è ancora fuoriuscita
}

// distruggi i semafori
void distruggi_sem() {
sem_destroy(&sem_imbuto); // elimina il semaforo imbuto
sem_destroy(&sem_pallina); // elimina il semaforo pallina
}

// attende di entrare nell’imbuto
void entra_imbuto() {
// per accedere all’imbuto la pallina effettua una wait sul
// semaforo imbuto che ne regola, appunto, l’accesso:
// di fatto, consuma una risorsa imbuto.
sem_wait(&sem_imbuto);
}

// esce dall’imbuto
void esci_imbuto() {
// Quando la pallina esce dall’imbuto segnala la sua presenza
// facendo una post sul semaforo pallina, che conta quante
// palline sono transitate attraverso l’imbuto: produce una
// risorsa pallina.
sem_post(&sem_pallina);
}

// fa entrare n thread "pallina" nell’imbuto
void sblocca(int n) {
// Il thread principale sblocca n palline effettuando n post
// sul semaforo imbuto: produce n risorse imbuto.
int i;
for (i=0;i<n;i++) sem_post(&sem_imbuto);
}

// attende che n thread "pallina" escano dall’imbuto
void attendi(int n) {
// Il thread principale attende la fuoriuscita di n palline
// effettuando n wait sul semaforo pallina: consuma n risorse
// pallina
int i;
for (i=0;i<n;i++) sem_wait(&sem_pallina);
}
[/sourcecode]