Semafori
il problema produttori-consumatori spesso viene risolto usando i semafori, e viene fatto in questo modo:
// Inizializzazione
int N = 100 // Dimensione massima del buffer
semaphore mutex = 1 // Lucchetto per il buffer (1 = libero)
semaphore empty = N // All'inizio, tutti gli N slot sono vuoti
semaphore full = 0 // All'inizio, ci sono 0 elementi da consumare
// -----------------------------------------------------------------
function producer() {
while (true) {
item = produce_item() // Crea un nuovo dato (fuori dalla sezione critica)
down(empty) // C'è spazio? Se no, mi blocco e aspetto. Se sì, occupo uno slot "vuoto" (-1)
down(mutex) // Prendo il lucchetto per accedere al buffer
insert_item(item) // SEZIONE CRITICA: Inserisco l'elemento in modo sicuro
up(mutex) // Rilascio il lucchetto del buffer
up(full) // Segnalo che c'è un nuovo slot "pieno" (+1), svegliando il consumer se dormiva
}
}
// -----------------------------------------------------------------
function consumer() {
while (true) {
down(full) // C'è roba da leggere? Se no, mi blocco e aspetto. Se sì, "consumo" uno slot pieno (-1)
down(mutex) // Prendo il lucchetto per accedere al buffer
item = remove_item() // SEZIONE CRITICA: Rimuovo l'elemento in modo sicuro
up(mutex) // Rilascio il lucchetto del buffer
up(empty) // Segnalo che si è liberato un nuovo slot "vuoto" (+1), svegliando il producer se dormiva
consume_item(item) // Faccio qualcosa con il dato (fuori dalla sezione critica)
}
}
abbiamo principalmente solo due operazioni: up e down, che incrementano/decrementano il contatore passato come parametro, è importante che il contatore non sia mai negativo.
Mutex e thread utente
Tra i thread utente che fanno riferimento ad un unico processo modello 1 a molti i mutex si possono usare in modo efficiente facendo uso di TSL (o XCHG)
CITE
Ricordiamo:
- TSL (Test and Set Lock): È un’istruzione hardware che esegue due operazioni contemporaneamente e in modo indivisibile: legge il valore di una locazione di memoria (il “lock”) copiandolo in un registro della CPU, e subito dopo imposta (scrive) quella stessa locazione di memoria a un valore non nullo (solitamente
1, per indicare che la risorsa è “occupata”).
- A cosa serve: Se il valore letto era
0, il processo capisce che il lucchetto era libero, lo ha appena chiuso a chiave (1) ed entra nella sua sezione critica. Se il valore letto era1, sa che qualcun altro è già dentro e continua a ciclare (Spinlock) finché non si libera.- XCHG (Exchange) (nota: spesso la troverai scritta
XCHGinvece diXHCG, tipica delle CPU x86): È un’istruzione hardware alternativa al TSL che scambia (exchange) in modo atomico il contenuto di un registro della CPU con il contenuto di una locazione di memoria.
- A cosa serve: Il meccanismo è simile al TSL. Un processo mette il valore
1in un suo registro interno e poi esegue laXCHGcon la variabile di lock in memoria. Dopo lo scambio, il processo controlla il suo registro: se c’è uno0, significa che ha “rubato” lo zero alla memoria lasciandoci un1(ha acquisito il lock). Se c’è un1, il lock era già preso e deve riprovare.
L’implementazione di queste due istruzioni cambia e andremo ad usare delle primitive introdotte precedentemente (thread_yield)
FUTEX (Fast Userspace Mutex) Garantiscono prestazioni eccellenti riducendo drasticamente le costose chiamate di sistema (system call). L’idea chiave è tentare di gestire il lock interamente in modalità utente. Si compongono di due elementi:
- Libreria utente: Tenta di acquisire il lock usando istruzioni hardware atomiche (come le TSL o XCHG viste prima). Se il lock è libero, lo prende e ritorna istantaneamente. Non essendoci chiamate al sistema operativo, l’operazione è velocissima.
- Servizio kernel: Interviene solo in caso di contesa. Se la libreria utente trova il lock già occupato, effettua una chiamata a sistema per chiedere al kernel di bloccare il processo (mettendolo in sleep) e accodarlo finché la risorsa non si libera.
Monitor
Sono delle astrazioni di alto livello che offrono una gestione semplice della mutua esclusione, che sollevano il programmatore della responsabilità di usare bene i mutex.
TIP
I semafori sono universali non essendo legate al linguaggio di programmazione, sono delle chiamate a sistema a differenza dei monitor che sono dei costrutti di più alto livello.
Quando i linguaggi di programmazione introducono i monitor molto spesso integrano anche una gestione autonoma dei thread, per garantire la sincronizzazione il monitor crea una variabile condizione sulla quale esercita i wait e signal
Distrazione
Ha discusso la signal
- fatta da Haore (so solo che non è stata mai implementata)
- Mesa: implementazione usata anche da Java
- concurrent Pascal: nessuna la usa, ma usa un approccio diverso
Di seguito la soluzione dei produttori-consumatori ma usando i monitor
Scambio messaggi tra processi
Questo approccio utilizza due primitive ad alto livello fornite dal sistema operativo: send e receive.
I concetti chiave da ricordare sono tre:
- Sincronizzazione implicita (Blocchi): La
receiveè tipicamente bloccante: se non ci sono messaggi da leggere, il processo si mette in attesa. Anche lasendpuò esserlo: se assumiamo che ci sia un buffer di appoggio con capienza finita N, e questo buffer è pieno, chi spedisce si blocca finché non si libera spazio. - Indirizzamento: Può essere diretto (il mittente specifica il PID esatto del destinatario) oppure indiretto tramite una mailbox (una “cassetta della posta” condivisa da cui i processi pescano i messaggi).
- Scalabilità: Il grande vantaggio di questo approccio è che non richiede memoria condivisa. Per questo motivo è facilmente estendibile a sistemi distribuiti, permettendo a processi su computer diversi di comunicare via rete (ad esempio usando le librerie MPI).
Il Codice (Produttore-Consumatore): risolvere il problema del Bounded-Buffer in questo modo è elegantissimo. Il producer impacchetta il dato e fa una send; il consumer fa una receive e lo estrae. Tutta la complessità dei semafori visti in precedenza qui è gestita “dietro le quinte” dal sistema di messaggistica del sistema operativo!