L'astrazione ad alto livello fornisce un meccanismo conveniente ed efficace per la sincronizzazione tra processi; purtroppo molti anni fa la maggiore astrazione possibile era quello dell'abstract data type, ovvero variabili interne accessibili solo da codice all'interno della procedura.

Un solo processo alla volta può essere attivo all'interno il monitor. L'obbiettivo del monitor* è quindi quello di fornire un ulteriore livello di astrazione, che assicuri una programmazione più agevole mediante il tipo di dato astratto.

monitor monitor-name{
    // variabili shared
    function P1(...){...}
    function P2(...){...}
    function Pn(...){...}

    initialization code(...) {...}    //inizializzare le variabili shared
}

Pensiamo al monitor come un oggetto che offre una memoria comune a dei processi, che invocano il monitor stesso per utilizzarla.

Ad esempio se dovessimo creare un buffer condiviso, non andiamo direttamente a salvare e prelevare dal buffer, ma usiamo un monitor che gestisce il buffer, e richiamiamo solo le funzioni che lavorano sulla memoria, per salvare e prelevare.

L'implementazione del monitor mi assicura che con il suo utilizzo venga rispettata la mutua esclusione; il programmatore non deve più preoccuparsi della mutua esclusione, deve semplicemenete invocare le funzioni del monitor, ed esse verranno eseguite una per volta.

Pensiamo a processi che vogliono semplicemente leggere i contenuti della memoria. Con il monitor non è possibile; questo perchè la funzione di lettura viene eseguita, anche in questo caso, una alla volta.

Se ho un processo che modifica l'area di memoria, e tanti processi che vogliono solo leggere (e quindi essere eseguiti concorrentemente, visto che leggendo non si fanno danni, ma solo scrivendo in memoria), questi non vengono eseguiti concorrentemente, ma uno alla volta (perdendo molto tempo).

All'interno del monitor (rappresentato dall'ovale) è presente l'area dei dati condivisi; le operazioni del monitor (metodi che possiamo invocare dall'esterno per lavorare sui dati shared); infine un codice da inizializzazione.

La entry queue indica che nel monitor i processi entrano uno alla volta, e se ci sono più richieste è presente una coda di processi in ingresso, e quindi i processi che sono in attesa potranno entrare all'interno del monitor uno alla volta.

condition x, y;

Servono ad implementare all'interno di un monitor la sincronizzazione su condizione; sono interne al monitor, e quindi non visibili all'esterno. Per effettuare operazioni su queste variabili sarà necessario quindi utilizzare un eventuale metodo del monitor stesso.

Sulle variabili condition sono ammesse delle operazioni chiamate x.wait() e x.signal();

ATTENZIONE! queste due operazioni sono completamente diverse da quelle viste per i semafori.

x.wait() è un modo formale di invocare l'operazione di wait() su una variabile condition che ho predichiarato chiamata x. Se un processo in esecuzione nel monitor richiama una funzione x.wait() su una variabile condition, il processo viene sospeso. La wait delle variabili condition, quindi, sospende irrevocabilmente il processo che la esegue.

x.signal() nel momento in cui viene eseguita va a vedere la coda di processi sospesi sulla variabile condition x; quindi, associata ad ogni variabile condition è presente una coda di processi sospesi.

Capiamo quindi che la tecnica usata per il risveglio è di tipo FIFO. Quando chiamiamo signal() viene risvegliato il processo che è in attesa da più tempo, cosa non garantita per i semafori.

Qualora non ci fossero processi sospesi su quella variabile condition, la signal() non ha effetti. Questo non accadeva con i semafori, visto che in quel caso sia se erano o non erano presenti processi in attesa, la variabile veniva sempre incrementata.

In questa immagine notiamo le code associate alle variabili condition x e y. Questi saranno risvegliati nell'ordine in cui sono arrivati.

Reminder: nel monitor entra un processo per volta.

Situazione 1:

• Siamo dentro il monitor; una delle operazioni invoca una wait(), perchè ad esempio voglio prelevare qualcosa da un buffer, ma è vuoto e devo sospendermi (processo).

• Il monitor è quindi libero ed un altro processo può entrare.

Situazione 2:

• Pensiamo al processo che chiama la signal().

• E' arrivato un processo e ci sono dei processi in sospeso perchè dovevano effettuare un'operazione ma non era ancora il momento. (la sospensione su condizione è proprio questo, ovvero un processo che attende di eseguire un'operazione finchè non è il momento)

• Il processo risvegliante esegue un'operazione ed esegue una segnalazione; effettuare una signal significa che uno dei processi in attesa sulla coda di x, può andare in esecuzione.

Ovviamete il nuovo processo non può essere eseguito insieme al processo precedente! Bisogna fare una scelta:

• Chi ha fatto la signal si sospende ed attende di essere risvegliato in un secondo momento. Il processo che è stato risvegliato riprende l'esecuzione immediatamente. Questa tecnica si chiama Signal And Wait. Ovviamente il processo che ha chiamato la signal() non va a finire nella entry queue, siccome era già all'interno del monitor, quindi "salta la fila".

• Signal and continue: Questa tecnica è quella più utilizzata (anche da java). Il segnalatore procede ed il processo risvegliato (in attesa) viene posto nella entry queue, ma andando sulla coda non è necessariamente il primo!

Se diversi processi sono in coda su una variabile condition x, e viene eseguito x.signal(), quale processo deve essere ripreso?

A volte i processi possono avere delle priorità: ad esempio posso assegnare priorità alta ai processi real time per far sì che essi possano essere eseguiti per primi.

Con i semafori questo meccanismo non è possibile.

FINE CAPITOLO 6

Nota per chi utilizza un libro di edizione <10 : nelle vecchie edizioni i capitoli 6 e 7 erano entrambi compresi nel capitolo 6.

🏁 05-19 00:20

Questa soluzione prevede l'utilizzo di 3 semafori in maniera "creativa":

C'è un semaforo che viene utilizzato esclusivamente per la mutua esclusione, chiamato mutex, inizializzato al valore 1.

Gli altri due semafori sono simmetrici: il primo, full inizializzato a 0, conta il numero delle posizioni "piene", mentre l'altro, empty inizializzato al valore n, conta i posti vuoti.

Struttura del processo produttore:

while (true) {
    // produce un item in next_produced
    wait(empty);
    wait(mutex);
    
    // aggiunge il prossimo prodotto al buffer

    signal(mutex);
    signal(full);
}

Simmetricamente, il consumatore (colui che preleva dal buffer), attende se full == 0, e dopo essere entrato segnala incrementando empty.

Supponiamo di avere una struttura dati, o una variabile, che deve essere condivisa da più processi; alcuni di questi processi vogliono apportare delle modifiche, come ad esempio aggiornare il valore della variabile, mentre altri volgiono semplicemente leggerlo. Come gestiamo questo problema di sincronizzazione?

La soluzione potrebbe essere molto semplice: non mi interessa se sei lettore o scrittore, faccio operare tutti i processi in mutua esclusione, risolvendo così il problema. Questa soluzione funziona, ma perchè impedire a processi che vogliono solo leggere di leggere allo stesso momento?

Vorrei quindi un meccanismo leggermente più flessibile della mutua esclusione, che permetta ai lettori di sovrapporsi tra di loro.

Un po' tutti i sistemi operativi dispongono di particolari primitive che consentono proprio l'accesso in lettura, bloccando solo i processi che effettuano delle scritture.

L'idea è quella di trattare tutti i lettori come se fossero un unico processo, proprio perchè in realtà, se è presente un solo lettore, o molti, all'atto pratico non cambia nulla. La mutua esclusione va fatta tra il gruppo dei lettori, ed uno degli scrittori (sempre processi).

Cosa utilizza?

• Un semaforo mutex inizializzato ad 1 usato solo per la mutua esclusione, per essere sicuri che quando lavoriamo su read_count ci sia la mutua esclusione.

• red_count una variabile condivisa tra tutti i lettori ed inizializzata a 0

• Un altro semaforo rw_mutex inizializzato ad 1 che permette di gestire le attese tra lettori ed il gruppo degli scrittori. Questo semaforo tratta tutti i lettori come un unico processo (guardare il codice del lettore per capire meglio).

Struttura di un generico scrittore

while (true) {
    wait(rw_mutex);
    ...
    // azioni dello scrittore
    ...
    signal(rw_mutex);
}

Lo scrittore deve solo richiedere un accesso in mutua esclusione, siccome deve essere l'unico ad accedere alla variabile, senza altri scrittori o lettori.

Struttura del lettore

while (true) {
    wait(mutex);
    read_count++;
    if(read_count == 1)
        wait(rw_mutex);
    signal(mutex);

    ...
    //
    ...

    wait(mutex);
    read count--;
    if(read_count == 0)
        signal(rw_mutex);
    signal(mutex);
}

Il lettore è più complicato, infatti la logica è la seguente:

il primo lettore, supposto non ci siano lettori in attività, deve fare una wait() come lo scrittore, in modo da assicurarsi i diritti di accesso esclusivi. Successivamente al primo possiamo aggiungere n lettori, e li tratto come un gruppo.

Per sapere quanti lettori ci sono in attività, usiamo la variabile read_count, che conta il numero dei lettori, ed è una variabile shared, quindi per incrementare e decrementare la variabile devo usare la mutua esclusione.

Per essere sicuro di essere in mutua esclusione utilizzo un altro semaforo, mutex. Quindi effettuo una wait() sul semaforo mutex, e quando ho l'accesso incremento il read_count.

Dopo aver incrementato, controllo se il read_count è uguale ad 1; se è uguale ad 1, quindi sono il primo lettore, devo effettuare una wait su rw_mutex (semaforo) per assicurarmi l'accesso. Appena ho accesso su rw_mutex rilascio con una signal mutex,

A questo punto posso leggere!

Cosa succede se in questo momento arriva un altro lettore? Se in questo momento arriva un altro lettore, incrementa read_count che diventa 2, quindi salta la wait su rw_mutex e va direttamente alla lettura della variabile in memoria, dopo aver rilasciato mutex.

Uscita Dopo aver fatto la lettura devo ridurre il numero di lettori in attività, devo quindi richiedere la mutua esclusione per scrivere sulla variabile condivisa, se read_counter è uguale a zero, vuol dire che il processo che sta uscendo era anche l'ultimo dei lettori, ed in questo caso deve effettuare una signal() per rilasciare rw_mutex. Infine rilascia anche mutex.

Con questa soluzione, viene data una priorità ai lettori: supponendo che arrivi sempre un nuovo lettore a leggere sulla variabile condivisa, questi si aggiungeranno uno dopo l'altro, e lo scirttore attenderà per sempre.

Dobbiamo quindi avere una disciplina più flessibile, che gestisca lo scheduling ed alterni lettori e scrittori per evitare una possibile starvation (ovvero l'attesa infinita da parte degli scrittori).

Morale della favola: Questa soluzione è brillante e quasi funzionante, ma non è la soluzione adatta al problema.

Ci sono 5 filosofi seduti attorno ad un tavolo, che passano la loro vita a pensare ed a mangiare, senza fare nient'altro. Al centro del tavolo è presente un piatto di riso, e tra ogni filosofo e quello adiacente è presente una sola bacchetta cinese per filosofo.

Se un filosofo vuole mangiare, è costretto a sincronizzarsi con il vicino di destra e di sinistra, proprio per poter utilizzare entrambe le bacchette.

Questo diventa quindi un problema di esclusione a coppie.

Una soluzione che risolve il problema, fa utilizzo di un semaforo per ogni bacchetta cinese, inizializzato ad 1.

Ogni filosofo deve quindi effettuare una wait() sulla bacchetta sinistra e destra, ed aspettare quindi che entrambe siano disponibili.

while (true){
    wait(chopstick[i]);
    wait(chopstick[ (i+1) % 5]);

    //il filosofo magna
    
    signal(chopstick[i]);
    signal(chopstick[ (i+1 % 5)]);
    
    //pensa per un po'
}

codice dell'i-esimo filosofo

Purtroppo la soluzione non funziona.

Il problema è che se tutti tentano di mangiare più o meno contemporaneamente, tutti i filosofi effettueranno una wait sull'i-esima bacchetta, questo vuol dire che tutti riusciranno ad ottenere la mutua esclusione sulla bacchetta di sinistra, e tutti vogliono anche la bacchetta di destra, che non sarà presente per via del fatto che sono già tutte "occupate".

Diventa quindi una situazione di stallo, in gergo deadlock. Non possiamo quindi accettare la soluzione.

Basta semplicemente che uno dei 5 filosofi inverta l'ordine di accesso alle bacchette.

Se i primi 4 richiedono la mutex prima sulla bacchetta di Sx e poi quella di Dx, ed il quinto invece richiede la mutex prima su quella di Dx, il problema non si verifica.

Ammesso che tutti richiedano l'accesso contemporaneamente, il quinto non riuscirà ad avere la mutex ne sulla bacchetta di Sx ne su quella di Dx.

In questo modo tutti i filosofi riescono a mangiare a rotazione, basta solo inserire una asimmetria.

Alla fine del capitolo 7 sono presenti diversi esempi di sincronizzazione su sistemi operativi noti, che il professore salta.

POSIX dispone di:

• mutex locks

• semafori

• variabili condition

Java da la possibilità di creare dei threads; se un metodo viene dichiarato synchronized, il thread chiamante possiede il lock per l'oggetto, in parole povere, il metodo viene eseguito in mutex.

Inoltre, è possibile utilizzare due operazioni simili a wait() e signal() dei monitor; questo significa che ogni oggetto java ha un mutex definito internamente, ed un variabile condition.

public synchronized void insert(E item){
    while(count == BUFFER_SIZE){
        try{
            wait();    // corrispondente wait
        }
        catch(InterruptedException ie){}
    }

    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
    count ++;

    notify();            //corrispondente signal
}

FINE CAPITOLO 7

🏁 05-19 1:05

I deadlock sono un fenomeno abbastanza generale, applicabile anche alla vita reale:

Pensiamo a due persone che hanno bisogno di coltello e forchetta per mangiare; uno ha il coltello e l'altro ha la forchetta, nessuno presta all'altro il suo utensile, e quindi entrambi restano bloccati senza poter mangiare.

Abbiamo il generico sistema, al cui interno sono poste delle risorse: Spazio in memoria, I/O devices, ecc. Le risorse sono indicate con R1, R2, ... , Rn.

Il discorso è il seguente: dobbiamo disciplinare in qualche modo l'accesso alle risorse, per evitare fenomeni in cui nessuno può andare avanti, ed i processi restano bloccati per sempre.

L'idea è quella di utilizzare un protocollo che:

• Faccia richiesta della risorsa.

• Utilizzi la risorsa.

• Rilasci la risorsa non appena ha finito.

Quando è presente un deadlock, ci troviamo in un caso in cui queste quattro condizioni sono vere:

• Mutua esclusione: un solo processo alla volta può utilizzare una risorsa. Infatti se una risorsa fosse condivisibile, il problema non si porrebbe.

• Hold and wait: ogni processo ha almeno una risorsa, e ne vuole acquisire un'altra addizionale. Nell'esempio della forchetta, se una persona avesse entrambe le posate, ed un'altra nemmeno una, il problema non si pone. Nei casi di deadlock ognuno ha una risorsa, ma non vuole rinunciarvi.

• No Preemption (prelazione): una risorsa può essere rilasciata solo volontariamente dal processo che la trattiene, dopo che il dato processo ha completato il suo task.

• Attesa circolare: Il caso più semplice di deadlock è quello tra due processi, dove entrambi i processi vogliono una risorsa del corrispettivo, ma nessuno dei due è disposto a rilasciarla. Questa teoria può essere estesa ad N processi, come nel caso dei filosofi.

I Deadlock sono situazioni in cui dei processi restano bloccati per sempre, ovvero questi due processi non verranno sbloccati mai dalla situazione corrente; se invece un processo resta bloccato per un dato tempo, anche lunghissimo, non siamo in un caso di deadlock.

E' evidente che il metodo più semplice per esaminare le dinamiche dei deadlock, è quello di costruire dei grafi.

Reminder: un grafo è un insieme di Vertici V e di archi E, e possono essere di tipo orientato o non orientato.

L'idea è quella di avere due tipi di vertici:

• Vertici che corrispondono ai processi

• Vertici che corrispondono alle risorse

Anche gli archi sono di due tipi:

• Processo ➡️ Risorsa se richiedo la risorsa

• Risorsa ➡️ Processo se la risorsa è stata assegnata ad un processo.

I processi (T1,T2,T3) sono rappresentati da Cerchi.

Le risorse (R1,R2,R3,R4) sono rappresentate con i rettangoli.

I "pallini" all'interno delle risorse rappresentano le istanze in cui le risorse sono disponibili; ad esempio R4 abbiamo 3 istanze.

• La risorsa R1 (una sola istanza) è stata assegnata al processo T2.

• T2 ha anche il possesso di una risorsa R2 che gli è stata assegnata.

• T1 ha una risorsa R2.

• T2, non solo ha le risorse R1 ed R2, ma vorrebbe anche la risorsa R3: T2 ➡️ R3, ma R3 al momento è assegnata a T3.

Se riesco a trovare un percorso chiuso (ciclo), in qualche modo c'è una catena di richieste infinite, che vanno a bloccare il tutto.

In questo caso non è presente nessun ciclo, ed infatti non è un caso di Deadlock.

Potrebbe sembrare un caso di deadlock, ma questa situazione, prima o poi, verrà risolta con T3 che finisce di utilizzare R3, che viene quindi assegnata a T2.

Se le risorse sono multiple no.

In questo caso, T2 e T4 non hanno richieste "inesaudite", per cui prima o poi rilasceranno R1 ed R2 che potranno così essere assegnate a T1 e T2.

Quindi la presenza di un ciclo è una condizione necessaria, ma non sufficiente.

Se un grafo contiene un ciclo:

• Se è presente una sola istanza per tipo di risorsa, allora abbiamo un deadlock.

• Se abbiamo diverse istanze per tipo di risorsa, abbiamo la possibilità di un deadlock.

FINE LEZIONE 9