Stallo (informatica): differenze tra le versioni

Versione delle 13:45, 15 dic 2006

Versione attuale delle 23:47, 5 feb 2025

(92 versioni intermedie di 67 utenti non mostrate)

Riga 1:

{{nd||Deadlock (disambigua)|redirect=Deadlock}}

In [[informatica]] il '''Deadlock''' è una situazione in cui due (o più) [[Processo (informatica)|task]] si bloccano a vicenda aspettando che uno esegua una certa azione (es. rilasciare il controllo su una risorsa come un [[File]], una porta [[Input/Output]] ecc.) che serve all'altro e viceversa.

{{F|programmazione|gennaio 2012}}

In [[informatica]], lo '''stallo''' o '''deadlock'''<ref>https://www.google.it/books/edition/Le_idee_dell_informatica/xzEB4WBf_4cC?hl=it&gbpv=1&pg=PA381</ref> indica una situazione in cui due o più [[Processo (informatica)|processi]] o azioni si bloccano a vicenda, aspettando che uno esegua una certa azione (per esempio rilasciare il controllo su una [[Risorsa informatica|risorsa]] come un [[file]], una porta [[input/output]] ecc.) che serve all'altro e viceversa.

Un esempio è rappresentato da due persone che vogliono disegnare. Per disegnare hanno a disposizione solo una riga e una matita. Per disegnare hanno bisogno di entrambe. Potendo prendere un solo oggetto per volta, se uno prende la matita e l'altro prende la riga i due generano un deadlock.

Un esempio è rappresentato da due persone che vogliono disegnare: hanno a disposizione solo una riga e una matita e hanno bisogno di entrambe. Potendo prendere un solo oggetto per volta, se uno prende la matita, l'altro prende la riga, e se entrambi aspettano che l'altro gli dia l'oggetto che ha in mano, i due generano uno stallo.

Questa situazione può esser vista come un [[paradosso]] (come la questione dell'uovo e della gallina) e non può essere risolta. Applicazioni che sono tipicamente soggette ai deadlock sono i [[database]], nel caso in cui ci siano richieste circolari di accesso esclusivo da parte di diverse transazioni sulle stesse risorse, oppure i [[sistema operativo|sistemi operativi]] che gestiscono l'accesso contemporaneo a file e a dispositivi di I/O di diversi processi.

Questa situazione può esser vista come un [[paradosso]] e non può essere risolta, ma si può prevenire. Applicazioni che sono tipicamente soggette agli stalli sono le [[Base di dati|basi di dati]], nel caso in cui ci siano richieste circolari di accesso esclusivo da parte di diverse transazioni sulle stesse risorse, oppure i [[sistema operativo|sistemi operativi]] che gestiscono l'accesso contemporaneo a file e a dispositivi di I/O di diversi processi.

==Condizioni necessarie e sufficienti ==

Le condizioni necessarie, ma non sufficienti, per il verificarsi di un Deadlock sono:

#'''Mutua esclusione''': almeno una delle risorse del sistema deve essere 'non condivisibile' (ossia usata da un processo alla volta oppure libera).

#'''Possesso ed attesa''': i processi che possiedono una risorsa possono richiederne altre.

#'''Impossibilità di prelazione''': solo il processo che detiene la risorsa può rilasciarla.

#'''Attesa circolare''': esiste un gruppo di processi {P₀,P₁,...,P_n} per cui P₀ è in attesa per una risorsa occupata da P₁, P₁ per una risorsa di P₂, ecc... P_n per una risorsa di P₀.

Una situazione di Deadlock può essere riconosciuta analizzando il [[Grafo delle attese]] dei task del sistema.

== {{Anchor|Condizioni necessarie (Condizioni di Havender)}}Condizioni necessarie ==

Le quattro condizioni di cui sopra, sono collettivamente anche sufficienti per provocare il Deadlock.

In un deadlock si verificano sempre queste condizioni, dette anche di Havender:

#Mutua esclusione: almeno una delle risorse del sistema deve essere 'non condivisibile' (ossia usata da un processo alla volta oppure libera).

#Accumulo incrementale: i processi che possiedono almeno una risorsa devono attendere prima di richiederne altre (già allocate ad altri processi).

#Impossibilità di prelazione: solo il processo che detiene la risorsa può rilasciarla.

#Attesa circolare: esiste un gruppo di processi <math>\{ {P_0,P_1, \dots,P_n} \}</math> per cui <math>P_0</math> è in attesa per una risorsa occupata da <math>P_1</math>, <math>P_1</math> per una risorsa di <math>P_2</math>, ecc. <math>P_n</math> per una risorsa di <math>P_0</math>.

Una situazione di deadlock può essere riconosciuta analizzando il [[grafo delle attese]] dei processi del sistema.

I deadlock si possono verificare solo se sono presenti contemporaneamente le quattro condizioni di cui sopra (che sono quindi necessarie).

==Gestione==

Le condizioni diventano anche sufficienti nel caso di una sola istanza per ciascun tipo di risorsa.

===Evitare i Deadlock===

È una soluzione possibile solo se il sistema è capace di mantenere delle informazioni sulle risorse disponibili al sistema e sulle risorse che ogni processo può potenzialmente richiedere.

== Gestione ==

Si definisce '''Stato sicuro''' di un sistema quando è possibile eseguire i processi in una sequenza tale per cui, allocando ad ognuno di essi tutte le risorse che potenzialmente può richiedere, gli si permetta di terminare la propria esecuzione e quindi evitare il Deadlock. Se il sistema si trova in uno stato sicuro il Deadlock può essere evitato, ma uno stato non sicuro non implica necessariamente un Deadlock.

=== Ignorare i deadlock ===

L'approccio consiste nell'assumere che il deadlock non avverrà mai. Se l'intervallo di tempo tra i deadlock è sufficientemente grande e la perdita di dati tollerabile, si può applicare l'[[algoritmo dello struzzo]]<ref name="distri_tanen">{{Cita libro|cognome=Tanenbaum|nome=Andrew S.|url=https://books.google.com/books?id=l6sDRvKvCQ0C&q=Tanenbaum+ostrich&pg=PA177|editore=Pearson Education|anno=1995|titolo=Distributed Operating Systems|edizione=1st|p=117|isbn=9788177581799|accesso=16 ottobre 2020|urlarchivio=https://web.archive.org/web/20210418011235/https://books.google.com/books?id=l6sDRvKvCQ0C&q=Tanenbaum+ostrich&pg=PA177|urlmorto=}}</ref> ignorando di fatto l'esistenza dei deadlock. Questo può essere fatto in modo sicuro se viene [[Verifica formale|provato formalmente]] che i deadlock non si verificheranno mai. La maggior parte dei sistemi operativi moderni, compresi [[Windows]] e [[Linux]] utilizza questo metodo.<ref>{{Cita libro|autore=Abraham Silberschatz|titolo=Sistemi Operativi. Concetti ed esempi|edizione=10|anno=2019|editore=Pearson|p=350|ISBN=9788891904560}}</ref>

<!-- Il framework RTIC utilizza questo metodo.<ref>{{Cita web|url=https://rtic.rs/0.5/book/en/|titolo=Preface - Real-Time Interrupt-driven Concurrency|accesso=1º ottobre 2020|urlarchivio=https://web.archive.org/web/20200918143731/https://rtic.rs/0.5/book/en/|urlmorto=}}</ref> -->

=== Evitare i deadlock ===

È una soluzione possibile solo se il sistema è capace di mantenere delle informazioni sulle risorse disponibili e sulle risorse che ogni processo può potenzialmente richiedere.

Si definisce [[#Stato sicuro|stato sicuro]] di un sistema quando è possibile eseguire i processi in una sequenza tale per cui, allocando a ognuno di essi tutte le risorse che potenzialmente può richiedere, gli si permetta di terminare la propria esecuzione e quindi evitare il deadlock. Se il sistema si trova in uno stato sicuro il deadlock può essere evitato, ma uno stato non sicuro non implica necessariamente un deadlock.

Il sistema può dunque evitare del tutto gli stalli se, ad ogni richiesta di una risorsa da parte di un processo, effettua una verifica dello stato in cui si troverebbe allocando la risorsa. Se lo stato è sicuro la risorsa può essere tranquillamente allocata. A tal fine si può utilizzare l'[[Algoritmo del banchiere]].

Il sistema può dunque evitare del tutto gli stalli se, a ogni richiesta di una risorsa da parte di un processo, effettua una verifica dello stato in cui si troverebbe allocando la risorsa. Se lo stato è sicuro la risorsa può essere tranquillamente allocata. A tal fine si può utilizzare l'[[algoritmo del banchiere]].

Tuttavia, per la maggior parte dei sistemi è impossibile conoscere in anticipo le risorse che richiederà un processo, per cui è spesso impossibile evitare del tutto i Deadlock.

Tuttavia, per la maggior parte dei sistemi è impossibile conoscere in anticipo le risorse che richiederà un processo, per cui è spesso impossibile evitare del tutto i deadlock.

===Prevenzione dei Deadlock===

In questo caso si cercando di evitare i Deadlock annullando una o più delle condizioni di cui sopra: essendo esse collettamente sufficienti basta infatti invalidarne una.

=== Prevenire i deadlock ===

In questo caso si cerca di evitare i deadlock annullando una o più delle condizioni di cui sopra: essendo esse collettivamente sufficienti basta infatti invalidarne una.

Per esempio:

# Annullando la condizione di mutua esclusione e permettendo l'accesso contemporaneo ada una stessa risorsa da parte di diversi processi (es. file aperti in lettura). Può essere impossibile come nei casi di scrittura su file o accesso ada una risorsa senza ''[[Spool|spooling]]''.

# Si può richiedere ada un processo di richiedere tutte le risorse di cui dovrà disporre all'avvio oppure con la convenzione di rilasciare una risorsa prima di richiederne un'altra. Spesso questa soluzione non è praticabile o poco efficace. Tuttavia è utilizzata nei database che fanno uso di ''[[Twotwo-phase Phase Lockinglocking]]''.

# Permettere la prelazione, il che peròquindi permetterebbe a un processo di rilasciare la risorsa detenuta da un altro processo: ciò può lasciare l'applicazione ''vittima'' in uno stato inconsistenteincoerente, dato che finisce per perdere una risorsa che stava utilizzando.

# L'attesa circolare si può risolvere permettendo ada ogni processo di richiedere solo una risorsa alla volta oppure imponendo un ordinamento (o una gerarchia) sui processi e prevenire in tal modo la formazione di cicli nel grafo delle attese.

=== Risolvere i deadlock ===

Quando non è possibile evitare o prevenire i deadlock si possono solo definire degli algoritmi per riconoscere e risolvere gli stati di deadlock.

Per quanto riguarda la risoluzione, si può procedere con la terminazione di tutti i processi in stallo o di un processo per volta fino alla risoluzione del deadlock, oppure con la prelazione sulla risorsa che causa il problema. Particolare cura deve essere riposta nella scelta della vittima della prelazione.

=== Deadlock distribuiti ===

In presenza di un [[sistema distribuito]] (come per esempio un database risiedente su diversi [[server]]), riconoscere una situazione di potenziale deadlock si rende ancora più complessa. In genere la rivelazione del possibile stato insicuro può essere effettuata solo ricostruendo il [[grafo delle attese]] globale a partire da quelli locali o con particolari algoritmi (vedi la variante distribuita del ''[[two-phase locking]]'').

Tuttavia, la possibilità che il grafo delle attese globale non rifletta sempre correttamente l'effettivo stato del sistema distribuito, può rivelare dei deadlock inesistenti (''phantom deadlocks'') che sono già stati risolti perché uno dei processi ha terminato la sua esecuzione nel frattempo o che non sono mai esistiti realmente.

== Stato sicuro ==

Si definisce "stato sicuro" uno stato in cui è possibile allocare tutte le [[Risorsa informatica|risorse]] richieste da un processo senza che questo finisca in un deadlock.

Il fatto che il sistema si trovi in uno stato sicuro non implica che tutte le allocazioni avverranno con successo, ma solo che esiste almeno un modo per allocare tutte le risorse. Se il sistema si trova in uno stato sicuro il deadlock può essere evitato, ma uno stato non sicuro non implica necessariamente un deadlock.

Il sistema può dunque evitare del tutto gli stalli se, a ogni richiesta di una risorsa da parte di un processo, effettua una verifica dello stato in cui si troverebbe allocando la risorsa. Se lo stato è sicuro la risorsa può essere tranquillamente allocata. A tal fine si può utilizzare l'[[algoritmo del banchiere]].

===Ripristinare i Deadlock===

Quando non è possibile evitare o prevenire i Deadlock si possono solo definire degli algoritmi per riconoscere e ripristinare i stati di Deadlock. Il riconoscimento dello stato di blocco può avvenire con lo stesso [[Algoritmo del banchiere]].

Tuttavia, per la maggior parte dei sistemi è impossibile conoscere in anticipo le risorse che richiederà un processo, per cui è spesso impossibile evitare del tutto i deadlock visto che non si può determinare in anticipo se un futuro stato sarà sicuro.

Per quanto riguarda il ripristino, si può procedere con la terminazione di tutti i processi in stallo o di un processo alla volta fino alla risoluzione del Deadlock, oppure con la prelazione sulla risorsa che causa il problema. Particolare cura deve essere riposta nella scelta della '''vittima''' della prelazione.

== Note ==

===Deadlock distribuiti===

<references/>

In presenza di un [[sistema distribuito]] (come per esempio un database risiedente su diversi server), riconoscere una situazione di potenziale Deadlock si rende ancora più complessa. In genere la rivelazione del possibile stato insicuro può essere effettuata solo ricostruendo il [[grafo delle attese]] globale a partire da quelli locali o con particolari algoritmi (vedi la variante distribuita del [[Two Phase Locking]]).

== Voci correlate ==

Tuttavia, la possibilità che il grafo delle attese globale non rifletta sempre correttamente l'effettivo stato del sistema distribuito, può rivelare dei '''Deadlock inesistenti''' (''Phantom Deadlocks'') che sono già stati risolti perché uno dei processi ha terminato la sua esecuzione nel frattempo o che non sono mai esistiti realmente.

* [[Algoritmo del banchiere]]

* [[Grafo delle attese]]

* [[Multithreading]]

* [[Processo (informatica)]]

* [[Thread (informatica)]]

* [[Sincronizzazione dei processi]]

* [[Starvation]]

== Collegamenti esterni ==

==Voci correlate==

* {{Collegamenti esterni}}

*[[Processo (informatica)|Task]], processi e thread.

* {{FOLDOC|deadlock|deadlock}}

*[[Multithreading]]

*[[Sincronizzazione (informatica)]]

*Rivelamento dei Deadlock:

**[[Grafo delle attese]]

**[[Algoritmo del banchiere]]

{{Portale|informatica}}

[[Categoria:Sistema operativo]]

[[Categoria:Controllo della concorrenza]]

[[Categoria:Concorrenza]]

[[ca:Abraçada mortal]]

[[cs:Deadlock]]

[[de:Deadlock]]

[[en:Deadlock]]

[[es:Bloqueo mutuo]]

[[fr:Interblocage]]

[[ja:デッドロック]]

[[ko:교착 상태]]

[[lt:Rakinimo aklavietė]]

[[pl:Zakleszczenie]]

[[pt:Deadlock]]

[[ru:Взаимная блокировка]]