Lezione 8 Sistemi operativi

PROBLEMA DEI CINQUE FILOSOFI:

Un altro problema introdoto per studiare la sincronizzazione

dei procesii è il problema dei 5 filosofi. Lo sccenario

descrive 5 filosofi a tavola a mangiare, ognuno ha il suo

piatto che va mangiato con 2 bacchette. Avendo a

disposizione solo una bacchetta per ogni filosofo. Questo

problema pone in evidenza il problema di gestione delle

risorse condivise.

Si può rappresentare ogni bacchetta con un semaforo,

allora ogni filosofo tenta di afferrare la bacchetta con una

wait, e la rilascia con una signal. Quindi per far si che un

filosofo possa mangiare devono andare a buon fine 2 wait.

- Dati condivisi:

Semaphore chopstick[] = new Semaphore[5];

Inizialmente tutti i semafori valgono uno.

PRIMA SOLUZIONE:

while (true) {

chopstick[i].acquire();

chopstick[(i+i)%5].acquire();

…

<mangia>

…

Chopstick[i].release();

chopstick[(i+1)%5].release();

…

<pensa>

…}

Questa soluzione è molto semplice però si nasconde una

possibilità di deadlock, ovvero se tutti i processi riescono

a fare la prima acquire, nessuno riesce a fare la seconda.

Una soluzione banale ma funzionale sarebbe consentire

solo a 4 processi di fare l’acquire in modo che una

bacchetta resti libera, che verà presa da uno dei 4 processi

che hanno una bacchetta. Ovviamente questa bacchetta se

la aggiudicherà un csolo processo, che , quando finirà di

mangiare, òascierà sul tavolo insieme all’altra bacchetta

utilizzata, utilizzando 2 release. A quel punto ci saranno 2

bacchette libere che verranno prese da due processi e così

il deadlock è sicuramente risolto.

MONITOR:

I semafori sono un ottima arma per la sincronizzazione dei

processi, però se non bene implemantati possono portare a

situazioni di deadlock o di starvation. Per questi motivi vi è

stata esigenza di creare un altro costrutto chiamato

monitor. Il Monitor è un costrutto di alto livello che

consente la condivisione sicura di un tipo di dati astratto

tra più thread garantendo la mutua esclusione. Può essere

implementato come una classe che racchiude variabili

condivise e condition ed esporta metodi che accedono a

tali variabili in modo atomico.

Il costrutto monitor garantisce che soltanto un processo per

volta può essere attivo nel monitor, quindi un processo ala

volta può eseguire i metodi del monitor, se un processo sta

già eseguendo i processi del monitor nessun altro processo

può eseguire nessun metodo del monitor.

Quando in Java si dichiara un monitor, è come se stessimo

dichiarando una classe (infatti in Java la classe monitor

viene richiamata come classe speciale, di tipo

syncronaized), e quindi devo dichiarare variabili e metodi.

Ad ogni istanza del monitor è associata una coda di thread

che sta attendendo di eseguire i metodi del monitor.

CONDITION:

Per consentire ad un processo di attendere all’interno del

condition:

monitor si utilizzano le

condition x,y;

Una variabile condition può essere manipolata solo

attraverso le variabili wait e signal.

L’operazione x.wait() sospende il processo fino a quando un

altro processo non lo invoca.

L’operazione x.signal() risveglia esattamente un processo.

Se nessun processo è sospeso l’operazione di signal non ha

effetto.

RAPPRESENTAZIONE CONCETTUALE DI UN MONITOR:

Monitor nome_monitor {

Dichiarazione variabili del monitor e condition;

metodo m_1 (){ … }

…

MONITOR DI HOARE E DI HANSEN:

Supponiamo che un processo P esegua x.signal() ed esista

un altro processo Q che in precedenza ha fatto una x.wait().

Questa è una situazione particolare perché P è dentro il

monitor ed esegue una signal che dovrebbe sbloccare Q

che era in attesa. Ma entrambi nel monitor non possono

starci.

- Soluzione di Hansen: Q attende che P lasci il

monitor o si metta in attesa su un’altra variabile

condition diversa da x.

- Soluzione di Hoare: P attende che Q lasci il monitor

o si metta in attesa su un’altra variabile condition

diversa da x;

Dopo una lunga discussione viene fuori che la soluzione di

Hoare è preferibile. Infatti, consentendo al processo P di

continuare, la condizione logica attesa da Q potrebbe non

valere più nel momento in cui Q viene ripreso;

Tuttavia esiste una soluzione compromesso: P deve lasciare

il monitor nel momento stesso dell’esecuzione

dell’operazione signal, in quanto viene immediatamente

ripreso il processo Q.

Questo modello è meno potente di quello di Hoare, perché

un processo non può effettuare una signal più di una volta

all’interno di una stessa procedura.

ESEMPIO CINQUE FILOSOFI:

Soluzione senza deadlock: al filosofo è permesso di

prelevare le bacchette solo se sono entrambe disponibili.

La distribuzione delle bacchette è controllata dal monitor

dining_phil.

Monitor dining_phil{

Var state [5] = {thinking, hungry, eating};

var self[5] condition;

init(){

for (int i = 0; i<=4; i++) {

state[i] = thinking;}}}

Il primo array di variabili state vuole identificare lo stato

del filosofo (che può essere di 3 tipi, thinking, hungry,

eating, in base a cosa sta facendo il filosofo). La seconda

variabile dichiarata self[5] indica le 5 bacchette, che

identificano le condition. Il costruttore è identificato dal

metodo init() che da ad ogni filosofo lo stato thinking.

Andiamo avanti a definire il codice:

Ciclo del codice del filosofo i:

while (true){

dining_phil.pickup(i);

//mangia

dining_phil.putdown(i);}

metodo pickup(int i){

state[i] = hungry;

test(i); //controlla se può mangiare

if (state[i] != eating)

self[i].wait);}

metodo putdown(int i){

state[i]= thinking;

test((i+4)%5);// controlla i vicini

test((i+1)%5); //destro e sinistro e se possibile li sblocca}

metodo test (int i){ //verifica disponibilità bacchette

if((state[(i+4)%5]!

=eating)&&(state[i]==hungry)&&(state[(i+1)%5]!=eating){

state[i] = eating;

self[i].signal();}}

- Il metodo pickup porta come argomento l’infice

posizionale del filosofo in questione nell’array dei

filosofi. Come prima istruzione cambia lo stato in

test

hungry, poi effettua il metodo sullo stesso indice,

ed infine effettua un if. Questo if controlla che il

metodo test sia andato a buon fine, infatti la sua

condizione è che se il suo stato NON è eating allora

mette il suo semaforo in wait, che potrà essere

putdown;

sbloccato dal metodo

- Il metodo test va a guardare lo stato dei suoi vicini. Se

i vicini sono nello stato eating ovviamente non sono

disponibili le bacchette poiché vuol dire che uno od

entrambi dei filosofi adiacenti stanno mangiando

quindi non ci sono le bacchette necessarie disponibili.

Oltre a verificare lo stato dei vicini controlla anche il

proprio stato, che deve ovviamente essere hungry

(passaggio, si potrebbe dire inutile per il metodo

pickup, ma utile nel secondo metodoput putdown). Se

tutte e tre le condizioni dell’if sono rispettate allora si

procede con i comandi effettivi del metodo ovvero il

cambio di stato in eating e l’operazione di signal

condition

sulla di riferimento;

- Il metodo putdown ha come argomento l’indice

posizionale del filosofo in questione nell’array dei

filosofi. Come prima istruzione porta un cambio di

stato in thinking, segno che il filosofo non sta facendo

nulla (nel caso di questo metodo, il cambio di stato sta

a significare che il filosofo ha mangiato ed ora torna a

test

pensare). Le altre 2 istruzioni vogliono mandare in

i ‘vicini’ del filosofo che ha appena finito di mangiare

(quindi del filosofo in argomento), e, se sono rispettate

tutte le condizioni dell’if all’interno di test, sblocca i

semafori dei filosofi vicini.

MONITOR IN JAVA:

In Java ogni oggetto ha associato il proprio monitor se

contiene il codice sincronizzato (metodo dichiarato come

syncronized). Una classe può avere diversi metodi, se

voglio avere metodi all’interno di un monitor (e quindi

sincronizzati) vanno dichiarati come syncronized. Se un

thread entra in un metodo syncronized ms di un

determinato oggetto O, nessun altro thread potrà entrare

in nessun metodo sincronizzato dell’oggetto O, sino a

quando il Thread T non avrà terminato l’esecuzione del

metodo ms (ovvero finchè non avrà abbandonato il

monitor dell’oggetto O). lock

P.s. Si dice che il thread T ha il dell’oggetto O,

quando è entrato nel suo monitor. Java non implementa

fisicamente il concetto di monitor di un oggetto, ma

questo è facilmente associabile alla parte sincronizzata

dell’oggetto stesso.

Java supporta meccanismi di mutua esclusione e

sincronizzazione simili a quelli del monitor, mediante le

interfaccia lock e Condition del package

java.util.concurrent.locks;

- Lock: è un costrutto per controllare l’acesso ad una

risorsa condiisa tra più thread. Un Lock garantisce

l’accesso esclusivo: soltanto un thread per volta può

acqusire il Lock ed accedere alla rete condivisa;

- Condition: è una variabile che può essere associata

ad un Lock e consente ad un thread di sospendere la

propria esecuzione fino a quando sarà notificato

(notify) da un altro thread del verificarsi di una

determinata condizione.

GESTIONE DEL DEADLOCK:

Uno stallo(deadlock) è paragonabile ad un ingorgo

stradale ad un incrocio, dove tutti gli automobilisti vogliono

passare per primi ma così facendo nessuno riesce a

informatico

passare. Dal punto di vista i deadlock

impediscono il completamento del lavoro a gruppi di

processi concorrenti. Esistono vari metodi di prevenzione di

situazioni di deadlock.

Stato di deadlock: Un insieme di processi bloccati,

ognuno dei quali possiede (= ha acquisito) una risorsa ed è

in attesa di acquisire un’altra risolta posseduta (acquisita)

da un altro processo dello stesso insieme.

Immaginiamo di modellareun sistema concorrente con tanti

thread con m risorse(CPU, spazi di memoria, dispositivi di

I/O…).Ogni tipo di risorsa (Ri) ha un certo numero di

istanze (Wi). Ogni processo utilizza una risorsa secondo il

seguente schema:

- Richiesta(request);

- Uso (use);

- Rilascio (release);

CONDIZIONI NECESSARIE AL DEADLOCK:

Si può verificare un deadlock solo se si verificano

contemporaneamente le seguenti condizioni:

- Mutua esclusione: solo un processo per