Che materia stai cercando?

Sistemi operativi

Appunti di Sistemi operativi basati su appunti personali del publisher presi alle lezioni del prof. Grisetti, dell’università degli Studi La Sapienza - Uniroma1, facoltà di Ingegneria dell'informazione, Corso di laurea in ingegneria informatica e automatica. Scarica il file in formato PDF!. Scarica il file in formato PDF!

Esame di Sistemi operativi docente Prof. G. Grisetti

Anteprima

ESTRATTO DOCUMENTO

Sincronizzazione dei processi

race condition,

Serve per evitare la ovvero più processi paralleli che cercano di

modificare gli stessi dati nello stesso momento provocando risultati casuali.

coerenza dei dati condivisi.

È quindi necessaria per mantenere la

La sezione critica (SC)

sezione critica

Con si intende la parte esatta del codice di

programma che accede ai dati in comune e necessita di

mutua esclusione

protocolli di accesso che permettano la

(ME), ovvero se un processo in esecuzione è entrato in SC

nessun altro processo deve poter accedere alla SC

corrispondente.

Nei sistemi multiprogrammati la sezione critica più importante

è proprio quella relativa alle strutture dati del kernel, poiché

ogni processo che entra in modalità kernel cerca di accedervi.

Si possono avere quindi 2 tipi di kernel:

- kernel con diritto di prelazione => implementa gestione autonoma dei processi in

modalità kernel, può decidere chi può usare le sue strutture dati in ogni momento,

necessita di gestione della SC

- kernel senza diritto di prelazione => non ha il controllo sul processo già presente,

questo rilascerà la modalità kernel in modo autonomo solo alla fine delle sue operazioni

Soluzione di Peterson

Soluzione software classica al problema nel caso di 2

processi, non implementabile su calcolatori moderni.

I processi condividono i dati:

- int turno;

- Boolean flag[2];

Se turn == i, il processo Pi può accedere alla SC, flag

invece serve per dire se il processo è pronto ad entrare.

Protocollo:

1. il processo i per entrare imposta il suo flag su TRUE

2. assegna il turno all’altro processo j

3. finito l’accesso j imposterà il flag su FALSE conferendo il passaggio al processo i.

Lock e sincronizzazione hardware

Le soluzioni al problema della sezione critica si basano tutte su uno strumento chiamato

lock; a livello hardware, nei sistemi monoprocessore è sufficiente disabilitare gli interrupt,

nelle architetture attuali si usano le istruzioni atomiche .

26

test_and_set compare_and_swap,

La e la protocollo:

1. Si dichiara una variabile globale lock, inizialmente lock = 0

2. Quando un processo entra in sezione critica imposta lock = 1

3. Gli altri processi trovando lock = 1 non possono accedere alla SC e si mettono in

attesa della terminazione del processo in SC starvation

OSS questo metodo comporta Busy waiting da parte di altri processi e 27

OSS generalmente non accessibili ai programmatori

istruzione atomica = non si può interrompere la sua esecuzione, una volta iniziata deve essere

26 completata

starvation = processo non viene mai scelto dallo scheluder e quindi non può evolvere

27 18

Mutex lock

Soluzione più semplice per la gestione

della SC utilizzabile dai programmatori.

Prima di poter accedere alla SC il

processo deve acquisire il possesso

del mutex lock tramite la funzione

acquire() per poi rilasciarlo alla fine

relase().

delle operazioni tramite

Solo un processo alla volta può acquisire il lock e quindi avere

accesso alla SC, gli altri rimangono in attesa

Semafori

Un semaforo è una variabile intera alla quale si può accedere (escludendo inizializzazione)

solo tramite le operazioni atomiche predefinite:

- wait(), che decrementa il valore del semaforo

- signal(), che invece lo incrementa

Si può accedere alla SC solo quando il valore del semaforo è positivo (>0).

I semafori possono essere di 2 tipi:

- semafori binari => valore 1 oppure 0, equivalente ai mutex lock

- semafori contatore => utilizzabile su risorse multiple; inizializzato con il numero di

risorse disponibili, ogni volta che un processo accede ad una di esse ne decrementa il

valore tramite wait() per poi incrementarlo nuovamente con signal(), quando il semaforo

arriva a 0 blocca tutti gli altri processi.

OSS nei semafori contatori i processi che tentano di entrare in SC senza successo

non rimangono in Busy waiting ma il loro PCB viene salvato in una coda associata

al semaforo così che altri processi possano essere eseguiti nel frattempo.

block() e mackup() sono le funzioni che bloccano e riattivano i processi. 19

Deadlock

Il deadlock è una condizione nella quale 2 o

più processi non possono evolvere poiché

ognuno attende la terminazione dell’altro.

Ex. essendo la funzione wait() bloccante per

il processo, si ha che se un processo P 0

invoca wait(S) e P invoca wait(Q), se P

1 0

dovesse invocare wait(Q) l’attesa

diventerebbe infinita.

Questo poiché il semaforo Q già posseduto

da P che non può terminare fintanto che il semaforo S non viene rilasciato.

1

ex. Produttore / consumatore

Prima implementazione base dei semafori, serve per la gestione di un buffer di n dati.

Il semaforo binario mutex permette l’accesso alla SC ad un solo processo alla volta.

I semafori contatori empty e full tengono conto di quanti processi stanno scrivendo o

prelevando dati dal buffer. Produttore Consumatore 20

Monitor

Evoluzione dei semafori, più semplice da controllare ed implementato in più linguaggi.

tipo di dato astratto

È un (ADT) che incapsula:

- Variabili condivise

- Procedure che operano sui dati condivisi

Il costrutto monitor quindi incapsulando le

variabili condivise ne rende possibile l’accesso

solo tramite le sue procedure interne che

implementano la mutua esclusione tramite

variabili di condizione, wait() e signal()/post().

In questo modo un solo processo alla volta può

avere accesso alle procedure del monitor e

modificarne le variabili 21

IPC (inter process communication)

Meccanismo di comunicazione tra processi per lo scambio dei dati che permette di usare

cooperativi,

processi si implementa in 2 modi:

(a) (b)

(a) shared memory

Un processo alloca una o più zone di memoria e permette l’accesso in lettura e scrittura

ad altri processi, questo permette una sola chiamata al kernel durante la creazione, tutte

le altre interazioni avvengono in modalità user, richiede mutua esclusione.

Usata per processi su stesso elaboratore, può provocare problemi coerenza cache su

elaboratori con molti processori o core

(b) Message passing:

Permette lo scambio di messaggi tra due processi tramite un communication link (canale

send receive,

di comunicazione) e le primitive e non necessita la condivisione dello

stesso spazio di indirizzi e non ha problemi di sincronizzazione ma implica passaggio per

il kernel ad ogni interazione. (il che provoca un overhead maggiore)

Ottimale in sistemi distribuiti o processori con più core.

I componenti necessari per implementare questo metodo sono:

- naming => riferimento al processo a cui indirizzare messaggi, si può avere:

Comunicazione diretta => il destinatario/mittente viene esplicitato direttamente

• nella funzione, semplice ma non modulare

Comunicazione indiretta => messaggi vengono scambiati tramite una porta o

• mailbox nel sistema alla quale accedono entrambi i processi.

OSS la mailbox può anche essere associata direttamente ad un processo, in

questo caso però può solo ricevere i messaggi da altri processi

- Sincronizzazione => definisce se chiamate sono bloccanti:

Invio sincrono => processo che invia messaggio si blocca finché non viene ricevuto

• Invio asincrono => processo invia messaggio e riprende normale esecuzione

• Ricezione sincrona => processo si blocca fino a ricezione messaggio

• Ricezione asincrona => ricezione di messaggio durante normale esecuzione

• OSS è possibile implementare qualsiasi combinazione 22

Possibile implementazione shared memory POSIX

#include <unistd.h>

#include <sys/mman.h >

28

#define MAX_LEN 10000

struct region { /* Defines "structure" of shared memory */

int len;

char buf[MAX_LEN];

}; Vedere dispense programmazione per

altre implementazioni e message passing

struct region *rptr;

int fd;

/* open or create shared memory object and set its size */

fd = shm_open("/myregion", O_CREAT | O_RDWR, S_IRUSR | S_IWUSR) ;

29

if (fd == -1) /* Handle error */;

/* set object size (function of unistd.h)*/

if (ftruncate(fd, sizeof(struct region)) == -1) /* Handle error */;

/* Map shared memory object */

rptr = mmap(NULL, sizeof(struct region), PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0) ;

30

if (rptr == MAP_FAILED) /* Handle error */;

/* Now we can refer to mapped region using fields of rptr */

int shm_unlink(const char *name) => rimuove segmento di memoria condivisa

dal /dev/shm ma non dealloca spazio mappato in processo e

filedescriptor, bisogna usare munmap e close

<sys/mman.h> = contiene syscall per creazione e gestione zone shared memory

28 oflag, mode)

int shm_open(const char *name, int mode_t => apre zona di memoria condivisa,

29 ritorna file descriptor che si riferisce alla zona, -1 in caso di errore

- name = nome univoco della zona nel filesystem visibile ad i processi (in /dev/shm)

- oflag = O_RDWR specifica apertura in lettura scrittura, O_CREAT se la zona con nome

name non è già presente ne crea una… posso utilizzare tutti i flag di open()

- mode = attributi di creazione per O_CREAT

len, prot, flags, fildes, off)

void *mmap(void *addr, size_t int int int off_t => consente di mappare

30 il filedescriptor (qui segmento di memoria condivisa) nella memoria del processo, ritorna

indirizzo in caso di successo, MAP_FAILED in caso di errore

- addr =

- len = grandezza blocco da mappare

- prot = permessi di accesso alla zona

- flags = informazioni su handling zona (ex. MAP_SHARED => cambiamenti condivisi,

MAP_PRIVATE => cambiamenti privati)

- filedes = filedescriptor da mappare

- off = offset 23

Deadlock

Ogni sistema è composto da un numero limitato di risorse che possono essere richieste

ed in caso utilizzate dai processi, il deadlock è una condizione di stallo nella quale 2 o più

processi non possono evolvere poiché ognuno attende il rilascio delle risorse da parte di

un altro.

Condizioni necessarie per deadlock:

Mutua esclusione

1. => almeno una delle risorse condivise dai processi deve essere

non condivisibile e quindi richiedere la mutua esclusione

Possesso e attesa

2. => un processo deve possedere una risorsa ed allo stesso tempo

richiederne un altra

Assenza di prelazione

3. => le risorse non possono essere momentaneamente

rilasciate

Attesa circolare

4. => P attende P , P attende P , …

0 1 1 2

Grafo di assegnazione

Rappresenta situazioni di stallo, formato da vertici V e archi E, con V diviso in:

- P = { P , P ,… ,P } => tutti i processi del sistema

0 1 n

- R = { R , R , … , R } => tutte le risorse del sistema

0 1 n

E invece è composto da:

P → R arco di richiesta

indica che il processo i ha richiesto utilizzo risorsa j,

i j

R → P arco di assegnazione

indica che la risorsa j è stata assegnata al processo j,

j i

Il grafo permette di controllare immediatamente la presenza di cicli che sono condizione

necessaria (ma non sufficiente) per il deadlock

NO deadlock deadlock

Metodi gestione stallo

Il problema del deadlock si può affrontare a livello di sistema in 3 modi:

- Si usa protocollo che previene oppure evita situazioni di deadlock:

Prevenire stalli => si evita a monte il verificarsi di almeno una delle 4 condizioni

• necessarie per il deadlock

Evitare stalli => si forniscono al sistema le informazioni sulle risorse richieste dai

• processi in anticipo, in modo che possa decidere quali soddisfare e quali devono

invece rimanere in attesa.

- Si permette al sistema di entrare in stallo, individuarlo, e quindi eseguire ripristino

tramite specifici algoritmi evitando il degrado delle prestazioni

- Si ignora il problema, i processi possono entrare in stallo e provocare un degrado delle

prestazioni se non se ne occupa il programmatore applicativo.

Utilizzato dalla maggior parte dei sistemi operativi, compresi Linux e Windows

poiché l'implementazione è più economica e flessibile 24

Prevenire stalli

Per evitare il verificarsi di una delle 4 condizioni:

1. Mutua esclusione => in caso di risorse non condivisibili deve valere condizione di

mutua esclusione, non necessaria invece per risorse condivisibili sulle quali possono

lavorare entrambi i processi (ex. File aperto in sola lettura).

2. Possesso e attesa => si permette solo a processi non aventi risorse in possesso di

richiederne altre, i processi sono quindi obbligati ad esplicitare tutte le risorse di cui

necessitano per il completamento.

3. Assenza di prelazione => se un processo richiede una risorsa che non gli si può

assegnare allora rilascia tutte le altre in suo possesso fino a quando non potrà avere

tutte le risorse necessarie, altrimenti il processo impone il rilascio delle risorse agli altri

processi per poi rilasciare tutto una volta terminato.

4. Attesa circolare => si impone un ordinamento totale all’insieme di tutti i tipi di risorse e

si impone che ciascun processo le richieda in ordine crescente.

Evitare stalli

Le tecniche per evitare stalli si basano su una conoscenza approfondita da parte del

sistema delle risorse necessarie al processo durante tutto il suo ciclo di vita, evitando

possibili sprechi di risorse come può accadere nei metodi di prevenzione.

Ogni algoritmo differisce per la quantità ed il tipo di informazioni richieste, la versione più

semplice richiede al processo solo il numero massimo per ogni tipo di risorsa che utilizza,

garantisce quindi l’assenza di stalli confrontando tutte le risorse e le richieste presenti.

stato sicuro

Un sistema si dice in se è in grado di assegnare risorse a ciascun processo

in un certo ordine impedendo situazioni di stallo, ovvero esiste una sequenza sicura.

sequenza sicura

Una sequenza di processi <P , P ,… ,P > è una per lo stato di

0 1 n

assegnazione attuale se, per ogni P , le richieste che P può ancora fare si possono

i i

soddisfare impiegando le risorse attualmente disponibili più le risorse possedute da tutti i

processi P con j<i.

j

È quindi possibile evitare stalli mantenendo sempre il sistema in stato sicuro.

Algoritmo con grafo di assegnazione risorse

Utilizzabile solo quando si ha una sola risorsa per ogni tipo.

Basato sui grafi di assegnazione, oltre agli archi di richiesta e assegnazione introduce gli

archi di rivendicazione che indicano quali risorse può richiedere il processo in futuro

P → R

(come arco di richiesta ma tratteggiato).

i j

Quando un processo entra in esecuzione esplicita tutti i suoi archi di rivendicazione che

ad ogni richiesta di una risorsa diventano archi di richiesta.

L’algoritmo (costo n2 con n = numero processi) ad ogni richiesta controlla se questa

provoca la formazione di cicli e conseguente passaggio a stato non sicuro, se non ci sono

problemi la richiesta viene soddisfatta, altrimenti il processo viene messo in attesa.

Stato non sicuro del grafo

Stato sicuro del grafo 25

Algoritmo del banchiere

Utilizzabile con più risorse dello stesso tipo.

Ogni nuovo processo per entrare in esecuzione deve esplicitare il numero massimo di

risorse di cui necessita per ogni tipo di risorsa in modo che il sistema possa verificare che

si mantenga lo stato sicuro in caso di assegnazione.

n m

Dati processi ed tipi di risorsa, l’algoritmo necessita delle seguenti strutture dati:

- Disponibili m

=> vettore lunghezza che indica numero di istanze disponibili;

disponibili[j] = k => k indica il numero di istanze disponibili per il tipo di risorsa R j

- Massimo n m

=> matrice x che definisce la richiesta massima di ogni processo;

massimo[i,j] = k => k indica il numero massimo di R che può richiedere P

j i

- Assegnate n m

=> matrice x che definisce numero di istanze di ogni tipo di risorsa già

assegnate ad ogni processo;

assegnate[i,j] = k => k indica il numero di istanze di R già assegnate a P

j i

- Necessità n m

=> matrice x che indica risorse ancora necessarie ad ogni processo;

necessità[i,j] = k => k indica il numero di istanze di R mancanti a P

j i

OSS necessità[i,j] = massimo[i,j] - assegnate[i,j]

X ≤ Y X[i] ≤ Y [i]

n),

Dati due vettori X e Y (lunghezza si dice che se per ogni i = 1, .., n

X ≠ Y

Inoltre X < Y se vale anche la condizione

I. Algoritmo di verifica della sicurezza

Serve per determinare se il sistema è in uno stato sicuro controllando le risorse disponibili

per ogni tipo, una ad una.

1. Siano Lavoro e fine vettori di lunghezza m e n, con: notazione: ogni riga delle

lavoro = disponibili

• matrici assegnate e

fine[i] = falso, per i = 1,2, …, n-1

• necessità si indica con

2. Si cerca un indice i per cui valgono le relazioni: assegnate e necessità

fine[i] == falso

• i i

necessità lavoro

• i

3. lavoro = lavoro + assegnate Il costo asintotico

i

fine[i] = vero m n

dell’algoritmo è x 2

goto II

4. If (fine[i] == vero) per ogni i => sistema è al sicuro

II. Algoritmo di richiesta delle risorse

Serve per determinare se le richieste possono essere soddisfatte.

Dato richieste , vettore delle richieste di P .

i i

Si ha che richieste [j] == k, indica il numero di istanze della risorsa tipo R richieste da P .

i j i

Se P effettua una richiesta si effettuano le seguenti azioni:

i richieste ≤ necessita

1. If ( ) goto 2;

i i

else condizione di errore, superato numero massimo di richieste

richieste ≤ disponibili

2. If ( ) goto 3;

i

else P deve aspettare risorse diventino disponibili

i

3. Si simula l’assegnazione delle risorse modificando le strutture dati:

disponibili = disponibili − rishieste

i

assegnate = assegnate + richieste

i i i

necessita = necessita − richieste

i i i

4. If (simulazione ritorna stato sicuro) vengono assegnate le risorse al processo P i

else il processo P deve aspettare, si ripristina assegnazione risorse precedente

i 26

Rilevamento e ripristino situazioni di stallo

Rilevamento

I. Istanza singola per ogni tipo di risorsa

Si effettua tramite una variante del grafo di

assegnazione detta grafo d’attesa.

Connessione diretta tra i processi, ad ogni

P → P

arco d’attesa tra i processi i j

P → R R → P

corrispondono 2 archi e ,

i q q i

questo infatti indica che il processo P i

attende la terminazione di P per essere

j

eseguito.

Anche in questo caso i cicli indicano la

presenza di stallo.

II. Più istanze per ogni tipo di risorsa

n m

Simile ad algoritmo del banchiere, dati processi ed tipi di risorsa, l’algoritmo

necessita delle seguenti strutture dati:

- Disponibili m

=> vettore lunghezza che indica numero di istanze disponibili;

disponibili[j] = k => k indica il numero di istanze disponibili per il tipo di risorsa R j

- Assegnate n m

=> matrice x che definisce numero di istanze di ogni tipo di risorsa già

assegnate ad ogni processo;

assegnate[i,j] = k => k indica il numero di istanze di R già assegnate a P

j i

- Richieste n m

=> matrice x che indica richiesta attuale di ogni processo;

necessità[i,j] = k => k indica il numero di istanze di R che sta richiedendo P

j i

OSS necessità[i,j] = massimo[i,j] - assegnate[i,j]

Algoritmo di rilevamento:

1. Siano Lavoro e fine vettori di lunghezza m e n, con:

lavoro = disponibili

• For ( i=0; i<n; i++)

• Il costo asintotico

If (assegnate != 0) fine[i] = falso

i m n

dell’algoritmo è x 2

else fine[i] = true

2. Si cerca un indice i per cui valgono le relazioni:

fine[i] == falso

• ≤

richieste lavoro

• i

IF (non esiste nessun i) goto 4;

3. lavoro = lavoro + assegnate i

fine[i] = vero

goto II

4. If (fine[i] == falso) per qualche i => sistema è in stallo, inoltre è proprio i in stallo

L’utilizzo dell’algoritmo per la rivelazione degli stalli comporta un notevole aumento del

carico computazionale, quindi, anche se si potrebbe usare ogni volta che un processo

effettua una richiesta che non si può soddisfare immediatamente, solitamente l’algoritmo

viene utilizzato ad intervalli definiti oppure quando il carico computazionale scende sotto

una determinata soglia. 27

Ripristino

Si può effettuare in 2 modi differenti:

I. Terminazione dei processi

Si possono usare 2 metodi:

- Terminazione di tutti i processi in stallo => operazione onerosa, inoltre non potendo

salvare lo stato dei processi i risultati dovranno essere scartati e ricalcolati

- Terminazione di un processo alla volta fino all’eliminazione dello stallo => comporta

overhead notevole dovendo richiamare l’algoritmo di rilevazione dopo ogni

terminazione

II. Prelazione delle risorse

Si prelevano risorse ai processi, considerando i seguenti problemi:

1. Selezione vittima => bisogna stabilire un ordine con il quale togliere determinate

risorse a determinati processi allo scopo di minimizzare il costo dell’operazione

2. Ristabilimento stato precedente => prelevando una risorsa si altera lo stato del

processo che deve quindi essere ricondotto ad uno stato sicuro precedente (rollback),

oppure più semplicemente si esegue un riavvio dello stesso

3. starvation => non si devono verificare situazioni di attesa indefinita su un processo,

ovvero bisogna variare i processi ai quali si sottraggono risorse 28

La memoria centrale

A livello logico la memoria è come un grande vettore di byte,

ognuno con il suo indirizzo, usati tramite le primitive load e store.

registro base registro limite

Ogni processo possiede un ed un

che permettono di dividere la memoria in intervalli.

Ad ogni accesso in memoria da parte di un processo la cpu

confronta l’indirizzo generato con i valori contenuti nei 2 registri,

effettuabile solo dal kernel in modo da mantenere sicurezza.

Associazione indirizzi

I programmi sono salvati sul disco come file binari eseguibili da caricare in memoria

input queue.

durante l’esecuzione, l’insieme dei processi in attesa di esecuzione è detta

In fase di compilazione non è possibile conoscere in quale porzione di memoria verrà

salvato il programma, viene quindi generato codice assoluto basato su un indirizzo di

partenza chiamato indirizzo di rilocazione.

Quando il programma viene lanciato il loader effettua una fase di linking che permette di

associare (bind) gli indirizzi simbolici (ex. x= &x+4) del codice sorgente con gli indirizzi

logici corrispondenti nell’immagine di memoria.

Durante la fase di esecuzione invece tutti gli indirizzi

MMU

logici del programma vengono mappati dalla 31

sugli indirizzi fisici, visibili solo dalla memoria ed in

comune per ogni programma che risiede in essa.

Nella versione più semplice l'associazione avviene

sommando l’indirizzo logico al registro di rilocazione

ed effettuando un controllo per verificare che

l’indirizzo fisico non vada oltre il registro limite.

OSS Per ottimizzare l’utilizzo della memoria è

dynamic loading

possibile utilizzare il (caricamento dinamico) che permette di caricare

solo porzioni del programma in memoria durante l’esecuzione, quando necessarie.

Il linking dinamico si utilizza anche per sfruttare le librerie di sistema delle quali si salva

solo un riferimento e non tutto il codice.

Swapping (avvicendamento processi)

Per aumentare gli indirizzi fisici della memoria è possibile creare aree di swapping sul

disco nelle quali spostare temporaneamente

processi momentaneamente inattivi.

Quando il sistema schedula un processo dalla

ready queue, controlla prima se questo è

presente nella memoria principale, altrimenti

lo carica dall’area di swap. swap out

Sa la memoria è piena esegue uno swap in

di un processo già presente ed uno

del processo richiesto, questo però aumenta

di molto il tempo di context switch.

Lo swapping non è presente su dispositivi

mobili, i quali chiudono direttamente altri

processi attivi.

MMU = memory-management unit, componente hardware per la mappatura degli indirizzi

31 29

Allocazione contigua della memoria

La prima parte della memoria fisica è riservata per il sistema operativo, il resto viene

lasciato ai processi, ognuno dei quali possiede una sezione contigua di memoria.

L’utilizzo degli indirizzi di rilocazione perme al sistema operativo di cambiare le sue

dimensioni semplicemente alterando il loro valore.

Esistono diversi modi per effettuare l’allocazione:

- Schema a partizioni fisse => implementazione più semplice (non più in uso), consiste

nel dividere la memoria in sezioni di dimensione fissa ad ognuna delle quali si associa

un processo, limita multiprogrammazione.

- Schema a partizione variabile => la grandezza della sezione di memoria viene

calcolata al momento di avvio del processo aumentando la flessibilità, inoltre il SO

mantiene una tabella con posizione e grandezza degli spazi vuoti.

Avendo che processi diversi necessitano di una quantità diversa di memoria nasce

problema di allocazione dinamica della memoria,

il ovvero in quale buco libero

allocare i dati dei nuovi processi, si

possono usare 3 diversi criteri:

First-fit

• => il primo spazio libero

abbastanza grande

Best-fit

• => il più piccolo buco

abbastanza grande

Worst-fit

• => il più grande tra quelli disponibili

frammentazione

OSS si crea inoltre il problema della che implica un utilizzo

inefficiente dello spazio libero

La frammentazione

Ne esistono 2 tipi:

- Frammentazione esterna => Ne soffrono first-fit e best-fit , si verifica quando, pur

avendo spazio sufficiente in memoria, non è possibile allocare dati poiché le sezioni

libere non sono contigue.

Infatti caricando e rimuovendo dalla memoria dati di diverse dimensioni, si

possono creare tanti piccoli buchi frammentati.

Una soluzione a questo problema è data dalla compattazione che permette di

spostare le locazioni di memoria utilizzando solamente l’indirizzo di rilocazione

- Frammentazione interna => si verifica quando la memoria allocata è superiore a

quella realmente necessaria a causata dall’allineamento dei dati.

L’allineamento è utile poiché permette

di ridurre le strutture necessarie per la

memorizzazione di posizioni e

grandezze, inoltre semplifica molte

operazioni. 30

Segmentazione

Con questo approccio non si vede più la memoria come un grande array lineare ma si

associa un segmento di memoria ad ogni componente del programma (ex. stack, heap).

<numero segmento, offset>,

A livello logico si usano indirizzi bidimensionali del tipo dove

numero segmento specifica il componente del programma e offset specifica l’indirizzo

logico all’interno dell’elemento.

La traduzione da indirizzi logici bidimensionali a indirizzi fisici unidimensionali si effettua

tabella dei segmenti, base segmento

tramite la ogni suo elemento è una coppia ordinata

limite segmento,

e la base contiene l’indirizzo iniziale del segmento e il limite la fine.

Quindi riprendendo la coppia

<numero segmento, offset>:

- Numero segmento estrae l’elemento

base con l'indirizzo

- Offset viene confrontato con il limite

corrispondente al componente

IF (offset < limite) offset si somma a

base e genera indirizzo fisico

ELSE si genera errore

OSS soffre del problema della

frammentazione esterna 31

Paginazione frame,

Consiste nel suddividere la memoria fisica in blocchi di dimensione fissa, detti su

tabella delle pagine pagine.

cui mappare (tramite la ) blocchi di memoria logica, detti

32

Ogni processo possiede una propria tabella delle pagine che si ricollega ad una tabella

tabella di frame,

principale, detta visibile solo al kernel, e nella quale sono indicati tutti i

frame già occupati e il/i processo/i a cui sono assegnati.

Questa completa separazione tra indirizzi

fisici ed indirizzi logici è ciò che permette

ad ogni processo di avere un immagine

di memoria (memoria virtuale) con spazio

degli indirizzi pari all’architettura

(ex. 64 bit) anche se la memoria reale è

nettamente inferiore.

La dimensione dei frame, e quindi delle

pagine, dipende dall’hardware e dal

sistema operativo, generalmente nei

sistemi di linux è di 4KB.

OSS Frame fissi evitano il problema della

frammentazione esterna ma possono

portare a problemi di frammentazione

interna.

indirizzamento

Dato uno spazio degli indirizzi logici di 2 bit (dove n è pari all’architettura) con pagine di

n

dimensione 2 bit, si ha che ogni indirizzo logico viene diviso in 2 componenti:

k

- Numero della pagina => contiene un indice

della tabella delle pagine tramite il quale è

possibile ricavare l’indirizzo base del frame,

n-k

dato dagli bit più significativi

- Offset di pagina => rimane invariato,

determina l’offset all’interno del frame, dato

k

dai bit meno significativi

Ex. Avendo un architettura a 32 bit, si ha:

Spazio indirizzi logici = 2 bit (n = 32)

32

Pagina = 4KB = 2 bit (k = 12)

12

=> tabella delle pagine = 2 /2 = 2 pagine

32 12 20

Nei sistemi moderni avendo che la quantità di pagine disponibili è molto grande, per

TLB

velocizzare l’accesso si utilizza una piccola cache associativa detta (translation

look-aside buffer) che contiene solo una parte della tabella delle pagine.

Così come per le normali cache ad ogni interazione si controlla prima la presenza della

pagina nella TLB, altrimenti in caso di TLB miss si accede in memoria e si controlla la

page table.

Avendo più processi che la utilizzano contemporaneamente, si associa ad ogni elemento

un ASID (address-space identifier) che indica univocamente il processo a cui si riferisce.

page table = array lineare con i riferimenti alle pagine del processo caricate in memoria,

32 contiene inoltre informazioni su validità riferimento e permessi di lettura scrittura su frame

32

La memoria virtuale

La memoria virtuale si basa sulla distinzione tra indirizzi logici e fisici, permette di astrarre

dalla quantità reale di memoria del calcolatore ed associare ad ogni processo uno spazio

degli indirizzi virtuale (immagine di memoria del processo) pari a 2 , dove n dipende

n

dall’architettura (ex. 32, 64, …).

Inoltre isola ogni blocco permettendo l’accesso ai dati solo a processi con permesso

esplicito, aumentando la protezione e permettendo condivisione della memoria.

Paginazione su richiesta

Estende il concetto di paginazione anche all’utilizzo in memoria secondaria, permette di

caricare in memoria solo le pagine realmente utili, le altre rimangono su disco.

Ad ogni accesso a memoria le operazioni sono:

1. Si controlla nella tabella delle pagine il bit di validità del riferimento

2. IF (riferimento valido) carica da memoria la pagina corrispondente, exit

ELSE controlla l’esistenza del riferimento nella tabella interna al processo (in PCB):

page fault,

IF (riferimento esiste) goto 3

ELSE errore, segmentation fault

3. Si individua un frame libero e la pagina in

memoria secondaria

4. Si trasferisce la pagina dal disco alla

memoria principale

5. Completato il trasferimento si modifica la

tabella delle pagine

6. Si riavvia l’istruzione interrotta

Teoricamente un processo potrebbe iniziare

l’esecuzione caricando solo la prima pagina e

poi caricare le altre, una alla volta.

Sebbene questo modo permetta di risparmiare

molto spazio in memoria, ogni caricamento di

pagina è molto costoso, ed avendo anche solo

un page fault ogni 1000 accessi l’esecuzione del programma può rallentare di 40 volte.

OSS la generazione di nuovi processi avviene duplicando il genitore, ma poiché gran

parte dei processi figli non necessita di tutte le pagine del padre, è possibile utilizzare il

sistema di copy-on-write che duplica solo le pagine che vengono modificate dal figlio.

In linux e diverse versioni UNIX questo si effettua tramite la vfork().

La continua allocazione di nuove pagine da parte

di più processi comporta il riempimento della

memoria, si necessita quindi di un sistema di

sovrallocazione che vada a modificare il punto 3.

I. Se la memoria è piena si sceglie un frame

vittima tra quelli inutilizzati.

dirty bit

II. Se il corrispondente è posto a 1 si

33

esegue un swap out del frame nel disco e

swap in del nuovo frame, altrimenti

direttamente lo swap in.

dirty bit = (bit di modifica) indica se frame è stato sovrascritto dopo inserimento in memoria

33 33

Gestione della paginazione su richiesta

Per il funzionamento ottimale di questa sistema è richiesta la presenza di 2 algoritmi:

- Sostituzione delle pagine => scelgono quali frame sostituire, minimizzano la

frequenza di page fault

- Allocazione dei frame => determinano numero di frame da associare al processo

Algoritmi di sostituzione delle pagine

La valutazione degli algoritmi si effettua tramite una reference string, ovvero una stringa

composta dai soli riferimenti alle pagine.

Si considera solo il numero della pagina e non tutto l’indirizzo, poiché l’accesso alla

stessa pagina, già contenuta in memoria, non provoca page fault.

Negli esempi:

Reference string => 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

numero di frame = 3

First in, first out (FIFO)

Si sostituisce la pagina presente in memoria da più tempo, non è necessario salvare

l’istante di memorizzazione di ogni pagina, si usa una coda FIFO delle pagine in memoria.

Questo algoritmo è semplice da implementare ma non ha buone prestazioni poiché non

considera la frequenza di utilizzo delle pagine.

di belady,

Inoltre questo algoritmo soffre dell’anomalia ovvero aumentando i frame le

prestazioni invece di migliorare potrebbero peggiorare

ex. Reference string =>

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 34

Algoritmo ottimale (OPT o MIN)

Si sostituisce la pagina che non verrà usata per il periodo di tempo più lungo, non

potendo conoscere questa informazione questo algoritmo rimane teorico ed è utilizzato

solo come metro di misura per gli altri algoritmi.

I page fault con la stessa reference string diventano 9.

Last Recently Used (LRU)

Si sostituisce la pagina che non è stata utilizzata per più tempo, concettualmente simile a

OPT ma guarda al passato invece che al futuro, algoritmo con prestazioni migliori rispetto

a FIFO ma ovviamente peggiori rispetto a OPT.

I page fault con la stessa reference string diventano 12.

Implementabile in 2 modi:

- Contatori => si associa un contatore generale alla CPU e dei contatori specifici ad

ogni pagina, ad ogni riferimento si incrementa il valore del contatore generale e si copia

il valore nel registro contatore associato alla pagina.

Ad ogni sostituzione si prende il frame con il valore del contatore più basso.

Richiede una ricerca lineare sulla tabella delle pagine ad ogni caricamento e può

avere problemi di overflow sul contatore.

- Stack => si mantengono i numeri di pagina in uno stack

implementato tramite lista doppiamente collegata, ad

ogni riferimentoa una pagina il numero corrispondente

viene posizionato in cima, in modo che in basso si trovi

sempre il più vecchio.

l’aggiornamento della pila è più costoso

(max. cambio 6 puntatori) ma non richiede

ricerche sulla tabella delle pagine.

OSS LRU e OPT sono detti algoritmi e pila e non soffrono dell’anomalia di belady.

È quindi possibile dimostrare che l’insieme delle pagine in memoria per n frame è

sottoinsieme dell’insieme con n+1 frame. 35

LRU approximation algorithms

l’algoritmo LRU è lento e richiede un hardware dedicato.

reference Bit

Nella realtà si usano delle varianti basate su un (bit di riferimento), ovvero

un bit inizializzato a 0 che si associa ad ogni pagina e diventa 1 ogni volta che si fa

riferimento ad essa.

Di base solo questo sistema non permette di conoscere l’ordine di accesso alle pagine, si

usano quindi i seguenti algoritmi:

- Bit supplementari di riferimento => si salva in memoria una tabella contenente un

byte per ogni pagina, a intervalli regolari si passa il controllo al sistema operativo che

shifta ogni byte e salva il reference bit attuale della pagina nel bit più significativo.

Quindi si ha che la pagina da sostituire è quella con il valore del byte più piccolo.

- Seconda chance => implementato tramite una coda circolare, si basa sull'algoritmo

FIFO al quale si aggiunge il reference bit, ad ogni richiesta di sostituzione si esegue

ricorsivamente il seguente controllo:

IF (reference bit = 0) si sostituisce pagina

ELSE si pone reference bit = 0 e si passa a prossimo elemento della pila

- Seconda chance migliorato => miglioramento dell’algoritmo utilizzando una coppia

ordinata formata del reference bit e del dirty bit:

1. (0,0) => non utilizzato o modificato di recente

2. (0,1) => non usato ma modificato recentemente, necessita swap out

3. (1,0) => usato recentemente ma non modificato, probabilmente verrà usato presto

4. (1,1) => usato e modificato recentemente, probabilmente verrà riutilizzato presto

ed inoltre necessita di swap out

ATTENZIONE la ricerca della classe minore può richiedere di scandire la coda più volte

Algoritmi basati sul conteggio

Si mantiene un contatore del numero di riferimenti fatti alla pagina, 2 tipi:

- LFU (least frequently used) => si rimpiazza pagina con valore più basso

- MFU (most frequently udes) => si rimpiazza valore più alto, assumendo che pagine con

valore basso sono appena state caricate in memoria e quindi deve ancora essere usate

Implementazione costosa e poco efficienti

OSS per diminuire i costi di swap out è possibile mantenere una pool di frame liberi in

cui eseguire lo swap in delle nuove pagine rimandando lo swap out.

Inoltre si mantiene una lista delle pagine modificate e ogni volta che il dispositivo di

paginazione è inattivo si esegue lo swap out di una di queste evitando di dover

attendere al momento di selezione della vittima 36


PAGINE

43

PESO

17.06 MB

AUTORE

duke0000

PUBBLICATO

4 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica e automatica
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher duke0000 di informazioni apprese con la frequenza delle lezioni di Sistemi operativi e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Grisetti Giorgio.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica e automatica

Teoria dei Sistemi - Come fare gli esercizi e tutta la teoria
Appunto
Telecomunicazioni (Appunti+Esercizi esame+Formulario)
Appunto
Elettrotecnica - Come fare gli esercizi e tutte le domande teoriche
Appunto
Controlli Automatici - Come fare gli esercizi e tutte le domande teoriche
Appunto