Sistemi operativi: risposte alle domande d'esame ed esercizi svolti

Per tenere traccia del tempo l'algoritmo è implementato aggiungendo ad ogni entrata nella tabella

della pagine un campo che indica il tempo ogni volta che una pagina viene riferita. La CPU deve

mantenere aggiornato un contatore, incrementato ad ogni istruzione, che tiene traccia del tempo

che passa ed è utilizzato per aggiornare il campo nella tabella. Il sistema seleziona la pagina che ha

il tempo minore. Non è molto vantaggioso per vari motivi (devono essere aggiunte informazioni

nella tabella che ne aumentano la dimensione, per selezionare la pagina il sistema deve fare una

scansione di tutta la lista, occorre stabilire un numero di bit per il contatore che non sia troppo

grande per aumentare troppo la dimensione della tabella e che non sia troppo piccolo per

contenere il valore del contatore).

• Algoritmo con bit supplementari di riferimento (NFU) (not frequently used): approssimazione del

LRU che si ottiene memorizzando ad intervalli regolari bit di riferimento delle pagine, l'algoritmo

seleziona la pagina da più tempo non riferita. Questo algoritmo tiene traccia della frequenza con

cui vengono riferite le pagine anche attraverso il bit RB. Il sistema mantiene una tabella in

memoria contenente per ogni pagina un registro in traslazione che funziona da contatore.

Periodicamente una routine va in esecuzione e, per ogni pagina, trasla il contenuto del registro a

destra e inserisce il valore del bit RB a sinistra. Quando si verifica un page-fault, il sistema

seleziona per il rimpiazzamento la pagina con il contatore più basso

• Algoritmo con bit di riferimento a seconda chance: con una semplice modifica dell'algoritmo FIFO

è possibile evitare il problema della rimozione di pagine molto utilizzate. Viene controllato il bit RB

della pagina più vecchia: se vale 0 la pagina viene sostituita; se vale 1 il bit viene azzerato e la

pagina viene messa in coda alla lista come se fosse appena arrivata in memoria e viene consultata

la pagina successiva fino a quando non se ne trova una con RB=0 che verrà sostituita.

L'algoritmo si basa sulla ricerca di una pagina che non sia stata referenziata nell'ultimo giro di

clock; se tutte le pagine sono state referenziate nel giro di clock allora sfocia nel FIFO puro.

• Algoritmo di CLOCK: (come seconda chance con lista circolare) il sistema realizza questo algoritmo

utilizzando una lista circolare di pagine o di descrittori di pagina. Ad ogni pagina associa un bit RB

che inizialmente è settato ad 1. Quando si verifica un page-fault il sistema scansiona la lista

partendo da dove si trova il puntatore della lista e ogni volta che individua un pagina con RB=1 lo

setta a 0 e prosegue fino a quando non trova una pagina con RB=0 (non necessariamente quella

non più tempo) che viene scelta per il rimpiazzamento. Alla prima scansione, quando tutte le

pagine hanno RB=1 , prima vengono settate tutte con RB=0 e poi viene rimpiazzata la prima della

lista.

• Modello a Working Set (prepaging): a differenza degli altri algoritmi questo modello non utilizza la

paginazione su richiesta, ma il prepaging. Poiché la maggior parte dei processi esibiscono la

località degli accessi (durante qualsiasi fase dell'esecuzione il processo fa riferimento ad un piccolo

insieme di pagine) prima di eseguire un processo viene caricato in memoria centrale il working set

del processo. In generale invece di inserire una sola pagina in memoria ad ogni richiesta, si

inseriscono più pagine in modo da avere più pagine possibili del working set in memoria centrale ,

così da ridurre i page-fault.

Quando un programma causa page-fault per ogni piccolo insieme di istruzioni viene detto in thrashing,

cioè in memoria sono presenti troppi processi. Per evitare il thrashing viene utilizzato un processo

chiamato Paging Demon che è eseguito in background e che periodicamente controlla lo stato della

memoria e, se il numero di frame liberi in memoria non è sufficiente, si occupa di selezionare le pagine

da eliminare (secondo un algoritmo scelto).

La memoria secondaria rappresenta la parte più bassa del file system. La parte del sistema operativo che

si occupa della gestione della memoria deve implementare degli algoritmi di scheduling che ordinano la

sequenza delle operazioni di I/O ai fini di migliorare le prestazioni di sistema.

Il disco è gestito dal controllore. Quando arriva una richiesta di lettura o scrittura il driver controlla

prima se il dispositivo è libero o occupato, poi esegue opportune operazioni di traduzione. Il controllore

deve inoltre gestire la coda delle richieste pendenti da cui estrae i processi secondo determinate

politiche. I dischi sono dispositivi lenti e la durata delle operazioni di lettura o scrittura che lo

coinvolgono dipende da tre fattori:

• seek time: tempo impiegato per individuare la traccia che contiene il blocco fisico; proporzionale

alla distanza che la testina deve percorrere ad ogni spostamento.

• Latency: tempo che occorre per trovare il settore all'interno della traccia.

• Transfer time: tempo di lettura vero e proprio e trasferimento dati.

L'unica componente su cui si può agire per diminuire il tempo complessivo è il seek time. Se arriva una

richiesta quando il disco è libero, il sistema la serve normalmente. In questa situazione non esiste alcun

rimedio alla riduzione del tempo di esecuzione. Se il disco è occupato il sistema può agire sul seek time

sfruttando algoritmi di scheduling.

Inoltre per ridurre i tempi si cerca anche di sfruttare il principio di località per diminuire gli accessi al

disco. Quando riceve una richiesta il sistema legge non solo il settore che contiene la richiesta ma anche

alcuni settori successivi. Il driver riceve le informazioni che aveva richiesto e quelle lette in più vengono

memorizzate in una cache. In questo modo quando il driver riceve una richiesta che coinvolge settori

presenti nella cache il sistema non accede al disco, ma i dati da passare al driver vengono prelevati dalla

cache.

Algoritmi:

• FCFS (first come first-served): organizza la lista delle richieste pendenti secondo l'ordine di arrivo.

L'inserimento e l'estrazione delle richieste risulta semplice, ma questo algoritmo non permette di

migliorare le prestazioni del sistema dal punto di vista del seek time.

Questo algoritmo offre basse prestazioni poiché effettua un gran numero di spostamenti della

testina.

• SSTF (shortest seek time first): minimizza i tempi di ricerca. Il sistema serve le richieste in base alla

posizione della testina: seleziona dalla coda delle richieste pendenti quella più vicina alla testina in

migliorare le prestazioni del sistema dal punto di vista del seek time.

Questo algoritmo offre basse prestazioni poiché effettua un gran numero di spostamenti della

testina.

• SSTF (shortest seek time first): minimizza i tempi di ricerca. Il sistema serve le richieste in base alla

posizione della testina: seleziona dalla coda delle richieste pendenti quella più vicina alla testina in

quell'istante. L'inserimento nella coda è ancora semplice ma la selezione prevede lo scorrimento

di tutta la lista per scegliere la richiesta.

Questo algoritmo introduce starvation: se una richiesta è troppo lontana rispetto alle altre

richieste che continuano ad arrivare in coda, non verrà mai servita. Al contrario le richieste

favorite sono quelle che richiedono blocchi posizionati nelle tracce centrali al disco.

• SCAN: effettua una scansione di tutte le tracce. Il braccio del disco parte da un estremo, si sposta

nella sola direzione possibile servendo tutte le richieste che incontra sui cilindri, fino a raggiungere

l'estremo opposto del disco. A questo punto viene invertita la direzione e riparte a servire le

richieste (fa avanti indietro percorrendo ogni volta tutto il disco).

Questo algoritmo elimina la starvation poiché tutte le richieste vengono servite. Il tempo massimo

per soddisfare una richiesta è pari al tempo di percorrenza di due volte il disco. In generale è

peggiore del SSTF.

• C-SCAN: Variante dello SCAN che ha un solo senso di percorrenza del disco: parte da un estremo

per arrivare fino all'altro e una volta raggiunto riparte dall'estremo iniziale, cioè non effettua un

"viaggio di ritorno". Di fatto il disco qui viene trattato come una lista circolare

• LOOK: due algoritmi (LOOK e C-LOOK) che derivano da SCAN e C-SCAN che si basano sull'idea che

risulta inutile arrivare fino in fondo al disco se non ci sono più richieste oltre una determinata

traccia, quindi la testina si sposta finché ci sono richieste da servire, finite riparte all'inizio.

La crittografia è lo studio dei metodi per rendere un messaggio non comprensibile (la steganografia si

occupa di nasconderlo) a chiunque non sia il legittimo destinatario.

I sistemi crittografici si classificano in base a tre criteri: tipo di operazioni per passare da testo in chiaro a

testo cifrato; numero di chiavi usate; modo di elaborazione del testo in chiaro (a blocchi o a stream).

La crittografia è costituita da due campi: crittografia a chiavi pubblica (chiave asimmetrica) e crittografia

a chiave privata (chiave simmetrica). Ek(M)=C, Dk(C)=M Dk(Ek(M))=M.

La cifratura a chiave privata (simmetrica) prevede che i due utenti che dialogano condividano la stessa

chiave per avere un canale sicuro, tuttavia c’è il problema di come condividere la chiave. In particolare

questo metodo ha il problema della scalabilità, ovvero per garantire che tutti gli utenti abbiano un

canale sicuro con tutti gli altri il numero di chiavi è dell’ordine di N^2 (N numero di utenti).

La cifratura a chiave pubblica (asimmetrica) prevede che ciascun utente possegga una chiave che è

pubblica e pertanto visibile a tutti. In questo modo se A vuole mandare un messaggio a B, A utilizza la

chiave pubblica di B per cifrare il messaggio in modo tale che solo B sia in grado di decodificare il

messaggio tramite la sua chiave privata. Tuttavia chi riceve non è sicuro dell’identità del mandante

(problema “uomo nel mezzo”).

I messaggi firmati a differenza del metodo a chiave pubblica consentono di garantire l’identità di chi

scrive: A manda un messaggio a B cifrando il messaggio con la sua chiave privata (di A) e B la decifra

utilizzando la chiave pubblica di B. Tuttavia in questo modo il messaggio non è segreto ma tutti possono

leggerlo.

La soluzione a tutti i problemi è la presenza di un intermediario di fiducia, ossia il centro di distribuzione

delle chiavi (KDC). Se A e B vogliono comunicare con il metodo della chiave privata, KDC è un server che

condivide chiavi segrete con ciascun utente registrato, in questo modo A e B ricevono entrambe una

chiave privata individuale (una per A diversa da una per B) per comunicare con KDC. Ottenute le due

chiavi A comunica con KDC