Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Marco Lapegna » 9.La sincronizzazione dei processi


Sistemi operativi

La sincronizzazione dei processi

Problema

2 processi che comunicano attraverso una area di memoria condivisa:

  • Counter è una variabile condivisa
  • P1 incrementa counter, P2 decrementa counter
  • Se, ad esempio counter = 5, l’esecuzione di P1 e P2 dovrebbe riportare il valore di counter = 5
Schema del problema

Schema del problema


Problema

L’ istruzione di aggiornamento counter++ viene realizzata in linguaggio macchina come da immagine.

Se entrambi tentano di accedere a counter contemporaneamente, le istruzioni in linguaggio macchina possono risultare interfogliate e il risultato dipende da come i processi accedono alla cpu.

Schema del problema

Schema del problema


Problema con la memoria condivisa

Esempio: se counter inizialmente vale 5

Il risultato sarà 4 o 6 a secondo di chi accede per ultimo alla memoria condivisa (mentre il risultato corretto è 5)

Schema del problema

Schema del problema


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

Struttura generale di una sezione critica

L’implementazione delle funzioni che regolano l’accesso alla sezione critica può avvenire:

  • Attraverso strumenti software
  • Attraverso strumenti hardware
Codice (sezione critica)

Codice (sezione critica)


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

Processo P0 (analogamente per P1 ): in figura il codice relativo al processo.

Codice (algoritmo 1)

Codice (algoritmo 1)


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

Processo P0: in figura il codice relativo al processo.

Codice (algoritmo 2)

Codice (algoritmo 2)


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 3 (di Peterson)

Processo P0 ( analogamente per P1 ): in figura il codice relativo al processo.

Codice (algoritmo 3)

Codice (algoritmo 3)


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)

Algoritmo del fornaio (proc Pi)

Variabili condivise:

  • boolean scelta[n] = false;
  • int number[n] = 0;
Codice (algoritmo del fornaio)

Codice (algoritmo del fornaio)


Algoritmo del fornaio (proc Pi)

number [ i ] = 0 indica che Pi è uscito dalla sezione critica.

Codice (algoritmo del fornaio)

Codice (algoritmo del fornaio)


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.

Mutua esclusione con TestAndSet

Dati condivisi:

boolean lock = false;

Codice (testandset)

Codice (testandset)


Istruzione Swap

Istruzione Swap:

void Swap(boolean &a, boolean &b)

Definizione:

  • Scambia il contenuto di a e b

L’istruzione e’ eseguita atomicamente.

Mutua esclusione con Swap

Dati condivisi:

boolean lock = false;

Soluzione per n processi:

Processo Pi

Codice (swap)

Codice (swap)


Prossima lezione

I semafori

  • Definizione
  • Implementazione
  • Esempi di uso
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion