Guida Cooperazione tra processi & deadlock (Sistema Operativo)

Stato
Discussione chiusa ad ulteriori risposte.

syscall

Utente Emerald
21 Settembre 2013
683
43
581
475
Ultima modifica da un moderatore:
Adesso tratteremo in breve, in un unico post, la sincronizzazione, detta anche cooperazione tra processi, e il deadlock.

Iniziamo subito, come al solito, con una brevissima e semplice definizione:

Un processo si dice "cooperante" se influenza o puo' comunque essere influenzato da altri processi in esecuzione nel sistema, in caso contrario si definisce "indipendente".

L'accesso concorrente a dati condivisi puo' generare una serie di dati incoerenti e, al fine di evitare cio', e' necessario definire opportuni meccanismi che garantiscono la sincronizzazione dei processi che condividono la stessa risorsa. Si definisce dunque sezione critica, quella porzione di spazio condivisa dai processi all'interno della quale potrebbero insorgere degli errori dovuti ad eccessivi concorrenti e non sincronizzati.

Al fine di evitare situazioni che potrebbero generare incoerenza dei dati come output finale, bisogna seguire un protocollo basato su tre regole fondamentali:

- Mutua esclusione;
- Progresso;
- Attesa limitata

La mutua esclusione fa in modo che se un processo si trova in una sezione critica, nessun altro potra' accedervi. Progresso, se un processo e' gia nella sezione critica e qualche altro desidera entrare, possono partecipare alla decisione di farlo entrare o meno, solo quei processi residenti nella sezione d'ingresso.
Attesa limitata, se un processo ha gia richiesto l'ingresso, esiste un numero limitato di volte che si permette ad altri processi di entrarvi o di effettuare la medesima richiesta.

Al fine di far rispettare queste tre regole, vengono usati tre tipi di algoritmi, ed una sorta di variabile chiamata "variabile di turno" che ha la caratteristica di mantenere un solo assegnamento per volta.

Il primo algoritmo fa uso di due processi, una risorsa e della variabile di turno inizializzata a "false".
Il processo Pi assegna "true" alla variabile in modo da segnalare il suo accesso alla sezione critica. Se turno == i, allora il processo entra nella sezione critica, in caso contrario no.
Questo algoritmo garantisce la mutua esclusione ma non le altre due regole.

Il secondo algoritmo introduce un vettore booleano di due elementi inizializzato a "false". Il processo Pi assegna "true" al vettore e controlla che nessun altro abbia fatto la stessa richiesta.
Questa soluzione e' migliore della prima perche' non impone una stretta alternanza tra i processi ma non garantisce il progresso e l'attesa.

L'ultimo algoritmo fa un mix dei primi due, ovvero inizializza il vettore a "true" e controlla che nessun processo abbia fatto richiesta di entrare nella sezione critica.
Qualora un altro processo tenti di fare la stessa operazione non gli sara' permesso dalla variabile di turno, che mantiene una sola assegnazione per volta.
Questo algoritmo garantisce tutte e tre le regole.

Una soluzione di piu' alto livello per la gestione della sincronizzazione dei processi, e' data dai "semafori".
Potete approfondire comunque leggendo qui: Semaforo

Un semaforo viene gestito mediante istruzioni atomiche, ovvero istruzioni offerte dall'architettura del sistema di calcolo, quali: "wait" (decrementa) e "signal" (incrementa).

Quando un processo cambia il valore al semaforo, nessun altro processo potra' eseguire la stessa operazione, mantendo cosi' la mutua esclusione.

I semafori funzionano attraverso delle chiamate di sistema, per cui, affinche' essi funzionino correttamente e' necessario che le chiamate di sistema siano corrette.

Al fine di garantirne la correttezza si usano i "monitor".
Come per i semafori, potete trovare maggiori informazioni leggendo qui: Monitor (sincronizzazione)

Ovvero un insieme di operatori definiti dal programmatore, che vengono trasformati in corrette chiamate di sistema da parte del compilatore. Solo un processo alla volta puo' essere attivo in un monitor, ed ogni monitor gestisce le richieste e il rilascio di una risorsa.

Vi sono dei casi in cui si voglia che la sezione critica sia totalmente accessibile, per far cio' si usano le transazioni atomiche, ovvero una serie di operazioni quali una "read" ed una "write", seguite da un'operazione di successo (commit) o di fallimento (abort).

In seguito ad un abort sara' necessario riportare il sistema ad uno stato precedente e, per far cio', si dovra' tener traccia delle varie operazioni di write e read. Al fine di tenerne traccia si usano delle memorie stabili all'interno delle quali si creano dei file conosciuti come "file di log", o "giornali delle transazioni". Andando a leggere quindi i log e' possibile risalire al punto in cui si e' verificata una abort e ripristinare quindi il sistema!

Ma quando ci si trova davanti ad una sorta di "stallo", o comunque in una situazione in cui le risorse richieste da un processo sono trattenute da altri processi, magari a loro volta nello stato di attesa, cos'e' che succede?!

Bene, in questo caso siamo di fronte ad un "deadlock", ma se riusciamo, proviamo a scrivere la cosa in un altro modo!

Un esempio e' dato da due persone che vogliono disegnare, per farlo hanno a disposizione solo una riga ed una matita ma, per realizzare il disegno, hanno bisogno di usarle entrambe. Potendo prendere un solo oggetto per volta, se uno prende la matita e l'altro la riga, uno dei due dovra' aspettare che l'altro termini il suo lavoro, i due genereranno quindi un deadlock!

Applicazioni che tipicamente sono soggette ai deadlock sono i database!
Un deadlock si puo' verificare solo se si verificano contemporaneamente quattro condizioni, vediamo quali e spieghiamole in breve:

- Mutua esclusione (almeno una delle risorse del sistema deve essere non condivisibile
- Possesso e attesa (i processi che possiedono una risorsa possono chiederne altre)
- Impossibilita' di prelazione (una risorsa puo' essere rilasciata dal processo che la possiede solo in maniera volontaria)
- Attesa circolare (deve crearsi un insieme di processi tale per cui il primo attende una risposta dal secondo, il secondo dal terzo e cosi' via, sino ad arrivare all'ultimo processo che attende una risposta dal primo processo della lista)

Si puo' evitare uno stallo, assicurandosi che almeno una delle quattro condizioni descritte non si verifichi!

Nella mutua esclusione, un processo non dovrebbe mai attendere una risorsa condivisibile, ma poiche' alcune risorse sono intrinsecamente non condivisibili, non si puo' garantire la negoziazione di questa condizione.

Possesso e attesa, occorre garantire che un processo in possesso di una risorsa non ne possegga altre. Per far cio' si fa in modo che il processo richieda le risorse prima di iniziare la sua esecuzione.

Impossibilita' di prelazione, occorre garantire che si possa avere la prelazione su risorse gia' assegnate, al fine di garantire cio', se il processo che possiede una o piu' risorse ne richiede un'altra non gli puo' essere assegnata immediatamente, allora si esercita la prelazione sulle risorse attualmente in suo possesso.

Il processo viene nuovamente avviato quando potra' avere sia le vecchie che le nuove risorse.

Attesa circolare, un processo puo' richiedere una risorsa, solo se esso segue un ordine crescente di numerazione. Ogni processo, prima di richiedere un'istanza di Ri, deve rilasciare qualsiasi risorsa Rj tale che f(Rj)<=f(Ri). Nel caso di piu' istanze, potremmo usare l'algoritmo del banchiere (leggete qui per approfondire: Algoritmo del banchiere), dove ogni processo dichiara inizialmente tutte le risorse di cui ha bisogno.

L'algoritmo procede iterativamente, confrontando le risorse richieste con quelle disponibili nel sistema e le assegna solo se queste sono minori o uguali alle disponibili.

Ad esecuzione terminata, il processo libera le risorse che aveva allocato.

Per rilevare uno stallo e' possibile usare il "grafo d'attesa" (per maggiori informazioni in merito vi rimando qui: Grafo delle attese), ottenuto togliendo i nodi delle risorse e connettendo gli archi tra i processi che attendono risorse. Successivamente si analizza il grafo verificando che non vi siano cicli.

In seguito ad uno stallo, il sistema potra' comunque essere ripristinato in vari modi:

- informando l'operatore dello stallo, che provvedera' a gestirlo in maniera del tutto manuale
- Terminado tutti i processi in stallo
- Ignorando il problema. Comunque, una gestione di questo tipo potrebbe portare alla congestione o paralisi dell'intero sistema

Come al solito, qualora vogliate approfondire, vi lascio qualche nota:

- http://cs.unibg.it/scandurra/material/SO/lez3_processi.pdf
- http://www.disi.unige.it/person/DelzannoG/SO1/AA0405/cooperazionex4.pdf
- http://www-ictserv.poliba.it/piscit...0/8_sistop_IET_interprocess_communication.pdf
- http://www.dis.uniroma1.it/~baldoni/SOII-deadlock.pdf
- + quei piccoli paragrafetti inseriti direttamente all'interno del testo, semafori, monitor e quant'altro

Vi lascio inoltre, i link dei post che vi consiglio di leggere prima di questo:

- http://www.inforge.net/community/in...-introduzione-all-architettura-di-un-s-o.html
- http://www.inforge.net/community/informatica-zone/364352-guida-comunicazione-tra-processi-s-o.html
- http://www.inforge.net/community/in...uida-la-schedulazione-del-processore-s-o.html
- Sincronizzazione e deadlock
- http://www.inforge.net/community/in...os-e-file-system-di-un-sistema-operativo.html (prima del file system comunque penso proprio che buttero' dentro altri argomenti che dovrebbero avere la precedenza, seguendo comunque quest'ordine :p)

Nel prossimi post, se riesco, ho intenzione di trattare in breve, i seguenti argomenti:

- I sistemi di Input/Output
- La gestione delle periferiche
- La memoria virtuale
- La protezione dei file
- La gestione della memoria paginata

Penso comunque di realizzare un'altra discussione corredata da una breve introduzione e tutti i link ai vari post che trattano i singoli argomenti, cosi' da evitare di rimettere i vari link dei precedenti e successivi su ognuno, aggiungendo di volta in volta i link alle voci!

STAY TUNED !!!
Buon approfondimento! Ciao ciao o/
 
  • Mi piace
Reazioni: Asahi
Stato
Discussione chiusa ad ulteriori risposte.