Sistemi Operativi - Lezione del 21 aprile 2008

 :: 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.

• Poche pagine = tanti probabili page fault
• Tante pagine = meno pagefault, e tempo di accesso medio inferiore

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?

Vincoli

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:

• posso specificare un'indirizzo direttamente
• posso specificare un'indirizzo di una cella la quale contiene l'indirizzo che voglio
• etc.

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:

1. globale = tutti i frame liberi sono a disposizione di qualsiasi processo
2. locale = un processo ha a disposizione un tot di frame e basta

Allocazione omogenea

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...

Allocazione proporzionale alla dimensione

Consideriamo questi due casi:

• programmi con tanti dati = accedono a strutture dati ciccione, e quindi spantegate in diverse pagine
• programmi con codice ampio = hanno routine qua e là per tutto lo spazio di indirizzamento

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

Allocazione proporzionale alla priorità

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:

• una politica di schedulazione che eviti il thrashing, cioè che limiti la multiprogrammazione arrivati ad una certa soglia
• una politica di allocazione dei frame che riduca il numero dei frame che possono essere tolti dalla memoria

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.

Prevenzione del thrashing

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:

• il working set
• la page-fault frequency

Working Set

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...

Page fault frequency

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

Prepaginazione

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.

Dimensione della pagina

La dimensione della pagina ideale dipende da alcuni fattori.

Se ho pagine grandi, ho queste conseguenze:

• uso meno pagine => tabella piccola
• frammentazione interna (pagine poco sfruttate) e spreco di memoria
• tempi di s/caricamento minore
• minore risoluzione (il programma è spezzettato in un minor numero di pagine)
• possibili più page fault, perché carico roba per meno processi in memoria, avendo le pagine grosse.

Se ho invece pagine piccole:

• più pagine
• tabella più grossa
• minore frammentazione interna e meno spreco
• più tempo per s/caricamento (tempo totale, perché lo faccio più volte)
• più località
• più risoluzione
• possibile minor numero di page fault

TLB

Vedi le lezioni precedenti per sapere che cosa è.

Tabella invertita delle pagine

Anche per questa, vedi le lezioni precedenti

Strutturazione del programma

È 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.

Pagine residenti per dispositivi di I/O

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:

• usare solo la memoria del SO per le operazioni I/O
• impedire di swappare le pagine destinate all'I/O

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.

Pagine residenti per processi in tempo reale

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.

Direzione dell'I/O

• sola lettura
• sola scrittura
• lettura e scrittura

Condivisione

• periferica dedicata
• periferica condivisibile

Metodo di accesso

• sequenziale
• diretto (in inglese random, non perché sia casuale, ma semplicemente perché un dato accesso è in linea teorica slegato dagli accessi precedenti e da quelli futuri)

Modo di trasferimento dei dati

• a carattere
• a blocchi

Schedulazione del trasferimento

• sincrono
• asincrono

Velocità del dispositivo

• latenza
• tempo di ricerca
• tempo di trasferimento
• ritardo tra le operazioni

La velocità influenza anche come sarà trattato il processo che ne farà uso: quanto resterà bloccato in I/O, e quindi quando sarà schedulato.

Software di gestione delle periferiche

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:

• gestione del canale di comunicazione
• device dependent driver
• device independent driver

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.

Gestione del canale di comunicazione

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.

Device Dependent Driver

Tutte le periferiche dello stesso tipo devono essere viste come uguali, soprattutto nel modo di essere comandate, e nel modo di gestione degli errori.

Device Independent Driver

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.

Schedulazione richieste I/O

Ogni periferica ha la sua coda, e va gestita secondo le politiche che più ci aggradano per ottimizzarne l'uso.

Bufferizzazione

Posso dover adottare la bufferizzazione in due casi:

• le velocità della sorgente e della destinazione non coincidono
• le dimensioni dei blocchi della sorgente e della destinazione non coincidono
• ottenere la semantica della copia

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.

Caching

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.

Spooling

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.

Locking

Per usare una periferica in modo esclusivo. Per pietà non fatemi ripetere niente sull'argomento lock!:)

Gestione degli errori

Gli errori si possono catalogare in due tipi:

• guasti permanenti
• malfunzionamenti transitori

Se un guasto è transitorio, deve pensarci il driver a "riprovare" più tardi. Nell'altro caso, non c'è SO che tenga.

Strutture dati del kernel

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.

Prestazioni dell'I/O

L'I/O è quella parte del computer che più ne influenza le prestazioni.

Per migliorarle, dovrei

• ridurre i cambi di sistema
• ridurre la copia dei dati qua e là nella memoria
• ridurre la frequenza degli interrupt
• aumentare la concorrenza, così più processi evolvono
• gestire le periferiche a livello HW in modo decente
• equilibrare il tutto

Torna alla pagina di Sistemi Operativi