6 Il Sistema Operativo Indice

(1)

Il Sistema Operativo Architettura degli elaboratori - 1 - T. Vardanega Pagina 438

6 Il Sistema Operativo Indice

(segue)

6.4 La gestione dei processi

● Sincronizzazione e comunicazione tra processi (Inter-Process Communication)

● Situazioni catastrofiche (deadlock)

6.4 La gestione dei processi Sincronizzazione tra processi - 1

●

Processi indipendenti possono avanzare concorrentemente senza alcun vincolo di ordinamento

– Ricorda le condizioni di Bernstein per il parallelismo!

●

In pratica molti processi condividono risorse ed informazioni di stato

– In presenza di condivisione occorre introdurre meccanismi di sincronizzazione di accesso

6.4 La gestione dei processi Sincronizzazione tra processi - 2

●

Siano A e B due processi che condividono la variabile X, inizializzata al valore 10

●

Il processo A deve incrementare X di 2 unità

●

Il processo B deve decrementare X di 4 unità

●

A e B leggono concorrentemente il valore di X

– Il processo A scrive in X il suo risultato (12) – Il processo B scrive in X il suo risultato (6)

●

Il valore finale in X dipende da chi scrive per ultimo

●

Il valore atteso in X invece era 8

– Ottenibile solo con sequenze A;B o B;A indivise di lettura e scrittura

6.4 La gestione dei processi Sincronizzazione tra processi - 3

●

La modalità di accesso indivisa ad una variabile condivisa viene detta in mutua esclusione

– L’accesso concesso ad un processo inibisce quello di qualunque altro

●

Si utilizza una variabile ‘lucchetto’ (lock) che indica quando la variabile condivisa è in uso ad un altro processo

– Anche detta mutex (mutual exclusion)

6.4 La gestione dei processi Sincronizzazione tra processi - 4

// il processo A deve accedere ad X:

// Prima pero’ deve verificarne // lo stato di libero if (lock == 0) { // X è già in uso:

// Occorre ritentare il test }

else {

// X è libera, allora va bloccata lock = 0;

// e nuovamente liberata dopo l’uso lock = 1;

}

// il processo B deve accedere ad X:

// Prima pero’ deve verificarne // lo stato di libero if (lock == 0) { // X è già in uso:

// Occorre ritentare il test }

else {

// X è libera, allora va bloccata lock = 0;

// e nuovamente liberata dopo l’uso lock = 1;

}

Questa soluzione non può funzionare!

6.4 La gestione dei processi Sincronizzazione tra processi - 5

●

La soluzione mostrata é totalmente inadeguata

– Ciascuno dei due processi può essere prerilasciato dopo

aver testato la variabile lock, ma prima di esser riuscito a modificarla

●Situazione detta di ‘race condition’, che può generare pesante inconsistenza

– L’algoritmo usato comporta ‘attesa attiva’, ossia spreco di tempo di CPU a scapito di altre attività utili

●Tecnica detta di ‘busy waiting’ (o di ‘spin lock’)

(2)

6.4 La gestione dei processi Sincronizzazione tra processi - 6

●

Tecniche alternative

– Disabilitazione delle interruzioni

●Previene il prerilascio dovuto all’esaurimento del quanto di tempo e/o la promozione di processi a più elevata priorità

●Può essere inaccettabile per sistemi soggetti ad interruzioni frequenti

– Supporto hardware diretto: Test-and-Set-Lock

●Capace di cambiare valore alla variabile di lock se questa segnala ‘libero’

●Evita situazioni di ‘race condition’ ma comporta sempre attesa attiva

6.4 La gestione dei processi Sincronizzazione tra processi - 7

// Chiamiamo ‘regione critica’ la zona di programma // che delimita l’accesso e l’uso di una variabile // condivisa

enter_region:

TSL R1, LOCK // modifica il valore di // LOCK (se vale 0) e lo pone in R1 CMP R1, 0 // verifica l’esito

JNE enter_region // attesa attiva se =0

RET // altrimenti ritorna al chiamante // in possesso della regione critica leave_region:

MOV LOCK, 0 // scrive 0 in LOCK (accesso libero)

RET // ritorno al chiamante

6.4 La gestione dei processi Sincronizzazione tra processi - 8

●

Soluzione mediante semaforo

– Dovuta ad E.W. Dijkstra (1965)

– Richiede accesso indiviso (‘atomico’) alla variabile di controllo detta semaforo

●Semaforo binario (contatore booleano che vale 0 o 1)

●Semaforo contatore (consente tanti accessi simultanei quanto il valore iniziale del contatore)

– La richiesta di accesso, P, decrementa il contatore se questo non e’ già 0, altrimenti accoda il chiamante – L’avviso di rilascio, V, incrementa di 1 il contatore e

chiede al dispatcher di liberare il primo processo in coda

6.4 La gestione dei processi Sincronizzazione tra processi - 9

L’uso di una risorsa condivisa R e’ racchiuso entro le chiamate di P e V sul semaforo associato ad R

Processo ::

{ // avanzamento P(sem);

// uso di risorsa R V(sem);

// avanzamento }

P(sem) viene invocata per richiedere l’accesso alla risorsa

V(sem) viene invocata per rilasciare la risorsa

6.4 La gestione dei processi Sincronizzazione tra processi - 10 Mediante l’uso di semafori binari, due processi A e B possono coordinare l’esecuzione di attività distribuite

processo A ::

{// esecuzione indipendente

… P(sem);

// 2a parte del lavoro

… }

processo B ::

{// 1a parte del lavoro

… V(sem);

// esecuzione indipendente

… }

Contatore inizialmente a 0 (bloccante)

6.4 La gestione dei processi Sincronizzazione tra processi - 11

void P(struct sem){

sem.valore-- ; if (sem.valore < 0){

put(self, sem.lista);

suspend(self);

} }

void V(struct sem){

sem.valore++ ; if (sem.valore < 0)

wakeup(get(sem.lista));

} Un semaforo contatore è una struttura com- posta da un campo intero valoree da un campo listache accoda tutti i PCB dei processi in attesa su quel semaforo

(3)

6.4 La gestione dei processi Sincronizzazione tra processi - 12

●

La soluzione mediante semafori é di uso difficile e rischioso

– Un posizionamento incauto delle P può causare situazioni di blocco infinito, chiamato deadlock – Non e’ desiderabile lasciare all’utente il

controllo di strutture cosi’ delicate

●

Linguaggi evoluti di alto livello hanno introdotto una struttura esplicita di controllo delle regioni critiche, detta monitor

6.4 La gestione dei processi Sincronizzazione tra processi - 13

●

Un monitor é un aggregato di sottoprogrammi, variabili e strutture dati

●

Solo i sottoprogrammi del monitor possono accederne le variabili interne

●

Ad ogni istante, solo un processo può essere attivo entro il monitor

– Tale proprietà é garantita dai meccanismi del supporto a tempo di esecuzione del linguaggio di programmazione concorrente

6.4 La gestione dei processi Comunicazione tra processi - 1

●

Una volta noto come i processi possano condividere risorse, occorre determinare con quali meccanismi essi possano comunicare

Pipe (condotto) Stream (flusso)

Socket (connettore) Message (messaggio)

6.4 La gestione dei processi Comunicazione tra processi - 2

●

Il pipe è un condotto unidirezionale tra due processi, realizzato mediante un file

– Un processo immette dati al suo ingresso (sequenzialmente sul file)

– Un altro processo li legge (consumandoli) dalla sua uscita

●

Un pipe utilizzato da processi tra loro indipendenti ha una propria identità tramite la quali e’ da essi riconosciuto

●

Un pipe condiviso da un processo padre ed un processo figlio può essere non identificabile

6.4 La gestione dei processi Comunicazione tra processi - 3

●

Uno stream é analogo al pipe, ma consente l’invio e la manipolazione di informazioni strutturata

– Orientato al supporto di ‘protocolli di rete’

●

Un socket rappresenta una porta di comunicazione tra due processi tipicamente non locali

– Implementato come un file speciale, provvisto di connessione su rete

●

Il messaggio è il sistema più classico per mettere processi in comunicazione

– Relativamente agevole per comunicazioni locali, assai più complicato per comunicazione tra processi remoti

6.4 La gestione dei processi Comunicazione tra processi - 4

●

Primitive di scambio messaggi

– send (destinatario, messaggio) – receive (mittente, messaggio)

●

Struttura di comunicazione

– Canale simmetrico

●1 mittente - 1 destinatario – Canale asimmetrico

●1 mittente – N destinatari ; N mittenti – 1 destinatario – Casella postale, mailbox

– N mittenti – M destinatari

●

Forma di comunicazione

– sincrona (con attesa) o asincrona (senza attesa)

(4)

6.4 La gestione dei processi Produttore - consumatore 1

● Un processo Produttore produce dati ed un processo Consumatore li legge per elaborarli

– I due operano con tempi distinti e variabili

● Occorrono due semafori contatori, un semaforo binario ed un buffer

– int buffer// ad N posizioni inizialmente libere – sem vuoto // indica il numero di posizioni vuote nel buffer,

// inizialmente N

– sem pieno// indica il numero di posizioni del buffer che // contengono dati, inizialmente 0 – sem mutex// regola l’accesso dei processi al buffer

6.4 La gestione dei processi Produttore - consumatore 2

void produttore(){

// produrre dato P(vuoto);

P(mutex);

// invia dato // in buffer V(mutex);

V(pieno);

}

void consumatore(){

P(pieno);

P(mutex);

// preleva dato // dal buffer V(mutex);

V(vuoto);

// consumare dato }

6.4 La gestione dei processi Produttore - consumatore 3

Ugualmente realizzabile con il modello a messaggi

void produttore(){

int dato, msg;

do {

// produrre dato receive(consID,msg);

msg=dato;

send(consID,msg);

} while (!finito);

}

void consumatore(){

int dato, msg;

do {

receive(prodID,msg);

dato=msg;

// consumare dato send(prodID,NULL);

} while (!finito);

}

Pronto per ricevere

Dato prodotto

6.4 La gestione dei processi Stallo - 1

● I processi A e B hanno entrambi bisogno delle risorse R e Q – A chiede l’accesso alla risorsa R e, poiché essa è libera, ne ottiene

l’uso esclusivo

– B chiede l’accesso alla risorsa Q e, poiché essa è libera, ne ottiene l’uso esclusivo

– A chiede l’accesso alla risorsa Q, ma, poiché essa è occupata da B, si pone in attesa

– B chiede l’accesso alla risorsa R, ma, poiché essa è occupata da A, si pone in attesa

● In questa situazione, A blocca B che

é

a sua volta bloccato da A

– Situazione denominata ‘blocco circolare’

6.4 La gestione dei processi Condizioni di stallo necessarie e sufficienti

– Accesso esclusivo a risorsa condivisa – Cumulazione di risorse

●I processi possono accumulare nuove risorse senza doverne rilasciare altre

– Inibizione di prerilascio

●Il possesso di una risorsa deve essere rilasciato volontariamente

– Condizione di attesa circolare

●Un processo attende una risorsa in possesso del successivo processo in catena

6.4 La gestione dei processi Stallo - 3

●

Almeno tre strategie per affrontare lo stallo (noto come deadlock o starvation)

– Prevenzione

●Impedire almeno una delle condizioni precedenti – Riconoscimento e recupero

●Ammettere che lo stallo si possa verificare, ma essere in grado di riconoscerlo e possedere una procedura di recupero (sblocco)

– Indifferenza

●Considerare molto bassa la probabilità di stallo e non prendere alcuna precauzione contro di esso

– Che succede se esso si verifica?

(5)

6.4 La gestione dei processi Stallo - 4

●

Prevenzione sulle condizioni necessarie e sufficienti

– Accesso esclusivo alla risorsa

●Alcune risorse non consentono alternative – Cumulazione di risorse

●Assai ardua da eliminare – Inibizione del prerilascio

●Alcune risorse non consentono alternative – Attesa circolare

●Di riconoscimento difficile ed oneroso

6.4 La gestione dei processi Stallo - 5

●

Prevenzione sulle richieste di accesso

– Ad ogni richiesta di accesso, verificare se questa può portare allo stallo

●In caso affermativo non é però chiaro cosa convenga fare

●La verifica è un onere pesante ad ogni richiesta

– Una alternativa sensata è di richiedere preventivamente a tutti i processi quali risorse essi richiederanno cosi’ da ordinarne l’attività in maniera conveniente

6.4 La gestione dei processi Stallo - 6

●

Riconoscimento – Assai oneroso

●Occorre bloccare periodicamente l’avanzamento del sistema per analizzare lo stato di tutti i processi e verificare se quelli in attesa costituiscono una lista circolare chiusa

– Lo sblocco di uno stallo comporta la terminazione forzata di uno dei processi in attesa

●

Il rilascio delle risorse liberate sblocca la catena di dipendenza circolare

6.4 La gestione dei processi Stallo - 7

Il problema dei (cinque) filosofi a cena Cinque filosofi sono seduti ad un tavolo circolare. Ciascuno ha davanti a se un piatto di spaghetti ed una posata alla propria destra.

Ciascun filosofo necessita di due posate per mangiare. L'attività di ciascun filosofo alterna pasti a momenti di riflessione.

6.4 La gestione dei processi Stallo - 8

Soluzione con stallo

1

2 3 4

5 1

3 2 4

5 void filosofo_i_esimo(){

while (True) { // medita

prendi_forchetta(i);

prendi_forchetta((i++)%5);

// mangia posa_forchetta(i);

posa_forchetta((i++)%5);

} }

6.4 La gestione dei processi Stallo - 9

void filosofo_i_esimo(){

while (True) { // medita P(mutex);

P(f[i]);

P(f[(i+1)%5]);

V(mutex);

// mangia V(f[i]);

V(f[(i+1)%5]);

} }

6 Il Sistema Operativo Indice