Problema dei Fumatori di sigarette Problema dei Fumatori di

Problema dei Fumatori di
sigarette
1
•  3 processi “fumatori”
•  1 processo “tabaccaio”
•  Ogni fumatore esegue ripetutamente un ciclo in cui
prepara una sigaretta e poi la fuma
•  Per preparare la sigaretta un fumatore ha bisogno di 3
ingredienti (risorse):
–  tabacco
–  carta
–  fiammiferi
Problema dei Fumatori di
sigarette
2
•  Ogni processo “fumatore” possiede un solo ingrediente
(risorsa) in quantità illimitata:
–  fumatore 1 possiede il tabacco
–  fumatore 2 possiede la carta
–  fumatore 3 possiede i fiammiferi
•  Il tabaccaio possiede in infinita quantità tutti e tre gli
ingredienti
Problema dei Fumatori di
sigarette
3
•  Il tabaccaio sceglie 2 ingredienti a caso, li mette a
disposizione, e si sospende
•  Il fumatore che possiede il terzo ingrediente può
prelevare gli altri due, preparare la sigaretta e mettersi a
fumare.
•  Quando termina lo segnala al tabaccaio che si sveglia, e
il processo si ripete.
1
Problema dei Fumatori di
sigarette
4
•  scrivete 4 programmi concorrenti che simulino il
comportamento del tabaccaio e dei tre fumatori.
•  Suggerimento: avrete probabilmente bisogno di un
semaforo per controllare ogni risorsa in gioco
•  Alternativamente, potete usare un semaforo per ogni
fumatore
•  Avrete anche bisogno di un semaforo per controllare il
comportamento del tabaccaio
Problema dei Fumatori di
sigarette
5
•  Prima soluzione: usiamo 1 semaforo per ogni ingrediente +
1 semaforo per il tabaccaio
•  Inizializzazione:
–  carta = 0;
–  tabacco = 0;
–  fiammiferi = 0;
–  tabaccaio = 0;
6
Problema dei Fumatori di sigarette
Tabaccaio:
repeat
sceglie 2 ingredienti a e b
if (a == fiammiferi) signal(fiammiferi)
else if (a == tabacco) signal(tabacco)
else if (a == carta) signal(carta)
stessa cosa per l’ingrediente b
wait(tabaccaio)
until false
2
7
Problema dei Fumatori di sigarette
Fumatore 1 /* possiede il tabacco */
repeat
wait(fiammiferi)
wait(carta)
<prepara sigaretta>
<fuma>
signal(tabaccaio)
until false
8
Problema dei Fumatori di sigarette
•  Gli altri fumatori, hanno un codice analogo
–  Ad esempio, se il secondo fumatore ha la carta, farà una
wait su fiammiferi e su tabacco
•  Siamo sicuri che questa soluzione non produca deadlock o
starvation di uno dei processi?
•  Cambia qualcosa l’ordine in cui ogni fumatore esegue le
wait sui due ingredienti che gli mancano?
Problema dei Fumatori di
sigarette
9
•  Seconda soluzione: 1 semaforo per fumatore + 1 semaforo
per tabaccaio
•  Inizializzazione:
–  ha_tabacco = 0;
–  ha_carta = 0;
–  ha_fiammiferi = 0;
–  tabaccaio = 0;
3
Problema dei Fumatori di sigarette
10
Tabaccaio
repeat
sceglie ingrediente da non vendere (A)
if (A == fiammiferi) signal(ha_fiammiferi)
else if (A == tabacco) signal(ha_tabacco)
else if (A == carta) signal(ha_carta)
metti a disposizione gli altri ingredienti
wait(tabaccaio)
until false
Problema dei Fumatori di sigarette
11
Fumatore 1 /* possiede il tabacco */
repeat
wait(ha_tabacco) /* viene sbloccato quando sono
disponibili gli altri ingredienti */
<prepara sigaretta>
<fuma>
signal(tabaccaio)
until false
12
Problema dei Fumatori di sigarette
•  Gli altri fumatori, hanno un codice analogo
–  Ad esempio, se il secondo fumatore ha la carta, farà una
wait su ha_carta
•  Siamo sicuri che questa soluzione non produca deadlock o
starvation di uno dei processi?
•  quale delle due soluzioni è migliore secondo voi?
4
13
Problema del barbiere addormentato
•  In un negozio di barbiere vi sono:
–  Una sala d’attesa con N sedie
–  Una sedia del barbiere
•  Quando non ci sono clienti il barbiere dorme
•  Quando arriva un cliente:
–  se le sedie sono tutte occupate, il cliente se ne va
–  se ci sono sedie libere, il cliente aspetta di essere servito
–  se il barbiere sta dormendo, allora il cliente lo sveglia e
viene servito
Problema del barbiere
addormentato
14
•  Scrivete due programmi concorrenti che simulino il
comportamento del barbiere e del generico cliente
•  Suggerimento: avrete bisogno di contare il numero di
posti liberi, e/o il numero di clienti presenti
•  Avrete anche bisogno di indicare il fatto che il barbiere
sia occupato o meno
15
Problema del barbiere addormentato
•  Soluzione: usiamo le seguenti strutture dati:
–  1 semaforo customers per controllare l’accesso alla
sala d’attesa inizializzato a 0
–  1 semaforo barber per il barbiere inizializzato a 0
–  1 variabile waiting=0 che indica il numero di clienti in
attesa
–  1 semaforo mutex inizializzato a 1 per l’accesso
mutuamente esclusivo a waiting (e non solo...)
5
Problema del barbiere
addormentato
16
Barbiere
repeat
wait(customers) /* dormo finché la sala è vuota */
wait(mutex)
waiting = waiting –1 /* un cliente in meno in attesa */
signal(barber)
signal(mutex)
cut_hair()
until false
Problema del barbiere
addormentato
17
Cliente
wait(mutex)
if (waiting < N) {
waiting = waiting + 1 /* mi conto anch’io */
signal(customers) /* sveglio il barb. se dormiva */
signal(mutex)
wait(barber) /* se il barb. è occupato aspetto */
get_haircut()
} else signal(mutex) /* se la sala è piena me ne vado */
Problema del barbiere
addormentato
18
•  Notate: se assumiamo che sia possibile testare il valore
del semaforo “customers”, possiamo fare a meno della
variabile “waiting”.
6
Una soluzione “fair” al problema
dei Lettori-Scrittori
19
•  Strutture dati condivise:
semaphore mutex = 1, scrivi = 1 , leggi = 1;
int numlettori= 0;
•  Processo scrittore:
wait(leggi);
wait(scrivi);
…
esegui la scrittura del file
…
signal(scrivi);
signal(leggi);
Problema dei Lettori-Scrittori
20
•  Processo lettore:
wait(leggi);
wait(mutex); // mutua escl. per aggiornare numlettori
numlettori++;
if numlettori == 1 wait(scrivi); // il primo lettore ferma
// eventuali scrittori
signal(mutex);
signal(leggi);
... leggi il file ...
wait(mutex);
numlettori--;
if numlettori == 0 signal(scrivi);
signal(mutex);
7