Nome: Sezione Critica Contesto: si ha una risorsa condivisa da proteggere dall'esecuzione concorrene (variabile globale, flusso di I/O, file) Soluzione: mutex (semaforo binario) binarysem mutex = 1; // e' possibile accedere // alla risorsa P(mutex); // entrare nella s.c. .... // nessuna operazion sul mutex V(mutex); // rilasciare la s.c. Anti-pattern: P(mutex); .... P(sem); // P potenzialmente bloccante ... V(mutex); Sintomi: deadlock Soluzione 1: rilascio della s.c. prima della P P(mutex); ... V(mutex); P(sem); Problema della soluzione 1: riacquisire sezione critica P(mutex); ... V(mutex); P(sem); P(mutex); // fra la P(sem) e la P(mutex) // altri processi si possono // inserire e quindi la condizione // che ha determinato il risveglio // puo' essere nuovamente falsa ... V(mutex); Prima soluzione al problema della soluzione 1: il risvegliato effettua nuovamente il controllo della condizione P(mutex); .... do { V(mutex); P(sem); P(mutex); } while(!condition); ... V(mutex); Vantaggi: e' semplice da implementare in particolare quando condition riguarda variabili locali al processo Svantaggi: 1. cicli di clock sprecati 2. starvation e livelock Seconda soluzione al problema della soluzione 1: tecnica ``passing the baton'' P(mutex); ... V(mutex); P(sem); // al risveglio ha gia' la sezione // critica mutex ... V(mutex); perche' ha gia' la sezione critica? perche' ogni altro processo che fa V(sem) eseguono il seguente codice P(mutex); V(sem); // il processo passa la sezione // critica ovvero // 1. si impegna a non fare lui la // V(sem) // 2. si impegna a non accedere lui // ai dati protetti dalla sezione // critica ... Soluzione 2: la s.c. viene passata (tecnica ``passing the baton'' a un altro processo prima di addormentarsi P(mutex); ... V(sem'); P(sem); ... Problema della soluzione 2: lo stesso e con le stesse soluzioni della soluzione 1 =================================== Nome: barriere di sincronizzazione Contesto: un processo A non deve eseguire un certo frammento di codice prima che B abbia raggiunto una certa istruzione Soluzione: binarysem sem = 0; // B non ha finito A { B { C1'; C1; P(sem); V(sem); C2; C2'; } Variante: caso simmetrico (A attende B e viceversa) Soluzione: binarysem semAB = 0; // B non ha finito binarysem semBA = 0; // A non ha finito A { B { C1'; C1; V(semBA); V(semAB); P(semAB); P(semBA); C2; C2'; } =============================== Nome: letargo spontaneo Contesto: un processo vuole decidere autonomamente di addormentarsi; qualunque altro processo puo' svegliarlo *dopo* che si e' addormentato Soluzione: 0-arysemaphore sem = 0; // bool sleeping = false; A { ... sleeping = true; P(sem); // per addormentarsi // poiche' sem = 0 ci si addormenta ... } B { ... if (sleeping) V(sem); ... } Problema: se il semaforo 0-ario viene controllato (ovvero e' un run-time error metterlo a n > 0) allora il codice di sopra non funziona Soluzione al problema: { nota: soluzione fallace se il codice e' cosi' semplice perche': 1. l'if sara' sempre vero quindi 2. sleeping non serve piu', quindi 3. di fatto abbiamo aggirato il problema del semaforo 0-ario controllato usando un semaforo binario } 0-arysemaphore sem = 0; // bool sleeping = false; binarysem mutex = 1; // protegge l'invariante // sleeping == true iff // c'e' un processo // addormentato su sem sempahore sem' = 0; // serve per implementare // la soluzione 2 al // problema del primo // pattern A { ... P(mutex); sleeping = true; V(sem'); P(sem); // per addormentarsi // poiche' sem = 0 ci si addormenta V(mutex); ... } B { ... P(sem'); if (sleeping) // sempre vero V(sem); ... }