cerca
Sistemi Operativi - Lezione mattutina del 18 marzo 2008
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.Piuri18Marzo2008Mattina History

Hide minor edits - Show changes to output

Changed lines 22-23 from:
http://www.google.it/search?q=ide+sata+adapter&ie=UTF-8&oe=UTF-8
to:
Changed lines 2-3 from:
%titolo%''':: Sistemi operativi - Lezione mattutina del 18 marzo 2008.
to:
%titolo%''':: Sistemi operativi - Lezione mattutina del 18 marzo 2008 ::'''
Changed lines 4-6 from:
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 hanno pubblicato sulla [[pagina di SO -> Sistemi Operativi]].
to:
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 -> Sistemi Operativi]].
Changed lines 22-23 from:
to:
http://www.google.it/search?q=ide+sata+adapter&ie=UTF-8&oe=UTF-8
Changed line 87 from:
if (t == 0) flag0 = false;
to:
if (pid == 0) flag0 = false;
Changed lines 91-92 from:
to:
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.


%sottotitolo%'''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.
Changed lines 62-64 from:
to:
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 (t == 0) flag0 = false;
else flag1 = false;
}
Changed lines 26-27 from:
to:
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
Added lines 13-27:

!!!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.


%sottotitolo%'''Lezione 2 - Le variabili di lock'''

Added lines 7-12:
%sottotitolo%'''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.
Changed line 7 from:
[[Torna alla pagina di SO - > SistemiOperativi]]
to:
[[Torna alla pagina di SO -> SistemiOperativi]]
Added lines 1-7:
(:title Sistemi Operativi - Lezione mattutina del 18 marzo 2008:)
%titolo%''':: 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 hanno pubblicato sulla [[pagina di SO -> Sistemi Operativi]].


[[Torna alla pagina di SO - > SistemiOperativi]]