Problemi "classici" della programmazione concorrente: deadlock
Spiegazione sui problemi della programmazione concorrente
1. Cos'è Il deadlock?
1.1. È una situazione dove due o più processi si ostacolano a vicenda impedendosi di completare fare il loro lavoro, per verificarsi bisogna avere 4 situazioni :
1.1.1. mutua esclusione: ogni risorsa è assegnata a un solo processo o è libera (risorse seriali)
1.1.2. assenza di prerilascio: le risorse non possono essere prerilasciate
1.1.3. richieste bloccanti
1.1.4. attesa circolare: i processi devono essere in attesa di una risorsa occupata dall'altro
2. Come si individua?
2.1. Si individuano tramite i grafi di Holt. Più precisamente ce ne accorgiamo quando vediamo che un processo non è in grado di evolvere. Ci sono anche dei teoremi che lo determinano.
2.1.1. 1º Teorema sul grafo di Holt: Se le risorse sono ad accesso mutualmente esclusivo, seriali e non prerilasciabili lo stato è di deadlock se e solo se il grafo di Holt contiene un ciclo.
2.1.2. 2º Teorema sul grafo di Holt: Se le risorse sono ad accesso mutualmente esclusivo, seriali e non prerilasciabili lo stato non è di deadlock se e sole se il grafo di Holt è completamente riducibile, cioè esiste una sequenza di passi di riduzione che elimina tutti gli archi del grafo.
3. Come si affronta?
3.1. 1) detection e recovery (individuazione e recupero): L'individuazione viene svolta, come visto nel paragrafo apposito, mentre il recupero viene effettuato manualmente o automaticamente, ma in entrambi i casi consiste nelle seguenti modalità: Terminazione dei processi, prerilascio di una risorsa e checkpoint/rollback.
3.2. 2) Evitare lo stallo (avoidance): secondo questa metodologia si cerca di evitare lo stallo analizzando in anticipo l'utilizzo che il processo farà delle risorse. Ci vengono in aiuto i concetti di:
3.2.1. Stato Sicuro: Un sistema è in stato (save) soltanto se esiste una sequenza di completamento sicura per i propri processi.
3.2.2. Sequenza Sicura: Una sequenza di processi è sicura se per ogni processo le richieste di risorse che il processo può fare possono essere soddisfatte da: Risorse attualmente disponibili, risorse detenute da tutti i processi che lo precedono nella sequenza
3.3. 3) Prevenire lo stallo: Il deadlock si può prevenire in quattro modi:
3.3.1. Eliminare le condizioni e le risorse seriali: utilizzando strumenti come gli spool che spostano il problema su altri processi
3.3.2. Eliminare le richieste bloccanti: effettuare un'allocazione totale quindi, fare in modo che un processo richieda tutte le risorse
3.3.3. Effettuare la preemption: si obbliga un processo a rilasciare le risorse che possiede quando ne richiede un'altra che in quel momento non è disponibile
3.3.4. Eliminare la condizione di attesa circolare: si utilizza l'allocazione gerarchica attribuendo alle classi di risorse un valore di priorità