Marco Lapegna » 9.La sincronizzazione dei processi

Sistemi operativi

La sincronizzazione dei processi

Problema con la memoria condivisa

• L’istruzione di modifica di counter deve essere atomica (non deve subire interruzioni)
• Proteggere i dati nella memoria condivisa e controllare gli accessi

Race condition

• Situazione nella quale più processi accedono in concorrenza, e modificano, dati condivisi. L’esito dell’esecuzione (il valore finale dei dati condivisi) dipende dall’ordine nel quale sono avvenuti gli accessi.
• Per evitare le corse critiche occorre che processi concorrenti vengano sincronizzati.
• Ciascun processo è costituito da un segmento di codice, chiamato sezione critica, in cui accede a dati condivisi in maniera esclusiva.

Problema della sezione critica

Soluzione – progettare un protocollo di cooperazione fra processi:

• Ogni processo deve chiedere il permesso di accesso alla sezione critica, tramite una entry section
• La sezione critica è seguita da una exit section; il rimanente codice è non critico

Soluzione software al problema della s.c.

Requisiti da soddisfare:

• Mutua esclusione. Se un processo è in esecuzione nella sua sezione critica, nessun altro processo può eseguire la propria sezione critica.
• Progresso. Un processo che non è in esecuzione nella propria sezione critica non può impedire ad un altro processo di accedere alla propria sezione critica.

Soluzione software al problema della s.c.

Attesa limitata. Se un processo ha effettuato la richiesta di ingresso nella sezione critica, è necessario porre un limite al numero di volte che si consente ad altri processi di entrare nelle proprie sezioni critiche, prima che la richiesta del primo processo sia stata accordata:

• Si assume che ciascun processo sia eseguito ad una velocità diversa da zero.
• Non si fanno assunzioni sulla velocità relativa degli n processi.

Algoritmo 1

• Valido per 2 processi P0 e P1
• Variabile condivisa che determina il turno:
  • int turn; (inizialmente turn = 0)
  • turn = i => Pi può entrare nella propria sezione critica

Algoritmo 1 : caratteristiche

• Usa variabili globali per controllare quale processo può entrare nella sezione critica
• Verifica costantemente se la sezione critica è disponibile
  • (Attesa attiva)
  • Consuma cicli di cpu
• I processi eseguono la sezione critica alternandosi

Algoritmo 1 : caratteristiche

Soddisfa la mutua esclusione, ma non il progresso. Se turn=0, P1 non può entrare nella propria sezione critica, anche se P0 si trova fuori della propria sezione critica.

Algoritmo 2

Variabili condivise:

• boolean flag[2]; (inizialmente flag [0] = flag [1] = false)
• flag [ i ] = true => Pi vuole entrare nella propria sezione critica

Algoritmo 2 : caratteristiche

• Introduce un flag prima della sezione critica
• Garantisce la mutua esclusione
• Introduce la possibilità di stallo dei processi
  • Entrambi i processi possono porre flag[i] = true, (entrambi tentano di entrare) bloccandosi indefinitamente
• Garantisce il progresso

Algoritmo 3 (di Peterson)

Combina le variabili condivise degli algoritmi 1 e 2

• int turn = 0
• boolean flag[0] = flag[1] = false

Algoritmo di Peterson

Usa il concetto di “processo favorito” per determinare chi deve accedere alla sezione critica (variabile turn)

• Risolve i conflitti tra i processi

Sono soddisfatte tutte le condizioni (verificare per esercizio!):

• Mutua esclusione
• Progresso
• Attesa limitata

Risolve il problema della sezione critica per due processi.

Dimostr. mutua esclusione

Supponiamo (per assurdo) che P0 e P1 sono entrambi nella s.c.:

• flag[1]==false oppure turn==0 (in P0)
• flag[0]==false oppure turn==1 (in P1)

Ma flag[0]=flag[1]=true:

• turn=0 e turn=1

(assurdo perchè è una variabile condivisa)

Algoritmo del fornaio (Leslie Lamport)

• Soluzione del problema della sezione critica per n processi.
• Prima di entrare nella loro sezione critica, i processi ricevono un numero. Il possessore del numero più basso entra in sezione critica.
• Se i processi Pi e Pj ricevono lo stesso numero, se i < j, allora Pi viene servito per primo, altrimenti tocca a Pj.
• Notazione : (# biglietto, # processo)

Soluzioni Hardware al problema della s.c.

In un ambiente multiprogrammato per garantire la mutua esclusione basterebbe disabilitare le interruzioni, in modo che i processi non vengano interrotti mentre eseguano la sezione critica

-> Sono annullati tutti i vantaggi del time sharing

Soluzioni Hardware al problema della s.c.

• Molte architetture possiedono particolari istruzioni che sono eseguite atomicamente
• Tali istruzioni possono essere utilizzate per risolvere il problema della sezione critica in maniera facile, efficiente e sicuro

Istruzione TestAndSet

Istruzione TestAndSet:

boolean TestAndSet(boolean *target)

Definizione:

• Ritorna vero se target è vero
• Ritorna falso se target è falso
• Pone sempre target vero

L’istruzione è eseguita atomicamente.

Istruzione Swap

Istruzione Swap:

void Swap(boolean &a, boolean &b)

Definizione:

• Scambia il contenuto di a e b

L’istruzione e’ eseguita atomicamente.

Prossima lezione

I semafori

• Definizione
• Implementazione
• Esempi di uso