Riassunto esame Sistemi Operativi, prof. Laface

MUTUA ESCLUSIONE

N processi competono per l'uso di una risorsa comune o dati condivisi.

Bisogna assicurare che quando un processo sta eseguendo il codice nella sua sezione critica (in cui

si accede alla risorsa o ai dati condivisi) a nessun altro processo sia permesso di eseguire il codice

nella propria sezione critica (si necessita un protocollo di accesso in mutua esclusione alla sezione

critica, in modo che un processo prenoti l'accesso nell'attesa che questa si liberi)

LOCK e UNLOCK (mutua esclusione) in ambito mono e multiprocessore

Nei sistemi monoprocessore:

-disable interrupt all'entrata nella regione critica

-enable interrupt all'uscita dalla regione critica

In questo modo lo schedulatore del sistema non può intervenire e quindi nessun processo può essere

attivato.

Nei sistemi multiprocessore con memoria comune:

-non si possono disabilitare gli interrupt su tutti gli altri processori

-istruzione test & set su una variabile di lock:

- byte = 0 → regione critica: libera

- byte = 1 → regione critica: occupata

-permette di testare il contenuto di una variabile e lo pone a 1 in un solo ciclo indivisibile

-controlla e modifica automaticamente il contenuto di 1 byte

MONOPROCESSORE MULTIPROCESSORE

LOCK(s)

{ int Test-and-Set(int lock)

s.lock = true; {

} int test = lock;

UNLOCK(s) lock = true;

{ return test;

s.lock = false; }

} LOCK(s)

{ Test-and-Set(s.lock)

}

UNLOCK(s)

{ s.lock = false;

}

READERS & WRITERS (SINCRONIZZAZIONE PROCESSI)

La sincronizzazione tra processi puà avvenire in vari modi:

- tramite la funzione start, il processo si dirama in due flussi; quando si chiama la complete, si

riuniscono e riprendono lo stesso flusso di esecuzione

- con la begin si chiamano altri processi che eseguono altre parti di codice; cobegin permette di

eseguire in parallelo più processi; coend attende la loro fine

- con questi costrutti non si può realizzare ogni tipo di grafo

Regole per la concorrenza: espresse dalle condizioni di Bernstein:

gli scrittori non possono scrivere quando qualcuno scrive o legge; questo è il principio su cui si basa

la mutua esclusione.

READER WRITER

while(TRUE) Scambio i con j

{ flag[i] = TRUE;

turn = j;

while (flag[j] && turn == j);

sezione critica

flag[i] = FALSE;

sezione non critica

}

FINE MUTUA ESCLUSIONE

SEMAFORI - INIZIO

Semaforo: variabile associata a una lista di processi.

– disable(S) - sospende il processo che la esegue e lo accoda al semaforo S; unlock(S.lock).

– enable(S) - rende ready il processo bloccato in testa alla lista del semaforo S.

Con i semafori si possono sincronizzare più processi.

In UNIX → due funzioni per gestire i semafori: WAIT e SIGNAL

-WAIT → decrementa un contatore → se minore di 0 blocca il processo, in attesa che torni positivo

-SIGNAL → incrementa il contatore.

Lavorano in mutua esclusione.

Deadlock → si verifica se un processo attende un evento che dev'essere provocato da un processo

bloccato.

Starvation → blocco perpetuo in cui un processo non viene mai rimosso dalla lista in cui è bloccato.

1) PRIMITIVE SEMAFORICHE – INIT, WAIT e SIGNAL

WAIT(S) SIGNAL(S)

{ {

lock(S.lock); lock(S.lock);

S.cnt --; S.cnt++;

if (S.cnt < 0) if (S.cnt <= 0)

disable(S); enable(S);

unlock(S.lock); unlock(S.lock);

} }

INIT(S,k) {S.cnt = k} k >= 0

2) PRODUTTORE E CONSUMATORE – SEMAFORI

INIT(full) = 0; INIT(empty) = MAX;

Producer(){ Consumer(){

Message m; Message m;

while (TRUE) { while (TRUE) {

produce m; wait( full );

wait( empty ); m = remove();

enter( m ); signal( empty );

signal( full ); consuma m;

} }

} }

3) PRODUTTORE E CONSUMATORE – SEMAFORI – ME

INIT(full) = 0; INIT(empty) = MAX;

INIT(ME_p) = 1; INIT(ME_c) = 1;

Producer(){ Consumer()

Message m; Message m;

while (TRUE) { while (TRUE) {

produce m; wait( full );

wait( empty ); wait( ME_c );

wait( ME_p ); m = remove();

enter( m ); signal( ME_c );

signal( ME_p ); signal( empty );

signal( full ); consuma m;

} }

} }

Un kernel mette a disposizione solo due primitive di gestione di semafori binari: D (s) che

blocca il semaforo s e S (s) che lo sblocca; inizialmente un semaforo è ovviamente sbloccato.

Questi semafori sono facilmente utilizzabili per gestire la mutua esclusione. Usando questi

semafori implementare il codice delle primitive INIT WAIT e SIGNAL di un semaforo

generale, cioè con contatore non binario.

INIT(s,k)

{ s.count = k;

}

WAIT(s)

{ if (s.lock == false)

{ D(s);

s.count--;

if (s.count<0)

{ disable(s);

}

S(s);

}

}

SIGNAL(s)

{ if (s.lock == false)

{ D(s);

if (s.count<=0)

{ enable(s);

}

S(s);

}

} 4) READERS & WRITERS – SEMAFORI

-Readers: classe di processi a cui è consentito accedere a un database in concorrenza

-Wrtiters: classe di processi a cui è consentito accedere al database in mutua esclusione sia con altri

processi Writers che con i processi Readers

PRECEDENZA AI READERS

nr = 0; // contatore che indica numero lettori in fase lettura

INIT(w) = INIT(me) = INIT(me1) = 1

// w, me e me1 sono semafori.

-w blocca i Writers quando nella regione critica ci sono uno o più Readers

-me protegge in ME il contatore nr

-me1 garantisce che mentre il Writer scrive gli altri Writer siano bloccati

Reader:

WAIT(me); // Readers accedono alla regione critica in me (inizio fase lettura)

nr++;

if (nr == 1)

WAIT(w) // aspetta che il Writer abbia finito, la lettura è bloccata

SIGNAL(me);

read();

WAIT(me); // Readers accedono alla regione critica in me(fine fase lettura)

nr--;

if (nr == 0)

SIGNAL(w); // l'ultimo Reader ha terminato e può rilasciare il blocco

SIGNAL(me);

Writer:

WAIT(me1); // Writers in mutua esclusione: un solo processo di scrittura alla volta

WAIT(w) // aspetta che i Readers abbiano finito, la scrittura è bloccata

write();

SIGNAL(w); // la scrittura è finita e viene rilasciato il blocco

SIGNAL(me1);

Dare la precedenza ai Readers significa che ciascun Writer deve aspettare che non ci sia nessun

Reader che sta accedendo ai dati, ossia finché tutti i Readers che hanno accesso al momento

abbiano finito. Inoltre, a causa del blocco in mutua esclusione dei Writers prima della WAIT del

semaforo W, i Readers sono i soli che possono eseguire una WAIT(W) mentre i dati vengono scritti.

PRECEDENZA AI WRITERS

nr = nw = 0;

INIT(r) = INIT(w) = INIT(me) = INIT(me1) = INIT(me2) = 1

Reader: Writer:

WAIT(me2); WAIT(me1);

WAIT(r); nw++;

WAIT(me); if(nw == 1) WAIT(r);

nr++; SIGNAL(me1);

if(nr == 1) WAIT(w); WAIT(w);

⋮

SIGNAL(me);

SIGNAL(r); // scrittura

⋮

SIGNAL(me2);

// lettura SIGNAL(w)

WAIT(me); WAIT(me1);

nr--; nw--;

if(nr == 0) SIGNAL(w); if(nw == 0) SIGNAL(r);

SIGNAL(me); SIGNAL(me1);

FINE SEMAFORI

REGIONI CRITICHE

PRODUTTORE E CONSUMATORE

region V do S;

1)Cotrutti di alto livello → effettuano per noi la mutua esclusione.

2)shared T v; // definisce una variabile condivisa v di tipo T

3)i processi possono accedere a v (solo in mutua esclusione) in uno statement S: region v do S;

4)regioni che fan riferimento a stessa variabile → mutuamente esclusive;

REGIONI CRITICHE

cobegin

region v do S1;

region v do S2;

coend

v può essere usata da un solo processo alla volta.

PRODUTTORE-CONSUMATORE CON REGIONI CRITICHE

typedef struct BUFFER_tag {

shared Message buffer[MAX];

shared int p = 0, c = 0;

semaphore_t full=0, empty=MAX;

} Buffer;

send(Message m, Buffer b){ receive(Message m, Buffer b){

WAIT( b.empty ); WAIT( b.full );

region b.p do { region b.c do {

buffer[b.p] = m; m = buffer[b.c];

b.p = (b.p + 1) % MAX; b.c = (b.c + 1) % MAX;

} }

SIGNAL( b.full ); SIGNAL( b.empty );

} }

REGIONI CRITICHE CONDIZIONALI

REGION WHEN B DO S

region v when B do S;

Quando un processo cerca di eseuire S, viene valutata in mutua esclusione l'espressione booleana B.

-vera: S può essere eseguita subito

-falsa: -processo bloccato finché B diventa vera;

-nessun altro processo è nella sua regione critica associata alla variabile v.

1) PRODUTTORE-CONSUMATORE - RCC

typedef struct BUFFER_tag {

shared Message buffer[MAX];

shared int p = 0, c = 0;

shared int count;

} Buffer;

Produttore: Consumatore:

send(Message m, Buffer b){ receive(Message m, Buffer b){

region b.count region b.count

when b.count < MAX do { when b.count > 0 do {

region b.p do { region b.c do {

buffer[b.p] = m; m = buffer[b.c];

b.p = (b.p + 1)% MAX; b.c = (b.c + 1)% MAX;

} }

b.count++; b.count --;

} }

} }

2) DIAGRAMMA STATI DI UN PROCESSO - RCC

I processo che giunge in regione critica la trova libera:

-può quindi entrare nello stato Active

-escludere tutti gli altri processi che intendono entrare nella regione.

Nello stato active il processo valuta la propria condizione B

-se la trova vera è libero di eseguire il codice della sezione critica; terminata l'esecuzione esce dalla

regione critica rilasciando la m.e. → questo provoca lo scheduling del prossimo processo in base ad

un criterio di priorità:

-se vi è almeno un processo nello stato wait, il primo della coda di quest'ultimo viene posto

nello stato active

-altrimenti viene attivato il primo processo nella coda di ME.

-se invece la condizione di B era falsa il processo

-rilascia la mutua esclusione

-entra nello stato di wait.

Anche in questo caso viene effettuato uno scheduling del prossimo processo in base alla stessa

politica.

3) PRIMITIVE SEMAFORICHE INIT, WAIT e SIGNAL - RCC

INIT(s,k)

{ s.count = k; // k>=0

}

WAIT(s)

{ region s.lock

when s.lock == false do

{ s.lock = true;

region s.count do

{ s.count--;

if (s.count<0)

{ disable(s);

}

}

s.lock = false;

}

}

SIGNAL(s)

{ region s.lock

when s.lock == false do

{ s.lock = true;

region s.count do

{ s.count++;

if (s.count>=0)

{ enable(s);

}

}

s.lock = false;

}

}

4) READERS & WRITERS - RCC

PRECEDENZA AI READERS

Class RW_precedenza_ai_Readers{

private:

int nr, nw;

char busy;

public: // sono eseguite in mutua esclusione

void start_read(void);

void start_write(void);

void end_read(void);

void end_write(void);

void(init(void));

};

void start_read(void) {

nr++;

await (nw == 0);

}

void start_write(void){

await (!busy && nr==0);<