riassunto sistemi operativi

FIFO:

Il primo algoritmo che osserviamo è l’algoritmo FIFO. La selezione della pagina vittima viene effettuata sulla

base della prima pagina che è stata caricata in memoria. La cpu deve eseguire molte traduzioni anche per lo

stesso frame, perché le pagine possono cambiare posizione in maniera dinamica tra i vari frame quindi

l’MMU deve ogni volta fare traduzioni logiche/fisiche.

L’algoritmo FIFO elimina quella arrivata prima, cioè la più vecchia. Con questo algoritmo nonostante

aumentiamo la memoria disponibile, cioè aumentiamo il numero di frame, non è detto che il numero di page

fault diminuisca. Tale problema viene chiamato anomalia di Belady. Questo algoritmo non è molto

efficiente: il numero di page fault rimane alto, infatti molto spesso posso richiedere la pagina che è stata

selezionata come vittima all’interazione precedente. (Non tiene conto della pagina più vecchia)

ALGORITMO OTTIMO:

L’algoritmo idealmente migliore di tutti è scegliere come pagina vittima quella che devo utilizzare il più tardi

possibile. Tale algoritmo è quello che produce il minor numero possibile di page fault. Tale algoritmo non

soffre dell’anomalia di Belady, quindi all’aumentare del numero dei frame, i page fault rimangono uguali o

diminuiscono. Però per funzionare ci serve sapere le richieste delle pagine, cosa che non possiamo sapere

a priori. Dobbiamo quindi stimare il comportamento dei processi nelle richieste delle pagine. Da questa stima

nascono due differenti tipi di algoritmi che stimano il comportamento in base a due fattori differenti:

• LRU — Least Recently Used

• LFU — Least Frequently Used

Least Recently Used:

Qui cerchiamo di stimare l’utilizzo di una pagina in funzione dell’ultimo utilizzo di quella pagina.

La pagina vittima è la pagina usata meno di recente. E’ una stima, non posso sapere se è quella che non mi

serve più davvero. Ha delle prestazioni intermedie, mediamente è comunque migliore dell’algoritmo FIFO ma

comunque non è ottimo. Questo algoritmo è realizzabile semplicemente andando a guardare cosa succede

nel passato. Non soffre dell’anomalia di Belady.

Least Frequently Used:

Un altro modo per capire se una pagina mi serve ancora oppure no, potrebbe essere quello di andare a

vedere la frequenza di utilizzo di una pagina. Se la uso frequentemente potrei riutilizzarla troppe volte:

mentre si seleziona la pagina vittima si va a guardare la pagina che uso meno frequentemente.

Ogni volta che utilizziamo una pagina, incrementiamo un contatore. Quando dobbiamo scegliere la pagina

vittima andiamo a scegliere il contatore più basso.

LRU e LFU hanno delle prestazioni simili in media. Anche LFU non soffre dell’anomalia di Belady. Questi

algoritmi però sono molto complicati da implementare. Possiamo implementarli con dei contatori: ogni

elemento delle pagine ha un contatore e quindi qualora avessimo:

• LRU, ad ogni riferimento alla pagina ci segniamo il valore del clock che viene copiato nel contatore.

• LFU, ad ogni riferimento alla pagina incrementiamo il valore del contatore.

Ma questo significa che la tabella delle pagine si appesantisce notevolmente se dobbiamo aggiungere anche

il time stamp o il contatore. Questo è un problema in quanto già avevamo problemi di spazio per tale tabella.

Se le dimensioni crescono il problema diventa più serio. Usare questo algoritmo comunque vuol dire che

ogni volta che viene richiesta una pagina, oltre tradurre l’indirizzo logico e fisico dobbiamo memorizzare il

time stamp nella tabella delle pagine, quindi andiamo ad aumentare il numero delle operazioni da fare, cosa

che invece cercavamo di diminuire in quanto rallenta il sistema. Soprattutto quando andiamo a selezionare

la pagina vittima dobbiamo cercare il minimo tra i time stamp, il che ha una complessità pari a O(n) e

dobbiamo anche scorrere tutta la tabella delle pagine che non è piccola. Diventa quindi un’operazione molto

onerosa per l’interrupt handler (anche per LFU valgono gli stessi discorsi).

Non possiamo quindi utilizzare i contatori per l’implementazione di questi algoritmi.

Possiamo invece implementarli con lo stack:

I numeri delle pagine sono organizzati in una lista doppiamente concatenata, ogni volta che c’è un

riferimento ad una pagina, il suo numero viene inserito/spostato in cima allo stack.

Quando bisogna selezionare una pagina, si sceglie quella presente in fondo allo stack —> la sostituzione

non richiede nessuna ricerca nella lista.

Ad ogni pagina in memoria centrale poi possiamo associare un bit di riferimento (dirty bit), il quale

inizialmente è zero. Ogni volta che c’è un accesso alla pagina, il bit viene posto a 1.

Se non si utilizza lo stack, la lista delle pagine è gestita come l’algoritmo FIFO: tuttavia, la pagina che viene

sostituita è quella col bit a 0 (se esiste).

Il bit dice se la pagina è stata usata recentemente, ma non mi dice l’ordine d’uso.

Una variante dell’algoritmo appena discusso è l’algoritmo dell’orologio. Anche qui viene utilizzato il bit di

riferimento: la lista delle pagine è una lista circolare gestita FIFO e quando viene selezionata una pagina

possono succedere due cose:

Se il bit di riferimento è a 0 —> la pagina viene sostituita

Se il bit di riferimento è a 1 —> il bit viene messo a 0, la pagina è lasciata in memoria e viene selezionata la

pagina successiva a cui vengono applicate le stesse regole

20. Prevenzione del deadlock con risorse a istanza singola (grafo di allocazione

risorse)

Discorso generale su deadlock e starvation:

La violazione del progresso viene chiamata stallo o deadlock, mentre quella dell’attesa limitata viene

chiamata starvation.

Deadlock (stallo) — due o più processi sono in attesa per un tempo indefinito di un evento che può essere

causato solo da un processo a sua volta in attesa.

Starvation — attesa indefinita. Un processo potrebbe non essere mai rimosso dalla coda di attesa in cui si

trova. Un esempio è quello del Test&Set.

Il deadlock si verifica quando sono verificate tutte e quattro le seguenti condizioni:

I. Mutua esclusione: soltanto un processo alla volta può utilizzare una risorsa.

II. Possesso e attesa: un processo in possesso di almeno una risorsa è in attesa di acquisire ulteriori

risorse possedute da altri processi.

III. Senza prelazione: una risorsa può essere rilasciata dal processo che la possiede solo volontariamente.

Nessuno è in grado di togliere la risorsa ad un processo se non il processo stesso.

IV. Attesa circolare: esiste un insieme {P0, P1, P2, …, Pn} di processi in attesa tale che P0 è in attesa di una

risorsa posseduta da P1, P1 è in attesa di una risorsa posseduta da P2, …, Pn-1 è in attesa di una

risorsa posseduta da Pn, e Pn è in attesa di una risorsa posseduta da P0.

Queste quattro condizioni sono condizioni necessarie ma non sufficienti, cioè che se un sistema è in

situazione di deadlock, queste quattro condizioni sono verificate, ma non vale il contrario: ovvero non è vero

che se sono verificate queste quattro condizioni, è possibile che il sistema non sia in stato di deadlock. La

condizione necessaria non ci basta, dobbiamo trovare una situazione per cui è condizione necessaria e

sufficiente.

Dopo questa introduzione sul deadlock, descriviamo il grafo di assegnazione delle risorse:

GUARDA DIRETTAMENTE SULLA DISPENSA

Le quattro condizioni sono necessarie e sufficienti se tutte le risorse sono ad istanza singola.

Possiamo quindi dire che:

• Se il grafo non contiene cicli ==> no deadlock

• Se il grafo contiene un ciclo ==> siamo in una situazione di possibile deadlock:

- Se esiste una sola istanza per ogni tipo di risorsa coinvolta nel ciclo, allora si ha deadlock.

- Se esistono più istanze per tipo di risorsa, potrebbe esserci la possibilità di deadlock (condizione

necessaria ma non sufficiente).

Quali sono i metodi di gestione del deadlock?

Esistono tre soluzioni differenti per prevenire le situazioni di stallo:

I. Progetto il mio SO in modo tale che non si verifichino le condizioni per cui siamo in una situazione di

stallo. Può essere molto costoso, ho bisogno di algoritmi di prevenzione. La si adotta quando siamo in un

modello in cui lo stallo può portare in situazioni pericolose (es.: controllo centrale, diga ecc. ecc..).

Situazione safety critical.

II. Periodicamente vado a controllare se sono in situazione di stallo. In quel caso cerco di rimediare al

problema. Qui devo definire invece degli algoritmi di ripristino. Situazioni in cui lo stallo non è proprio

pericoloso però devo poter rimediare a tale situazione. Es.: server web.

III. Non mi preoccupo della situazione di stallo. Lo ignoro perchè ritengo che una situazione di stallo si

verifica molto raramente e comunque gli algoritmi sono più costosi per il mio sistema che non ne ha

bisogno in quanto non è pericolosa la situazione di stallo e perdo efficienza. Es.: maggior parte dei SO.

PREVENZIONE DEL DEADLOCK

Per prevenire lo stallo basta che una delle quattro proprietà necessarie per il deadlock diventi falsa.

I. La mutua esclusione però non possiamo rimuoverla in quanto incorreremo in altri errori e problemi.

II. L’assenza di prelazione si intende quando il kernel toglie quella risorsa a quel processo perché

comunque tutti i SO sono in grado di togliere una risorsa ad un processo, quindi cambia il senso di tale

proprietà. Dobbiamo capire quindi quando togliere una risorsa per evitare di finire in situazione di stallo:

- Un processo ha già una risorsa che richiede un’altra risorsa che però non può essergli assegnata

quindi potrei togliergli la risorsa in quel momento, cioè nel momento in cui quel processo arriva in

situazione di possesso e attesa. Viene sospeso in attesa di averle entrambe e viene riattivato quando

quel processo può averle entrambe.

- Questo però vale solo nel caso in cui l’uso di una risorsa può essere tolto a quel processo, cioè quando

posso salvare lo stato dell’uso che il processo sta facendo di quella risorsa per poi riprenderlo. Non tutte

le risorse possono adattarsi a questa situazione.

III. Negare il possesso e attesa significa negare questa proprietà prima che si arrivi in prelazione cioè come

nei cinque filosofi non do nessuna risorsa qualora non possa prendere tutte le risorse che gli servono,

mentre nel caso sopra avevamo visto che già alcune risorse gli possono essere date. Questo caso qui va

bene sempre, solo che abbiamo un altro svantaggio, in quanto c’è un basso utilizzo delle risorse. Molti

processi possono non usare delle ris