Situazione di deadlock

di il
10 risposte

Situazione di deadlock

Devo poter aggiungere e cancellare un elemento in modo mutualmente esclusivo in due liste, in modo da essere coerenti tra loro.

Lista A e B
AddSharedElement(arg){                         DelSharedElement(arg){
wait(A)                                        wait(A)
wait(B)                                        wait(B)
add(arg)                                       delete(arg)
signal(A)                                      signal(A)
signal(B)}                                     signal(B)}

Questa situazione può causare deadlock in quale caso?
So che i semafori devono essere rilasciati in ordine inverso alla loro richiesta

10 Risposte

  • Re: Situazione di deadlock

    Paolovox ha scritto:


    Devo poter aggiungere e cancellare un elemento in modo mutualmente esclusivo in due liste, in modo da essere coerenti tra loro.

    Lista A e B
    AddSharedElement(arg){                         DelSharedElement(arg){
    wait(A)                                        wait(A)
    wait(B)                                        wait(B)
    add(arg)                                       delete(arg)
    signal(A)                                      signal(A)
    signal(B)}                                     signal(B)}

    Questa situazione può causare deadlock in quale caso?
    So che i semafori devono essere rilasciati in ordine inverso alla loro richiesta
    Visto che lo sai, perche' non lo fai?
    Secondo te, partendo dal tuo esempio, in quale caso ci potrebbe essere un deadlock?
    Comunque, l'esempio, cosi' come lo hai scritto, non vuol dire nulla: non si capisce in che modo le liste A e B vengono usate. Per come lo hai scritto, i wait e i signal non servono a nulla.
  • Re: Situazione di deadlock

    Sono stato poco chiaro è un esercizio sul libro Windows System Programming.
    
    A=mutex per la lista A
    B=mutex per la lista B
    
    AddSharedElement(arg){                         DelSharedElement(arg){
    wait(A)                                        wait(A)
    wait(B)                                        wait(B)
    addA(arg)                                      deleteA(arg)
    addB(arg)                                      deleteB(arg)
    signal(A)                                      signal(A)
    signal(B)}                                     signal(B)}
    Queste due liste vengono mantenute da più threads che possono effettuare l'operazione di add o del.
    Per controllare la sezione critica sono richiesti due mutex per effettuare un lock quando insieriamo un elemento che va replicato in entrambe le liste.
    Ancora non riesco a trovare un possibile flusso di elaborazione e casi di preemption che possano portare ad un deadlock.
  • Re: Situazione di deadlock

    Ritentiamo:

    SO CHE I SEMAFORI DEVONO ESSERE RILASCIATI IN ORDINE INVERSO ALLA LORO RICHIESTA

    se lo casi, perche' continui a scrivere
    
    wait(A)
    wait(B)
    ...
    SIGNAL(A)
    SIGNAL(B)
    
    ????

    Ed ora la domandona: il deadlock lo hai durante l'ACQUISIZIONE di un lock o durante il RILASCIO???
  • Re: Situazione di deadlock

    Lo continuo a scrivere perchè è questo il caso da analizzare.

    In fase di acquisizione dato che restiamo in un attesa infinita aspettando che una risorsa venga rilasciata.
  • Re: Situazione di deadlock

    E quindi, secondo te, con la configurazione di wait/signal che hai indicato, c'e' la possibilita' di avere un deadlock?

    Se si, perche'?
    Se no, perche'?
  • Re: Situazione di deadlock

    Non la trovo una configurazione sfavorevole, ho provato anche con un grafo per vedere se si creava un ciclo. Un deadlock si potrebbe verifcare nel caso in cui uno dei threads fallisca senza rilasciare una delle risorse.
  • Re: Situazione di deadlock

    Infatti: con la configurazione che hai scritto, non puoi avere un deadlock.
    Se uno dei thread fallisce dopo aver acquisito un lock e non l'altro, non hai una deadlock, ma una situazione di cattiva implementazione.

    Un deadlock lo hai quando:
    
    thread 1 acquisisce A
    thread 2 acquisisce B
    thread 1 vorrebbe acquisire B
    thread 2 vorrebbe acquisire A
    DEADLOCK
    
    nel tuo caso:
    
    thread 1 acquisisce A
    thread 2 vorrebbe acquisire A
    thread 1 acquisisce B
    thread 1 rilascia A
    thread 2 acquisisce A
    thread 2 vorrebbe acquisire B
    thread 1 rilascia B
    thread 2 acquisisce B
    ...
    nessun problema!
    
    Una delle regole per evitare i deadlock e' proprio questa:
    assegnare un ordine alle risorse ed acquisirle seguendo quest'ordine
  • Re: Situazione di deadlock

    Ti ringrazio.
    Quando un thread fallisce ed un altro resta in attesa infinita per il rilascio delle risorse si chama "starvation" ovvero morte di fame?
    Per prevenire tale situazione, tutti i threads andrebbero monitorati con un apposito gestore che controlla i loro valori di ritorno e nel caso uno fallisca, vengono rilasciate le risorse da esso acquisite?
    O quale strategia implementativa si adotta?
  • Re: Situazione di deadlock

    Paolovox ha scritto:


    Ti ringrazio.
    Quando un thread fallisce ed un altro resta in attesa infinita per il rilascio delle risorse si chama "starvation" ovvero morte di fame?
    Per prevenire tale situazione, tutti i threads andrebbero monitorati con un apposito gestore che controlla i loro valori di ritorno e nel caso uno fallisca, vengono rilasciate le risorse da esso acquisite?
    O quale strategia implementativa si adotta?
    Non esiste una strategia, ne esistono molte:

    1) ogni linguaggio di programmazione mette a disposizione dei meccanismi che possono essere attivati in caso di eccezione: try/finally di Java, la chiamata del distruttore di un oggetto allocato nello stack in C++, ecc. Sfruttando questi meccanismi, ci si assicura che un thread, sia nel caso termini correttamente, sia che termini per eccezione, rilasci le risorse

    2) si usa un timeout quando si cerca di acquisire un risorsa: se non viene acquisita in quel lasso di tempo, il thread continua con un'opportuna logica (termina con errore, segnala il problema, ecc)

    3) si usano dei lock con timeout: cioe' la risorsa rimane in carico al thread solo per un tempo massimo prestabilito, dopo di che il thread ne perde il controllo.

    Un thread non dovrebbe MAI essere ucciso dall'esterno, ma e' il thread stesso che termina correttamente o al limite si suicida.

    Un thread non deve MAI bloccarsi per un tempo infinito, ma deve sempre sbloccarsi e continuare con opportune logiche.

    Eventualmente un thread usato come watchdog potrebbe dire al thread di suicidarsi: e questo puo' essere fatto PROPRIO perche' il thread non resta MAI bloccato per un tempo infinito.

    Il starvation e' un concetto leggermente diverso: in questo caso, tutti i thread potrebbero potenzialmente acquisire le risorse, solo che alcuni non riescono mai a farlo ad esempio perche' hanno una priorita' troppo bassa e c'e' sempre un thread con priorita' piu' alta che li frega.

    Oppure il thread ottiene le risorse, ma prima di poter iniziare ad usarle gli vengono rimosse per essere consegnate a qualcun altro.
  • Re: Situazione di deadlock

    Grazie spiegazione davvero utile.
Devi accedere o registrarti per scrivere nel forum
10 risposte