Introduzione

Definiremo alcuni concetti relativi all'accesso di risorse condivise, considereremo alcune situazioni critiche che possono presentarsi e analizzeremo le soluzioni esistenti in letteratura.

Processo

Definiamo in questa sede un Processo come una sequenza di istruzioni svolte da un calcolatore per eseguire un programma P. Un processore è un dispositivo in grado di eseguire tali azioni. Un processore può alternare nel tempo l'esecuzione di istruzioni di programmi diversi, viceversa l'esecuzione di un programma può essere sospesa e ripresa più volte, anche su processori diversi. Il processo può dunque essere complessivamente svolto in tempi diversi e su processori diversi.

Nota L'interruzione di un processo è un'operazione di solito in carico al sistema operativo, ma per i linguaggi interpretati o semi interpretati può anche essere gestito indirettamente dall'ambiente di run-time in cui avviene l'esecuzione.

In ogni istante t un processo può trovarsi essenzialmente in due stati: in esecuzione o in attesa. Quando è posto in attesa, il suo stato è preservato per poter consentire la ripresa della sua esecuzione. Si noti che il salvataggio dello stato ed il ripristino è un'operazione che in generale richiede delle risorse e del tempo.

Risorse

Si definiscono risorse tutti i dispositivi, hardware o software, fisiche o virtuali utilizzate da un processo. Ad esempio consideriamo un database come risorsa, così come (ad un livello più basso) un disco rigido, ma anche una zona di memoria o un'istanza di una classe può essere considerata una risorsa, a seconda del livello logico in cui ci troviamo.

Distinguiamo risorse permanenti e risorse consumabili. Le risorse permanenti possono essere usate ripetutamente da più processi. Le risorse consumabili sono create da un processo e distrutte da un altro.

Possono presentarsi vari problemi quando più processi in esecuzione utilizzano una stessa risorsa:

potrebbe essere necessario impedire che uno dei due inizi ad usarla prima che l'altro abbia finito, si pensi banalmente ad una stampante, in cui non è possibile stampare righe da un documento intervallate da righe di un altro documento
ogni processo presume di conoscere lo stato della risorsa quando inizia ad operarvi, ma se più processi vi operano simultaneamente questo non è più vero

pertanto è necessario gestire queste situazioni.

Interazioni tra processi

Due processi A e B possono interagire tra loro in modo diretto, se il processo A produce una risorsa che il processo B consuma (in questo caso si dice che B dipende da A), o in modo indiretto, se competono nell'uso di una risorsa, ossia ne fanno uso entrambi.

Nel caso di interazione indiretta abbiamo un problema detto "della mutua esclusione", mentre nell'interazione diretta abbiamo una situazione di "produttore - consumatore"

Problema della mutua esclusione

Sia R una risorsa, ed i processi P1..Pn, si vuole garantire che in ogni istante vi sia solo un processo che accede ad R, e che ogni processo riesca ad ottenere l'accesso alla risorsa in un tempo finito.

Questo problema può essere risolto con l'uso di un arbitro che conserva un indicatore S sulla risorsa, che vale 1 se la risorsa è al momento in uso da parte di qualche processore, o 0 se nessun processore la sta utilizzando. L'arbitro può essere un dispositivo o un algoritmo. I processori chiedono all'arbitro l'uso della risorsa, e l'arbitro valuta se in quel momento la risorsa è libera, nel qual caso l'assegna al processore con priorità più elevata. Alla fine di ogni ciclo di esecuzione (ossia sin quando il processo non viene nuovamente sospeso per qualche motivo), la risorsa viene liberata.

Distinguiamo due casi quando un processo richiede una risorsa che però è già in uso:

il processo continua ad impegnare il processore in attesa della risorsa (attesa attiva)
il processo viene sospeso sin quando la risorsa non diviene disponibile (attesa passiva)

Il secondo caso è certamente da preferirsi poiché consente ad altri processi di essere eseguiti nel frattempo e rende più efficiente l'uso del processore.

Si noti che l'arbitro interagisce direttamente con i processori e non con i processi, che in questo caso accedono alla risorsa in modo trasparente come se ne detenessero l'uso esclusivo.

In questo caso la competizione sulla risorsa è "nascosta" ed implementata dall'arbitro, pertanto si ha una interazione indiretta tra i processi.

Questo caso può sembrare "accademico" e confinato alla progettazione di moduli hardware, ma lo è di meno quando l'arbitro è una classe progettata per gestire una risorsa.

Interazione diretta

In questo caso i processi, mediante opportune tecniche e convenzioni, ad esempio scambiandosi dei messaggi di sincronizzazione, risolvono i problemi di competizione senza ricorrere all'uso di un arbitro.

In questo caso si parla anche di cooperazione tra i processi, che dovranno contenere delle istruzioni apposite per prevenire i conflitti.

A livello di linguaggio macchina, il nucleo di questi meccanismi risiede in istruzioni di test and set, cmpxchg o xchg su cui viene applicato un lock a livello di bus per impedirne la concorrenza.

Produttore consumatore

Supponiamo che ci sia un processo A che produce delle risorse R ed un processo B che le consumi. Distinguiamo due primitive che vengono usate per gestire questa situazione, wait e cause.

Il processo che produce invocherà la primitiva cause( Ri) per ogni risorsa prodotta ed il processo che le consuma effettua una R = wait ( ) quando necessita della risorsa.

E' da notare che non è detto che ci sia un processo in attesa di consumare le risorse quando vengono prodotte, e non è neanche detto che quando un processo esegue la wait ( ) vi sia già una risorsa da consumare.

Se un processo esegue la wait ( ) quando non vi sono ancora risorse disponibili, viene posto in stato di attesa sin quando questa non è disponibile. Tale processo sarà ripreso quando il produttore eseguirà la primitiva cause.

Prima di analizzare come si risolvono i problemi di sincronizzazione in un linguaggio specifico, considereremo il C#, esaminiamo in genere quali strumenti esistono allo scopo:

mutex sono oggetti in generale che consentono l'accesso esclusivo a risorse
semaforo è un oggetto che gestisce l'accesso condiviso ad una risorsa, non necessariamente esclusivo, gestendo una coda di richieste da parte di più processi

In C# esiste l'istruzione lock, che è il meccanismo più semplice per gestire una risorsa condivisa, e si usa così:

object x= new object(); //rappresenta simbolicamente la risorsa condivisa
lock (x) {
    // istruzioni che accedono alla risorsa associata ad x

    //    solo un processo alla volta può eseguire questo codice o altre 
    //    sezioni simili incorporate in un lock(x)
}

x in questo caso rappresenta la risorsa condivisa, e potrebbe essere una variabile di istanza o statica a secondo della "portata" che si intende dare al lock. Se più processi eseguono quello o altri blocchi di istruzioni che fanno riferimento alla stessa variabile x, la loro esecuzione sarà sospesa all'ingresso dell'istruzione lock, sin quando il processo che ne ha acquisito il lock non termina l'esecuzione di quel blocco.

L'istruzione lock è sintatticamente equivalente ad una coppia di istruzioni Monitor.enter(x) e Monitor.exit(x) che vedremo tra poco.

In C# ci sono varie classi per gestire la sincronizzazione tra più processi, di cui elenco di seguito i principali, con i principali metodi:

Mutex consente di ottenere l'accesso esclusivo ad una risorsa. Si avvisa che esistono anche altri metodi di Mutex che consentono, tramite un nome, di accedere a mutex esterni all'applicazione, tramite meccanismi forniti dal sistema operativo ospitante.

Mutex(bool initiallyOwned) costruisce il mutex, eventualmente auto-assegnandoselo se initiallyOwned è true
bool waitOne() acquisice un blocco esclusivo sul mutex. L'esecuzione si blocca, anche indefinitamente, sin quando non è acquisito il blocco. Il metodo restituisce sempre true.
bool waitOne(int milliseconds) simile al precedente, ma con un limite di tempo per l'acquisizione; se il lock non è acquisito entro il tempo prefissato, la funzione restituisce false
void ReleaseMutex() rilascia il mutex

Semaphore limita il numero di processi che accedono simultaneamente ad una risorsa

Semaphore(int nInitial, int nMax) crea un semaforo per l'accesso ad una risorsa a cui potranno accedere massimo nMax processi e inizialmente si assume che nInitial stiano già accedendo ad esso
bool waitOne(), bool waitOne(int milliSeconds) come per il Mutex
int Release() rilascia il semaforo e restituisce il numero di utilizzatori prima dell'istruzione Release
int Release(nTime) rilascia il semaforo nTime volte, è equivalente a chiamare Release() nTime volte

SemaphoreSlim simile a Semaphore ma non utilizza il kernel di sistema, quindi è più efficiente, ma funziona a patto che sia usato all'interno di uno stesso programma. Non presenta le varianti "per nome" di Semaphore e del Mutex

EventWaitHandle rappresenta un evento di sincronizzazione

EventWaitHandle(bool initialState, EventResetMode tipoReset) crea un evento con uno stato iniziale (risorsa disponibile=true o non disponibile=false), ed un tipo di reset. Se il tipo reset è autoReset, l'evento diventa non disponibile non appena un processo ne ottiene l'accesso (con waitOne ad esempio). Se il tipo reset è manualReset, occorre chiamare i metodi Reset e Set per cambiarne lo stato.
bool Reset() imposta l'evento come non disponibile (e bloccare i vari processi), restituisce true se riesce
bool Set() imposta l'evento come disponibile (e sbloccare uno o più processi)
bool waitOne(), bool waitOne(int milliSeconds) come per il Mutex
bool SignalAndWait(WaitHandle toSignal, WaitHandle toWait) rilascia il lock su un evento (toSignal) e si mette in attesa di un altro (toWait), sin quando non viene rilasciato.

Monitor garantisce l'accesso ad una risorsa condivisa, ed è simile per certi versi all'istruzione lock, ma consente di riferirsi anche a lock di sistema su oggetti esterni al programma

static void Enter(object o) rimane in attesa della risorsa o, sin quando non diviene disponibile
static void Exit(object o) rilascia la risorsa collegata
static void Wait(object o) rilascia la risorsa e si mette in attesa della risorsa stessa (che avviene tramite una Pulse)
static void Pulse(object O) rilascia nuovamente la risorsa al processo che l'aveva rilasciata con Wait.

I metodi Wait e Pulse della classe Monitor servono per implementare comportamenti cooperativi come quello del produttore-consumatore.

Polling vs Event Driven

I metodi considerati si intendono essere tutti "event driven" ossia il thread che li esegue rimane bloccato e in attesa "passiva", ossia non impegna il processore, sin quando il lock non viene acquisito.

Questo meccanismo si contrappone al meccanismo di "polling" in cui il processo interroga, in maniera attiva, eventualmente ad intervalli di tempo, lo stato di una risorsa, sin quando questa non divenga disponibile.

Considereremo ora alcuni problemi classici che ricorrono nell'ambito dell'accesso concorrente a risorse condivise e ne schematizzeremo una soluzione.

C# Produttore Consumatore- semaphore

Vediamo un esempio utilizzando l'oggetto semaphore

public class Producer {
    static List<T>  data = new List<T>();
    static object queue= new Semaphore(initialCount:1, maximumCount:10);
    void produce() {
        //qualche elaborazione
        lock(data){
            data.Add(risultato);
        }
        queue.Release();
    }

    void consume() {
        queue.WaitOne();
        object dataToProcess;
        lock(data){
            dataToProcess = data[0];
            data.RemoveAt(0);
        }
        //elaborazione di dataToProcess 
        ...
    }

}

In questo esempio produce e consume potranno essere usati in thread diversi, ad esempio ci potrebbe essere un thread sempre attivo che utilizza tutti i dati prodotti:

Task.Run ( () => { while(true) consume(); } );

mentre il metodo produce potrebbe essere chiamato in dipendenza di qualche altro evento.

E' importante l'istruzione lock in questo caso per evitare la concorrenza nell'accedere alla lista dataToProcess. Avendo fatto in modo da avere una Release per ogni elemento prodotto possiamo essere certi che il thread che esegue la consume, quando supera GetOne() troverà almeno un elemento nella coda.

C# Produttore Consumatore - senza semaphore

Senza l'oggetto semaphore avremmo dovuto effettuare un polling per assicurarci della disponibilità dei dati da elaborare, usando la sola istruzione lock, ad esempio:

 void consume() {
        object dataToProcess=null;
        lock(data){

            if (data.Count>0){

            dataToProcess = data[0];
            data.RemoveAt(0);
        }

        if (dataToProcess!=null) {
            //elaborazione di dataToProcess

        }
        ...
    }

ed in questo caso sarebbe stato necessario un polling

Task.Run ( () => { while(true) {    
    consume(); 
    await Task.Delay(5000);
} );

Appunti di informatica

sabato 20 marzo 2021

I pattern di concorrenza: accesso a risorse condivise