Deadlock o non deadlock

[Luca1995]

Buongiorno a tutti! Ho un problema a capire se un certo algoritmo di sincronizzazione può portare a deadlock o meno. Il problema è riportato nel libro "The art of multiprocessor programming" a pagina 26, dove dicono che ci sia deadlock. Il codice di sincronizzazione è il seguente:

Codice: Seleziona tutto

class LockTwo {
    private volatile int victim;

    public void lock(){
        int i = ThreadID.get();
        victim = i;
        while(victim == i);
    }

    public void unlock(){}
}


Il libro dice che in un'eventuale esecuzione sequenziale delle lock da parte di due Thread A e B, si può incorrere in un deadlock. Io al massimo vedo la possibilità di finire in starvation a causa dell'altro processo che non ha interesse a chiamare la lock.
Voi cosa ne pensate?

[PietroBaima]

Buongiorno a tutti! Ho un problema a capire se un certo algoritmo di sincronizzazione può portare a deadlock o meno.

Anche Turing aveva lo stesso problema. Non ne è uscito, pur risolvendolo.

Il problema è riportato nel libro "The art of multiprocessor programming" a pagina 26, dove dicono che ci sia deadlock. Il codice di sincronizzazione è il seguente:

Codice: Seleziona tutto

class LockTwo {
    private volatile int victim;

    public void lock(){
        int i = ThreadID.get();
        victim = i;
        while(victim == i);
    }

    public void unlock(){}
}


Il libro dice che in un'eventuale esecuzione sequenziale delle lock da parte di due Thread A e B, si può incorrere in un deadlock. Io al massimo vedo la possibilità di finire in starvation a causa dell'altro processo che non ha interesse a chiamare la lock.
Voi cosa ne pensate?

carino. Ha ragione il libro.

Codice: Seleziona tutto

class LockTwo {

    public void lock(){
        int i = ThreadID.get();
        while(1);
    }

    public void unlock(){}
}


[Luca1995]

Continuo a non capire.....

[PietroBaima]

Tutte le volte che dipendi da un processo esterno hai la possibilità di una lock.
Non a caso la variabile è volatile.
Potresti anche finire in starvation ma non è importante in questo caso.

[AjeieBrazov]

Continuo a non capire.....

Il codice che hai scritto si comporta come quello scritto da PietroBaima.

[PietroBaima]

In realtà la variabile è volatile, quindi potrebbe essere modificata da un parallel, ma non mi piace per niente scrivere del codice che dipende da un processo esterno, preferisco mettere sempre un watchdog.

Comunque, per me, il codice può comportarsi per come l'ho modificato e questo, se si vuole scrivere codice robusto, non deve mai accadere.

[Luca1995]

Dato che l'esempio dipende troppo da come è scritto il codice vediamo il seguente (che è quello proposto in classe dalla professoressa):

Codice: Seleziona tutto

variabile victim condivisa tra i thread con r/w atomiche!

void lock(){
    int i = this.ID;
    victim = i;
    while(victim == i);
}

void unlock(){}


Mettiamo che i thread che si alternano per entrare nella sezione critica siano 2.
Da quello che so io, perché ci sia deadlock tutti i thread non devono riuscire in nessun modo ad effettuare progressi.
Supponendo che A sia fermo sul suo ciclo di attesa, B è comunque libero di fare quello che vuole finché non richiede l'accesso alla sezione critica, sbloccando B.
Da come wikipedia definisce il deadlock (ed anche il libro SilberSchatz di sistemi operativi) sono necessarie alcune condizioni affinché ci sia, per esempio quella dell'attesa circolare: in questo caso però B non è in attesa di niente di quello richiesto anche da A, quindi è libero di fare ciò che vuole e quindi in caso di sbloccare A. Dato che A è quindi sbloccabile (anche se potenzialmente dopo tantissimo tempo) non penso si tratti di deadlock. Dal deadlock non si dovrebbe poter uscire. Non riesco ad immaginare una situazione in cui uno dei thread sia in attesa e non potrà mai più continuare la sua esecuzione.

In questo caso mi sembra molto più appropriato il termine starvation, quindi che cosa sbaglio?

[PietroBaima]

Vediamo se riesco a spiegarmi meglio.

La volatile potrebbe modificarsi fra il gray space, cioè quello spazio definito fra la volatilità della variabile e il controllo.
Se succede nessuno dei due processi è in grado di recuperare il lock, che finisce in dead end.
Per questo si usano i watchdog.

[Luca1995]

Okey, ho capito che nel caso il problema provenga dalla variabile di tipo volatile si incorre in un deadlock. In classe però viene spiegato che il deadlock è portato da un'esecuzione di tipo sequenziale dei due programmi del tipo:

Codice: Seleziona tutto

Thread A: victim = A;
Thread A: while(victim == A);
scheduler action
Thread B: victim = B;
Thread B: while(victim == B);


Lasciate quindi da parte per un attimo il fatto che la variabile è volatile ed ipotizzate solo che è un intero condiviso tra i thread con accesso già reso atomico dal sistema o dalla VM.
È ancora possibile questo deadlock?