Processi - stati, PCB, creazione con fork ed exec

In questa pagina 7

Questa nota descrive il processo: come è fatto in memoria, come il kernel lo rappresenta e lo fa avanzare, come nasce e muore (fork, exec, wait) e come due processi si scambiano dati. Il passaggio dalla singola esecuzione all'esecuzione concorrente di più flussi dentro lo stesso processo è in Thread e concorrenza - modelli, Pthreads e goroutine; la scelta di quale processo far girare è in Scheduling della CPU - FCFS, SJF, priorità e round robin. Le system call sono quelle di System call POSIX, file descriptor e API delle socket; i server che creano un processo per ogni connessione sono in Client e server TCP in C - bind, listen, accept e processi concorrenti.

Il concetto di processo

Definizione (processo). Un processo (process) è un programma in esecuzione. Il programma è un'entità passiva (il file eseguibile sul disco); il processo è un'entità attiva, che esiste quando l'eseguibile viene caricato in memoria. Un programma può generare più processi (più utenti che lanciano lo stesso editor).

Un processo esegue le istruzioni in sequenza: due istruzioni dello stesso processo non vanno in parallelo (salvo i thread). Comprende:

parte	contenuto
codice (text section)	le istruzioni del programma
dati (data section)	variabili globali e statiche
heap	memoria allocata dinamicamente a tempo di esecuzione (`malloc`)
stack	dati temporanei: parametri, indirizzi di ritorno, variabili locali delle funzioni
attività corrente	program counter e registri della CPU

In memoria, per un programma C, lo spazio del processo va dall'indirizzo basso (codice, dati inizializzati e non, poi l'heap che cresce verso l'alto) a quello alto (lo stack che cresce verso il basso, sopra di esso gli argomenti argc/argv e l'ambiente). Le istruzioni e le chiamate di funzione sono quelle già viste in Stack e chiamata di funzioni in ARM; l'allocazione dinamica in C è in Gestione della memoria in C.

Stati di un processo

Durante l'esecuzione un processo cambia stato:

stato	significato
new (nuovo)	il processo viene creato
ready (pronto)	aspetta di ricevere una CPU
running (in esecuzione)	le sue istruzioni sono eseguite
waiting (in attesa)	aspetta un evento (fine di un'operazione di I/O, un segnale, un semaforo)
terminated (terminato)	ha finito, può essere rimosso

Le transizioni:

new --ammesso--> ready --dispatch (scelto dallo scheduler)--> running --exit--> terminated
                   ^                                             |  |
                   |------- prelazione (interrupt del timer) ----+  |
                   |                                                |
                   +--- evento avvenuto <--- waiting <--- attesa di I/O o evento

Un processo che passa la maggior parte del tempo a fare I/O è I/O-bound; se invece calcola soprattutto è CPU-bound. I primi hanno molti burst di CPU brevi, i secondi pochi e lunghi: lo scheduling ne tiene conto.

Il Process Control Block

Il kernel rappresenta ogni processo con un PCB (Process Control Block, detto anche task control block):

campo	contenuto
stato	new, ready, running, waiting, terminated
program counter	indirizzo della prossima istruzione
registri della CPU	contenuto di tutti i registri del processo
informazioni di scheduling	priorità, puntatori alle code
gestione della memoria	memoria allocata (tabelle delle pagine, segmenti)
accounting	CPU usata, tempo trascorso, limiti
stato dell'I/O	dispositivi assegnati, file aperti

In Linux il PCB è la struttura C task_struct, con campi come il pid, lo state, le informazioni di scheduling, un puntatore al padre (parent), la lista dei figli (children), i file aperti (files) e lo spazio degli indirizzi (mm). In molti sistemi le informazioni sui processi (fuori dallo spazio degli indirizzi) stanno nella tabella dei processi (process table), un array di PCB, uno per ogni processo esistente.

Code di scheduling e cambio di contesto

Lo scheduler dei processi sceglie tra i processi disponibili quello che andrà sulla CPU, con l'obiettivo di tenerla sempre occupata. Mantiene delle code:

una ready queue: tutti i processi in memoria pronti ad eseguire;
diverse wait queue: i processi che aspettano un evento (per esempio una coda per ciascun dispositivo di I/O).

I processi migrano tra le code: un processo in esecuzione che chiede un I/O passa nella coda del dispositivo; quando l'I/O finisce (interrupt), torna nella ready queue.

Definizione (cambio di contesto). Il contesto di un processo è rappresentato nel suo PCB. Un context switch (cambio di contesto) avviene quando la CPU passa da un processo all'altro: il sistema salva lo stato del processo uscente nel suo PCB e carica lo stato salvato del processo entrante.

Il tempo del cambio di contesto è puro overhead: durante il passaggio il sistema non produce lavoro utile. Più il sistema operativo e il PCB sono complessi, più il cambio dura; dipende anche dall'hardware (se la CPU ha più insiemi di registri, più contesti si caricano insieme). Nella tabella di scheduling di Scheduling della CPU - FCFS, SJF, priorità e round robin il costo si trascura, ma conta nella scelta del quanto di tempo.

Creazione dei processi

Un processo padre crea processi figli, che a loro volta ne creano altri: si forma un albero di processi. Ogni processo ha un identificatore, il pid. In Linux il primo processo è systemd (pid 1), che avvia i servizi dell'utente; tutti gli altri discendono da lui. Le scelte possibili:

risorse: padre e figli condividono tutto, o solo un sottoinsieme, o niente;
esecuzione: il padre aspetta i figli oppure proseguono in concorrenza;
spazio degli indirizzi: il figlio è un duplicato di quello del padre oppure vi viene caricato un programma nuovo.

`fork`, `exec` e `wait`

In UNIX e Linux:

chiamata	che cosa fa
`fork()`	crea un nuovo processo, copia del chiamante (stesso codice, stessi dati, stesso program counter, copie dei descrittori di file aperti)
`exec` (famiglia `execlp`, `execvp`, ...)	sostituisce lo spazio di memoria del processo con un programma nuovo; non ritorna se riesce
`wait()` / `waitpid()`	il padre aspetta la fine di un figlio e ne legge lo stato di uscita
`exit()`	il processo termina e restituisce uno stato al padre; le sue risorse sono liberate dal sistema
`getpid()`, `getppid()`	pid del processo, pid del padre

Il punto chiave di fork è il valore restituito, diverso nei due processi:

dove	valore di `fork()`
nel padre	il pid del figlio (maggiore di 0)
nel figlio	0
in caso di errore	-1, nessun figlio creato

Dopo la fork ci sono due processi che eseguono lo stesso codice a partire dall'istruzione che segue la chiamata; l'unico modo di distinguerli è guardare il valore restituito. Poiché il figlio ha una copia della memoria del padre, le variabili modificate da un processo non cambiano nell'altro (nella pratica la copia è rimandata fino alla prima scrittura, copy-on-write, v. Memoria virtuale - paginazione su richiesta e sostituzione delle pagine). Il programma completo che segue crea un figlio, che lancia ls -l, mentre il padre aspetta:

fork_exec.cc

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void)
{
    pid_t pid = fork();                       /* da qui in poi due processi */

    if (pid < 0) {                            /* errore: nessun figlio */
        perror("fork");
        return 1;
    } else if (pid == 0) {                    /* ramo del FIGLIO */
        printf("[figlio] pid=%d, padre=%d\n", (int)getpid(), (int)getppid());
        execlp("ls", "ls", "-l", (char *)NULL);   /* sostituisce il programma */
        perror("execlp");                     /* si arriva qui solo se exec fallisce */
        _exit(127);
    } else {                                  /* ramo del PADRE */
        int status;
        pid_t w = waitpid(pid, &status, 0);   /* aspetta questo figlio */
        if (w < 0) {
            perror("waitpid");
            return 1;
        }
        if (WIFEXITED(status))
            printf("[padre] figlio %d terminato con stato %d\n", (int)w, WEXITSTATUS(status));
    }
    return 0;
}

Traccia: dopo la fork il figlio vede pid == 0, stampa i suoi pid e sostituisce il proprio programma con ls; il padre vede pid > 0 (il pid del figlio) e si blocca in waitpid finché il figlio non finisce. Poiché i due rami stampano su stdout in modo concorrente, l'ordine delle righe può cambiare da un'esecuzione all'altra (nel laboratorio 2 si mette una usleep nel padre per renderlo regolare). Si noti _exit nel figlio dopo un exec fallito: exit svuoterebbe i buffer di stdio copiati dal padre, duplicando l'output.

Quanti processi? Il conto delle `fork`

Ogni fork raddoppia i processi che la eseguono. Con

fork();
fork();
fork();
printf("x");

ci sono $2^3 = 8$ processi e la riga viene stampata 8 volte: il primo fork crea 2 processi, entrambi eseguono il secondo (4), tutti e 4 eseguono il terzo (8). Con una condizione cambia: in

if (fork() == 0)
    fork();            /* solo il figlio */
fork();                /* tutti */

la prima fork produce il padre P e il figlio C1; solo C1 esegue la seconda e genera C2 (3 processi); il terzo fork lo eseguono tutti e 3: in totale 6 processi. Il metodo è: contare, per ogni fork, quali processi la raggiungono.

Terminazione, zombie e orfani

Un processo termina quando esegue l'ultima istruzione e chiama exit(): lo stato di uscita va al padre e le risorse sono rilasciate. Un padre può anche terminare un figlio (con abort, o con un segnale) se questo ha superato le risorse, se il suo compito non serve più o se il padre sta uscendo e il sistema non permette ai figli di sopravvivere.

Il padre raccoglie la fine di un figlio con wait: pid = wait(&status) restituisce il pid del figlio terminato e il suo stato. Due situazioni anomale:

caso	cosa succede
zombie (defunct)	il figlio è terminato ma il padre non ha ancora chiamato `wait`: occupa ancora una riga della tabella dei processi (stato `Z` in `ps`) finché non viene raccolto
orfano (orphan)	il padre è terminato prima del figlio: il figlio, ancora in esecuzione, viene adottato da `init`/`systemd` (pid 1), che poi ne raccoglie la fine

Gli zombie non consumano CPU ma esauriscono la tabella dei processi se sono troppi: un server che crea un figlio per connessione deve chiamare waitpid (di solito in un gestore di SIGCHLD). La verifica pratica di orfani e pstree è nell'Esercizio - Creazione di processi con fork, pid e processi orfani (laboratorio 2).

Applicazioni a più processi

Alcuni browser vecchi erano un solo processo: se un sito si bloccava, si bloccava tutto. Google Chrome è multiprocesso, con processi di tipi diversi: il processo browser (interfaccia, disco e rete), un processo di rendering per ogni sito (HTML e JavaScript) e un processo per ogni plug-in. Un sito che si pianta non porta con sé il resto.

Comunicazione tra processi

I processi di un sistema sono indipendenti o cooperanti: un processo cooperante può influenzare gli altri o esserne influenzato, per esempio condividendo dati. Si coopera per condividere informazioni, per accelerare il calcolo (suddividendolo), per modularità o per comodità. I processi cooperanti hanno bisogno di comunicazione tra processi (interprocess communication, IPC). Ci sono due modelli:

modello	funzionamento	pregi	difetti
memoria condivisa (shared memory)	il sistema mappa un segmento nello spazio di più processi, che leggono e scrivono senza altre system call	il più veloce	i processi devono sincronizzarsi da soli (Sincronizzazione - sezione critica, race condition e mutex)
scambio di messaggi (message passing)	`send(messaggio)` e `receive(messaggio)`, mediate dal kernel	più sicuro, utile anche in rete	più lento (system call per ogni messaggio)

Memoria condivisa e produttore-consumatore

Nella memoria condivisa vale il problema produttore-consumatore: un processo produce informazioni, un altro le consuma. Con un buffer illimitato il produttore non aspetta mai e il consumatore aspetta se il buffer è vuoto; con un buffer limitato (bounded buffer, dimensione fissa) il produttore aspetta se è pieno. Il problema nasce quando i due toccano insieme contatori e indici: è la race condition di Sincronizzazione - sezione critica, race condition e mutex, risolta con i semafori in Semafori, monitor e problemi classici di sincronizzazione.

Con le API POSIX un segmento condiviso si crea con shm_open, si dimensiona con ftruncate e si mappa con mmap (vedi anche Sistemi di I-O e memory-mapped I-O):

shm_posix.cc

#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

#define NOME "/os_demo_shm"
#define DIM  4096

int main(void)
{
    int fd = shm_open(NOME, O_CREAT | O_RDWR, 0666);   /* crea l'oggetto di memoria condivisa */
    if (fd < 0) { perror("shm_open"); return 1; }
    if (ftruncate(fd, DIM) < 0) { perror("ftruncate"); return 1; }

    char *p = mmap(NULL, DIM, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if (p == MAP_FAILED) { perror("mmap"); return 1; }

    pid_t pid = fork();                                /* il figlio eredita la mappatura */
    if (pid == 0) {
        strcpy(p, "scritto dal figlio");               /* produttore */
        _exit(0);
    }
    waitpid(pid, NULL, 0);                             /* il padre attende: sincronizzazione minima */
    printf("[padre] letto: %s\n", p);                  /* consumatore */

    munmap(p, DIM);
    close(fd);
    shm_unlink(NOME);                                  /* rimuove l'oggetto dal sistema */
    return 0;
}

Qui la sincronizzazione è affidata a waitpid: il padre legge solo dopo che il figlio ha finito. Se i due processi lavorassero insieme servirebbero semafori (anche questi POSIX, in memoria condivisa).

Scambio di messaggi

Per comunicare con i messaggi due processi P e Q devono stabilire un collegamento (link) e scambiare messaggi con send/receive. Le scelte di realizzazione sono tre.

Diretta o indiretta.

	comunicazione diretta	comunicazione indiretta (casella postale)
operazioni	`send(P, m)`, `receive(Q, m)`	`send(A, m)`, `receive(A, m)` su una mailbox (o porta) A
collegamento	automatico, tra esattamente una coppia di processi	solo se i processi condividono una mailbox; può servire più processi
quanti per coppia	uno	anche più di uno

Con una mailbox condivisa da P1 (mittente), P2 e P3 (riceventi): chi riceve il messaggio? Soluzioni: limitare il collegamento a due processi, oppure far eseguire receive a un solo processo alla volta, oppure far scegliere il sistema (e avvisare il mittente di chi è stato).

Sincrona o asincrona. send e receive possono essere bloccanti (sincrone) o non bloccanti (asincrone): il send bloccante ferma il mittente finché il messaggio è ricevuto; la receive bloccante ferma il ricevente finché non c'è un messaggio; con send non bloccante il mittente prosegue; con receive non bloccante il ricevente ottiene un messaggio valido oppure un messaggio nullo. Se sono bloccanti sia send sia receive si ha un rendez-vous (appuntamento): il produttore-consumatore diventa banale.

Buffering. Una coda di messaggi legata al collegamento può avere capacità:

capacità	effetto
zero	nessun messaggio in coda: il mittente aspetta il ricevente (rendez-vous)
limitata (n messaggi)	il mittente aspetta se la coda è piena
illimitata	il mittente non aspetta mai

Pipe

Definizione (pipe). Una pipe è un canale che permette a due processi di comunicare. Le pipe ordinarie (anonime) sono unidirezionali (un'estremità per scrivere, una per leggere) e richiedono un legame padre-figlio: non si possono usare da fuori del processo che le ha create. Le named pipe (o FIFO) usano un file speciale, sono bidirezionali, non richiedono parentela e possono servire più processi (su UNIX e Windows; mkfifo).

Un esempio di pipe ordinaria: il padre manda una stringa al figlio.

pipe_padre_figlio.cc

#include <stdio.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void)
{
    int fd[2];                                 /* fd[0] = lettura, fd[1] = scrittura */
    if (pipe(fd) < 0) { perror("pipe"); return 1; }

    pid_t pid = fork();
    if (pid < 0) { perror("fork"); return 1; }

    if (pid == 0) {                            /* FIGLIO: legge */
        close(fd[1]);                          /* chiude l'estremità di scrittura che non usa */
        char buf[64];
        ssize_t n = read(fd[0], buf, sizeof buf - 1);
        if (n < 0) { perror("read"); _exit(1); }
        buf[n] = '\0';
        printf("[figlio] ricevuto: %s\n", buf);
        close(fd[0]);
        _exit(0);
    }
    close(fd[0]);                              /* PADRE: chiude la lettura */
    const char *msg = "ciao dal padre";
    write(fd[1], msg, strlen(msg));
    close(fd[1]);                              /* il figlio vedrà la fine del flusso */
    waitpid(pid, NULL, 0);
    return 0;
}

Le estremità inutilizzate vanno chiuse: se il padre non chiudesse fd[1], un figlio che legge fino alla fine del flusso (read che restituisce 0) non la vedrebbe mai. La stessa tecnica, con dup2 per collegare lo standard output di un processo allo standard input di un altro, è alla base delle pipe della shell (ls | wc -l) e di CGI e applicazioni web dinamiche.

Esercizi collegati

Domande d'esame

1. Cosa stampa fork(); fork(); fork(); printf("x");? E se la seconda fork è dentro if (fork() == 0)? Traccia. Ogni fork raddoppia i processi che la raggiungono: tre fork in fila danno 8 processi e 8 x. Con if (fork()==0) fork(); seguito da una fork per tutti: la prima crea 2 processi, solo il figlio esegue la seconda (3 processi), la terza la eseguono tutti (6 processi, 6 stampe se la printf viene dopo).

2. Che differenza c'è tra processo zombie e orfano? Come si evitano gli zombie? Traccia. Zombie: figlio terminato di cui il padre non ha letto lo stato (resta nella tabella dei processi). Orfano: figlio ancora vivo il cui padre è terminato (adottato da init/systemd). Gli zombie si evitano chiamando wait/waitpid (anche in un gestore di SIGCHLD) per ogni figlio.

3. Confrontare memoria condivisa e scambio di messaggi, e dire quando serve la sincronizzazione. Traccia. Memoria condivisa: segmento mappato in più spazi di indirizzamento, comunicazione veloce senza system call ma con sincronizzazione a carico dei processi (race condition sui dati comuni). Messaggi: send/receive mediati dal kernel, più semplici e sicuri ma più lenti; la sincronizzazione è implicita se le operazioni sono bloccanti (rendez-vous).

Versione ripasso

Processo = programma in esecuzione (attivo); programma = file (passivo). Parti: text, data, heap, stack, più program counter e registri.
Stati: new, ready, running, waiting, terminated. I/O-bound = molti burst brevi; CPU-bound = pochi burst lunghi.
PCB: stato, program counter, registri, scheduling, memoria, accounting, I/O e file aperti (Linux: task_struct). Tabella dei processi = array di PCB.
Code: una ready queue, tante wait queue. Context switch = salvare il PCB uscente e caricare quello entrante: overhead puro.
fork(): copia del processo; restituisce 0 al figlio, pid del figlio al padre, -1 se fallisce. exec: sostituisce il programma, non ritorna se riesce. wait/waitpid: il padre raccoglie lo stato. Dopo exec fallito: _exit.
Conto dei processi: ogni fork raddoppia chi la raggiunge; fork();fork();fork(); = 8; if(fork()==0)fork(); fork(); = 6.
Zombie: figlio terminato non raccolto (Z); orfano: padre morto prima, adottato da systemd (pid 1). Albero dei processi, ps -e, pstree.
IPC: memoria condivisa (veloce, serve sincronizzazione; shm_open, ftruncate, mmap, shm_unlink) oppure messaggi (send/receive).
- Messaggi: diretti (P, Q) o indiretti (mailbox); bloccanti (sincroni) o non bloccanti; send+receive bloccanti = rendez-vous; buffer a capacità zero, limitata, illimitata.
- Produttore-consumatore: buffer illimitato (il produttore non aspetta) o limitato (aspetta se pieno).
Pipe ordinaria: unidirezionale, solo padre-figlio, pipe(fd): fd[0] lettura, fd[1] scrittura; chiudere le estremità inutilizzate. Named pipe (FIFO): mkfifo, bidirezionale, senza parentela. Rimandi: System call POSIX, file descriptor e API delle socket, Semafori, monitor e problemi classici di sincronizzazione.
Programma completo fork/exec/wait:

pid_t pid = fork();
if (pid < 0)       { perror("fork"); return 1; }
else if (pid == 0) { execlp("ls", "ls", "-l", (char *)NULL); perror("execlp"); _exit(127); }
else               { int st; waitpid(pid, &st, 0); if (WIFEXITED(st)) printf("stato %d\n", WEXITSTATUS(st)); }

Il figlio ha una copia della memoria (copy-on-write): le variabili modificate da uno non cambiano nell'altro; l'output dei due rami può alternarsi (usleep nel padre per renderlo regolare).

Esempi di conto: fork();fork();fork();printf("x") $\to$ $2^3=8$ stampe. if(fork()==0) fork(); fork(); $\to$ prima fork: 2 processi; solo il figlio fa la seconda: 3; tutti fanno la terza: 6. Metodo: per ogni fork contare chi la raggiunge.
Terminazione: exit() restituisce lo stato e libera le risorse; un padre può terminare un figlio (risorse eccedute, compito non più necessario, padre in uscita). pid = wait(&status): pid del figlio terminato e stato. Zombie = terminato non raccolto (non consuma CPU ma riempie la tabella dei processi); orfano = padre morto prima, adottato da systemd. Un server con un figlio per connessione raccoglie i figli con waitpid in un gestore di SIGCHLD.
Chrome multiprocesso: processo browser (interfaccia, disco, rete), un processo di rendering per sito, un processo per plug-in: un sito che si pianta non porta con sé il resto.
IPC, riassunto: memoria condivisa (veloce, sincronizzazione a carico dei processi) o messaggi (kernel, più semplici e sicuri, più lenti). Messaggi: diretta (send(P,m), receive(Q,m): collegamento automatico, esattamente uno per coppia) o indiretta (mailbox: più processi, più collegamenti); con più riceventi sulla stessa mailbox si limita il collegamento, o un solo receive per volta, o sceglie il sistema. Produttore-consumatore: buffer illimitato (il produttore non aspetta) o limitato (aspetta se pieno).
Pipe: pipe(fd) crea fd[0] (lettura) e fd[1] (scrittura); dopo fork ogni processo chiude l'estremità che non usa; il lettore vede la fine del flusso (read = 0) solo quando tutte le copie di fd[1] sono chiuse. mkfifo per le named pipe (senza parentela). dup2 + pipe realizzano ls | wc -l.
Stati e transizioni: new $\to$ ready (ammissione) $\to$ running (dispatch) $\to$ terminated (exit); running $\to$ ready (timer: prelazione); running $\to$ waiting (I/O o evento) $\to$ ready (evento avvenuto). I/O-bound = molti burst brevi, CPU-bound = pochi lunghi.
PCB: stato, program counter, registri, scheduling (priorità, puntatori alle code), memoria (tabelle delle pagine), accounting, I/O e file aperti; Linux task_struct (pid, state, parent, children, files, mm). Tabella dei processi = array di PCB. Context switch = salva il PCB uscente, carica quello entrante: tempo di puro overhead, dipende da SO, PCB e hardware (più insiemi di registri).
Memoria condivisa POSIX: shm_open + ftruncate + mmap(MAP_SHARED); munmap, close, shm_unlink a fine uso.
Errori tipici: credere che padre e figlio condividano le variabili dopo fork; scordare wait (zombie); non chiudere le estremità della pipe (lettore bloccato); usare exit invece di _exit nel figlio dopo exec fallito; confondere zombie e orfano; contare male i processi con fork dentro un if.

Esercizi su questo argomento

Esercizio - Creazione di processi con fork, pid e processi orfani (laboratorio 2)