Sistemi Operativi: Stallo dei processi

Uno stallo si genera in sistemi multiprogrammati quando due o più processi si bloccano attendendo una richiesta di una risorsa che non gli viene concessa perchè è già assegnata ad un altro, generando così un circolo vizioso dove un processo attende una risorsa di un altro processo e viceversa.

La realizzazione di questa sintesi si basa sullo studio del testo: “Sistemi operativi” settima edizione di Sliberschatz, Galvin e Gagne, edizione Pearson.

Nelle ordinarie condizioni di funzionamento un processo può servirsi di una risorsa soltanto se rispetta la seguente sequenza: richiesta della risorsa, uso e rilascio.

Una situazione di stallo si genera quando un processo rimane fermo dopo aver inoltrato una richiesta di una risorsa che non viene mai soddisfatta perché la risorsa in questione è occupata da un processo che non riesce a liberarla, ad esempio perché necessita di un’altra risorsa che è in uso proprio dallo stesso processo che ha inoltrato la richiesta. Quindi il primo è bloccato perché necessita di una risorsa in possesso al secondo e non può nemmeno liberare quelle già acquisite e il secondo invece non può liberare la risorsa che serve al primo perché necessita di una che è in uso dal primo e che non può essere rilasciata.

Perché sia possibile il generarsi di uno stallo, si devono verificare contemporaneamente quattro situazioni:
- mutua esclusione, cioè che c’è una risorsa che non è condivisibile e quindi utilizzabile solo da un processo alla volta
- possesso e attesa, un processo in possesso di almeno una risorsa attende di acquisire altre risorse in possesso di altri processi
- impossibilità di prelazione, cioè non c’è il diritto di “rubare” risorse già in uso da altri processi
- attesa circolare, esiste un insieme di processi tali che il primo processo è in attesa di una risorsa posseduta dal secondo, il quale attende una risorsa posseduta dal terzo e così via fino all’ultimo che attende un processo posseduto dal primo.

Grafi di assegnazione delle risorse

Tramite grafi è possibile rappresentare bene le situazioni di stallo. Con i quadrati si rappresentano i tipi di risorse, con i cerchi i processi.
Quando un processo inoltra una richiesta di una risorsa si fa una freccia dal processo alla risorsa, quando invece la risorsa viene assegnata al processo si fa la freccia che parte dalla risorsa al processo.

Gestione degli stalli

Ci sono sostanzialmente tre approcci:
- usare un protocollo per prevenire o evitare gli stalli
- individuazione degli stalli ed esecuzione del ripristino
- ignorare il problema fingendo che non esistano.
Per prevenire gli stalli basta adottare dei sistemi che impediscano il verificarsi di almeno una delle quattro condizioni necessarie per lo stallo; per evitare le situazioni di stallo invece occorre che il sistema operativo abbia in anticipo informazioni aggiuntive riguardanti le risorse che un processo richiederà e userà durante le sue attività.

Sistemi di prevenzione degli stalli

Mutua esclusione

Se non vi saranno risorse assegnate in modo esclusivo ad un processo non vi sarà lo stallo. Una tecnica valida è quella dello Spooling: essa prevede un processo demone (deamon) e una directory di spooling, il processo sarà l’unico ad aver accesso alla risorsa desiderata gli altri processi si limitano a produrre l’output e a metterlo nella directory di spooling, sarà poi il demone a prelevare dalla cartella l’output di un processo e a mandarlo alla risorsa. Questa tecnica però non è utilizzabile con tutti i tipi di risorse, ma è ottima per ad esempio stampanti, email, ftp …

Possesso e attesa

Due sistemi vanno per la maggiore; il primo impone che un processo prima di andare in esecuzione richieda tutte le risorse di cui ha bisogno e se non ci sono si metta in attesa che siano tutte libere, il problema è che un processo potrebbe rimanere in attesa per troppo tempo; il secondo sistema invece impone che prima della richiesta di una nuova risorsa debba rilasciare temporaneamente quelle che stava usando. Lo svantaggio di queste due tecniche è l’inefficienza con cui sono gestite le risorse, poiché molte risorse potrebbero rimanere non assegnate.

Impossibilità di prelazione

Per saltare questo problema si può adottare questo protocollo: se un processo che possiede già una o più risorse ed inoltra un’altra richiesta che non può essere subito soddisfatta, allora si esercita la prelazione su tutte le risorse attualmente in possesso dal processo.

Attesa circolare

Per questo tipo di problema si da un ordinamento alle risorse (magari secondo priorità), quando un processo inoltra la sua prima richiesta di una risorsa può scegliere quella che vuole, dopo di che potrà scegliere solo le risorse che, in ordine, vengono dopo.

Evitare le situazioni di stallo

I metodi per evitare le situazioni di stallo si basano sul fatto che devono conoscere più informazioni riguardo a come verranno usate le risorse da un processo e come sono attualmente assegnate, con queste informazioni si potrà decidere se assegnare o meno le risorse a chi le chiede.

Stato sicuro

Un sistema si trova in uno stato sicuro solo se esiste una sequenza sicura. Una sequenza di processi si dice sicura per lo stato di assegnazione attuale se, per ogni processo Pi, le richieste che Pi può ancora fare si possono soddisfare impiegando le risorse attualmente disponibili più le risorse possedute da tutti i Pj con j< i.
Se ci si trova in uno stato sicuro non ci potranno essere stalli, sono invece gli stati insicuri che potrebbero condurre agli stalli

Algoritmo del banchiere

Quando si crea un processo, questo deve dichiarare il numero massimo di istanze di ciascun tipo di risorsa di cui necessita (questo numero non può superare il numero totale di risorse del sistema). Quando il processo richiede un gruppo di risorse si deve stabilire se l’assegnazione lasci il sistema in una stato sicuro; in caso affermativo si procede con l’assegnazione, altrimenti si lascia il processo in attesa che si liberi qualche risorsa.

Per realizzare l’algoritmo si ricorre a delle strutture dati che contengono le risorse disponibili, il massimo di istanze che può fare un processo, le risorse già assegnate, la necessità per completare il processo.

In sostanza si assegnano le risorse disponibili a quel processo che terminerà la sua esecuzione se gli dovessero essere assegnate, così appena terminato libererà tutte le risorse rendendo maggiore di prima quelle disponibili

Rilevamento delle situazioni di stallo

Gli algoritmi per rilevare gli stalli sono piuttosto costosi in termine di tempo.
Per le risorse a singola istanza si genera un grafo d’attesa semplicemente cortocircuitando le risorse, in questo modo si troveranno collegati i processi; se si è generato un ciclo allora si è in uno stallo. Per verificare l’esistenza dello stallo periodicamente viene mandato in esecuzione un algoritmo che cerca i cicli nel grafo di attesa; questo algoritmo ha mediamente un costo del tipo N² dove N è il numero di vertici del grafo.

Invece quando sono possibili istanze multiple per lo stesso tipo di risorsa si può usare un algoritmo simile a quello del banchiere.

La frequenza con cui si manda in esecuzione l’algoritmo di rilevazione degli stalli dipende dalla probabilità di deadlock e dal numero di processi in esecuzione.

Ripristino delle situazioni di stallo

Terminazione dei processi

Si può scegliere se: terminare tutti i processi che fanno parte dello stallo, o terminarne uno alla volta finche non si scioglie lo stallo; il problema della terminazione, oltre al fatto che vengono buttati tutti i calcoli fatti fino a quel momento, è che un processo che sta per essere terminato stia aggiornando un file e la sua terminazione potrebbe generare un file corrotto, per questo è molto difficile scegliere il processo da terminare e lo si fa scegliendo quello il cui termine genera il costo minimo; la scelta del processo vittima è fatta seguendo diversi criteri: priorità, tempo trascorso e tempo rimanente, quantità e tipo di risorse usate e di quelle che gli servono per terminare normalmente, numero di processi da eliminare, tipologia di processo.

Prelazione di risorse

Le risorse vengono prese da alcuni processi ed assegnate ad altri finche non si risolve lo stallo, ma vanno prese in considerazioni le seguenti problematiche:
- scegliere quali risorse assegnate a quali processi porre sotto prelazione
- garantire il ripristino sicuro del processo che è stato vittima di prelazione in quanto mancando una risorsa non può continuare in modo corretto
- garantire che non si verifichino situazioni di attesa indefinita.

I sistemi operativi usano soluzioni diverse per diverse classi di risorse di sistema e l’area di swap, ad esempio si usa la prevenzione per le risorse fisiche, la prelazione per la memoria utente, per le risorse ai processi si usa l’evitamento dello stallo ecc

Starvation

E’ una situazione simile a quella del deadlock; un processo non ottiene mai una risorsa di cui ha bisogno perché è detenuta da un altro processo, questa situazione potrebbe generarsi quando la priorità è bassa o la temporizzazione della richiesta della risorsa è errata oppure l’algoritmo di allocazione delle risorse non è efficiente. Una soluzione può essere quella di garantire ad ogni processo una percentuale adeguata di tutte le risorse, oppure aumentare la priorità del processo se questo è in attesa da troppo tempo. Anche un semaforo potrebbe risolvere il problema della starvation.
Fonte