Qui accade che prenoto il mio accesso, e quando l'altro ha finito tocca a me. Quindi non c'è alternanza stretta tra processi, come nell'Algoritmo 1. Tuttavia, il progresso dei processi qui non è garantito perché il processo lento comunque fa durare a lungo il suo turno.
Algoritmo 3
Ho due flag, più la variabile di turno. Le flag sono inizializzate a 0, e il turno a turno_0.
La variabile turno serve per dire a chi tocca. La flag è invece la prenotazione. È un po' la combo dei due precedenti algoritmi.
Devo controllare se l'altro NON ha prenotato, e che NON sia il suo turno.
entraSezioneCritica(int pid) {
int altro = 1 - t;
turno = altro;
if (pid == 0) {
flag0 = true;
while ((flag1) && (turno = altro)) {
Thread.yield();
}
}
else {
flag1 = true;
while((flag0) && (turno = altro)) {
Thread.yield();
}
}
}
Questo sistema garantisce mutex e progresso, perché non rimane bloccato a causa di prenotazioni, grazie alla doppia condizione del while.
Variabile di lock
È un cambio di punto di vista rispetto alla variabile di turno: non sono i processi ad alternarsi, ma è la risorsa stessa a dire se è disponibile o no.
Una variabile di lock assume due valori: 0 se è libera, 1 se è occupata.
Per acquisire una risorsa, devo seguire questi passi:
- disabilitare le interruzioni
- leggere il lock: se è 0 lo metto a 1 e spaciugo io, e riabilito le interruzioni
- se è a 1 riabilito le interruzioni e aspetto
- per rilasciare la risorsa, metto il lock a 0
Le interruzioni vanno bloccate perché le operazioni di lettura ed eventuale scrittura di un lock sono realizzate con più di una singola istruzione in linguaggio macchina. Dalle prime lezioni sappiamo che la singola istruzione macchina è atomica, cioè non può essere interrotta, ma una sequenza di istruzioni invece sì. Quindi, trattandosi qui di una sequenza di istruzioni, può capitare che qualche processo si infili in mezzo e legga la mia stessa variabile di lock.
C'è anche dell'hardware che è stato progettato in modo tale da scrivere variabili di lock con un'istruzione sola, la test-and-set che fa tutto in automatico.
Il problema di questo approccio è che il programmatore deve mettersi a spaciugare con gli int, e ciò non è una cosa buona e giusta.
Lezione 3 - I Semafori
Per evitare di fare affidamento sui programmatori, occorre che sia il SO a gestire sto ambaradan dei lock, che sappiamo che si comporta bene. In caso contrario occorrerebbe dare ai singoli programmi il permesso di gestire le interruzioni, ma non è una cosa positiva.
Inoltre, le variabili di turno, come abbiamo visto sopra, devono essere inizializzate e gestite a seconda del numero di processi che accedono alla stessa risorsa, e nella grande maggioranza dei casi questo numero non è predicibile a priori. I lock invece scalano benissimo, perché non importa quanti sono i processi che vogliono quella risorsa, che tanto il lock è sempre o lbero od occupato.
Ecco quindi che si inventano i 'semafori, ovvero un meccanismo scalabile per separare i processsi dalla risorsa che vogliono, e spostando la gestione dei lock dal programmatore al SO, il quale so che non dovrebbe fare pasticci.
Semaforo binario
Può assumere due valori, che per convenzione sono l'inverso di quelli del lock: 1 = libero (verde, se preferite), 2 = in uso.
Il semaforo si manipola con le chiamate acquire(S) e release(S). Sono chiamate di sistema, quindi per definizione atomiche (a meno di kernel realtime etc. etc. ma è un'altra faccenda).
Se un processo vuole entrare in una sezione critica, chiama la acquire(S), esegue e poi chiama la release(S). Ci pensa il SO a ordinare le priorità e così via, in caso siano supportate (e in questo caso andranno passate come parametro alle acquire(S)).
Implementazione
Si potrebbe pensare di mettere il processo in attesa attiva, quando ha trovato il semaforo rosso e aspetta quello verde. Ma c'è un problema, e il problema è che il processo dovrebbe continuare, al suo turno, a controllare se il semaforo ha cambiato finalmente colore, e quindi consumerebbe CPU.
Si preferisce quindi mettere il processo che ha trovato rosso in una coda dei processi relativa alla risorsa in oggetto.
Semaforo generalizzato
Posso avere una variabile S = n, che mi dice che ho n risorse di quel tipo libere. Ogni volta che qualcuno fa una acquire(S), scalo la variabile n. Quando arriva a 0, la acquire(S) si blocca.
Ciò garantisce la mutex e il progresso, ma cmq è lasciato al programmatore il compito di ricordarsi di chiamare i semafori.