Concorrenza e Sincronizzazione di Thread e Processi

Concorrenza e Sincronizzazione

• Obiettivi– garantire la mutua esclusione nell’accesso a

risorse condivise da parte di thread/processi concorrenti

– Più in generale, stabilire un coordinamento fra (sincronizzare) le azioni di thread/processi concorrenti

Mutua-esclusione• Problemi da risolvere

– Aggiornamenti perduti (lost update)• Azione: aggiornamento concorrente di un dato da parte di più

thread/processi• Risultato: l’ultimo valore sovrascrive tutti gli altri

– Letture inconsistenti (inconsistent read)• Azione: lettura di un dati che successivamente vengono modificati da altri

thread/processi concorrenti• Risultato: i calcoli basati sui dati non aggiornati producono risultati sbagliati

• Vincoli– Garantire il massimo di attività concorrenti (liveness)– Evitare lo stallo (deadlock)

• NB: Se l’accesso alle variabili condivise avviene solo in lettura (nessun thread cambia I valori) non ci sono mai problemi di mutua-esclusione

Esempio di inconsistenza

• a + 1 – 1 è sempre uguale a zero?

• Un caso pratico. Si supponga che…– a sia una variabile condivisa da 200 thread– 100 thread incrementano a– 100 thread decrementano a

• …qual è il valore finale di a?

Un occhio al codice assembler

Decremento di a load $R1, a sub $R1, 1 Store a,$R1

Incremento di a load $R1, a add $R1, 1 store a, $R1

100 thread per ogni sequenza

Possibile sequenza di esecuzionea vale inizialmente 0, comincia Thread 1

1. load $R1, a // legge il valore di a, $R1 = 02. add $R1, 1 // incremento, $R1 = 1

Preemption, cambio contesto, comincia Thread 2

3. load $R1, a // legge il valore di a, $R1 = 04. sub $R1, 1 // decremento, $R1 = -15. store a, $R1 // scrive valore di a, a = -1

Preemption, cambio contesto, continua Thread 1(NB: L’operazione 5 ha reso inconsistente la lettura 1)

6. store a, $R1 // scrive il valore di a, a = 1

Fine, a vale 1 invece che 0(NB: L’operazione 6 ha sovrascritto l’aggiornamento 5)

Inconsistentread

Lost update

Soluzione: sezioni critiche

• Una sezione critica viene eseguita senza cambi di contesto intermedi

Decremento di a test_and_set

lock load $R1, a sub $R1, 1 store a,$R1 unset lock

Incremento di a test_and_set

lock load $R1, a add $R1, 1 store a, $R1 unset lock

Mutua Esclusione in Windows: Oggetti Mutex

• Mutex = Mutual Exclusion object

• CreateMutex()• ReleaseMutex()• WaitForSingleObject()

• A basso livello, Windows usa un meccanismo hardware di sincronizzazione (sul modello test-and-set) per implementare un lock “primitivo” chiamato spinlock

Procedimento

• Si crea l’oggetto mutex– uso CreateMutex()

• Si inizia la sezione critica, occupando l’oggetto mutex– uso WaitForSingleObject()

• Alla fine della regione critica, si rilascia l’oggetto mutex– uso ReleaseMutex()

CreateMutex

• Funzione: creazione di un nuovo oggetto Mutex

HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpMutexAttributes, BOOL bInitialOwner, LPCTSTR lpName)

• lpMutexAttributes: attributi di sicurezza• bInitialOwner: se true, il Mutex viene risulta già occupato

dal processo/thread che lo crea• lpName: nome simbolico dell’oggetto

• Restituisce lo handle del Mutex creato

WaitForSingleObject

• Funzione: test_and_set di un oggetto Mutex

• DWORD WaitForSingleObject(HANDLE hMutex, DWORD dwMilliseconds)

• hMutex: il mutex da occupare • dwMilliseconds: timeout di attesa (eventualmente

INFINITE)

• Restituisce l’indicazione del motivo della terminazione (es. Timeout)

ReleaseMutex

• Funzione: rilascio (unlock) di un Mutex precedentemente occupato

BOOL ReleaseMutex(HANDLE hMutex)

• hMutex: il mutex da rilasciare

• Restituisce TRUE in caso di successo

Stati degli Handle e WaitForSingleObject

• Gli handle sono associati a “eventi di sincronizzazione”, in base ai quali possono transire fra due possibili stati:– Signaled– unsignaled

Handleunsignaled

Handlesignaled

WaitForSingleObject bloccata

[evento di sincronizzazione]

WaitForSingleObject eseguita

Handle e WaitForSingleObjectCaso dei Mutex

Handle Mutexunsignaled

Handle Mutexsignaled

WaitForSingleObject bloccata

[evento di sincronizzazione]ReleaseMutex(…)

WaitForSingleObject eseguita

CreateMutex(…,FALSE,…)

Handle e WaitForSingleObjectCaso di Thread/Processi

Handle threadunsignaled

Handle threadsignaled

WaitForSingleObject bloccata

[evento di sincronizzazione][terminazione del thread/processo]

WaitForSingleObject eseguita

CreateProcess(…)CreateThread(…)

Il nome degli oggetti

• Perché è possibile dare un nome ad un oggetto come un Mutex?– Dare un nome ad un oggetto significa dare visibilità

globale all’oggetto– Gli oggetti visibili globalmente sono accessibili da altri

processi

• Procedimento generale– Se in fase di creazione di un oggetto si specifica il

nome di un oggetto che esiste già nel sistema, viene restituito lo Handle dell’oggetto esistente

Handle table dei processi e object manager globale

Processo B

H.T.

Object Manager Oggetto 1 Oggetto 2 Oggetto 3 Oggetto 4

Processo A

H.T.

Processo C

H.T.

Gestore unico degli oggetti: li crea, cancella, li contiene, ecc….

Condivisione dei Mutex

• Se in CreateMutex di specifica il nome (terzo par.) di un Mutex già esistente– Viene restituito lo handle al Mutex esistente– Il secondo parametro (occupazione iniziale

del Mutex) viene ignorato

Coordinamento con Eventi• Un evento è una segnalazione di un processo/thread (solitamente

relativa a un cambiamento di stato) che può essere ricevuta da un altro processo/thread

• Il processo/thread che gestisce l’evento (e lo segnala) viene detto “observer”

• Il processo che riceve l’evento (e reagisce di conseguenza) viene detto “listener”

• CreateEvent() – per creare un nuovo evento o connettersi ad un evento esistente

• SetEvent()– per segnalare un evento

• WaitForSingleObject()– per ascoltare un evento, bloccandosi in attesa che sia segnalato

Handle e WaitForSingleObjectCaso degli Eventi

Handle eventounsignaled

Handle eventosignaled

WaitForSingleObject bloccata

[evento di sincronizzazione]SetEvent(...)

WaitForSingleObject eseguita

CreateEvent(…)

CreateEvent• Funzione: creazione di un nuovo oggetto evento o connessione ad uno

esistente

• HANDLE CreateEvent(LPSECURITY_ATTRIBUTES lpEventAttributes,BOOL bManualResetBOOL bInitialStateLPCTSTR lpName);

• lpEventAttributes: attributi di sicurezza• bManualReset: gestione manuale del reset (vedere ResetEvent)• bInitialOwner: se true, l’evento risulta già segnalato alla creazione• lpName: nome simbolico dell’oggetto

• Restituisce lo handle dell’evento creato (o connesso)

SetEvent

• Funzione: segnalazione di un evento

BOOL SetEvent(HANDLE hEvent)

• hEvent: l’evento da segnalare

• Restituisce TRUE in caso di successo