Perché le condizioni di Coffman sono necessarie per il verificarsi di un deadlock?

Question

Perché le condizioni di Coffman sono necessarie per il verificarsi di un deadlock?

#1 da (3 voti)
#2 da (0 voti)

1

Citando link :

A deadlock situation can arise if all of the following conditions hold simultaneously in a system:

Mutual exclusion: at least one resource must be held in a non-shareable mode.Only one process can use the resource at any given instant of time.

Hold and wait or resource holding: a process is currently holding at least one resource and requesting additional resources which are being held by other processes.

No preemption: a resource can be released only voluntarily by the process holding it.

Circular wait: a process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P1, P2, …, PN}, such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3 and so on until PN is waiting for a resource held by P1.

Wikipedia afferma che queste condizioni sono necessarie perché si verifichi un deadlock. Inoltre, ho sentito affermazioni che sono anche sufficienti (anche se posso aver interpretato male queste affermazioni).

Il problema è che ho esempi che mi sembrano contraddire sia la necessità sia la sufficienza di quelle condizioni. E non riesco a vedere il mio errore.

Necessità prima:
Lascia che R1 e R2 siano due risorse condivisibili da due processi al massimo. Sia P1, P2, P3, P4 siano processi come P1 e P2 reggono un pezzo di R1 ciascuno e ognuno aspetta un pezzo di R2, e P3 e P4 tengono un pezzo di R2 ciascuno e ciascuno aspetta un pezzo di R1, come qui di seguito:

Supponiamocheil#3siavalido.#2e#4sonoovviamentesoddisfatti,mail#1nonèinquantosiaR1cheR2possonoesserecondivisi.Tuttaviasembrachesiverifichiundeadlock.

Orasufficienza:
LasciacheR1eR2sianoduerisorse,comeR1ècondivisibiledadueprocessialmassimoeR2nonècondivisibile.SiaP1,P2eP3sianoprocessicomeP1detieneR2evuoleunpezzodiR1,R2contieneunpezzodiR1evuoleR2eR3detieneunpezzodiR1enonvuolealtro,comediseguito:

Ancora una volta, supponiamo che il # 3 sia valido. Quindi # 1 è soddisfatto poiché R2 non è condivisibile, P1 e P2 soddisfano entrambi # 2 quindi anche questa condizione è valida, e # 4 è soddisfatta dal ciclo formato da P1 e P2. Tuttavia non si verifica un deadlock, dal momento che non appena P3 termina il suo pezzo di R1 può essere concesso a P1, i cui requisiti saranno soddisfatti da allora; quindi, non appena P1 rilascia R2, P2 sarà in grado di procedere.

Dov'è il mio errore? Dov'è il mio malinteso?

conditions concurrency

posta gaazkam 19.02.2016 - 18:08

fonte

2 risposte

Leggi altre domande sui tag conditions concurrency

Algoritmo per trovare tutte le tessere vuote nella griglia rettangolare? Implementazione file-directory: un file deve possedere un riferimento alla sua dir?

score 3 · Answer 1

Hai introdotto una restrizione di conteggio alla condivisione. Mentre questo è interessante, è diverso da ciò che è normalmente considerato. Una risorsa condivisibile dovrebbe essere condivisibile da chiunque e tutti allo stesso tempo.

Quello che # 1 dice è che una risorsa deve essere mantenuta in una modalità non condivisibile. Nel tuo esempio se R1 fosse veramente condivisibile, non ci sarebbe alcun motivo per cui un altro processo non potesse acquisire anche R1 in una modalità condivisibile (e quindi non si verificherebbe un deadlock).

Quello che stai facendo è l'introduzione di una risorsa "limitata condivisibile", che inizialmente si comporta come una risorsa condivisibile, anche se quando viene raggiunto il limite si comporta come una risorsa non condivisibile. Quindi stai giocando con le regole (che va bene), ma questo cambia un po 'le cose. Dobbiamo considerare che R1 si trasforma in una risorsa non condivisa ogni volta che viene raggiunto il limite di condivisione.

Pensaci in questo modo: la modalità condivisibile non ci compra nient'altro che un elenco di utenti correnti di una risorsa. Non limita il programma in alcun modo.

L'uso condivisibile di risorse da solo non vale la pena di essere considerato nel contesto di deadlock. Ciò che inizia a renderlo interessante è l'uso e la necessità di modalità non condivisibili.

Quando aggiorni una risorsa, è meglio farlo in una modalità non condivisa, altrimenti puoi avere condizioni di gara. Quindi, gli aggiornamenti ti mettono in una situazione in cui hai razze o potenziali punti morti. Le razze vengono evitate dalle modalità non condivisibili (esistono altri metodi, sebbene più limitati). I deadlock dovuti a modalità non condivise possono essere evitati seguendo una gerarchia di risorse aciclic dirette, che elimina i cicli necessari per i deadlock.

score 0 · Answer 2

La citazione che hai incluso è un po 'mal formulata e questo ti fuorvia. In particolare, il paragrafo 1 della citazione è una descrizione non di una condizione per lo stallo che si verifica, ma di un'ipotesi di base sul tipo di sistema a cui si applicano i paragrafi rimanenti. Pertanto, ciò che possiamo dire è che se # 1 è vero, allora # 2, # 3 e # 4 formano un insieme necessario e sufficiente di condizioni per il deadlock che si verificano. In situazioni in cui # 1 non è vero (come negli scenari che descrivi) possono essere applicate condizioni diverse.