Il context switching si compone di tre fasi fondamentali. La prima fase ri-guarda il salvataggio dello stato della CPU nella PCB del processo in esecuzione. La seconda fase riguarda l'esecuzione di un algoritmo per la scelta del succes-sivo programma da eseguire e la terza fase comporta il caricamento della PCB del programma scelto nelle risorse della CPU, ovvero il ripristino dello stato del processo scelto.
2.4 Booting, shell e sistema dinamico
In qualsiasi macchina sica munita di sistema operativo, la fase di inizializzazione del sistema viene denominata fase di booting. Il programma di Bios, risiedente in una memoria programmabile separata, si occupa innanzitutto di veri care i dispositivi hardware collegati al computer, ed in seguito carica in memoria prin-cipale il primo blocco di byte della memoria secondaria. Quest'area di memoria è in genere occupata dalla prima routine eseguita dal sistema operativo, la routine di boot, mediante la quale vengono caricate in memoria principale altre routine di sistema no a raggiungere una mappatura della memoria ottimale. Il primo programma caricato in memoria, se si esclude il kernel stesso, è il programma che realizzata l'interfaccia tra l'utente e il sistema operativo: la shell. La shell mette a disposizione una serie di comandi che permettono all'utente di creare processi, eseguire operazioni sui le e interagire con i dispositivi di input ed output. Si capisce dunque, che il sistema operativo alloca le risorse (tabella delle pagine, strutture PCB) in maniera dinamica a seconda delle esigenze dell'utente e del carico stesso dei programmi mandati in esecuzione. La possibilità di accedere alla memoria secondaria implica il vantaggio di poter gestire page fault in lettura e swapping dei processi, garantendo grossi carichi di lavoro. Nel capitolo 4 si vedrà come questo concetto di sistema dinamico dovrà necessariamente venire sosti-tuito da un sistema statico. L'impossibilità di simulare i dispositivi di memoria secondaria, nonché il le system, introduce una pesante limitazione sullo sviluppo e sulle funzionalità del sistema operativo.
Capitolo 3
SimCPU - implementazione
hardware
Il primo capitolo riporta le direttive fondamentali per orientarsi in maniera quasi completamente autonoma all'interno del codice del simulatore didattico mentre le generalità sul funzionamento dei sistemi operativi individuate nel capitolo pre-cedente, ha permesso di comprendere a grandi linee quali siano eettivamente le modi che da apportare all'architettura. In questo capitolo verrà esaminata dapprima una versione evoluta di SimCPU, derivata dal merging eettuato dal codice sviluppato in due diversi lavori di tesi che, in maniera indipendente e scorrelata l'uno dall'altro avevano operato modi che sulla versione didattica di SimCPU. Le competenze acquisite nel capitolo 2, sono in ne necessarie e su -cienti a comprendere il perché di determinate modi che hardware adottate nei due progetti.
3.1 Macrostruttura di SimCPU - versione base evoluta
Con riferimento alla relativa sezione del capitolo 2 che descrive la necessità di introdurre un dispositivo hardware per la traduzione da indirizzi virtuali ad indi-rizzi sici (MMU), si voleva richiamare in questa sede il fatto che l'introduzione del sistema della memoria virtuale era dovuto alla restrizione imposta sulla gran-dezza della memoria sica, che essendo limitata, non permetteva la presenza di interi programmi in memoria.
In realtà, il problema relativo a SimCPU è del tutto opposto ma l'implemen-tazione della paginazione e della memoria virtuale giova comunque al sistema. Essendo SimCPU una macchina con un parallelismo di 16 bit, la memoria in-dirizzabile è pari a 65536B (216) e dunque anche la memoria sica presentava il medesimo numero di locazioni. Tuttavia, la necessità di sviluppare un sistema operativo che garantisse l'esecuzione di più programmi presenti contemporanea-mente in memoria, ha determinato come conseguenza un ampliamento della me-moria sica che è andata oltre la capacità di indirizzamento della macchina (che
nel frattempo ha mantenuto inalterato il suo grado di parallelismo). La macchina dunque non è più in grado di accedere ad ogni locazione della memoria ma deve avvalersi di un sistema di supporto sia hardware che software che comunichino e operino l'interfacciamento richiesto, altrimenti irrealizzabile.
Le principali modi che introdotte in questo senso, dunque, hanno riguardato l'introduzione della MMU per la gestione mediante paginazione di una memoria sica non più a 64kB, ma estesa no ad 1MB (nonostante il limite architetturale di una macchina a 32bit sia di 232 locazioni di memoria). Allo stesso tempo è stato introdotto il ag di kernel ed una serie di registri speciali demandati a speci ci scopi come ad esempio la memorizzazione dell'indirizzo base della tabella delle pagine del sistema operativo e dell'ultimo programma utente in esecuzione. Inoltre, prima di ogni instruction fetch, è stato aggiunto il cosiddetto interrupt test per la gestione delle interruzioni da dispositivi hardware esterni. Questi concetti verranno analizzati meglio nelle prossime sottosezioni.
3.1.1 Registri speciali, ag e istruzioni kernel
Il primo passo verso l'implementazione del sistema operativo è stato l'introduzione del ag di kernel il quale discrimina tra due diversi stati di funzionamento della CPU. Il sistema operativo è formato da codice che espleta la funzione di garantire l'esecuzione di più programmi utenti che devono coesistere all'interno della stessa memoria sica. Per ovviare a comportamenti maliziosi dei programmi utente e proteggere l'intero sistema è necessario introdurre due modalità dierenti di esecuzione delle istruzioni da parte della CPU, la modalità utente e la modalità kernel. In particolare, le istruzioni più sensibili verranno precluse ai programmi utente mentre potranno essere utilizzate solamente quando viene eseguito codice di sistema operativo (o kernel per l'appunto).
A tutti gli eetti, il sistema operativo si comporta come un programma spe-ciale che regola il funzionamento di altri programmi. Come i programmi utente, il sistema operativo possiede una sua tabella delle pagine (che si vedrà essere me-morizzata nel sul spazio di indirizzamento assieme a quelle dei programmi utente) il cui indirizzo base è sso e viene memorizzato all'interno di un registro speciale. Un altro registro speciale viene dedicato alla memorizzazione dell'indirizzo base della tabella delle pagine del programma utente in esecuzione.
L'introduzione del sistema di paginazione, ha reso necessario dunque l'introdu-zione di una certa quantità di registri speciali nei quali memorizzare dati sensibili e importanti (KTB - Kernel Base Table Address \ UTB - User Base Table Ad-dress). Tra i ag aggiunti, si ricordano, oltre al ag di kernel_mode, quelli che abilitano o disabilitano il sistema di paginazione, l'attività della TLB (Transla-tion Lookaside Buer) e il ag di interruzione. Il ag di interruzione, come verrà visto in seguito, è soltanto un ag ttizio in quanto l'eettivo test della presenza o meno della necessità di servire un interruzione avviene sulla linea di interruzione stessa, e non sul ag.
L'introduzione del kernel_mode e dei registri speciali, ha reso possibile imple-mentare delle protezioni per istruzioni particolarmente sensibili dell'Instruction
3.1. MACROSTRUTTURA DI SIMCPU - VERSIONE BASE EVOLUTA 23
Set. In particolare, in sede di discussione sui registri speciali, si fa riferimento a due nuove istruzioni protette introdotte per eseguire operazioni sui registri spe-ciali da e verso registri di ALU. Le nuove istruzioni sono denominate SSR (Set Special Register) e LSR (Load Special Register).
3.1.2 MMU e paginazione
La MMU è il dispositivo hardware che gestisce la traduzione tra indirizzi virtuali ed indirizzi sici. Di fatti, come appena accennato, la necessità di sviluppare un sistema operativo che provvedesse a gestire la schedulazione di vari programmi presenti contemporaneamente in memoria sica, ha comportato la necessità di un ampliamento della stessa, che dai normali 64kB indirizzabili mediante i consueti 16 bit, è stata portata a circa 1MB, indirizzabili mediante 20bit. Tuttavia, il parallelismo della CPU è rimasto a 16bit: la CPU da sola non può teoricamente coprire/accedere a tutte le locazioni di memoria. La MMU è adibita proprio a garantire un interfacciamento corretto tra memoria indirizzabile e memoria sica mediante l'opportuna traduzione tra indirizzo virtuale e indirizzo sico. Il metodo che viene sfruttato nel nostro caso è quello che viene denominato sistema di paginazione.
La paginazione nel caso di SimCPU ha un duplice scopo, da un lato è un metodo di gestione della memoria che permette che lo spazio degli indirizzi -sici assegnati ad un processo non sia contiguo tra di loro, dall'altro permette il superamento dell'ostacolo causato dall'ampliamento della memoria sica oltre lo spazio di memoria indirizzabile da una macchina con un parallelismo ridotto.
Il principio di funzionamento della paginazione e il ruolo svolto dalla MMU nell'implementazione base evoluta di SimCPU saranno qui di seguito descritti a grandi linee. Per un approfondimento maggiore sull'argomento si rimanda a testi più speci ci, nonché alla consultazione della tesi di riferimento, che svolge un'analisi dettagliata di ogni riga di codice modi cata o introdotta nel sorgente del simulatore.
Il dispositivo hardware simulato è caratterizzato dalla presenza di un ulterio-re livello di memoria, costituito dalla TLB (Translation Lookaside Buer), una specie di cache nei confronti della tabella delle pagine. In virtù del principio di lo-calità spaziale e temporale, l'introduzione di un ulteriore livello di memoria tra il processore e la memoria principale dove risiede la tabella delle pagine comporta in realtà un aumento ragguardevole delle prestazioni in termini di tempo. La MMU, infatti, andrà a cercare la pagina prima all'interno della TLB, e qualora non la trovasse, all'interno della tabella delle pagine in memoria principale. Tuttavia, è altamente probabile che i successivi accessi in memoria facciano riferimento sem-pre la stessa pagina che a questo punto si troverà nella TLB: l'accesso in memoria principale, che è lento in confronto all'accesso alla TLB, sarà quindi evitato.
Vengono ora raccolte le speci che tecniche sulle quali le modi che si sono basate:
• PARALLELISMO CPU: 16bit - 64kB
• PARALLELISMO MEMORIA FISICA: 20bit - 1MB • INDIRIZZO FISICO: 32bit - 4B
• DIMENSIONE PAGINE\FRAME: 256B
• NUMERO MASSIMO DI PAGINE PER PROGRAMMA: 256
• DESCRITTORE DI PAGINA: 4B - 3B più signi cativi di indirizzo - 1B per ag di controllo
• DIMENSIONE TABELLA DELLE PAGINE: 1024B • ELEMENTI NELLA TLB: 4
Prima di passare a descrivere il principio grossolano di funzionamento della tradu-zione degli indirizzi, è opportuno descrivere la struttura della tabella delle pagine. La tabella delle pagine, una per ogni processo in esecuzione, è memorizzata a par-tire da una determinata locazione scelta dal sistema operativo. L'indirizzo base della tabella delle pagine del programma utente in esecuzione, è posto nel relati-vo registro speciale. La tabella delle pagine è dunque un'area di memoria nella quale, in maniera consecutiva, vengono memorizzate delle informazioni inerenti ogni pagina del segmento. Queste informazioni vengono denominate descrittori di tabella e sono formati da 4B. I primi 3B (quelli più signi cativi) contengono l'indirizzo sico della pagina a cui fanno riferimento, mentre l'ultimo byte median-te l'attribuzione di un signi cato ad ogni suo bit, è adibito a funzioni di controllo della pagina stessa (tra le quali informazioni di protezione e presenza/assenza della pagina in memoria principale). Per puntare all'inizio del descrittore di ta-bella della pagina N-esima, è necessario sommare all'indirizzo base della tata-bella delle pagine, il numero N moltiplicato per 4, ovvero i byte di ogni descrittore. Una tabella delle pagine occupa dunque un totale di 256(pagine)*4B(lunghezza descrittore)=1024B.
Il principio di funzionamento è il seguente (sia disabilitato il ag di activi-ty_TLB mentre sia abilitato il ag di paginazione): si supponga che in esecuzio-ne ci sia un programma utente (il ag di keresecuzio-nel è impostato a zero). Qualsiasi referenziamento in memoria, compreso quello necessario al fetch dell'istruzione necessita ovviamente di una traduzione da indirizzo virtuale ad indirizzo sico. Come appena speci cato, il numero di pagine in cui è suddiviso il segmento del programma utente è 256, dunque, se si prende in considerazione il fatto che l'indi-rizzo virtuale è a 16 bit, allora i primi 8 bit (byte più signi cativo) rappresentano il numero di pagina, mentre, il byte meno signi cativo rappresenta l'oset all'in-terno della pagina. A questo punto viene prelevato il numero della pagina nella quale è contenuto l'indirizzo che si vuole tradurre e con questo elemento, unito all'indirizzo base della tabella delle pagine presente nel registro speciale UTB, si individua l'indirizzo in memoria del descrittore di pagina che si sta cercando. Da questo si prelevano i 3B più signi cativi dell'indirizzo sico e vi si accoda l'oset
3.1. MACROSTRUTTURA DI SIMCPU - VERSIONE BASE EVOLUTA 25
(ovvero il byte meno signi cativo dell'indirizzo virtuale) pervenendo all'indirizzo sico nale.
Il byte meno signi cativo del descrittore di tabella, tra le altre cose, prevede un bit di presenza della pagina in memoria sica. Qualora quest'ultimo indichi l'assenza della pagina, avviene il cosiddetto PAGE FAULT, fenomeno che deve venire correttamente gestito dal sistema operativo caricando in memoria princi-pale la pagina prelevata dalla memoria secondaria (PAGE FAULT in lettura) o attribuendo al programma un ulteriore frame libero (PAGE FAULT in scrittura). Con la TLB attivata, ciò che cambia è sostanzialmente il fatto che la ricerca del descrittore di pagina associato ad una determinata pagina viene eettuata in primo luogo all'interno della TLB. Qualora non vi fosse presente allora si provvede con la sostituzione di un elemento della TLB (il più vecchio) con quello nuovo e successivamente la traduzione viene ripresa normalmente.
3.1.3 Return Address
Nella versione didattica di SimCPU, ogni istruzione di CALL, eseguiva via hard-ware un Push nello stack del program counter incrementato di due unità. La relativa istruzione di RET realizzava, sempre via hardware, un Pop del program counter, riprendendo l'esecuzione del programma chiamante dall'istruzione suc-cessiva a quella di CALL (in quanto il program counter inserito nello stack era stato precedentemente incrementato di due). Una siatta gestione della chiamata e del relativo ritorno richiedeva sempre almeno due accessi in memoria principale dovuti al push e al pop del program counter.
Nella versione base evoluta di SimCPU, uno dei registri della ALU (R14) è stato demandato ad assolvere al ruolo di Return Address. Il sistema di chiamata di funzioni, in questa versione, non prevede più il push e il pop del program counter, ma le istruzioni CALL e RET si limitano rispettivamente a salvare in RA (Return Address - Indirizzo di ritorno) il valore del program counter incrementato di due, e a ripristinare il valore del program counter con il dato contenuto nel Return Address, evitando dunque i due accessi in memoria dovuti alle push e alle pop. Per quanto riguarda chiamate singole il vantaggio è evidente, soprattutto se si considera che l'accesso in memoria principale richiede molto tempo, in confronto ad una operazione realizzata con i registri. Tuttavia, il sistema mostra dei limiti quando vengono eseguite delle chiamate a funzione foglia (una CALL dentro una CALL). In questi casi, se non si provvedesse a salvare nello stack di sistema il registro RA, quest'ultimo, verrebbe sovrascritto e inevitabilmente perduto con la CALL successiva.
3.1.4 Stack Pointer
Un'altra modi ca sostanziale è stata introdotta per ciò che concerne lo stack pointer. Nella versione didattica del simulatore lo stack pointer era un registro particolare della CPU al quale era possibile accedere solamente mediante opportu-ne istruzioni che permettevano di settaropportu-ne il valore. In maniera del tutto analoga
a quanto realizzato per il registro RA, è stato deciso di dedicare allo stack pointer un ulteriore registro di ALU (in particolare R15 - SP). Le operazioni istruzioni di PUSH e di POP operano ora su un registro della ALU e dunque ogni incre-mento (dovuto alle PUSH) e ogni decreincre-mento (dovuto alle POP), è nettamente più veloce in termini di tempistiche. Inoltre, il vantaggio di utilizzare un registro standard per lo stack pointer consiste nel poterlo manipolare con le istruzioni normali per allocare o rilasciare spazio sullo stack.
3.1.5 Interruzioni
Il sistema delle interruzioni è stato implementato con l'aggiunta di una nuova linea di segnale oltre ai bus di controllo e ai bus dati, la linea delle interruzioni. Inoltre, come già detto, prima di ogni instruction fetch, durante l'esecuzione di una istruzione, è stata aggiunta la fase di testing della linea di interruzione. Qualora tale linea sia stata impostata ad uno da un dispositivo hardware esterno, l'interruzione deve essere servita, il ag di kernel viene sollevato e l'hardware salta ad una locazione di memoria prede nita nella quale è presente la routine di gestione dell'interruzione. Nello speci co, questi aspetti verranno lungamente trattati nel corso di questo stesso capitolo.