Appunti di Sistemi Operativi Enzo Mumolo e-mail address ...unina.stidue.net/Universita' di...

Appunti di Sistemi Operativi

Enzo Mumolo

e-mail address :[email protected] address :www.units.it/mumolo

Indice

1 La Gestione della Memoria di Massa 1

1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Caratteristiche generali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2.1 Struttura di un disco magnetico . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.2 Tracce e settori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.3 Il meccanismo di SEEK: posizionamento del sensore di lettura/scrittura . . . 41.2.4 Inseguimento della traccia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.5 Tempo di lettura/scrittura di un �le . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Tecniche di ottimizzazione delle prestazioni del disco . . . . . . . . . . . . . . . . . . 81.3.1 Posizione di riposo della testina di lettura/scrittura . . . . . . . . . . . . . . . 81.3.2 Gestione della coda del disco . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.3 Gestione della disk cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.3.4 La gestione degli errori nei dischi . . . . . . . . . . . . . . . . . . . . . . . . . 13

i

Capitolo 1

La Gestione della Memoria di Massa

1.1 Introduzione

La memoria di massa é estremamente importante per le prestazioni dell'intero Sistema Operativo.Molte informazioni essenziali per il SO, infatti, sono memorizzate nella memoria di massa che lemantiene stabilmente nel tempo. Ovviamente la memoria di massa é indispensabile per memorizzareil codice del Sistema Operativo stesso, tutti i processi eseguibili e tutti i tipi di dati. La memoriadi massa piú utilizzata attualmente é il disco �sso a memorizzazione magnetica. Anche se esistonoalcune alternative, tuttavia il disco magnetico fornisce il minore costo per byte memorizzato e sarádunque utilizzato per lungo tempo ancora.

1.2 Caratteristiche generali

In vista del lungo tempo di vita del disco magnetico, é importante considerare le sue caratteristicheprincipali:

Densitá Naturalmente la densitá é legata alla capacitá del disco, cioé alla quantitá di byte che pos-sono essere memorizzati sul disco. Negli ultimi anni la densitá di memorizzazione é aumentatacostantemente con incrementi di circa 80 % all'anno. L'aumento della densitá di memoriz-zazione é legata all'aumento della densitá lineare e all'aumento del numero delle tracce perunitá di spazio.

Velocitá Il tempo di lettura/scrittura delle informazioni memorizzate sul dico �sso dipende prin-cipalmente dalla velocitá di rotazione e dalla densitá di memorizzazione. Per leggere l'infor-mazione memorizzata su una traccia del disco, infatti, é necessario che il sensore che legge leinformazioni magnetiche sia posizionato all'inizio della traccia stessa e che la traccia, ruotandocol disco, scorra sotto il sensore di lettura/scrittura. Un disco che ruota ad una velocitá vespressa in RPM [rotazioni per minuto] impiega 60/v secondi per far scorrere l'intera tracciasotto il sensore. Se il disco ha raggio R in cm, il disco ruota ad una velocitá di (2πRv)/60[cm/secondo].

Se in�ne l'informazione viene memorizzata sul disco con una densitá pari a D [byte/cm],l'informazione puó essere acceduta ad una velocitá di

2πDvR

60

byte al secondo. Quindi, come a�ermato in precedenza, la velocitá d'accesso all'informazionesul disco dipende dalla densitá di memorizzazione e dalla velocitá di rotazione. La riduzione

1

1.2 Caratteristiche generali 2

del tempo d'accesso implica soluzioni contrastanti che obbligano ad un compromesso. Infatti,se la densitá di memorizzazione é un fattore tecnologico, la velocitá di rotazione é un fattoremeccanico: se un'alta velocitá di rotazione é desiderabile, ha delle implicazioni negative siasul calore sviluppato per attrito che sulla stabilitá della struttura, che deve essere moltoresistente per sopportare le alte accelerazioni centrifughe. Per ridurre la forza sviluppatadalla accelerazione centrifuga bisogna ridurre la massa, e quindi fare dischi di piccolo raggio.Questo peró riduce la velocitá d'accesso, come risulta dalla relazione riportata sopra. Ancorapiú importante é il fatto che piccoli raggi implicano che i sensori di lettura/scrittura devonoavere una altissima de�nizione, cioé devono operare su spazi piccolissimi e che il sistema dicontrollo del movimento del braccio di lettura/scrittura deve essere estremamente preciso.

A�dabilitá Le informazioni memorizzate su un sistema di memoria di massa possono perdersi acausa di guasti �sici del sistema di memorizzazione. I linea di principio ci sono due modi pera�rontare questo problema: la protezione dei dati con dei codici d protezione e la replicazionedei dati. Ovviamente i due sistemi possono essere combinati. La protezione mediante codiciconsiste nel calcolo di una sequenza di bit partendo da una certa informazione che puó essereutilizzata per ricostruire le informazioni stesse nel caso siano perdute. I problemi di questo tipodi protezione stanno nei limiti o nella potenza del codice (non tutte le informazioni possonoessere ricostruite) da un lato e nella richiesta computazionale dei relativi algoritmi dall'altro.Naturalmente il primo problema é piú serio del secondo.

Il secondo modo consiste nella replicazione dei dati. I dati replicati devono preferibilmenteessere memorizzati in unitá indipendenti. Il problema della replicazione consiste nel fatto chei guasti �sici sono tanto piú frequenti quanto piú sono le unitá di memorizzazione. I guasti sirisolvono usando codici di protezione.

Costo In linea di principio il costo per bit del sistema rotante con dischi magnetici é minore di altrisistemi di memorizzazione, come per esempio le memorie a stato solido permanenti (memorieFlash). C'e' un fattore di scala tuttavia, cioé é diverso se si considera il costo per bit o ilcosto per Gigabit. Mentre é abbastanza poco costoso aumentare la quantitá di informazionimemorizzate su un disco (basta aggiungere un altro piatto al disco) per aumentare la quantitádi memoria memorizzata in un sistema a stato solido la cosa non é cosí facile, perché i chipdisponibili hanno un limite intrinseco e allora bisogna aumentare la complessitá del sistemaa stato solido. In sostanza é piú facile aumentare la memorizzazione su un disco che su unsistema di altro tipo. Per lo meno allo stato attuale della tecnologia.

Memoria Primaria, Secondaria, Terziaria É una classi�cazione di alcuni livelli di memoriz-zazione: la memoria primaria é la memoria centrale di un elaboratore, la memoria sec-

ondaria é la memoria di massa. I due tipi di memoria sono usati congiuntamente e hanno lacaratteristica la prima di essere volatile e di quantitá piccola/media ma a basso tempo d'ac-cesso, la seconda di essere non volatile, di capacitá decisamente maggiore e a piú alto tempod'accesso. La memoria terziaria é una memoria con capacitá decisamente maggiore, conpreatazioni peggiori in termini di tempo d'accesso e di capacitá di indirizzare porzioni dei datiesendo tipicamente sequenziali ma di maggiore durata e di minore costo per bit. Pertanto,l'uso della memoria terziaria é archiviazione e backup, usi nei quali si trattano comunquegrandi quantitá di dati.

I supporti utilizzati per memoria terziaria sono magnetici (ad esempio nastri magnetici) oppureottici (ad esempio CD-ROM, DVD).

Memoria di rete Questa memoria si puó collegare direttamente alla Rete di Calcolatori (NetworkStorage) e serve per fornire un accesso centralizzato ai dati e risorse di memorizzazione dimassa agli utenti collegati alla rete, che tipicamente usano diversi Sistemi Operativi (clienti


Figura 1.1: Il gap tra le prestazioni della CPU e dei dischi magnetici aumenta nel tempo

eterogenei). La disponibilitá dei dati viene cosí aumentata perché l'accesso ai dati non dipendeda un particolare server. Le prestazioni di questa memoria dipendono dalle prestazione dellarete alla quale é collegata.

Naturalmente l'utente vorebbe un disco ad alta velocitá di accesso, altamente a�dabile e di costobasso. Dalla discussione precedente si conclude peró che queste tre caratteristiche sono alquantocontrastanti. Se si cerca di aumentare la velocitá di un disco si aumenta il costo e si diminuiscel'a�dabilitá. Se si aumenta l'a�dabilitá si aumente il costo e si diminuisce la velocitá del sistema.Se si diminuisce il costo, in�ne, si abbassa velocitá e a�dabilitá. Bisogna quindi ricorrere a deicompromessi. Gli strumenti utilizzati per trovare un punto di compromesso sono gli algoritm digestione e ottiizzazione delle prestazioni del disco, che possono essere piuttosto so�sticati.

Tutti i problemi menzionati sono poi sempre piú importanti perché c'é una tendenza attuale,legata allo sviluppo della tecnologia dei calcolatori, che fá sí che la di�erenza delle prestazionidell'unitá di calcolo (CPU) e dei sistemi di memorizzazione di massa aumenti col tempo. Piú pre-cisamente, possiamo dire che se da un lato la velocitá delle CPU raddoppia approssimativamenteogni due anni, e la capacitá dei dischi raddoppia ogni 1.5 anni circa, il tempo d'accesso dei dis-chi aumenta molto piú lentamente. Questa di�erenza di prestazioni é rappresentato in Fig.1.1 ecostituisce il vero collo di bottiglia attuale dei sistemi di calcolo.

1.2.1 Struttura di un disco magnetico

1.2.2 Tracce e settori

Un settore é l'unitá di base di un disco �sso. Un disco é formato da un gruppo di settori cheformano un cerchio, chiamato traccia. Un gruppo di tracce concentriche de�nisce la super�cie diun piatto del disco. La serie di tracce corrispondenti sui diversi piatti viene chamata cilindro eviene acceduta come entitá singola, perché il sistema di lettura/scrittura é generalmente solidale,per ridurre il costo del sistema, con tutti i piatti; cioé andare alla traccia n-esima vuol dire andareal cilindro n-esimo. In Fig.1.2 é riportata la struttura di base del disco.

Se un disco é preparato con i valori di default, ogni settore contiene 512 byte di dati. La capacitátotale in byte di un disco é quindi data da: 512 · settori_per_traccia · tracce_per_piatto ·piatti_per_disco. Una partizione é una parte della divisione del disco. Generalmente le partizionisono divise lungo il con�ni di un cilindro. Quindi, come visualizzato in �gura, generalmente unapartizione contiene un numero intero di cilindri, e cosí la dimensione di una partizione é un multiplodel numero di byte contenuto in un cilindro.


Figura 1.2: Struttura del disco: tracce e settori

Per completezza, in Fig.1.3 si riporta l'immagine del disco IBM Ultrastar 36ZX, che ha unacapacitá di 36 GB e ruota a 10000 RPM. Il disco ha 10 piatti.

Come si é detto la dimensione standard di un settore é di 512 byte. Tuttavia ogni settorecontiene molto piú di 512 byte di informazione. Sono necessarie infatti ulteriori informazioni cheriguardano la struttura di controllo del settore, la gestione dell'unitá, la localizzazione dei dati ecosí via. Un settore puó essere visualizzato come una struttura di dati, come illustrato nella Fig.1.4.Naturalmente questo é solo un esempio, non é uno standard: i costruttori non sono tenuti a questastrutturazione. La struttura esatta del settore usata in un disco dipende dalle scelte di progettazionedel particolare costruttore.

I campi riportati in Fig.1.4 sono i seguenti:

ID L'ID identi�ca il numero del settore. É usato per localizzare il settore sul disco.

Stato Questa informazione indica se il settore é difettoso e, in questo caso, in quale settore é statorimappato.

Sincro Questa informazione é usata dal controller per guidare il processo di lettura dei dati.

Dati Sono i dati e�ettivi

ECC É il codice di correzione errore (tipicamente CRC) usato per assicurare l'integritá dei dati.

Gaps É il separatore tra i settori.

1.2.3 Il meccanismo di SEEK: posizionamento del sensore di lettura/scrittura

La prima operazione necessaria quando dobbiamo accedere ad un disco é quella di posizionare latestina di lettura/scrittura sul cilindro desiderato. Questa é l'operazione di seek ed é una com-ponente importante del tempo di accesso al disco. Per posizionare la testina di lettura/scritturabisogna muovere il braccio sul quale la testina é posizionata mediante un opportuno sistema dicontrollo automatico. Lo scopo del sistema di posizionamento é di assicurare che la testina appro-priata raggiunga la traccia richiesta nel tempo minore possibile e che rimanga ancorata su quella


Figura 1.3: Immagine del disco IBM ultrastar 36zx

Figura 1.4: Un settore


traccia nonostante ci possano essere vibrazioni esterne, colpi o imperfezioni meccaniche del disco(basta pensare a un piatto del disco non perfettamente concentrico per un difetto di fabbricazione).Quindi il compito del sistema di controllo é molto importante. La velocitá del braccio dipende dallapotenza applicata al motore che controlla il braccio, e dalla massa del braccio. Tipicamente, se sivuole dimezzare il tempo di posizionamento bisogna quadruplicare la potenza.

La prima fase del posizionamento é a catena aperta. La corrente di spunto da fornire al motoreper raggiungere una certa traccia é fornita da una tabella dove ad ogni distanza da percorrere éassociata l'appropriata corrente di spunto. Ovviamente la funzione corrente-distanza non é lineare;inoltre i dati cambiano con la temperatura e quindi devono venire ricalibrati. Dopo il primo po-sizionamento entra in gioco il controllo a catena chiusa. Il movimento di seek passa attraverso variefasi:

accelerazione Il braccio viene accelerato �no a raggiungere metá della distanza di seek oppure�no a raggiungere una velocitá massima pre�ssata. Buoni tempi di seek vengono raggiunticon accelerazioni di 30-40g. Questo vuol dire che il braccio deve essere molto robusto persopportare queste accelerazioni senza torcersi. Inoltre un braccio troppo �essibile a questeaccelerazioni puó mettere la testina di lettura/scrittura a contatto con il piatto povocandodanneggiamenti sullo strato magnetico. I dischi con diametro piú piccolo hanno distanze diseek piú piccole e bracci di lunghezza minore e di peso minore, che é piú facile da rendererigidi per resistere alle accelerazioni. Dischi di diametro minore hanno dunque minori tempi diseek. Per contro le dimensioni delle tracce sono minori e quindi la testina di lettura/scritturae il sistema di movimento devono essere molto pi�precisi e quindi pi'�costosi. La soluzione éovviamente un compromesso tra i due fattori.

navigazione In questa fase il braccio si muove ad una velocitá costante, che é la velocitá massimaraggiunta al passo precedente. Questa fase si veri�ca per lunghe distanze di seek.

decelerazione Il braccio viene fermato quando é vicino alla posizione desiderata.

posizionamento puntuale (settle time) Il controller del disco controlla il sistema di posizion-amento della testina in modo che si acceda la traccia precisa. In questa operazione si usal'informazione di identi�cazione memorizzata nel settore.

I seek molto corti sono dominati dal tempo di posizionamento puntuale che si aggira intorno a1-3 ms. Se la distanza di seek é corta, intorno a qualche centinaio di cilindri, il tempo é dominatodalla fase di accelerazione, e il tempo é proporzionale alla radice quadrata della distanza di seek.In�ne, seek lunghi sono dominati dl movimento a velocitá costante, e il tempo di seek é proporzionalealla distanza. Queste considerazioni sono riassunte nella Fig.1.5, dove é riportata la dipendenza deltempo di seek con la distanza di seek in cilindri, tenendo conto di tutte le considerazioni descrittein precedenza.

Il gra�co fá riferimento a un vecchio disco della HP, il modello C2200A. Il gra�co viene modellatocon la seguente relazione:

• Per distanze di seek < 616 cilindri, seek time = 3.45 + 0.597√

d

• Per distanze di seek ≥ 616 cilindri, seek time = 10.8 + 0.012d

Questo tipo di modellazione é generale e viene utilizzato con altri dischi, ovviamente cambiando icoe�cienti.

1.2.4 Inseguimento della traccia

Una volta che la testina é posizionata sulla traccia, deve essere mantenuta su quella traccia durantela rotazione del disco. Il sistema di inseguimento usa le informazioni che sono memorizzate sul disco


Figura 1.5: Dipendenza del tempo di seek dalla distanza di seek per il disco C2200A

dal costruttore nella fase del formattamento �sico del disco, che é quella fase nella quale il discoviene diviso in tracce e settori; dopo questa fase il disco si presenta come una matrice di blocchi didati ed é quindi pronto per memorizzare una struttura logica di �le system.

Il sistema di inseguimento traccia é fondamentale anche per realizzare un cambiamento di testinatra piatto e piatto. Quando il controller richiede di cambiare piatto sullo stesso cilindro, la nuovatestina deve generalmente riposizionarsi sulla traccia per via delle inevitabili di�erenze tra piatto epiatto. Stesso problema quando bisogna cambiare il cilindro, cioé passare da un cilindro al prossimo.Il tempo di questi cambiamenti (di piatto o di cilindro) é abbastanza simile, ed é tipicamente da1/3 a 1/2 del settle time.

1.2.5 Tempo di lettura/scrittura di un �le

Una volta posizionata la testina di lettura/scrittura sul cilindro, bisogna leggere o scrivere i datidal/sul disco e questo si realizza aspettando che la traccia, ruotando, presenti il settore sotto latestina. Una volta che il settore desiderato si trova sotto la testina, la lettura o scrittura si e�ettuaman mano che il settore scorre. Da quanto detto, si puó ritenere che il tempo di lettura/scritturasia la somma di quattro componenti:

1. tempo di seek, che é il tempo necessario per muovere il braccio del disco sulla tracciarichiesta,

2. tempo di latenza che é il tempo richiesto a�nché il disco, ruotando, presenta il settorerichiesto sotto il sensore di lettura/scrittura,

3. tempo di trasferimento, che é il tempo necessario per trasferire i dati dal/sul disco mag-netico.

4. tempo di elaborazione é il tempo richiesto dal controllore del drive per elaborare unarichiesta. Il controller deve anche eseguire i calcoli richiesti dagli algoritmi di ottimizzazionedelle prestazioni del disco.

In genere si considerano i primi tre fattori perché si puó ritenere che il tempo di elaborazionesia trascurabile rispetto agli altri dato che il controllore del drive é sempre piú potente; infattiattualmente si utilizzano dei processori di tipo DSP.

Questi tre fattori possono essere valutati come segue:

1.3 Tecniche di ottimizzazione delle prestazioni del disco 8

Tempo di seek É una funzione del numero di tracce percorse; dovrebbe essere valutato da gra�cicome quello riportato in Fig.1.5. In realtá si usa generalmente il tempo di seek medio che éun dato fornito dal costruttore del disco.

Tempo di latenza Si puó valutare come segue: se il disco ruota ad una velocitá v espressa in[RPM], il disco impiega 60/v secondi per compiere una rotazione. Allora, la latenza rotazionalesi puó ritenere sia mediamente metá del tempo di rotazione, cioé 0.5 · 60/v.

Tempo di trasferimento É il tempo nel quale passa sotto il sensore, ruotando, l'informazione.Se il una traccia ci sono N settori, un settore ruota in 1/N · 60/v secondi. Analogamente, sein una traccia ci sono M byte, la zona del settore che contiene 1 byte ruota in 1/M · 60/vsecondi. In altri termini, se in una traccia ci sono M byte, la zona del settore che contiene Bbyte ruota in B/M · 60/v secondi.

Questi dati possono essere usati per dare una idea del tempo di trasferimento in un �le. Facendoun esempio numerico, supponiamo che un disco con tempo di seek medio di 10 ms abbia settori di512 byte, 64 settori per traccia e che ruoti a 6000 RPM. Un piatto impiega quindi 60/6000 secondiper ruotare, cioé 0.01 secondi ovvero 10 ms. Il tempo di latenza medio é dunque di 5 ms. Per leggereuna traccia intera ci vogliono 10 ms e per leggere un settore ci vogliono 1/64 · 10ms = 0.15625 ms.

Se un �le di 256 Kbyte é memorizzato in maniera contigua, occupa 8 tracce contigue per untotale di 512 settori. Infatti una traccia memorizza 64[settori] · 512[byte/settore] = 32768 byte equindi 32768 · 8 = 262144 = 256 Kbyte. Il tempo di lettura/scrittura é dunque dato da: Tseek +Tlatenza + Ttrasferimento = 10ms + 5ms + 8 · 10ms = 95ms. Infatti c'é sono un seek per la primatraccia, poi il posizionamento sulle altre tracce avvene in tempo trascurabile.

Se lo stesso �le é memorizzato in modo completamente frammentato, bisogna considerare il fattoche ogni settore é acceduto in maniera indipendente. Il tempo di lettura/scrittura di un settore édato da: Tseek + Tlatenza + Ttrasferimento = 10ms + 5ms + 0.15625ms = 15.15625ms. L'intero �lerichiede 512 settori cioé 512[settori] · 15.15625ms/settore = 7.76secondi.

1.3 Tecniche di ottimizzazione delle prestazioni del disco

La valutazione riportata precedentemente riguarda l'uso di un disco nel quale le informazioni sonomemorizzate in due casi limite: nel caso in cui i byte sono memorizzati in sequenza e nel caso in cuii byte sono distribuiti in maniera completamente frammentata. In realtá i risultati si pongono inuna situazione intermedia. Anche in questo caso i tempi di lettura/scrittura sono molto alti essendodll'ordine dei secondi. É necessario quindi diminuire queti tempi, cosa che si ottiene con alcunetecniche di ottimizzazione che sono assolutamente necessarie.

L'ottimizzazione delle prestazioni di un disco riguarda essenzialmente due aspetti: la gestionedella coda di richieste e l'uso di una cache di disco. La struttura tipica di un disk drive (unitá didisco �sso) é infatti quella riportata in Fig.1.6.

1.3.1 Posizione di riposo della testina di lettura/scrittura

Dopo che il disco riceve ed esegue una richiesta, la testina di lettura/scrittura resta ferma sull'ul-tima traccia servita. Questa posizione é chiamata posizione di riposo della testina. Quando ildisco riceve un'altra richiesta, comincia a servirla dalla posizione di riposo. Qual'é l'in�uenza dellaposizione di riposo sulla distanza media di seek? c'é una posizione di riposo ottimale nel sensoche minimizza la distanza di seek? se cos'í fosse il braccio, dopo aver servito una richiesta, potrebbeessere posizionato nella posizione di riposo ottimale appro�ttando del tempo tra una richiesta el'altra, tempo nel quale il disco resta inattivo. La risposta a questa domanda é che sí, esiste una


Figura 1.6: Struttura tipica di una unitá disco �sso

Figura 1.7: Posizione di riposo


posizione di riposo ottimale. Il suo valore dipende dalla distribuzione statistica delle richieste. Ilproblema si puó visualizzare in Fig.1.8.

Il disco, cioé, numera le tracce partendo da 0, localizzato al centro del disco, ed ha un numero ditracce pari a Max. Inoltre la sua posizione di riposo é x. La nuova richiesta di traccia puó cadereo prima o dopo x e viene chiamata y. La lunghezza di seek é (y-x) se la richiesta cade dopo x, e(x-y) se la richiesta cade prima della posizione di riposo. Visto che i punti in cui cadono le richiesteseguono una certa distribuzione statistica, il valor medio della distanza si puó valutare come segue:

seek =∫ x

0(x− y)f(y)dy +

∫ Max

x(y − x)f(y)dy

dove f(y) é la funzione densitá di probabilitá. In pratica, la funzione non é facilmente rilevabileperché il meccanismo delle richieste dipende da molti fattori di�cilmente quanti�cabili, come ilcomportamento dei programmi e l'uso dell disk cache. Per mostrare che in certe condizioni esisteuna posizione ottimale, supponiamo che la distribuzione delle richieste sia uniformemente distribuita.In questo caso f(y)=1 e la soluzione é particolarmente semplice:

seek =∫ x

0(x−y)f(y)dy+

∫ Max

x(y−x)f(y)dy = x[y]x0−[

y2

2]x0+[

y2

2]Maxx −x[y]Max

x = x2−xMax+Max2

2

Si puó facilmente vedere che questa é una parabola rivolta verlo l'alto che ha un minimo per

x = Max/2

dove Max, ricordiam, é il massimo numero di tracce sul disco. Quindi la posizione di riposo ottimalese la distribuzione delle richieste é uniforme, é alla metá del disco. In realtá la distribuzione dellerichieste non é uniforme; tuttavia questa é una euristica utilizzata in certi sistemi operativi, adesempio in Unix BSD, dove i blocchi particolarmente utilizzati come gli Inode vengono messi appuntonella metá del disco.

1.3.2 Gestione della coda del disco

I processi fanno richieste di lettura e scrittura al disco. Le richieste sono caratterizzate dai seguentiparametri principali: quantitá di byte, tipo di operazione (lettura o scrittura) e indirizzo sul disco,cioé numero di blocco di disco. Il numero di blocco viene facilmente convertito in numero di tracciae numero di settore. Supponendo infatti che un blocco corrisponda per esempio ad un settore, persempli�care le cose, e sapendo che il numero di settori per traccia é S, si puó facilmente concludereche il blocco N corrisponde alla traccia N/S (divisione intera) e al settore N%S.

FIFO Questo tipo di gestione é ovviamente la piú semplice: le richieste vengono messe in codaman mano che arrivano e vengono servite con lo stesso ordine. Questo vuol dire che se peresempio le richieste sono relative, nell'ordine di arrivo, a tracce molto distanti, la distanza diseek (e quindi il tempo di servizio, diventa molto alta. Ad esempio, consideriamo il seguentecaso: le tracce richieste arrivato nell'ordine 98, 183, 37, 122, 14, 124, 65, 67 e che la posizionedi riposo della testina di lettura/scrittura prima di quest richieste é la traccia 53. La gestioneFIFO di queste richieste é descritta in Fig.1.8.

dalla quale emerge che la distanza di seek totale é di 640 tracce.

SSTF La gestione SSTF (Shortest Seek Time First) analizza tutte le richieste in coda, e scegliela richiesta piú vicina alla posizione corrente. Questa politica minimizza le tracce percorse.Considerando gli stessi dati del caso precedente, la distanza di seek totale diventa di 236tracce. Questo tipo di scheduazione delle richieste é visualizzato nella Fig.1.9.


Figura 1.8: Esempio di gestione della coda del disco con politica FIFO

Figura 1.9: Esempio di gestione SSTF


Figura 1.10: Strategia SCAN

Figura 1.11: Strategia CSCAN

Il problema di questa schedulazione é che se le maggior parte delle richieste sono localizzatein alcune tracce ravvicinate, tutte le altre richieste che sono relative a tracce piú distanti nonvengono servite, dando luogo ad un problema di starvation delle richieste. La soluzione allastarvation é fornita dalle politiche SCAN, CSCAN, LOOK, CLOOK. Generalmente questepolitiche forniscono peró un maggiore tempo d'accesso.

SCAN La strategia SCAN chiamata anche dell'ascensore, esplora il disco completamente andandodal centro all'ultima traccia esterna, per poi tornare velocemete al centro. Durante questocammino serve le richieste. Le richieste che arrivano durante questa esplorazione verrannoservite nella prossima esplorazione. In Fig.1.10 é riportato l'esempio della gestione SCANdella coda del disco.

Nelle stesse condizioni precedenti, il numero di tracce esplorate diventa 208.

CSCAN La testina si muove da un estremo del disco all'altro. Quando raggiunge la �ne ritornasubito all'inizio del disco e riparte. Il nome (Circular Scan) deriva dal fatto che le traccesono considerate come una lista circolare. Questa strategia produce un tempo d'attesa piúuniforme rispetto a SCAN ed é illustrata in Fig.1.11.

CLOOK Questa strategia rappresenta una versione ottimizzata di C-SCAN, nel senso che il braccioarriva �no all'ultima richiesta in una direzione e poi inverte la direzione senza arrivare altermine del disco. La politica CLOOK é illustrata in Fig.1.12.


Figura 1.12: Strategia di gestione CLOOK

1.3.3 Gestione della disk cache

L'uso di una cache nel drive puó migliorare sensibilmente le prestazioni del disco. Infatti, mem-orizzando parte delle informazioni del disco nella cache, si evita gran parte delle operazioni cherichiedono gli accessi alla meccanica, che sono i piú lenti. Un modo per gestire la cache nel drivedel disco é quello di memorizzare in cache una certa quantitá di informazioni che seguono quellerichieste. Se per esempio una richiesta riguarda la lettura di un settore, vengono letti e messi incache un certo numero di settori sequenzialmente memorizzati dopo il settore richiesto. É moltorobabile che questi dati siano utilizzati nel prossimo futuro. Come in tutte le gestioni della memoriacache, i dati vengono trattenuti in cache il piú a lungo possibile.

La cache consente di eliminare le componenti meccaniche, cioé il seek e la latenza. Iltempo di lettura/scrittura diventa quindi solo il tempo di trasferimento. Facendo riferimento all'e-sempio citato prima, la disk cache consente di leggere il �le contiguo in 8[tracce] · 10[ms/traccia] =80ms verso 95ms senza disk cache. Il tempo di lettura del �le frammentato diminuisce moltissi-mo, perché diventa pari a 512[settori] · 0.15625[ms/settore] = 80ms cioé lo stesso tempo dilettura/scrittura del �le contiguo.

1.3.4 La gestione degli errori nei dischi

Generalmente non ci si rende conto del fatto che é assolutamente normale che un disco abbia deglierrori durante la lettura delle informazioni memorizzate. Questo é un evento assolutamente normaleperché i dischi sono spinti ai limiti della tecnologia, facendoli lavorare con tracce vicinissime, conlivelli di magnetizzazioni bassi per evitare interferenze, con disturbi ad alta frequenza prodotti daimotori, citando solo i principali problemi. In queste condizioni é assolutamente normale avere erroridi lettura. Per questo motivo i dischi utilizzano codici di correzione errori per proteggere i dati.Questi codici funzionano cosí bene che l'utente si accorge dei problemi di lettura solo quando glierrori sono cosí grandi che non possono essere risolti. É importante notare che man mano che idischi sono piú capienti, usano la tecnologia a limiti sempre piú spinti e i codici sono sempre piúpotenti e complessi.

Sono stati sviluppati molti codici di protezione degli errori. Tra questi é importante considerarela famiglia di codici basati sull'algoritmo di Reed-Solomon, perché sono i piú semplici da decodi-�care e richiedono la minore quantitá di bit di protezione. Un altro importante codice é il CodiceRidondante Ciclico che viene utilizzato durante il trasferimento dei dati. Il CRC é un codice di rile-vazione degli errori. Se un traferimento produce errori, il traferimento viene ripetuto. Formalmenteil CRC si basa su divisioni tra polinomi nel campo GF(2), realizzati semplicemente in Hardware.

Appunti di Sistemi Operativi Enzo Mumolo e-mail address ...unina.stidue.net/Universita' di...

Documents

Transcript of Appunti di Sistemi Operativi Enzo Mumolo e-mail address ...unina.stidue.net/Universita' di...