Sartomiki.net

Si descriva, nell’ambito dei sistemi operativi UNIX, la gestione del “buffer cache” UNIX. A cosa serve? Come viene gestita la ricerca di un blocco? Cosa è la free list?
Per migliorare le prestazioni molti sistemi operativi riservano una sezione della memoria centrale separata per la gestione della cache del disco. Alcune versioni di UNIX utilizzano la cosiddetta buffer cache unificata, per eliminare il problema del double caching: le letture/scritture in memoria secondaria in un normale sistema senza cache unificata dovrebbero essere precedute da due ricerche in cache (una nella page cache, che memorizza le pagine in uso, e una nella buffer cache, che contiene la cache del disco per le classiche chiamate di sistema read()/write()). Il double caching crea problemi di coerenza tra le due cache e uno spreco di memoria. Una buffer cache unificata utilizza la stessa cache di pagina per memorizzare sia l’I/O mappato in memoria sia quello effettuato attraverso il file system.
Il funzionamento della buffer cache (BC) prevede che il kernel prima di effettuare un'operazione di I/O, cerchi se nella BC sia già presente il file. Se non lo trova esso viene copiato nella BC per eventuali usi successivi. I blocchi della BC che vengono modificati, vengono ugualmente tenuti nella BC per usi successivi. Le scritture su disco sono limitate, anche per i file modificati, poiché, mediante diversi algoritmi (come LRU), si cerca di definire quali file nella BC verranno riutilizzati.
Ogni campo della BC contiene spazio sufficiente per contenere un blocco del disco e un header, che contiene:
-numero del blocco
-2 puntatori alla free list
-2 puntatori per la coda di hash
-flag di buffer locked, attivo se il blocco è in uso
-flag per attivare il delayed write
-flag per contrassegnare se i dati sono validi
I record della BC liberi vengono memorizzati una lista circolare, detta free list.

Si descriva brevemente il meccanismo di gestione di un driver generico per i dispositivi di I/O, identificando le funzioni svolte da processo utente,  processo driver e interrupt handler. Che cosa si intende con il termine interrupt vector (vettore di interruzione)? Che differenza c’è, nei sistemi UNIX, tra un driver per dispositivo a caratteri e a blocchi?
Il meccanismo di gestione di un dispositivo di I/O avviene in diversi passi:
-il processo utente effettua una richiesta di I/O al SO
-il sottosistema di I/O del kernel, verifica se la richiesta può essere immediatamente soddisfatta (i dati si trovano già nella buffer cache), oppure invia la richiesta al driver del dispositivo corretto. Se la chiamata è bloccante, il processo viene messo in pausa.
-il driver del dispositivo elabora la richiesta e impartisce gli ordini direttamente al controllore
-il controllore del dispositivo esegue fisicamente le operazioni di I/O, e nel momento in cui ha terminato le operazioni invia un segnale di interruzione
-il gestore delle interruzioni riceve l’interruzione, memorizza i dati provenienti dal dispositivo, ed emette un nuovo segnale
-il driver del dispositivo salva in alcuni registri i risultati delle operazioni svolte
-il sottosistema di I/O trasferisce i dati al processo e riporta il codice di terminazione corretto L’interrupt vector table è una tabella di puntatori presente in memoria principale. In essa sono presenti tutti i puntatori alle procedure di gestione degli interrupt. Nel momento in cui viene sollevato un interrupt deve essere indicato il numero della procedura di gestione a cui si sta facendo riferimento.
Un dispositivo a caratteri trasmette un byte per volta (tastiera, mouse,…), mentre un dispositivo a blocchi trasmette blocchi di dato di dimensione variabile. I sistemi operativi, normalmente, gestiscono i dispositivi mediante interfacce.
L’interfaccia dei dispositivi a caratteri fornisce le funzioni di get() e put(), che permettono di leggere/scrivere un carattere sul dispositivo. E’ possibile implementare funzioni più complesse, come la cancellazione o la lettura di una riga.
L’interfaccia dei dispositivi a blocchi risulta invece più completa, in quanto sono presenti le interfacce per le funzioni write(), read() e seek(). Alcuni sistemi operativi consentono la lettura/scrittura diretta dei dispositivi a blocchi (raw disk) o anche l’I/O diretto, che permette di gestire parti di disco direttamente in memoria principale con in più la possibilità dell’accesso diretto.

Si descrivano le principali similitudini e differenze tra le strategie di schedulazione adottate nei sistemi operativi Windows a Linux. Si  considerino, in particolare, gli schemi di priorità (statica e dinamica), la gestione della preemption e dei processi real-time.
Lo schema di scheduling Windows prevede un algoritmo basato sulle priorità e su prelazione (è quindi possibile garantire che i thread vengano eseguiti in base alla loro priorità). Lo schema di funzionamento prevede 32 livelli di priorità. Le classi sono due:
-classe a priorità variabile (1-15), prevede che la priorità possa aumentare in caso di wait, in modo da permette ai processi interattivi di avere tempi di risposta veloci.
-classe real time (16-31).
Lo schema Windows prevede l’esistenza di un processo di sistema a priorità massima (0) e, nel caso in cui non ci sia nessun processo in esecuzione, la possibilità di eseguire un thread speciale (idle thread). Ogni thread ha un priorità derivante dalla classe di appartenza e una priorità interna alla classe stessa.
Lo scheduling di Linux è stato modificato recentemente, in quanto la versione standard di UNIX aveva problemi nella gestione degli SMP e non era scalabile.
Il nuovo scheduling si basa su priorità e prelazione e prevede l’esistenza di due classi, e 140 priorità:
-real time (0-99), con priorità statica
-nice (100-140), con priorità dinamica, che varia a seconda del grado di interattività del processo (il dispatcher somma o sottrae 5 gradi di priorità a seconda del tempo di attesa delle operazioni di I/O).
Linux gestisce le code di priorità mediante due vettori, ordinati per priorità. In un vettore sono presenti i processi da eseguire, nell’altro tutti quelli che hanno esaurito il proprio quanto di tempo. Quando la prima coda è vuota, le code cambiano di ruolo.

Si descrivano brevemente , nell’ambito dell’organizzazione RAID per dischi magnetici, i concetti di striping, mirroring (shadowing), parità.  Si dica infine perché esistono più livelli di RAID (da RAID-1 a RAID-6).
-STRIPING. Supponiamo di avere un insieme di X dischi fisici, ognuno di essi contiene dei dati e nel caso di guasto tali dati vanno interamente persi. Lo striping è una tecnica per cui i dati vengono suddivisi in “striscie”, ovvero blocchi di una certa dimensione, e mescolati fra i dischi che compongono l'array RAID. Aggiungendo un certo numero di striscie contenenti il controllo d'errore, e quindi sacrificando una certa quantità di spazio, e organizzando opportunamente la dislocazione delle striscie è possibile ricostruire i dati persi nell'eventuale guasto di uno o più dischi.
-MIRRORING. Tecnica che consiste nel duplicare esattamente il contenuto di un disco in un secondo disco, effettuando gli accessi ai dati comese fosse effettivamente presente un disco solo. Ciò permette di aumentare le prestazioni in lettura e di ridurre la probabilità di perdita dei dati in caso di guasti.
-LIVELLI RAID. Sono le possibili configurazioni di un array di dischi ed esistono per motivi di evoluzione storica e flessibilità. Il progettista sceglie il livello di RAID principalmente in base a due parametri: affidabilità (in altre parole quanto spazio disco si vuole sprecare per i codici di controllo) e prestazioni (in altre parole quanto spazio disco si vuole sprecare per il parallelismo).

Si descrivano brevemente, nell’ambito dell’organizzazione fisica dei dischi magnetici, i concetti di traccia, settore, cilindro, testina. Si dica cosa si intende con “seek time”, latenza rotazionale, tempo di posizionamento, tempo di trasferimento. Si dica infine quali criteri vengono utilizzati (e perché) per la schedulazione efficiente degli accessi a disco.
Un disco è composto da uno o più piatti sovrapposti in rotazione sul medesimo asse. Una traccia è una “circonferenza” di un piatto contenente i dati fisici uno dietro l'altro, divisi in settori (“spicchi” di traccia). Un cilindro è l'insieme delle corrispondenti tracce di ogni piatto. Ogni piatto dispone inoltre di una testina in grado di spostarsi su tutte le traccie, in modo solidale con le testine degli altri piatti.
Il tempo di posizionamento è quanto necessario alla testina per collocarsi sopra il settore richiesto e si divide in due componenti:
seek time (ovvero il tempo necessario a raggiungere la traccia) e latenza rotazionale (ovvero il tempo necessario affinché il piatto, ruotando, porti il settore desiderato sotto la testina). Il tempo di trasferimento, solitamente molto più piccolo del tempo di posizionamento, è quanto necessario a leggere i dati e trasferirli alla memoria principale.
FCFS, First Come First Served. Le richieste vengono soddisfatte in ordine di arrivo.
SSTF, Shortest Seek Time First. Ad ogni passo si sceglie la richiesta caratterizzata dal seek time più basso. Può causare starvation (richieste in attesa infinita).
SCAN. La testina continua a spostarsi dalla prima all'ultima traccia e a tornare indietro fermandosi di volta in volta su ogni traccia per la quale esista una richiesta pendente. La variante C-SCAN effettua la scansione delle tracce in una sola direzione.
LOOK. Una variante di SCAN in cui una volta raggiunta la traccia verso l'esterno (o verso l'interno) per cui oltre non vi sono richieste pendenti si inverte la direzione della scansione. La variante C-LOOK effettua la scansione delle tracce in una sola direzione (ovvero arrivati alla richiesta più “esterna” si riparte a scandire dalla più “interna” o viceversa).

Si descrivano le principali caratteristiche del sistema di I/O Unix. In particolare, se ne descriva la collocazione nell’architettura del sistema operativo. Si descrivano i sotto-sistemi di I/O e si discuta infine la relazione tra I/O system e file system.  
Nel sistema per l’I/O di Unix tutti i driver dei dispositivi, nei limiti del possibile, sono  rappresentati come file ordinari. L’utente apre un canale d’accesso a un dispositivo nello stesso modo in cui apre un file qualunque: i dispositivi possono comparire come oggetti del file system. All’interno del file system possono esserci file speciali con riferimenti a un driver specifico, e un utente che apre tale file potrà leggere e scrivere nel dispositivo associato.
I dispositivi sono suddivisi in tre classi: dispositivi a blocchi, dispositivi a caratteri e dispositivi di rete.

Si dica che cosa sono (e a cosa servono), nell’ambito di un sistema operativo Unix, le seguenti tabelle:
Switch tables (si dica anche quante sono e di che tipo), Partition tabe, Tabella dei descrittori dei file dell'utente utente, Tabella dei file, Tabella degli Inode:
-Switch table: tabella usata per accedere ai device drivers. C’è una switch table per i dispositivi a blocco e una per i dispositivi a carattere. Ogni dispositivo è caratterizzato da un device number composto di due parti: la prima è usata come indice nella switch table, la seconda per selezionare la corretta sottounità del dispositivo.
-Partition table: tabella che contiene la descrizione delle partizioni. Ad esempio il SO usa questa tabella per vedere se una partizione contiene un file system a cui si vuole accedere.

-Tabella dei file: L'apertura di un file implica l'aggiunta di una voce nella tabella dei file di sistema (ovvero dei file aperti complessivamente nel sistema operativo). Le voci di questa tabella devono avere un riferimento all'inode, la modalità di apertura (lettura, scrittura o entrambe), la posizione corrente nel file per le letture o le scritture successive, un contatore di riferimenti interni.

-Tabella degli Inode: Quando si accede a un file per la prima volta, le informazioni relative al suo inode vengono caricate in una voce della tabella degli inode. Ogni voce contiene almeno: il numero dell’inode, il tipo di file e i permessi d’accesso, il numero UID del proprietario del file, il numero GID del proprietario del gruppo, la dimensione del file, le date di accesso e modifica del file e di creazione dell’inode, la quantità di riferimenti provenienti dalla directory, una serie di numeri di blocchi occupati dal file o dalla directory.

-Tabella dei descrittori dei file: Ogni processo elaborativo ha una propria tabella dei descrittori dei file, nella quale, le voci rappresentano i file aperti dal processo stesso. Le voci della tabella includono il riferimento alla tabella dei file di sistema e le opzioni date in fase di apertura, riguardanti aspetti più precisi rispetto alla semplice distinzione di un accesso in lettura o in scrittura.

Si dica cosa sono, nell’ambito della gestione della memoria, TLB e inverted page table. Se ne descrivano brevemente le funzioni, mettendo in evidenza similitudini e differenze.
-TLB (translation look-aside buffer): è una piccola cache di ricerca veloce che permette di risolvere il problema del doppio accesso alla memoria. È una memoria associativa ad alta velocità in cui ogni suo elemento consiste di due parti: una chiave o un  identificatore (tag) e una valore. Quando si presenta un elemento la memoria associativa lo confronta contemporaneamente con tutte le chiavi; se trova una corrispondenza riporta il valore correlato. La ricerca è molto rapida ma le memorie associative sono molto costose. Il numero di elementi di una TLB è piccolo, tra 64 e 1024.
Se l’indirizzo cercato non si trova nella TLB si ha un TLB miss e bisogna consultare la tabelle delle pagine in memoria per ottenere il numero del frame desiderato e inserirlo nella TLB (così il prossimo accesso sarà più veloce).
-Inverted page table: è una tabella delle pagine con un elemento per ogni frame. Ciascun elemento è quindi costituito dall’indirizzo virtuale della pagina memorizzata in quella reale locazione di memoria, con informazioni sul processo che possiede tale pagina. Quindi nel sistema esiste una sola tabella delle pagine che ha un solo elemento per ciascuna pagina di memoria fisica. Questo schema aumenta il tempo di ricerca nella tabella: infatti le ricerche si svolgono per indirizzi virtuali, mentre la tabella è ordinata per indirizzi fisici.

Si dica, nell’ambito della gestione del buffer cache UNIX, che cosa sono “read ahead” e “delayed write”. In che modo possono migliorare le prestazioni di accesso a disco ? Si descriva brevemente la struttura dati utilizzata per gestire i blocchi (in memoria) del buffer cache.
Con l’uso del buffer cache Unix, i blocchi modificati sono messi in una free list, in attesa di essere scritti su disco.
Con il delayed write non viene fatto il salvataggio per ogni modifica fatta perché si prevede che in futuro saranno svolte altre modifiche. In questo modo si riduce il numero di accessi a disco.
Con il read ahead invece, carico nella cache il contenuto di file che con elevata probabilità saranno richiesti dai processi: anche questo viene fatto per ridurre gli accessi a disco.

Si dica che cos’è, nell’ambito della gestione della memoria virtuale, il bit di validità. Si dica poi dove viene memorizzato e come viene utilizzato.
Il bit di validità è un bit che si aggiunge per ogni entry della tabella delle pagine per verificare la validità dei frame. Se un frame è valid significa che si trova in memoria e può essere acceduto subito; se un frame è invalid significa che la pagina richiesta non appartiene allo spazio di indirizzi logici del processo oppure è una pagina valida ma che attualmente sta su disco. L’elemento della tabelle delle pagine corrispondente a una pagina che attualmente non è in memoria è semplicemente contrassegnato come non valido oppure contiene l’indirizzo che consente di trovare la pagina dei dischi.

Si descrivano le principali caratteristiche di una FAT (File Allocation Table): di cosa si tratta, quali vantaggi/svantaggi presenta rispetto a schemi alternativi di organizzazione di file. Si descriva un esempio di uso della FAT per un file che richieda almeno 3 blocchi.
La FAT (file allocation table) è una variante del metodo di allocazione concatenata, ed è usata nei sistemi operativi MS-DOS e OS/2. Per contenere tale tabella si riserva una sezione del disco all’inizio di ciascun volume; la FAT ha un elemento per ogni blocco del disco ed è indicizzata dal numero del blocco. L’elemento di directory contiene il numero del primo blocco del file. L’elemento della tabella indicizzato da quel numero di blocco contiene a sua volta il numero del blocco successivo del file. Questa catena continua fino all’ultimo blocco, che ha come elemento della tabella un valore speciale di fine del file. I blocchi inutilizzati sono indicati nella tabella da un valore 0. l’allocazione di un nuovo blocco a un file implica semplicemente la localizzazione del primo elemento della tabella con valore 0 e la sostituzione del valore di fine del file precedente con l’indirizzo del nuovo blocco; lo 0 è quindi sostituito con il valore di fine del file.
Uno svantaggio di questo tipo di allocazione è il numero significativo di spostamenti della testina: prima devo leggere la FAT e poi spostarmi al blocco richiesto.
Un vantaggio invece è dato dall’ottimizzazione del tempo d’accesso diretto, poiché la testina del disco può trovare la locazione di ogni blocco leggendo le informazioni contenute nella FAT.

Si descrivano, nell'ambito della schedulazione di processi, le multilevel feedback queues, facendo notare, in particolare, la politica di schedulazione realizzata e i criteri di ottimalità scelti a tale scopo.
L’algoritmo di scheduling delle multilevel feedback queues (code multiple con retroazione) prevede una gestione dinamica dei processi nelle code: l’assegnazione dei diversi processi a diverse code non è rigida, come invece avviene per lo scheduling  a code multiple. Dopo una iniziale assegnazione dei processi alle varie code, ciascuno dei processi può cambiare coda: se un processo usa la cpu per troppo tempo (non termina entro il quanto di tempo della coda in cui si trova) viene spostato in una coda con priorità più bassa, se invece attende tanto per accedere alla cpu lo si può spostare in una coda a priorità più alta. Si cerca quindi di fare si che se il processo dura di più, verrà interrotto di meno. In questo modo si evita la starvation dei processi. Quindi, i processi della coda a priorità più alta che non terminano nel quanto di tempo di questa coda, vengono spostati in fondo alla coda successiva. Se poi la prima coda risulta vuota (perché non arrivano nuovi job nel frattempo) si fa partire i processi della seconda coda, che a questo punto avranno un quanto di tempo maggiore rispetto a quello della coda superiore. Analogamente per le code successive. In generale un processo ottiene la cpu solo se non c’è nessun processo nelle code superiori. Ogni coda prevede una politica di schedulazione locale.

Sia dato un sistema operativo Unix, con gestione dei blocchi su disco basata su “buffer cache”. Se ne illustri brevemente il relativo meccanismo di gestione della “free list”. Si dica poi come viene gestito nella free list un blocco identificato come “delayed write”. E’ possibile che un blocco sia contemporaneamente presente nella “free list” e nella tabella di hash del “buffer cache” (si giustifichi la risposta)?
Per evitare continui accessi sul disco viene implementata una gestione dei blocchi basata su una free list e una hash table. I buffer liberi stanno in una free list circolare, mentre i blocchi in uso sono messi nella hash table: il kernel, quando ha bisogno di un buffer, lo preleva dalla testa della free list e inserisce i buffer appena liberati (i buffer non più in uso) in coda (gestione LRU dei buffer liberi).  Quando ho bisogno di un blocco, prima lo cerco nella hash table e, se non c’è, prelevo il primo buffer dalla free list, ci carico il blocco richiesto dal disco e lo metto nella hash table. Quando poi il blocco non è più in uso rimetto il buffer in coda alla free list.
Un blocco delayed write è un blocco che è stato modificato e che, non essendo più in uso, si trova nella free-list e in attesa di essere salvato su disco: il kernel incomincia la scrittura asincrona su disco del buffer e a scrittura completata reinserisce il buffer appena scritto in testa alla free list (per evitare un giro a vuoto del buffer e rispettare la gestione LRU); seleziona il prossimo buffer della free list e, se anche questo è marcato delayed write, ripete l’operazione di scrittura. Il meccanismo dei delayed write permette di evitare scritture su disco inutili: alcuni file infatti vengono aggiornati molto frequentemente e non conviene fare salvataggi a ogni modifica.
Un blocco può essere presente contemporaneamente nella free-list e nella hash: in generale un blocco, una volta caricato in un buffer, sta sempre in hash e, se non è più in uso, viene messo in coda alla free list, rimanendo però anche nella hash.