Che materia stai cercando?

Appunti di Sistemi operativi

Testo completo e dettagliato, con immagini , tabelle, riassunti, definizioni ed esempi. Ad ogni studente che si appresta allo studio di questa materia farebbe comodo una dispensa del genere. Garantito! Appunti basati su appunti personali del publisher presi alle lezioni del prof.Pravadelli.

Esame di Sistemi operativi docente Prof. G. Pravadelli

Anteprima

ESTRATTO DOCUMENTO

Si potrebbe sistemare il No preemption imponendo che un processo che richiede una risorsa non

disponibile debba cedere tutte le altre risorse che detiene, oppure cede risorse che detiene su

richiesta di un altro processo; però è fattibile solo per risorse il cui stato può essere facilmente

ristabilito come CPU registri semafori e file, non con risorse come stampanti e nastri.

Si potrebbe sistemare l’attesa circolare assegnando una priorità globale ad ogni risorse, in modo che

un processo possa richiedere solo risorse in ordine crescente di priorità.

Tutte queste soluzioni però possono portare a un basso utilizzo delle risorse con tutti i vincoli sul loro

accesso da parte dei processi.

2) Prevenzione dinamica

Mai utilizzata perché richiede una conoscenza delle risorse troppo approfondita. Si tratta dell’analisi

dinamica del grafo delle risorse per evitare situazioni cicliche. Si applica cercando che il sistema sia

in uno stato safe, cioè se usando le risorse disponibili può allocare risorse ad ogni processo, in qualche

sequenza, in modo che ognuno di essi possa terminare la sua esecuzione. Se tale sequenza non esiste

allora ci si trova in uno stato unsafe, cioè che può andare in deadlock. Due algoritmi per la

prevenzione dinamica sono il RAG e l’algoritmo del banchiere.

L’algoritmo con RAG funziona solo se c’è una sola istanza per risorsa. Vengono aggiunti archi di

richiamo (tratteggiati) che indicano la possibilità di richieste future. All’inizio ogni processo deve dire

quali risorse vorrebbe utilizzare e l’allocazione viene soddisfatta soltanto se non si crea un ciclo nel

2

RAG, con un algoritmo di complessità O(n ), con n numero di processi.

L’algoritmo del banchiere è meno efficiente del precedente ma funziona con più istanze delle risorse.

Ogni processo dichiara la sua massima richiesta. Ogni volta che un processo richiede una risorsa, si

determina se soddisfarla ci lascia uno stato di safe, dividendosi in due algoritmi di allocazione e

verifica dello stato.

3) Rivelazione e ripristino

Permettere che si verifichino deadlock e riportare il sistema bloccato al suo funzionamento normale.

La rilevazione e ripristino tramite RAG funziona solo con una risorsa per tipo e consiste nell’analizzare

periodicamente il RAG per verificare se esistono deadlock e iniziare il ripristino. Così facendo non si

ha bisogno di sapere in anticipo le richieste e viene utilizzato il sistema in modo migliore, a patto di

un elevato costo di ripristino.

L’algoritmo di rilevazione è basato sull’esplorazione di ogni possibile sequenza di allocazione per i

processi che non hanno ancora terminato. Una volta trovata una situazione di deadlock si può:

o Uccisione di tutti i processi: molto costoso perché tutti i processi devono ripartire perdendo

il lavoro svolto;

o Uccisione selettiva: costosa perché invoca l’algoritmo di rilevazione dopo ogni uccisione, fino

alla scomparsa del deadlock;

o Prelazione delle risorse: rollback in uno stato safe e ripartenza da questo stato.

La soluzione è combinata, infatti si partizionano le risorse in classi ordinate e all’interno di ogni classe

utilizzare l’algoritmo più appropriato per quella classe. L’ordine delle classi è: risorse interne,

menoria, risorse di processo e spazio di swap.

4) Algoritmo dello struzzo

Ignorare la possibilità che si verifichi un deadlock per rendere il sistema più performante.

GESTIONE DELLA MEMORIA

La condivisione della memoria da parte di più processi è essenziale per l’efficienza del sistema. Ogni

programma infatti per essere eseguito deve prima essere portato in memoria e trasformato in processo,

attraversando varie fasi.

BINDING

Innanzitutto bisogna tradurre indirizzi logici in indirizzi fisici, con un processo chiamato binding. Gli indirizzi

del programma sorgente infatti sono simbolici, associati poi dal compilatore ad indirizzi rilocabili, associati a

loro volta dal linker/loader ad indirizzi assoluti.

Statico:

- A tempo di compilazione (compile time)

Se è noto a priori in quale parte della memoria risiederà il processo. Se la locazione di partenza

cambia, allora è necessario ricompilare.

- A tempo di caricamento (load time)

Necessariamente bisogna generare un codice rilocabile, con indirizzi relativi.

Dinamico:

- A tempo di esecuzione (run time)

Se il processo può essere spostato in posizioni diverse della memoria durante l’esecuzione.

LINKING

- Statico: tutti i riferimenti sono definiti prima dell’esecuzione, l’immagine del processo contiene una

copia delle librerie usate;

- Dinamico: link posticipato al tempo di esecuzione, il codice del programma infatti contiene solo un

riferimento per recuperare le librerie.

LOADING

- Statico: costoso perché tutto il codice è caricato in memoria al tempo di esecuzione;

- Dinamico: caricamento dei moduli posticipato al primo utilizzo, il codice non utilizzato non viene

caricato. Utile per codice con tanti casi speciali.

SPAZI DI INDIRIZZAMENTO

Lo spazio di indirizzamento logico (generato dalla CPU, virtuale) è legato a uno spazio di indirizzamento fisico

(visto dalla memoria). Nel binding statico i due spazi coincidono, nel binding dinamico sono generalmente

diversi, tradotti con MMU.

MEMORY MANAGEMENT UNIT (MMU)

Dispositivo hardware che mappa indirizzi virtuali in indirizzi fisici. Contiene un registro di rilocazione, il cui

valore viene aggiunto ad ogni indirizzo generato da un processo e inviato alla memoria. Sono presenti anche

registri di rilocazione per proteggere lo spazio dei vari processi, che contengono il valore dell’indirizzo più

basso (registro base) e il limite superiore dello spazio logico. Ogni indirizzo logico deve risultare minore del

limite.

In un sistema multiprogrammato non è possibile conoscere in anticipo dove un processo può essere

posizionato in memoria e l’esigenza di avere lo swap impedisce di utilizzare indirizzi rilocati in modo statico.

Di conseguenza il binding statico non è possibile, la rilocazione dinamica viene usata nei sistemi complessi e

per gestire la memoria nel S.O. mentre la rilocazione statica viene usati in sistemi per applicazioni specifiche.

SCHEMI DI GESTIONE DELLA MEMORIA

1) ALLOCAZIONE CONTIGUA

I processi vengono allocati in memoria in posizioni contigue all’interno di una partizione. La memoria è divisa

infatti in partizioni, che possono essere di dimensioni fisse o variabili.

- Partizioni fisse

Insieme di partizioni di dimensioni definite e spesso diverse. Si spreca però molto spazio nel caso in

cui un processo occupa uno slot che ha a disposizione più risorse di quelle che effettivamente gli

occorrono. Anche il supporto per la rilocazione dinamica diventa un problema.

L’assegnazione della memoria viene effettuata dallo scheduler a lungo termine, impostando una

coda per ogni partizione (possono però esserci partizioni vuote e job nelle altre code) oppure una

coda unica per tutte le partizioni (con algoritmi FCFS o di scansione della memoria come il best-fit-

only e best-available-fit). Sono entrambi semplici da implementare, ma limitati dal numero di

partizioni e affetti da frammentazione interna (se la dimensione della partizione è maggiore del job)

ed esterna (se vi sono partizioni inutilizzate perché non soddisfano le richieste dei processi in attesa).

- Partizioni variabili

La dimensione delle partizioni è adattata al processo, eliminando la frammentazione interna. Il

problema è ancora l’assegnazione di memoria al job, la rilocazione dinamica e l’intensificarsi della

frammentazione esterna. Il sistema operativo tiene traccia delle partizioni allocate e degli spazi liberi

(hole). Quando arriva un processo, gli viene allocata memoria usando tre algoritmi: First-Fit (la prima

buca grande a sufficienza, il miglior algoritmo), Best-Fit (la più piccola buca grande a sufficienza),

Worst-Fit (la buca più grande).

Per ridurre la frammentazione, si ricorre alla compattazione, possibile solo se la rilocazione è

dinamica perché richiede la modifica del registro di base, inoltre è molto costosa. Il contenuto della

memoria viene spostato in modo da rendere contigui i blocchi di un processo.

- Buddy System 2

Compromesso tra partizioni fisse e variabili, consiste in una serie di liste di blocchi di dimensione 2 ,

L U

con L < k < U, dove 2 è il più piccolo blocco allocato e 2 è il più grande. Quando arriva una richiesta,

si cerca un blocco libero con dimensione adatta purché sia di una potenza di 2. Quando un processo

rilascia la memoria, il blocco viene compattato con altri blocchi liberi adiacenti e torna a far parte

k k

della lista dei blocchi di dimensione corrispondente (es: blocco 2 libero + blocco 2 libero = blocco

k+1

2 libero). La compattazione risulta così veloce e la frammentazione interna è causata solo da

L

blocchi di dimensione 2 .

2) PAGINAZIONE

Tecnica per eliminare la frammentazione esterna. Permette che lo spazio di un indirizzamento fisico

di un processo non sia contiguo, allocando la memoria fisica dove è disponibile. La memoria fisica

viene divisa in frame di dimensione fissa, mentre la memoria logica viene divisa in blocchi di

dimensione uguale ai frame detti pagine. Per eseguire un programma di n pagine bisogna trovare n

frame liberi. Si utilizza una tabella delle pagine (page table) per ogni processo per mantenere traccia

di quale frame corrisponde a quale pagina e quindi poter tradurre gli indirizzi. La frammentazione

interna è presente eventualmente solo nell’ultima pagina. L’indirizzo logico viene diviso in due parti:

numero di pagina (indice nella tabella delle pagine) e offset (per definire l’indirizzo fisico). L’MMU

sarà quindi più complesso di quelli precedenti. L’efficienza per l’implementazione della tabella delle

pagine è fondamentale e si riduce a due metodi.

Nell’implementazione tramite registri le righe della tabella delle pagine sono mantenute nei registri,

però è efficiente solo se il numero di righe è limitato e allunga i tempi di context switch con il

salvataggio dei registri.

Nell’implementazione in memoria la tabella risiede in memoria e vengono utilizzati solo i registri

PTBR (punta alla tabella delle pagine) e PTLR (contiene la dimensione della tabella, opzionale). Il

context switch è più breve perché richiede solo la modifica del PTBR. Ogni accesso a dati/istruzioni

però richiede due accessi in memoria. Il problema può essere risolto tramite una cache veloce e

costosa, la TLB (tranlation look-aside buffers) che confronta l’elemento fornito con il campo chiave

di un piccolo sottoinsieme di righe. Il TLB viene ripulito per evitare mapping di indirizzi errati ad ogni

context switch. Se la pagina cercata è nel TLB, si ha un miglioramento del 10% in velocità.

La protezione viene realizzata associando un bit ad ogni frame, chiamato bit di validità, oltre a un bit

di accesso per marcare se una pagina è modificabile o eseguibile. In caso di codice condiviso, ci sarà

un'unica copia fisica ma più copie logiche.

Sono necessari meccanismi per gestire il problema della dimensione della tabella delle pagine, poiché

nelle architetture moderne lo spazio di indirizzamento virtuale è molto maggiore dello spazio fisico.

Una soluzione consiste nella paginazione multilivello, cioè nella paginazione della tabella delle

pagine. Così facendo, solo alcune parti della tabella delle pagine sono salvate in memoria mentre

altre sono salvate su disco. Si possono creare fino a 4 livelli di paginazione, che però richiedono per

la conversione 4 accessi a memoria.

Un'altra soluzione consiste nella tabella delle pagine invertita, una tabella unica nel sistema avente

una riga per ogni pagina fisica, contenente l’indirizzo virtuale della pagina che occupa quel frame e

informazioni sul processo che la usa. Di conseguenza ci sarà un aumento del tempo necessario per

cercare un riferimento ad una pagina. È necessario inoltre un meccanismo per gestire le collisioni

quando diversi indirizzi virtuali corrispondono allo stesso frame, con una tabella hash ad esempio si

ridurrebbe il tempo di ricerca.

3) SEGMENTAZIONE

Schema che consiste in una collezione di segmenti di dimensione differente indicati da nome e

lunghezza. L’indirizzo logico è quindi composto da numero di segmento e offset. La tabella dei

segmenti è una mappa di indirizzi logici bidimensionali in indirizzi fisici unidimensionali. Ogni riga

contiene una base e un limite. È simile alla tabella delle pagine, con STBR (punta alla locazione della

tabella dei segmenti in memoria) e STLR (numero di segmenti usati da un programma). Il TLB viene

usato per memorizzare le righe maggiormente usate, come nella paginazione.

La protezione viene garantita con l’associazione di bit di modalità (read/write/execute) e valid bit. Se

si vuole condividere qualcosa, basta inserirlo in un segmento, addirittura intere librerie.

Il S.O. deve allocare spazio in memoria per tutti i segmenti di un programma che hanno lunghezza

variabile, con algoritmi come first-fit e best-fit. È possibile la frammentazione esterna per segmenti

di dimensione significativa.

4) SEGMENTAZIONE PAGINATA

È possibile combinare i due schemi per migliorarli entrambi, paginando i segmenti. Ogni segmento è

suddiviso in pagine e possiede una sua tabella delle pagine. Ogni tabella dei segmenti non contiene

l’indirizzo base di ogni segmento, ma l’indirizzo base delle tabelle delle pagine per ogni segmento.

Elimina così il problema dell’allocazione dei segmenti e della frammentazione esterna.

MEMORIA VIRTUALE

Solo una parte del programma in esecuzione può essere in memoria. Lo spazio di indirizzi logici può essere

molto più grande dello spazio di indirizzi fisici, così facendo più processi possono essere mantenuti in

memoria.


PAGINE

43

PESO

3.79 MB

PUBBLICATO

7 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea magistrale in ingegneria e scienze informatiche
SSD:
Università: Verona - Univr
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher martini.enrico1997 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à Verona - Univr o del prof Pravadelli Graziano.

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 magistrale in ingegneria e scienze informatiche

Test completo per Architettura degli Elaboratori
Appunto
Appunti riassuntivi di Logica
Appunto
Logica - Formulario
Appunto