Come rilevare manualmente i deadlock

Sì, è un deadlock, mostra la catena di attesa dei processi (1 - > 2 indica P1 in attesa su P2 per rilasciare una risorsa):

1 - > 3 - > 4 - > 2 - > 1

Tornato in 1 nella catena di attesa e il ciclo è completo; cioè 1 è in attesa di risorse in attesa su risorse in attesa su 1.

Se seguire 1 come questo non ha funzionato di nuovo in sé, sarebbe accurato dire che 1 non è in un deadlock (per esempio se era 1- > 3- > 4- > 2). Tuttavia, se uno non era in una situazione di stallo che dimostra non o indica che nessuno degli altri è in deadlock. Per verificare che nessuna delle risorse si trovi in una condizione di stallo, è necessario rappresentare graficamente la stessa catena con tutti i nodi che non si trovavano nel percorso critico per 1 (se nel percorso critico si trovavano in un deadlock allora 1 sarebbe, quindi sai tutti i membri della sua catena di dipendenze non sono in deadlock). Dal momento che 5 non è nel percorso critico dovresti seguire il percorso di 5 se 1 non era in un deadlock (incidentalmente 5 è anche in un deadlock perché si collega allo stesso ciclo 1 è in, quindi tutte le risorse elencate sono deadlock in quel ciclo)

Un altro punto riguardante questo particolare problema è che le tutte risorse disponibili (il set di R1-R5) sono già state acquisite. In tale scenario è impossibile per qualsiasi processo acquisire un'altra risorsa se nessun processo è disposto a rilasciare prima una risorsa. Un ciclo è inevitabile in uno scenario del genere. Questo fatto che dovresti rilasciare risorse prima di richiederne di più è presumibilmente la lezione del problema dei filosofi 73.4 (non citatemi sopra)

Uno degli strumenti formali volti a rilevare problemi nei sistemi concorrenti (deadlock, fame di risorse ...) è reti di Petri .

Modella il tuo problema con una rete di Petri, quindi puoi eseguire analisi matematiche su di esso e provare alcune proprietà del tuo sistema, come stati non raggiungibili.

In senso formale, un deadlock sarà indicato da uno o più cicli nel grafico di allocazione delle risorse. I processi che formano il ciclo o i cicli, o che dipendono in modo transitorio dai cicli, sono bloccati.

Per questo problema, ho usato una rete Place / Transition (P / T). Ho usato la grafica "standard" per P / T Net con due modifiche: cambiato il colore del token dal nero al "rossastro-arancio", aggiungendo un riquadro di delimitazione con linee tratteggiate per rappresentare un processo. Ho modificato le etichette che hai usato per processi e risorse - invece di partire da 1, ho iniziato da 0.

Poi ho segnato la rete in base alle condizioni che hai specificato: P0 contiene R0, P1 contiene R1, ecc.

Successivamente ho calcolato manualmente lo stato di ciascuna transizione nella rete (ispezionando visivamente la rete contrassegnata). Non ho trovato nessuna transizione abilitata. Così ho lasciato ogni transizione incolore. Poiché nessuna transizione è abilitata, il sistema è deadlock.

Hoinclusolasituazioneincuituttelerisorsedisponibili-inquestocaso,alcunedelletransizionisonoabilitate(ecolorateinverde).

Includerò una versione interattiva in PDF utilizzando JavaScript. Lo posterò più tardi.