[SO] Sottile differenza tra deadlock e starvation?

[Matrixbob]

Wikipedia non è il massimo della chiarezza, sopratutto perché collega male i 2 argomenti e non li contestualizza uno rispetto l'altro.

La starvation viene rappresentata tipicamente col problema dei 5 filosofi, mentre il deadlock con l'ingorgo stradale intorno a una piazza.

Quello che mi pare d'aver capito è che una starvation può diventare deadlock?
Quando ogni filosofo attende che si leberi l'altra bacchetta con cui mangiare, ma se capita che tutti attendono in circolo avviene il deadlock?

Il deadlock indipendentemente lo si ha quando ho una catena in cui ogni processo interessato attende che si liberi una risorsa detenuta da un'altro processo in attesa a sua volta, creando de facto in circolo vizioso infinito.

Chi mi sa chiarire maglio?
TNX!

[Matrixbob]

... poi attualmente pare che per mantenere presatazioni soddisfacenti i moderni SO non:

1. preveniscono
2. evitano
3. individuano e risolvono
4. combianono quanto sopra visto

, scaricano sull'utente finale il problemone; devono essere i programmi a livello utente a preoccuparsene se è il caso.

Ma della starvation non mi sovviene nulla ... blackout totale!

[mad_hhatter]

Originariamente inviato da Matrixbob

Wikipedia non è il massimo della chiarezza, sopratutto perché collega male i 2 argomenti e non li contestualizza uno rispetto l'altro.

La starvation viene rappresentata tipicamente col problema dei 5 filosofi, mentre il deadlock con l'ingorgo stradale intorno a una piazza.

Quello che mi pare d'aver capito è che una starvation può diventare deadlock?
Quando ogni filosofo attende che si leberi l'altra bacchetta con cui mangiare, ma se capita che tutti attendono in circolo avviene il deadlock?

Il deadlock indipendentemente lo si ha quando ho una catena in cui ogni processo interessato attende che si liberi una risorsa detenuta da un'altro processo in attesa a sua volta, completando il ciclo.

Chi mi sa chiarire maglio?
TNX!

sono 2 concetti distinti.

si ha un deadlock quando un agente A si blocca in attesa che un agente B liberi una certa risorsa e B è a sua volta bloccato in attesa che A liberi un'altra risorsa. Gli agenti sono vicendevolmente bloccati e in attesa l'uno dell'altro senza possibilità di soluzione.

la starvation è la condizione per cui, pur non essendo in deadlock, un agente non riesce mai ad acquisire tutte le risorse di cui necessita. Supponi che 3 agenti A, B, C si contendano iterativamente una risorsa R senza particolari vincoli di precedenza: A acquisisce R, A rilascia R e torna a competere per essa, B acquisisce R, la rilascia e torna a competere per essa, A riacquisisce R, ecc... per puro caso C non riesce mai ad acquisire R, non perché sia bloccato, ma perché non essendoci vincoli di precedenza o altri criteri di arbitraggio, ogni agente ha, in ogni momento, la stessa probabilità degli altri di acquisire R. In questo caso si dice che C è soggetto a starvation.
Lo stesso si può dire se i criteri di arbitraggio per l'acquisizione di R fossero tali da sfavorire sempre un agente rispetto agli altri.

[mad_hhatter]

scusami, l'esempio di starvation è poco calzante perché basandosi solo sulla probabilità, prima o poi anche C deve poter entrare in possesso di R.

Riformuliamo l'esempio dicendo che ad A e B è stata accordata una priorità più alta di C sicché fin tanto che A e B tentano di acquisire R, C non sarà in grado di entrarne in possesso. Come vedi non possiamo parlare di deadlock: gli agenti non si bloccano a vicenda (c'è una sola risorsa in gioco).

Spero di essere stato più chiaro

[Matrixbob]

Originariamente inviato da mad_hhatter

scusami, l'esempio di starvation è poco calzante perché basandosi solo sulla probabilità, prima o poi anche C deve poter entrare in possesso di R.

Riformuliamo l'esempio dicendo che ad A e B è stata accordata una priorità più alta di C sicché fin tanto che A e B tentano di acquisire R, C non sarà in grado di entrarne in possesso. Come vedi non possiamo parlare di deadlock: gli agenti non si bloccano a vicenda (c'è una sola risorsa in gioco).

Spero di essere stato più chiaro

Si + calzante.
Grazie CMQ a tutti.

[tuccio`]

nel caso di deadlock, un processo non ha più la possibilità di avere la risorsa che aspetta, perché c'è un attesa circolare delle risorse e nessun processo può progredire se una risorsa non viene liberata (la storia dell'attesa circolare la si può capire disegnando un grafo "delle attese" in cui i processi sono i nodi, e c'è un arco da un nodo a un altro se il primo è in attesa di una risorsa detenuta da un altro.. è chiaro che se c'è un ciclo in un grafo così fatto, vuol dire che tutti i processi sono bloccati in attesa di qualcosa che non arriverà mai)

la starvation è l'attesa indefinita, i processi non sono bloccati, solo che non è possibile definire a priori quando arriva il loro turno.. ad esempio se hai un mutex unfair, che sblocca i processi con una politica lifo, il primo che si è bloccato potrebbe non uscirne mai

in realtà trovare un esempio di starvation è difficile perché è difficile riprodurlo in un programma, è molto più facile ad esempio trovare la starvation negli algoritmi di scheduling (ad esempio shortest remaining time)

[clockover]

Originariamente inviato da tuccio`

in realtà trovare un esempio di starvation è difficile perché è difficile riprodurlo in un programma, è molto più facile ad esempio trovare la starvation negli algoritmi di scheduling (ad esempio shortest remaining time)

qual'era quel fatto di quel processo che era stato in attesa chissà quanti anni e se ne sono accorti quando hanno spento il calcolatore appena lo trovo in rete posto il link più esempio di starvation di così

[Matrixbob]

Originariamente inviato da clockover

qual'era quel fatto di quel processo che era stato in attesa chissà quanti anni e se ne sono accorti quando hanno spento il calcolatore appena lo trovo in rete posto il link più esempio di starvation di così

era al MIT che l'han scoperto
ma quindi si verifica solo se ho alg con priorità?

[misterx]

starvation è "far morire di fame un processo" che non viene mai servito se non ricordo male.
E se ancora non ricordo male gli scheduler del tipo round robin definito "democratico" dal mio docente risolve tale problema dedicando ad esempio 20 ms di cpu per processo.

Il deadlock invece si realizza quando c'è contesa di una risorsa ed uno dei due processi contendenti non la libera mai: da qui uso di semafori e quant'altro.

[clockover]

Originariamente inviato da misterx

starvation è "far morire di fame un processo" che non viene mai servito se non ricordo male.
E se ancora non ricordo male gli scheduler del tipo round robin definito "democratico" dal mio docente risolve tale problema dedicando ad esempio 20 ms di cpu per processo.

Ma così facendo però non c'è una differenziazione tra un processo ad alta priorità, ad esempio un processo interattivo, e uno con una bassa priorità! Sarebbero trattati tutti allo stesso modo e questo non è buono!

[misterx]

Originariamente inviato da clockover

Ma così facendo però non c'è una differenziazione tra un processo ad alta priorità, ad esempio un processo interattivo, e uno con una bassa priorità! Sarebbero trattati tutti allo stesso modo e questo non è buono!

ciao,
in effetti poi ci è stato detto che ad esempio windows usa diversi tipi di scheduler a seconda del tipo di processo.
Comunque la spiegazione era per farci capire in cosa consiste la starvation

[clockover]

Si infatti è un ottimo esempio per introdurre algoritmi con fairness, per lasciare spazio poi a quelli più complessi e efficienti!

[Matrixbob]

Ma il TOP per la sincronizzazione allo stato dell'arte sono i "monitor"?

[pabloski]

il problema della starvation si risolve brillantemente con le code di priorità

in questo modo hai tante code, i processi nelle code a maggiore priorità sono "trattati meglio", ma tutte le code devono essere processate, non esiste che ci sia una coda che resta lì intoccata

[Matrixbob]

quindi stiamo parlando di problemi differenti o riguarda cose che si sovrappongono in qualche applicazione/contesto?

• starvation --> scheduling di code senza priorità pesata dall'invecchiamento
• deadlock --> richiesta di risorse per procedere

?

[pabloski]

Originariamente inviato da Matrixbob

quindi stiamo parlando di problemi differenti o riguarda cose che si sovrappongono in qualche applicazione/contesto?

• starvation --> scheduling di code senza priorità pesata dall'invecchiamento
• deadlock --> richiesta di risorse per procedere

?

direi che sono decisamente due cose diverse

la starvation è colpa del sistema operativo che dorme e non manda in esecuzione determinati processi

i deadlock sono in massima parte colpa delle applicazioni che si mettono a competere circolarmente per una o più risorse

se il primo problema il sistema operativo lo può risolvere facilmente, il secondo non è per nulla facile da risolvere

in genere il sistema operativo setta un timeout oltre il quale significa che il processo è andato in deadlock, ma poi decidere cosa fare è un altro paio di maniche

su un pc uccido il processo e buona notte, ma in una centrale nucleare le cose non sono così semplici

[misterx]

Originariamente inviato da pabloski

su un pc uccido il processo e buona notte, ma in una centrale nucleare le cose non sono così semplici

a me avevano raccontato che il razzo Arianne programmato dai francesi era precipitato per un problema di deadlock.

Difatti in molti settori tipo quello aereonautico, ma non solo, tali problemi guai se esistessero.

[pabloski]

Originariamente inviato da misterx

a me avevano raccontato che il razzo Arianne programmato dai francesi era precipitato per un problema di deadlock.

Difatti in molti settori tipo quello aereonautico, ma non solo, tali problemi guai se esistessero.

l'hanno programmato maluccio allora

adesso capisco perchè chi tiene alla sicurezza usa qnx

[Matrixbob]

Quindi quando programmo io programmatore ad esempio in Java devo essere io a gestire bene il multithreading usando correttamente i Synchronized Methods?

Della starvation invece me ne infischio?
Se Symbian ad esempio la gestisse malissimo (assunzione mia a cazzo) potrei trovarmi in quella situazione senza possibilità di operare, corretto?

[WarDuck]

Originariamente inviato da misterx

a me avevano raccontato che il razzo Arianne programmato dai francesi era precipitato per un problema di deadlock.

Difatti in molti settori tipo quello aereonautico, ma non solo, tali problemi guai se esistessero.

Assolutamente no, è andata ancora peggio se vogliamo.

Hanno riciclato un modulo pensato per i 16bit in una architettura a 32bit, non tenendo conto del possibile overflow.

Le routine di controllo (se non erro ce n'erano più di una) sono andate in panico e hanno attivato la procedura di auto-distruzione, di fatto facendolo esplodere.

Ci sono svariati esempi di cattiva progettazione e programmazione, purtroppo anche in ambito medico.

In molti di questi ambiti andrebbe testata matematicamente la correttezza totale degli algoritmi in gioco, e credo che in alcuni casi lo facciano.