:: Sistemi operativi - Lezione mattutina del 18 marzo 2008 ::
OCIO: siccome il pomeriggio non c'ero, non ho preso appunti e non posso quindi scriverli! Fate quindi riferimento a quelli che Lara Rossa e Teto e Guido hanno pubblicato sulla pagina di SO.
Lezione 1 - Processi concorrenti
Abbiamo visto sinora la cooperazione tra processi, ora vediamo la concorrenza, che si ha quando si vuole accedere a risorse condivise, usabili solo in mutua esclusione.
Posso ammettere 2 processi alla stessa risorsa solo se le operazioni che vogliono compiervi NON sono in contrasto tra di loro, come ad esempio 2 letture da un file. Le risorse di cui occorre sincronizzare l'uso possono essere fisiche o informative.
Corsa critica
C'è una zona di memoria condivisa, un buffer, che da qualche parte ha segnato il numero di messaggi che contiene. Un processo scrivente scrive fino a che ci sono messaggi disponibili. Un processo leggente legge finché ci sono messaggi. Se i processi non vengono sincronizzati, può darsi che la variabile che contiene il numero di messaggi nel buffer non sia corretta. Ad esempio, lo scrittore scrive solo se il buffer è vuoto. Ora il buffer è pieno, quindi non può scrivere, ma il processo che legge diventa attivo. Il processo che legge DIMINUISCE la variabile che indica la dimensione del buffer, ma prima di leggere EFFETTIVAMENTE, il SO lo sospende e riattiva lo scrittore. Lo scrittore vede che c'è ancora spazio per un messaggio, e scrive, di fatto sovrascrivendo il messaggio precedente.
Questi problemi si chiamano corsa ritica delle operazioni su una variabile condivisa, e la sezione critica è la sezione di codice che può generare corse critiche se eseguita in modo concorrente. Può, non è che deve, e in effetti potrebbe non accadere mai, ma quella volta che succede sono dolori.
Le sezioni critich di codice quindi devono avere accesso esclusivo alle variabili condivise, e devono spicciarsela in modo rapido perché se no gli altri che attendono quella stessa risorsa non arrivano più.
2 processi cooperanti si possono invece sincronizzare: l'uno dà il via libera all'altro, e l'altro non parte finché non riceve il via libera, e quindi le loro evoluzioni sono sincronizzate.
Lezione 2 - Le variabili di lock
Vediamo qui un po' di tipi di variabili di lock.
Variabile di turno
È una variabile condivisa tra i processi che vogliono la risorsa, e dice QUALE processo può usare la risorsa in quel turno. È quindi un accesso in mutua esclusione (d'ora in poi abbrevio con mutex).
Algoritmo 1
Ho due processi, 0 e 1. Ho una variabile all'inizio messa a 0, e indica che è il turno di 0. Finché la variabile turno è diversa dal mio pid, io attendo. Controllo la variabile turno PRIMA di entrare nella sezione critica. Quando ho finito la sezione critica, lascio il mio turno e lo faccio diventare quello dell'altro.
Ecco un po' di pseudo-java.
inizializza() {
turno = 0;
}
entraSezioneCritica(int pid) {
while (turno != pid) {
Thread.yield(); // faccio riposare il mio thread
}
}
esciSezioneCritica(int pid) {
turno = 1 - pid,
}
Il codice 1 - t realizza il trucchetto: se sono 0, turno diventa 1, e viceversa.
Il codice che chiama farà così:
entraSezioneCritica(mioPid);
// Codice critico
esciSezioneCritica(mioPid);
Se è il suo turno, esegue, altrimenti attenderà durante la chiamata di entraSezioneCritica(pid).
Questo sistema garantisce la mutex, ma non garantisce il progresso, perché i processi sono sempre alternati, e un processo lento rallenta quello veloce, che è obbligato ad aspettare il suo turno.
Algoritmo 2
Imposto due flag a false all'inizio, ognuna associata ad un processo. Quando entro nella sezione critica la mia flag viene messa a true, e attendo che anche l'altra flag venga messa a false. Quando esco, metto la mia flag a false
boolean flag0, flag1;
inizializza() {
flag0 = false;
flag1 = false;
}
entraSezioneCritica(int pid) {
if (pid == 0) {
flag0 = true;
while (flag1 == true) {
Thread.yield();
}
}
else {
flag1 = true;
while (flag0 = true) {
Thread.yield();
}
}
}
esciSezioneCritica(int pid) {
if (pid == 0) flag0 = false;
else flag1 = false;
}
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.
Torna alla pagina di SO
