1.6.1

1.6: Processi Concorrenti● Programmi concorrenti

● Chiamate di sistema Unix per il controllo di processi

– Creazione, terminazione di processi

– Sincronizzazione sulla terminazione, segnalazione di eventi

– Comunicazione

– Esempi di codice

● Sincronizzazione tra processi

– Mutua esclusione

– Produttore­consumatore

● Primitive di sincronizzazione; semafori

– Implementazione

– Esempi di codice

● Stallo e blocco indefinito 

1.6.2

Programmi Concorrenti● Programmi:

– Sequenziali ­  singolo processo

– Concorrenti ­  più processi (o thread) che competono tra loro per risorse di sistema, si sincronizzano, comunicano tra loro.

● Più versatili ed efficienti● Applicazioni più complesse e sofisticate

● Requisiti: normale linguaggio sequenziale + primitive (chiamate di sistema o API) per

– creazione/terminazione processi

– sincronizzazione/comunicazione/segnalazione tra processi

1.6.3

Programmi Concorrenti

P0

(sh) 

P0

(sh) 

P1

(ls) 

P0 

P0 

P1  P2  P3  P4 

Sincronizzazione sulla terminazione

Comunicazione dati

● Esempi:

1.6.4

Chiamate di Sistema Unix● pid = fork(); creazione

– crea nuovo processo (child ­  figlio), duplicando quello originale (parent ­  padre)– ritorna

● al figlio: 0● al padre: il PID del figlio appena creato● in caso di errore, ­1 (al padre)

– il processo figlio eredita tutto l'ambiente del padre, compresi i canali aperti (tutto tranne il PID)

– il figlio si trova come se avesse eseguito tutto il programma fino al fork, come il padre; continua ad eseguire (indipendentemente)

– N.B. ­ il figlio riceve una copia dell'ambiente del padre (programma, dati etc.); non c'è condivisione di dati tra padre e figlio.

– es.:pid = fork();if(pid diverso da 0){ /* padre */

if(pid uguale a ­1) { errore(); exit(1); }...

} else {/* figlio */

...}

● Linux supporta i kernel thread con la chiamata clone(2)

1.6.5

Chiamate di Sistema Unix (Cont.)● exit(code); terminazione

– termina il processo– flush dell'I/O pending (stdout etc.), chiude tutti i file, esce– trasmette code al Kernel (codice d'uscita ­  exit code) ­  convenzione: code = 0 ⇒ 

OK ; code ≠ 0 ⇒ errore (vari codici possibili)– non ritorna mai

● pid = wait(status_address); sincronizzazione su terminazione– aspetta finchè uno dei processi figli termina (sincronizzazione)– ritorna il PID del primo figlio che ha terminato– se status_address non è nullo, ritorna anche, nell'intero puntato, lo stato d'uscita 

del figlio (exit code e altro).● execl(path, name, arg1, ...);

– sostituisce, nel processo corrente, un nuovo programma all'attuale, e lo esegue– path è il percorso del file eseguibile, name è il nome del programma, arg1 è il 

primo argomento, etc.– il processo rimane lo stesso, quindi tutto l'ambiente è inalterato– "viaggio senza ritorno": se c'è un valore di ritorno, è ­1 (impossibile eseguire il 

nuovo programma)– esistono altre varianti (tutte API che conducono a un'unica chiamata di sistema, 

execve(2) ).– N.B. ­ combinazione di fork() + execl() : due processi che eseguono due 

programmi diversi.

1.6.6

Esempio di Codice  ­  1● Combinazione tipica delle chiamate viste (pseudo­codice):

pid = fork();if(pid diverso da 0){

/* processo padre */if(pid uguale a ­1)

error_exit("cannot fork");...wait(status_address);excode = (estrai codice da status);exit(excode); /* esce col codice del figlio */

}else{

/* processo figlio *//* eventuale ridirezione dell'I/O */execl("/usr/local/bin/program", "program", "­x", "file", NULL);error_exit("cannot exec program");

}

1.6.7

Chiamate di Sistema Unix (Cont.)● kill(pid, sig); segnalazione

– invia il segnale sig al processo con PID pari a pid (segnalazione: comunicazione di evento asincrono)

– processo ricevente: stesso UID del processo mittente (salvo se mittente è root)

– segnale: provoca interrupt software nel processo ricevente

– azione di default all'interrupt:    a) exit    b) core­dump + exit [*]● SIGINT (2)   ­ intr char. da terminale● SIGQUIT (3) ­ quit char. da terminale [*]● SIGKILL (9) ­ terminazione forzata (non intercettabile)● SIGTERM (15) ­ terminazione software (default per kill(1))

– N.B. ­  la chiamata di sistema signal(sig, func) permette di predisporre un'azione specifica (la chiamata alla funzione func) al ricevimento del segnale sig.

1.6.8

Esempio di Codice  ­  2prog() {

pid = fork();

if(pid non uguale a 0) { /* processo padre */

print("PID processo figlio = ", pid);

print("attesa 10 secondi");

sleep(10);   /* attendi 10 sec. senza fare nulla */

print("terminazione del processo figlio");

kill(pid, SIGTERM); /* segnale di terminazione al processo "pid" */

exit(0);

} else { /* processo figlio */

print("processo figlio inizia");

pid = getpid();  /* ottengo il mio proprio identificativo */

loop

{

print("processo figlio", pid, "lavora");

sleep(1);

}

}

}

1.6.9

Come lavora la shell di Unixshell() {

loop {

write(1, "$ ", 2); /* prompt ­  2 caratteri allo stdout */

read(0, line, SIZE); /* leggi riga da stdin */

parse(line); /* separa i token; applica i vari operatori ($, *, ?, [ ], etc.) */

pid = fork();

if(pid non uguale a 0) {  /* processo padre: la shell originaria */

if( line  non termina con '&' ) {

wait(status_address);excode = (estrai codice d'uscita da status);/* tieni conto di  excode per istruzioni di controllo della shell: if, while, etc. */

}

} else {  /* processo figlio */

redirect(); /* applica ridirezioni di stdin, stdout etc. (operatori <, >, >> etc.) */

execl(file, program, args); /* esegui il comando nel processo figlio */

}

}

}

1.6.10

Chiamate di Sistema Unix (Cont.)● pipe(fdc); comunicazione/sincronizzazione

– è il più semplice (e più limitato) meccanismo di comunicazione dati tra processi

– stabilisce un canale di comunicazione tra processi, che può essere condiviso con i processi figli (che ereditano i canali aperti)

– il canale è unidirezionale– fdc[0] serve per leggere dal pipe, fdc[1] per scrivere– il pipe è implementato come un canale di trasmissione di tipo FIFO, di 

dimensione finita (di solito 4 Kbyte)– sincronizzazione automatica di processi scrittori e lettori, che vanno a 

dormire in caso di pipe pieno/vuoto– EOF (0 byte letti) ritornato dalla read() al lettore se il pipe è chiuso in scrittura– N.B. ­  questa descrizione è incompleta per un uso reale.

fdc[1]   

fdc[0]   

fdc[1]   

fdc[0]   

Padre Padre Figlio

fdc[1]   

fdc[0]   

1.6.11

Esempio di Codice  ­  3

Padre(produttore)

Figlio(consum.)

sel file pattern file  grep pattern  

stdout  fdc[1]  fdc[0] 

1.6.12

Esempio di Codice  ­  3 (Cont.)sel(file, pattern) {

pipe(fdc);

pid = fork();

if(pid diverso da 0)

{          /* padre ­  produttore */

ifd = open(file, read­only);

loop(nread = read(ifd, buffer, 1024); finchè nread diverso da 0)

write(fdc[1], buffer, nread);

close(fdc[1]); /* così il figlio troverà EOF dopo lo svuotamento della pipe */

close(ifd);

wait(status_address); /* sincronizzati sulla terminazione di grep */

code = (estrai exit code da status);

exit(code);

} else { /* figlio ­  consumatore */

redirect(fdc[0] sul f.d. 0, cioè lo stdin);

execl("/usr/bin/grep", "grep", pattern);

}

}

1.6.13

Sincronizzazione tra Processi● Due o più processi interagiscono tra loro quando si contendono l'uso di 

risorse, permanenti o consumabili.

● Due paradigmi di base:

– Mutua esclusione

– Produttore­consumatore

● Tutti i casi sono riconducibili a produzione e consumo di risorse consumabili.

– Vincolo di sincronizzazione tra P1 e P2 :  "P1  è il produttore di una risorsa consumabile R e P2 è il consumatore di R".

● R è una risorsa software creata ad hoc dal Kernel.

1.6.14

Mutua Esclusione● Paradigma della mutua esclusione:

– risorsa permanente R contesa da più processi P1 ... Pn

– garantire che 

● Ad ogni istante vi sia al max. un processo Pi che occupi R (Mutua Esclusione)

● Ogni processo richiedente ottenga l'uso di R entro un intervallo limitato di tempo (Attesa Limitata)

● Generalizzazione: esecuzione di una parte di codice che deve gestire dati in modo esclusivo  problema della sezione critica.

– L'accesso concorrente a dati condivisi può provocare un'inconsistenza dei dati stessi, se non si adotta una disciplina di accesso.

● Caso tipico: quando si vuole rendere seriale una risorsa permanente del sistema (area RAM, disk controller, etc.)

1.6.15

Problema della Sezione Critica● N processi che si contendono l'uso di dati condivisi

● Ogni processo ha una parte di codice, chiamata sezione critica, nella quale accede ai dati condivisi.

● Problema della sezione critica – garantire che quando un processo Pi sta eseguendo codice nella propria sezione critica, nessun altro processo possa fare altrettanto → trovare un protocollo adeguato.

● Struttura del generico processo Pi

for(;;){    entry section          critical section    exit section           non­critical section}

1.6.16

Produttore­Consumatore● Paradigma produttore­consumatore:

– Risorse consumabili (dati) R prodotte in loop da uno o più Pp e consumate da uno o più Pc

– Dati normalmente trasmessi tramite un buffer di dimensione finita (canale di comunicazione a capacità limitata)  problema del buffer limitato (bounded­buffer problem); talvolta il canale è concettualmente a capacità illimitata.

● Il processo consumatore va comunque a dormire nel caso di risorsa non disponibile (canale vuoto)

● Il processo produttore va a dormire, solo nel caso di capacità limitata, se il canale è pieno.

1.6.17

Produttore­Consumatore (Cont.)● Esempio tipico: due processi comunicano attraverso un buffer comune, 

di dimensione limitata● Dati condivisi:

#define N ...;typedef ... item;item buffer[N];int in = 0, out = 0,counter = 0;   /* in: next free slot in buffer ­                             out: first full slot */

1.6.18

Produttore­Consumatore (Cont.)● Processo produttore:

item nextp;for(;;){

…produce an item in nextp;…while ( counter == N )    /* (while buffer full) */        no­op;buffer [in] =nextp;in = ++in % N;++counter;

}

1.6.19

Produttore­Consumatore (Cont.)● Processo consumatore:

item nextc;for(;;){

while ( counter == 0 ) /* (while buffer empty) */        no­op;nextc = buffer [out];out = ++out % N;­­counter;…consume the item in nextc; …

}● Problema: a causa dell'esecuzione concorrente, le istruzioni:

++counter ­­counter

devono essere istruzioni atomiche, cioè eseguite atomicamente (mutua esclusione), per evitare race conditions (altrimenti il risultato è indefinito).

• N.B. ­ race = corsa

1.6.20

Produttore­Consumatore (Cont.)– Varianti:

●  Un produttore, un consumatore– es. 1: pipe (canale a capacità limitata)– es. 2: processo che legge caratteri da tastiera (canale 

concettualmente a capacità illimitata).● Più produttori, un consumatore

– es.: spooler di stampa● Più produttori, più consumatori

– es.: programma concorrente con più processi che eseguono in multiprogrammazione la stessa funzione.

● Il server HTTP Apache è normalmente configurato in modo da preallocare da 4 a 10 processi server in parallelo, per essere pronto a picchi di carico.

1.6.21

Hardware di Sincronizzazione● L'hardware può aiutare a risolvere il problema dell'atomicità.● Istruzione “test+modify” di una variabile, in modo atomico:

boolean TestAndSet(boolean target){

boolean result = target;target = TRUE;return result;

}● Dati condivisi:

boolean lock = FALSE;● Processo Pi

for(;;){

while (TestAndSet(lock))no­op;

critical sectionlock = FALSE;non­critical section

}● L'implementazione hardware di instruzioni atomiche del tipo visto non è 

semplice.

1.6.22

Semaforo● I problemi visti diventano più complessi quando si estendono a un 

numero arbitrario di processi concorrenti

● Occorre disporre di uno strumento di sincronizzazione di uso generale.

● Mutua esclusione di risorsa permanente R: può ottenersi associando risorse consumabili XR ; ogni processo

– acquisisce una XR prima di utilizzare R

– rilascia XR dopo aver utilizzato R.

● XR: tipo di risorsa fittizia generata dal Kernel, solo per regolare il traffico di processi:

– affluiscono verso la risorsa permanente R (acquisizione di XR)

– se ne distaccano (rilascio di XR)

     chiamato, con evidente analogia, semaforo. E' questo lo strumento generale ricercato.

1.6.23

Primitive di Sincronizzazione● lock() / unlock(): primitive di implementazione di semafori (la risorsa 

consumabile). Risolvono qualunque problema di mutua esclusione.

● Pseudo­codice:

lock(X) {

loop(X non è disponibile)

aspetta;consuma X;

}

unlock(X) {

produci X; /* sblocca eventuale processo in attesa     nella chiamata a lock() */

}

● N.B. ­  lock() e unlock() sono chiamate spesso, nella letteratura tecnica, wait() e signal(), o anche P() e V().

1.6.24

Primitive di Sincronizzazione (Cont.)● send() / receive(): primitive di implementazione di comunicazione 

sincronizzata di messaggi (la risorsa consumabile). Risolvono problemi di tipo produttore­consumatore.

● Pseudo­codice (caso di canale a capacità limitata):

send(m,dest) {

loop(canale pieno)

aspetta;inserisci <m,dest> nel canale; /* sblocca eventuale processo in attesa 

    nella chiamata a receive() */

}

receive(m,mitt) {

loop(canale vuoto)

aspetta;estrai <m,mitt> dal canale; /* sblocca eventuale processo in attesa 

    nella chiamata a send() */

}

1.6.25

Esempio: Sezione Critica di n Processi● Variabile condivisa:

semaphore mutex = 1; /* mutex: mutual exclusion */● Processo Pi

for(;;)

{

wait(mutex);critical sectionsignal(mutex);non­critical section

}

1.6.26

Implementazione dei Semafori● Nello pseudo­codice visto per lock()/unlock() (ma anche per 

send()/receive() ), l'istruzione "aspetta" può significare in pratica due cose:

– No­op (loop continuo, ovvero busy­waiting; impegno di CPU) ­> spinlock (spin while locked)

– Vai a dormire (il processo passa in stato Waiting; sarà svegliato successivamente; non impegna CPU)    semaforo bloccante

● In generale, molto più adatto ad ambienti multitasking

1.6.27

Implementazione dei Semafori (Cont.)● Un semaforo spinlock è normalmente una variabile intera, a cui si accede 

esclusivamente tramite due operazioni atomiche:– wait (S):   while (S <= 0)

                                              no­op;            ­­S;

– signal (S):     ++S;

• Può assumere due valori (semaforo binario):

– 0    risorsa occupata (semaforo bloccato)

– 1   risorsa diponibile (semaforo libero)

1.6.28

Implementazione dei Semafori (Cont.)Implementazione a livello Kernel di un semaforo bloccante:

● Semaforo definito come un record (struttura di dati):struct semaphore{        int value;        process *proclist; /* puntatore a lista di Process Descriptor */};

● Basato su due semplici operazioni:–  sleep() sospende il processo che la invoca (il processo va a dormire)–  wakeup(P) riprende l'esecuzione di un processo sospeso P (il processo vene 

risvegliato).● N.B. ­ queste due operazioni possono essere implementate facilmente in 

qualunque sistema multitasking; in particolare, Unix dispone di funzioni sleep() e wakeup() nel Kernel (N.B. ­  nulla a che vedere con la funzione sleep(3) ).

1.6.29

Implementazione dei Semafori (Cont.)● Le primitive di semaforo possono ora definirsi così:

wait(S): if (­­S.value < 0)                 {                           add this process to S.proclist;

                        sleep();                 }

signal(S):  if (S.value++ < 0)                 {                           remove a process P from S.proclist;

             wakeup(P);                 }

● Diversamente dall'implementazione vista in precedenza, questo semaforo può assumere valori negativi (semaforo contatore); questi corrispondono al numero di processi in attesa della risorsa.

● N.B. ­ la distinzione tra semaforo binario e semaforo contatore è indipendente da quella tra semaforo spinlock e semaforo bloccante.

1.6.30

Sezione Critica di n Processi: ScenarioSem.value Resource (Free, Busy)1 F

P1: wait() 0P1: go B...P2: wait() ­1P2: sleep()P3: wait() ­2P3: sleep()...P1: signal() ­1 FP1: wakeup(P2)P2: go B…P2: signal() 0 FP2: wakeup(P3)P3: go B...P3: signal() 1 F

1.6.31

Sincronizzazione Generica: Scenario

● Exegui B in Pj solo dopo aver eseguito A in Pi

● Si usa un semaforo flag initializzato a 0● Codice:

Pi Pj

 ... ...

A wait(flag)

signal(flag) B

1.6.32

Implementazione in Unix● Unix System V: IPC (InterProcess Communication) ­  insieme di 

chiamate di sistema per sincronizzazione e comunicazione tra processi

– Comprende: a) code di messaggi  b) memoria condivisa  c) semafori

– Implementato ormai in tutti i tipi di Unix, incluso Linux

● Un esempio di implementazione di lock() / unlock() in Unix a livello utente:

– Sfrutta l'apertura di file, in modo esclusivo

– open(file, O_CREAT+O_EXCL): ha successo solo se il file non esiste (e viene dunque creato ex­novo)

– Un semaforo = un file; file esiste: risorsa occupata; file non esiste: risorsa libera.

1.6.33

Esempio di Codice  ­  4/* name: nome del file, cioè del semaforo */

lock(name) {

loop {

fd = open(name, O_CREAT+O_EXCL);

if(errore: il file esiste già)

sched_yield();else if(altro tipo di errore)

return errore;else

return fd; /* file creato in modo esclusivo = risorsa acquisita;     restituisci descrittore del semaforo */

}

}

● N.B. ­  sched_yield(): chiamata sistema per rilascio volontario della CPU ­   il processo è messo in Ready state, in fondo alla ready queue.

1.6.34

Esempio di Codice  ­  4 (Cont.)/* name: nome del file, cioè del semaforo; fd: descrittore del semaforo */

unlock(name, fd) {

close(fd);

if(errore)

return errore; /* uso errato del semaforo */

else {

unlink(name);  /* file rimosso = risorsa rilasciata; da questo     momento può essere ricreato tramite lock() */

return OK;

}

}

● N.B. ­  l'uso di sched_yield() può provocare spreco di CPU (a forza di context switch), se il semaforo è tenuto bloccato per molto tempo (secondi).

1.6.35

Problemi di sincronizzazione● L'uso delle primitive viste può portare a problemi in caso di errori di 

programmazione (uso improprio delle primitive)

● Stallo (deadlock): due o più processi attendono indefinitamente un evento che può essere causato solo da un altro dei processi in attesa.

– Esempio: processi PA  e  PB ; semafori R1 e R2

● Soluzione: acquisire semafori in un ordine prefissato (e rilasciarli nell'ordine inverso).

● Responsabilità del programmatore, non del S.O.

PA

lock(R1);lock(R2);...unlock(R1);unlock(R2);

PB

lock(R2);lock(R1);...unlock(R2);unlock(R1);

1.6.36

Problemi di sincronizzazione (Cont.)● Blocco indefinito (starvation): uno o più processi possono non essere 

mai rimossi dalla coda dei processi in attesa di acquisizione di un semaforo, perchè altri processi in attesa hanno sempre maggior priorità.

– Ciò può avvenire ad esempio se la coda è gestita in ordine LIFO (Last­In, First­Out).

– Problema analogo a quello già visto nel caso dello scheduling di CPU con priorità