:: Sistemi Operativi - Lezione del 21 aprile 2008 ::
Torna alla pagina di Sistemi Operativi
Tecniche di allocazione dei frame
Come decidere di allocare i frame? Senza fare riferimenti ai segmenti, ma parlando solo di pagine, vediamo un po' quante pagine dare ad un processo.
Da notare, che anche se do TUTTA la memoria fisica ad un processo, non è detto che non avrò pagefault, per il semplice motivo che se lo spazio di indirizzamento del processo è superiore alla memoria installata, ovviamente non ci starà:)
Quindi, al solito occorre trovare la risposta giusta ad una domanda: quanti frame allocare ad un processo?
Dobbiamo tenere presente alcuni vincoli, prima di decidere i numeri. Uno di questi deriva dall'architettura del computer, che riguarda anche le dimensioni dele pagine: si tratta del vincolo di numero minimo di frames da attribuire ad un processo.
Perché dipende dall'architettura? Il motivo è che i processori hanno delle istruzioni che permettono di specificare degli indirizzi. Se qualcuno si ricorda i gloriosi tempi dell' LC-2, ricorderà anche che:
Queste robe sono dette livelli di indirezione. Se un'architettura di CPU prevede 2 livelli di indirezione, vuol dire che per arrivare ad 1 dato mi occorrono 3 accessi: 1 per leggere l'istruzione, 2 per arrivare alla cella che contiene l'indirizzo, 3 per pescare il valore effettivo nell'indirizzo finalmente recuperato. Questo vuol dire che nel peggiore dei casi mi servono 3 frames diversi: ecco spiegato il numero minimo di frames.
Poi, devo tenere conto anche della condivisione
fi = numero di frames allocati al processo Pi fj = numero di frame utlizzati dal gruppo di processi Gj d = frame disponibili Σifi - Σjfj <= d
Il gruppo di processi è composto da processi che condividono dei frame, per i motivi che abbiamo visto nelle pagine precedenti.
Ho due strategie per andare a prendere i frame da allocare:
Ogni processo ha la stessa quantità di frame di ogni altro processo correntemente in memoria
m = numero totale di frame n = numero di processi fi = frame del processo Pi fi = m /n
In questo modello, anche il SO ha lo stesso numero di frame dei processi normali. Al massimo pretenderà un trattamento migliore.
Più ho processi in memoria, meno pagine posso dare al singolo processo. Ciò vuol dire che c'è un limite alla multiprogrammazione. Allo stesso tempo, se ho pochi processi in memoria, ne ho al converso tanti nello spazio di swap che non avanzano pur magari potendolo fare.
L'idea sarebbe allora di tenere in memoria i processi ready e quelli che presumo lo saranno a breve. Come fare ciò, è un mistero...
Consideriamo questi due casi:
L'allocazione omogenea tratterebbe molto male questi processi. Per migliorarla, si è pensato di allocare tanti frame quanto più un processo è grosso:
si = dimensione dello spazio virtuale occupato dal processo Pi fi = m * Si / Σisi
Finora, ho trattato tutti i processi come se fossero uguali dal punto di vista del processore. Però, ho scenari in cui i processi hanno priorità diverse, e sembra allora giusto poter dar loro più frame così che perdano meno tempo a caricare roba dal disco.
Ecco perché parla di allocazione proporzionale alla priorità.
fi = m * pi / Σipi
Ocio: questa formula è scritta con il presupposto che p alto = priorità alta. Non sempre è così (eg Unix).
Generalizzando, posso decidere di allocare in modo proporzionale a qualsiasi parametro che più mi garba.
Lezione 4 - Thrashing
Se un processo ha poche pagine in memoria, passa più tempo a caricare e scambiarle col disco fisso che nemmeno a progredire. Questo è ciò che si dice thrashing, ovvero paginazione della spazzatura.
Le cause del thrashing sono l'elevata multiprogrammazione, e il fatto che lo scheduler a lungo termine introduca in memoria molti processi per tenere occupato il processore.
Per evitare il thrashing, devo avere:
Per ottenere il secondo punto, serve una allocazione locale. Un processo ha un numero minimo di frame, sotto al quale non deve scendere. Quando devo scegliere la vittima, la scelgo tra i frame dello stesso processo che ne ha bisogno, così che i suoi bisogni non vadano a thrashare gli altri processi: al massimo ci smena soltanto lui, piuttosto che l'intero sistema.
I programmi hanno una piacevole caratteristica, detto principio di località di esecuzione.
Questa proprietà mi dice che, nell'intorno di un certo istante di tempo, un processo accederà tipicamente solo a certe zone del suo spazio di indirizzamento, e non ad altre. Poi, dopo un po' cambierà zone, poi ancora etc., ma in ognuna di queste diverse configurazioni ci passerà un po' di tempo.
Come è possibile sta magia? È possibile per via di come sono scritti i programmi. Se uso tecniche di buona programmazione, e ancor meglio se uso linguaggi di alto livello, tendenzialmente scriverò codice raggruppato in moduli, che il compilatore ed il linker metteranno in zone attigue della memoria.
Se riesco a sfruttare questo principio, riduco il numero di page fault. Ma come, visto che non ho nessuna sfera di cristallo? Posso approssimare con 2 tecniche:
Nella mia stringa di riferimento, definisco una finestra di dimensione Δ, che contiene quindi un certo numero di pagine precedenti a quella in cui mi trovo in un dato istante. Questo insieme di pagine nella finestra Δ è detto appunto working set, cioè insieme di lavoro.
Man mano che procedo nella stringa di riferimento, il WS si sposta, e i frame che stanno prima della finestra sono passibili di scalzamento.
La formuletta magica è
fi = maxt (wsi(t))
Più Δ è grande, più frame un processo ha in memoria, meno pagefault ho.
Se invece capita che
Σk fk > m
dove m è il numero di pagine disponibili, allora scelgo una vittima e la scarico.
Il brutto è che devo avere una stringa di riferimento per poter usare il WS, e la stringa non ce l'ho finché non è un po' che eseguo il programma...
Se ho poche miss, sto usando troppe pagine per il processo.
Se ho poche pagine, posso rischiare il thrashing.
Allora, in medio stat virtus, e cerco di far sì che ogni processo si mantenga ad un certo livello di frequenza di page fault, così da evitare le due situazioni estreme.
I processi ricchi di pagine vengono depauperati, quelli poveri arricchiti. Esattamente come faceva Robin Hood.
Lezione 5 - Ottimizzazione delle prestazioni
Sceglo prima quali pagine caricare, prevedendo magicamente quali pagine il processo utilizzerà. Il problema è che non ho in anticipo la stringa di riferimento.
Un processo, comunque, ha la sua frequenza massima di page fault quando viene avviato (perché non ha ancora caricato niente) e quando viene riattivato, perché deve riguadagnarsi lo spazio.
Almeno nel secondo caso, quando riattivo un processo, carico anche tutto il WS precedente, così da cercare di ottimizzare un po' l'uso delle pagine.
La dimensione della pagina ideale dipende da alcuni fattori.
Se ho pagine grandi, ho queste conseguenze:
Se ho invece pagine piccole:
Vedi le lezioni precedenti per sapere che cosa è.
Anche per questa, vedi le lezioni precedenti
È quello che dicevamo prima, con l'aggiunta che le strutture dati usate influenzano la "resa" del programma.
Infatti, se devo accedere ad una matrice per righe, è meglio salvare per righe, così è più facile che ci stia una riga in una pagina. Se salvassi per colonne, potrei invece dover saltare di pagina in pagina per ogni colonna.
I buffer dei dispositivi I/O li lascio in memoria, marcandoli come residenti. Il motivo è questo: quando un processo aspetta dati provenienti da una periferica, tipicamente avrà una sua zona di memoria destinata a riceverli. Le I/O ci mettono un po' di tempo: se PRIMA che arrivino quei dati, quella pagina che dovrebbe contenerli è stata swappata, succede un macello.
Le soluzioni sono le seguenti:
La prima soluzione è poco conveniente, perché pur evitando il problema impone una copia successiva dei dati dalla memoria del SO alla memoria del processo. Quindi, si usa la seconda soluzione.
Così non perdono tempo a caricare dal disco. Abbiamo visto prima che il tempo di accesso alla memoria, nel caso della memoria virtuale, dipende dalla probabilità. Ma un SO real time vuole tempi certi, non probabilistici. Ecco perché memoria virtuale e real time vanno d'accordo come Denis e lo Svizzero.
:: I/O ::
Struttura e funzioni dei sottosistemi I/O
Posso dividere i sottosistemi di I/O in base a diverse caratteristiche.
La velocità influenza anche come sarà trattato il processo che ne farà uso: quanto resterà bloccato in I/O, e quindi quando sarà schedulato.
Lo scopo è quello di avere un'interfaccia software omogenea, che è facile da gestire per il programmatore, in quanto standardizzata.
Dovrei avere una visione omogenea di tutte le periferiche, a prescindere dal tipo di periferica, e dal modello di periferica.
Per ottenere questo, devo strutturare il software di gestione in questo modo:
e questi tre strati sono uno sopra l'altro: lo strato sopra vede solo quello che lo strato sotto gli dice di vedere, e non altro.
Lo strato device independent driver mostra tutte le periferiche allo stesso modo, senza distinguere tra schede video, modem, webcam o quello che è.
Lo strato device dependent driver mostra tutte le periferiche dello stesso tipo allo stesso modo, senza differenze di modelli etc. Ad esempio, tutte le schede video, indipendentemente da chi le fa, vanno "esibite" allo stesso modo.
Il gestore del canale di comunicazione deve nascondere le modalità specifiche di gestione del canale di comunicazione. Robe come mappatura in memoria, attesa attiva, interruzione e DMA devono scomparire alla vista del programmatore.
Tutte le periferiche dello stesso tipo devono essere viste come uguali, soprattutto nel modo di essere comandate, e nel modo di gestione degli errori.
Tutte le periferiche vanno trattate allo stesso modo, sia che esse utilizzino buffer, cache, spooling, che vedremo qui sotto.
Realizzazione sottosistema I/O
Il sottosistema I/O è quella parte del kernel che si occupa di gestire l'I/O, e fa quindi da ponte tra l'utente del SO e l'hardware sottostante.
Ogni periferica ha la sua coda, e va gestita secondo le politiche che più ci aggradano per ottimizzarne l'uso.
Posso dover adottare la bufferizzazione in due casi:
Nel primo caso, ho ad esempio una periferica lente, a fronte di un processo che spara fuori tanti dati in un secondo. Il buffer serve per ammortizzare questa differenza: il SO mette a disposizione un'area di memoria (che rimane sempre del SO) sulla quale il processo scriverà.
Il processo non deve sapere se sta scrivendo realmente sulla periferica o sul buffer: deve solo poter scrivere, e avere magari il vantaggio di non bloccarsi anche se la periferica è più lenta di lui.
Questo però si basa sul presupposto che prima o poi il processo si fermerà, nella sua opera di creazione di dati da inviare alla periferica, altrimenti non c'è buffer che tenga: non posso infatti farlo crescere all'infinito...
Il secondo caso, quello della differenza tra dimensioni dei blocchi, si ha per esempio quando ho un terminale a caratteri, ma un processo che invia blocchi di dati. Ci deve pensare il SO, e NON il programmatore, a prendere ogni singolo carattere del blocco e ad inviarlo al terminale.
Una cosa da tenere a mente è che il buffer è come se fosse la periferica, dal punto di vista del processo. Se scrivo un certo dato in un certo punto, invio le istruzioni relative a quest'operazione al buffer. Se poi, mentre queste istruzioni sono ancora nel buffer in attesa di essere eseguite, invio altri comandi sullo STESSO dato, il buffer deve fregarsene: scrive quello che gli è arrivato primo, per primo, il resto poi.
Questa faccenda, ovvero il processo che scrive sul buffer senza saperlo, e così dal suo punto di vista la I/O è durata poco, si chiama semantica della copia.
Conservo una copia dei dati letti di recente da una periferica per riuso rapido.
Soprattutto se ho periferiche lente, il primo accesso sarà lento. Ma il secondo sarà rapido perché userà la cache, se sfruttata bene, e quindi in media guadagno in tempo di accesso.
Se ho periferiche molto lente e/o condivise, posso usare questa tecnica per supplire.
Un processo che utilizzasse una di queste periferiche potrebbe ritrovarsi bloccato per molto tempo in attesa del suo turno. Pensiamo alla stampante: devo aspettare che il processo che è arrivato prima di me termini la sua stampa prima del mio turno.
Serve ancora un buffer, ma date le dimensioni dei dati in ballo - diversi mega -, il buffer lo si realizza non in memoria centrale, ma in memoria di massa.
C'è una cartella in cui ogni processo scrivente scriverà un file, marchiato con un time stamp.
C'è poi 1 solo processo che può accedere effettivamente alla periferica, ed è detto spooler. Esso prenderà i file scritti nella cartella in ordine di tempo, e pian piano li manda alla periferica. Il fatto che siano marchiati col tempo garantisce la mutua esclusione.
Gli altri processi non accedono mai direttamente alla periferica, ma passano sempre attraverso il controllo dello spooler. E hanno anche il vantaggio di non venire rallentati dalla periferica lenta.
Per usare una periferica in modo esclusivo. Per pietà non fatemi ripetere niente sull'argomento lock!:)
Gli errori si possono catalogare in due tipi:
Se un guasto è transitorio, deve pensarci il driver a "riprovare" più tardi. Nell'altro caso, non c'è SO che tenga.
Il processo ha, nella sua PCB, la lista dei files/periferiche da lui aperte. Esse sono indicate da un descrittore.
All'interno del SO, ogni descrittore rappresenta una periferica o un file, e il SO ha la tabella di tutti i files/periferiche aperti nel sistema.
All'interno di questa tabella, ogni file/periferica ha un puntatore alle routine che lo devono gestire, così da permettere un rapido accesso alle funzioni di gestione.
L'I/O è quella parte del computer che più ne influenza le prestazioni.
Per migliorarle, dovrei