DEADLOCK

Definizione di Risorsa

• Hardware: dispositivi fisici come un masterizzatore Blu-ray.

• Informazioni: dati come un record in un database.

Tipologie di Risorse

1. Ignorare il problema: Sperare che non si verifichino.
6.3 ALGORITMO DELLO STRUZZO (IGNORARE)
L'algoritmo dello struzzo rappresenta l'approccio più semplice per affrontare i deadlock: ignorarli completamente e fingere che non siano un problema reale. Questo metodo si basa sull'idea che, in alcuni casi, i costi di affrontare i deadlock possono superare i benefici della loro prevenzione.
• in questo caso il deadlock è un fenomeno raro e sopportabile

2. Rilevamento e Risoluzione: Consentire che i deadlock si verifichino, rilevarli e agire per risolverli.
6.4 RILEVAMENTO E RECUPERO

6.4.3 Recovery from Deadlock

Dopo che l'algoritmo di rilevamento ha individuato un deadlock (quindi si è fermato), è necessario un metodo per ripristinare il sistema. Esistono diverse strategie, ma nessuna di esse è particolarmente ideale.

Recupero tramite Prelazione (prestito)

In alcuni casi, è possibile prendere temporaneamente una risorsa da un processo bloccato e assegnarla a un altro. Ad esempio:

• Per una stampante laser, l'operatore può raccogliere i fogli già stampati, sospendere il processo (rendendolo non eseguibile) e assegnare la stampante a un altro processo.

• Una volta completato il secondo processo, i fogli originali vengono rimessi nella stampante e il processo sospeso viene riavviato.

Questo metodo è altamente dipendente dalla natura della risorsa. Non tutte le risorse possono essere prelazionate facilmente, e spesso può essere richiesto un intervento manuale. La scelta del processo da sospendere dipende da quali risorse possono essere recuperate senza problemi.

Recupero tramite Rollback (checkpoint)

Implemento un sistema di checkpointing:

• Un checkpoint salva periodicamente lo stato di un processo in un file, includendo una fotografia di memoria e stato delle risorse allocate.

• Quando viene rilevato un deadlock, un processo può essere riportato a uno stato precedente (prima che acquisisse una risorsa contesa).

• Tuttavia, tutto il lavoro svolto dal checkpoint fino al momento del rollback viene perso, e l'output generato potrebbe dover essere scartato e ripetuto.

Questa tecnica è utile, ma comporta una perdita di lavoro ed è efficace solo se il sistema è stato configurato per il checkpointing.

Recupero tramite Terminazione dei Processi (vittima)

Il metodo più semplice e diretto per risolvere un deadlock è terminare uno o più processi coinvolti:

• Si può scegliere di terminare un processo all'interno del ciclo di deadlock, con la speranza che questo consenta agli altri processi di continuare.

• In alternativa, si può terminare un processo esterno al ciclo che detiene risorse necessarie ai processi bloccati, liberandole per risolvere il deadlock.

La scelta del processo (vittima) da terminare deve essere ponderata:

• Processi che possono essere eseguiti nuovamente senza effetti collaterali, come una compilazione, sono buoni candidati.

• Processi che modificano uno stato persistente(ovvero dati memorizzati su disco e che influenzano per lungo tempo il sistema), come l'aggiornamento di un database, devono essere gestiti con cautela.

Rilevamento dei Deadlock

Il sistema monitora continuamente lo stato delle risorse e dei processi per individuare eventuali situazioni di stallo. Questo processo implica:

• Analizzare assegnamenti delle risorse e le richieste in attesa per Identificare cicli che impediscono ai processi di procedere.

6.4.1 Deadlock Detection with One Resource of Each Type (Algoritmo di rilevamento = ALGORITMO DI DAISTRA)

In un sistema in cui esiste solo una risorsa per ogni tipo, il deadlock può essere identificato utilizzando un grafo delle risorse. Se nel grafo è presente almeno un ciclo, significa che si è verificato un deadlock e che i processi coinvolti nel ciclo sono bloccati.

• Per tipo di risorsa si intende una classe di risorse che svolgono la stessa funzione o hanno lo stesso scopo all'interno di un sistema

Esempio di Rilevamento



Algoritmo per il Rilevamento dei Cicli

Grafi di rappresentazione

modello basato sui grafi per rappresentare l'allocazione delle risorse nei sistemi, utilizzando due tipi di nodi:

• processi (rappresentati da cerchi)

• risorse (rappresentate da quadrati).

• Un arco diretto da una risorsa a un processo indica che la risorsa è assegnata al processo

• un arco da un processo a una risorsa significa che il processo è in attesa di quella risorsa.



Esempio di Richiesta e Rilascio di Risorse

I grafi di allocazione delle risorse permettono di determinare se una sequenza di richieste e rilasci può portare a un deadlock:



1. i grafi mostrano come le richieste portano a un ciclo e quindi a un deadlock.

2. Tuttavia, il sistema operativo può prevenire il deadlock non concedendo alcune richieste
1. In questo caso, evitando di concedere S a B fino a quando A non ha completato il proprio lavoro, si impedisce la formazione di un ciclo.

Per ciascun nodo N, nel grafo, esegui i seguenti cinque passaggi

1. Inizializza L come lista vuota e designa tutti gli archi come non marcati.

2. Aggiungi il nodo N a L e verifica se il nodo appare due volte in L. Se appare due volte, il grafo contiene un ciclo (indicato in L) e l'algoritmo termina

3. Dal nodo dato, verifica se ci sono archi uscenti non marcati. Se ci sono, vai al punto 4; in caso contrario, vai al punto 5.

4. Scegli un arco uscente non marcato a caso e segnalo come marcato. Poi segui l'arco fino al nuovo nodo corrente e vai al punto 2.

5. NON ci sono archi uscenti
1. se sono al nodo iniziale, il grafo non contiene cicli e l'algoritmo termina (in pratica se a fine esplorazione torno ad N allora ho finito e nn ci sono cicli).
2. se non sono al nodo iniziale, abbiamo raggiunto un vicolo cieco Rimuovilo e torna al nodo precedente, ovvero quello che era corrente subito prima di questo. Rendilo il nuovo nodo corrente e vai al punto 3.

Limiti dell'Algoritmo

Sebbene l'algoritmo sia funzionale, non è ottimale per sistemi complessi con più risorse.

6.4.2 Deadlock Detection with Multiple Resource of Each Type

• approccio basato su matrici.

Strutture Dati Utilizzate

1. Vettore delle risorse totali esistenti (E = occorrenze)
• Il vettore E specifica quante unità(istanze) esistono in totale per ciascun tipo di risorsa

2. Vettore delle risorse disponibili (A): E - C (per ogni tipo)

3. Matrice delle allocazioni correnti (C):
• Ogni riga mostra quante istanze di ciascun tipo di risorsa sono attualmente allocate e quindi in utilizzo per un processo.

4. Matrice delle richieste e nn ricevute (R): (indipendentemente da ogni calcolo tra risorse disponibili)
• Ogni riga mostra quante istanze di ciascun tipo di risorsa un processo necessita per completare il proprio lavoro.



• in entrambe le matrici n righe = n processi

Algoritmo di Rilevazione

• Termina quando non è più possibile trovare processi eseguibili, a questo punto, i processi non marcati sono identificati come bloccati (deadlocked).

• nella riga in cui dice “se non esiste tale processo, terminare algoritmo” in parole povere ho trovato un deadlock

3. Evitamento dinamico: Allocare risorse con attenzione per evitare deadlock.
6.5 Evitare il Deadlock tramite Allocazione Attenta delle Risorse (la differenza col precedente è che l’allocazione di risorse è ragionata, non mi limito a monitorare se c’è il deadlock, faccio lo step in più di cercare di anticiparlo e quindi evitarlo ad ogni allocazione di risorse, ma l’algoritmo è lo stesso)

• L’evitamento richiede informazioni anticipate sul comportamento dei processi e sull'uso delle risorse.

• L'evitamento totale del deadlock è impossibile, poiché richiederebbe conoscere in anticipo le richieste future di risorse da parte dei process
💡

Sospensione in Punti Critici

(metodo di recovery fattibile solo con i metodi dell’evitamento)

Sospendere temporaneamente un processo che richiede risorse in momenti critici è una strategia efficace per mantenere il sistema in uno stato sicuro.



6.5.1 Traiettorie delle Risorse

Le traiettorie delle risorse rappresentano graficamente gli stati combinati di due processi che condividono due risorse, ad esempio una stampante e un plotter:
• L'asse orizzontale rappresenta il numero di istruzioni eseguite dal processo A
• L'asse verticale rappresenta il numero di istruzioni eseguite dal processo B
• Ogni punto del diagramma corrisponde a uno stato congiunto dei due processi.
Nel diagramma le traiettorie orizzontali e verticali indicano rispettivamente avanzamento del processo A e B mentre l’altro sta fermo, questo pk solo un processo può essere eseguito alla volta, quindi i processi non possono avanzare contemporaneamente. Perciò, il movimento nel grafico è alternato: o il sistema esegue A (traiettoria orizzontale) o esegue 𝐵 (traiettoria verticale).
Zone di Blocco
• Regioni vietate:
• tratteggio ad x: entrambi i processi cercano di accedere contemporaneamente alla risorsa dell'altro, = deadlock
• tratteggio singolo: un processo detiene una risorsa che interessa anche all’altro processo ma nn ne ha ancora fatto richiesta esplicita, quindi il sistema rischia altamente di entrare in deadlock se anche l’altro processo fa la richiesta (regione ad x)
• il tracciato non raggiunge mai la regione vietata pk impossibile
• Zona insicura:
• spazio adiacente alle regioni vietate ma che non è ancora vietato:
• Si trova lateralmente o perpendicolarmente alle zone tratteggiate.
 
6.7.1 Two-Phase Locking (blocco le risorse una alla volta)
Il Two-Phase Locking (locking a due fasi) rientra nella categoria dell'evitamento dinamico del deadlock.
particolarmente utile in contesti in cui più processi eseguono simultaneamente richieste di blocco, aumentando il rischio di deadlock.
Fasi del locking a due fasi
1. Prima fase:
• Il processo tenta di bloccare tutti i record necessari, uno alla volta, senza effettuare alcun aggiornamento effettivo.
• Se riesce a bloccare tutti i record necessari, passa alla seconda fase. Se un record richiesto è già bloccato, il processo rilascia tutti i blocchi acquisiti e ricomincia la prima fase da capo.
2. Seconda fase:
• Utilizza i record o le risorse bloccate nella prima fase per eseguire le operazioni necessarie sui dati necessari.
• Questa strategia assicura che nessun lavoro venga avviato fino a quando il processo non ha la certezza di poter completare la sua operazione senza rimanere bloccato.
LIMITI
6.7.3 Live-lock (simile al deadlock)
Livelock: una forma alternativa di stallo
Il livelock è una situazione in cui i processi, pur non essendo bloccati come nel deadlock, non riescono comunque a fare progressi. Si verifica quando i processi continuano a rilasciare e riacquisire risorse contemporaneamente in un ciclo infinito, impedendosi reciprocamente di proseguire. Anche se il sistema sembra "attivo" e non ci sono blocchi, nessun processo riesce a completare il suo lavoro.
La maggior parte dei sistemi operativi, come UNIX e Windows, ignora il problema del livelock, accettando che possa verificarsi occasionalmente.
• la sua applicabilità è limitata a scenari in cui i processi possono essere facilmente riavviati senza compromettere l'integrità del sistema o dei dati
6.5.3 Funzionamento dell'Algoritmo
L'algoritmo del banchiere esamina ogni richiesta di risorse:
1. Verifica se la concessione della richiesta porterà il sistema in uno stato sicuro, usando la simulazione per matrici
NOTA BENE: matrici con 2 modi d’uso
Le matrici possono essere usate sia per il rilevamento che per l'evitamento, ma il modo in cui vengono usate distingue i due scenari:
1. Rilevamento del deadlock: Le matrici vengono utilizzate per analizzare cicli e determinare quando e quali processi sono bloccati
2. Evitamento del deadlock: spiegazione
6.5.2 STATO SICURO E INSICURO (matrici)
Gli algoritmi di evitamento dei deadlock si basano sulla distinzione tra stati sicuri e stati insicuri, utilizzando le informazioni delle matrici possiamo decidere se concedere risorse ai processi in modo che tutti possano completare il loro lavoro senza rischio di deadlock.
Stato Sicuro
Uno stato è considerato sicuro se esiste un ordine che garantisce il completamento di tutti i processi (si riferisce all’esempio delle matrici in cui ho n processi=n righe e questi processi devono essere eseguiti uno alla volta in una sequenza che non crei deadlock).
Differenza tra Stato Insicuro e Deadlock
Tuttavia, uno stato insicuro non offre alcuna garanzia che tutti i processi potranno completare.
2. Se lo stato risultante è sicuro, la richiesta viene approvata.
3. Se lo stato risultante è insicuro, la richiesta viene negata o posticipata.
Per determinare se uno stato è sicuro:
• L'algoritmo simula il completamento dei processi, verificando se tutti possono terminare in un ordine che garantisca la disponibilità delle risorse
6.5.4 The Banker’s Algorithm
💡
STATO SICURO = scenario simulato in cui tutti i processi possono eseguire le loro operazioni senza arrivare al deadlock
Uno stato insicuro non implica necessariamente un deadlock immediato
È possibile che un processo rilasci risorse prima di richiederne altre, permettendo il completamento degli altri processi.
• è proprio questo il problema, un processo ha una risorsa e nel frattempo ne richiede altre pk puoi usarne molteplici in contemporanea ma aumenta il rischio di deadlock
Segue esattamente lo stesso concetto con cui si individua il deadlock a posteriori
Differenza di Obiettivo:
• Algoritmo di rilevazione: Serve a identificare se si è già verificato un deadlock, analizzando lo stato corrente del sistema.
• Banker’s Algorithm: Serve a prevenire il deadlock, verificando se lo stato attuale è sicuro prima di allocare nuove risorse.

DESCRIZIONE
• quella a sinistra indica le risorse attualmente assegnate ai processi, mentre quella a destra riporta le risorse da assegnare
• da assegnare: Il processo non può terminare senza che queste risorse vengano allocate. Fino a quando non riceve tali risorse, rimarrà in uno stato di attesa.
• i vettori
• E = risorse totali
• P = assegnate (somma dei dati della matrice sx)
• A = disponibili = E - P
• ogni riga nelle matrici rappresenta un processo
Funzionamento dell’algoritmo
L’algoritmo verifica se uno stato è sicuro seguendo questi passaggi:
1. Si cerca una riga nella matrice delle risorse necessarie (DESTRA) i cui valori siano minori o uguali alle risorse disponibili (A). Se non esiste, il sistema è destinato al deadlock.
2. Si assume che il processo scelto ottenga tutte le risorse necessarie, termini l’esecuzione e rilasci le sue risorse, che vengono sommate al vettore A.
3. Questo processo viene ripetuto fino a quando tutti i processi sono terminati (stato sicuro) o non ci sono processi eseguibili (stato non sicuro).
La selezione del processo da eseguire, in caso di più opzioni, non influisce negativamente sul sistema.
Limiti
raramente utilizzato, pk nonostante la validità teorica, nella pratica è difficile conoscere in anticipo le risorse necessarie ad un processo, però alcune strategie ispirate all’algoritmo vengono impiegate in contesti pratici, ad esempio per limitare l’utilizzo eccessivo delle risorse in reti o sistemi.
• NEL caso della identificazione risoluzione nn c’è problema di limite pk non deve fare previsioni, ma solo individuare e risolvere
• DIFFERENZA
Nel “singole resource” si lavora su una sola risorsa (rappresento la dinamica con una matrice ad una colonna: più processi e una risorsa) e nel seguente su più risorse (matrice con più colonne)

4. Prevenzione: Modificare la struttura del sistema per eliminare una delle quattro condizioni necessarie al deadlock.
6.2.1 4 Condizioni per evitare il Deadlock sulle Risorse
Se anche solo una di queste condizioni è assente, il deadlock NON può verificarsi
1. Mutua esclusione: Almeno una risorsa deve essere utilizzabile esclusivamente da un processo alla volta
NOTARE CHE:
• Se non implementi la mutua esclusione:
Puoi evitare i deadlock, ma rischi race conditions, che possono portare a comportamenti imprevedibili e incoerenti nei processi.
• Se implementi la mutua esclusione:
Previeni le race conditions, ma soddisfi una delle condizioni che possono portare al deadlock.
2. Blocco in attesa (Hold and Wait): Un processo che detiene alcune risorse può richiederne altre senza rilasciare quelle già in suo possesso
3. Non preemption: Le risorse non possono essere forzatamente tolte a un processo; devono essere rilasciate volontariamente.
4. Attesa circolare (Circular Wait): Deve esistere una catena sequenza circolare e sequenziale di processi, in cui ogni processo attende una risorsa detenuta dal successivo nella sequenza.
6.6 Analisi 4 condizioni
L'idea è garantire che almeno una di queste condizioni non si verifichi mai.
SINTESI:
Rimuovere la mutua esclusione (dare una risorsa a più processi contemporaneamente)
Questo è difficile per molte risorse fisiche (es. stampanti), ma per risorse virtuali (es. file)
Evitare il blocco in attesa
Fare in modo che i processi allochino tutte le risorse necessarie in un unico momento. Tuttavia, questo può portare a uno spreco di risorse, poiché i processi potrebbero non usarle immediatamente.
Consentire la preemption
Alcuni tipi di risorse (es. CPU) possono essere prelevate e riassegnate ad altri processi, ma questo non è sempre possibile o conveniente (es. stampanti).
Prevenire l’attesa circolare:
Si può imporre un ordine gerarchico per la richiesta delle risorse. Ad esempio, ogni processo può richiedere risorse solo in un ordine predefinito (es. prima stampanti, poi memoria, poi CPU), impedendo cicli di attesa.
L’approccio più efficace?
• Prevenire l’attesa circolare: Si può imporre un ordine gerarchico per la richiesta delle risorse. Ad esempio, ogni processo può richiedere risorse solo in un ordine predefinito (es. prima stampanti, poi memoria, poi CPU), impedendo cicli di attesa.
6.6.1 Annullare la condizione di mutua(alternata) esclusione → SPOOLING

Se nessuna risorsa fosse mai esclusivamente assegnata, i deadlock non si verificherebbero.

• Ad esempio, per i dati, si potrebbe renderli di sola lettura, permettendo a più processi di accedervi contemporaneamente.

• Tuttavia, per risorse fisiche come le stampanti, l’uso simultaneo da parte di più processi porterebbe al caos → dipende dalla natura della risorsa

spooling dell’output

(quindi il processo può fare altro nel frattempo)

Lo spooling è una tecnica che permette a più processi di inviare il proprio output a un’area temporanea sul disco (chiamata spazio di spooling), invece di inviarlo direttamente alla stampante. Una volta che i dati sono stati salvati in questa area, un programma speciale chiamato demone che si occupa di leggere l’output dallo spazio di spooling e inviarlo alla stampante fisica.

Non devono aspettare che la stampante sia libera per iniziare a generare il loro output, hanno assegnato il compito al demone (ovvero un algoritmo/processo) che non avendo altre richieste oltre alla stampante non può generare deadlock

In pratica la mutua esclusione è alimentata NON permettendo l’accesso a tutti i processi contemporaneamente, ma al contrario eliminando tale possibilità a tutti i processi e dandola ad un solo programma

6.6.3 Annullare the Non-Preemption Condition → IDONEO/SPOOLING(il demone sceglie con inclusa la prelazione, come se fosse lo scheduler)
Concetto
Rimuovere forzatamente una risorsa da un processo durante il suo utilizzo non è sempre possibile/conveniente o cmq facile
• Ad esempio, se un processo sta stampando e gli viene tolta la stampante perché un'altra risorsa non è disponibile, questo potrebbe creare complicazioni tecniche o rendere impossibile la continuazione del processo.
Metodo
Alcune risorse fisiche possono essere virtualizzate per aggirare il problema.
In questo modo nello spooling salvo l’output ed il demone si occuperà di assegnare la risorsa condivisa ad uno degli output e se volessi interrompere un operazione, posso salvare il nuovo output nello spooling
• invece di passare da un processo all’altro, passo da un operazione all’altra (no scheduler, bensì demone)
Limiti della virtualizzazione
Non tutte le risorse possono essere virtualizzate
• risorse bloccate
  Le risorse bloccate sono risorse che vengono riservate da un processo attraverso un meccanismo di lock (blocco), per garantire che nessun altro processo possa accedervi contemporaneamente.
  
6.6.2 Annullare the Hold-and-Wait Condition → Faccio una sola richiesta per tutto
• Una soluzione consiste nel richiedere ai processi di specificare tutte le risorse necessarie prima dell'esecuzione. Se tutte le risorse richieste sono disponibili, il processo le riceve e può eseguire fino al completamento; altrimenti nessuna risorsa viene allocata, e il processo rimane in attesa.
• Rilascio temporaneo delle risorse:
• Quando un processo richiede una nuova risorsa, è obbligato a rilasciare temporaneamente tutte le risorse che già possiede. Questo libera le risorse e consente al sistema di verificarne la disponibilità.
• Dopo aver rilasciato le risorse, il processo effettua una nuova richiesta per tutte le risorse necessarie, comprese sia quelle appena rilasciate sia quelle aggiuntive di cui ha bisogno
• quindi se le risorse sono disponibili le ottiene al completo
Problemi
• Imprevedibilità delle richieste: Molti processi non sanno in anticipo quante risorse richiederanno
• Spreco di risorse: Se tutte le risorse sono allocate in anticipo, alcune possono rimanere inutilizzate per lungo tempo
• potrebbe portare a un aumento del numero di riassegnazioni e a rallentamenti nell'esecuzione dei processi.
 
6.6.4 Annullare the Circular Wait Condition → ordinamento(percorso predefinito)
DIVERSE STRATEGIE
• ELIMINO L’USO SIMULTANEO DI RISORSE
  se necessita di un'altra risorsa, deve rilasciare quella attualmente detenuta.
 
• Ordinamento numerico delle risorse
Il processo è vincolato dallo storico delle richieste precedenti
Un metodo più efficace consiste nel fornire un ordinamento globale numerico di tutte le risorse. I processi possono richiedere risorse in qualsiasi momento, ma sempre e solo in ordine numerico crescente
• Se si arriva alla ventesima risorsa, significa che il processo ha accumulato tutte le risorse dalla prima alla ventesima e le detiene contemporaneamente.
• Variante del metodo
Il processo è NON è vincolato dallo storico delle richieste precedenti
hanno la flessibilità di poter richiedere risorse inferiori rispetto a quelle assegnate attualmente de-allocandole e aggiornando la sequenza di allocazione crescente
LIMITI
• per operazioni che richiedono l’uso simultaneo di più risorse, come copiare un file da un nastro a una stampante, questa soluzione risulta impraticabile.
• trovare un ordinamento che soddisfi tutti i processi è molto difficile

• problema simile al deadlock e al livelock

• Starvation: Il processo non è bloccato, ma viene perennemente ignorato o posticipato dall’algoritmo di allocazione.