Sistemi Operativi - Lezione del 5 maggio 2008

 :: Sistemi Operativi - Lezione del 5 maggio 2008 ::

Torna alla pagina di Sistemi Operativi

Lezione 4 - Realizzazione dei Files - Allocazione dei blocchi

Abbiamo visto che prediligiamo la tecnica del bytestream per realizzare i files. Ma i files sono composti da blocchi: con che criterio andiamo a scrivere questi blocchi sul disco? Ci sono diversi modi per allocare.

Allocazione contigua

Semplicemente, metto i blocchi relativi ad un file uno dietro l'altro. La directory contiene la lista dei files, con

• numero del blocco dove il tal file comincia
• lunghezza del file in blocchi

Sicuramente questo schema di allocazione ha il vantaggio che la lettura di un file intero è molto veloce, trattandosi di blocchi contigui: la testina non deve mai spostarsi dalla traccia in cui si trova.

Il problema è l'accesso diretto (ricerca di un determinato punto del file), che è un po' più lento perché devo partire dall'inizio del file.

Inoltre, i problemi più evidenti riguardano la frammentazione interna ed esterna, e la creazione dei files. Se per creare un file occorre spazio contiguo, è anche possibile non riuscire a trovarne: ci sono complessivamente tanti blocchi, ma tutti separati, e non posso usarli perché non contigui. È qui che deve entrare in campo quel simpatico processo chiamato deframmentazione, che cerca appunto di risolvere la frammentazione esterna.

La frammentazione interna invece riguarda il fatto che devo assegnare spazio vuoto ad un file (ma quanto?) perché forse nel futuro lo userà.

Per conoscere lo spazio libero nel sistema, leggo tutte le directory, faccio la somma dei blocchi liberi e ritorno il risultato. Ma siccome sto sistema sarebbe infinitamente lento, si usa anche una tabella esterna che tiene traccia del numero di blocchi liberi.

Allocazione collegata

Tolgo dalle mie pretese l'obbligo di avere blocchi fisicamente contigui. Tratto i singoli blocchi come elementi di una lista collegata, con ogni blocco che ha un puntatore al blocco successivo, mentre l'ultimo blocco contiene un indicatore di fine file.

Nella directory per ogni file memorizzo il 1° e l'ultimo blocco, così che si possano fare degli append rapidamente.

Il vantaggio principale è che elimino la frammentazione esterna, perché posso usare teoricamente tutti i blocchi, in qualsiasi posizione essi si trovino.

Ma il problema è l'accesso diretto: devo per forza partire dal primo blocco, va beh, ma poi devo seguire tutti i puntatori fino al punto che mi serve, e siccome la contiguità potrebbe non esserci, la testina potrebbe fare dei saltoni qua e là per il disco, che rallenterebbero la ricerca.

Un SO furbo cercherà di allocare i blocchi di un file il più contigui possibile, ovviamente, oppure usare il concetto di cluster.

Il cluster è un insieme di blocchi, e diventa lui l'unità minima di memorizzazione dei files. Un file riempie un cluster dietro l'altro, così almeno non si deve fare una nuova ricerca per ogni fine di blocco.

Il cluster serve anche per ovviare al problema seguente: se un blocco a metà file si danneggia, come faccio a sapere qual'è il blocco successivo, visto che solo il blocco danneggiato contiene un puntatore a quel blocco?

Se invece so che tutti i blocchi appartengono ad un cluster, male che vada perdo quel blocco, ma so che quello dopo appartiene ancora a quello stesso cluster.

Occorre anche tenere in considerazione che i blocchi di un cluster non hanno tutti la stessa dimensione, perché di solito il primo contiene i riferimenti per puntare al cluster che logicamente lo segue. Questo complica un poco i calcoli per la scelta del blocco in funzione del record logico.

File Allocation Table (FAT)

Si tratta sempre di allocazione collegata, ma stavolta si usa una tabella, che è esterna ai files, che viene memorizzata in blocchi noti a priori.

Questa tabella contiene la lista dei blocchi di un file: il nome del file porta ad una voce in tabella, che contiene il numero di un blocco e il numero del blocco successivo (cioè della voce in tabella che lo rappresenta).

In questo modo le ricerche avvengono in tabella e non in giro per il disco. Non c'è frammentazione esterna, ma se ho files grossi, la ricerca nella tabella può essere difficoltosa.

Allocazione indicizzata

Introduco il concetto di i-node, ovvero index node: ogni file ha il suo i-node, che è un blocco che contiene la sequenza dei blocchi che compongono quel file. Per trovare l'n-esimo blocco, quindi, cerco l'n-esima voce nella lista dell'i-node.

La contiguità qui è realizzata tramite l'i-node. Non c'è frammentazione esterna, l'accesso diretto è veloce anche se quello sequenziale un po' meno, ed è affidabile perché pur perdendo un blocco, il nodo mi sa dire qual'è quello successivo. E per evitare di perdere i nodi, ne tengo una copia.

Il problema che balza all'occhio qui è che se un file ha bisogno di più blocchi di quanti non possano essere listati in un nodo, allora quel file non può essere creati.

Ci sono quindi 3 sistemi diversi per superare questo ostacolo:

• blocco indice con schema collegato: l'ultima voce del nodo non porta ad un blocco ma ad un altro nodo. Semplice, ma se ho troppi nodi, le ricerche possono andare per le lunghe
• blocco indice con indice multi-livello: metto tutto quanto in un albero, così il tempo di ricerca non è O(n) ma O(logn)
• blocco indice con schema combinato: siccome a volte è inutile creare alberi per files piccoli, faccio una combo: un nodo ha un po' di entry che indicano direttamente blocchi (per files piccoli), altre entry che portano al primo livello dell'albero, e altre ancora che portano al terzo (ed eventualmente al quarto etc.). A seconda delle dimensioni del file, uso più o meno livelli.

Miglioramento delle prestazioni per le allocazioni

I sistemi sono fondamentalmente 2:

• fare il caching delle informazioni relative ai files
• read-ahead: leggo anticipatamente i blocchi, così che siano disponibili prima della richiesta. Il read-ahead è tanto più efficiente quanto più i blocchi sono fisicamente contigui.

Gestione dello spazio libero

Occorre anche trovare un modo per tener traccia dello spazio libero sul disco.

Vettore di bit

Uso una mappa dei blocchi, in cui 1 bit indica se quel blocco è in uso o meno (qui ci sono versioni discordanti: 1 = in uso, 0 = vuoto o viceversa? Va beh, non cambia niente).

Non importa da chi è stato usato quel blocco, ai fini dello spazio libero importa solo che non sia utilizzabile

Quando voglio salvare un file, devo trovare nella mappa lo spazio contiguo adatto a contenerlo, se so in anticipo le dimensioni. Per evitare di sprecare gli spazi contigui ampi, uso il più piccolo spazio contiguo che può contenere il file.

Questo approccio funziona bene se è gestito in hardware (?).

Lista collegata

Mantengo una lista collegata dei blocchi liberi. Si può usare una roba del genere coi diversi tipi di allocazione, perché in fondo è come se fosse un file particolare.

Il problema è che i gruppi di blocchi vuoti contigui non sono immediatamente riconoscibili: occorre scandire la lista e controllare blocco per blocco la contiguità.

Raggruppamento

Memorizzo l'indirizzo del primo blocco di una serie di blocchi contigui, e il numero di blocchi vuoti che lo seguono.

Tengo traccia di questa lista, che può anche essere separata dal resto del FS, e ad essa attingo durante le mie ricerche.

Lezione 5 - Valutazione dell'efficienza e delle prestazioni

Lezione un po' confusa...

L'efficienza riguarda l'uso delle risorse. Le prestazioni riguardano la velocità.

Efficienza

Per migliorare l'efficienza, devo tenere conto di vari parametri, come le dimensioni dei blocchi, dei puntatori ai blocchi e dei metadati. Questo mi può dire quanto spazio spreco per memorizzare tot dati.

La dimensione dei blocchi deve essere tale da ridurre le frammentazioni esterna ed interna, e ridurre lo spazio usato per la gestione internamente ad ogni blocco.

Per migliorarla, potrei usare dei cluster di dimensioni non uguali ma variabili a seconda delle dimensioni del file. La FAT, se uso quella, sarebbe più grossa, ma ridurrei gli sprechi.

Prestazioni

Per migliorare le prestazioni, oltre all'utilizzo della cache, dovrei usare algoritmi semplici e strutture dati a cui si possa accedere velocemente.

Un esempio di miglioramento delle prestazioni si ha quando metto in memoria centrale la tabella degli i-node, così che sia rapidamente accessibile.

Supporti hardware dedicati

• cache del disco in memoria centrale, ma anche direttamente sul disco (e che vuol dire?)
• cache delle pagine in memoria centrale

Vediamo di chiarire il discorso cache, che è piuttosto nebuloso.
I dischi fissi hanno al proprio interno una cache, ovviamente gestita in proprio: quando il SO vuole un blocco, se questo è in cache il disco gli dà quello ed evita di muovere la testina. Questa cache contiene interi settori.

Alcuni sistemi hanno la cache del disco, dove cachano i blocchi: se mi serve ancora, lo pesco dalla cache e non dal disco. Niente di nuovo.

Altri sistemi invece di cachare i blocchi, cachano le pagine: usano lo stesso gestore della memoria virtuale, ma invece di metterci le pagine dei processi, nei frames ci mettono i pezzi di blocco. Il libro sostiene che "memorizzare i dati del file tramite indirizzi virtuali è più efficiente che nemmeno memorizzarli con i blocchi fisici del disco". La sintassi di questa frase non lascia capire se:

• ricercare un pezzo di file tramite indirizzo virtuale è più veloce che nemmeno ricercarlo per numero di blocco
• utilizzare la memoria virtuale per fare questo mestiere è più veloce che usare una cache separata

A quanto pare, il paragrafo successivo ripete quanto detto qui sopra, chiamandolo memoria virtuale unificata.

Aggiunge poi la nota che Solaris invece usa due cache diverse: quella del blocco per cachare i metadati del filesystem, che sono gli i-node e le varie strutture dati del FS; poi usa anche la cache di pagina per i dati effettivi di ogni singolo file.

Il pezzo succcessivo lo interpreto così: c'è un modo che non abbiamo contemplato, riguardante l'apertura dei files: la mappatura in memoria. Vuol dire che per accedere ad un file, non specifico un blocco, bensì un indirizzo di memoria, e ci pensa poi il SO a capire che quell'indirizzo è stato mappato ad un file e non ad un indirizzo di memoria centrale. Un po' quello che succede con le periferiche I/O mappate in memoria.
Successivamente, occorre ricordarsi della semantica della copia, che mi diceva che le I/O vengono effettuate in un buffer per velocizzarle, e poi il buffer viene flushato asincronicamente sul disco.
Orbene: se uso contemporaneamente questi due sistemi, la prima cosa da notare è che il buffer viene prima di tutto il resto: ciò vuol dire che le mie I/O vengono prima fatte nel buffer, e poi il buffer viene flushato.
Ma qui sorge il problema: se flusho sul disco, ok, ma se flusho su un file mappato in memoria, vuol dire che i dati che escono dal buffer devono passare dalla cache della memoria virtuale, ed infine trasferiti sul disco. Ciò implica uno spreco di tempo, ed ha anche un nome proprio: double caching.
Per evitare ciò, si usa la buffer cache unificata, il che vuol dire che la memoria virtuale realizza tutto, sia i files mappati in memoria che la I/O bufferizzata.

Ad ogni modo, avere più di una cache vuol dire sincronizzarle tutte, e sincronizzare infine col disco. La cache, usata per mediare l'I/O, lo rende più efficiente, soprattutto se mi permette di schedulare bene le richieste, così da muovere il meno possibile la testina in giro per il disco.

Però, sopravviene il problema delle scritture asincrone: se un processo scrive qualcosa, e riceve il segnale di "TUTTO OK" quando la scrittura è terminata solo in memoria centrale ma non ancora sul disco, un guasto che accadesse immediatamente dopo avrebbe come conseguenza il fatto che sul disco non è stato scritto niente, anche se al processo risulta diversamente. Allora, in genere per i dati critici si usa la scrittura sincrona.

Poi, parlando della memoria virtuale unificata, compare il disco virtuale, gestito come un FS, ma risiedente direttamente in memoria centrale, con tutti i vantaggi (velocità) e svantaggi (se tolgo la corrente perdo tutto) del caso.

Lezione 6 - Manutenzione del FS

Ci possono essere errori nel FS, che non riguardano i dati, ma le strutture di gestione del FS stesso. Possono essere dovuti ad errori fisici nel disco, oppure ad errori di scrittura nel FS da parte del SO.

Il risultato è che il FS perde la sua coerenza: il controllore della coerenza è quello che fa il check del FS, per controllare che dati e metadati parlino della stessa roba.

Backup e ripristino

Il concetto di backup mi dice che posso poter accettare di perdere parte delle modifiche, pur di tornare ad uno stato coerente del FS.

L'idea è di creare, periodicamente, delle copie di backup del FS, quando esso è in uno stato consistente, cioè dati e metadati sono a posto.

Il backup completo consiste nel salvare ogni volta tutto quanto. Quello incrementale invece salva solo le modifiche relative all'ultimo backup completo.

Il ripristono (restore) avviene diversamente, nei due casi. Se ho il backup completo, prendo l'ultimo backup e lo copio. Nel caso di quello incrementale, prima copio l'ultimo backup completo, poi applico tutti i backup incrementali che trovo.

Le copie di backup devono comunque essere tenute anche fisicamente al sicuro.

Nei FS orientati alle transazioni, c'è un log delle transazioni come per le basi di dati, che permette di recuperare eventuali errori.

Nei FS con journaling c'è un journal, un diario, che tiene traccia di tutte le attività svolte.

:: Protezione ::

Lezione 1 - Concetti fondamentali della protezione

Il dominio di protezione è il concetto generale, mentre tutto il resto sono implementazioni dello stesso.

Si vuole avere protezione da accessi indebiti (cioè da chi non dovrebbe accedere) e errati. Bisogna poter definire che cosa si può fare con le risorse.

Al solito, abbiamo regole, cioè le politiche per decidere chi e come può usare le risorse, e meccanismi, ovvero come implementare suddette regole.

Le risorse di cui parliamo sono sia fisiche che informative, e sono tutte identificabili con un id. Ci sono poi delle operazioni che si possono svolgere su queste risorse.

Il principio di minima conoscenza dice che un processo deve avere i minimi permessi necessari al suo funzionamento, niente di più.

Il dominio di protezione definisce un insieme di risorse e le relative operazioni lecite per un processo autorizzato ad accedere al dominio.

Il processo che entra in un dominio vede solo le operazioni e le risorse associate a quel dominio.

Questo insieme assume l'aspetto di un insieme di coppie del tipo <oggetto, diritto>. Ci possono anche essere intersezioni tra i vari domini, il che è anche abbastanza intuitivo.

Come si associano i processi ai domini? Dicevamo qui sopra che un processo deve entrare in un dominio, e vedere solo le cose che il dominio gli permette di vedere. L'assegnazione di un processo ad un dominio può essere statica o dinamica.

Se è statica, il processo entra in un dominio e vi rimane fino alla morte.
Se è dinamica, invece, può cambiare da un dominio all'altro durante la sua vita, ovviamente se dispone delle autorizzazioni necessarie.

Quindi, pensandoci bene, se devo avere le autorizzazione anche per cambiare di dominio, allora il dominio stesso è concepibile come una risorsa, cioè un oggetto a cui applicare dei permessi! Vuol dire che ad ogni dominio può essere associato un permesso su di un altro dominio, che potrebbe essere quello di accedervi, oppure quello di modificarne i contenuti.

Oltre che essere concessi, i diritti di accesso ad un processo possono venir revocati. La revoca può essere:

• immediata o ritardata. Se è ritardata, si può attendere o la morte del processo o altri eventi
• selettiva o generale: riguarda o no tutti i processi in quel dominio
• totale o parziale: revoco alcuni diritti, oppure tutti
• temporanea o permanente

Infine, se voglio avere delle regole specifiche per un singolo processo, occorre avere un dominio in cui l'unico autorizzato ad entrarvi sia proprio quel processo.

Lezione 2 - Realizzazione

Qui vediamo come realizzare i domini di protezione.

Matrice degli accessi

La matrice degli accessi è una tabella le cui righe sono i domini, e le colonne sono le risorse. L'incrocio tra una riga ed una colonna, cioè una cella, mi dice che cosa quel dominio può fare a quella risorsa.

Come dicevamo prima, i domini sono anche delle risorse, quindi avremo i domini anche tra le colonne.

L'operazione di cambio di dominio si chiama switch.

Quando viene eseguito uno switch, può esserci o meno il diritto di copia, ovvero copiare i permessi da un dominio all'altro, così che il processo li ha tutti e due.

Alternativamente, posso implementare il diritto di proprietà, che limita il diritto di copia ai soli casi in cui il processo sia proprietario di quella risorsa.

La matrice degli accessi è un concetto astratto, che rappresenta tutto quello che mi serve relativamente ai domini di protezione. Poi, però, devo anche rappresentarla fisicamente.

Matrice completa

Semplicemente, disegno l'intera matrice degli accessi. Il problema è che è una matrice sparsa, ovvero avrà un sacco di celle vuote, e soprattutto sarà immensa.

Lista di controllo degli accessi

Invece di memorizzare la matrice completa, salvo solamente le colonne.

Per ogni risorsa, c'è una lista di coppie <dominio, permessi>.

Così facendo, faccio alla svelta a modificare i diritti relativi ad una risorsa: scorro la lista e applico le dovute modifiche. Al contrario, se voglio aggiungere o eliminare dominî, devo scandire tutte le liste di tutte le risorse.

Nei sistemi grandi, sono poco efficienti perché le risorse saranno tantissime.

Lista delle capacità

Memorizzo le righe della matrice degli accessi. Avrò quindi una lista <risorsa, permessi>.

Rispetto alla lista di controllo degli accessi, la modifica ad una risorsa implica il traversamento di tutte le liste, mentre le modifiche ad un dominio riguardano solo quella lista.

Le revoche diventano altamente inefficienti, perché devo cercare la risorsa in tutte le liste.

Lock-key

L'idea è: se un processo ha la chiave, esegue l'operazione. Ad ogni risorsa viene assegnato un lucchetto, che può anche essere uguale, e ad ogni processo una chiave, o più di una. Quando un processo vuole accedere ad una risorsa, deve controllare se la sua chiave funziona con quel lucchetto.

Amenità varie

Ci sono SO basati sulle liste di capacità.

Ci sono protezioni basati sul linguaggio di programmazione, in cui

• il programmatore
• il progettista
• l'amministratore

danno i permessi ad un processo già in fase di compilazione. Però la sicurezza è inferiore.

Torna alla pagina di Sistemi Operativi