Appunti di Fabio Missagia parte 4.pdf

12. File System Il file system fornisce il meccanismo per la memorizzazione e l’accesso di dati e programmi. Consiste di una collezione di file e della struttura di cartelle (directory). Interfaccia del file system Concetto di file Il sistema operativo astrae dalle caratteristiche fisiche dei sup...

12. File System Il file system fornisce il meccanismo per la memorizzazione e l’accesso di dati e programmi. Consiste di una collezione di file e della struttura di cartelle (directory). Interfaccia del file system Concetto di file Il sistema operativo astrae dalle caratteristiche fisiche dei supporti di memorizzazione fornendo una loro visione logica. Si considera un file come uno spazio di indirizzamento logico e contiguo rappresentante un insieme di informazioni correlate identificate da un nome. I file possono essere dati di qualsiasi tipo e programmi. Attributi di un file Su disco, nella struttura della directory, sono salvati per ogni file il nome (unica informazione in formato leggibile), tipo, posizione (puntatore allo spazio fisico sul dispositivo), dimensione, protezione (controllo sui permessi), tempo, data e identificazione dell’utente. Operazioni sui file Creazione: si cerca lo spazio necessario su disco e si crea un nuovo elemento sulla directory per gli attributi. Scrittura: una system call che specifica il nome del file e i dati da scrivere, è necessario che sia noto il puntatore alla locazione della prossima scrittura. Lettura: una system call che specifica il nome del file e dove mettere i dati letti in memoria, è necessario conoscere il puntatore alla locazione della prossima lettura, lo stesso della scrittura. Riposizionamento all’interno di file: aggiornamento del puntatore alla posizione corrente. Cancellazione: libera lo spazio associato al file e l’elemento corrispondente nella directory. Troncamento: mantiene inalterati gli attributi ma cancella il contenuto del file. Apertura: ricerca il file nella struttura della directory su disco, copia il file in memoria e inserisce un riferimento nella tabella dei file aperti. In sistemi multi-utente si trovano 2 tabelle: una per ogni processo che contiene i riferimenti per i file aperti relativi a esso e una per tutti i file aperti da tutti i processi che contiene i dati indipendenti dal processo. Chiusura: copia del file in memoria su disco. Struttura dei file I tipi di file possono essere usati per indicare la struttura interna del file. Di seguito 3 esempi di struttura di file. 1. Nessuna struttura: si considera un file come una sequenza di parole o bytes, come avviene ad esempio in Unix. 2. Struttura a record semplice: un record è una riga di lunghezza fissa o variabile. 3. Struttura complessa: come accade nei documenti formattati e i formati ricaricabili (load module). Le ultime due si possono emulare con la prima usando caratteri di controllo. Metodi di accesso Sequenziale Questo metodo viene usato da editor e compilatori, permettono le operazioni read next, write next, reset (rewind). Non è permesso il rewrite in quanto si rischia inconsistenza se si scrive qualcosa a metà del file in quanto si potrebbe eliminare ciò che sta dopo. Diretto Come accade nel database in cui un file è una sequenza numerata di blocchi detti record. Le operazioni permesse sono read n, write n, position to n, read next, write next, rewrite n. Struttura delle directory Le directory sono una collezione di nodi contenenti informazioni sui file. Si trovano entrambi sul disco e determinano la struttura del file system. Per ogni file contengono il nome, tipo, indirizzo, lunghezza attuale, massima lunghezza, data di ultimo accesso, data di ultima modifica, proprietario e informazioni di protezione. Operazioni sulla directory Aggiungere un file. Cancellare un file. Visualizzare il contenuto della directory. Rinominare un file. Cercare un file. Attraversare il file system. Organizzazione logica I vantaggi dell’organizzazione logica delle directory sono l’efficienza (rapido accesso ad un file), nomenclatura conveniente agli utenti in quanto permette stessi nomi per file e utenti diversi e nomi diversi per lo stesso file e raggruppamento: i file vengono classificati logicamente per un criterio come il tipo o la protezione. Grazie alle directory il file system può assumere diverse strutture, definite durante l'implementazione. Vediamone alcune. Directory a un livello In questo metodo si trova una singola directory per tutti gli utenti. Nascono problemi di nomenclatura, in quanto è difficile ricordare se un nome esiste già e inventarne sempre di nuovi. Nascono inoltre problemi di raggruppamento. Directory a due livelli In questo metodo si trova una directory separata per ogni utente. Nasce il concetto di percorso (path), è possibile usare lo stesso nome di file per utenti diversi e la ricerca è efficiente. Non esiste comunque raggruppamento e si pone il problema di dove mettere i programmi di sistema condivisi dagli utenti (in Unix si usa PATH). Directory ad albero In questo metodo la directory viene implementata come un albero permettendo una ricerca efficiente e la possibilità di raggruppamento. Nasce il concetto di working directory e i nomi di percorso possono essere assoluti o relativi. Tuttavia manca ancora la possibilità di condivisione di file e directory. Directory a grafo aciclico In questo metodo si espande la versione ad albero a grafo aciclico per permettere la condivisione di file. La condivisione avviene: in Windows: attraverso i collegamenti  in Unix: attraverso i link, che in base alle policy sviluppate in merito possono essere di 2 tipi. link simbolici: un semplice file contenente un percorso ad un file/directory reale. Nel caso la risorsa venga eliminata si può scegliere se ricercare nel file system i vari link simbolici relativi ed eliminare anche essi oppure lasciarli pendenti. Corrispondono ai collegamenti in UNIX/Windows. hard link: non permettono l’eliminazione del file linkato se esistono ancora hard link che lo puntano. Viene tenuto per il file un contatore con il numero di riferimenti ad esso, il file può essere eliminato solo se tale contatore è a 0. Directory a grafo generico Questo metodo nasce come estensione della directory a grafo aciclico e si deve garantire che le ricerche terminino per evitare loop infiniti nell’attraversamento del grafo (visto che in questo caso può avere cicli). Per risolvere questo problema si può permettere di collegare solo file non directory o usare un algoritmo di controllo di esistenza di un ciclo ogni volta che si crea un nuovo collegamento, che può essere costoso. Mount di un file system Il mount di un file system è il processo attraverso il quale un file system viene aggiunto al sistema operativo e reso accessibile. Quando si crea un file system, è possibile renderlo modulare, consentendo di collegare (mount) e scollegare (unmount) interi file system a file system esistenti. Prima di poter accedere a un file system però, è necessario montarlo. Il processo di montaggio richiede che un file system sia associato a un punto specifico del sistema operativo, noto come "mount point". Il mount point è una directory esistente nel sistema di file che funge da punto di accesso al file system che viene montato. Una volta montato, il file system diventa parte integrante del sistema operativo e può essere utilizzato per leggere o scrivere dati. Condivisione di file La condivisione di file è importante in sistemi multiutente ed è realizzabile tramite uno schema di protezione. Nei sistemi distribuiti, i file possono essere condivisi attraverso una rete. Per esempio, il Network File System (NFS) è un tipico schema di condivisione di file via rete. Protezione Il possessore di un file deve poter controllare cosa è possibile fare su un file e da parte di chi. Per farlo si può implementare una lista di accesso per ogni file o directory che lista chi può fare cosa. Gli utenti si possono raggruppare in tre classi con una perdita di generalità: il proprietario, il gruppo (utenti appartenenti allo stesso gruppo del proprietario) e gli altri. Per ogni classe i permessi possono essere di read(r), write(w) ed execute(x). CHMOD In Unix per esempio, è possibile cambiare i permessi di un file utilizzando il comando chmod. Un esempio di utilizzo può essere il seguente: chmod 754 nome_file dove le 3 cifre rappresentano rispettivamente il livello di permessi per l'utente, il livello di permessi del gruppo e il livello di permessi generale. In base alla cifra si ha una serie di permessi. La tabella seguente indica il significato dei singoli valori: Valore decimale Permessi 7 lettura, scrittura ed esecuzione 6 lettura e scrittura 5 lettura ed esecuzione Valore decimale Permessi 4 solo lettura 3 scrittura ed esecuzione 2 solo scrittura 1 solo esecuzione 0 nessuno Dunque nel nostro esempio il proprietario ha i permessi di read, write ed execution, il gruppo non ha la write, e gli altri solo la read. Implementazione di un file system Per gestire un file system si usano diverse strutture dati in parte su disco e in parte in memoria. Le caratteristiche, pur avendo una base comune sono fortemente dipendenti dal sistema operativo e dal tipo di file system. Strutture su disco Blocco di boot: contiene le informazioni necessarie per l’avvio del sistema operativo. Blocco di controllo delle partizioni: contiene i dettagli riguardanti la partizione come numero e dimensione dei blocchi, la lista dei blocchi liberi, dei descrittori liberi. Strutture di directory: descrivono l’organizzazione dei file. Descrittori dei file: contengono vari dettagli sui file e i puntatori ai blocchi dati. Strutture in memoria Tabella delle partizioni: informazioni sulle partizioni montate. Strutture di directory: copia in memoria delle directory a cui si è fatto accesso di recente. Tabella globale dei file aperti con le copie dei descrittori dei file. Tabella dei file aperti per ogni processo contenente il puntatore alla tabella globale e le informazioni di accesso. Allocazione dello spazio su disco I blocchi su disco possono essere allocati in modi diversi con l’obiettivo di minimizzare i tempi di accesso e massimizzare l’utilizzo dello spazio. Allocazione contigua In questo metodo ogni file occupa un insieme di blocchi contigui su disco. L’entry della directory è semplice in quanto contiene l’indirizzo del blocco di partenza e la lunghezza del file. Vantaggi Permette un accesso semplice in quanto l’accesso al blocco b + 1 non richiede lo spostamento della testina rispetto al blocco b, a meno che b non sia l’ultimo blocco di un cilindro (raro). Supporta sia l’accesso sequenziale che casuale in quanto per leggere il blocco i di un file che inizia al blocco b basta leggere b + i. Svantaggi Presenta problemi simili a quelli dell’allocazione dinamica della memoria: si deve scegliere tra algoritmi bestfit, first-fit o worst-fit e porta a uno spreco di spazio dovuto a frammentazione esterna e richiede una compattazione periodica dello spazio. La decisione della dimensione dello spazio da allocare è un problema, in quanto i file potrebbero crescere dinamicamente. Si può fare in modo che, se il file deve crescere e non c’è spazio, nasce un’errore e una terminazione del programma e si riesegue. In questo modo si tende a sovrastimare lo spazio necessario che porta a uno spreco. Un’altra soluzione consiste nel trovare un buco più grande e ricopiare tutto il file in questo, operazione trasparente per l’utente ma che rallenta il sistema. Variante Alcuni file system moderni usano uno schema modificato di allocazione contigua come Linux ext2fs basato sull’extent, una serie di blocchi contigui su disco. Il file system alloca extent invece di blocchi singoli che in generale non sono contigui e si prestano pertanto per l’allocazione a lista. Allocazione a lista In questo metodo ogni file è costituito da una lista di blocchi concatenati, che possono essere sparsi ovunque nel disco. La directory contiene puntatori al primo e all’ultimo blocco e ogni blocco contiene un puntatore al blocco successivo. Considerando X l’indirizzo logico e N la dimensione del blocco, è il numero X (N −1) del blocco nella lista, mentre X mod (N − 1) è l’offset all’interno del blocco. Vantaggi L’allocazione a lista permette una semplice creazione di un nuovo file in quanto basta cercare un blocco libero e creare una nuova entry nella directory che punta ad esso. Anche l’estensione del file è semplice: si cerca un blocco libero e lo si concatena alla fine del file. Non c’è spreco se non si considera lo spazio per il puntatore in quanto si può usare qualunque blocco e non c’è frammentazione esterna. Svantaggi Non permette però accesso casuale in quanto bisogna scorrere tutti i blocchi a partire dal primo. Richiede tanti riposizionamenti sparsi che portano a scarsa efficienza. È inoltre scarsamente affidabile in quanto la perdita di un puntatore o un errore causa il prelevamento del puntatore sbagliato. Si devono quindi introdurre metodi di recupero con overhead come le liste doppiamente concatenate e memorizzare il nome del file e il numero di blocco in ogni blocco del file. Variante - FAT (file allocation table) Una variante che migliora l'accesso casuale fa uso della File Allocation Table (FAT). Questa è una tabella che occupa i primi blocchi del volume e contiene una lista di tutti i blocchi allocati. Inoltre, per ogni blocco si registra anche la posizione del suo blocco successivo. Purtroppo le dimensioni della FAT (spesso FAT32 perchè con entry di 32 bit) impediscono una scansione efficiente e cominciano ad occupare una porzione significativa di memoria con l'aumentare delle dimensioni del disco. Questi svantaggi rendono oggi l'uso della FAT proibitivo. L’accesso diretto ai file di grandi dimensioni, per esempio utilizzando la system call lseek, può essere inefficiente nei file system di tipo FAT a causa del modo in cui i dati vengono organizzati e gestiti. In un file system FAT, i dati vengono memorizzati in cluster di dimensioni fisse. Quando si accede a un file, il sistema operativo deve seguire una catena di cluster per trovare il cluster corretto che contiene i dati richiesti. Per i file di grandi dimensioni, questo può comportare il passaggio attraverso molti cluster, il che può richiedere molto tempo. Inoltre, se il file è frammentato (cioè i suoi cluster non sono contigui), il tempo necessario per trovare il cluster corretto può aumentare ulteriormente. Questo può rendere l’accesso diretto ai file di grandi dimensioni utilizzando lseek inefficiente nei file system di tipo FAT. Allocazione indicizzata In questo metodo ogni file ha un blocco indice (index block) che contiene la tabella degli indirizzi dei blocchi fisici, ossia il blocco indice punta a tutti gli altri blocchi dello stesso file. La directory contiene l’indirizzo del blocco indice. Se X è l’indirizzo logico e N la dimensione del blocco X N è l’offset nella index table e X mod N è l’offset all’interno del blocco dati. Vantaggi L’accesso casuale è efficiente. Non c'è frammentazione esterna. Svantaggi Rispetto all'allocazione a lista (non alla FAT) tende a sprecare più memoria, in quanto per ogni file richiede l'allocazione di un blocco indice che potrebbe essere non del tutto utilizzato. La dimensione del blocco indice limita la dimensione del file massima. Infatti, se per esempio il blocco indice ha 512 entry (gli indirizzi fisici), e ogni indirizzo fisico corrisponde ad un blocco di 512 parole, la dimensione del file può essere massimo di 512 = 256000 parole. Pertanto, per i file di grandi dimensioni, 2 si usano schemi a più livelli, che vedremo ora. Indici multilivello Il blocco indice punta ad altri blocchi indici, che punteranno ai dati dei file veri e propri. Sia X l’indirizzo logico e N la dimensione del blocco in parole. è il blocco della index table di primo n X ⋅N livello e X mod (N ⋅ N ) = R , dove R N è l’offset nel blocco della index table di secondo livello e R mod N è l’offset nel blocco dati. Per esempio, blocchi da 4KB consentono 1K indici da 4 byte, mentre due livelli di indici consentono file da 4GB. Schema concatenato Si usano più blocchi indice collegati tramite una lista concatenata: l’ultimo degli indici di un blocco indice punta a un altro blocco indice. X è il numero del blocco indice all’interno della lista dei blocchi indice e N (N −1) X mod (N (N − 1)) = R , dove R N −1 è l’offset nel blocco indice e R mod N è l’offset nel blocco dati. Esempio N = 1KB = 256 parole (parola=32bit) 4 byte per parola Max file = 256 blocchi da 1KB = 256KB X = 12200 X N = 12200/256 = 47 (blocco 47) X mod N = 168 (parola 168 all’interno del blocco 47)  X = 644000 Non basta un primo livello X (N (N −1)) = 9 (blocco della lista concatenata) X mod (N (N − 1)) = R = 56480 R N −1 = 220 (offset nel blocco index) R mod N = 160 (offset nel blocco dati) Schema combinato Unix usa lo schema combinato in cui ad ogni file è associato un i-node (index-node) che contiene gli attributi del file e fa da blocco indice. Gli i-node sono gestiti dal sistema operativo e memorizzati in modo permanente in una porzione riservata al sistema operativo di solito all’inizio del disco. Per memorizzare i blocchi di dati del file, ogni i-node contiene: 10 puntatori diretti ai blocchi di dati di file. Un puntatore single indirect che punta ad un blocco indice che contiene puntatori a blocchi di dati di file. Un puntatore double indirect che punta ad un blocco indice che contiene puntatori a blocchi indice contenenti puntatori a blocchi di dati di file. Un puntatore triple indirect che punta ad un blocco indice che contiene puntatori a blocchi indice che contengono puntatori a blocchi indice che contengono puntatori a blocchi di dati di file. Implementazione delle directory Le directory vengono implementate con lo stesso meccanismo usato per memorizzare i file. Non contengono dati, ma una lista di file e directory. Questo spazio può essere memorizzato in due modi: lista di puntatori ai blocchi dati: la directory contiene una lista di puntatori al primo blocco di ogni file. È di facile implementazione ma poco efficiente in quanto lettura, scrittura e rimozione di file richiedono una ricerca per trovare il file. tabella hash: con tempo di ricerca migliore ma che richiede la gestione delle collisioni. Gestione dello spazio libero Per tenere traccia dello spazio libero su disco si mantiene una mappa dei blocchi liberi. Per creare un file si cercano blocchi liberi nella mappa e per rimuovere un file si aggiungono i suoi blocchi a tale mappa. Vediamo ora diverse alternative per implementare la mappa. Vettore di bit Si mantiene un vettore in cui ogni posizione indica se un blocco è occupato o no. Bit[i] = 0 implica che il blocco i è libero e Bit[i] = 1 implica che è occupato. La mappa di bit richiede spazio extra ed è efficiente solo se il vettore è mantenibile tutto in memoria. Risulta comunque facile ottenere blocchi contigui. Lista concatenata di blocchi liberi (free list) Ogni blocco libero punta ad un altro blocco libero. Permette spreco minimo(solo per la testa della lista) ma lo spazio contiguo non è ottenibile. Raggruppamento Il concetto è simile a quello della lista concatenata, ma qui un blocco contiene la lista di n − 1 indirizzi di blocchi liberi, e l'ultima entry punta ad un altro blocco usato come lista. Fornisce rapidamente un gran numero di blocchi liberi. Conteggio Si usa una lista che contiene ad ogni entry un blocco libero e quanti blocchi liberi consecutivi seguono. La lista risulta più corta se il contatore è maggiore di 1 per ogni gruppo di blocchi liberi. Efficienza e prestazioni Efficienza Il disco è un collo di bottiglia e l’efficienza dipende dall'algoritmo di allocazione dello spazio su disco e dal tipo di dati contenuti nella directory. Prestazioni Il controller del disco possiede una piccola cache che è in grado di contenere un’intera traccia ma non basta per garantire prestazioni elevate, pertanto si usano dischi virtuali (RAM disk) e cache del disco o buffer cache. Dischi virtuali Parte della memoria viene gestita come se fosse un disco: il driver di un RAM disk accetta tutte le operazioni standard dei dischi eseguendole in memoria. È veloce ma supporta solo file temporanei. Viene gestito dall’utente che scrive sul RAM disk invece che sul disco. Cache del disco È una porzione di memoria che memorizza blocchi usati di frequente, simile alla cache tra memoria e CPU. Viene gestita dal sistema operativo e sfrutta il principio di località spaziale e temporale. Il trasferimento di dati nella memoria del processo utente non richiede spostamento di byte. Nascono problematiche riguardanti la politica di rimpiazzamento del blocco (se la cache è piena devo scegliere il blocco da togliere usando LRU, LFU, RANDOM, ecc.) e la politica di scrittura. Cioè se devo scrivere sul blocco usato di recente, intanto scrivo su quello in cache ma quando aggiorno quello originale che è memorizzato su disco? Posso decidere di fare write-back, ovvero scrivere solo quando devo rimuovere il blocco dalla cache (può generare problemi di affidabilità in caso di crash) oppure write-through, scrivendo sempre (meno efficiente, la cache è praticamente in sola lettura). Recupero I problemi di consistenza tra disco e cache possono essere risolti attraverso un controllo di consistenza che confronta i dati nella directory con i dati su disco e sistema le inconsistenze, oppure attraverso l’uso di programmi di sistema per fare il backup del disco su memoria di massa come i nastri che permettono il recupero di file persi tramite il restore dei dati di backup. File system log structured Si registra ogni cambiamento del file system come una transazione. Tutte le transazioni sono scritte su log e considerate completate quando vengono scritte su log (anche se il file system può non essere aggiornato). Le transazioni sono scritte in modo asincrono nel file system e quando il file system è modificato la transazione viene cancellata dal log. Se il sistema va in crash le transazioni non avvenute sono quelle presenti sul log. In questo modo si ottimizza il numero di seek. 13. Sistemi RAID L’evoluzione tecnologica ha permesso di avere dischi sempre più piccoli e meno costosi, pertanto è più facile equipaggiare un sistema con molti dischi in modo da raggiungere maggiori prestazioni attraverso letture e scritture in parallelo e maggior affidabilità tramite ridondanza. Il RAID nasce nel 1988 come Redundant Array of Independent Disks, con l’obiettivo di migliorare l’affidabilità incrementando le prestazioni. La struttura software dei dispositivi RAID si basa su più dischi indipendenti collegati al bus e la funzionalità RAID implementata dal sistema operativo. La struttura hardware si basa su un controllore intelligente che gestisce diversi dischi collegati alla macchina. Una batteria RAID è un’unità a sè stante composta da controllore, cache e dischi autonomi collegati a una macchina. Concetti di base Le strutture RAID si basano su copiatura speculare dei dati (mirroring) e sezionamento dei dati (data striping), per implementare parallelismo che garantisce aumento di prestazioni e affidabilità. Affidabilità Un guasto a un disco comporta la perdita di dati e per migliorare l’affidabilità si deve ricorrere alla ridondanza, che consiste nel memorizzare informazioni non strettamente necessarie ma utili per ricostruire le informazioni perse in caso di guasto. Vediamo ora come implementarla. Copiatura speculare Il modo più semplice per implementare la ridondanza è il mirroring (o shadowing) in cui un disco logico corrisponde a due dischi fisici, ogni scrittura avviene su entrambi i dischi e i dati si perdono solo se si guastano entrambi i dischi. Il tempo medio di perdita dei dati in caso di mirroring dipende dal tempo medio di guasto di ogni singolo disco e dal tempo medio di riparazione. Per esempio, supponendo un tempo medio di guasto sul singolo disco di 100.000 ore e un tempo di riparazione di 10 ore, si ha il seguente tempo medio di perdita dei dati su un sistema con mirroring: 2 100.000 = 57.000 anni 2 ⋅ 10 Si noti come offra protezione solo contro i guasti indipendenti e per cause esterne (calo di tensione, difetti di fabbricazione in una partita di dischi, ecc.) entrambi i dischi potrebbero guastarsi contemporaneamente. Con mirroring la frequenza di gestione delle letture raddoppia perchè si può leggere da uno qualunque dei due dischi e il tempo di trasferimento rimane inalterato. Sezionamento dei dati Usando più dischi è possibile migliorare la capacità di trasferimento distribuendo i dati in sezioni su più dischi (data striping). Il sezionamento può avvenire a livello di bit, ovvero i bit di ciascun byte vengono distribuiti su più dischi, o a livello di blocco, in cui i blocchi dei file sono distribuiti su più dischi. Il parallelismo tramite il bilanciamento del carico aumenta la produttività per accessi multipli a piccole porzioni di dati e riduce il tempo di risposta relativo agli accessi a grandi quantità di dati. Livelli di RAID Il mirroring garantisce un'alta affidabilità ma è costoso, mentre il data striping permette alta capacità di trasferimento dati ma non migliora l’affidabilità. Spesso si usano tecniche basate sui bit di parità. L’utilizzo combinato di queste tecniche è stato schematizzato in 6 livelli di RAID. Livello RAID 0 Puro data striping a livello di blocco per migliorare soltanto le prestazioni, senza ridondanza. Vantaggi È economico e garantisce alte prestazioni grazie al parallelismo delle operazioni di lettura e scrittura. Svantaggi Non ha ridondanza e l’affidabilità diminuisce all’aumentare del numero di dischi impiegati. Livello RAID 1 Avviene mirroring senza sezionamento di blocco. Vantaggi Aumenta l’affidabilità linearmente con il numero di copie. Si aumentano le prestazioni in lettura (se il disco è occupato si può leggere dall’altro). Svantaggi Ha un alto costo e bassa scalabilità. Livello RAID 2 Avviene il data striping a livello di bit, congiunto all'uso del codice di Hamming che consente di correggere gli errori. I bit di correzione sono memorizzati singolarmente in dischi separati diversi rispetto a quelli usati per i dati. Se un disco si guasta i bit rimanenti del byte dati e i bit di correzione associati vengono usati per ricostruire il dato danneggiato. Il RAID 2 richiede solo 3 dischi in più per 4 dischi dati rispetto ai 4 richiesti dal RAID 1. Questo perchè utilizza il codice di Hamming, che codifica 4 bit dati in 7 bit, aggiungendone 3 di parità. Vantaggi È un RAID 0 con correzione degli errori, dunque maggiore affidabilità. Svantaggi Gli accessi non possono essere paralleli, poichè i dati devono essere ricostruiti mano a mano che le letture proseguono, e la rotazione dei dischi deve essere sincronizzata, proprio perchè si deve leggere un bit da un disco ed un bit dall'altro alternatamente. Inoltre è costoso. Livello di RAID 3 Avviene il data striping a livello di byte, con un disco dedicato ai bit di parità noto come organizzazione con bit di parità. I controllori dei dischi sono in grado di rilevare se un settore è stato letto correttamente. Se un settore è danneggiato per ogni bit del settore è possibile determinare se deve valere 0 o 1 calcolando la parità dei bit corrispondenti dai settori degli altri dischi. Vantaggi Ha la stessa efficienza del RAID 2 ma usa un solo disco per i bit di parità. La velocità di trasferimento è pari a n volte quella del RAID 1. Svantaggi Rispetto al RAID 1 fornisce meno operazioni di I/O al secondo in quanto ogni disco è coinvolto da tutte le richieste. Il tempo di scrittura è più lungo dovuto al calcolo del bit di parità. È possibile però risolvere delegando al controllore RAID il calcolo della parità, sollevando così la CPU dall’incarico. Livello di RAID 4 Avviene il data striping a livello di blocco, con un disco dedicato ai bit di parità detto organizzazione con blocchi di parità intercalati. È simile al RAID 0 con un blocco di parità in un disco separato. Ha più tolleranza ai guasti e letture più veloci grazie al parallelismo. Vantaggi Visto che il data striping avviene a livello di blocco, le operazioni di accesso ai dischi sono parallelizzabili, consentendo così letture più veloci. Inoltre ha la tolleranza ai guasti. Svantaggi Il disco usato per la parità può diventare un collo di bottiglia e le scritture sono lente a causa del calcolo della parità. Livello di RAID 5 Avviene il data striping a livello di blocco, con bit di parità distribuiti tra tutti i dischi del RAID, noto come organizzazione con blocchi intercalati a parità distribuita. Ovviamente un blocco di parità non può contenere informazioni di parità per blocchi che risiedono nello stesso disco, altrimenti un guasto al disco farebbe perdere i dati. Vantaggi Ha gli stessi vantaggi del RAID 4 senza il collo di bottiglia del disco di parità, visto che i blocchi contenenti bit di parità sono distribuiti in tutti i dischi. Svantaggi Come il RAID 4 ha scritture lente. Livello di RAID 6 È simile al RAID 5 ma con maggiori informazioni di ridondanza per gestire il malfunzionamento di ben 2 dischi contemporaneamente. Al posto della parità usa altri codici per la correzione degli errori come Reed- Solomon. Vantaggi Ha un altissima ridondanza. Svantaggi È molto costoso e le scritture sono lente per la gestione dei codici per la correzione degli errori. Livello RAID 0 + 1 Combina il RAID 0 e 1 per fornire affidabilità e alte prestazioni: si trovano due RAID 0 messi in RAID 1. I dischi principali effettuano data striping tra di loro, le copie effettuano data striping tra di loro. Vantaggi Ha prestazioni migliori rispetto al RAID 5 e alta affidabilità. Svantaggi È molto costoso e richiede il doppio dei dischi necessari per memorizzare dati. Infine non supporta la rottura simultanea di due dischi, se non appartengono allo stesso stripe. Livello RAID 1 + 0 Combina 1 e 0 per fornire affidabilità e alte prestazioni: dati n dischi si trovano n 2 RAID 1 in RAID 0. In breve, ogni disco ha la sua copia accanto. Vantaggi È più robusto del RAID 0 + 1 in quanto ogni disco di ogni stripe può guastarsi senza far perdere dati al sistema. Svantaggi È costoso. 14. Sistema di I/O Il sistema di I/O è l’insieme dei metodi per controllare i dispositivi di I/O con l’obiettivo di fornire ai processi utente un’interfaccia efficiente e indipendente dai dispositivi. Consiste nell’interazione tra l’hardware di I/O e il software di I/O, determinato dal sistema operativo. Hardware di I/O Esistono numerosi ed eterogenei dispositivi di I/O che si differenziano tra loro per le funzioni che svolgono, come la memorizzazione (dischi, nastri), la trasmissione (modem, schede di rete) e l'interazione uomo- macchina (tastiera, monitor). Tuttavia, tutti i dispositivi di I/O condividono alcuni componenti fondamentali, tra cui: Porta: il punto di connessione Bus: il canale di comunicazione Controllore: la parte elettronica che agisce su porta, bus o dispositivi Controllore dei dispositivi Il controllore è la parte elettronica di un dispositivo, detto anche device controller. Viene connesso tramite bus al resto del sistema. È associato ad un indirizzo e contiene registri per comandare il dispositivo: Registro di stato: per capire se il comando è stato eseguito, se c’è stato un errore o se i dati sono pronti per essere letti. Registro di controllo: per inviare comandi al dispositivo. Un numero arbitrario di buffer per la conversione dei dati. L’accesso ai registri può avvenire in vari modi: Dispositivi mappati in memoria (memory-mapped): i registri sono visti nello spazio di indirizzamento della memoria e il loro accesso avviene tramite istruzioni di accesso alla memoria (necessario disabilitare la cache). Permettono di scrivere driver in linguaggio di alto livello e non esiste nessun speciale accorgimento per la protezione in quanto è sufficiente allocare lo spazio di indirizzamento fuori dallo spazio utente. Dispositivi mappati su I/O (I/O-mapped): l’accesso ai registri avviene tramite istruzioni specifiche e non esiste nessun problema di gestione della cache. Soluzioni ibride come il Pentium in cui i registri sono I/O mapped e i buffer memory mapped. Per esempio per il display l’hardware mappa i registri e la memoria del display nello spazio di indirizzi fisico, si scrive nella memoria (frame buffer) i cambi che avvengono nello schermo e le descrizioni grafiche nell’area della coda di comandi. Scrivere nel registro comando potrebbe causare all’hardware grafico del display di fare qualcosa. Accesso ai dispositivi di I/O Esistono inoltre differenti tecniche con le quali la CPU ed il controllore comunicano. Vediamone alcune. Polling Lo stato del dispositivo viene determinato mediante la lettura ripetuta del busy-bit del registro di status: quando è 0 il comando viene scritto nel registro di controllo, il command-ready-bit viene posto a 1 e l’operazione di I/O viene eseguita. Questa è chiaramente un tecnica di busy waiting e causa uno spreco delle risorse e del tempo di CPU, specialmente se si cerca di comunicare con periferiche molto lente. Interrupt Il dispositivo di I/O avverte la CPU tramite un segnale su una connessione fisica. Gli interrupt sono una problematica complessa, per questo sono gestiti da un apposito controllore di interrupt. Questo perchè: possono essere temporaneamente disattivati durante l'esecuzione di istruzioni critiche per garantire l'integrità del sistema è necessario che siano numerati in un apposito vettore di interrupt (affinchè ad un dato interrupt corrisponda un dato handler) devono essere gestibili tramite un ordine di priorità DMA - Direct Memory Access Questa tecnica è basata sull'idea di scaricare l'onere della gestione dell'I/O da parte della CPU, su un controllore dedicato chiamato DMA controller. In questo modo non sprechiamo la CPU per controllare il registro di stato del controllore e trasferire pochi byte alla volta. Ma come opera il DMA controller? Una volta ottenuti tutti gli indirizzi necessari dalla CPU (l’indirizzo di partenza dei blocchi/memoria da trasferire, l’indirizzo di destinazione, il numero di byte da trasferire e la direzione del trasferimento), il DMA controller interagisce direttamente con il controller della periferica, mentre la CPU effettua altre operazioni. Al termine dell'operazione, notifica la CPU con un interrupt. Interfaccia di I/O I dispositivi di I/O si differenziano per molti aspetti e pertanto si rende necessaria dell’astrazione, incapsulamento e software layering per nascondere le differenze al kernel del sistema operativo, costruendo un’interfaccia comune che dà un insieme di funzioni standard. Le differenze sono incapsulate nei device driver. Le interfacce semplificano il lavoro del sistema operativo aggiungendo nuovo hardware senza modificare il sistema operativo. Dispositivi a blocco e a carattere L’interfaccia dei dispositivi a blocchi è utilizzata dai dispositivi che memorizzano e trasferiscono dati in blocchi, la lettura e scrittura di un blocco è indipendente dagli altri, i comandi sono di read, write e seek, ed è tipica nei dischi. L’interfaccia dei dispositivi a carattere è utilizzata dai dispositivi che memorizzano e trasferiscono stringhe di caratteri anzichè blocchi di dati. Non esiste indirizzamento (seek) e i comandi tipici utilizzati sono get e put. I dispositivi tipici sono terminali, mouse e porte seriali. Software di I/O Gli obiettivi del software di I/O sono l’indipendenza dal dispositivo, la notazione uniforme, la gestione degli errori, la gestione di varie opzioni di trasferimento e le prestazioni. È organizzato per livelli di astrazione: 1. Gestori degli interrupt: sono astratti il più possibile dal resto del sistema operativo e bloccano/sbloccano i processi attraverso semafori o segnali. 2. Device driver: devono tradurre le richieste astratte del livello superiore in richieste device dependent, contengono tutto il codice device-dependent, condivisi per classi di dispositivi, interagiscono con i controllori dei dispositivi e tipicamente scritti in linguaggio macchina. 3. Software del sistema operativo indipendente dal dispositivo: ha funzioni speciali come la definizione di interfacce comuni, naming (individuare un dispositivo e gestire i nomi), protezione (tutte le primitive di I/O sono privilegiate) e buffering, ovvero la memorizzazione dei dati durante un trasferimento per gestire diverse velocità e diverse dimensioni. Deve definire la dimensione del blocco, allocare e rilasciare i dispositivi e gestire gli errori tipicamente device-dependent. 4. Programmi utente: tipicamente system call per l’accesso ai dispositivi Per esempio nello spooling durante la gestione di I/O dedicato più processi possono voler scrivere su una stampante contemporaneamente, ma le stampe non devono essere interfogliate, pertanto i dati da processare vanno accodati nella spooling directory e lo spooler, un processo di sistema è l’unico autorizzato ad accedere alla stampante. Periodicamente stampa i dati nella spooling directory.