MINIX in ASM

Il professor Boerger ha analizzato, in un suo articolo, il kernel Minix tramite le Abstract State Machine (ASM). Una sorta di pseudocodice su dati astratti che permette di avere una visione globale su sistemi molto complessi e nè facilita l’estensione delle funzionalità.
Di seguito riporto un sunto in italiano.

O.S. Kernel in ASM

Il tempo del sistema è tenuto contando i cicli di clock(tick clock). Questo compito è affidato ad un task, che quando si verifica un tick di clock riceve un messaggio di interruzione e registra il time attuale del sistema. Registrare il passare del tempo consente di eseguire operazioni centrali del
kernel quali: notifica allarme dei processi, operazioni che consentono di cambiare lo stato di un processo(processing switching) e lo swapping. Il task che si occupa di processare i compiti relativi al tick di clock è modellato da una ASM chiamata ExecClockISR. Ad ogni occorrenza di una interruzione per tick di clock viene seguita un passo della ExecClockISR ASM,a sua volta descritto da tre azioni, in successione:

• DeSchedule : descrive la politica di scheduling per i processi utente. Se un processo è da troppo tempo in esecuzione(RunTooLong) ed un altro è presente in lista pronti; il processo corrente viene inserito in fondo alla lista pronti utente. la procedura viene eseguita ad interruzioni disabilitate
  
• ManageTimedFeatures : aggiorna il time del sistema a quella corrente(now) e chiama le componenti relative alla notifica dei processi sospesi,in swap e zombie.
  
• ReSchedule : settare 'cur_proc'(currp) e 'proc_ptr'(tabella dei processi),rispettivamente l'identificatore al processo corrente e il puntatore alla tabella dei processi Se il sistema è inattivo 'cur_proc' e 'proc_ptr' vengono settati ad un valore speciale IDLE, per identificare lo stato di inattività. Per impostare il processo corrente controlla se è presente un processo nelle liste pronti, in ordine di priorità, verifica : quella dei task, dei processi server e di quelli utente.Se è in esecuzione il task per il controllo del ciclo di clock, 'cur_proc' = CLOCKTASK. Viene settato anche il puntatore al processo bill_ptr che conta i cicli di clock
  della CPU.
  

ExecClockISR =
if HwClockTick then
DeSchedule
step ManageTimedFeatures
step ReSchedule

Nota. Scrivere questa regola come un turbo-ASM sequenziale riflette che la sua azione è considerata "atomica" L'uso della tecnica di locking farà si che riusciamo mappare un passo della ASM, visto come l'esecuzione di tre sottomacchine, in una sequenza di azioni protette da LOCK e UNLOCK, per ottenere la mutua esclusione nelle zone critiche, visto che siamo in uniprocessor, basterà disabilitare prima di una sezione critica.

Processi.
Distinguiamo tre tipi di processi:

• user(utente)
  
• system (di sistema)
  
• device (dispositivi)

abbiamo anche 2 tipi di processi speciali: idleProcess e nullProcess
Quindi :
Process = DeviceProcess
U SystemProcess U UserProcess U{idleProcess,nullProcess}
RealProcess = Process\{idleProcess,
nullProcess}

Ogni processo ha un suo stato interno(registri,pc,psw,etc) il quale viene salvato al momento del DeSchedule (stato da running a ready) e ripristinato quando viene chiamata la sottomacchina ReSchedule.
Ogni processo è schedulato per un certo quanto di tempo. Il valore dell'intervallo di tempo associato al processo è memorizzata nella locazione timeQuant(currp) che decresce quando il processo è in esecuzione
In caso che un processo è da troppo tempo in esecuzione RunTooLong passa dalla testa della coda readyq(kind(currp)) alla coda.
Gli accessi alla coda pronti e l'aggiornamento di stato di processi sono e devono essere fatti in mutua
esclusione. La coppia di macchine LOCK ed UNLOCK consentono di eseguire operazioni senza interruzioni..

DeSchedule =
SaveState //salvo stato processo in esecuzione
Lock //disabilità interruzioni
seq
status(currp) := ready //setta lo stato di currp a ready
HandleProcessQuantum(currp) //se scade il quanto di tempo commuta contesto
seq
UnLock //abilità interruzioni
where
HandleProcessQuantum(p) =
if p ∈ UserProcess then // solo per i processi utente
timeQuant(p) := timeQuant(p) − 1 //decrementa il quanto
if RunTooLong(p) then //se è da troppo tempo in esecuzione
RemoveHead(readyq(kind(p))) //rimuove dalla testa
seq
Enqueue(p, readyq(kind(p))) // e mette in coda
RunTooLong(p) = (timeQuant(p) − 1 minUserTimeQuant)

ReSchedule =
ScheduleNext //seleziona nuovo processo in esecuzione
seq
RestoreState(currp) //ripristina lo stato del processo
where
ScheduleNext =
prevp := currp //prevp prende proc precedente
let p = selectLowLevelScheduler(readyq) /*preleva proc da mandare in esecuzione,per
priorità,dalla lista pronti*/
if p = undef then //se non ci sono processi in coda pronti
currp := idleProc /*si assegna a currp il processo speciale per identificare lo stato di inattività del sistema */
else
currp := p //altrimenti si manda il prcesso in esecuzione
status(p) := running // modifica stato in runnung

Quando non ci sono processi nelle liste pronti idleProcess viene schedulato.Può essere visto come un processo che fa attesa attiva finchè non si verifica un INT (while true do Skip).

ManageTimedFeatures =
now := now + ticklength //aggiona ora corrente
Wake(clockDriver) // sveglia il task swap driver
seq
Wake(deZombifier) // sveglia task che elimina i proc. zombie

ManageTimedFeatures aggiorna l'ora corrente aggiungendogli ticklength e sveglia i i task che gestiscono i processi sospesi in swap e il kill dei zombie(Wow come Resident Evil), rispattevamente chiamando le sottomacchine ExecSwapper ed ExecDeZombifier.

2 ExecCLOCKD RIVER
ManageTimedFeatures sveglia attraverso la regola wake la sottomacchina ExecClockDriver, inizializzata a sleep.
ExecClockDriver chiama le 2 sottomacchine:

• UpdateStorageTimes: aggiorna il time dei processi presenti in disco ed
  esegue la macchina ExecSwapper
  
• ResumeAlarmedProcesses: i processi con
  tempo di attesa con tempo di attesa alarmTime(p) superiore a now vengono svegliati,cioè inseriti in lista pronti.

e si rimette a “dormire”.

ExecClockDriver =
Lock
seq
UpdateStorageTimes
Wake(swapper) //sveglia la macchina ExecSwapper
ResumeAlarmedProcesses
UnLock
PutToSleep(clockDriver) // ritono a 'dormire'

UpdateStorageTimes =
forall p ∈ Process
if status(p) = swappedout then //per ogni proc residente in disco
swappedOutTime(p) := swappedOutTime(p) + 1 // inc. tempo di permanenza fuori swap
else
residencyTime(p) := residencyTime(p) + 1 // incr. tempo permanenza nel disco

ResumeAlarmedProcesses =
let alarmed = { p ∈ RealProcess | alarmTime(p) ≤ now }
if alarmed ≠ Ø then
forall p ∈ alarmed //se ci sono processi da svegliare
alarmTime(p) := undef //azzera allarme
MakeReady(p) //metti il processo in coda pronti

MakeReady(p) =
Lock
seq
Enqueue(p, readyq(kind(p))) //mette il processo p nella sua lista pronti
status(p) := ready // cambia lo stato del processo
seq UnLock

3 La componente DeZombifica
La macchina ExecDeZombifier in attesa su un semaforo, quando viene svegliata, cerca tutti i processi terminati ma che non hanno rilasciato le risorse poichè condividevano le risorse con i loro figli ora(now) terminati

ExecDeZombifier =
Lock seq
KillAllZombies
UnLock
PutToSleep(deZombifier) //torna a 'dormire'
where

KillAllZombies =
letdeadzs = { z ∈ zombies | children(z ) ≠ Ø} //zombie senza figli
zombies := zombies \ deadzs //aggiorno insieme dei proc zombie
forall z ∈ deadzs
parent(z ) := undef //kill zombie senza figli

children è una funzione derivata da parent, children(p) = {q | parent(q) = p}, che ha sua volta è una funzione dinamica.


4 La componente Swapper.

La sotto macchina ASM ExecSwapper ha il compito di effettuare lo swap dei
processi user tra memoria e disco,e viceversa. Nello stato iniziale fa attesa
passiva su un semaforo.
ExecSwapper = DiskSwap step PutSwapperToSleep


4.1 La Componente DiskSwap
La macchina astratta DiskSwap usa una funzione nextProcessToSwapIn per determinare il prossimo processo p da swappare, quello con il massimo valore di swappedOutTime.
Successivamente, calcola la memoria richiesta dal processo s = memSize(p) è verifica se il sistema può soddisfare tale richiesta, attraverso la funzione CanAllocateInStore(s).
Se la condizione è vera si chiama la sottomacchina SwapProcessIntoStore(p, s), che swappa il processo in memoria.
Altrimenti si cerca un candidato in memoria di dimensione s per lo swapOut, se è presente si fa lo swapIn del processo p.

DiskSwap =
if nextProcessToSwapIn ≠ undef then
let p = nextProcessToSwapIn // p proc. per swap in
let s = memSize(p) // determina memory size di p
if CanAllocateInStore(s) then // posso allocare p in mem.?
Trigger(SwapProcessIntoStore(p, s)) // si, faccio lo swapIn
else
let cand = swapOutCandidate(s) //no, prendo proc. per swap out
if cand ≠ undef then //se c'è un candidato
Trigger(SwapProcessOut(cand, start, size)) //faccio lo swapOut di cand
step
SwapProcessIn(p, s) // e faccio lo swapIn del proc.p

where
nextProcessToSwapIn = // il proc. In disco conpermanenza massima
p(swappedOutTime(p) = max{swappedOutTime(q) | status(q) = swappedout})

swapOutCandidate(s) = //proc. Da più tempo in mem. Condimensione maggiore di s
p ∈UserProcess with status(p) = ready memSize(p) ≥ s

residencyTime = max{residencyTime(q) |
q ∈ UserProcess and status(p) ≠ swappedout}

CanAllocateInStore(s) = forsome h ∈ holes s ≤ size(h)


4.2 Storage Management Background
Il Gestore del disco fa l'assunsione che la memoria principale è composta da una sequenza di unita primarie di immagazzinamento(Primary Storage Units, es.byte o parole), mem:PSU*, e che ogni pocesso p occupa ne una sotto sequenza contigua(regione di memoria).
La memoria mem(p) associata al processo p è la sotto sequenza compresa tra memStart(p), l'indirizzo base di p e memSize(p), la dimensione. Quindi la regione di memoria di p è :
[mem(memStart(p)), . . . ,mem(memStart(p) + memSize(p) − 1)]

L'intera memoria è partiziona in regioni occupate da processi. Le restanti sottosequenze di memoria non allocate hai processi sono chiamati buchi(holes). La funzione CanAllocateInStore(s) cerca un buco di dimenzione almeno s.
CanAllocateInStore(s) = forsome ∈ holes s ≤ size(h)

Quando viene chiamato SwapProcessIntoStore(p, s) siamo sicuri che c'è un
hole che soddisfa la dimensione s richiesta dal processo p.
Viene assegnato l'indirizzo di partenza del processo in corrispondenza del
hole AllocateFromHole(s), il quale restituisce il buco h sufficiente a contenere s.
Successivamente si invia la richiesta allo swap disk driver ExecSwapDiskDriver e si mette in attesa dell'esito. Infine, il processo swappato viene messo in coda pronti MakeReady(p) e i suoi
attributi aggiornati .
SwapProcessIntoStore(p, s) =
let h = AllocateFromHole(s) in memStart(p) := start(h) //x ind. Base del proc p
step
RequestSwapIn(p, memStart(p)) //invia richiesta di swapIn al ExecSwapDiskDriver
step
swapDiskDriver_donesema.Wait //attesa esito
step
Delete(p, SwappedOut) // processo non più in disco
status(p) := ready // cambia lo stato in ready
UpdateRelocationReg // aggiornamento registri
residencyTime(p) := 0 //inizializza attributi
swappedOutTime(p) := 0
MakeReady(p) //inserisce coda pronti

RequestSwapIn scrive nel buffer swapReqBuffer la richiesta di swapIn passando come parametro il processo da swappare e il suo indirizzo base in memoria.
Successivamente si sveglia disk driver ExecSwapDiskDriver-
RequestSwapIn(p, loadpt) =
swapDiskMsg_sema.Wait //stato iniziale in attesa
step
swapReqBuff := SWAPIN(< p, loadpt >) //scrive sul buffer la richiesta
step
swapDiskMsg_sema.Signal //sveglia ExecSwapDiskDriver
Wake(swapDiskDriver)

La regola AllocateFromHole, protetto dalla coppia LOCK ed UNLOCK, sceglie un hole che soddisfa la richiesta di dimensione s. Associa tale regione al processo p ed infine calcella hole(buco) scelto dalla collezioni di holes.
AllocateFromHole(s) =
Lock
seq
choose h ∈ holes with s ≤ size(h) //si sceglie un hole che soddisfa la richiesta
Insert((start(h), s), usermem) /*il nuovo segmento di mem. viene aggiunta alla collezione di mem. riservata ai proc. Utente*/
result:= (start(h), s) // restituisce la coppia(ind.base,dim.)
Delete(h, holes) //elimino h dalla collezione holes
if size(h) − s > 0 then //se il buco è più di s
Insert((start(h) + s, size(h) − s), holes) //se ne crea un'altro con differenza
seq
UnLock

Visto che il processo padre condivide il codice con i processi figli, di conseguenza quando il processo padre è salvato nel disco(swapout), i figli perdono il riferimento al codice del padre, quindi dovranno passare in uno stato di attesa.
SwapProcessOut(p, st, sz ) = // p proc., ind. St,dimensione sz
SwapProcessOutOfStore(p, st, sz ) // swapOut processo p
step
if children(p)≠Ø and IsCodeOwner(p) then //se ha figli con codice condiviso
BlockProcessDescendants(p) //mette in attesa i figli di p

where
BlockProcessDescendants(p) =
forall q ∈ child⁺(p) //per ogni figlio q del processo p;
Insert(q, blockswaiting(p)) //si inserisce nell'insieme discendenti bloccati di p
status(q) := waiting //stato impostato in attesa
MakeUnready(q) //e rimosso dalla lista pronti

SwapProcessOutOfStore(p, st, sz ) esegue la computazione inversa di SwapProcessIntoStore(p, sz ). La regola RequestSwapOut fa richiesta, per mezzo di un buffer, al processo driver swap disk,il cui compito è quello di gestisce il trasferimento mem-disco e viceversa, che la regione p deve essere 'swappata' in discola regione di memoria che era occupata dal processo p viene aggiunta nella collezioni di buchi(holes)
Gli attributi del processo swappato nel disco vengono aggiornati e il processo viene messo stato di attesa(non pronto)
SwapProcessOutOfStore(p, st, sz ) =
RequestSwapOut(p, st, st + sz ) // invia richiesta di swapOut al ExecSwapDiskDriver
step
swapDiskDriver_donesema.Wait // attesa esito
step
Insert(p, SwappedOut) // processo in disco
status(p) := swappedOut // cambio lo stato
residencyTime(p) := 0 //inizializza attributi
swappedOutTime(p) := 0
FreeMainStore(st, sz ) // libera la memoria che era occupata da p
MakeUnready(p) // rimuovo processo dalla coda pronti

La sottomacchina MakeUnready estrae il processo r, passato come parametro, dalla relativa lista pronti.
MakeUnready(r) =
let q = readyq(schedlev(r)) //q è la coda relativa a r
if q ≠[] then //q non è vuota
if r = head(readyq)then //se è il processo corrente
Delete(r , q) //elimina dalla lista q
seq
ReSchedule // manda un nuovo proc. In esecuzione
else
Delete(r , q) //altrimenti elimina dalla lista q

La regola FreeMainStore elimina la regione passata come parametro, ed unifica buchi adiacenti.
FreeMainStore(region) =
Lock
seq
FreeMainStoreBlock(region) //elimina regione dalla mem.
seq
MergeAdjacentHoles //unifica holes adiacenti
seq
UnLock

where
FreeMainStoreBlock(region) =
Delete(region, usermem) //elimina region dalla memoria associata all'utente
Insert(region, holes) //e la inserisce nella colleizone di holes

MergeAdjacentHoles =
forall h1, h2 ∈ holes //per ogni coppia di buchi adiacenti
if start(h1) + size(h1) = start(h2) then
Delete(h1, holes) //li elimino dalla collezione di holes
Delete(h2, holes) //e ne aggiungo uno dato dalla somma h1+h2
Insert((min{start(h1), start(h2)}, size(h1) + size(h2)), holes)

RequestSwapOut è la funzione simile di RequestSwapIn. Cambia solo il valore inserito nel buffer
RequestSwapOut(p, s, e) =
swapDiskMsg_sema.Wait //stato iniziale in attesa
step
swapReqBuff := SWAPOUT(< p, s, e >) //scrive sul buffer la richiesta
step
swapDiskMsg_sema.Signal
Wake(swapDiskDriver) //sveglia ExecSwapDiskDriver

Nel caso in cui un processo padre entra in swap(swapin, in memoria principale), i fogli devono essere svegliati e messi in stato di pronto.
SwapProcessIn(p, s) =
SwapProcessIntoStore(p, s) // swapIn processo p dim. s
step
if children(p)≠Ø and IsCodeOwner(p) then //se p ha figli con codice condiviso
ReadyProcessDescendants(p) //sveglia i figli di p

where
ReadyProcessDescendants(p) =
forall q ∈ blockswaiting(p)//per ogni discendente q di p in attesa;
Delete(q, blockswaiting) //si elimina dall'insieme dei discendenti bloccati di p
status(q) := ready //stato impostato in pronto
MakeReady(q) //q aggiunto in lista pronti

Il processo relativo alla gestione delle fasi di swap(swap disk driver), è definita dalla macchina ExecSwapDiskDriver che compie le seguenti azioni: Se nel buffer è presente una richiesta pendente, viene processata da una sottomacchina HandleRequest, che a secondo del tipo di richiesta effettua operazioni di : swapin, wapout,elimina e crea un nuovo processo.
ExecSwapDiskDriver =
let rq= Read(swapReqBuff)
if rq ≠ NullSwap then //se il buffer delle richieste non è vuoto
HandleRequest(rq)// processa la richiesta
swapDiskDriver donesema.Signal //e sveglia chi era in attesa su questo sem.
PutToSleep(swapDiskDriver) //torna in Wait

where
HandleRequest(rq) =
case swapReqBuff of
SwapOut(p, start, end) → dmem(p) := [mem(start), . . . ,mem(end)]
SwapIn(p, ldpt) → forall ldpt ≤ ldpt + memSize(dmem(pdo) do mem(i):= dmem(p)(i)
DelProc(p) → dmem(p) := undef
NewProc(p, img) → dmem(p) := img

dmem = memoria del disco
mem = memoria principale
Le regole di lettura(READ) e scrittura(WRITE) usano il semaforo swapDiskMsg_sema per la sincronizzazione tra il swap disk process e il swapper process.
Write(rq) =
swapDiskMsg_sema.Wait
step
swapReqBuff := rq //scrive rq nel buffer delle richieste
step
swapDiskMsg_sema.Signal

Read =
step
SwapDiskMsg_sema.Wait
step
result:= swapReqBuff //ritorna il buffer delle richieste
swapReqBuff := Nullswap
sstep
swapDiskMsg_sema.Signal

5 Lo Scheduler
La regola principale per le operazioni di scheduling è definita dalla ASM ScheduleNext già descritta in precedenza. In questo paragrafo viene mostrato il raffinamento della funzione
selectLowLevelScheduler , e le definizioni di SaveState e RestoreState..

5.1 SelectLowLevelScheduler
La funzione SelectLowLevelScheduler è utilizzata per selezionare un processo, rispetto alla priorità su tre code rispettivamente ai tre tipi di processi. I processi device hanno massima priorità e quelli user minima. Ogni coda è gestita tramite una politica FIFO(round robin scheduler), il raffinamento corrispondente per la gestione delle code in ASM è definita da:
Enqueue =InsertAtEnd and Dequeue = RemoveHead

readyq, logicamente è un unica lista, ma è definita come una locazione derivata dalla concatenazione delle tre readyq(i) per device(dispositivi), system(sistema) e user(utente) con i=1,2,3. La concatenazione è ordinata a secondo della priorità. La testa della lista
punta al processo con priorità più alta. readyq può essere definite nel seguente modo:
readyq = readyq(1).ready(2).readyq(3)

5.2 Definizione di SaveState e RestoreState.
La sotto macchina saveState è utilizzata per salvare lo stato della macchina. In dettaglio, salva l'ip,l'insieme dei registri,lo stack e la process status word nel descrittore del processo corrente presente nella tabella dei processi
SaveState =
if currp ≠ nullProcess then
ip(currp) := ip
regs(currp) := regs
stack(currp) := stack
statwd(currp) := statwd

RestoreState esegue l'operazione inversa, cioè ripristina lo stato del processo caricando i valori dal descrittore di processo in tabella dei processi al nuovo processo in esecuzione
RestoreState =
if currp ≠ idleProcess then
ip := ip(currp)
regs := regs(currp)
stack := stack(currp)
statwd := statwd(currp)

6 Semaphores and Lock/Unlock Mechanism
semacount, è un semaforo con contatore. Il contatore rappresenta il numero di processi che simultaneamente vogliono accedere ad una sezione critica. SIGNAL incrementa il contatore di 1 e WAIT lo sottrae 1. Se il contatore prende valori negativi significa che c'è già un processo in sezione critica., quindi nel caso di WAIT il processo corrente sarà inserito nella coda di attesa del semaforo salvando lo stato e viene eseguito un'altro processo.
Wait =
Lock
seq
let newcount = semacount − 1 //decrementa contatore
semacount := newcount
if newcount < 0 then // se contaore negativo
Enqueue(currp, waiters) // inserisce nella coda del semaforo currp
status(currp) := waiting // e lo stato passa in attesa
SaveState(currp) // e si commuta contesto
MakeUnready(currp) seq ReSchedule
seq
UnLock

SIGNAL aggiunge uno al contatore. Se il contatore è ancora negativo vuol dire che c'è almeno un processo in coda d'attesa del semaforo; di conseguenza il processo in attesa viene messo in esecuzione.
Signal =
Lock
seq
let newcount = semacount + 1 //decrementa contatore
semacount := newcount
if newcount ≤ 0 then // se contaore non è positivo
let cand = head(waiters) //prendo il primo processo in coda
status(cand) := ready // e lo sveglio, và in stato di pronto
MakeReady(cand) //viene inserito in lista pronti
Delete(cand, waiters) //eliminato dalla coda del sem.
seq
UnLock

Si usano le macro:

• Wake(device) = device_sema.Signal
• PutToSleep(device) = device_sema.Wait
  

per le operazioni di SIGNAL E WAIT su un semaforo legato ad un device.

Daniele Licari

MINIX: Il livello più basso

Il file mpx88.s fa parte dello strato più basso del kernel MINIX. In esso sono descritte ed implementate in assembly tutte le operazioni che consentono di cambiare lo stato di un processo(processing switching) e di gestire lo scambio di messaggi (message handling).

Questo file è utilizzato ogni qual volta si fà riferimento al kernel.
Es. per l’ invio e/o ricezione di messaggi e per la gestione delle interruzioni/trap.
Nei casi di eccezioni hardware, quali TRAP o interruzioni, prima di eseguire il relativo gestore viene chiamata la procedura save() per salvare lo stato della macchina nella tabella dei processi. Successivamente si passa a lavorare sullo stack del kernel e finalmente viene eseguita la reale trap o chiamato il reale gestore di interruzioni scritto in codice C. Al ritorno della chiamata di procedura relativa ai gestori, il numero di processo o task contenuto in ‘cur_proc’ viene messo in esecuzione.
I punti d’ingresso(entry points) definiti in questo file sono:

• minix: inizializza lo stack del kernel e chiama la procedura main(scritta in C )
• s_call: per un processo o task che vuole inviare o ricevere un messaggio
• tty_int: routine d’interruzioni per ogni tasto pressato e rilasciato
• lpr_int: routine d’interruzioni per ogni linea di stampata
• disk_int: routine d’interruzioni per il disco
• wini_int: routine d’interruzioni per Winchester
• clock_int: routine d’interruzioni per il clock (Hz)
• surprise : per altri interrupt(inaspettati)
• trp: per tutte le trap(esclusa trap su divisione)
• divide: per le trap del tipo divide overflow
• restart: per l’inizio dell’ esecuzione di un task o un processo

Queste entry point vengono chiamate prima di eseguire la relativa procedura in C

MINIX
L’entry point per il kernel MINIX setta il DS e l’ SS del kernel all’indirizzo 4 e lo stack pointer sp del kernel viene inizializzato al valore #K_STACK_BYTES(256); infine viene chiamata la procedura main. Tutte queste operazioni vengono chiamate ad interruzioni disabilitate.
Ricordiamo che:

• DS : Data Segment è l’area che contiene i dati del programma
• CS : Code Segment è l’area di memoria che contiene le istruzioni(il testo) del programma
• SS : Stack Segment è l’area di memoria relativa allo stack del programma
• ES: Extra Segment è l’area di memoria per le informazioni extra relative al programma

|*===========================================================================* |* MINIX * |*===========================================================================* MINIX: | this is the entry point for the MINIX kernel.
jmp M.0 | skip over the next few bytes
M.0: cli | disable interrupts
…
mov ax,4 | build has loaded this word with ds value
mov ds,ax | ds now contains proper value
mov ss,ax | ss now contains proper value
mov _scan_code,bx | save scan code for '=' key from bootstrap
mov sp,#_k_stack | set sp to point to the top of the
add sp,#K_STACK_BYTES | kernel stack
call _main | start the main program of MINIX


System Call
Questo entry point inserisce i parametri della funzione sys_call(function, caller, src_dest, m_ptr) nella stack del kernel prima della vera chiamata in codice C.
Al ritorno della procedura per la chiamata di sistema viene mandato un task o un processo in esecuzione(viene chiamata la procedura restart)
I parametri della sys_call vengono recuperati accendendo alla posizione della tabella dei processi relativa al processo o task in esecuzione.


|*===========================================================================* |* s_call * |*===========================================================================* _s_call: | System calls are vectored here.
call save | save the machine state
mov bp,_proc_ptr | use bp to access sys call parameters
push 2(bp) | push(pointer to user message) (was bx)
push (bp) | push(src/dest) (was ax)
push _cur_proc |push caller
push 4(bp) | push(SEND/RECEIVE/BOTH) (was cx)
call _sys_call | sys_call(function, caller, src_dest, m_ptr)
jmp _restart | jump to code to restart proc/task running


Interruzioni e trap.
l’entry point per :

• interruzione da tastiera(tty_int) :
• interruzione stampa di una linea(lpr_int)
• una trap(trp)
• una trap di divisione(divide ,es. divisione per 0)
• altre interruzioni inaspettate(surprise)

si salva lo stato della macchina , si chiama il relativo gestore e si continua l’esecuzione


Es. routine per interruzione d'input da terminale
|*===========================================================================* |* tty_int * |*===========================================================================* _tty_int: | Interrupt routine for terminal input.
call save | save the machine state
call _keyboard | process a keyboard interrupt
jmp _restart | continue execution


I punti di ingresso alla chiamata delle routine di interruzione per :

• il floppy disk
• winchester disk
• clock

hanno un comportamento analogo; per chiamare la funzione interrupt(definita in codice C,proc.c) vengono copiati i parametri nello stack del kernel.

Es. Nella routine di interruzione per il floppy disk viene costruito il messaggio di interruzione da inviare; successivamente viene inpilato nello stack insieme all’argomento FLOPPY che identifica il destinatario.
Infine viene chiamata la funzione interrupt.
In questo caso gli argomenti passati alla funzione sono FLOPPY, &intmess.
Se la routine chiamata fosse stata di clock o winchester, i parametri passati alla funzione interrupt sarebbero rispettivamente [CLOCK, &intmess] o [WINI, &intmess]

|*===========================================================================* |* disk_int * |*===========================================================================* _disk_int: | Interrupt routine for the floppy disk.
call save | save the machine state
mov _int_mess+2,*DISKINT| build message for disk task
mov ax,#_int_mess | prepare to call interrupt(FLOPPY, &intmess)
push ax | push second parameter
mov ax,*FLOPPY | prepare to push first parameter
push ax | push first parameter
call _interrupt | this is the call
jmp _restart | continue execution



idle
l’entry point idle fa attesa attiva aspettando un interruzione
idle: | executed when there is no work
sti | enable interrupts
L3: wait | just idle while waiting for interrupt
jmp L3 | loop until interrupt


Save
Questo è il punto di ingresso utilizzato per salvare lo stato del sistema, quindi le informazioni relative al processo in esecuzione, nella tabella dei processi.
Nel dettaglio, vengono recuperati dallo stack del programma attualmente in esecuzione i valori della program status word (psw), del segmento del codice(cs) e il program counter(pc) e salvati nella tabella dei processi.
Successivamente si salvano i registri relativi al processo, che in ordine di inserimento sono : sp,es,bp,di,si,dx,cx,bx,ax.
La procedura termina con un salto all’indirizzo del chiamante(indirizzo di ritorno della save)

Nota: _proc_ptr ritorna la posizione(indirizzo) nella tabella dei processi del processo in esecuzione.

|*===========================================================================* |* save * |*===========================================================================* save: | save the machine state in the proc table
. ..
pop ds_save | stack: psw/cs/pc/ret addr
pop ret_save | stack: psw/cs/pc
mov bx_save,bx | save bx for later ; we need a free register
mov bx,_proc_ptr | start save set up; make bx point to save area
add bx,*OFF | bx points to place to store cs
pop PC-OFF(bx) | store pc in proc table
pop csreg-OFF(bx) | store cs in proc table
pop PSW-OFF(bx) | store psw
mov ssreg-OFF(bx),ss | store ss
…
push ds_save | start saving all the registers, sp first
push es | save es between sp and bp
mov es,bx | es now references kernel memory too
push bp | save bp
push di | save di
push si | save si
push dx | save dx
push cx | save cx
push bx_save | save original bx
push ax | all registers now saved
…
mov ax,ret_save | ax = address to return to
jmp (ax) | return to caller; Note: sp points to saved ax

Restart
Complementare a Save, questo entry point inizializza ed esegue un processo o un task.
Se il sistema è attivo, i valori psw, cs, sp e dei registri del processo da mandare in esecuzione, contenuti nella tabella dei processi, vengono ripristinati inserendoli nello stack.

|*===========================================================================* |* restart * |*===========================================================================* _restart: | This routine sets up and runs a proc or task.
cmp _cur_proc,#IDLE | restart user; if cur_proc = IDLE, go idle je idle | no user is runnable, jump to idle routine
cli | disable interrupts
mov sp,_proc_ptr | return to user, fetch regs from proc table
pop ax | start restoring registers
pop bx | restore bx
pop cx | restore cx
pop dx | restore dx
pop si | restore si
pop di | restore di
mov lds_low,bx | lds_low contains bx
mov bx,sp | bx points to saved bp register
mov bp,SPLIM-ROFF(bx) | splimit = p_splimit
mov splimit,bp | ditto
mov bp,dsreg-ROFF(bx) | bp = ds
mov lds_low+2,bp | lds_low+2 contains ds
pop bp | restore bp
pop es | restore es
mov sp,SP-ROFF(bx) | restore sp
mov ss,ssreg-ROFF(bx) | restore ss using the value of ds push PSW-ROFF(bx) | push psw
push csreg-ROFF(bx) | push cs
push PC-ROFF(bx) | push pc
lds bx,lds_low | restore ds and bx in one fell swoop
iret | return to user or task


le costanti utilizzate in mpx88.s e contenute in com.h sono:
K_STACK_BYTES = 256 | dimensione kernel stack
WINI = -6 |identificativo per task che si occupa del wininchester disk
FLOPPY = -5 |identificativo per il task floppy disk
CLOCK = -3 | identificativo per il task clock
IDLE = -999 | costante che identifica sistema inattivo
DISKINT = 1 | per identicare il tipo del mess. di interruzione disk
CLOCK_TICK = 2 | per identicare il tipo del mess. di interruzione clock

MINIX: I processi

Il file proc.c contiene tutte le principali operazioni compiute dai processi e per la gestione dei messaggi. La comunicazione tra processi,in MINIX, è effettuata attraverso lo scambio di messaggi, utilizzando delle procedure chiamate send e receive.

Le procedure che descriverò, contenute nel file proc.c cono:

• system call : chiamata quando un processo o task vogliono eseguire una SEND e/o RECIVE
• interrupt : utilizzato dalla routine delle interruzioni per inviare il messaggio di interrupt ad un task
• ready: prende un processo della lista pronti e lo mette in esecuzione
• unready: rimuove il processo dalla lista pronti
• sched: se un processo è da tanto tempo in esecuzione, ne viene schedulato un altro
• pick_proc: porta un processo in esecuzione
• send: invia un messaggio tra pocessi
• receive: per la ricezione di messaggi tra pocessi
  

interrupt

Quando occorre una interruzione viene chiamata la funzione interrupt, la quale prova ad inviare un messaggio di interruzione al task con identificatore passato come argomento
PUBLIC interrupt(task, m_ptr)
int task; /* number of task to be started */
message *m_ptr; /* interrupt message to send to the task */
{/* An interrupt has occurred. Schedule the task that handles it. */

il messaggio di interruzione ha come sorgente la costante che identifica l'hardware, definita nel file com.h,il destinatario ed il puntatore al buffer del messaggio
if (mini_send(HARDWARE, task, m_ptr) != OK) {
/* The message could not be sent to the task; it was not waiting. */

Se l'invio del messaggio di interruzione fallisce, (es. non era in attesa di riceverlo), si setta nella bitmap busy_map per ricordarsi cheil task destinatario è occupato e si salva il riferimento al messaggio di interruzione nel vettore message *task_mess[NR_TASKS+1] (contiene i puntatori ai messaggi dei task occupati).

Nel caso in cui la send è stata eseguita con successo, quindi l'interruzione hardware è stata inviata correttamente, si resetta a zero il bit nella busy_map per identificare che il task è di nuovo libero.
busy_map &= ~this_bit; /* turn off the bit in case it was on */
old_map = busy_map;

Se vi è qualche altro task che ha un interruzione pendente, allora la richiesta viene soddisfatta inviandogli il messaggio di interruzione ed si aggiorna la bitmap relativa ai task occupati
if (old_map != 0) {
for (i = 2; i <= NR_TASKS; i++) {
/* Check each task looking for one with a pending interrupt. */
if ( (old_map>>i) & 1) {/* Task 'i' has a pending interrupt. */
n = mini_send(HARDWARE, -i, task_mess[i]);
if (n == OK) busy_map &= ~(1 << i);

Infine, si controlla se la lista pronti relativa ai taks non è vuota e se c'è
una processo utente in esecuzione, allora porto il task in esecuzione
/* If a task has just been readied and a user is running, run the task. */
if (rdy_head[TASK_Q] != NIL_PROC && (cur_proc >= 0 || cur_proc == IDLE))
pick_proc();

System Call

Solo le system call posso eseguire le procedure send e/o receive, per l'invio e/o ricezione dei messaggi.
Tali chiamate sono eseguite quando viene fatta una trap al kernel con una istruzione INT.
La trap viene catturata e chiamate le procedure send e/o receive .

le System Call prendono come parametri:

• il tipo di funzione da eseguire
• il chiamante, identifica il processo che ha chiamato la sys_call.
• l'identificatore del processo mittente(in caso di receive) e/o destinatario(in caso di send) del messaggio
• il puntatore al messaggio

PUBLIC sys_call(function, caller, src_dest, m_ptr)
int function; /* SEND, RECEIVE, or BOTH */
int caller; /* who is making this call */
int src_dest; /* source to receive from or dest to send to */
message *m_ptr; /* pointer to message */

Le uniche chiamate di sistema consentite ai processi utente sono dove sono presenti sia la send che la receive, altrimenti nel registro per il codice di ritorno da system call del processo chiamante verrà assegnato un codice di errore.
if (function != BOTH && caller >= LOW_USER) {
rp->p_reg[RET_REG] = E_NO_PERM; /* users only do BOTH */
return;}

Negli altri casi si limita ha chiamare le procedure send e/o receive a secondo dei casi
if (function & SEND)
n = mini_send(caller, src_dest, m_ptr); /* func = SEND or BOTH */
if (function & RECEIVE)
n = mini_rec(caller, src_dest, m_ptr); /* func = RECEIVE or BOTH */

Send

La procedura send è utilizzata per inviare un messaggio tra due processi.
Se il destinatario è in attesa di questa comunicazione il messaggio viene copiato nell'area di memoria della parte DATI del processo destinatario ed in seguito ne viene fatta la sveglia.

Nel caso contrario, se il destinatario non è in attesa di ricevere o è in attesa di ricevere da un altro processo, il mittente(il chiamante della send) passa in attesa ed il messaggio viene messo in coda.
In minix i processi utente posso inviare solo al File System ed al processo
gestore della memoria.

I parametri sono:

• identificatore processo mittente(il chiamante),
  
• identificatore processo destinatario
  
• il puntatore al messaggio da recapitare.
  

PUBLIC int mini_send(caller, dest, m_ptr)
int caller; /* who is trying to send a message? */
int dest; /* to whom is message being sent? */
message *m_ptr; /* pointer to message buffer */

Dagli identificatori, passati come argomento alla procedura, si accede alla tabella dei processi e si recuperano gli indirizzi del processo chiamante e del processo destinatario.

Vengono fatti controlli di validazione per verificare se il destinatario è ancora in vita e se l'intero messaggio può essere contenuto nel segmento DATI dell'aera di memoria del
processo chiamante('caller')
if (dest_ptr->p_flags & P_SLOT_FREE)
return(E_BAD_DEST); /*dead dest */
if (vhi < vlo || vhi - caller_ptr->p_map[D].mem_vir >= len)
return(E_BAD_ADDR);

Se il destinatario era bloccato in attesa di questo messaggio viene chiamata la routine
cp_mess[src, src_clicks, src_offset, dst_clicks, dst_offset] che esegue una copia veloce di un messaggio da una parte ad un altro qualsiasi indirizzo di memoria e svegliato il destinatario,se il processo diventa runnable(dest_ptr->p_flags == 0) viene inserito nella propria lista pronti(ready).
N.B.Dopo la sveglia il destinatario si troverà il messaggio nella sua memoria DATI.
/* Check to see if 'dest' is blocked waiting for this message. */
if ( (dest_ptr->p_flags & RECEIVING) &&
(dest_ptr->p_getfrom == ANY || dest_ptr->p_getfrom == caller) ) {
/* Destination is indeed waiting for this message. */
cp_mess(caller, caller_ptr->p_map[D].mem_phys, m_ptr,
dest_ptr->p_map[D].mem_phys,
dest_ptr->p_messbuf);
dest_ptr->p_flags &= ~RECEIVING; /* deblock destination */
if (dest_ptr->p_flags == 0) ready(dest_ptr);
}

cp_mess è implementata direttamente in assembly,contenuta nel file klib88.asm, durante il trasferimento copia l'identificatore del processo mittente nella prima parole del messaggio
In tal modo il processo destinatario potra ricavare l'indirizzo del processo accedendo alla tabella dei processi.
le restanti 11 parole del messaggio vengono copiate contenuto dall'area DATI del mittente al 'area DATI del destinatari.
Un messaggio è composto da 12 parole.Ricordiamo che in minix una parola è composta da 16-bit(2byte), di conseguenza l'intero messaggio consta di 24byte
;===========================================================================
; cp_mess
;===========================================================================
Msize = 12 ; size of a message in 16-bit words
cp_mess:
...
mov es:[di],ax ; copy sender's process number to dest message
...
mov cx,Msize-1 ; remember, first word doesn't count
rep movsw ; iterate cx times to copy the message
...

ret ; that's all folks!

Nella situazione in cui il destinatario non è in attesa di ricevere la comunicazione viene salvato il puntatore al messaggio ed attraverso la procedura unready il caller passa in stato di attesa per invio non riuscito
/* Destination is not waiting. Block and queue caller. */
if (caller == HARDWARE) return(E_OVERRUN);
caller_ptr->p_messbuf = m_ptr;
caller_ptr->p_flags |= SENDING;
unready(caller_ptr);

Infine il puntatore al processo mittente(caller) viene inserito nella lista dei processi che hanno comunicazioni pendenti

Receive

E' la procedura complementare alla Send; utilizzata quando un processo o task vuole ricevere un messaggio.
In questo caso i parametri sono:

• identificatore processo che vuole ricevere(il chiamante),
• identificatore processo del mittente atteso
• il puntatore al buffer per il messaggio
  

PRIVATE int mini_rec(caller, src, m_ptr)
int caller; /*process trying to get message */
int src; /* which message source is wanted (or ANY) */
message *m_ptr; /* pointer to message buffer */

Se la coda dei processi che hanno provato ad inviare un messaggio al chiamante non è vuota , (bloccati perché il destinatario non era in attesa del messaggio), si cerca un mittente con il messaggio desiderato (ANY, prende il primo messaggio presente in coda).
Tale messaggio viene acquisisce attraverso cp_mess (descritta in precedenza), che fa la copia dalla memoria fisica dell'area dati del processo sender alla memoria fisica della parte dati del processo destinatario.
Dopo la copia si sblocca il mittente, attraverso la procedura ready che inserisce il descrittore di processo mittente nella opportuna lista pronti, di conseguenza viene aggiornata la coda dei processi delle comunicazione pendenti con il chiamante, eliminando il processo mittente utilizzato per la receive.
caller_ptr = proc_addr(caller);/* pointer to caller's proc structure */
/* Check to see if a message from desired source is already available. */
sender_ptr = caller_ptr->p_callerq;
while (sender_ptr != NIL_PROC) {
sender = sender_ptr - proc - NR_TASKS;
if (src == ANY || src == sender) {
/* An acceptable message has been found. */
cp_mess(sender, sender_ptr->p_map[D].mem_phys, sender_ptr->p_messbuf,
caller_ptr->p_map[D].mem_phys, m_ptr);
sender_ptr->p_flags &= ~SENDING; /* deblock sender */
if (sender_ptr->p_flags == 0) ready(sender_ptr);

Se il messaggio richiesto non è ancora disponibile, si salva lo stato della comicazione e si blocca il chiamante.
caller_ptr->p_getfrom = src;
caller_ptr->p_messbuf = m_ptr;
caller_ptr->p_flags |= RECEIVING;
unready(caller_ptr);

Infine si verifica se ci sono segnali pendenti da parte del kernel al processo gestore memoria, quindi viene chiamata la procedura assembly inform(MM_PROC_NR) per informare il gestore
if (sig_procs > 0 && caller == MM_PROC_NR && src == ANY) inform(MM_PROC_NR);

pick_proc

Questa funzione è utilizzata principalmente per settare 'cur_proc' e 'proc_ptr',rispettivamente l'identificatore al processo corrente e il puntatore alla tabella dei processi
Se il sistema è inattivo 'cur_proc' e 'proc_ptr' vengono settati ad un valore speciale IDLE, per identificare lo stato di inattività.
Per impostare il processo corrente controlla se è presente un processo nelle liste pronti, in ordine di priorità, verifica : quella dei task, dei processi server e di quelli utente.
register int q; /* which queue to use */
if (rdy_head[TASK_Q] != NIL_PROC) q = TASK_Q;
else if (rdy_head[SERVER_Q] != NIL_PROC) q = SERVER_Q;
else q = USER_Q;
if (rdy_head[q] != NIL_PROC) {
/* Someone is runnable. */
cur_proc = rdy_head[q] - proc - NR_TASKS;
proc_ptr = rdy_head[q];

Se è in esecuzione il task per il controllo del ciclo di clock, 'cur_proc' = CLOCKTASK.
Viene settato anche il puntatore al processo bill_ptr che conta i cicli di clock della CPU.

ready

La ready inserisce il puntatore al processo(al descrittore di processo), passato come argomento, alla propria lista pronti ricavandola dall'identificatore del processo.
PUBLIC ready(rp)
lock(); /* disable interrupts */
r = (rp - proc) - NR_TASKS; /* task or proc number */
q = (r < 0 ? TASK_Q : r < LOW_USER ? SERVER_Q : USER_Q);
...
// aggiunge rp in rdy_head[q]
..
restore(); /* restore interrupts to previous state */

Tutte le operazioni vengono effettuate ad interruzioni disabilitate, chiamanto la procedura lock definita a livello assembler e alla fine viene chiamata la procura assembly restore ripristinare le interruzioni allo stato precedente.
In tal modo siamo sicuri queste operazioni vengono eseguite in maniera indivisibile, senza essere interrotte da interruzioni.
Il codice assembly delle per le operazioni lock e restore sono presenti nel file klib88.asm
;===========================================================================
; lock
;===========================================================================
; Disable CPU interrupts.
lock:
pushf ; save flags on stack
cli ; disable interrupts
pop lockvar ; save flags for possible restoration later
ret ; return to caller

;===========================================================================
; restore
;===========================================================================
; Restore enable/disable bit to the value it had before last lock.
restore:
push lockvar ; push flags as they were before previous lock
popf ; restore flags
ret ; return to caller

unready

Rimuove il processo ,il cui puntatore è passato come parametro, dalla sua lista pronti.
Il codice è simile alla ready, ma in questo caso viene fatta la rimozione anzichè l'inserzione dalla lista rdy_head[q].
Un processo può essere in stato unready anche se un segnale di kill l'ha terminato.
Anche in questa procedura su utilizza la lock e restore per le stesse motivazioni della procedura descritta in precedenza

sched

Descrive la politica di scheduling per i processi utente. Se un processo è da troppo tempo in esecuzione ed un altro è presente in lista pronti. Il processo corrente viene inserito in fondo alla lista pronti utente.
La procedura viene eseguita ad interruzioni disabilitae
PUBLIC sched(){
lock(); /* disable interrupts */
if (rdy_head[USER_Q] == NIL_PROC) {
restore(); /* restore interrupts to previous state */
return;
}/* One or more user processes queued. */
rdy_tail[USER_Q]->p_nextready = rdy_head[USER_Q];
rdy_tail[USER_Q] = rdy_head[USER_Q];
rdy_head[USER_Q] = rdy_head[USER_Q]->p_nextready;
rdy_tail[USER_Q]->p_nextready = NIL_PROC;
pick_proc();
restore(); /* restore interrupts to previous state */

Per capire meglio uso che i processi fanno delle primitive di comunicazione mi rifaccio al classio esempio di un processo 'APPL' che vuole leggere dal disco; 'DRIVER' è il processo gestore del disco con il quale altri processi attraverso opportune send e/o receive
Nel compilato del processo APPL ci sarà il riferimento alle procedure di comunicazione che il kernel minix mette a disposizione.

Es. In pseudocodice,nel compilato dei processi, avremo:
APPL:
...
send(driver,“LETTURA N parole”)
recieve(driver,risultato)
...

DRIVER:
...
recieve(appl,“LETTURA N parole ”)
send(appl,letti())
...

Il prossimo post su minix descriverò file mpx88.asm che contiene lo strato più basso del kernel Minix, sono quasi 300 righe di codice assembly utilizzare per implementare lo switching dei processi, gestione dei messaggi, la procedura save() che contiene il codice per salvare lo stato della macchina quando occorre una Trap o un' Int,etc

Daniele Licari