Organizzazione di Minix

Livelli di MINIX
Scambio di messaggi interni
Scheduler di MINIX
Area Dati del Kernel
Implementazione della chiamata di primitive
Sequenza temporale dall'inizio di MINIX
Evoluzione temporale
MINIX versione nuova

Livello 1:

• Gestione di interrupt hardware e software (in assembler)
• Context switch fra processi e schedulazione
• Gestione dei messaggi interni al S.O.

Livello 2:

• I/O process: device driver e system task

I primi due livelli costituiscono il kernel di MINIX.

Livello 3:

• MM: implementa le system call per la gestione della memoria (fork, exec, ...)
• FS: System call per file system (mount, read, mknod, ...)

Livello 4:

User level: init, comandi, shell, compilatori, processi vari.

In pratica il S.O. MINIX e' un programma costituito da piu' processi (task e server) e una parte (il livello 1) che non e' un processo ma che li gestisce (e' solo una parte di codice in esecuzione con uno stack privato). Il kernel e' eseguito con la CPU in modo kernel.

C'e' ancora un altro punto di vista, seguendo la modellazione di sistema operativo come  macchina astratta: i livelli 2-3-4 di MINIX costituiscono un insieme di processi che comunicano fra loro tramite scambio di messaggi, gestiti da un S.O. operativo di livello inferiore (il livello 1 di MINIX) che non fa altro che gestire le interruzioni e smistare i messaggi scambiati fra i processi. Per semplicita' chiameremo kernel interno il livello 1 di MINIX, che agisce come un mini S.O.

Attenzione: il meccanismo di scambio di messaggi all'interno di MINIX di cui si sta parlando qui, non e' quello utilizzato dai processi UNIX, basato su socket o pipe. Si tratta di un meccanismo di piu' basso livello, di cui parleremo in seguito.

I processi MINIX, compreso i task, comunicano fra loro attraverso messaggi di 6 tipi diversi, ciascuno di lunghezza e tipologia di componenti prefissata (massimo 24 byte), che sono inseriti sullo stack locale del processo prima della chiamata alla send.
In pratica, come Unix fornisce un certo insieme di primitive di sistema (open, fork, time, ecc.), il kernel interno fornisce solo le seguenti 3 primitive:

• send (dest, &message)
• receive (source, &message),    receive (any, &message)
• send_rec(src_dest, &message)

All'interno di ogni messaggio i campi sono:

• l'identificatore del processo sorgente (l'indice della tavola dei processi, non il pid, perche' siamo "dentro" MINIX, non fuori) e
• il tipo del messaggio, che identifica il numero e il tipo di dati che seguono
• il primo dato identifica la richiesta.

I messaggi non sono bufferizzati fra sender e receiver, e sono completamente bloccanti, nel senso che il mittente non puo' proseguire finche' il ricevente non ha ricevuto e ricopiato sul suo stack locale il messaggio. Allo stesso modo il ricevente e' bloccato finche' un mittente non gli invia qualcosa.

Questo meccanismo si chiama rendez-vous.
Figura 8.2

Al momento del rendez-vous il kernel interno ricopia il contenuto del messaggio dallo stack del mittente a quello del destinatario, liberando poi eventualmente i processi.

Processi utente
I processi utente possono usare solo la funzione send_rec(), che equivale ad una send seguita immediatamente da una receive, entrambe bloccanti, e possono rivolgere richieste solo a uno dei due server, MM o FS.

Un processo utente non chiama comunque direttamente send-rec, ma solo primitive del kernel, ad esempio read. Queste funzioni si trovano in una libreria di sistema. Al loro interno i parametri del messaggio (richiesta di servizio) sono ricopiati sullo stack e viene effettuata una chiamata a send_rec. Una successiva libreria espande la send_rec in una trap.

ESEMPIO

 user process
 . . . . .
 read()      ==>  costruzione messggio
                      ......
                  send_rec (fs, &msg)    ==>   trap (sys_call address)

Server e task
Il codice di questi processi usa direttamente le funzioni di comunicazione primitive di MINIX.

FS process
 . . . .
 receive (any, &msg)      =====>  trap (sys_call address)

Il processo FS nell'esempio precedente, si blocca su una receive. Il kernel interno e' attivato dalla trap.

Un processo utente che esegue una chiamata send_rec entra in stato waiting (in coda d'attesa) finche' l'altro processo non e' pronto a ricevere. Nell'esempio, sopra:

• Lo user richiede una read da disco. Viene quindi effettuata  una send_rec e la richiesta e' messa sullo stack locale. Viene infine eseguita una trap, che, con il meccanismo delle interruzioni, attiva una procedura del kernel interno che gestisce questo tipo di richieste.
• Il kernel interno controlla se il FS e' libero, ossia se e' bloccato su una richiesta di receive.


Ci sono a questo punto due possibilita':

1. Il FS sta lavorando per qualcun altro: ==> il kernel lascia il processo richiedente in coda d'attesa per il FS.
2. Il FS e' bloccato su una funzione receive: ==> il kernel ricopia il messaggio dallo stack del richiedente allo stack del FS. Il FS e' sbloccato ed e' inserito sulla coda dei processi ready per poi eseguire la richiesta. Il processo utente rimane invece bloccato sulla seconda parte della send_rec, cioe' rimane in attesa di ricevere un messaggio dal FS quando avra' terminato il servizio.

Nel primo caso (FS busy) abbiamo le azioni:

• Quando il FS termina il servizio riesegue una richiesta di receive. Viene eseguita una trap che attiva una procedura del kernel interno, mentre il FS rimane bloccato.
• Il kernel interno controlla se c'e' una richiesta in coda d'attesa al FS. Se si' ricopia il messaggio di richiesta sullo stack di FS e, se non era una send_rec ma solo una receive, mette il mittente in coda ready per la CPU, altrimenti rimane bloccato. Il FS e' inserito in coda ready.

Analogamente ci si comporta per le operazioni send.

Si tratta di uno scheduler multilivello.
Figura 8.4

Seguiamo qui la vecchia versione (piu' semplice e illustrata nel primo libro di Tanenbaum) che e' piu' semplice. La versione del laboratorio e ' piu' recente ma estende semplicemente (maggio numero di task, stack di interruzioni ecc.) quella vecchia.
 

Tavola dei processi:   proc

Ogni entry contiene informazioni sui processi: prima i task, poi i server, quindi init e infine i processi utente. NR_TASK = 8 e' il numero dei task. L'indice parte da -7, per cui i task hanno indice negativo.

-8  ........... PRINTER
-7  ........... TTY
-6  ........... WINCHESTER
-5  ........... FLOPPY
-4  ........... MEM
-3  ........... CLOCK
-2  ........... SYSTASK
-1  ........... HARDWARE  (fasullo: viene usato per i messaggi da interruzioni)
 0  ........... mm
 1  ........... fs
 2  ........... init
............... processi utente

curr_proc   indice in proc del processo corrente
proc_ptr     puntatore in proc al processo corrente
idle            = -999  (cur_proc di idle)

Coda dei processi ready

Parlando dello  scheduler  di MINIX, abbiamo visto che ci sono 3 code. Per ognuna (indice NQ = 0  per task, NQ = 1 per server, NQ =  2 per utenti), abbiamo:
rdy_head [NQ]    punta alla testa della coda dei processi ready
rdy_tail [NQ]      punta alla fine della coda (per l'inserimento)

Ogni slot di proc contiene informazioni su un processo.  Le piu' imporanti:
 
 

Nella figura 8.3 sono rappresentate le relazioni logiche di chiamata per le funzioni primitive del kernel interno di MINIX. Vediamo invece ora le relazioni effettive.
Si utilizza il meccanismo di interruzione visto sopra. Le procedure di interruzione sono dei semplici handler, che effettuano operazioni molto veloci, per minimizzare il tempo in cui le interruzioni rimangono disabilitate. Ogni procedura e' collegata ad un task di MINIX, come visibile in figura 8.7. Costruisce cioe' un messaggio, come se l'interruzione fosse un messaggio proveniente da un processo "esterno", e mette in stato ready il task.
In realta' alcuni task (clock, tty) potrebbero essere gia' operativi per precedenti richieste. Allora i dati dell'interruzione (in pratica il fatto che l'interruzione e' arrivata) sono bufferizzate assieme ad altri eventuali dati, e si accoda la richiesta. E' questo l'unico caso di comunicazione non sincrona in MINIX, d'altra parte una interruzione non si "bloccare" come un processo MINIX.

Il kernel interno non e' un processo, non ha pid ne' slot nella Proc Table, ma ha un suo stack riservato e una sua area dati.

Nota: guardando cio' che succede nella figura 8.6, si puo' notare che i valori Flags, CS e IP sono salvati sul top dello stack prima di attivare la procedura di interruzione. Poi sono ripristinati, ma i due stack non sono necessariamente gli stessi......

Nella figura 8.10 sono rappresentate le relazioni logiche, nella 8.11 quelle effettive.

Come si vede ogni send o receive genera una trap, cioe' un'interruzione interna. Si passa quindi in modo kernel, e la CPU e' forzata ad eseguire l'handler richiesto. Il risultato per l'utente e' che viene inserito nella coda di attesa per il fs. Il kernel, a cui e' rimasto il controllo dentro l'handler d'interruzione, esamina le code dei processi ready e guarda se c'e' un processo che puo' essere eseguito. Se si', gli passa la CPU.

Vediamo piu' in dettaglio il codice di MINIX relativo all'esempio sopra (richiesta di read):

TRAP:

• salvataggio automatico dei registri di stato
• attivazione dell'handler corrispondente (scritto in assembler) con entry point s_call.
1. salva lo stato del processo (procedura save) che ha inviato la trap nella tavola dei processi, in posizione cur_proc.
2. carica il puntatore al messaggio da inviare (top dello stack) assieme all'identificatore (indice in proc) del chiamante, del chiamato (fs) e del tipo della chiamata (read) sul top dello stack del kernel,
3. chiama sys_call (function, caller, src, dst, m_ptr)
4. esegue jmp restart. Questa procedura esegue una schedulazione: cerca nella coda ready il primo task, server o processo. Ricopia i dati salvati in proc per quel processo. Rimette sul top dello stack i valori dei flag, CS e IP a lui relativi ed esegue un return from interrupt

La funzione sys_call  (funzione scritta in C) controlla la correttezza dei parametri e se il destinatario e' libero, chiama la procedura mini-send (o mini-receive se si tratta di una primitiva receive).

La funzione mini-send ricopia un messaggio dallo stack del chiamante a quello del destinatario. Ricordarsi che la memoria e' protetta: ogni utente ha una sua area, con il proprio CS e DS e SS, quindi solo in modo kernel c'e' la visivilita' completa (indirizzamento assoluto) ed e' possibile ricopiare aree di memoria.

Per quanto riguarda le interruzioni esterne, il funzionamento e' molto simile. Si sono 4 tipi di interruzione:
tty_int, lpr_int, disk_int e clock_int. Ad esse corrispondono 4 indirizzi nel vettore delle interruzioni a routine assembler. Tutte chiamano save, e preparano un messaggio per chiamare la procedura interrupt (scritta in C) invece di sys_call.
Quest'ultima schedula il task che aspettava l'interruzione come ready (se era blocked) e lo manda in esecuzione, o in coda ready, se c'era gia' un altro task running.
 

• minix   entry point per il kernel. Routine in assembler attivata al reset. A sua volta attiva:
• main     scritto in C. Inizializza proc con le informazioni realative ai 10 task e server iniziali. Inizializza le 3 code ready. La situazione delle code ready e' la seguente:

Inizializza il vettore delle interruzioni, ecc. Chiama pick-proc che effettua la schedulazione e che restituisce cur_proc, puntatore al primo processo che sara' attivato. Fino a questo momento non esistono ancora processi. Infine chiama

• restart    ripristina l'ambiente (registri ecc.) come indicato in proc[cur_proc]. Le ultime istruzioni di restart sono di mettere sullo stack del kernel il registro dei Flags, CS e IP memorizzati per cur_proc, quindi esegue una istruzione iret, return from interrupt. Guardando la Figura 1.16   vediamo che il contenuto dello stack e' ripristinato sui registri. Quindi l'istruzione eseguita subito dopo dalla CPU e' quella puntata da IP (prima istruzione del nuovo processo). Si ritorna in modo user.  restart sara' in sequito chiamata solo dentro una procedura di interruzione.

Da questo punto l'interruzione e' asincrona. cur_proc vale -8 e indica l'entry di proc contenente le indicazioni per il task PRINTER.

Processo PRINTER. A questo punto si puo' parlare di processo.
Ogni task e' strutturato allo stesso modo:

entry point
init()    /* inizializzazione */
while (TRUE)
    { receive (ANY, &msg);     =========> trap
      esegue la richiesta
    }

All'esecuzione di receive, viene emessa una trap che attiva l'handler  s_call.
Il processo PRINTER rimane quindi bloccato. Seguiamo il kernel:

s_call  salva lo stato del processo in proc. Costruisce il messaggio con la richiesta (attesa di ricevere un messaggio) sul top dello stack del kernel. Chiama
sys_call.c che controlla se ci sono processi in lista d'attesa per PRINTER (campo  p_callerq  di proc[cur_proc]). Naturalmente non ce ne sono. Toglie PRINTER dalla ready queue tramite la funzione unready. Quest'ultima chiama pick-proc che assegna a cur_proc un nuovo valore, cioe' TTY. In seguito s_call esegue un jmp restart che attiva il processo TTY,
mettendo in IP l'indirizzo dell'entry point di TTY.

Processo TTY.  Si comporta allo stesso modo di PRINTER.

entry point
init()      /* inizializzazione */
while (TRUE)
    { receive (ANY, &msg);      =========> trap
      esegue la richiesta
    }

L'esecuzione di receive provoca una trap, eccetera....

Quando tutti i processi hanno eseguito l'operazione receive (anche i server hanno la stessa struttura) viene attivato il processo init. Finche' non ci sono richieste il kernel rimane in stato idle.

Evoluzione temporale    (Indice)

Supponiamo che la situazione della coda ready sia la seguente:

Figura 8.13

Il processo proc1 possiede la CPU. Arriva una interruzione del clock.
Viene attivata l'interrupt handler clock_int (vedi  Figura 1.16 ). Salva lo stato del processo proc1 su proc. Costruisce il messaggio con la richiesta per il task CLOCK (si tratta semplicemente di un messaggio fasullo, proveniente da HARDWARE e contenente l'indicazione che c'e' stata un'interruzione dal clock).   Chiama successivamente
interrupt.c che incrementa lost_tiks. Poiche' il processo  attivo era di tipo user, e quindi con minore priorita' di un task, e il task CLOCK e' ora ready (era bloccato in attesa di una interruzione) assegna immediatamente cur_proc al task CLOCK tramite la procedura pick_proc. Quindi torna a clock_int che attraverso restart riattiva CLOCK. (nota: proc1 rimane dov'era in coda ready).

Processo CLOCK.
Chiama la procedura do-clock-tick che controlla se ci sono allarmi da attivare. Aggiorna il tempo dell'ultimo processo user (se era attivo precedentemente un processo user, come in questo esempio) e controlla se ha superato il quanto di tempo (100 millisec.). Supponiamo che proc1 abbia raggiunto il massimo: viene chiamata la procedura
sched.c che inserisce il processo proc1 alla fine della sua coda ready. Poi aggiorna cur_proc tramite pick_proc (schedulazione). Ritorna a do-clock-tick che ritorna al main .
Il task CLOCK resta di nuovo bloccato su un receive (non e' piu' presente in coda ready).

Nota: l'handler della trap e' s_call, che chiama la procedura sys-call. E' l'unica system call che esiste in Minix, ed e' usata per inviare e/o ricevere messaggi.

   sys_task         wini_task         floppy_task         .........
      |                 |                  |
      |                 |                  |
      --------------------------------------
                        |
                        | 
                       s_call

Puo' rendere ready qualunque task.

MINIX versione nuova  (Indice)

Vediamo qui solo le cose piu' importanti relative al kernel:
 

• C'e' un task in piu'
• Le routine di interruzione sono ottimizzate come codice:
• s_call espande in linea parte di save
• Ci sono diverse versioni a seconda del tipo di CPU
• Ci sono due procedure Restart (anche restart1) la cui chiamata e' simulata sullo stack da save
• E' gestita in modo piu' chiaro la possibilita' di avere nesting di interrupt (rientranza)
• Sono segnalati meglio i punti in cui le interruzioni sono disabilitate.
• Ci sono piu' posizioni nella tavola proc (32 processi e 9 task)
• I nome dei file e delle directory sono diversi in alcuni casi.
• Eccetera.

I comandi di MINIX sono un sottoinsieme di quelli di Unix, con qualche differenza. Ad esempio manca il comando ps, sostituito dall'uso dei due tasti F1 e F2 (vedere minix_uso.html ). Inoltre i comandi per accedere a file DOS su floppy sono diversi, iniziano con "dos" anziche' "m" (esempio: dosdir, dosread, doswrite,...) e sono meno numerosi.

Non si puo' stampare direttamente (manca driver stampante di rete). Bisogna quindi farsi una copia su floppy (in DOS) e poi stampare da Linux o da Windows. Esistono i soliti editori di Unix, piu' "mined", che pero' non e' comodissimo.

Il compilatore C non e' quello di Unix, ma e' stato realizzato usando l'Amsterdam Compile Tool Kit. E' comunque abbastanza standard.

Attivazione:    cc  filename

Passi di compilazione:

1. /lib/CPP      preprocessor ( _.c ==> _.i )
2. /lib/CEM    parser ( _.i ==> _.k )
3. /lib/OPT      optmizer (_.i==> .m )
4. /lib/CG       code generator (_.m ==> _.s )
5. /lib/ASLD  assembler/loader (out  a.out)

Opzioni di compilazione

• -D   define, consente di definire simboli
• -F  il file successivo conterra' l'uscita del parser
• -I  directory per include
• -LIB  genera un modulo per libreria
• -R  warning per non standard
• -c  non esegue l'ultimo passo (link)
• -o  il file indicato successivamente conterra' l'eseguibile
• -v  verbose

Costruzione binario di MINIX

Il S.O. MINIX e' fisicamente costituito da un unico file binario (image) contenente gli eseguibili di bootblock, init, kernel, fs, mm, menu (fschk)
riuniti insieme dopo la compilazione separata dal programma build.

Per ottenere image:

• Si genera il file kernel: sotto /usr/src/kernel  ==>  eseguire make   (make clean per ripulire)
• Si genera il file fs:  sotto /usr/src/fs   ==>  eseguire make
• Si genera il file mm:  sotto /usr/src/mm   ==>  eseguire make
• Si puo' anche evitare di compilare separatamente le varie componenti usando il Makefile che si trova in    /usr/src/tools  eseguendo make.
• Nella stessa directory eseguendo make image viene costruito il file image.
• Per avere il boot su floppy si esegue il comando mkboot fdboot fd0

Ricordarsi di dare prima la data corretta.
Per maggiori informazioni sul flusso di controllo del kernel di MINIX consultare  minix_flow.html. Per informazioni sulla struttura dei device, vedere la sezione 7.

Per informazioni sull'avviamento di MINIX in Laboratorio leggere minix_uso.html