Programmazione con i Monitor

Semafori con i Monitor

Vediamo come realizzare un semaforo contatore tramite Monitor. Consideriamo il problema dei filosofi a cena in cui vogliamo limitare il numero di filosofi a tavola a 4. Con i semafori è sufficiente inizializzare un semaforo al valore 4 e eseguire una P(S) prima di raccogliere le bacchette e una V(S) dopo che le bacchette sono state depositate.

Estendiamo il Monitor tavola con due nuove procedure siediti e alzati che vengono invocate come segue:

Per realizzare tali procedure è sufficiente un contatore per il numero di sedie libere e una condition per la coda di attesa:

La procedura siediti può essere invocata 4 volte prima di diventare bloccante. La procedura alzati incrementa il contatore e sblocca un thread in coda. Di fatto siediti e alzati si comportano come P e V su un semaforo inizializzato a 4.

Notare che con questa soluzione non è più necessario che le bacchette vengano raccolte in maniera atomica in quanto lo stallo viene evitato.

Esercizio: Provare a realizzare la soluzione in cui le bacchette vengono raccolte singolarmente e testare che le procedure alzati() e siediti() prevengono lo stallo.

Lettori e scrittori: la notifyAll()

Rivediamo il problema dei lettori e scrittori che avevamo risolto tramite semafori.

Abbiamo due tipologie di thread:

Dobbiamo realizzare il Monitor rw in modo che sia garantito l’accesso a un numero arbitrario di lettori oppure a un solo scrittore.

È importante capire quale informazione è necessaria per realizzare la sincronizzazione. In questo caso specifico dobbiamo sapere se c’è uno scrittore in sezione critica oppure il numero esatto di lettori in sezione critica. I lettori entrano se non c’è uno scrittore, lo scrittore entra se non c’è nessuno in sezione critica.

Come vediamo sopra, i monitor permettono di ‘programmare’ la sincronizzazione tramite variabili senza preoccuparsi della mutua esclusione che viene garantita automaticamente.

In end_scrivi() notiamo l’uso di notifyAll() sulla condition c. Questa operazione sblocca tutti i thread in coda. In questo caso specifico è necessario sbloccare tutti i thread perché eventuali lettori in attesa riescano ad entrare tutti in sezione critica. Notare che grazie al ciclo while che racchiude le wait tutti i thread ri-verificheranno la condizione di attesa prima di proseguire.

La notifyAll() ha anche la particolarità di affidare allo scheduler di sistema la scelta del prossimo thread che entrerà in sezione critica. Generalmente questo evita starvation grazie ai meccanismi anti-starvation presenti negli scheduler di tutti i moderni sistemi operativi.

Rispettare l’ordine d’arrivo

Mostriamo come sia possible rispettare l’ordine di arrivo dei thread nonostante l’uso di notify e notifyAll. Consideriamo l’esempio precedente e aggiungiamo una coda q al Monitor. I thread vengono accodati appena invocano le funzioni ini_leggi e ini_scrivi, e per uscire dal while devono essere i primi della coda q. I thread vengono rimossi dalla coda alla fine delle suddette procedure. I thread passano il proprio id alle procedure del Monitor per poter essere accodati:

Notare che oltre alla coda abbiamo

  1. aggiunto una notifyAll alla fine di ini_leggi per sbloccare altri lettori in attesa che potrebbero essersi ribloccati perché non erano i primi della coda q;
  2. sostituito la notify con una notifyAll in end_leggi in quanto non siamo sicuri che i thread sulla coda q sono nello stesso ordine dei thread sulla condition: dobbiamo sbloccarli tutti e lasciare che loro stessi si riblocchino (solo il primo passerà). Di fatto, usando questo metodo dobbiamo usare sempre notifyAll per evitare stalli: se sblocchiamo un solo thread ed esso non è il primo della coda, si ribloccherà e nessun altro thread verrà eseguito.

Leave a Reply

Your email address will not be published. Required fields are marked *