Teoria Sistemi operativi

Il conoy effect è un fenomeno che si verifica nell’algoritmo di scheduling FCFS, esso consiste in più processi

I/O Bound che attendono che un processo CPU Bound termini di utilizzare la CPU. SI puo risolvere in diversi

modi:

 Algoritmo di scheduling a priorità con processi I/O Bound che hanno priorità maggiore dei processi

CPU Bound

 Algoritmo SJF

 Algoritmo di schedulazione Round Robin assegna un quanto di tempo di CPU ad ogni processo

gestendo la coda di ready come una lista circolare.

Short-term scheduler e long-term-scheduler

Lo schedulatore a lungo termine si occupa di inserire i processi pronti nella coda dei ready

Lo schedulatore a breve termine si occupa di scegliere a quale processo allocare la cpu

CAPITOLO 7 : SINCRONIZZAZIONE

Un semaforo gestisce la sincronizzazione imponendo interattivamente un blocco attivo durante l’attesa

(SPIN LOCK). Lo spin lock viene utilizzato per impedire che più processi o più thread possano accedere

simultaneamente ai dati condivisi e modificabili. Quindi i processi o i thread chiedono l’accesso ai dati

condivisi protetti da uno spin lock che controlla se l’accesso è disponibile, se non lo è il processo il thread

rimane in attesa.

Il semaforo è composto da:

- acquire() : metodo per accedere al semaforo

- relase() : metodo per rilasciare il semaforo

Per essere implementato necessita ovviamente che due thread o processi possano condividere memoria.

Il fenomeno del busy waiting nei semafori.

Quando un thread T1 vuole entrare nella propria sezione critica ed effettua un acquire(S), ma un altro

thread T2 è già all’interno della propria sezione critica, quindi S<=0, allora T1 entra in un ciclo di attesa

attivo fin quando T2 non effettua un release(S), ossia busy waiting, questo spreca cicli di CPU.

Per risolverlo si introducono altri due metodi:

block () : richiamato dopo acquire() dal thread quando entra in un ciclo di attesa attivo, in modo da essere

sospeso e rilasciare la CPU

wakeup () : richiamato da un altro thread quando lascia la sua sezione critica per svegliare il thread sospeso

da block().

CAPITOLO 8 : DEADLOCK

Le condizioni necessarie e sufficienti per identificare uno stato di deadlock sono:

Mutua esclusione : le risorse devono essere accessibili solo da un processo per volta

 No preemption : non è possibile sottrarre ad un processo una risorsa che ha già acquisito

 Hold and wait : un processo possiede delle risorse ed attende risorse in possesso da altri processi

 Circular wait : processo attende una risorsa in possesso di un altro processo che a sua volta attende

 una risorsa in possesso da un altro processo in maniera ciclica

Queste quattro caratteristiche devono essere vere contemporaneamente affinché si posso verificare lo

stato di deadlock.

Hold and wait è una delle quattro condizioni che devono essere vere affinché si possa verificare un

deadlock, consiste nel fatto che un processo che detiene delle risorse attende delle risorse in possesso da

altri processi.

Il contesto in cui si colloca è nel contesto del deadlock prevention, ossia si cerca di rendere non vera una

delle quattro condizioni.

Per rendere non vera la caratteristica di hold and wait bisogna far si che un processo che richiede delle

risorse non ne detenga altre, quindi un processo o chiede ed ottiene tutte le risorse di cui ha bisogno per

completare la sua esecuzione oppure può richiedere delle risorse solo nel momento in cui non ne detiene

altre.

Questo può portare ad uno spreco di risorse in quanto il loro utilizzo risulta poco efficiente, inoltre si può

verificare la starvation, ossia processi che richiedono delle risorse molto usate e attendono

indefinitivamente.

Una volta rilevato un deadlock, una possibile soluzione consiste nel rilascio anticipato delle risorse da

parte di un processo, ossia effettuare una prelazione delle risorse, le problematiche relative a questa

soluzione sono:

- Bisogna stabilire quali risorse e quali processi si devono sottoporre a prelazione considerando dei

fattori di costo come numero di risorse occupate e tempo di elaborazione del processo

- Bisogna effettuare un rollback del processo in modo da riportarlo ad uno stato sicuro

- Si può incontrare la starvation di un processo, in quanto può accadere che il rollback e il rilascio

delle risorse vengano effettuate sempre allo stesso processo

Una soluzione alla starvation consiste nel verificare che un processo possa subire la prelazione delle sue

risorse un numero limitato di volte, includendo il numero di rollback effettuati sul processo all’interno dei

fattori di costo

CAPITOLO 9 : MEMORIA CENTRALE

La frammentazione è un problema dell’allocazione dinamica della memoria ai processi, e può essere :

Frammentazione esterna : c’è abbastanza spazio di memoria per soddisfare la richiesta di un

 processo, ma questa non è contigua ma frammentata, quindi per soddisfare la richiesta del

processo va effettuata una compattazione, cosa non banale se la rilocazione degli indirizzi dei

processi non è dinamica e fatta in tempo di esecuzione

Frammentazione interna : ad un processo viene allocata una porzione di memoria leggermente

 maggiore rispetto a quella di cui necessita, questo spazio di memoria in più risulterà inutilizzato e

quindi sprecato.

La segmentazione è una tecnica di suddivisione logica dello spazio di indirizzamento di un processo in

segmenti di codice di dimensioni diverse che hanno la stessa funzione. Si allocano in memoria i singoli

segmenti e non l’intero processo con algoritmi di allocazione dinamica, poiché i segmenti non sono di

dimensione fissa ma eterogenea, si presenta il problema della frammentazione esterna e questa è la

differenza sostanziale con la paginazione.

La paginazione , a differenza della segmentazione, consiste nel suddividere l’intera memoria in frame della

stessa dimensione delle pagine dei processi, l’allocazione riguarda quindi le singole pagine ed è un banale

problema di assegnazione dei frame liberi della memoria alle pagine dei processi, in questo modo si elimina

del tutto la frammentazione esterna, cosa che invece si presenta nella segmentazione, in quanto le pagine

hanno tute la stessa dimensione, tuttavia si presenta il problema della frammentazione interna quando

l’intero spazio di indirizzamento del processo non è una potenza di 2, mediamente si ha per ogni processo

mezza pagina inutilizzata per via della frammentazione interna.

Le tre principali tecniche di paginazione della memoria per architetture a 64 bit sono :

 Tabella delle pagine con hashing : Consiste nell’utilizzo di una funzione di hashing che riceve in

input il numero di pagina restituendo in output un indice i alla tabella delle pagine, questo indice i

porta ad una lista concatenata in cui sono presenti tutte le pagine il cui numero ha portato ad un

conflitto nella generazione dell’indice, scorrendo questa lista si trova l’elemento della pagina

cercata che contiene il frame fisico, sommando al frame fisico il displacement dell’indirizzo logico

iniziale si ottiene l’indirizzo fisico.

 Tabella delle pagine invertita : Ogni processo non ha più la propria tabella delle pagine ma c’è

un'unica tabella delle pagine del sistema che memorizza tutte le pagine di tutti i processi. L’indice di

questa tabella rappresenta il numero di frame fisico, per questo si dice invertita, mentre ogni

elemento della tabella contiene il numero di pagina e il PID del processo a cui appartiene quella

pagina. La ricerca in questa tabella avviene per scorrimento in base al PID e al numero di pagina;

una volta trovato l’elemento cercato si ottiene il frame fisico che sommato al displacement ci da

l’indirizzo fisico.

 Paginazione gerarchica : Consiste nel paginare la PMT, che è troppo grande poiché contiene troppi

elementi in un’architettura a 64 bit, creando un EPMT, anch’essa è troppo grande ma si può

paginare creando una paginazione a tre livelli. Nella risoluzione dell’indirizzo logico in fisico, questa

tecnica comporterebbe numerosi accessi alla memoria, per questo è preferibile optare per le prime

due tecniche.

La segmentazione paginata è una combinazione delle tecniche di segmentazione e paginazione. Consiste

nel segmentare il processo in segmenti di codice logicamente affini, e nel suddividere lo spazio di

indirizzamento del processo in due tabelle di segmenti:

- Tabella dei segmenti privati LST

- Tabella dei segmenti condivisi GST

Quindi l’indirizzo di un segmento è un indirizzo bidimensionale. Nel selettore sono contenute le

informazioni circa il segmento tra cui:

- ID segmento nella Segmnet table

- 1 bit che indica in quale tabella si trova il segmento

- 2 bit di proiezione, indica quali permessi sono concessi per il segmento

Una volta acceduto all’elemento della specifica tabella dei segmenti grazie al selettore si ottengono i

registri base e limite del segmento, sommando al registro base ottenuto il displacement dell’indirizzo di

partenza si ottiene un indirizzo lineare ancora logico. Da qui parte la tecnica di paginazione, supponiamo la

page table molto grande quindi paginazione a due livelli.

L’indirizzo logico ottenuto dalla risoluzione della segmentazione contiene : directory, pagina, displacement.

Da qui, si risolve l’indirizzo logico in indirizzo fisico come in una paginazione a due livelli, ossia:

- Da directory risalgo all’elemento della tabella delle directory da cui ricavo la page table

- Dalla page table ricavata e da pagina dell’indirizzo logico ottengo l’elemento della page table della

pagina specifica da cui ottengo il frame

- Sommando il frame al displacement ottengo l’indirizzo fisico

Questo schema risolve la frammentazione esterna presente nello schema a segmentazione paginata grazie

alla paginazione che permette di avere pagine di dimensione fissa mappate in frame della stessa

dimensione. La frammentazione interna è ancora non risolta come nello schema di paginazione, in quanto

lo spazio di indirizzamento di un processo potrebbe non essere potenza di 2.

In ambito di memoria paginata, l’EAT è il tempo di accesso effettivo per la risoluzione di un indirizzo di

memoria quando si fa uso della TLB, esso viene calcolato mediante l’uso di diversi parametri:

- β : tempo di accesso alla memoria

- ɛ : tempo di accesso alla TLB

- α : Hit ratio

EAT = β(2- α) + ɛ

CAPITOLO 10 : MEMORIA VIRTUALE

L’anomalia di belady si verifica nell’algoritmo di sostituzione delle pagine FIFO, esso avviene quando pur

incrementando il numero di frame allocabili per processo, si verifica un inaspettato aumento delle page

fault, questo fenomeno è completamente imprevedibile, per questo l’algoritmo FIFO non &egrav