Sistemi Operativi

Sistemi Operativi
Lezione 7-bis
Esercizi
Esercizio
• Problema dei lettori e scrittori
• Un insieme di processi condivide un file dal quale
alcuni possono solo leggere i dati, altri solo
scriverli
• Più lettori possono leggere simultaneamente
• Un solo scrittore per volta può scrivere
• Quando uno scrittore scrive, nessun lettore può
leggere
• Diverso da Prod/cons
• i lettori non modificano i puntatori al buffer
• i produttori leggono i puntatori, gli scrittori no
AA 2001/02
©Bruschi, Rosti
2
Corso: Sistemi Operativi
Esercizio
• Sviluppare una soluzione al problema
della corretta sincronizzazione degli
accessi
• 1 scrittore, 1 lettore
• accessi in mutua esclusione al file
• sia dello scrittore sia del lettore rispetto a questo
• 1 scrittore, n lettori
• n scrittori, n lettori
• considerare chi ha priorità, lettori o scrittori
AA 2001/02
©Bruschi, Rosti
3
Corso: Sistemi Operativi
M scrittori, n lettori con priorità
• Gli scrittori aspettano che tutti i lettori
abbiano terminato
• Gli scrittori scrivono in mutua esclusione
• I lettori devono sapere quanti sono
• Se c’è un solo lettore, deve aspettare che
eventuali scrittori finiscano
• Lettori che arrivano quando altri stanno già
leggendo procedono senza aspettare
AA 2001/02
©Bruschi, Rosti
4
Corso: Sistemi Operativi
M scrittori, n lettori con priorità
Lettori_scrittori();
int numlett;
/* contiamo solo i lettori perché gli scrittori li aspettano */
semaphore x = 1, scritt = 1;
/* x per contare I lettori correttamente; scritt per la mutua esclusione */
{
numlett = 0;
parbegin
lettore; scrittore;
parend
}
AA 2001/02
©Bruschi, Rosti
5
Corso: Sistemi Operativi
M scrittori, n lettori con priorità
scrittore();
{
while TRUE do {
down(scritt):
scrivi_dato();
up(scritt);
}
}
AA 2001/02
©Bruschi, Rosti
6
lettore();
{
while TRUE do {
down(x);
numlett = numlett + 1;
if numlett == 1
down(scritt);
up(x);
leggi_dato();
down(x);
numlett = numlett - 1;
if numlett == 0
up(scritt);
up(x);
}
}
Corso: Sistemi Operativi
M scrittori, n lettori con priorità
• Che tipo di semafori abbiamo usato?
• Si potrebbe usare un semaforo generalizzato
per contare i lettori?
• Cosa succede nei seguenti casi
• Solo lettori presenti
• Solo scrittori presenti
• Lettori e scrittori presenti ma
• un lettore è arrivato primo
• uno scrittore è arrivato primo
• I lettori continuano ad arrivare prima che l’ultimo
finisca
• In coda su scritt ci sono sia lettori che scrittori
AA 2001/02
©Bruschi, Rosti
7
Corso: Sistemi Operativi
M scrittori con priorità, n lettori
• I lettori si bloccano se c’è almeno uno
scrittore che ha segnalato di voler accedere
ai dati
• Dobbiamo sapere quanti sono gli scrittori
• L’aggiornamento del numero di scrittori deve
essere fatto in mutua esclusione
• Quando c’è un solo scrittore, aspetta sulla
coda dei lettori per ragioni di priorità
AA 2001/02
©Bruschi, Rosti
8
Corso: Sistemi Operativi
M scrittori con priorità, n lettori
lettore();
{
while TRUE do {
aggiorna il numero di lettori
in mutua esclusione;
se c’e` un solo lettore, lascia
passare gli scrittori;
leggi_dato();
aggiorna il numero di lettori
in mutua esclusione;
se non ci sono piu` lettori,
lascia passare gli scrittori;
}
}
AA 2001/02
©Bruschi, Rosti
scrittore();
{
while TRUE do {
aggiorna il numero di scrittori
in mutua esclusione;
se c’e` un solo scrittore,
aspetta che i lettori finiscano;
scrivi_dato() in mutua
esclusione;
aggiorna il numero di scrittori
in mutua esclusione;
se non ci sono piu` scrittori,
lascia passare i lettori;
}
}
9
Corso: Sistemi Operativi
M scrittori con priorità, n lettori
Lettori_scrittori();
int numlett, numscritt;
semaphore x = 1, y = 1, lett = 1, scritt = 1;
/* x per contare I lettori, y per gli scrittori;
* scritt per la mutua esclusione degli scrittori,
* lett per fare aspettare gli uni e gli altri
*/
{
numlett = 0; numscritt = 0;
parbegin
lettore; scrittore;
parend
}AA 2001/02
©Bruschi, Rosti
10
Corso: Sistemi Operativi
M scrittori con priorità, n lettori
lettore();
{
while TRUE do {
down(lett);
down(x);
numlett = numlett + 1;
if numlett == 1
down(scritt);
up(x);
up(lett);
leggi_dato();
down(x);
numlett = numlett - 1;
if numlett == 0
up(scritt);
up(x);
}
} AA 2001/02
©Bruschi, Rosti
11
scrittore();
{
while TRUE do {
down(y);
numscritt = numscritt + 1;
if numscrit == 1
down(lett);
up(y);
down(scritt);
scrivi_dato();
up(scritt);
down(y);
numscritt = numscritt - 1;
if numscritt == 0
up(lett);
up(y);
}
}
Corso: Sistemi Operativi
M scrittori con priorità, n lettori
• Cosa succede se
• ci sono solo lettori
• ci sono solo scrittori
• per primo arriva un lettore poi lettori e
scrittori
• primo arriva uno scrittore poi lettori e
scrittori
• arrivano molti lettori poi uno scrittore
AA 2001/02
©Bruschi, Rosti
12
Corso: Sistemi Operativi
M scrittori con priorità, n lettori
Lettori_scrittori();
int numlett, numscritt;
semaphore x = 1, y = 1, z = 1, lett = 1, scritt = 1;
/* x per contare I lettori, y per gli scrittori; z per far aspettare lettori e scrittori
* su code diverse; scritt per la mutua esclusione degli scrittori,
* lett per fare aspettare un lettore e uno scrittore
*/
{
numlett = 0; numscritt = 0;
parbegin
lettore; scrittore;
parend
}AA 2001/02
©Bruschi, Rosti
13
Corso: Sistemi Operativi
M scrittori con priorità, n lettori
scrittore();
{
while TRUE do {
down(y);
numscritt = numscritt + 1;
if numscrit == 1
down(lett);
up(y);
down(scritt):
scrivi_dato();
up(scritt);
down(y);
numscritt = numscritt - 1;
if numscritt == 0
up(lett);
up(y); }
}
AA 2001/02
©Bruschi, Rosti
14
lettore();
{
while TRUE do {
down(z);
down(lett):
down(x);
numlett = numlett + 1;
if numlett == 1
down(scritt);
up(x);
up(lett);
up(z);
leggi_dato();
down(x);
numlett = numlett - 1;
if numlett == 0
up(scritt);
up(x); }
Corso: Sistemi Operativi
}
Osservazioni
• La programmazione della concorrenza con i
semafori non è facile
• P e V, Up e Down sparpagliate nel codice
• problema del corretto ordine di esecuzione di P e
V
• l’uso di P e V in ordine errato può portare a deadlock o a
violazione della mutua esclusione
• Proposte soluzioni alternative a livello di
linguaggio di programmazione
• monitor
• primitiva di sincronizzazione di alto livello
AA 2001/02
©Bruschi, Rosti
15
Corso: Sistemi Operativi
Altre soluzioni
• A livello di linguaggio di programmazione
• monitor
• costrutto di linguaggio tipo ADT
• Mediante primitive di comunicazione
• sincronizzazione mediante scambio di messaggi con
primitive bloccanti e no
• Send(destination, msg)/receive(source, msg)
• tipicamente usato in ambiente multiprocessore a
memoria distribuita
• Message Passing Interface
• complesso e poco controllabile
• problema dell’affidabilita dei canali, dell’autenticità
dei messaggi, dei nomi dei partecipanti
AA 2001/02
©Bruschi, Rosti
16
Corso: Sistemi Operativi
Monitor
• Collezione di procedure, variabili, strutture
dati raccolte in un pacchetto
• i dati del monitor non sono accessibili al di fuori di
esso
• le procedure del monitor accedono ai dati
condivisi
• un processo può chiamare le procedure del
monitor ovunque ma una sola per volta può
essere in esecuzione
• mutua esclusione
• il monitor è un costrutto di linguaggio
• il compilatore sa cosa fare nella traduzione
AA 2001/02
©Bruschi, Rosti
17
Corso: Sistemi Operativi
Monitor
I processi produttori e
consumatori eseguono
le procedure del monitor,
senza preoccuparsi della
mutua esclusione
La mutua esclusione è
implicita nell’uso del costrutto
monitor
La sezione critica è tutta
raccolta nel monitor
Più semplice da controllare
AA 2001/02
©Bruschi, Rosti
18
Corso: Sistemi Operativi
Prod-cons con Monitor
Una sola procedura del monitor è attiva alla volta
AA 2001/02
©Bruschi, Rosti
Il buffer ha N slot
19
Corso: Sistemi Operativi
Deadlock
• Un insieme di processi è in deadlock se
ciascuno di essi è in attesa di un evento che
si può verificare solo grazie ad un altro
processo dell’insieme, in una catena
• Es. Due processi A e B usano lo stesso file in
modo esclusivo e la stessa stampante durante la
loro esecuzione. All’istante t A acquisisce il file indi
viene sospeso, la CPU viene assegnata a B che
acquisisce la stampante e poi si mette in attesa
del file; quando la CPU torna ad A, A si mette in
attesa della stampante
• A questo punto nessuno dei due è più in grado di
proseguire
AA 2001/02
©Bruschi, Rosti
20
Corso: Sistemi Operativi
Deadlock
•
Il deadlock è caratterizzato da 4 condizioni
necessarie
1. Accesso alle risorse in mutua esclusione
2. Hold and Wait
•
processi in possesso di risorse possono continuare a
richiederne delle nuove, senza cedere quelle già
acquisite anche se rimangono bloccati in attesa
3. Le risorse non sono prelazionabili
4. Attesa circolare
•
AA 2001/02
©Bruschi, Rosti
due o più processi sono in attesa di risorse usate da un
altro del gruppo
21
Corso: Sistemi Operativi
Deadlock
• In genere sono usate 4 strategie per far
fronte al deadlock
• Ignorarlo
• Rilevamento e ripristino
• detection and recovery
• Dynamic avoidance
• si usa un’attenta strategia di allocazione risorse
• Prevention
• si tratta di fare in modo che una delle 4
condizioni necessarie non si verifichi mai
AA 2001/02
©Bruschi, Rosti
22
Corso: Sistemi Operativi