PROGRAMMAZIONE CONCORRENTE

Testi:

Tanenbaum, I moderni sistemi operativi, cap.2
Ben-Ari, cap.2
Deitel, cap.4-5
Peterson e Silbershatz, cap.9-10

In questa parte di programma esamineremo vari modi per realizzare:

·        la comunicazione tra processi (IPC, inter process communication)

·        la cooperazione tra processi, che si realizza correttamente solo se  si rispetta la mutua esclusione

·        la sincronizzazione tra processi

CONCETTI DI BASE

PROGRAMMA SEQUENZIALE: specifica l'esecuzione sequenziale di una lista di istruzioni. La sua esecuzione e' un PROCESSO.

PROGRAMMA CONCORRENTE: specifica due o più programmi sequenziali che possono essere eseguiti concorrentemente come processi paralleli.

AMBIENTI DI ESECUZIONE

MULTIPROGRAMMAZIONE

Un solo processore, più processi

MULTIPROCESSING

Più processori su una memoria condivisa (shared memory)

Sia m numero dei processori, n numero dei processi, allora parliamo di:

• m>=n multiprocessing puro;
• m<n multiprocessing con multiprogrammazione

DISTRIBUTED PROCESSING

Più processori collegati da una rete di interconnessione (in generale privi di memoria condivisa). Su ogni processore è possibile avere la multiprogrammazione

Interazione tra processi

Per poter cooperare, i processi concorrenti devono

• comunicare
• sincronizzarsi

Comunicazione: il modo attraverso il quale un processo influenza l'esecuzione di un altro processo. E' possibile comunicare attraverso:

• variabili condivise (shared variables)
• trasmissione di messaggi (message passing)

Le variabili condivise costituiscono un ambiente globale di elaborazione, che si realizza su una architettura a memoria comune.

Lo scambio di messaggi consente l'elaborazione in ambiente locale; può essere realizzato con o senza una memoria comune.

Sincronizzazione: è necessaria per una comunicazione corretta.

Vi sono diversi fattori, tra cui l'ambiente di esecuzione mono- o multi-processore, che influenzano la velocità con cui è eseguito un processo, e la sua velocità relativa rispetto ai processi con cui coopera.

E' quindi in generale molto difficile formulare ipotesi su tale velocità.

E' comunque possibile e necessario formulare la seguente ipotesi:

FINITE PROGRESS ASSUMPTION: a tutti i processi di un programma concorrente è garantito di poter progredire in un tempo finito, se almeno uno di essi è pronto per l'esecuzione.

PROGREDIRE va inteso

• in senso globale: completare la propria esecuzione
• in senso locale: terminare una sezione critica

Quando l'ipotesi di finite progress assumption viene violata, si verifica una situazione "patologica" di errore come ad es. deadlock, livelock, starvation.

NONDETERMINISMO

Supponiamo di avere un programma concorrente composto da n>2 processi.

Un processo raggiunge uno stato in cui è disponibile per comunicare con m altri processi, m>1.

Tra gli m processi, potrebbe essercene più di uno contemporaneamente disponibile a tale comunicazione; ma in ogni istante non può avvenire più di una comunicazione per volta.

In generale non ci sono motivi per privilegiare una tra le m comunicazioni possibili; anzi, spesso imporre un ordine prestabilito a tali comunicazioni potrebbe causare ritardi (un processo è pronto a comunicare ma quello che lo precede non ancora) e addirittura errori (deadlock o lockout).

E' utile poter esprimere la disponibilità ad una scelta "nondeterministica".

PROPRIETA' DI UN PROGRAMMA CONCORRENTE

Safety: SE il programma termina, allora il suo risultato è corretto. (N. B. il programma potrebbe non terminare e non dare nessun risultato)

Liveness: il programma termina e il suo risultato è corretto. In altri termini: la proprietà di liveness esprime il fatto che se qualcosa deve accadere, allora effettivamente accadrà (eventually, prima o poi).

Minacce:

• Deadlock (risorse, comunicazioni)
• Starvation e lockout

Aiuti:

• Meccanismi di fairness

Una notazione per la programmazione concorrente

• Come indicare l’esecuzione concorrente
• Quale modo di comunicazione tra processi utilizzare
• Quale meccanismo di sincronizzazione tra processi utilizzare
• Come esprimere e controllare il nondeterminismo
• Come poter verificare le proprietà di un programma concorrente
• Come garantire l’efficienza del programma evitando attese infruttuose (busy waiting) o eccessivo overhead.

Evoluzione delle notazioni per la programmazione concorrente

RACE CONDITION E MUTUA ESCLUSIONE

Partiremo da alcuni esempi

Esempio 1: copia di file parallelizzando le operazioni di I/O

Scriviamo un programma che copia da un file sequenziale f ad un file sequenziale g. Sappiamo che le operazioni di accesso ai dischi (input/output) sono molto lente, e cerchiamo di fare in modo che possano avvenire “contemporaneamente”. Per fare questo, occorre utilizzare due buffer, r e s: dopo aver letto il primo blocco in r, lo si ricopia in s e si può leggere in r il secondo blocco contemporaneamente alla scrittura del primo blocco.

Schematizziamo la situazione delle prime due letture:

Possiamo pensare a un ciclo while dentro al quale vengono eseguite le due operazioni concorrenti, mentre occorre una sincronizzazione prima di eseguire la copia.

Il ciclo termina quando la lettura da f incontra la fine del file.

Esempio 2: variabili condivise

Consideriamo due processi P1 e P2 eseguiti su un sistema multiprogrammato (quindi in interleaving). I due processi condividono una risorsa, o una variabile (nell'esempio è A).

• non tutti i possibili interleaving sono leciti (race condition, in italiano "corsa critica");
• l'accesso alla variabile o risorsa deve avvenire in modo mutuamente esclusivo.

Sappiamo che il valore iniziale di A è 0. Ci aspettiamo che al termine dell'esecuzione di P1 e P2 il valore di A sia 3.

In realtà una assegnazione a variabile viene eseguita dalla macchina con una sequenza di istruzioni macchina elementari, ad esempio potrebbe essere la seguente:

--carico il valore di A in un registro;
--sommo una costante (1 oppure 2) al registro;
--trasferisco il valore del registro all'indirizzo di memoria di A.

L'interleaving si verifica a livello di istruzioni macchina, quindi è possibile che al termine di una esecuzione "arbitraria" delle due assegnazioni il valore di A sia 1 oppure 2, invece del valore desiderato 3!

Diremo quindi che

• P1 e P2 sono due processi concorrenti,
• le istruzioni A1 e A2 devono essere eseguite in mutua esclusione;
• le istruzioni A1 e A2 rappresentano due sezioni critiche.

Esempio 3: spooler di stampa

La stampa è una operazione meccanica, che richiede ancora più tempo della scrittura su disco. Quindi sarebbe bene che in un sistema in multiprogrammazione, alcuni processi potessero eseguire operazioni di CPU mentre uno o più altri processi stanno eseguendo operazioni di I/O, soprattutto stampe.

Per la gestione di una sola stampante (risorsa condivisa) da parte di più processi solitamente i sistemi operativi usano un meccanismo detto spooler di stampa. Infatti, se due processi stessero scrivendo contemporaneamente, si avrebbe un interleaving delle loro uscite, cioè una uscita con righe mescolate, totalmente illeggibile; se invece obbligassimo i processi a stampare uno alla volta, potremmo obbligare ad attendere anche molto a lungo.

Quindi, i processi non stampano direttamente il file ma richiedono la stampa di un file inserendo il nome del file in una apposita tabella detta "directory di spool". Possiamo supporre che questa tabella abbia dimensione "infinita", ovvero che sia sempre possibile inserire il nome di un ulteriore file da stampare, riempiendo successivamente le posizioni di indice 0, 1, 2, ecc.

Vi è un processo detto "demone di stampa" che controlla il contenuto della directory di spool e, se c'è il nome di un file, si incarica di stamparlo e di rimuovere quindi tale nome dalla directory.

In questo modo la stampante NON viene condivisa, ma è riservata al demone di stampa. I vari processi, per poter inserire il nome dei files nella directory, devono conoscere l'indice delle posizione libera nella tabella (in), mentre il demone di stampa gestisce l'indice del file da stampare (out). Chiameremo la directory di spool slot.

Consideriamo questa situazione:

Due processi P1 e P2 vogliono entrambi stampare "contemporaneamente", con le seguenti sequenze di istruzioni:

Supponiamo allora che l'interleaving tra i due processi faccia eseguire nell'ordine le istruzioni seguenti:

prima la 1-1, poi 2-1 e 2-2, poi 1-2 e 1-3, infine 2-3.

Quali files verranno stampati?

Le race condition o corse critiche sono situazioni in cui, come negli esempi visti, vi sono più processi che condividono variabili o risorse e in cui diversi interleaving portano a risultati diversi.

Le sezioni critiche di un processo concorrente sono le istruzioni (o gruppi di istruzioni) in cui il processo accede a risorse o variabili condivise.

Per evitare le race condition occorre

• individuare le sezioni critiche di ogni processo concorrente;
• eseguire le sezioni critiche in mutua esclusione.

Più precisamente, si vuole che:

1. due o più processi concorrenti non si trovino contemporaneamente nelle rispettive sezioni critiche;
2. nessun processo fermo fuori dalla sua sezione critica impedisca ad altri processi di procedere;
3. nessun processo attenda un tempo infinito per entrare nella propria sezione critica;
4. i tre criteri precedenti siano sempre validi qualunque sia la velocita' relativa dei processi.

Vediamo un esempio di interazione corretta tra processi che si trovano entrambi contemporaneamente nella necessità di entrare nelle rispettive sezioni critiche:

La soluzione al problema delle corse critiche si ottiene facendo precedere e seguire tutte le sezioni critiche dei vari processi da opportuni <prologhi> ed <epiloghi>:

Come scrivere il <prologo> e l' <epilogo> per avere la mutua esclusione sulle sezioni critiche????

Vediamo alcune possibili soluzioni:

DISABILITARE LE INTERRUZIONI

• Quando un processo entra nella propria sezione critica, disabilita le interruzioni
• Quando esce, riabilita le interruzioni.

Problema 1:

e se il processo (utente) non riabilita più le interruzioni???

Il sistema cessa di funzionare! => Disabilitare ed abilitare le interruzioni è compito SOLO del kernel

Problema 2:

se ho una memoria condivisa tra più processori, devo disabilitare le interruzioni di TUTTI i processori (non solo di quello dove è in esecuzione il processo che entra nella sezione critica). Questo NON è facile anzi, spesso è impossibile.

VARIABILI DI LOCK

In memoria condivisa c'e' la variabile di lock L inizializzata a 0.

P1 legge L:

• Se vale 0 puo' entrare nella sezione critica, la setta a 1 ed entra.
• Se vale 1 aspetta che torni 0 e procede come sopra.

=> stesso problema che per lo spooler: un altro processo P2 potrebbe leggerla a 0 e settarla a 1 prima di P1.

Si potrebbe allora:

• leggere L
• se L=0 allora la rileggo, e
• se e' ancora L=0 la setto a 1 altrimenti attendo

=> e' ancora possibile che P2 setti L a 1 dopo la seconda lettura di 0 !!!

ALTERNANZA STRETTA

Tramite l’uso della variabile condivisa turn, due processi si alternano nell’entrare nella propria sezione critica.

shared int turn;

process P1
while (true)
{
while (turn==2);/*busy wait*/
sezione_critica_1;
turn=2;
sezione_non_critica_1;
}

process P2
while (true)
{
while (turn==1);/*busy wait*/
sezione_critica_2;
turn=1;
sezione_non_critica_2;
}

main
{
turn=1;
<facciamo partire P1 e P2 in parallelo>
}

• non da' deadlock
• garantisce in parte liveness
• non funziona se un processo termina o abortisce

ma soprattutto, viola la condizione 2 della mutua esclusione

Provate a pensare cosa succede se P1 fosse 100 volte più veloce di P2 e terminasse rapidamente la propria sezione non critica: non potrebbe rientrare nella sezione critica neppure se sapesse con certezza che l’altro processo starà ancora a lungo nella propria sezione non critica. Deve comunque aspettare che P2 entri ed esca nella propria sezione critica.

Inoltre, istruzioni come quelle commentate con /*busy wait*/ occupano la CPU senza motivo (inefficienza). In questi casi, si dice che turn è usata come spin lock.

ALGORITMO DI PETERSON (1981)

I processi hanno un numero (0 oppure 1)

Prima di entrare nella sezione critica, il processo chiama la funzione enter_region() con il proprio numero come parametro

Al termine della sezione critica, il processo chiama leave_region()

#define TRUE 1
#define FALSE 0
#define N 2 /* numero dei processi */

int turn;          /* di chi è il turno? */
int interested[N]; /* tutti inizialmente a 0 */

void enter_region (int process) /* process=0 oppure 1 */
{ int other;
other=1-process; /* l'altro processo */
interested[process]=TRUE;
turn=process;
while(turn==process && interested[other]==TRUE);/*attesa */
}

void leave_region (int process) /* process sta uscendo */
{
interested[process]=FALSE;
}

Se i due processi chiamano contemporaneamente la enter_region(), uno dei due (ad es. il numero 1) eseguirà l'assegnazione a turn dopo l'altro (cancellando lo 0): allora il processo 0 proseguirà e il processo 1 si bloccherà sul while finché lo 0 non chiamerà leave_region().

L’algoritmo di Peterson funziona per DUE processi e fornisce una soluzione esclusivamente software per il problema della mutua esclusione. In realtà, ben prima del 1981, si poteva disporre di hardware per gestire la mutua esclusione.

ISTRUZIONE TSL (test-and-set-lock)

Su molti calcolatori (in particolare sulle CPU progettate per costruire i multiprocessori) esiste una istruzione macchina detta TSL che funziona in modo atomico (cioè non interrompibile) nel modo seguente:

• l'operando (variabile in memoria) è copiato in un registro,
• un valore non-zero viene messo al posto dell'operando.

Possiamo allora riscrivere la enter_region e la leave_region in assembler:

enter_region:
tsl register,flag
cmp register,#0
jnz enter_region
ret

leave_region:
mov flag,#0
ret

N.B. Se non è presente TSL, sovente è presente un’altra istruzione macchina che consente operazioni analoghe (es. scambia un registro con una cella di memoria)