Sincronizzazione dei processi Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Outline Il problema della sincronizzazione Sincronizzazione hardware Semafori Monitor Problemi tipici di sincronizzazione Produttori/Consumatori Lettori/Scrittori 5 filosofi Stallo Operating System Concepts – 8th Edition 6.2 Silberschatz, Galvin and Gagne ©2009 Outline Il problema della sincronizzazione Sincronizzazione hardware Semafori Monitor Problemi tipici di sincronizzazione Produttori/Consumatori Lettori/Scrittori 5 filosofi Stallo Operating System Concepts – 8th Edition 6.3 Silberschatz, Galvin and Gagne ©2009 Il problema della sincronizzazione Nei Sistemi Operativi multi-programmati diversi processi o thread sono in esecuzione asincrona e possono condividere dati I processi cooperanti possono… ...condividere uno spazio logico di indirizzi, cioè codice e dati (thread) …oppure solo dati L’accesso concorrente a dati condivisi può condurre all’incoerenza dei dati nel momento in cui non si adottano politiche di sincronizzazione Per garantire la coerenza dei dati occorrono meccanismi che assicurano l’esecuzione ordinata dei processi cooperanti … Vediamo un esempio per capire meglio il problema Operating System Concepts – 8th Edition 6.4 Silberschatz, Galvin and Gagne ©2009 Il problema produttore/consumatore - 1 Consideriamo il problema del produttore e del consumatore dove: Un produttore genera degli oggetti Un consumatore preleva gli oggetti Gli oggetti vengono inseriti/prelevati in un buffer condiviso Il buffer permette di inserire al più DIM_BUFFER elementi Una variabile contatore condivisa viene incrementa ogni volta che si aggiunge un elemento nel buffer e si decrementa ogni volta si preleva un elemento dal buffer Dati condivisi: #define DIM_BUFFER 10 typedef struct { . . . } Elemento; Elemento buffer[DIM_BUFFER]; int contatore 0; Operating System Concepts – 8th Edition 6.5 Silberschatz, Galvin and Gagne ©2009 Produttore e cinsumatore Produttore inserisci: indice della successiva posizione libera nel buffer while (true) { /* produce un elemento in appena_Prodotto */ while (contatore == DIM_BUFFER) ; /* non fa niente */ buffer[inserisci] = appena_Prodotto; inserisci = (inserisci + 1) % DIM_BUFFER; contatore++; } Consumatore preleva : indice della prima posizione piena nel buffer while (true) { while (contatore == 0) ; /* non fa niente */ da_Consumare = buffer[preleva]; preleva = (preleva - 1) % DIM_BUFFER; contatore--; } Operating System Concepts – 8th Edition 6.6 Silberschatz, Galvin and Gagne ©2009 Inconsistenza dei dati - 1 La variabile contatore è usata in modo concorrente dal produttore e dal consumatore e quindi il suo valore potrebbe essere inconsistente ad un certo punto Se le istruzioni contatore++ e contatore– sono tipicamente implementate in linguaggio macchina nel seguente modo registro1 := contatore registro1 := registro1 + 1 contatore : = registro1 L’esecuzione concorrente di queste istruzioni può portare alla seguente sequenza di istruzioni interleaved: T0: T1: T2: T3: T4: T5: registro2 := contatore registro2 := registro2 - 1 contatore : = registro2 produttore esegue produttore esegue consumatore esegue consumatore esegue produttore esegue consumatore esegue registro1 registro1 registro2 registro2 contatore contatore = = = = = = contatore registro1 + 1 contatore register2 – 1 registro1 registro2 {registro1 = 5} {registro1 = 6} {registro2 = 5} {registro2 = 4} {contatore = 6} {contatore = 4} … Che portano ad avere contatore pari a 4 (per il consumatore) e 6 (per il produttore)! Operating System Concepts – 8th Edition 6.7 Silberschatz, Galvin and Gagne ©2009 Il problema della sezione critica Supponiamo di avere n processi {P0, P1,…,Pn} ognuno con una porzione di codice, definita sezione critica (o regione critica), in cui può modificare dati condivisi L’esecuzione della sezione critica da parte dei processi deve essere mutuamente esclusiva nel tempo Ad esempio una variabile, un file, etc. Un solo processo alla volta può trovarsi nella propria sezione critica Processi devono quindi cooperare: Ogni processo deve chiedere il permesso di accesso alla sezione critica, tramite una sezione d’ingresso (entry section) La sezione critica è seguita da una sezione d’uscita (exit section) Il rimanente codice è non critico Un processo avrà la seguente struttura while (true) { sezione di ingresso sezione critica sezione di uscita sezione non critica } Operating System Concepts – 8th Edition 6.8 Silberschatz, Galvin and Gagne ©2009 Soluzione al problema della sezione critica Il problema della sezione critica si affronta progettando un protocollo che i processi possono usare per cooperare e che deve deve soddisfare i 3 requisiti: Mutua esclusione Se il processo Pi è in esecuzione nella sua sezione critica nessun altro processo può trovarsi nella propria sezione critica Progresso Se nessun processo è in esecuzione nella propria sezione critica ed esiste qualche processo che desidera accedervi, allora la selezione del processo che entrerà prossimamente nella propria sezione critica non può essere rimandata indefinitamente Ad esempio nessun processo può impossessarsi della stampante se è già utilizzata da un processo In altre parole, si deve permettere l’accesso Attesa limitata Deve esistere un limite al numero di volte che si consente ai processi di entrare nella propria sezione critica dal momento in cui un processo precedentemente ha richiesto di farlo In altre parole, un processo entrerà prima o poi in tempo finito nella propria sezione critica (politica fair per evitare la starvation) Operating System Concepts – 8th Edition 6.9 Silberschatz, Galvin and Gagne ©2009 Uso del lock Per una corretta gestione della sezione critica bisogna garantire mutua esclusione L’accesso alla sezione critica può essere risolto utilizzando uno strumento detto lock (lucchetto) progresso attesa illimitata Tutte le strutture dati condivise sono protette da uno o più lock Per accedere alle strutture dati è necessario acquisire il possesso del lock che verrà restituito all’uscita della sezione critica while (true) { acquisisce il lock sezione critica restituisce il lock sezione non critica } Operating System Concepts – 8th Edition 6.10 Silberschatz, Galvin and Gagne ©2009 Outline Il problema della sincronizzazione Sincronizzazione hardware Semafori Monitor Problemi tipici di sincronizzazione Produttori/Consumatori Lettori/Scrittori 5 filosofi Stallo Operating System Concepts – 8th Edition 6.11 Silberschatz, Galvin and Gagne ©2009 Sincronizzazione hardware Per poter implementare il concetto della lock esistono istruzioni implementate in hardware nelle moderne CPU, ad esempio: testAndSet(var) - testa e modifica il valore di una cella di memoria swap(var1, var2) - scambia il valore di due celle di memoria L’aspetto fondamentale di queste istruzioni macchina è che sono atomiche ovvero non possono essere interrotte da un cambio di contesto Due istruzione atomiche eseguite contemporaneamente saranno sempre eseguite completamente in modo sequenziale in un ordine arbitrario Operating System Concepts – 8th Edition 6.12 Silberschatz, Galvin and Gagne ©2009 TestAndSet Avendo definito la variabile globale che mantiene lo stato del lock come segue: boolean lock = false; L’istruzione testAndSet può essere definita nel seguente modo: boolean testAndSet(boolean *lockVar) { boolean valorePrecedente = *lockVar; *lockVar = true; return valorePrecedente; } Il significato è quello di impostare la variabile lock a true e restituire il suo precedente valore contenuto in valorePrecedente Operating System Concepts – 8th Edition 6.13 Silberschatz, Galvin and Gagne ©2009 Mutua esclusione con testAndSet La mutua esclusione mediate testAndSet può essere realizzata attraverso una variabile booleana globale lock inizializzata a false nel seguente modo while (true) { while(testAndLock(&lock)) ; sezione critica lock = false; sezione non critica } La testAndSet per poter risolvere il problema della sezione critica deve poter soddisfare i requisiti di: Mutua esclusione Progresso Attesa limitata Sono soddisfatti tutti e tre i requisiti? Operating System Concepts – 8th Edition 6.14 Silberschatz, Galvin and Gagne ©2009 TestAndSet – Mutua Esclusione while (true) { while(testAndLock(&lock)) ; sezione critica /*lock = true*/ lock = false; sezione non critica } Dati due processi P1 e P2 il primo dei due che esegue la testAndSet imposta lock a true ed entra nella sezione critica L’altro processo troverà lock a true e si metterà in attesa nel ciclo while Operating System Concepts – 8th Edition 6.15 Silberschatz, Galvin and Gagne ©2009 TestAndSet – Progresso while (true) { while(testAndLock(&lock)) ; sezione critica /*lock = true*/ lock = false; sezione non critica } Un processo P dopo aver lasciato la sezione critica imposta lock a false permettendo ad un altro processo di entrare nella sezione critica Operating System Concepts – 8th Edition 6.16 Silberschatz, Galvin and Gagne ©2009 TestAndSet con attesa limitata while (true) { attesa[i] = true; chiave = true; Strutture dati condivise: lock e attesa[n] while (attesa[i] && chiave) chiave = testAndSet(&lock); attesa[i] = false; Mutua esclusione: Entra nella sezione critica quando chiave è false o attesa[i] è false sezione critica j = (i + 1) % n; while ((j != i) && !attesa[i]) j = (j + 1) % n; Progresso: In uscita imposta lock=false a if (j==i) lock = false; else attesa[j] = false; Attesa limitata: Scorre la lista e trova il primo interessato ad entrare sezione non critica } Il processo che esce dalla propria sezione critica designa attraverso una coda circolare il prossimo processo che può entrare Qualsiasi processo che intende entrare nella sezione critica attenderà al più n-1 turni Operating System Concepts – 8th Edition 6.17 Silberschatz, Galvin and Gagne ©2009 Outline Il problema della sincronizzazione Sincronizzazione hardware Semafori Monitor Problemi tipici di sincronizzazione Produttori/Consumatori Lettori/Scrittori 5 filosofi Stallo Operating System Concepts – 8th Edition 6.18 Silberschatz, Galvin and Gagne ©2009 Semafori Un semaforo S è una variabile intera utilizzata come strumento di sincronizzazione Le due operazioni atomiche possibili su S sono: wait(S) signal(S) wait(S) { while(S <= 0) ; //no-op S--; } Operating System Concepts – 8th Edition signal(S) { S++; } 6.19 Silberschatz, Galvin and Gagne ©2009 Esempi di uso del semaforo Accesso a sezioni critiche Un semaforo può essere utilizzato per risolvere il problema dell’accesso alla sezione critica tra n processi mediante un semaforo comune mutex (mutual exclusion) inizializzato ad 1 while (true) { wait(mutex); sezione critica signal(mutex); sezione non critica } Sincronizzazione di operazioni Supponiamo che il processo P1 debba compiere una operazione op1 prima dell’operazione op2 del processo P2. Quindi op2 sarà eseguita solo dopo che op1 termina Utilizziamo un semaforo mutex inizializzato a 0 op1; signal(mutex); Operating System Concepts – 8th Edition wait(mutex); op2; 6.20 Silberschatz, Galvin and Gagne ©2009 Evitare il busy waiting dei semafori - 1 I processi che girano inutilmente mentre attendono un semaforo per il rilascio di una risorsa sono chiamati spin lock (girano sul lucchetto) Il busy waiting o attesa attiva costituisce un problema per i sistemi multiprogrammati, perché la condizione di attesa spreca cicli di CPU che altri processi potrebbero sfruttare produttivamente L’attesa attiva è vantaggiosa solo quando è molto breve perché, in questo caso, può evitare un context switch Per evitare il busy waiting possiamo modificare la definizione di wait in modo che: Il processo invoca una wait per ottenere una risorsa Se la risorsa è in uso, blocca se stesso inserendosi in una coda di attesa del semaforo e passando nello stato di attesa Lo scheduler della CPU può quindi selezionare un altro processo pronto per l’esecuzione Il processo sarà sbloccato da una signal da parte di qualche altro processo Operating System Concepts – 8th Edition 6.21 Silberschatz, Galvin and Gagne ©2009 Evitare il busy waiting dei semafori - 2 Per realizzare l’operazione di bloccaggio abbiamo bisogno di una struttura dati semaforo implementata nel seguente modo typedef struct { int valore; struct Processo *lista; } semaforo; Il sistema operativo deve inoltre fornire due operazioni: block() – sospende il processo che la invoca wakeup(P) – pone in stato di pronto il processo P bloccato Le operazioni wait() e signal() saranno realizzate nel seguente modo: wait(semaforo *S) { S->valore--; if(S->valore < 0) { aggiungi questo processo a S->lista block(); } } Operating System Concepts – 8th Edition signal(semaforo *S) { S->valore++; if(S->valore <= 0) { togli un processo P da S->lista wakeup(P); } } 6.22 Silberschatz, Galvin and Gagne ©2009 Outline Il problema della sincronizzazione Sincronizzazione hardware Semafori Monitor Problemi tipici di sincronizzazione Produttori/Consumatori Lettori/Scrittori 5 filosofi Stallo Operating System Concepts – 8th Edition 6.23 Silberschatz, Galvin and Gagne ©2009 Monitors Incapsula dati osservabili e modificabili solamente dall’ “interno” del monitor Costrutto linguistico Realizza l’accesso in mutua esclusione ai dati che incapsula una sola procedura d’accesso alla volta può essere attiva (1 processo alla volta) Operating System Concepts – 8th Edition 6.24 Silberschatz, Galvin and Gagne ©2009 Monitor Il monitor è un costrutto di sincronizzazione di alto livello che permette la condivisione sicura di un tipo astratto di dati fra processi concorrenti Incapsula i dati privati mettendo a disposizione metodi pubblici per operare su tali dati La rappresentazione di un tipo monitor è formata da: dichiarazioni di variabili i cui valori definiscono lo stato di un’istanza del tipo procedure o funzioni che realizzano le operazioni sul tipo stesso Supportati da Concurrent Pascal, C#, Java Operating System Concepts – 8th Edition 6.25 Silberschatz, Galvin and Gagne ©2009 Esempio di monitor in Java? Variabili condivise il cui accesso deve avvenire in mutua esclusione class MyMonitor { private int dato1; private Vector dato 2; public void cambiaDato2() { synchronized(this) { … } } public int getDato1() { synchronized(this) { … } } } Operating System Concepts – 8th Edition 6.26 Silberschatz, Galvin and Gagne ©2009 Outline Il problema della sincronizzazione Sincronizzazione hardware Semafori Monitor Problemi tipici di sincronizzazione Produttori/Consumatori Lettori/Scrittori 5 filosofi Stallo Operating System Concepts – 8th Edition 6.27 Silberschatz, Galvin and Gagne ©2009 Problemi tipici di sincronizzazione Alcuni problemi tipici di sincronizzazione dove poter verificare schemi di sincronizzazione sono: Problema dei produttori e consumatori Problema dei lettori e degli scrittori Problema dei cinque filosofi Operating System Concepts – 8th Edition 6.28 Silberschatz, Galvin and Gagne ©2009 Problema dei produttori e consumatori Il problema del produttore e del consumatore con memoria limitata può essere risolto utilizzando i semafori e le seguenti strutture dati buffer[DIM_BUFFER] buffer circolare di dimensione limitata Semafori piene, vuote, mutex piene inizializzato a 0, mantiene il numero degli elementi inseriti vuote inizializzato a n, mantiene il numero delle posizioni libere mutex inizializzato ad 1, sincronizza gli accessi al buffer Va in attesa se buffer è utilizzato (mutex = 0) Va in attesa se piene è <= 0 Va in attesa se buffer è utilizzato (mutex = 0) Va in attesa se vuote è <= 0 while(true) { produce un elemento in prod wait(vuote); wait(mutex); … inserisce in buffer l’elemento prod … signal(mutex); signal(piene); } while(true) { wait(piene); wait(mutex); … rimuove un elemento da buffer e lo mette in prod … signal(mutex); signal(piene); … consuma l’elemento in prod } Consumatore Produttore Operating System Concepts – 8th Edition 6.29 Silberschatz, Galvin and Gagne ©2009 Problema dei lettori e degli scrittori Un insieme di dati (ad es., un file) deve essere condiviso da più processi concorrenti che possono: Lettori: richiedere la sola lettura del contenuto… Scrittori: richiedere l’accesso ai dati sia in lettura che in scrittura I processi lettori possono accedere contemporaneamente al file Un processo scrittore deve accedere in mutua esclusione con tutti gli altri processi (sia lettori che scrittori) Strutture dati condivise: numLettori: Inizializzato a 0, mantiene il numero di processi che leggono i dati while(true) { wait(mutex); numLettori++; if(numLettori == 1) wait(scrittura); signal(mutex); … esegue l’operazione di lettura … wait(mutex); numLettori--; if(numLettori == 0) signal(scrittura); signal(mutex); } Lettore Semafori mutex ,scrittura mutex inizializzato a 1, gestisce l’accesso a numLettori scrittura inizializzato a 1, gestisce la mutua esclusione nella scrittura while(true) { wait(scrittura); … esegue l’operazione di scrittura … signal(scrittura); } Scrittore Operating System Concepts – 8th Edition 6.30 Silberschatz, Galvin and Gagne ©2009 Problema dei cinque filosofi Il problema dei 5 filosofi è un classico problema di sincronizzazione sviluppato da Dijkstra Cinque filosofi passano la loro vita pensando e mangiando I filosofi siedono attorno ad un tavolo rotondo con 5 posti Un filosofo può essere nei seguenti stati: Pensa: non interagisce con niente e nessuno Mangia: tenta di prendere le bacchette alla sua destra ed alla sua sinistra Il filosofo può appropriarsi di una sola bacchetta alla volta Quando un filosofo affamato possiede due bacchette contemporaneamente, mangia; terminato il pasto, appoggia le bacchette e ricomincia a pensare Variabili condivise: La zuppiera di riso (l’insieme dei dati) Cinque semafori, bacchetta[5], inizializzati ad 1 La soluzione con i semafori non esclude la possibilità di deadlock I filosofi hanno fame contemporaneamente ed ognuno si impossessa della bacchetta alla propria sinistra Operating System Concepts – 8th Edition 6.31 while(true) { wait(bacchetta[i]); wait(bacchetta[(i+1) % 5]); … mangia … signal(bacchetta[i]); signal(bacchetta[(i+1) % 5]); … pensa … } Silberschatz, Galvin and Gagne ©2009 Outline Il problema della sincronizzazione Sincronizzazione hardware Semafori Monitor Problemi tipici di sincronizzazione Produttori/Consumatori Lettori/Scrittori 5 filosofi Stallo Operating System Concepts – 8th Edition 6.33 Silberschatz, Galvin and Gagne ©2009 Come risolvere il deadlock? Operating System Concepts – 8th Edition 6.34 Silberschatz, Galvin and Gagne ©2009 Condizioni Necessarie e Sufficienti per Generare uno Stato di Deadlock divieto di rapina (no preemption) accesso in mutua esclusione alle risorse acquisizione incrementale delle risorse attese circolari Operating System Concepts – 8th Edition 6.35 Silberschatz, Galvin and Gagne ©2009 Accesso in mutua esclusione Alcune risorse sono per natura non condivisibili quindi è difficile prevenire lo stallo negando la condizione di mutua esclusione … Operating System Concepts – 8th Edition 6.36 Silberschatz, Galvin and Gagne ©2009 Acquisizione incrementale Acquisire tutte le risorse atomicamente acquisire le 2 forchette con una unica azione Rilascio risorse con timeout rilasciare una forchetta acquisita se trascorso un certo tempo non si riesce a progredire (starvation, livelock) Operating System Concepts – 8th Edition 6.37 Silberschatz, Galvin and Gagne ©2009 No Preemption È possibile “rubare” le risorse a processi che le hanno già acquisite prendere una forchetta già acquisita da un filosofo Rollback rilasciare tutte le forchette e ricominciare Operating System Concepts – 8th Edition 6.38 Silberschatz, Galvin and Gagne ©2009 Attese circolari Protocolli ad-hoc Introdurre un ordine specifico di acquisizione delle risorse alcuni filosofi acquisiscono le forchette in ordine inverso Escludere alcuni processi dall’attività solamente 4 dei 5 filosofi possono sedersi al tavolo Operating System Concepts – 8th Edition 6.39 Silberschatz, Galvin and Gagne ©2009 Alcune soluzioni al problema dei filosofi Se dopo un certo perido di tempo la bacchetta mancante non si libera, si rilascia qualla acquisita Un filosofo può prendere le bacchette solo se sono entrambe disponibili Viola acquisizione incrementale Alcuni filosofi prendono le bacchette con ordine inverso Viola acquisizione incrementale Viola attese circolari Solo quattro filosofi possono stare a tavola contemporaneamente Viola attese circolari Operating System Concepts – 8th Edition 6.40 Silberschatz, Galvin and Gagne ©2009