Sincronizzazione nei sistemi operativi: processi concorrenti

Sincronizzazione

Sistemi Operativi e Laboratorio A. Formisano Dipartimento di Scienze Matematiche, Informatiche e Fisiche Anno Accademico 2024-25 Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Contenuti

1. Il Problema della Sezione Critica
2. Semafori
3. Tipici Problemi di Sincronizzazione
4. Monitor
5. IPC in UNIX/Linux

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Il Problema della Sezione Critica

Processi Concorrenti

In condizioni normali, un moderno sistema operativo deve gestire più processi contemporaneamente in esecuzione

• tali processi possono eseguire indipendentemente (dal punto di vista logico) o essere cooperanti
• nella situazione generale avremo processi che compiono le loro azioni inframezzandole e interessando risorse condivise (interleaving e overlapping)
• tali processi necessitano di
  • sincronizzazione
  • comunicazione
  • accesso a dati e informazioni condivise

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Esecuzione Concorrente

L'accesso contemporaneo da parte di due processi a dati condivisi può essere problematico:

• i dati possono essere modificati in modo incoerente/inconsistente dato che lo switch di contesto può avvenire prima che il processo abbia completato tutte le modifiche
• il S.O. deve mettere a disposizione degli strumenti per mantenere la consistenza dei dati
• si deve concedere solo ad un processo alla volta di accedere a dati condivisi: accesso in mutua esclusione; gli altri processi devono attendere: problema di serializzazione degli accessi
• si deve garantire che il tempo di attesa sia "ragionevole" e adottare una politica che non penalizzi parte dei processi (fairness)
• non si devono verificare attese infinite (es. processi che si aspettano vicendevolmente)

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Il Problema della Sezione Critica

Concetti Essenziali (1)

In questa breve descrizione abbiamo introdotto le nozioni fondamentali che studieremo nelle prossime lezioni: Sezione Critica (SC) Una sezione di codice che legge/scrive dati condivisi Race Condition Una situazione in cui l'esecuzione concorrente di una sezione critica, da parte di più processi, porta a risultati dipendenti dall'ordine in cui i processi alternano l'esecuzione delle loro istruzioni (Ciò è potenziale fonte di inconsistenze dei dati)

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Concetti Essenziali (2)

Mutua Esclusione Meccanismo con cui si evitano le race condition assicurando l'accesso esclusivo ai dati. (Un processo deve essere "autorizzato" ad entrare in una sezione critica) Deadlock (o blocco critico) Situazione in cui dei processi sono permanentemente bloccati perchè in attesa vicendevole del rilascio di risorse Starvation Situazione in cui ad un processo che ha richiesto l'accesso ad una sezione critica non viene mai permesso di evolvere perchè vengono sempre servite le richieste di altri processi

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Il Problema della Sezione Critica

Un Esempio di Programmazione Concorrente

Due processi collaborano nello svolgere un semplice compito: un processo produttore produce dei dati che vengono utilizzati da un processo consumatore. Lo scambio dei dati avviene tramite un buffer condiviso. Ecco le definizioni:

#define BUFFER_SIZE 10 / / dimensione del buffer typedef struct { . . . } item; item buffer [BUFFER_SIZE] ; / / array circolare int in = 0; / / posizione in cui scrivere int out = 0; / / posizione da cui leggere int counter = 0; / / num. di record memorizzati

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Un Produttore e un Consumatore che ...

item nextProduced; while (1) { / / loop forever while (counter == BUFFER_SIZE) ; /* non fa niente (busy waiting! !! ) */ buffer [in] = nextProduced; in = (in+1) % BUFFER_SIZE; counter++; } item nextConsumed; while (1) { / / loop forever while (counter == 0) ; /* non fa niente (busy waiting! !! ) */ nextConsumed = buffer [out] ; out = (out+1) % BUFFER_SIZE; counter --; }

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Il Problema della Sezione Critica

Non Funzionano !!!

• Presi singolarmente i codici di produttore e del consumatore sono corretti, tuttavia in esecuzione concorrente possono generare inconsistenze nei dati
• la gestione della variabile condivisa counter non è adeguata: cosa accade se le due istruzioni counter++ e counter -- sono eseguite contemporaneamente?
• dipende da come sono compilate e eseguite dal/i processore/i: regA := counter regA := regA + 1 regB := regB - 1 counter := regA counter := regB regB := counter
• errori di questo tipo sono difficili da scoprire: non sono riproducibili perchè dipendono dalla velocità relativa dei due processi
• le due istruzioni sono sezioni critiche
• siamo in presenza di una race condition

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Soluzione del Problema della Sezione Critica

Consideriamo una specifica risorsa condivisa e le sezioni critiche ad essa relative presenti nei codici eseguiti da diversi processi. Una soluzione al problema della sezione critica deve garantire:

• Mutua esclusione: ci può essere al più un solo processo che esegue la SC
• Progresso: se nessun processo è nella sua SC e dei processi richiedono di entrare in SC, la decisione su quale richiesta esaudire deve avvenire entro un intervallo di tempo finito. Inoltre, i processi che stanno eseguendo la propria sezione non critica non possono influenzare tale decisione.
• Attesa limitata: se un processo P1 ha richiesto di accedere alla sua SC, allora può esserci solo un numero finito di processi che entrano nella SC prima che a P1 sia concesso di entrare. (Ciò significa che non si ammette starvation)

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Soluzione del Problema della Sezione Critica

Si ha quindi che:

• nessun processo P1 fuori dalla sua SC può impedire ad un altro processo P2 di entrare nella propria SC: P1 ha questo privilegio solo se è nella sua SC.
• se un processo si blocca in una sezione non critica, ciò non può interferire con l'esecuzione degli altri processi
• ogni processo resta nella SC solo per un tempo finito
• quando nessun processo è in SC e un processo richiede di entrare, il permesso deve essere concesso senza attese
• tutti i processi evolvono con velocità non nulla, ma NON si fa alcuna assunzione su quale sia né la velocita assoluta di un processo né quella relativa agli altri processi
• NESSUNA assunzione sul numero dei processori

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Verso una Soluzione del Problema della SC

La soluzione del problema consiste nel progettare un protocollo che se adottato dai processi garantisca che l'effetto globale delle loro azioni non dipenda dal modo in cui le queste si inframezzano. Uno schema generale per una soluzione prevede che:

• la sezione critica sia racchiusa tra due porzioni di codice dette sezione d'ingresso e sezione d'uscita, quindi
• la richiesta di accesso alla sezione critica corrisponde alla esecuzione del codice della sezione d'ingresso
• con l'esecuzione del codice della sezione d'uscita il processo abbandona la sezione critica (che portà eventualmente essere concessa ad un altro processo)

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Verso una Soluzione del Problema della SC

Consideriamo due processi P0 e P1 con questa semplice struttura: ... sezione non critica sezione d'ingresso sezione critica sezione d'uscita sezione non critica P0 e P1 condivideranno delle variabili al fine di sincronizzarsi. Cerchiamo la soluzione:

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Primo Tentativo di Soluzione

Usiamo una variabile turno per indicare chi ha il diritto di ingresso. Ecco il codice del processo Pi (l'altro è Pj): int turno = 0; /* turno=i indica ok per Pi */ do { . sezione non critica ... while (turno != i) ; / / attesa del proprio turno . sezione critica ... turno = j; / / permetto all'altro di entrare . . sezione non critica ... } while (1) ;

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Primo Tentativo di Soluzione

Per verificare se è una soluzione corretta dobbiamo assicurarci che garantisca le tre proprietà: mutua esclusione: OK progresso e attesa limitata NO !!! infatti:

• la autorizzazione per un processo viene conferita dall'altro processo quando esce dalla sua SC
• se quest'ultimo si blocca o termina prima di eseguire turno = j; l'altro processo resta bloccato.
• se un processo non necessita di entrare nella sua SC e non lo fa, allora l'altro non può entrarvi più volte consecutive

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Secondo Tentativo di Soluzione

Usiamo due flag booleani per indicare l'interesse di un processo a entrare nella SC. Ecco il codice del processo Pi (l'altro è Pj): boolean flag [2] ; / * flag [i]=true indica che Pi vuole entrare inizialmente flag[0]=flag[1]=false * / do { . sezione non critica ... flag [i] = true; / / dichiara il suo interesse while (flag[j] ) ; / / attesa del proprio turno ... sezione critica ... flag[i] = false; £ / / dichiara la fine dell'interesse . . sezione non critica ... while (1) ; }

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Secondo Tentativo di Soluzione

In questo caso un processo può entrare in SC più volte consecutive. Ma le tre proprietà NON sono tutte garantite: mutua esclusione: OK progresso e attesa limitata NO !!! infatti:

• il funzionamento dipende dalla velocità reciproca dei processi . si ha deadlock se accade che flag[0]=flag [1]=true

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF

Soluzione di Peterson

Usiamo sia la variabile turno che i due flag per dichiarare l'interesse a entrare nella SC. Ecco il codice del processo Pi (l'altro è Pi): boolean flag [2] ; int turno; do { . sezione non critica ... flag[i] = true; // dichiara il suo interesse turno = j; / / assume che sia il turno dell'altro / / e gli offre l'occasione di entrare while (flag[j] and turno == j) ; / / attesa del proprio turno . sezione critica ... flag [i] = false; // fine dell'interesse .... sezione non critica ... } while (1) ; Vi convince? Perchè?

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF