Introduzione

Tutti i calcolatori moderni sono in grado di elaborare diverse cose contemporaneamente, mentre un programma utente è in esecuzione, un calcolatore può anche leggere da un disco e stampare su un terminale o una stampante.

In un sistema multiprogrammato, la CPU passa di programma in programma, eseguendo ciascuno di essi per alcune decine o centinaia di millisecondi. A dire la verità, in qualunque momento la CPU esegue un solo programma, mentre nell'arco di un secondo può lavorare su più programmi, dando così agli utenti l'illusione del parallelismo. Qualche volta si parla di pseudoparallelismo per indicare questo veloce saltare avanti e indietro tra i programmi della CPU, in contrapposizione al vero parallelismo hardware della CPU, che effettua delle elaborazioni mentre stanno lavorando uno o più dispositivi di I/O.

E' molto difficile tenere sotto controllo le molteplici attività parallele. Nel corso degli anni, i progettisti di sistemi operativi hanno sviluppato un modello che rende più facile trattare il parallelismo.

Il modello dei processi

Nel modello a processi, tutto il software eseguibile sul calcolatore, compreso spesso il sistema operativo, è organizzato in un certo numero di processi. Un processo è un programma in esecuzione, e comprende anche i valori correnti del program counter, dei registri e delle variabili. Concettualmente ciascun processo ha la propria CPU virtuale, in realtà, invece, la vera CPU salta avanti e indietro da processo a processo.

Per capire il sistema è molto più facile pensare ad una collezione di processi eseguiti in modo (pseudo) parallelo, piuttosto che pensare che la CPU passi da un programma all'altro. Questo rapido saltare avanti e indietro viene chiamato multiprogrammazione. Con la CPU che salta avanti e indietro tra i processi, la velocità a cui un processo realizza la sua computazione non sarà uniforme e probabilmente nemmeno riproducibile se lo stesso processo viene eseguito di nuovo. Così i processi non devono essere programmati con delle assunzioni sulle temporizzazioni.

Quando un processo ha dei bisogni critici in tempo reale, cioè certi eventi devono accadere assolutamente entro un numero di millisecondi specificato, occorre prendere delle misure speciali per assicurare che questo succeda. Normalmente la maggior parte dei processi non è influenzata dalla multiprogrammazione della CPU o dalla velocità relativa dei diversi processi. La differenza tra un programma e un processo è sottile, ma cruciale.

Un'analogia può aiutare a chiarire questo punto.

Consideriamo un informatico in cucina che sta preparando una torta di compleanno per sua figlia. Egli ha una ricetta per una torta di compleanno e una cucina ben fornita con gli ingredienti necessari: farina, uova, zucchero e così via. In questa analogia, la ricetta è il programma, l'informatico è la CPU e gli ingredienti sono i dati in ingresso. Il processo è l'attività costituita dal nostro cuoco che legge la ricetta, prende gli ingredienti e prepara la torta. Ora immaginiamo che l'informatico cominci a correre gridando perchè è stato punto da un'ape. Il calcolatore registra il punto della ricetta a cui il cuoco è arrivato (lo stato del processo viene salvato), tira fuori un libro di pronto soccorso ed inizia ad eseguirele istruzioni. Qui vediamo che il processore è passato da un processo (preparare una torta di compleanno) ad un altro di priorità più alto (somministrazione di cure mediche), ciascuno con il proprio programma (ricetta e libro di pronto soccorso). Quando la puntura d'ape è stata curata, l'informatico torna alla sua torta, continuando dal punto in cui l'aveva lasciata.

L'idea chiave è che un processo è un'attività qualsiasi che ha un programma, con un ingresso, un'uscita e uno stato. Un processore singolo può essere condiviso da diversi processi, attraverso l'uso di un algoritmo di scheduling che interrompa il lavoro di un processo per servirne un altro.

Gerarchia di processi

I sistemi operativi che si basano sulla nozione di processo devono fornire un metodo per creare tutti i processi di cui si ha bisogno. In sistemi molto semplici o in sistemi progettati per eseguire un'unica applicazione, è possibile che all'avvio del sistema siano già presenti tutti i processi necessari.

In Linux, invece, questi ultimi vengono creati attrverso la chiamata di sistema fork, che crea una copia del processo chiamante. Anche il processo figlio può eseguire una fork, e così è possibile avere un albero di processi.

Come semplice esempio del modo in cui sono trattati gli alberi di processi, vediamo adesso come Linux inizializza se stesso in fase di boot. Dopo la fase di avvio (vedi [1]), Linux esegue una serie di scripts che lo portano alla lettura del file /etc/inittab. Questo file contiene una serie di righe del tipo:

una per ciascun terminale di sistema. Se i terminali sono N il sistema creerà, attraverso la system call fork, N processi ciascuno dei quali eseguirà il programma /sbin/agetty. Questo programma richiede all'utente che si connette da quel terminale di inserire una user id e una password. Dopo l'autenticazione dell'utente il controllo passa a un programma denominato shell che consente l'interazione tra utente e computer attraverso opportuni comandi. Questi ultimi possono generare nuovi processi e così via. In questo modo, nel sistema, tutti i processi appartengono ad un singolo albero, la cui radice è detta init (task idle).

In Fig. 1 è possibile osservare un esempio di gerarchia di processi Linux.

Step 0: un semplice memory manager

Prima di continuare con la descrizione di come Linux (e quindi anche il nostro kernel) gestisce i processi, introduciamo in questa sezione un semplice memory manager che ci tornerà utile più avanti.

Un sistema operativo moderno dovrebbe avere un memory manager che gestisca la memoria virtuale, lo swap, slab allocator ed altre cose di questo tipo. Anche a noi piacerebbe avere queste cose, ma il nostro obiettivo è quello di realizzare il kernel step by step, implementando ad ogni passo solo quello che riteniamo indispensabile. Per ora a noi basta un memory manager che allochi/deallochi pagine di memoria fisica in modo da poter allocare un address space minimale per i nostri processi. Più avanti, magari, miglioreremo questa gestione.

Il nostro memory manager alloca semplicemente 64 pagine (ciascuna di 4096 bytes) nell'area di memoria seguente a quella del kernel. Attraverso due semplici routine: get_free_page, free_page; avremo la possibilità di allocare e deallocare le pagine. Una mappa di bit verrà mantenuta per sapere, ad ogni istante, quali sono le pagine utilizzate e quali sono quelle libere.

Iniziamo con il creare un file mm.h che contenga l'interfaccia del nostro memory manager:

Si osservi la definizione della costante PAGE_SIZE che definisce la size delle nostre pagine in memoria. La prima routine cerca una pagina libera e la restituisce in output, mentre la seconda libera una pagina precedentemente allocata. Definiamo ora il file mm.c in cui definiamo alcune costanti:

dove la prima ci dice che la memoria riservata ai processi inizia proprio dove termina l'area riservata al kernel. Inoltre, viene stabilito a priori il numero di pagine riservate ai processi.
Definiamo poi la mappa di bit costituita da 8 bytes (8*8=64 bits). Se il bit i è uguale a 0 significa che la pagina i è libera, altrimenti è in uso.

Su questa mappa utilizzeremo tre funzioni di help: get_bit, clear_bit e set_bit. La prima restituisce l'i-esimo bit della mappa, la seconda azzera l'i-esimo bit della mappa, mentre l'ultima imposta a 1 l'i-esimo bit.

A questo punto è facile implementare le due routine principali del memory manager. La funzione get_free_page scorre la mappa di bit e non appena trova l'i-esimo bit a 0, lo marca a 1 e restituisce la i-esima pagina.

La funzione free_page, invece, dato un indirizzo in input cerca di capire a quale pagina i si riferisce. Trovato tale valore i la funzione azzera l'i-esimo bit della mappa. La funzione genera un kernel panic se l'indirizzo in input non punta al primo byte di una delle 64 pagine disponibili.

In questo step abbiamo aggiunto il file kernel_map.h che contiene alcune costanti che delimitano l'area riservata al kernel.

Abbiamo, inoltre, definito la funzione panic nel file panic.c che stampa semplicemente un messaggio e cicla all'infinito in modo da arrestare l'esecuzione del kernel. Abbiamo già visto sopra l'uso di questa routine da parte del memory manager.

In Fig. 6 è possibile osservare come sarà suddivisa la memoria fisica alla fine degli steps descritti in questo articolo.

Task State Segment (TSS) & Local Descriptor Table (LDT) di un processo

L'architetture Intel 80x86 utilizza uno specifico segmento, chiamato Task State Segment (TSS), per memorizzare il contesto hardware di un processo. Come vedremo nella sezione successiva, ad ogni processo vengono riservati due descrittori: uno per il TSS e l'altro per la Local Descriptor Table (LDT). Questi descrittori sono, rispettivamente, chiamati TSS Descriptor e LDT Descriptor.

Facendo riferimento al documento [1] avremo i seguenti valori per i vari campi del TSS Descriptor:

Il registro TR conterrà il selettore del TSS del processo correntemente in esecuzione.

Per ogni processo, invece, esiste nella LDT un LDT descriptor che consente di recuperare il segmento in cui è memorizzata la LDT per quel dato processo. La LDT è una tabella contenente 3 descrittori che consentono di reperire il code, data e lo stack segment del processo.

Step 1: setup della Global Descriptor Table (GDT)

In [1] abbiamo ampiamente parlato della GDT e del suo impiego nella architettura Intel. In quell'articolo abbiamo anche visto come inizializzare le prime 3 entries. La prima entry è stata inizializzata con valori nulli, la seconda e terza, rispettivamente, sono state inizializzate con il riferimento al code e data segment del kernel (entrambi partono dall'indirizzo 0x00, l'unica cosa diversa sono i permessi). In questo step completeremo il setting della GDT al fine di poter effettuare una corretta gestione dei processi.

La Fig. 7 mostra come verrà inizializzata la GDT in questo step.

Ricordiamo, innanzittutto, che ogni entry è composta da 8 bytes. Le prime 3 entries verranno impostate come già detto sopra, poi, per ciascun processo, ci saranno due entries, una che punta al TSS e l'altra che punta alla LDT.

Il TSS conterrà lo stato del processo, mentre la LDT, come sappiamo, conterrà 3 entries grazie alle quali sarà possibile accedere al codice, dati e stack del processo. La GDT è composta da 2¹³=8192 entries=3+2*NR_TASKS (13 bit disponibili in un selettore, vedi [1] ), da cui si ricava che il numero max di processi allocabili è NR_TASKS=(8192-3)/2=4094 (ovviamente è approssimato per difetto).

Nel file head.S modifichiamo la routine startup_32 invocando una nuova routine chiamata setup_gdt poco prima della chiamata a start_kernel. La routine setup_gdt imposterà le prime 3 entries in modo analogo a quello visto in [1] , mentre imposterà a NULL (cioè tutti valori 0) tutte le entries inerenti ai processi.

Piccole altre modifiche al codice sono state apportate in questo step. Ad esempio, il numero max di processi allocabili è stato fissato a 8 (lo so un pò pochino ma per ora bastano) nel file tasks.h. Poi nel file main.c ho scritto un pò di codice di debug per il gestore della memoria attivabile mediante la modifica della variabile DEBUG nel Makefile.

Stato di un processo

Sebbene ciascun processo sia un'entità indipendente, con il proprio program counter e il proprio stato interno, esso ha spesso bisogno di interagire con altri processi. Un processo può generare dei dati in uscita che un altro processo usa come dati in ingresso. Nel comando di shell:

il primo processo, l'esecuzione di cat, concatena tre file producendo in output un unico file. Il secondo processo (grep) seleziona, dall'output del primo processo, tutte le linee che contengono la parola "tree". In funzione della velocità relativa dei due processi (che dipende per entrambi dalla complessità relativa dei due programmi e da quanto tempo di CPU ciascuno ha a disposizione), potrebbe succedere che quando grep è pronto ad andare in esecuzione, non c'è nessun dato pronto. Allora deve essere bloccato finchè non è disponibile in ingresso un dato. Un processo si blocca perchè logicamente non può continuare l'esecuzione, ad esempio perchè sta aspettando un dato non ancora disponibile. E' possibile anche che un processo, concettualmente pronto e capace di andare in esecuzione, sia fermato perchè il sistema operativo ha deciso di allocare per un pò la CPU ad un altro processo.

In Fig. 2 è possibile osservare il diagramma degli stati di un processo.

Tale diagramma mostra che un processo Linux può trovarsi essenzialmente in 5 stati: running, ready, waiting, stopped e zombie.

Running: in tale stato il processo è correntemente in esecuzione.

Ready: il processo è pronto per entrare in esecuzione ma aspetta che lo scheduler (un componente del kernel che si preoccupa di selezionare, di volta in volta, il processo che deve essere eseguito) gli assegni la CPU. In Linux i due stati Running e Ready sono collassati in un unico stato denominato TASK_RUNNING.

Waiting: un processo entra in tale stato quando attende il verificarsi di un evento o che una risorsa diventi disponibile. Linux utilizza principalmente due tipi di attesa, interrompibile e non interrompibile.

Nel primo caso il processo può essere risvegliato da un evento, mentre nel secondo caso ciò non avviene perchè magari il processo si è messo in attesa direttamente su eventi dell'hardware.

Stopped: quando avviene il debugging di un processo, l'utente può decidere di far stoppare l'esecuzione in un punto particolare. In tal caso il kernel invierà un segnale di stop al processo che interromperà quindi la sua esecuzione.

Zombie: in tale stato il processo ormai è terminato ed ha rilasciato tutte le risorse tranne l'entry nella process table (che analizzeremo più avanti). Questo avviene perchè tale entry contiene molte informazioni statistiche che potrebbero servire al padre su sua esplicita richiesta.

Strutture Dati

Ogni processo all'interno di un sistema Unix è identificato da un valore intero chiamato pid (process identificator). Le informazioni relative a ciascun processo sono contenute in una particolare struttura dati detta Process Descriptor (task_struct in Linux). Questa struttura tiene traccia di informazioni del tipo:

- pid del processo;
- stato del processo;
- informazioni statistiche;
- informazioni di scheduling (più avanti vedremo cosa sono);
- registri;
- molto altro ancora.

Tutti i descrittori di processo vengono collezionati in una opportuna tabella detta Process Table. Le operazioni generalmente associata ad essa, sono quelle di aggiungere e rimuovere un task, oppure reperire un task dato il suo valore di pid.

Aggiungere un nuovo task alla tabella, significa essenzialmente associare un task ad una entry (slot). Nelle prime versioni, Linux ricercava uno slot libero facendo ogni volta la scansione di tutta la tabella (questa sarà la tecnica che adotteremo anche nel nostro kernel, visto che è la più semplice da implementare), le versioni più recenti utilizzano, invece, una lista che tiene traccia di tutti gli slot liberi (slot free list).

La Fig. 3 mostra un esempio di process table con 3 process descriptor (A, B e C) che descrivono 3 differenti processi.

continua prossimo post ...

Bibliografia

[1] Linux Native Boot Process

 Create your own free wiki!Support CommunityPublic, not yet premium Privacy Policy RSS