Il punto in cui, durante l’esecuzione dei processi, vengono modificate vbl condivise, prende il nome di sezione critica, ed è questa che deve essere protetta adottando dei protocolli di sincronizzazione.

La sezione critica

Per proteggere i dati condivisi da accessi che possono causare inconsistenza o incoerenza degli stessi occorre progettare un protocollo di sincronizzazione che tutti i processi devono usare per cooperare.

Tale protocollo deve dividere il codice in una sezione non critica, dove non c’è pericolo di accedere a dai condivisi, e una sezione critica che deve essere mutuamente esclusiva, ovvero un solo processo per volta può eseguire il codice marcato come tale.

Per garantire questo, ogni processo deve tentare di accedere alla sezione critica usando un protocollo d’entrata chiamato entry section, e comunicare di essere uscito dalla sezione critica usando un protocollo d’uscita chiamatoexit section. Come nella figura seguente.

Fig.1

Per far sì che il problema della sezione critica possa essere risolto occorre che vengano soddisfatti i seguenti requisiti:

1. Mutua esclusione. Vedi fig.1
2. Progresso. Un processo può progredire, o in altre parole superare l’entry section, ed entrare nella sua sezione critica solo dopo che qualcuno gli ha dato il permesso. La decisione se accordare o meno tale permesso deve essere presa solo dai processi che si trovano nella loro sezione critica, perché sono loro che sanno se i dati su cui stanno lavorando possono subire interferenze dal lavoro di un nuovo processo che esegue la sua sezione critica.
3. Attesa limitata. Deve esistere un limite al numero di permessi non accordati ad un processo che vuole eseguire la sua sezione critica e che invece viene superato da altri processi.

Semafori

Una soluzione al problema della sezione critica può essere trovata implementando un oggetto che ponga in attesa un processo che tenta di accedere a una risorsa già occupata (da qualche altro processo), finche questa non viene rilasciata. Un oggetto del genere funziona come un semaforo che disciplina l’accesso ad un incrocio, con la differenza che non scatta a verde automaticamente, ma quando l’automobilista (il processo) ha liberato l’incrocio, mentre chi usa l’incrocio trovato libero, pone il semaforo a rosso (per i futuri utenti dell’incrocio che dovessero arrivare quando questi è ancora occupato).

L’implementazione di un semaforo quindi appare abbastanza semplice e deve fornire almeno due primitive.

1. Semaforo.P() che viene chiamata da un processo prima della propria sezione critica. Pone il semaforo a rosso se la risorsa è libera (per garantire che nessun altro possa progredire nello stesso momento per entrare sua sezione critica), o se è occupata (quindi il semaforo era già rosso) mette in attesa il processo chiamante, magari bloccandolo in uno spinlock (un while( condizione ) ; ) oppure in modi più eleganti descritti in seguito.
2. Semaforo.V() che viene chiamata da un processo per comunicare di aver liberato la risorsa o più genericamente di essere uscito dalla propria sezione critica, permettendo a chi era bloccato di progredire.

I semafori implementati con uno spinlock hanno pregi e difetti:

1.      Se i processi che usano tali semafori hanno una sezione critica che dura molto tempo (molto di più del time slice dello scheduler) si manifestano i seguenti difetti: sprecano prezioso tempo di CPU, perché quando assegnati alla CPU altro non fanno che eseguire l’istruzione nulla che segue il while. Inoltre vengono schedulati perché il loro stato quando eseguono il while e running e quindi allo scadere del quanto di tempo vengono messi nella ready queue con conseguente context switch.

1.      Se invece i processi hanno una sezione critica che può essere eseguita brevemente: hanno il pregio di evitare un context switch che verrebbe invece causato se il semaforo fosse implementato senza la tecnica dello spinlock ma con il meccanismo di wait e notify ( che funziona come una signal ) come descritto sotto.

Un semaforo infatti può inserire nella primitiva P, al posto dello spinlock ( ; ), una chiamata a system call del S.O. che sospende il processo dallo stato di running e lo inserisce in una coda d’attesa associata al semaforo, in questo caso un processo non è bloccato in uno spinlock e quindi non spreca tempo di CPU, inoltre non trovandosi più nella ready queue non sarà schedulato per tutto il tempo che il processo che sta eseguendo la sua sezione critica non eseguirà l’exit section.

Ovviamente se la durata della sezione critica è breve, conviene di più uno spinlock.

Il processo che è stato inserito nella coda d’attesa del semaforo può uscirne a seguito di una chiamata della primitiva V, che viene in questo caso, implementata con una chiamata ad una system call che sblocca il processo.

Quindi un semaforo del genere deve avere una coda di processi in attesa. Tale coda però può essere rappresentata anche da un valore intero che riporta (se <0) solo il numero dei processi in attesa, ma non fornisce, come è ovvio, informazioni sull’ordine di risveglio. Questa è l’implementazione del semaforo usato nell’esempio del buffer sincronizzato, che è stato molto facile da realizzare perché il linguaggio con cui è stato scritto ci fornisce le primitive wait e notify che verranno spiegate in dettaglio nel paragrafo dei monitor.

Problemi tipici di sincronizzazioni che possono essere risolti con l’uso di un semaforo per sincronizzare processi cooperanti sono: il buffer limitato e il problema dei filosofi.

Regioni critiche

Questi semafori sembra abbiano risolto il problema della sezione critica, ma se non usati dal programmatore in modo attento introducono un altro problema che può essere confinato in un blocco di codice chiamato regione critica.

Una regione critica è la chiamata di un metodo del semaforo, ed critica perché un programmatore potrebbe chiamare la Semaforo.P() prima di una sezione critica e non chiamare la Semaforo.V() all’uscita, causando un deadlock, o potrebbe effettuare altri tipi di combinazioni di chiamate non corrette. Quindi in queste regioni di codice è opportuno fare attenzione.

Monitor

Un monitor è un costrutto di sincronizzazione di alto livello. Ovvero fornisce metodi d’accesso pubblici (che possono essere usati dai processi concorrenti) per accedere a dati privati (locali del monitor) sui quali si applica la sincronizzazione e ai quali solo i metodi del monitor possono accedere.

Un monitor quindi è composto da del codice d’inizializzazione che setta le sue vbl private quando un oggetto di tipo monitor viene allocato, da un’insieme di metodi o funzioni che manipolano i dati o consentono agli utenti del monitor (i processi) di accedervi, dalle variabili condivise dai processi, una lista di processi che fanno richiesta di entrare nel monitor.

Di questi processi uno solo avrà il permesso di usare i metodi del monitor per accedere alle variabili condivise, questo garantisce la mutua esclusione.

Le variabili condivise, inoltre, non sono tipi primitivi, ma oggetti di tipo condition che oltre al loro valore hanno una lista d’attesa nella quale vengono inseriti i processi che vogliono accedere a tale valore, e dei metodi che garantiscono che un solo processo per volta, fra tutti quelli inseriti nella coda d’attesa della vbl condition, possa operare su di essa, usando sempre però i metodi del monitor. Uno solo di essi quindi potrà farlo in un dato istante. Graficamente si può rappresentare un monitor come nella figura seguente.

Fig. 2

Su una variabile x di tipo condition, il processo che è riuscito ad entrare nel monitor, può effettuare queste due chiamate: x.wait o x.signal. Queste chiamate sembrano simili a quelle di un semaforo, ma in realtà sono diverse nell’implementazione e quindi negli effetti.

Chi chiama la x.wait (un processo o un thread), rimane sospeso nella coda d’attesa finchè un altro processo non chiama la x.signal, che risveglia un processo tra quelli nella coda. Se però viene chiamata un x.signal quando non c’è nessun processo nella coda d’attesa, questa chiamata non ha alcun effetto ed è come se non fosse mai stata chiamata, in un semaforo invece la signal che sarebbe la Semaforo.V incrementa il valore della vbl value del semaforo.

Un vantaggio dei semafori è che sollevano il programmatore dallo stare attento ai problemi derivanti dalle regioni critiche quando si usano oggetti come i semafori.

Tuttavia anche un monitor può essere usato male dal programmatore e introdurre problemi simili a quelli delle regioni critiche.

Sincronizzazione in java

Linguaggi di programmazione ad alto livello ed O.O. come il java adottano dei meccanismi nativi di sincronizzazione, che se non identici ad un monitor, vi si ispirano fortemente.

In java, infatti, è possibile usare una sincronizzazione su un oggetto usando metodi synchronized, istruzioni synchronized, e primitive che consentono ai thread che operano concorrentemente di comunicare per sincronizzarsi, cioè la wait e la  notify.

Prima di vedere in dettaglio l’uso di questi metodi è opportuno descrivere il modello di monitor che usa java.

Ad ogni oggetto di java, sia esso fornito dal linguaggio (String, Integre, ecc) o cerato da noi, viene associato un monitor. Tale monitor non supporta la definizione di più variabili condition, ma esiste solo una variabile condition che può ricevere e rilasciare il lock usando istruzioni o metodi synchronized. Sebbene questa scelta sembri limitante, la sua forza stà sulla semplicità.

Se due o più thread vogliono condividere un variabile ma, si vuol evitare che il loro lavoro concorrente produca risultati incoerenti o inconsistenti si possono dichiarare i metodi d’accesso o di modifica della variabile condivisasynchronized.

Se un thread a questo punto invoca un metodo synchronized su un oggetto, questi viene bloccato, cioè riceve un lock. Se un altro thread invoca un metodo synchronized sullo stesso oggetto, entrerà nella coda d’attesa dell’oggetto, restando cioè bloccato, finché il lock non verrà rimosso.

Un esempio di metodo synchronized è:

synchronized void metodo( … ){

            istruzioni

}

Si può ottenere lo stesso effetto usando le istruzioni synchronized che assegnano il lock ad un oggetto senza pero chiamare un metodo synchronized, per esempio:

public void metodo( … ){

            synchronized( espressione ){

                        istruzioni

}

}

Questi meccanismi non sono però sufficienti a garantire la mutua esclusione in tutti i casi, ecco perché vanno usati in combinazione con i metodi wait e notify che tutti gli oggetti java hanno. Tali primitive, infatti, fanno parte della classe Object, dalla quale tutti gli oggetti (pure i nostri) derivano.

Questi metodi come i lock di riferiscono a determinati oggetti. Su tali oggetti si può quindi attendere (wait) finché qualcuno non ci segnala che l’evento che attendevamo su quell’oggetto si è verificato (notify). Esiste uno standard che i thread devono rispettare nell’uso di tali metodi:

Chi vuole usare un oggetto deve priva verificare che non sia già usato, es.:

synchronized void metodo1(…){

            while( non si verifica l’evento atteso cioè è falsa condizione da verificare ) wait();

}

Chi sta usando l’oggetto e vuole comunicare a chi attende, che non lo usa più deve:

synchronized void metodo2(…){

rendi vera la condizione o fa verificare l’evento che consente all’altro thread di uscire dal wile e invoca :

notify();

}

Nota che nel metodo1 se si sostituisce il while con un if non funziona più niente.

La chiamata alla notify risveglia uno dei thread in attesa sull’oggetto, ma non si può sapere esattamente quale, se si ha la necessità di risvegliare tutti i thread in attesa si può usare a notifyAll, dopo di che, il primo thread che ottiene il lock riesce a usare l’oggetto, gli altri ritornano in attesa.