Che materia stai cercando?

Sintesi del Corso di Sistemi Operativi Appunti scolastici Premium

Appunti di sistemi operativi basati su appunti personali del publisher presi alle lezioni del prof. Tegolo dell’università degli Studi di Palermo - Unipa, facoltà di Scienze matematiche fisiche e naturali, Corso di laurea in informatica. Scarica il file in formato PDF!

Esame di Sistemi operativi docente Prof. D. Tegolo

Anteprima

ESTRATTO DOCUMENTO

6

I processi compute-bound hanno in genere burst di CPU lunghi e attese di I/O poco frequenti,

mentre i processi I/O-bound hanno burst di CPU brevi e attese di I/O frequenti. Il fattore chiave è la

7

lunghezza del burst di CPU e non quella del burst di I/O .

I processi I/O-bound vengono così chiamati perchè non eseguono molti calcoli mentre le loro

richieste di I/O vengono esaudite e non perchè le loro richieste di I/O durano a lungo. L'invio

all'hardware di una richiesta di lettura di un blocco del disco comporta lo stesso tempo, richiesto

dall'elaborazione dei dati dopo il loro arrivo. Più sono veloci le CPU più i processi tendono ad

essere I/O-bound.

Processo CPU-bound:

Burst di CPU lunghi In attesa di I/O

Processo IO-bound:

Busrt di CPU brevi Tempo

2.5.3 Quando schedulare

Si deve schedulare quando:

1. un processo crea un processo figlio: lo scheduler prende una decisione su quale dei 2

mandare in esecuzione dato che sono entrambi nello stato di pronto;

2. un processo termina spontaneamente: il processo terminato non può più essere attivato

perchè non esiste, quindi si attiva lo scheduler per assegnare la CPU ad un processo presente

nella lista dei processi pronti;

3. quando un processo si blocca su un'operazione di I/O, su di un semaforo, o per qualche

altra ragione, si deve scegliere un altro processo per la sua esecuzione;

4. quando si attiva un'interruzione di I/O: deve essere presa una decisione di schedulazione;

il processo, che era stato bloccato dal dispostivo in cui si era effettuato un I/O, adesso è

pronto per essere eseguito, sarà compito dello scheduler identificare quale processo mandare

in esecuzione:

1. il processo appena posto sullo stato di pronto;

2. quello che era stato bloccato;

3. uno dei processi presenti nella lista dei processi pronti.

2.5.4 Tipi di schedulatore

Gli algoritmi di schedulazione possono essere suddivisi in 2 grandi famiglie:

preemptive: lo schedulatore sceglie un processo e lo lascia girare sino al massimo

– consentito; questa quantità è predefinita ed è chiamata quantum di tempo. Se il processo è

ancora in esecuzione alla fine del suo quantum di tempo, questo viene sospeso e viene

eseguito un altro preso dalla lista dei processi pronti; l'eventuale assenza di processi mette in

gioco il processo appena schedulato;

non preemptive: in questo caso viene scelto un processo (dallo scheduler) e viene lasciato

– in esecuzione finchè non termina spontaneamente la sua esecuzione.

6 Burst di CPU: uso continuato della CPU da parte di un processo (burst=raffica)

7 Burst di I/O: uso continuato di un dispositivo di I/O da parte di un processo

2.5.5 Categorie di algoritmi di scheduling

Gli schedulatori si classificano per categorie di sistemi di elaborazione, in quanto la politica dello

schedulatore varia tra i diversi sistemi:

sistemi batch: non sono presenti utenti impazienti in attesa ai loro terminali di una rapida

– risposta;

sistemi interattivi: in questi sistemi occorre prevedere una gestione preemptive delle risorse

– per evitare che un processo acquisisca la CPU impedendo ad altri processi di proseguire i

loro job o di offrire servizi;

sistemi real-time: in generale, sono di supporto ad altri processi, quindi, poichè tali processi

– tendono a liberare la CPU rapidamente, sono necessari scheduler non-preemptive.

2.5.6 Obiettivi degli algoritmi di scheduling

Gli obiettivi sono classificati per tipologia di schedulatore:

1. Sistemi batch:

1. Throughput: massimizzare i processi nell'unità di tempo;

2. Tempo di turnaround: minimizzare il tempo tra la richiesta e la conclusione;

3. Uso della CPU: tenere occupata la CPU per tutto il tempo del suo utilizzo.

2. Sistemi interattivi:

1. Tempo di risposta: rispondere velocemente alle richieste;

2. Proporzionalità: andare incontro alle aspettative degli utenti.

3. Sistemi real-time:

1. Rispettare le scadenze: evidare la perdita dei dati;

2. Prevedibilità: evitare la degradazione qualitativa dei sistemi multimediali.

4. Obiettivi comuni:

1. Equità: dare ad ogni processo una porzione equa della CPU

2. Applicazione delle politiche di sistema: mettere in atto la politica di sistema;

3. Bilanciamento: tenere occupate tutte le parti del sistema.

2.5.6.1 Obiettivi dei processi batch

Throughput: è il numero di job per unità di tempo che il sitema completa. Mescolare job CPU

bound con job I/O bound migliora il throughput del sistema: separando le 2 classi si rischia di avere

tempi in cui la CPU è pesantemente occupata a discapito dell'uso dei dischi e tempi in cui l'I/O è

eccessivamente usato a discapito di una CPU inattiva.

Turnaround: è il tempo medio statistico dei processi dal momento in cui viene richiesto il servizio

fino al loro completamento. Un algoritmo che massimizza il throughput non necessariamente

minimizza il turnaround.

Per esempio, supponiamo di avere job estremamente corti e job estremamente lunghi,

massimizzando il troughput lo schedulatore è portato ad eseguire i job corti, e, se questi vengono

prodotti a scadenza regolare, i job lunghi non saranno attivati sulla CPU, quindi tempi di attesa

infiniti per i job lunghi e anche il turnaround sarà infinito.

Uso massiccio della CPU: l'uso massiccio della CPU garantisce l'esecuzione di più processi e

migliora le performance di un job.

2.5.6.2 Obiettivi dei processi interattivi

Tempo di risposta: tempo intercorso tra l'invio di un comando e l'arrivo del risultato. Priorità ai

processi interattivi anzichè a quelli batch.

Proporzionalità: tempo impiegato per eseguire un'attività. In genere l'utente fa una stima del tempo

necessario per compiere un'attività (molto spesso errata) così quando una richiesta percepita come

complessa impiega molto tempo (e.g. chiamata ad un provider: circa 45 secondi), lo accetta; invece,

l'utente è insofferente quando una richiesta molto semplice impiega molto tempo (e.g. sgancio del

modem da internet: 45 secondi circa).

In alcuni casi lo schedulatore riesce a bilanciare la proporzionalità, in altri, come il modem, non può

fare nulla.

2.5.6.3 Obiettivi dei processi real-time

Rispettare le scadenze: uno scheduler orientato ai sistemi real-time ha la necessità di rispettare i

tempi di risposta di un dispositivo. Se l'obiettivo, ad esempio, fosse un processo di acquisizione dati

da un dispositivo, la cattiva gestione delle scadenze potrebbe portare alla perdita dei dati.

Prevedibilità: processi orientati alla multimedialità (video e audio) sono estramente prevedibili e

regolari e questo è per garantire il rispetto delle scadenze per non degradare nè la qualità video nè

quella audio.

2.5.7 Scheduling per processi batch

Gli algoritmi di schedulazione dei processi batch possono essere catalogati in 4 grandi famiglie;

inoltre alcuni degli algoritmi utilizzati per i sistemi interattivi possono essere utilizzati per tali

sistemi. Le 4 famiglie sono:

1. First-Come First-Served: il primo processo che arriva è quello servito (struttura FIFO

coda);

2. Shorted Job-First: viene eseguito per primo il processo più breve in termini di tempo di

esecuzione;

3. Shorted Remaining Time Next: viene eseguito il job che necessita del più breve tempo di

esecuzione per terminare la sua elaborazione;

4. Schedulatore a 3 livelli: per I/O, memoria e CPU.

2.5.7.1 First-Come First-Served

In questo caso i processi sono assegnati alla CPU nell'ordine in cui la richiedono.

Fondamentalmente c'è una singola coda di processi in stato di pronto. Quando il primo lavoro entra

nel sistema, è avviato immediatamente e gli è consentito di essere eseguito finchè vuole. Non viene

interrotto perchè è da troppo tempo in esecuzione. All'arrivo degli altri lavori, questi sono messi in

fondo alla coda. Quando il processo in esecuzione si blocca, viene eseguito il primo processo della

coda. Quando un processo bloccato ritorna pronto, è messo in fondo alla coda come un processo

appena arrivato.

Scegliere un processo da eseguire significa toglierlo dalla testa dei job pronti, mentre aggiungere un

nuovo job significa inserire un nuovo processo in fondo alla coda.

Svantaggi: lo svantaggio di questo scheduler è nel fatto di essere non-preemptive e questo risulta

evidente quando siamo in presenza di pochi processi CPU-bound e molti processi I/O-bound.

Per esempio, supponiamo di avere un processo CPU-bound che viene eseguito per 1 secondo alla

volta, poi legge un blocco dal disco e richiede la CPU per un altro secondo. Nella coda dei processi

pronti, inoltre, si trovano molti processi I/O-bound ciascuno dei quali deve eseguire 1000 letture: in

questo modo ogni processo I/O-bound impiegherà almeno 1000 secondi per effettuare tutte le 1000

letture, in quanto dovrà attendere 1000 secondi dovuti al processo CPU-bound. Ad ogni richiesta di

lettura la CPU sarà rilasciata e assegnata al processo CPU-bound.

In alternativa, uno schedulatore preemptive assegnerà un intervallo di 10ms al processo CPU-

bound, così ogni processo I/O-bound impiegherà 10 secondi per effettuare la lettura.

2.5.7.2 Shorted Job First

È un algoritmo di tipo non-preemptive, ha come presupposto la conoscenza anticipata dei tempi di

esecuzione di ogni job (e.g. computo delle stesse operazioni su dati diversi) e la sua strategia è di

eseguire il job più corto per primo.

In generale, siano dati 4 processi A,B,C,D, con tempi di escuazione pari ad a b c d, il tempo di

turnaround sarà dato da:

turnaround = (a+(a+b)+(a+b+c)+(a+b+c+d))/4 = (4a+3b+2c+d)/4

Da ciò ci si rende conto che il tempo di esecuzione del primo processo influenza pesantemente il

tempo di turnaround. Quindi la strategia di eseguire il processo più corto per primo è ottimale.

Esempio:

Siano A,B,C,D 4 processi che impiegano rispettimante 8, 4, 4 e 4 minuti in esecuzione. Il loro

tempo di turnaround sarà rispettivamente 8, 12, 16 e 20 e il turnaround medio sarà dato dalla media

dei 4 turnaround, cioè: (8+12+16+20)/4=14 minuti.

Se invece il primo a partire fosse il processo più breve, i tempi di turnaround sarebbero 4, 8, 12 e 20

e il turnaround medio sarebbe (4+8+12+20)/4=11 minuti.

Lo S.J.F. presenta però uno svantaggio: deve conoscere tutti i job che saranno mandati in

esecuzione. Infatti, supponiamo di avere 5 job A B C D E con tempi di esecuzione pari a 2,4,1,1,1 e,

inoltre, A e B arrivano al tempo t=0, C, D ed E arrivano al tempo t=3 così che il turnaround sarà

uguale a 6,4;

Se invece avessimo la sequenza 4 1 1 1 2 il tempo di turnaround risulterebbe pari a 6,2-

2.5.7.3 Shortest remaining time next

È una versione preemptive dell'algoritmo SJF. In questo caso lo scheduler sceglie sempre il

processo il cui tempo che manca alla fine dell'esecuzione è il più breve. Anche qui il tempo di

esecuzione deve essere conosciuto in anticipo. All'arrivo di un nuovo lavoro il suo tempo totale è

confrontato al tempo restante dei processi attuali. Se il nuovo lavoro ha bisogno di minor tempo del

processo attuale per terminare, il processo attuale viene sospeso ed è avviato il nuovo lavoro.

2.5.7.4 Schedulatore a 3 livelli

Schedulatore di ingresso: decide quale processo deve essere ammesso nel sistema, gli altri

vengono tenuti nella coda d'ingresso per essere selezionati in futuro.

Schedulatore di memoria: decide quali processi devono essere tenuti in memoria e quali vanno sul

disco.

Schedulatore di CPU: decide quali processi eseguire tra quelli presenti nella coda dei processi

pronti.

2.5.8 Scheduling nei sistemi interattivi

Gli schedulatori per i sistemi interattivi possono andar bene anche per i sistemi batch; essi possono

essere rivolti sia alla CPU che alla memoria ma non all'I/O.

Quindi, nei sistemi interattivi possiamo parlare di schedulatori a 2 livelli e non a 3.

Tra quelli orientati alla CPU abbiamo gli schedulatori:

1. round-robin;

2. con priorità;

3. a code multiple;

4. shortest process next;

5. a garanzia;

6. a lotteria;

7. fair-share;

2.5.8.1 Scheduler round-robin

Il quanto di tempo (o quantum di tempo) è un intervallo di tempo all'interno del quale un processo

può restare in esecuzione sulla CPU.

Tra le caratteristiche del round-robin, esso è semplice, imparziale, usatissimo e vecchissimo.

Lo schedulatore round-robin per assegnare la CPU ai processi fa riferimento al quanto di tempo.

Il processo acquisisce la CPU per un quanto di tempo, trascorso il quale, la CPU sarà rilasciata e

assegnata a un altro processo.

Qualora il processo terminasse il proprio compito (blocco per I/O, fine naturale) prima dello scadere

del quanto di tempo, la CPU sarà assegnata al primo processo pronto senza aspettare la fine del

quanto.

La domanda è: quanto deve essere grande il quantum di tempo?

Il quanto di tempo assicura che allo scadere del tempo il processo presente nella CPU sarà sostituito

con un altro, quindi ogni quanto di tempo si svolgeranno compiti amministratici come scaricare,

caricare, assegnare, etc., cioè tempo di overhead per la gestione.

Per esempio, supponiamo di avere un quanto di tempo di 4 ms e che il tempo per la gestione di un

processo sia pari a 1 ms, in questo modo avremo il 25% del tempo di CPU sprecato a fare gestione.

Questo conduce ad innalzare il quanto di tempo. Se fosse esteso a 100 ms, il tempo sprecato sarebbe

solo l'1%, il che è accettabile. Però, anche in quest'ultima situazione, ci sono dei contro: siano 10

utenti che digitano contemporaneamente (o quasi) il <RET> dalla tastiera per l'esecuzione di un

processo con un quantum di 100ms; l'ultimo utente accodato tra i processi pronti, nel caso peggiore,

cioè quando tutti utilizzano i 100 ms, dovrà attendere 1 secondo prima di ottenere la CPU.

In conclusione, si hanno delle prestazioni degradanti: assegnare un quanto di tempo troppo breve

provoca troppi cambi di contesto e peggiora l'efficienza della CPU. Di contro, un quanto di tempo

lungo può provocare tempi di risposta lunghi per richieste interattive brevi.

2.5.8.2 Scheduler con priorità

L'algoritmo di schedulazione round-robin considera tutti i processi di pari importanza. In realtà, in

ogni elaboratore esistono processi di diversa importanza. La tecnica della priorità è utile per

garantire l'importanza di esecuzione di un processo.

In generale, i processi a più alta priorità sono eseguiti frequentemente dalla CPU. Lo schedulatore,

per evitare che tali processi occupino indefinitivamente la CPU, fino allo svolgimento del proprio

compito, abbassa la priorità del processo in esecuzione (ad ogni interruzione) sino a quando non

raggiunge la priorità del processo con priorità più alta presente nella lista dei processi pronti.

L'assegnazione della priorità più alta può essere:

statica: è assegnata al processo in relazione alla famiglia di appartenenza e può solo

– diminuire per dar spazio agli altri processi nella CPU;

dinamica: è assegnata dinamicamente ad un processo; in generale viene attribuito un valore

– pari a 1/f con f = frazione di quanto di tempo impiegata.

Per esempio: quantum di tempo = 50ms

Processo A ha impiegato 1ms

Processo B ha impiegato 25ms

Priorità di A = 1/(1/50)=50

Priorità di B = 1/(25/50)=1/(1/2)=2

I processi a priorità vengono raggruppati per classi all'interno delle quali vengono usati algoritmi di

scheduling round-robin.

2.5.8.3 Scheduler a code multiple

Lo scheduler a code multiple può essere visto come un estensione dello scheduler a priorità. In

questo caso la priorità non è percepita come diritto di prelazione sulla CPU (maggiore priorità

maggior diritto di acquisire la CPU), ma come diritto di persistenza sulla CPU.

Lo scheduler, piuttosto che aumentare le priorità, si comporta in maniera totalmente diversa,

aumenta i quanti di tempo e diminuisce la priorità.

I processi con priorità più alta vengono eseguiti con 1 quanto di tempo, quelli nella classe

immediatamente sottostante sono eseguiti con 2 quanti, quelli ancora sotto con 4, etc...

Ogni processo che consuma tutto il suo quanto di tempo, viene spostato nella classe sottostante: in

tal senso lo schedulatore abbassa la priorità ma innalza il tempo di persistenza nella CPU,

Processi che corrono verso il basso avranno maggiore persistenza nella CPU, ma saranno caricati

meno frequentemente: questo garantisce l'esecuzione dei processi più piccoli con tempi di attesa

minori.

Ad esempio: supponiamo che un processo per la sua esecuzione abbia bisogna di 100 quanti di

tempo, con un round-robin classico occorrebbero 100 scaricamenti e caricamenti della CPU; invece,

con le code multiple il numero di caricamenti/scaricamenti viene ridotto di molto.

Infatti, la prima volta il processo prende possesso della CPU; alla fine del suo quanto di tempo

questo viene scaricato dalla CPU ed è a questo punto che lo schedulatore lo porrà in una coda con

priorità più bassa assegnandogli 2 quanti, poi 4, 8, 16, 32, 64.

Il processo termina dopo 7 caricamenti (non 100) e, anche se alla fine, per ottenere i suoi 100 quanti

di tempo, ne ha usati solo 37 dei 64 assegnatigli dallo scheduler, ha raggiunto lo scopo di diminuire

l'overhead.

2.5.8.4 Scheduler Shortest Process Next (SPN)

I processi interattivi eseguono di solito uno schema classico: aspettare un comando e quindi

eseguirlo, poi aspettare un nuvo comando ed eseguirlo, etc...

Potremmo minimizzare i tempi di risposta eseguendo il processo più corto. Il problema sta nel

calcolare i tempi di risposta. L'idea è quella di fare delle stime interattive per i processi lanciati

utilizzando la tecnica dell'invecchiamento. La stima potrebbe essere basata sulla media pesata o

esponenziale.

Supponiamo che il tempo stimato per l'esecuzione di un comando all'istante t=0 sia t e che a t=1 sia

0

t , quindi la media pesata sarà dalla data da:

1 S = t

1 0

S = αt + (1-α)S

n+1 n n

S = t

1 0

-----------------------

S = (1/2)t + (1/4)t + (1/8)t + (1/8)t

4 3 2 1 0

Il tempo iniziale pesa meno del tempo corrente

Questo algoritmo di schedulazione è non-preemptive. La stima del tempo di esecuzione permette di

stabilire quale processo può andare in esecuzione secondo lo schema Shorted Job First.

2.5.8.5 Scheduler garantito

L'approccio dello scheduler garantito si basa sul fare delle promesse all'utente per quanto riguarda

le prestazioni e poi mantenerle.

Una promessa realistica può essere quella di assegnare al processo la risorsa CPU in quantità pari a

1/n dove n rappresenta il numero di processi presenti in quell'istante.

Per far ciò, il sistema deve tenere traccia di quanta CPU è stata assegnata ai processi dal momento

in cui questi sono stati creati:

(tempo di CPU assegnato) / (tempo di CPU a cui si ha diritto)

Ovviamente lo schedulatore stabilisce di mandare in esecuzione il processo con rapporto più basso,

fin quando questo rapporto non sarà maggiore di quello del suo concorrente più vicino.

2.5.8.6 Scheduler a lotteria

Lo scheduler a lotteria funziona come una vera e propria lotteria: ad ogni processo vengono

assegnati uno o più biglietti della lotteria e quando l'estrazione sarà effettuata, chi ha più biglietti ha

maggiore probabilità di utilizzo della risorsa (CPU). La regola fondamentale è:

chi detiene una frazione f di biglietti, avrà circa una frazione f della CPU

I processi che cooperano hanno la possibilità di scambiarsi i biglietti in modo da dare al partner

più possibilità di riuscita.

Per esempio, consideriamo un server video: esso deve soddisfare diversi processi che inviano video,

a frequenza diversa (10, 20, 25), ai loro clienti; se a tali processi assegniamo rispettivamente 10, 20,

25 biglietti, i processi hanno una probabilità di soddisfare le aspettative pari a quella richiesta.

2.5.8.7 Scheduler fair-share (quota equa)

Alcuni sistemi, prima di schedulare un processo, prendono in considerazione chi lo possiede. Nel

modello fair-share a ogni utente viene assegnata una frazione di CPU e lo scheduler raccoglie i

processi in modo tale da farla rispettare. Così se a 2 utenti è stato assegnato il 50% della CPU,

l'avranno, indipendentemente da quanti processi abbiano attivi.

Per esempio, si consideri un sistema con 2 utenti, a ognuno dei quali è stato assegnato il 50% della

CPU. L'utente 1 ha 4 processi A B C D e l'utente 2 ha solo il processo E. Con il round-round una

sequenza di scheduling potrebbe essere: A E B E C E D E A E B E C E D E ....

D'altro canto, se l'utente 1 ha diritto ad avere il doppio del tempo di CPU dell'utente 2, si potrebbe

avere: A B E C D E A B E C D E ....

2.5.9 Schedulatore nei sistemi real-time

I sistemi real-time in genere di dividono in:

Hard Real Time: hanno scadenze incondizionate da rispettare;

– Soft Real Time: sporadicamente possono non raggiungere l'obiettivo.

Gli eventi a cui i sistemi real-time devono reagire possono essere catalogati in:

periodici: si verificano ad intervalli di tempo regolari;

– aperiodici: non vi è periodicità.

Gli algoritmi possono essere:

statici: prendono le decisioni di schedulazione prima della loro esecuzione;

– dinamici: prendono le decisioni di schedulazione durante la loro esecuzione;

Per esempio: supponiamo di avere nel sistema N eventi periodici e l'evento i-esimo arriva con

periodo P e richiede un tempo di CPU pari a C ; il carico di lavoro per la CPU può essere gestito

i i

solo se la seguente sommatoria risulta vera:

N

Σ (C /P ) <= 1

i i

i=1

3 eventi con periodicità 100 200 e 500 ms richiedono un tempo di CPU pari a 50 30 e 100 ms.

I tre processi potranno quindi essere schedulati in quanto

(50/100) + (30/200) + (100/500) = 0,5+0,15+0,2 = 0,85 < 1

2.5.9.1 Schedulatore nei sistemi real-time: proprietà

controllano e monitorizzano processi fisici entro limiti temporali;

– sono affidabili per lunghi periodi;

– non richiedono intervento umano diretto;

– operano sotto vincoli più severi rispetto agli schedulatori;

– devono operare con la minima memoria e il minimo supporto hardware;

– sono più difficili da sviluppare e da corregere;

– non usano memoria di massa;

– non interagiscono con il display e/o la tastiera.

– Pipe

Processo Comunicazione FIFO Processo

scrittore lettore

2.5.9.2 Schedulatore nei sistemi real-time: applicazioni

sistemi embedded: un componente di un sistema hardware/software più ampio;

– sistemi concorrenti: il sistema controlla simultaneamente e/o reagisce ad aspetti differenti

– dell'ambiente;

sistemi sicuri: affidabili, ma anche sicuri; il fallimento dell'esecuzione non provoca danni a

– persone o cose. Tipicamente lo sviluppo di sistemi sicuri richiede la ridondanza;

sistemi reattivi: il sistema ha una continua interazione con l'ambiente, il quale fornisce

– eventi ai quali il sistema reagisce. La risposta del sistema è tipicamente dipendente dallo

stato.

2.5.10 Politiche e meccanismi degli schedulatori

Lo scheduler, in generale, per le sue decisioni, non conosce informazioni provenienti dai processi

utenti, quindi, anche se effettua uno tra i vari modelli di scheduling, quasi mai effettua la scelta

migliore, ma effettua la più opportuna.

Per effettuare la scelta migliore sono essenziali parametri forniti dagli utenti, e a volte lo

schedulatore permette all'utente di definire la sequenza di schedulazione per i processi figli.

In questo modo si è scorporato il meccanismo di schedulazione dalla politica di schedulazione:

il meccanisno sta nel kernel;

– la politica è stabilita da un processo utente.

2.5.11 Schedulazione dei Thread

Possibile scheduling di thread utente: lo schedulatore assegna un processo alla CPU e all'interno del

suo quanto di tempo possono essere eseguiti i thread dettati dall'utente, ma non quelli di un altro

processo.

Possibile scheduling di thread nel kernel: lo schedulatore assegna un processo alla CPU, all'interno

di un intervallo possono essere eseguiti i thread definiti dall'utente, ma anche quelli di un altro

processo in quanto i thread sono definiti a livello kernel.

I thread a livello kernel sono più dispendiosi, in overhead, di quelli definiti dall'utente, in quanto

ogni volta che un thread si blocca se ne carica un altro che può non appartenere allo stesso

processo con conseguente caricamento del contesto.

2.6 Le pipe in UNIX

Le pipe sono canali di comunicazione unidirezionali che costituiscono uno strumento di

comunicazione tra processi UNIX generati dallo stesso processo.

La funzione per creare una pipe è: che inizializza in piped 2 descrittori:

int pipe(int piped[2])

piped[0] per la lettura;

piped[1] per la scrittura;

La lettura e la scrittura sulla pipe sono ottenute mediante le normali primitive di lettura e scrittura

proprie del linguaggio (e.g. e ).

read write

I valori di ritorno della funzione pipe sono:

0 : tutto ok;

– -1 : se si ha un errore

– errno:

EMFILE: troppi file descriptor in uso;

– ENFILE: la system file table è piena;

– EFAULT: filedes non trovato

Sincronizzazione. L'accesso alla pipe è regolato dal seguente meccanismo: la lettura di una pipe da

parte di un processo è bloccante se la pipe è vuota, in attesa che arrivino i dati; la scrittura su una

pipe da parte di un processo è bloccante se la pipe è piena.

Le pipe sono dette anche pipe anonime (unnamed pipe) perchè non sono associate ad alcun nome

nel file system; quindi solo i processi che possiedono i descrittori possono comunicare attraverso

una pipe.

Inoltre, la tabella dei file aperti di un processo, contenente i descrittori della pipe, viene duplicata

per i processi figli, quindi la comunicazione attraverso una pipe anonima è possibile solo per

processi in relazione di parentela che condividono un progenitore.

Codice pipe.c

#include <stdio.h>

#include <ctype.h>

#include <stdlb.h>

#include <unistd.h>

#include <sys/wait.h>

#define N_MESSAGGI 10

int main (){

int pid, j, k, piped[2]; /*apre la pipe creando 2 file descriptor, uno

per la lettura e l'altro per la scrittura. Vengono memorizzati

in piped[2] */

if(pipe(piped)){

print("Errore! File %s, line %d\n",__FILE__,__LINE__);

exit(EXIT_FAILURE);

}

if((pid=fork())<0){

print("Errore! File %s, line %d\n",__FILE__,__LINE__);

exit(EXIT_FAILURE);

}

else if(pid==0){ /* il figlio eredita piped[1] */

close(piped[1]); /*figlio lettore pipe, chiudi piped[1] */

for(j=1;j<=N_MESSAGGI;j++){

read(piped[0],&k,sizeof(int));

printf("Figlio %d:ho letto dalla pipe # %d\n",getpid(), k);

}

exit(SUCCESS);

}

else{ /* processo padre */

/*il padre è scrittore sulla pipe, chiude piped[0] */

close(piped[0]);

for(j=1;j<=N_MESSAGGI; j++){

write(piped[1], &j, sizeof(int));

}

wait(NULL); break;

}

}

Tutti i processi devono chiudere i descrittori di PIPE tramite la close() per evitare situazioni di

deadlock. 3 – DEADLOCK

In un ambiente multiprogrammato più processi possono entrare in competizione tra loro per

ottenere un numero finitio di risorse.

Si definisce deadlock ( stallo ) un insieme di processi bloccati dove ciascun processo possiede una

risorsa ed attende di acquisire una risorsa allocata ad un altro processo dell'insieme.

Un tipico esempio di situazione di deadlock è il "problema dei 5 filosofi a cena":

Piatto Forchetta

Nell'immagine, i piatti sono i processi e le forchette sono le risorse. Ci sono 5 piatti (uno per

filosofo) e 5 forchette. Ogni filosofo per mangiare necessita di 2 forchette (destra e sinistra). Se ogni

filosofo (processo) prendesse la forchetta (risorsa) alla propria sinistra, nessuno avrebbe disponibile

la forchetta di destra e, dato che ognuno ha bisogno di 2 forchette per mangiare, si verrebbe a creare

appunto una situazione di stallo: deadlock.

Altri esempi dove possiamo avere situazioni di deadlock sono nelle:

risorse hardware:

– nei primi sistemi batch alcuni sistemi di spooling richiedevano il completamente

– dell'output prima di cominciare la stampa;

se l'output era maggiore della dimensione del disco il sistema si bloccava;

risorse software:

– semafori A e B inizializzati a 1:

– P0 P1

Wait(A); Wait(B);

Wait(B); Wait(A);

Esempio di stallo hardware:

Supponiamo di avere 2 processi che vogliono registrare su di un CD un documento digitalizzato da

uno scanner:

1. il processo P1 chiede il permesso di utilizzare lo scanner ed è autorizzato;

2. il processo P2 chiede il permesso di utilizzare il masterizzatore ed è autorizzato;

3. a questo punto, P1 chiede l'uso del masterizzatore; ovviamente la richiesta viene rifiutata e

P1 viene bloccato;

4. successivamente, P2 fa una richiesta di uso dello scanner che ovviamente viene rifiutata,

ponendo P2 in blocco.

Dopo questi 4 passi, i 2 processi sono in deadlock. P1 e P2 sono bloccati poichè ognuno di essi

necessita della risorsa allocata all'altro:

P1 P2

3 4

1 2

Scanner Masterizzatore

Esempio di stallo software:

Nei sistemi che gestiscono database si possono verificare situazioni di stallo sui processi che

gestiscono la lettura e la scrittura.

Supponiamo che 2 processi P1 e P2 stiano referenziando 2 record R1 e R2 e quindi hanno bloccato

tali risorse; in seguito, i 2 processi richiedono i record in modo incrociato, cioè P1 chiede R2 e P2

chiede R1: ovviamente anche qui si verifica il deadlock.

3.1 Le risorse

I deadlock sono associati al concetto di risorsa disponibile.

Una risorsa è un qualsiasi oggetto hardware o software che sia in grado di suscitare interesse in un

certo istante di tempo ad un processo (stampanti, monitor, file, record, etc).

3.1.1 Risorse preemptve e non-preemptive

Una risorsa preemptive è una risorsa che può essere tolta la processo senza provocare crisi.

Un esempio di risorsa preemptive è la memoria centrale.

Ad esempio, siano dati 2 processi P1 e P2 che devono stampare un documento:

il processo P1 ha il processo della stampante e inizia a stampare; dopo il suo quanto di

– tempo viene messo in blocco;

P2 richiede la stampante, ma questa è stata assegnata a P1, quindi P2 non può stampare.

Siamo quindi in una situazione di stallo dove P2 non può stampare e P1 per stampare ha bisogno

della memoria: P1 può utilizzare la risorsa memoria in quanto essa è preemptive; la memoria verrà

sottratta a P2 e sarà destinata a P1 senza creare crisi di elaborazione a P2.

Una risorsa non-preemptive è una risorsa che non può essere allocata ad altri processi senza

provocare la crisi del processo a cui è stata tolta.

Per esempio, se un processo P1 ha iniziato a scrivere su di un CD e lo si priva improvvisamente del

masterizzatore, il CD sarà incomprensibile in lettura.

In generale i deadlock si hanno con le risorse non-preemptive. Per le risorse preemptive è possibile

risolvere lo stallo.

3.2 Condizioni e modelli per le situazioni di stallo

3.2.1 Condizioni di stallo delle risorse (da Coffman 1971)

Una situazione di stallo può verificarsi se si verificano contemporaneamente queste 4 condizioni:

1. mutua esclusione: ogni risorsa è assegnata ad un solo processo oppure è disponibile;

2. prendi e aspetta (hold and wait): i processi che già hanno richiesto ed ottenuto delle

risorse, ne possono richiedere altre per essere eseguiti;

3. non-preemptive (impossibilità di prelazione): le risorse che sono state già assegnate a un

processo non gli possono essere tolte in modo forzato ma devono essere rilasciate

spontaneamente dal processo che li detiene;

4. attesa circolare: deve esistere una catena circolare di processi, ognuno dei quali aspetta il

rilascio della risorsa da parte di un altro processo.

Queste 4 condizioni devono essere tutte presenti affinchè ci sia una situazione di stallo; se una di

esse non è presente, allora non ci sarà nessuna situazione di stallo presente nel sistema.

3.2.2 Modelli per le situazioni di stallo

La risorsa R trattiene il processo A

R A Il processo Bfa richiesta della risorsa S

B S

D U Il processo D possiede la risorsa T.

Il processo C possiede la risorsa U.

Quando D chiede U, non può ottenerla

perchè usata da C, e quando C chiede T

non può ottenerla perchè usata da D.

Si crea così un'attesa circolare.

T C Il sistema è in deadlock

Risorsa Processo

La freccia da risorsa a processo indica che il processo ha quella risorsa già assegnata.

La freccia da processo a risorsa indica che il processo è in attesa di quella particolare risorsa.

Esempi di processi sequenziali che non portano ad uno stallo sono:

Processo A: richiede R, richiede S, rilascia R, rilascia S;

Processo B: richiede S, richiede T, rilascia S, rilascia T;

Processo C: richiede T, richiede R, rilascia T, rilascia R;

Il SO può mandare in esecuzione un qualsiasi processo non bloccato finchè non avrà finito il suo

compito.

La gestione sequenziale non porta a situazioni di stallo in quanto non è presente nessuna forma di

'parallelismo' con conseguente non competizione sulle risorse.

Nella gestione sequenziale dei processi i tempi dedicati a effettuare I/O non vengono usati da altri

processi per effettuare computo (uso della CPU), quindi una politica sequenziale, in generale, non è

una buona soluzione.

La politica di eseguire processi piccoli che non fanno I/O in una gestione sequenziale dei processi

può essere un alternativa al round-robin.

Un altro esempio di situazione di stallo è:

1. A richiede R;

2. B richiede S;

3. C richiede T;

4. A richiede S;

5. B richiede T;

6. C richiede R;

In questo modo si viene a creare la cosidetta attesa circolare.

Il SO non è obbligato a eseguire i processi come nell'ordine sopra; se assegnare una risorsa ad un

processo può portare a una situazione di stallo, allora il SO può sospendere il processo e assegnare

la risorsa successivamente.

3.2.3 Strategie per le situazioni di stallo

In generale, per trattare le situazioni di stallo, si possono adottare le seguenti strategie:

1. ignorare semplicemente il problema ("algoritmo dello struzzo");

2. rilevare e risolvere: lascia che avvenga il deadlock, rilevalo e regolati di conseguenza;

3. elusione dinamica, tramite un'allocazione attenta delle risorse;

4. prevenzione, tramite la negazione strutturale di una delle 4 condizioni richieste

3.3 Algoritmo "dello struzzo"

"Caccia la testa sotto la sabbia e fai finta che non vi sia alcun problema"

Da questa frase, prende il nome l' "algoritmo dello struzzo": non fare assolutamente niente.

Questo algoritmo viene fuori per rispondere alla domanda: correttezza o convenienza per

l'esecuzione dei processi ?

Correttezza: i matematici trovano inaccettabile l'esistenza di situazioni di stallo e quindi sostengono

che devono necessariamente essere eliminate.

Convenienza: gli ingegneri, invece, trovano ingiustificato correggere un errore che si verifica

raramente (e.g ogni 5 anni) rispetto ai crash giornalieri di una macchina.

In un elaboratore esistono tantissime situazioni di stallo. Si pensi ad esempio alle tabelle gestite dai

SO (tabelle processi, tabelle dei file system,...): queste, poichè sono di dimensione finita, possono

creare una condizione di stalo quando sono piene e un processo tenta di farne richiesta.

In generale, l'approccio adottato dai SO è quello di ignorare il problema: Unix e Windows adottano

questa strategia in quanto è soluzione più accettabile rispetto a quella in cui ogni utente è costretto a

usare una singola risorsa alla volta.

3.4 Prevenire i deadlock

Mutua esclusione , processo e attesa , impossibilità di prelazione e attesa circolare sono

condizioni necessarie e sufficienti affinchè si verifichi il deadlock, quindi basta negarne una per far

sì che il deadlock non avvenga.

3.4.1 Attacco alla mutua esclusione

Sulla condizione di mutua esclusione abbiamo poche possibilità di movimento, in quanto, spesso, la

mutua esclusione su una risorsa (hardware o software) è una condizione intrinseca della risorsa e

non può essere trascurata (e.g. la CPU può essere assegnata ad un solo processo alla volta; un file,

che deve essere utilizzato in scrittura da vari processi, può essere utilizzato da un solo processo alla

volta). Quindi, in generale, su risorse dove è necessaria la mutua esclusione non si può intervenire

per prevenire situazioni di stallo.

3.4.2 Attacco alla condizione di possesso e attesa

Possiamo, invece, intervenire sulla condizione di possesso e attesa. Negare questa condizione

significa appunto "non possedere" o "non attendere". Quindi si può:

richiedere ad un processo di allocare tutte le risorse necessarie prima che inizi l'esecuzione:

– evitare l'attesa;

consentire la richiesta di risorse solo quando il processo non ne possiede alcuna: evitare il

– possesso;

questi 2 approcci comportano un impiego poco efficiente delle risorse, in quanto queste

– risorse vengono allocate al processo e rilasciate tutte insieme, anche se magari il processo ha

bisogno di 1 sola risorsa alla volta: c'è un uso poco efficiente delle risorse;

è possibile che si verifichi l'attesa indefinita, come nel caso del "problema dei filosofi a

– cena".

3.4.3 Attacco alla condizione di impossibilità di prelazione

Anche in questo caso abbiamo una scarsa efficienza nell'utilizzo delle risorse. Negare l'impossibilità

di prelazione significa che:

se un processo, che possiede alcune risorse, richiede un'altra risorsa che non gli può essere

– allocata immediatamente, allora rilascia tutte le risorse possedute;

le risorse rilasciate (prelazionate al processo) vengono aggiunte alla lista delle risorse che il

– processo sta attendendo;

il processo viene avviato nuovamente solo quando può ottenere sia le vecchie che le nuove

– risorse;

vi è quindi una scarsa efficienza: le risorse vengono acquisite e rilasciate tutte insieme per

– evitare appunto il possesso e l'attesa.

3.4.4 Attacco alla condizione di attesa circolare

Più facilmente si può intervenire sulla condizione di attesa circolare: si tratta di fare in modo che si

venga a creare un ciclo all'interno del grafo di allocazione delle risorse.

Ciò è facilmente ottenibile imponendo un ordinamento sulle risorse, numerandole con indici, e

permettendo ad ogni processo di acquisire le risorse in ordine crescente: così facendo non si viene

mai a creare un ciclo all'interno del grafo di allocazione delle risorse.

Esempio:

Ordinamento risorse:

1. stampante;

2. scannere:

3. plotter;

4. unità nastro;

5. unità cd;

Siano poi R e S 2 risorse e A e B 2 processi.

Se R > S allora A non può richiedere S

Se R < S allora B non può richiedere R

Assenza di cicli

3.5 Evitare i deadlock

Presuppone che il sistema conosca a priori informazioni addizionali sulle richieste future dei

processi:

il modello più semplice e utile richede che ciascun processo dichiari il numero massimo di

– risorse di ciascun tipo di cui può usufruire;

algoritmo di deadlock-avoidance: esamina dinamicamente lo stato di allocazione delle

– risorse per assicurare che non si possa verificare mai una condizione di attesa circolare;

gli algoritmi di deadlock-avoidance si basano sul concetto di stato sicuro.

3.5.1 Stati sicuri e stati non sicuri

Uno stato sicuro è uno stato di un sistema dove il sistema non è in stallo e dove è possibile

soddisfare le richieste pendenti eseguendo i processi in un qualche ordine, detto sequenza sicura .

Soltanto se si eseguono i processi in questo ordine siamo sicuri che tutti vanno a completamento e

non si viene a creare una situazione di stallo. Quindi:

se un sistema è in stato sicuro allora non evolve verso il deadlock;

– se un sistema è in stato non sicuro allora può evolvere verso il deadlock: potrebbe ad

– esempio rilasciare autonomamente alcune risorse;

quando un processo richiede una risora disponibile, il sistema deve decidere se l'allocazione

– immediata lasci il sistema in stato sicuro.

Una sequenza <P , P , ..., P > è sicura se, per ogni P , le risorse che P può ancora richiedere

1 2 n i i

possono essergli allocate sfruttando le risorse disponibili più le risorse possedute da tutti i P , con

j

j<i: se le richieste di P non possono essere soddisfatte immediatamente, allora P deve attendere

– i i

finchè P ha terminato;

j

quando P ha terminato, P può ottenere le risorse richieste, eseguire i suoi compiti, restituire

– j i

le risorse allocate e terminare;

quando P termina, P può ottenere le risorse richieste, etc...

– i i +1

Esempio di stato sicuro:

Risorse Risorse Risorse Risorse Risorse Risorse

in possesso max richieste in possesso max richieste in possesso max richieste

P1 3 9 P1 3 9 P1 3 9

P2 2 4 P2 4 4 P2 0 -

P3 2 7 P3 2 7 P3 2 7

Risorse libere: 3 Risorse libere: 1 Risorse libere: 5

a b c

Risorse Risorse Risorse Risorse

in possesso max richieste in possesso max richieste

P1 3 9 P1 3 9

P2 0 - P2 0 -

P3 7 7 P3 0 -

Risorse libere: 0 Risorse libere: 7

d e

a: P1 ha 3 risorse e ne chiede al massimo 9;

– P2 ha 2 risorse e ne chiede al massimo 4;

– P3 ha 2 risorse e ne chiede al massimo 4;

– 3 risorse libere;

b: P2 ha bisogno solo 2 di istanze per completare la sua esecuzione: quindi si assegnano 2 delle

– 3 risorse libere a P2 che termina rilasciando anche le 2 risorse che aveva in precedenza;

c: adesso le risorse le libere sono 5;

d: P3 ha bisogno esattamente di 5 risorse per completare la sua esecuzione;

– quando P3 termina, rilascia le risorse che già aveva: le risorse libere diventano 7;

e: le 7 risorse libere possono essere assegnate P1 che può terminare così la sua esecuzione.

Quindi, abbiamo anche determinato la seguente sequenza sicura: P2 – P3 – P1.

Con questo ordine garantiamo la terminazione dei processi. In un ordine diverso la terminazione

non è garantita.

Esempio di stato non sicuro:

Risorse Risorse Risorse Risorse Risorse Risorse Risorse Risorse

in possesso max richieste in possesso max richieste in possesso max richieste in possesso max richieste

P1 3 9 P1 4 9 P1 4 9 P1 4 9

P2 2 4 P2 2 4 P2 4 4 P2 - -

P3 2 7 P3 2 7 P3 2 7 P3 2 7

Risorse libere: 3 Risorse libere: 2 Risorse libere: 0 Risorse libere: 4

a b c d

Se dallo stato 'a' si assegna un'ulteriore istanza al processo P1 si ottiene uno stato non sicuro ('b')

che conduce a un deadlock ('d').

Nello stato 'b', anche assegnando le 2 risorse libere a P1 o P3 (anzichè a P2) si ottiene un

deadlock.

3.5.2 Algoritmo del banchiere per una singola risorsa

Idea: in base alle risorse disponibili soddisfare prima le richieste di un processo che può completare

la propria esecuzione permetendo così il rilascio di tutte le risorse in suo possesso.

Ciascun processo deve dichiarare a priori il massimo impiego di risorse. Quando un processo

richiede una risorsa, si verifica prima che il nuovo stato sia uno stato sicuro. In caso contrario il

processo attende.

Il nome deriva dal fatto che esso può essere applicato in una banca per evitare che il cassiere

consegni tutto il denaro disponibile, cioè le risorse, e non possa più soddisfare le richieste di tutti i

suoi clienti, cioè i processi.

Risorse Risorse Risorse Risorse Risorse Risorse

in possesso max richieste in possesso max richieste in possesso max richieste

A 0 6 A 1 6 A 1 6

B 0 5 B 1 5 B 2 5

C 0 4 C 2 4 C 2 4

D 0 7 D 4 7 D 4 7

Risorse libere: 10 Risorse libere: 2 Risorse libere: 1

a b c

Quello che fa l'algoritmo è controllare se concedere o meno la richiesta porti a uno stato sicuro

oppure no: se porta ad uno stato sicuro allora la richiesta è concessa, altrimenti è negata.

Nell'immagine, vi sono 4 clienti A B C D, ad ognuno dei quali è stato accordato un certo numero di

unità di credito. Il banchiere sa che non tutti hanno immediatamente bisogno del loro credito

massimo, infatti ha riservato solo 10 unità da rifornire anzichè 22.

I clienti chiedono di volta in volta le risorse. Ad un certo momento troviamo la situazione in figura

'b', che rappresenta uno stato sicuro perchè con 2 unità rimaste il banchiere può ritardare ogni

richiesta, tranne quella di C, permettendo così a C di finire e liberare tutte e 4 le risorse.

Adesso, con 4 unità disponibili, il banchiere può permettere a B o D di ottenere tutte le unità

necessarie,....

Se, invece, a B fosse accordata la richiesta per un'altra unità, si otterrebbe la situazione non sicura

(figura 'c'). Se tutti i clienti richiedessero all'improvviso il loro credito massimo, il banchiere non

potrebbe soddisfarne alcuno e si verrebbe a creare una situazione di deadlock. Dato che un cliente

potrebbe non necessitare dell'intero credito disponibile, uno stato non sicuro non deve condurre a un

deadlock, ma il banchiere non può fare conto su questo comportamento.

L'algoritmo del banchiere considera ogni richiesta nel momento in cui si verifica e vede se il

concederla porti o meno ad uno stato sicuro.

Per valutare se uno stato è sicuro, il banchiere controlla per vedere se ha abbastanza risorse per

soddisfare alcuni clienti. Se è così, si considera che quei prestiti siano ripagati e viene controllato il

cliente che è al momento più vicino al limite, etc... Se alla fine tutti i prestiti possono essere

ripagati, lo stato è sicuro e la richiesta iniziale può essere accordata.

3.5.3 Algoritmo del banchiere per molteplici risorse

Processo Unità a nastro Plotter Stampanti CD ROM

A 3 0 1 1

B 0 1 0 0 E=(6 3 4 2)

C 1 1 1 0 P=(5 3 2 2)

D 1 1 0 1 A=(1 0 2 0)

E 0 0 0 0

Risorse assegnate

Processo Unità a nastro Plotter Stampanti CD ROM

A 1 1 0 0

B 0 1 1 2

C 3 1 0 0

D 0 0 1 0

E 2 1 1 0

Risorse ancora necessarie

La matrice di sopra mostra quante istanze di ogni risorsa siano al momento assegnate a ciascuno dei

5 processi, mentre la matrice di sotto mostra quante risorse ogni processo ha bisogno per finire.

Anche qui, i processi devono dichiarare la loro necessità di risorse totali prima dell'esecuzione, in

modo che il sistema possa calcolare in ogni momento la matrice di sotto.

I tre vettori E, P ed A sono rispettivamente le risorse esistenti, le risorse possedute e le risorse

disponibili.

Per verificare se uno stato è sicuro si deve:

1. individuare una riga R, le cui necessità insoddisfatte relative alle risorse sono tutte minori o

uguali ad A. Se non esiste una riga di questo tipo, il sistema alla fine andrà in deadlock dato

che nessun processo può completarsi;

2. assumere che il processo della riga scelta richieda tutte le risorse di cui necessita e termini e

quindi marcare questo processo come terminato e aggiungere tutte le sue risorse al vettore

A;

3. ripetere i passi 1 e 2 finchè tutti i processi non siano marcati come conclusi o nessun

processo venga lasciato con necessità di risorse che possano essere soddisfatte (nel caso ci

sia un deadlock).

Se nel passo 1 ci sono più processi idonei a essere scelti, non è importante quale sia selezionato per

primo: l'insieme di risorse disponibili diventa maggiore o, alpiù, resta lo stesso.

Supponiamo che adesso il processo B richieda una stampante. Questa richiesta può essere conessa

perchè lo stato che ne risulta è ancora sicuro: il processo D può finire, quindi A o E, e il resto.

Invece, se, dopo aver assegnato a B una delle 2 stampanti rimaste, E volesse l'ultima stampante, il

vettore A diventerebbe (1 0 0 0), portando così ad una situazione di deadlock. Quindi la richiesta di

E deve essere ritardata per un po'.

3.6 Rilevamento e risoluzione dei deadlock

Un'altra tecnica è quella del rilevamento e della risoluzione. Quando è utilizzata questa tecnica, il

sistema non prova a evitare che accadono i dedlock, ma li lascia accadere e cerca di rilevarli quando

avvengono e compiere qualche azione per poi risolverli.

3.6.1 Rilevamento dei deadlock con una risorsa per ciascun tipo

Il caso più semplice è quando esiste una risorsa per ciascun tipo. Per un sistema del genere si può

costruire un grafo delle risorse. Se questo grafo contiene almeno un ciclo, allora esiste un deadlock.

Qualunque processo che faccia parte di un ciclo è in deadlock. Se non ci sono cicli non ci sono

deadlock.

Ad esempio, si può considerare un sistema con 7 processi (da A a G) e 6 risorse (da R a W). Lo

stato delle risorse attualmente possedute e che sono attualmente richieste è il seguente:

1. A possiede R e vuole S;

2. B non possiede risorse ma vuole T;

3. C non possiede risorse ma vuole S;

4. D possiede U e vuole S e T;

5. E possiede T e vuole V;

6. F possiede W e vuole S;

7. G possiede V e vuole U B

R A

S D

C E

T

F U

W V

G

Come si vede dalla figura, i processi D, E e G sono tutti in deadlock. I processi A, C e F non sono in

deadlock poichè S può essere allocata a qualunque di loro, che poi termina e la resituisce; quindi gli

altri 2 possono averla a turna e anch'essi terminare.

L'individuazione dei processi in deadlock nei sistemi attuali necessita di un algoritmo formale. Un

algoritmo semplice è quello che ispezioa un grafo e finisce sia quando rilevi il deadlock o mostri

che non ne esistono. Utilizza una struttura dati dinamica L, un elenco di nodi e un elenco di archi.

Durante l'algoritmo tutti gli archi sono marcati per indicare che sono già stati ispezionati, per evitare

il ripetersi dei controlli. n C + A = E

ij j j

i=1

L'algoritmo si esegue con i seguenti passi:

1. per ciascun nodo N nel grafo esegui i successivi 5 passaggi, con N nodo iniziale;

2. inizializza L alla lista vuota e designa tutti gli archi come non marcati;

3. aggiungi il nodo attuale alla fine di L e controlla se il nodo appare 2 volte all'interno di L. Se

si allora il grafo ha un ciclo, elencato in L, e l'algoritmo termina;

4. dal nodo dato, verifica se partono archi non marcati. Se sì, vai al passo 5, altrimenti vai al

passo 6;

5. scegli casualmente un arco in uscita non marcato e marcalo. Percorrilo poi fino al nuovo

nodo attuale e vai al passo 3;

6. se questo nodo è quello iniziale, il grafo non contiene alcun ciclo e l'algoritmo termina.

Altrimenti abbiamo raggiunto un vicolo cieco. Rimuovilo e portati al nodo nodo precedente,

cioè quello che era il nodo attuale prima di questo, designalo come attuale e vai al passo 3.

Questo algoritmo prende un nodo alla volta come radice di quello che spera sia un albero e fa una

ricerca in profondità (depth-first) al suo interno. Se raggiunge un nodo che ha già incontrato, allora

ha trovato un ciclo. Se esaurisce tutti gli archi da un determinato nodo, risale al nodo precedente. Se

risale alla radice e non può risalire oltre, allora il sottografo raggiungibile dal nodo attuale non

contiene alcun ciclo e non ci sono deadlock nel sistema.

Tenendo conto del grafo di sopra si può vedere come lavora in pratica quest'algoritmo. L'ordine di

elaborazione dei nodi è arbitrario, quindi possiamo procedere da sinistra verso destra e dall'altro

verso il basso. Se c'è un ciclo l'algoritmo si ferma.

Partiamo da R e inizializziamo L alla lista vuota. Poi aggiungiamo R alla lista e spostiamoci

nell'unica possibilità, A, e la aggiungiamo ad L, avendo così L = [R, A]. Da A andiamo a S,

ottenendo L = [R, A, S]. S non ha archi in uscita, quindi è un vicolo cieco, il che ci costringe a

retrocedere ad A. Dato che A non ha archi non marcati, retrocediamo ad R, completando la nostra

ispezione.

Ricominciamo adesso l'algoritmo partendo da A, reimpostando L alla lista vuota. Anche questa

ricerca si ferma velocemente, così ricominciamo da B. Da B continuiamo a seguire archi che non

escono finchè non raggiungiamo D e in questo momento abbiamo L = [B, T, E, V, G, U, D].

Ora dobbiamo fare una scelta. Se scegliamo S andiamo in un vicolo cieco e dobbiamo retrocedere a

D. La seconda volta prendiamo T e aggiorniamo L a essere [B, T, E, V, G, U, D, T], scoprendo così

il ciclo e quindi fermare l'algoritmo.

3.6.2 Rilevamento dei deadlock con più risorse per ciascun tipo

Quando esistono più copie delle risorse di alcune risorse, serve un approccio diverso per rilevare i

deadlok. In questo caso, si usa un algoritmo basato su una matrice, per rilevare i deadlock fra n

processi, da P a P . Sia m il numero di classi di risorse, con E che indica le risorse di classe 1,....,

1 n 1

in generale E le risorse di classe i (1<= i <=m). 'E' è il vettore delle risorse esistenti (istanze di

i

ciascuna risorsa): per esempio, se la classe 1 è formata da unità a nastro, E =2 significa che ci sono

1

2 unità a nastro.

Nello stesso istante, alcune delle risorse sono assegnate e non sono disponibili.

Sia A il vettore delle risorse disponibili, A fornisce il numero di istanze delle risorse i attualmente

i

disponibili. Se entrambe le unità a nastro sono assegnate, A sarà 0.

i

Adesso servono 2 array: C la matrice di allocazione corrente ed R la matrice delle richieste. La i-

esima riga di C indica quante istanze di ciascuna classe di risorse possiede attualmente P . Così C è

i ij

il numero di istanze della risorsa j posseduto dal processo i. Allo stesso modo, R è il numero di

ij

istanze della risorsa j richiesto da P .

i

Un'importanze invarianza accomuna queste 4 strutture dati. In particolare ogni risorsa è o allocata o

disponibile. Ciò significa che: Σ

Se sommiamo tutte le istanze della risorsa j allocate e a queste aggiungiamo tutte le istanze

disponibili, il risultato è il numero esatto di istanze esistenti di quella classe di risorse.

L'algoritmo di rilevamento dei deadlock si basa sul confronto tra vettori. Definiamo la relazione

A<=B su 2 vettori A e B a significare che ogni elemento di A è minore o uguale del corrispondente

elemento di B. Quindi A<=B è valido <=> A <=B con 1<=i<=m.

i i

Inizialmente, ogni processo è impostato come non marcato. Eseguendo l'algoritmo, i processi

saranno marcati, a indicare che sono in grado di essere completati e così non presentano deadlock.

Quando l'algoritmo finisce, qualunque processo non marcato è in deadlock. Questo algoritmo

considera lo scenario peggiore, cioè tutti i processi trattengono tutte le risorse sino al loro termine.

L'algoritmo di rilevamento dei deadlock può essere così formulato:

1. crea un processo non marcato, Pi, per cui l'i-esima riga di R sia minore o uguale ad A;

2. se si trova questo processo, aggiungi l'i-esima riga di C ad A, marca il processo e ritorna al

passo 1;

3. se un tale processo non esiste, l'algoritmo termina.

Al termine dell'algoritmo tutti i processi non marcati, qualora ve ne siano, sono in deadlock.

Quello che fa l'algoritmo al passo 1 è cercare un processo eseguibile fino al termine. Un processo

del genere è caratterizzato dal fatto di avere delle richieste di risorse che incontrano l'attuale

disponibilità di risorse disponibili. Il processo selezionato è poi eseguito sino alla fine e, a quel

punto, restituisce le risorse che ha trattenuto all'insieme delle risorse disponibili. Poi è

contrassegnato come completato.

Se, alla fine, tutti i processi sono in grado di essere completati, allora nessuno è in deadlock.

Come esempio del funzionamento dell'algoritmo di rilevamento dei deadlock, possiamo considerare

queste 2 matrici:

C=Matrice di allocazione corrente:

0 0 1 0

2 0 0 1

0 1 2 0

R=Matrice delle richieste:

2 0 0 1

1 0 1 0

2 1 0 0

E questi 2 vettori:

E = (4 2 3 1) A = (2 1 0 0)

Abbiamo quindi 3 processi e 4 classi di risorse (unità a nastro, plotter, scanner, CD-ROM).

Il processo 1 ha uno scanner, il processo 2 ha 2 unità a nastro e 1 unità CD-ROM, il processo 3 ha 1

plotter e 2 scanner. Ciascun processo ha bisogno di risorse aggiuntive (matrice R).

Per eseguire l'algoritmo di rilevazione dei deadlock cerchiamo un processo la cui richiesta di risorse

possa essere esaudita. Il primo non può essere soddisfatto, dato che non c'è disponibilità di CD-

ROM. Anche il secondo non può essere soddisfatto, dato che non c'è alcuno scanner libero. Per

fortuna il terzo può essere esaudito, così il processo 3 viene eseguito e, alla fine, restituisce tutte le

sue risorse, ottenendo: A= (2 2 2 0).

A questo punto il processo 2 può essere eseguito e restituire le sue risorse, ottenendo A=(4 2 2 1).

Il processo rimasto può ora essere eseguito. Non c'è alcun deadlock nel sistema.

Si consideri adesso una piccola variante. Si supponga che il processo 2 abbia bisogno di un'unità

CD-ROM, così come di 2 unità a nastro e del plotter. Nessuna delle richieste può essere soddisfatta,

così l'intero sistema è in deadlock.

Come crare i deadlock? Un modo per crearli è fare una verifica ogni volta che c'è la richiesta di una

risorsa, così è certo che li si rileva il più in fretta possibile, ma è potenzialmente dispendioso in

termini di tempo della CPU. Una strategia alternativa è quella di controllare ogni k minuti o magari

solo quando l'utilizzo della CPU sia sceso al di sotto di una certa soglia.

Il motivo per considerare l'utilizzo della CPU è che, se ci sono parecchi processi in deadlock, ci

saranno pochi processi in esecuzione e la CPU sarà spesso inattiva.

3.6.3 Risoluzione di un deadlock

Quando l'algoritmo di rilevamento trova un deadlock, serve un modo per risolvere la situazione e

avere il sistema di nuovo funzionante. Ecco 3 metodi di risoluzione:

uso della preemption;

– uso del rollback;

– ripristino tramite l'eliminazione dei processi.

Uso della preemption

In alcuni casi si può prelevare temporaneamente una risorsa dal suo attuale proprietario e assegnarla

a un altro processo. In molti casi può essere richiesto un intervento manuale, specie nei sistemi

operativi con processi batch, eseguiti sui mainframe.

Per prelevare una stampante laser dal suo proprietario, l'operatore può raccogliere i fogli già

stampati e metterli insieme da pare. A questo punto la stampante può essere assegnata a un altro

processo. Quando un processo termina, la pila di fogli può essere rimessa nel cassetto di output

della stampante e il processo originale riavviato. La possibilità di portare via una risorsa da un

processo, farla usare a un altro e poi restituirla senza che il (primo) processo lo noti è altamente

dipendente dalla natura della risorsa.

Risolvere il deadlock in questo modo è spesso difficile o impossibile. La scelta del processo da

sospendere dipende in larga misura da quali hanno le risorse che possono essere prese con facilità.

Uso del rollback

Se i progettisti dei sistemi operativi e gli operatori delle macchine sanno che i deadlock sono

probabili, possono fare in modo che, periodicamente, vengano generati dei checkpoint dei processi.

Generare un checkpoint per un processo in questo caso significa scrivere il suo stato in un file in

modo che più tardi possa essere riavviato. Il checkpoint cotiene sia l'immagine della memoria che lo

stato delle risorse. Per essere più efficaci possibile, i nuovi checkpoint non dovrebbero

sovrascrivere i precedenti, ma dovrebbero essere scritti in file nuovi, così durante l'esecuzione del

processo si accumula un'intera sequenza.

Quando è rilevato un deadlock, è semplice vedere quali risorse sono necessarie. Per fare il

ripristino, un processo che possiede una risorsa necessaria è riportato (rollback) a un istante

precedente all'acquisizione di quella risorsa, ripristinando uno dei suoi checkpoint precedenti. Tutto

il lavoro fatto a partire dal checkpoint precedente viene perso.

Il processo è reimpostato a un momento precedente, in cui non aveva la risorsa, che ora è assegnata

a uno dei processi in deadlock. Se il processo riavviato prova ad acquisire ancora la risorsa, dovrà

aspettare finchè non diventi disponibile.

Ripristiono tramite l'eliminazione dei processi

Il metodo più brutale, ma più semplice, per interrompere un deadlock è quello di eliminare uno o

più processi. Una possibilità è eliminare un processo nel ciclo. Con un po' di fortuna gli altri

processi potranno proseguire. Se ciò non serve, si può ripetere l'operazione finchè il ciclo non è

interrotto.

In alternativa, affinchè rilasci le sue risorse, si può scegliere come vittima designata un processo

fuori dal ciclo. In questo caso il processo da terminare va scelto attentamente dato che sta

trattenendo delle risorse necessarie a uno dei dei processi nel ciclo.

Ad esempio, un processo potrebbe avere una stampante e necessitare di un plotter, mentre un altro

processo sta tenendo un plotter e ha bisogno di una stampante. Questi 2 sono così in deadlock. Un

terzo processo potrebbe trattenere un'altra identica stampante e un altro identico plotter ed essere in

esecuzione. La soppressione di quest'ultimo rilascerebbe queste risorse e interromperebbe i 2

deadlock che coinvolgono i primi 2 processi.

Quando è possibile, la cosa migliore è sopprimere un processo che, in fondo, può essere rieseguito

senza alcun effetto negativo.

3.7 Starvation

Un problema strettamente legato ai deadlock e ai livelock è la starvation. Si è in presenza di

starvation quando i processi, o più semplicemente un processo, sono in attesa di un evento in

maniera indefinita (stallo senza coinvolgere completamente le risorse).

Per esempio, immaginiamo l'allocazione di una stampante. Immaginiamo che il sistema usi un certo

algoritmo per assicurarsi che l'allocazione della stampante non porti ad alucn deadlock. Adesso

supponiamo che molti processi la vogliano, tutti insieme. Chi la prende?

Un possibile algoritmo di allocazione è di darla al processo con il minor numero di file da stampare

(sempre se si abbia questa informazione). Questo approccio massimizza il numero di utenti

soddisfatti e sembra equo. Ogni volta che la stampante è libera, il sistema si guarda attorno e sceglie

il processo con il file più breve. Se c'è un flusso costante di processi con file piccoli, il processo con

un file grande non avrà mai l'allocazione della stampante: andrà a morire lentamente, rimandato

all'infinito, anche se non in deadlock.

La starvation può essere evitata usando la politica di allocazione delle risorse del first-come first-

served. Con questo approccio il processo che è in attesa da più tempo è servito come successivo.

Nel corso del tempo tutti i processi alla fine prima o poi diventano "il più veccho" è ottengono

quindi la risorsa necessaria.

3.8 Conclusioni

Lo stallo si ha quando un processo che detiene una risorsa necessaria ad un altro processo ne

richiede un'altra acquisita dall'altro processo.

Lo stallo si può evitare tenendo traccia degli stati sicuri e di quelli non sicuri.

Lo stallo si può evitare progettando un sistema in modo che non si verifichi mai lo stallo; per

esempio assegnando una risorsa alla volta ad ogni processo.

Lo stallo si può prevenire assegnando una numerazione alle risorse e facendo sì che i processi le

richiedano in ordine strettamente crescente.

4 – GESTIONE DELLA MEMORIA

Il modulo della Gestione delle Memorie è una macchina virtuale il cui compito è quello di

distribuire opportunamente la memoria centrale, in modo trasparente ed efficiente, al fine di

risolvere le esigenze dei vari processi.

I suoi compiti principali sono:

proteggere dati e istruzioni;

– mascherare la locazione fisica dei dai;

– può sovrappore gli spazi di memoria associati ai programmi.

Garanzie:

garantisce che nessun altro processo possa leggere o modificare i dati contenuti nello spazio

– di indirizzamento;

garantisce l'indirizzamento della memoria centrale più esteso di quello ammissibile e in

– modo indipendente dalla specifica locazione;

garantisce la non ridondanza dei dati o dei programmi.

Perchè un gestore della memoria centrale ? :

presenza della multi-utenza e della multi-programmazione;

– presenza di processi di dimensioni più grandi della memoria centrale libera;

– presenza di dati con dimensioni più grandi della memoria centrale libera;

– ridurre la quantità di dati e dei processi presenti in memoria centrale.

Compiti del gestore della memoria centrale:

risolve le problematiche relative alla multiprogrammazione e alla multiutenza;4

– risolve i problemi di incompatibilità tra dimensione del programma e memoria disponibilie;

– risolve le problematiche relative allo spostamento dell'applicativo in memoria;

Strategie:

consentire il caricamento dei programmi a partire da un indirizzo qualunque;

– ridurre lo spazio di memoria conservando solo quelle porzioni di processo necessarie;

– condividere insiemi di istruzioni tra più processi.

Idealmente si vorrebbe avere per ogni elaboratore una memoria infitamente grande e infinitamente

veloce, ma ciò non è possibile e la maggior parte degli elaboratori hanno una gerarchia di memoria:

una piccola quantità di cache costosa ma veloce (volatile);

– una memoria centrale meno costosa ma meno veloce (volatile);

– una unità a disco molto economica ma lenta (non volatile);

– soluzioni miste...

La parte del SO che gestisce la memoria si chiama gestore della memoria. I suoi compiti sono:

tenere conto delle parti di memoria usate e di quelle non utilizzate;

– allocare memoria ai processi quando ne fanno richiesta;

– liberarla quando hanno finito;

– gestire gli scambi tra memoria e disco

I sistemi di gestione della memoria possono essere divisin in 2 classi:

quelli che spostano i processi dalla memoria ai dischi e viceversa;

– quelli che non lo fanno.

4.1 Nessuna astrazione della memoria

La più semplice astrazione della memoria è l'assenza di astrazione. I primi mainframe, i primi

microcomputer e i primi personal computer non avevano astrazione della memoria. Ogni

programma vedeva semplicemente la memoria fisica. Quando un programma eseguiva un'istruzione

come , il computer spostava semplicemente il contenuto della locazione di

MOV REGISTER1,1000

memoria fisica 1000 a REGISTER1. Così facendo, il modello di memoria presentato ai

programmatori era semplicemente memoria fisica, un insieme di indirizzi da 0 a un certo massimo,

ogni indirizzo corrispondente a una cella contenente un certo numero di bit, solitamente 8.

In queste condizioni non era possibile avere 2 programmi eseguiti in memoria nello stesso istante.

Se il primo programma avesse scritto un nuovo valore, avrebbe cancellato qualunque valore vi

avesse registrato il secondo programma. Non avrebbe funzionato nulla ed entrambi sarebbero falliti

quasi immediatamente.

4.1.1 Monoprogrammazione senza swapping o paginazione

Lo swapping e la paginazione sono strategie dettate dall'insufficienza della memoria centrale a

contenere tutti i programmi.

Lo schema di gestione della memoria più semplice possibile è quello di eseguire soltanto un

programma alla volta condividendo la memoria tra programma e SO.

In uno schema di questo tipo, in un generico istante di tempo, solo un processo può essere caricato

in memoria. Quando un utente richiede l'esecuzione di un programma, attraverso il prompt dei

comandi, questo viene caricato in memoria, al termine del quale la memoria sarà rilasciata restando

in attesa del caricamento di un nuovo programma.

0xFFF... Driver

dispositivi in ROM

S.O.

nella ROM

Programma

utente Programma

utente

Programma

utente

S.O.

nella ROM S.O.

nella RAM

0 0 0

a b c

4.1.2 Multiprogrammazione con partizioni fisse

Quasi tutti i sistemi di elaborazione consentono ai diversi processi di girare contemporaneamente

sulla CPU, nel senso che, quando un processo è bloccato (in attesa di risorsa) la CPU viene

assegnata ad un altro processo.

Il modo più semplice per realizzare la multiprogrammazione è di dividere la memoria in n partizioni

di dimensioni diverse.

Come definire e quando effettuare la partizione: la partizione può essere effettuata quando il

sistema sta per attivarsi ed è l'operatore di sistema che può definire le partizioni.

Come agisce il processo sulla partizione: il gestore della memoria assegna al processo la più

piccola partizione di memoria utile per farlo lavorare, poichè la partizione non è dinamica, al

processo sarà assegnata una parte di memoria non utilizzata.

Svantaggio delle code multiple: la partizione della memoria in aree diverse, ciascuna con una

dimensione diversa dall'altra, implica che, in certi momenti, alcune partizioni non sono utilizzate in

quanto prive di processi in coda mentre altre saranno estremamente affollate.

Prima alternativa: una singola coda per i processi in attesa della memoria, ogni volta che si libera

una partizione, il job più vicino alla testa della coda che può entrare nella partizione è caricato.

Poichè non è desiderabile sprecare partizioni grandi per processi piccoli (cosa frequente in questa

alternativa), allora un'altra opzione è data da una seconda alternativa.

Seconda alternativa: scegliere tra la coda dei processi in attesa della memoria il processo più

grande che può entrare. Lo svantaggio di tale strategia è quello di non agevolare i processi piccoli,

che di solito sono quelli interattivi e che quindi dovrebbero essere più agevolati.

Terza alternativa: due code, una per i processi piccoli e l'altra per i processi più grandi.

Quarta alternativa: assegnare a un job un valore numerico che stabilisce il numero di volte che il

processo è stato messo da parte. Superata una soglia, il processo viene eseguito.

Un gestore della memoria per la multi-programmazione basato su partizioni fisse, qualsiasi sia

l'alternativa utilizzata, è impensabile negli attuali sistemi di elaborazione.

4.1.3 Rilocazione e protezione

L'attività di programmazione introduce 2 problemi essenziali che devono essere risolti: rilocazione

e protezione.

Ad esempio, quando viene effettuato un link, il linker deve conoscere l'indirizzo dove sarà caricato

il programma.

Soluzione 1: cambiare l'indirizzo ad ogni istruzione. Ai programmi caricati nella partizione 1 si

somma il valore 100, a quelli in posizione 2 il valore 200, ....

La rilocazione non risolve i problemi della protezione!

La protezione fu risolta, sul 360 dell'IBM, assegnando ad ogni partizione di 2KB un codice di 4 bit

PSW che il gestore della memoria controlla ogni volta che un processo effettua un accesso ad una

specifica locazione di memoria.

Soluzione 2: sono stati definiti 2 registri hardware (base, limite) che rappresentano il campo di

azione del programma e contengono rispettivamente l'indirizzo dove il programma è stato caricato e

il suo limite di azione (indirizoo finale). Tale soluzione risolve contemporaneamente i problemi di

rilocazione e di protezione.

L'hardware protegge i registri base e limite per evitare che qualcuno li possa modificare.

4.2 Un'astrazione della memoria: gli spazi degli indirizzi

Esporre la memoria fisica ai processi presenta tanti inconvenienti:

se i programmi utente possono indirizzare ogni byte della memoria, allora possono

– facilmente spazzar via il SO, intenzionalmente o accidentalmente, conducendo il sistema a

un brusco stop;

con questo modello è difficile che siano eseguiti contemporaneamente molteplici

– programmi.

Sui personal computer è normale avere parecchi programmi aperti contemporaneamente. Poichè è

difficile ottenere una simile situazione della memoria fisica, occorre fare qualcosa.

4.2.1 Nozione di spazio degli indirizzi

Per permettere a molteplici applicazioni di risiedere in memoria contemporaneamente senza

interferire l'un l'altra, devono essere risolti 2 problemi: la protezione e il riposizionamento.

Una soluzione primitiva, usata sull'IBM 360, è quella di etichettare grossi pezzi di memoria con una

chiave di protezione e confrontare la chiave del processo in esecuzione con quella di ogni parola di

memoria prelevata. Tuttavia, quest'approccio non risolve il problema del riposizionamento, sebbene

si possano riposizionare i programmi quando vengono caricati, ma si tratta di una soluzione lenta e

complicata.

Una soluzione migliore è inventare una nuova astrazione per la memoria: lo spazio degli indirizzi.

Uno spazio degli indirizzi è l'insieme degli indirizzi che un processo può usare per indirizzare la

memoria. Ogni processo ha il suo spazio degli indirizzi personale, indipendente da quello

appartenente ad altri processi.

Il concetto di uno spazio degli indirizzi è molto generale ed è appropriato in molti contesti. Per

esempio, per un numero di 7 cifre, lo spazio degli indirizzi va da 0000000 a 9999999, gli indirizzi

32

IPv4 sono numeri a 32 bit, così il loro spazio degli indirizzi va da 0 a 2 -1.

Gli spazi degli indirizzi non devono essere numerici. Anche l'insieme dei domini Internet .com è

uno spazio degli indirizzi. Questo spazio consiste di tutte le stringhe da 2 a 63 caratteri che possono

essere creati usando lettere, numeri e trattini, seguiti da .com.

Una cosa difficile invece è dare a ogni programma il suo spazio degli indirizzi: l'indirizzo 28 in un

programma significa una locazione fisica diversa dall'indirizzo 28 in un altro programma.

Registri base e registri limite

Questa soluzione si basa su una versione particolarmente semplice della rilocazione dinamica.

Quello che fa è mappare lo spazio degli indirizzi di ogni processo su di una parte diversa di

memoria fisica in modo semplice.

La soluzione classica è quella di equipaggiare ogni CPU con 2 registri hardware speciali,

solitamente chiamati registro base e registro limite. Quando sono usati questi registri, i programmi

sono caricati in posizioni di memoria consecutive dovunque vi sia spazio e senza riposizionamento

durante il caricamento. Al momento dell'esecuzione di un processo, il registro base è caricato con

l'indirizzo fisico dove comincia il suo programma in memoria e il registro limite è caricato con la

lunghezza del programma.

Ogni volta che un processo consulta la memoria, sia per prelevare un'istruzione sia per leggere o

scrivere una parola dati, prima di inviare l'indirizzo sul bus di memoria, l'hardware della CPU

aggiunge automaticamente il valore di base all'indirizzo generato tramite il processo.

Contemporaneamente controlla se l'indirizzo offerto sia uguale o maggiore del valore nel registro

limite, nel cui caso è generato un errore e l'accesso viene interrotto.

Così, nel caso qui sotto, il processo esegue l'instruzione , ma l'hardware la tratta come se

JMP 28

fosse , così si dirige sull'istruzione come previsto:

JMP 16412 CMP 0 32764

.

.

CMP 16412

16408

16404

16400

16396

16392

16388

JMP 28 16384

0 16380 0 16380 0 16380

. . .

. . .

ADD 28 CMP 28 ADD 28

MOV 24 24 MOV 24

20 20 20

16 16 16

12 12 12

8 8 8

4 4 4

JMP 24 0 JMP 28 0 JMP 24 0

a b c

Poichè ad ogni indirizzo di memoria, generato automaticamente, viene aggiunto il contenuto del

registro base prima di essere spedito alla memoria, l'impiego di registri limite e base è un modo

semplice per attribuire a ciascun processo il suo spazio degli indirizzi.

In molte implementazioni i registri limite e base sono protetti in modo che solo il SO possa

modificarli.

Uno svantaggio della rilocazione per mezzo dei registri limite e base è la necessità di eseguire una

somma e un confronto per ogni riferimento alla memoria. I confronti possono avvenire

velocemente, ma le somme sono lente a causa del tempo di propagazione, a meno che non siano

usati circuiti speciali per la somma.

4.2.2 Swapping

Problema: immaginiamo che la dimensione del codice da eseguire sia maggiore della dimensione

della memoria centrale libera e, più in generale, immaginiamo di avere un numero di processi tale

che la somma delle dimensioni del loro codice sia maggiore della memoria centrale disponibile.

In questi casi il SO non è in grado di caricare il processo, sia nel primo sia nel secondo caso dovrà

attendere la fine di qualche processo per liberare la memoria.

Soluzione: la soluzione tipica per evitare questi problemi è abilitare il SO a trasferire il contenuto di

un'area di memoria centrale in un'area della memoria di massa (tipicamente della area di swap) al

fine di rendere disponibile la memoria resa libera.

Questa tenica, denominata tecnica di swapping, generalmente è applicata ai processi che sono in

attesa.

Nei sistemi timesharing o nei personal computer, in generale, la memoria centrale non è sufficiente

a mantenere tutti i processi che richiedono di andare in esecuzione.

La soluzione a tale problema è quella di spostare i processi attivi e in attesa sul disco e di reinserirli

quando necessitano della CPU.

Lo swapping carica in memoria l'intero processo da mandare in esecuzione per un tempo minore o

uguale al suo quanto di tempo, quindi lo sposterà in una speciale memoria sul disco chiamata swap

disco.

La memoria virtuale consente di caricare in memoria centrale solo porzioni del processo.

C C C C C

B B B B A

A A A D D D

S.O. S.O. S.O. S.O. S.O. S.O. S.O.

a b c d e f g

Nota: in questo contesto il S.O. sta nella parte bassa della memoria

In questo esempio:

a. il processo A viene caricato in memoria;

b,c. i processi B e C sono anch'essi caricati in memoria (dinamicità della memoria);

d. il processo A viene scaricato dalla memoria per fare posto ad altri processi;

e. viene caricato il processo D;

f. il processo B viene scaricato liberando una porzione di memoria in cui può essere

caricato il processo A;

g. viene caricato il processo A in una posizione diversa da quella originale.

La flessibilità è data dal non essere legati alla specifica dimensione della partizione della memoria

ma alle dimensioni del processo:

la flessibilità crea qualche problema di rilocazione e di rilascio della memoria;

– si deve tener conto di quale parte della memoria è stata resa libera.

Possono sorgere 2 problemi nel caricamento dei processi in memoria:

la gestione della comparsa di buchi di memoria non usati da nessun processo;

– la gestione di quei processi che hanno dimensione variabile nel tempo (le variabili crescono

– dinamicamente).

Caricare e scaricare processi in e dalla memoria può provocare buchi di memoria non riutilizzabili.

Per evitare tali disfunzioni il gestore della memoria ha un modulo preposto a compattare i buchi

presenti in memoria: quindi si parla di compattazione della memoria.

Nota: questa tecnica raramente viene usata in quanto necessità molto tempo di CPU.

Quando si tenta di caricare in memoria un processo che cresce dinamicamente, ad esempio quando

fa uso di variabili dinamiche, si possono verificare alcuni problemi:

1. se il processo si trova in prossimità di un buco (area di memoria libera) questo può crescere

facilmente espandendosi occupando il buco;

2. se il processo è invece adiacente ad un altro processo, o si sposta il processo in crescita

verso un area di memoria che può contenerlo o si spostano i suoi processi adiacenti in modo

da creare un buco;

3. se il processo non può crescere in memoria, o se l'area di swap è piena, allora il processo

deve attendere la risorsa memoria o sarà killato (se in deadlock).

Se ci si aspetta che il processo cresca, è buona norma allocare più memoria di quanto il processo

necessita alla sua partenza per ridurre il carico relativo allo swapping o allo spostamento dei

processi che non stanno più all'interno della memoria allocata.

Quando si fa lo swapping di processi sul disco, solo la memoria effettivamente in uso dovrebbe

essere interessata: è uno spreco fare lo swapping anche della memoria extra.

Nel caso i processi presentino 2 segmenti che crescono (e.g. heap e stack), si propone una soluzione

alternativa. Stack B

Spazio per Spazio per

crescere crescere

Dati B

Spazio effetttivamente Spazio effetttivamente

B in uso in uso

Programma B

Stack A

Spazio per Spazio per

crescere crescere

Dati A

Spazio effetttivamente Spazio effetttivamente

A in uso in uso

Programma A

S.O. S.O.

a b

In quest'esempio, ogni processo illustrato ha uno stack in cima alla sua memoria allocata e sta

crescendo verso il basso e il segmento dati appena oltre il testo del programma sta crescendo verso

l'alto. La memoria in mezzo a loro può essere usata per ciascun segmento. Se si esaurisce, il

processo dovrà essere spostato in uno spazio vuoto con spazio sufficiente, dovrà esserne fatto lo

swapping dalla memoria finchè possa essere creato uno spazio abbastanza largo, oppure dovrà

essere terminato.

4.2.3 Gestione della memoria libera

Quando la memoria è assegnata dinamicamente, il SO deve gestirla. Ci sono due modalità di tener

traccia dell'utilizzo della memoria: bitmap e liste.

Gestione della memoria con bitmap

La memoria, con una bitmap, è divisa in unità di allocazione più piccole come qualche parola o

grandi come molti KB. A ogni unità di allocazione corrisponde un bit della bitmap, che è 0 se l'unità

è libera e 1 se è allocata (o viceversa).

Più piccola è l'unità di allocazione, maggiore è la bitmap. Tuttavia, anche con un'unità di

allocazione piccola fino a 4 byte, 32 bit di memoria richiederanno un solo bit della mappa.

n

Una memoria di 32 bit userà n bit di mappa, così la bitmap occuperà solo 1/33 della memoria. Se si

è scelta un'unità di allocazione grande, la bitmap sarà più piccola, ma una quantità non banale di

memoria potrà essere sprecata nell'ultima unità del processo, se la dimensione del processo non è

esattamente un multiplo dell'unità di allocazione.

Poichè la dimensione della bitmap dipende solo dalla dimensione della memoria e dalla dimensione

dell'unità di allocazione, una bitmap fornisce un modo semplice per tener traccia di parole di

memoria in una quantità fissa di memoria.

Il problema principale è che, se si stabilisce di portare un processo di k unità in memoria, il gestore

della memoria deve cercare nella bitmap per trovare una serie di un numero k di bit 0 consecutivi

nella mappa.

Cercare in una bitmap una serie di lunghezza predefinita è un'operazione lenta, poichè la serie

potrebbe essere a cavallo dei limiti della parola della mappa: questa motivazione è a sfavore delle

bitmap.

A A A A A B B B B B B C C C C D D D D D D E E E --------

0 8 16 24

^ ^ ^ ^ ^ ^ ^ ^

1 1 1 1 1 0 0 0

1 1 1 1 1 1 1 1

1 1 0 0 1 1 1 1

1 1 1 1 1 0 0 0

-------- --------

P 0 5 H 5 3 P 8 6 P 14 4 H 18 2 P 20 6 P 26 3 H 29 3 X

Una parte di memoria con 5 processi e 3 spazi vuoti. Le zone in grigio (0 nella bitmap) sono libere

La bitmap corrispondente

Stesse informazioni in lista L1

Gestione della memoria con liste collegate

F1 Prima che X finisca Dopo che X è finito

a) A X B Diventa -> A B

b) A X Diventa -> A

c) X B Diventa -> B

d) X Diventa ->

Un altro sistema per tener traccia della memoria è mantenere delle liste di segmenti di memoria

allocati e liberi, in cui un segmento o contiene un processo o è uno spazio vuoto tra 2 processi.

Nella lista descritta sopra (L1), la lista dei segmenti è in ordine di indirizzo: fare questo

ordinamento ha il vantaggio che, quando un processo finisce o ne viene fatto lo swapping,

l'aggiornamento della lista è molto semplice. Un processo che finisce ha normalmente 2 vicini

(tranne per i processi in cima e in fondo alla memoria). Questi possono essere sia processi, sia spazi

vuoti, e tutto ciò porta ad avere le 4 combinazioni descirtti in figura sopra (F1).

Poichè il posto della tabella dei processi per il processo in chiusura punta normalmente alla voce

della lista del processo stesso, può essere più comodo che la lista sia doppiamente collegata,

piuttosto che con un singolo collegamento come nella lista L1. Questa struttura rende più semplice

trovare la voce precedente e vedere se è possibile l'unione.

Quando processi e spazi vuoti sono tenuti su una lista ordinata per indirizzo, molti algoritmi

possono essere usati per allocare la memoria per un processo creato o già esistente e di cui viene

fatto lo swapping da disco.

Consideriamo che il gestore della memoria sappia quanta memoria allocare:

FIRST FIT

L'algoritmo più semplice è first fit (il primo va bene). Il gestore della memoria scorre la lista dei

segmenti finchè non trova uno spazio vuoto abbastanza grande. Lo spazio è suddiviso in 2 parti, una

per il processo, l'altra per la memoria inutilizzata, fatta eccezione per il caso, molto improbabile,

che lo spazio coincida perfettamente. Poichè cerca il meno possibile, first fit è un algoritmo veloce.

NEXT FIT

Una variante di first fit è next fit (il prossimo va bene). Lavora allo stesso modo di first fit, ma tiene

traccia di ogni posto dove ha trovato uno spazio adatto. La volta seguente che è interpellato alla

ricerca di uno spazio, cerca nella lista a partire dal punto dove era rimasto l'ultima volta, invece di

partire dal principio, come fa invece sempre first fit.

BEST FIT

Un altro algoritmo molto noto e molto usato è best fit. Quest'algoritmo cerca all'interno della lista,

dall'inizio alla fine, prendendosi lo spazio più piccolo che sia comunque adatto. Piuttosto che

impossessarsi di uno spazio grande, che potrebbe essere necessario in seguito, best fit prova a

cercare lo spazio che più si avvicini allo spazio reale necessario, per ottimizzare al meglio la

richiesta di spazi disponibili.

Esempio: nella figura F1, se è necessario un blocco di dimensione 2, first fit alloca lo spazio in

posizione 5 (ossia la prima disponibile), mentre best fit lo allocherebbe in posizione 18 (esattamente

2 blocchi liberi).

Best fit è più lento di first fit, poichè deve cercare ogni volta nell'intera lista. Inoltre, genera anche

un maggior spreco di memoria rispetto a first fit e next fit, perchè tende a riempire la memoria di

piccoli ed inutili spazi. First fit genera, mediamente, degli spazi vuoti più grandi.

WORST FIT

Per aggirare il problema di combinare quasi esattamente un processo e uno spazio idoneo, si

potrebbe pensare anche a worst fit, che si prende lo spazio disponibile più grande, in modo che il

nuovo spazio sia grande abbastanza da essere utile.

Da quanto visto, neanche worst fit è una buona idea.

Tutti e 4 gli algoritmi possono essere velocizzati mantenendo liste separate per i processi e gli spazi.

In questo modo tutti loro possono dedicare totalmente la propria energia nel ricercare gli spazi, non

i processi. Il prezzo da pagare questa velocizzazione dell'allocazione è l'aggiunta di complessità e il

rallentamento nel rilasciare la memoria, poichè un segmento liberato deve essere tolto dall'elenco

dei processi e inserito nell'elenco degli spazi.

Se sono mantenute liste distinte per processi e spazi, la lista degli spazi può essere ordinata per

dimensione, in modo da far sì che best fit sia più veloce.

Quando best fit cerca nella lista degli spazi dal più piccolo al più grande, appena trova uno spazio

adatto, già sa che quello è il più piccolo possibile per svolgere il lavoro, quindi il migliore. Non è

necessaria alcun'altra ricerca, così come accade con lo schema a singola lista. Con la lista degli

spazi ordinata per dimensione, first fit e best fit sono veloci allo stesso modo e next fit è superfluo.

Quando gli spazi sono mantenuti su liste separate dai processi è possibile fare una piccola

ottimizzazione. Invece di avere un insieme di strutture dati separato per mantenere la lista degli

spazi, le informazioni possono essere archiviate negli spazi. La prima parola di ogni spazio potrebbe

essere la dimensione dello stesso, la seconda un puntatore alla voce successiva.

QUICK FIT

Un altro algoritmo di allocazione è quick fit, che mantiene liste divise per alucne delle più comuni

dimensioni richieste. Ad esempio, potrebbe esserci una cartella con n voci, di cui la prima è un

puntatore alla testa di una lista di spazi di 4 KB, la seconda è un puntatore alla lista degli spazi da 8

KB, la terza a quella da 12 KB, etc...

Ipotizziamo che gli spazi da 21 KB possano essere insieme a quelli da 20 KB nella lista speciale

degli spazi extra-large. Con quick fit la ricerca di uno spazio della dimensione richiesta è molto

veloce, ma presenta lo stesso svantaggio di tutti gli schemi ordinati per dimensione, infatti, quando

un processo finisce o ne viene fatto lo swapping su disco, trovare i suoi vicini per vedere se sia

possibile unirlo a loro è dispendioso. Se non viene eseguita l'unione, la memoria si frammente

velocemente in molti spazi piccoli non adatti ad alcun processo.

4.3 Memoria virtuale

L'idea alla base della memoria virtuale è che ogni programma ha il proprio spazio degli indirizzi

personale, suddiviso in pezzi chiamati pagine. Ogni pagina è un intervallo di indirizzi contigui.

Queste pagine sono mappate nella memoria fisica, ma non tutte le pagine devono stare nella

memoria fisica per eseguire il programma.

Quando il programma fa riferimento a una parte del proprio spazio degli indirizzi che è nella

memoria fisica, l'hardware esegue il necessario mappaggio diretto.

Quando il programma fa riferimento a una parte del proprio spazio degli indirizzi che non è nella

memoria fisica, il SO è avvisato di andare a prendere il pezzo mancante e rieseguire l'istruzione

fallita.

In un certo senso, la memoria virtuale è la generalizzazione dell'idea dei registri base e limite.

L'8088 aveva registri base separati per il testo e per i dati.

Con la memoria virtuale, invece di avere una rilocazione separata solo per i segmenti dati e testo,

l'intero spazio degli indirizzi può essere rimappato sulla memoria fisica in unità equamente piccole.

La memoria virtuale funziona bene in un sistema di multiprogrammazione, con bit e pezzi di

progammi nello stesso tempo in memoria. Mentre un programma è in attesa che un suo pezzo sia

letto, la CPU può essere assegnata a un altro processo.

4.3.1 Paginazione

La maggior parte dei sistemi di memoria virtuale usa una tecnica detta paginazione o paging. Su

qualsiasi computer i programmi referenziano un insieme di indirizzi di memoria. Quando un

programma esegue un'istruzione come la esegue per copiare il contenuto

MOV REG, 1000

dell'indirizzo di memoria in . Gli indirizzi possono essere generati usando l'indicizzazione,

1000 REG

i registri base, i registri segmento, o in altri modi....

Questi indirizzi generati dal programma sono chiamati indirizzi virtuali e formano lo spazio

virtuale degli indirizzi. Sui computer senza memoria virtuale, l'indirizzo virtuale è messo

direttamente sul bus di memoria e provoca la lettura o la scrittura della parola della memoria fisica

con lo stesso indirizzo. Quando è usata la memoria virtuale, gli indirizzi virtuali non vanno

direttamente al bus di memoria, ma a una MMU (Memory Management Unit) che mappa gli

indirizzi virtuali sugli indirizzi di memoria fisica

Package della

CPU

CPU La CPU invia

indirizzi virtuali Controller

Memoria

alla MMU del disco

La MMU invia

indirizzi fisici

alla memoria Bus

MMU

Un esempio semplice di mappaggio è il seguente: abbiamo un computer che genera indirizzi di 16

bit, da 0 a 64 K. Questi sono indirizzi virtuali. Questo computer, però, ha solo 32 KB di memoria

fisica. Così, sebbene possano essere scritti programmi da 64 KB, questi non possono essere caricati

nella loro interezza nella memoria ed essere eseguiti. Una copia completa dell'immagine del nucleo

del programma, fino a 64 KB, deve comunque essere presente sul disco, in modo che possano

essere caricati dei pezzi secondo necessità.

Lo spazio degli indirizzi virtuali è suddiviso in unità di dimensione fissa, chiamate pagine. Le unità

corrispondenti della memoria fisica sono chiamate frame o page frame. Le pagine e i frame sono

generalmente della stessa dimensione. Nei sistemi reali le pagine vanno da 512 byte a 64 KB. Con

64 KB di spazio degli indirizzi virtuali e 32 KB di memoria fisica otteniamo 16 pagine virtuali e 8

frame. I trasferimenti fra la RAM e il disco sono sempre di pagine intere.

Spazio degli

indirizzi virtuali

60K – 64K X

56K – 60K X }Pagina virtuale

52K – 56K X

48K – 52K X

44K – 48K 7

40K – 44K X Indirizzo di

36K – 40K 5 memoria fisica

32K – 36K X

28K – 28K –

32K X 32K

24K – 24K –

28K X 28K

20K – 20K –

24K 3 24K

16K – 16K –

20K 4 20K

12K – 12K –

16K 0 16K

8K – 8K –

12K 6 12K

4K – 4K –

8K 1 8K

0K – 0K –

4K 2 4K

}Frame

Nell'immagine, l'intervallo segnato 0K – 4K signfica che gli indirizzi fisici o virtuali in quella

pagina vanno da 0 a 4095, 4K – 8K significa da 4096 a 8191, 8K – 16K significa da 8192 a 12287,

e così via...

Ogni pagina contiene esattamente 4096 indirizzi a un multiplo di 4096 a un multiplo di 4096

successivo.

Quando il programma prova, ad esempio, ad accedere all'indirizzo 0, usando l'istruzione

MOV REG, 0

l'indirizzo virtuale 0 è inviato alla MMU che vede questo indirizzo virtuale cadere nella pagina 0

(da 0 a 4095) che, secondo il suo mappaggio, è il frame 2 (da 8192 a 12287). Così trasforma

l'indirizzo a 8192 e invia esternamente sul bus l'indirizzo 8192. La memoria non sa nulla riguardo

l'MMU e dà semplicemente seguito a una richiesta per leggere o scrivere l'indirizzo 8192. Così la

MMU ha effettivamente mappato tutti gli indirizzi virtuali fra 0 e 4095 sugli indirizzi fisici da 8192

a 12287.

Allo stesso modo, l'istruzione è trasformata effettivamente in

MOV REG, 8192 MOV REG, 24576

poichè l'indirizzo virtuale 8192 (pag virtuale 2) è mappato sul 24576 (nel frame fisico 6).

Un altro esempio: l'indirizzo virtuale 20500 dista 20 byte da dall'inizio della pagina virtuale 5

(indirizzi virtuali da 20480 a 24575) e mappa sull'indirizzo fisico 12288+20=12308.

Questa capacità di mappare le 16 pagine virtuali su qualsiasi degli 8 frame, impostando in modo

appropriato la mappa della MMU, non risolve per proprio conto il problema che lo spazio degli

indirizzi virtuali è maggiore della memoria fisica. Poichè abbiamo solo 8 frame fisici, solo 8 delle

pagine virtuali sono mappate sulla memoria fisica. Le altre (X in figura) non sono mappate.

Nell'hardware effettivo, un bit presente/assente tiene traccia di quali pagine sono presenti

fisicamente in memoria.

Sempre considerando la figura, con l'istruzione che è di 12 byte all'interno della

MOV REG, 32780

pagina virtuale 8, la MMU rileva che la pagina non è mappata (X) e causa un trap della CPU verso

il SO. Questo trap è chiamato errore di pagina (page fault). Il SO preleva un frame poco utilizzato

e ne scrive il suo contenuto su disco. Prende poi la pagina appena referenziata e la mette nel frame

appena liberato, cambia la mappa e riavvia l'istruzione che era in trap.

Esempio: se il SO dedice di sfrattare il frame 1, dovrebbe caricare la pagina virtuale 8 all'indirizzo

8192 e fare 2 cambiamenti alla mappa della MMU. Per prima cosa dovrebbe contrassegnare la

prima voce della pagina virtuale come non mappata, per fare il trap di qualsiasi accesso futuro agli

indirizzi virtuali da 4096 a 8191. Dovrebbe poi sostituire la X nella voce della pagina virtuale 8 con

un 1 in modo che, qundo l'istruzione che ha generato il trap viene eseguita, essa mappi l'indirizzo

virtuale 32780 con l'indirizzo 4108 (4096+12).

Consideriamo di avere il seguente indirizzo virtuale: 0010000000000100 (8196 in decimale). Le

prime 4 cifre, cioè 0010 (2 in decimale) indicano appunto la pagina virtuale 2, mentre le altre 12

cifre indicano l'offset di 12 bit (000000000100). La pagina 2 è mappata con 110, quindi l'indirizzo

di uscita sarà 110000000000100 (24580 = 24576+4).

Con 4 bit per il numero di pagina, possiamo avere 16 pagine e con 12 bit di offset possiamo

indirizzare 4096 byte per pagina.

Il numero di pagina è usato come indice nella tabella delle pagine che porta al numero di frame

corrispondente alla pagina virtuale. Se il bit presente/assente è 0 allora avviene un trap al SO. Se il

bit è 1, il numero di frame trovati nella tabella delle pagine viene copiato nei 3 bit più significativi

del registro di output, insieme all'offset di 12 bit che è copiato senza modifiche dall'indirizzo

virtuale in arrivo. Insieme formano un indirizzo fisico di 15 bit. Il registro di output è poi messo sul

bus di memoria come indirizzo fisico di memoria.

4.3.2 Tabelle delle pagine

In una semplice implementazione si può sintetizzare il mappaggio degli indirizzi virtuali sugli

indirizzi fisici come segue: l'indirizzo virtuale è diviso in un numero di pagina virtuale (i bit più

significativi) e un offset (i bit meno significativi). Con un indirizzo di 16 bit e una dimensione di

pagina di 4 KB, i 4 bit superiori potrebbero specificare una delle 16 pagine virtuali e i 12 bit più

bassi specificherebbero il byte di offset (da 0 4095). Tuttavia è possibile suddividere con 3 o 5 o un

altro numero di bit per pagina. Diverse suddivisioni implicano diverse dimensioni della pagina.

Il numero di pagina virtuale è utilizzato come un indice nella tabella delle pagine per trovare la voce

per quella pagina virtuale. Il numero di frame è rintracciato dalla voce nella tabella delle pagine ed è

allegato alla parte più significativa dell'offset, rimpiazzando il numero di pagina virtuale, per

formare un indirizzo fisico che può essere inviato alla memoria.

In questo modo lo scopo della tabella delle pagine è di mappare le pagine virtuali sui frame delle

pagine. La tabella delle pagine è una funzione che ha come argomento il numero di una pagina

virtuale e come risultato il numero di frame. Usando il risultato di questa funzione, il campo relativo

alla pagina virtuale può essere rimpiazzato dal campo del frame, andando a formare un indirizzo di

memoria fisico.

Struttura di una voce della tabella delle pagine

Caching

disabilitata Modificato Presente/Assente Numero di frame

Referenziato Protezione

L'esatto layout di una voce dipende molto dalla macchina, ma il tipo di informazione presente è più

o meno lo stesso per tutte le macchine. La dimensione cambia da computer a computer, ma quella

usuale è di 32 bit. Il campo più importante è il numero dei frame. L'obiettivo del mappare le pagine

è di avere questo valore. Il bit successivo è il bit presente/assente che, se messo a 1, la voce è valida

e può essere utilizzata. Se è 0, la pagina virtuale cui appartiene la voce non è effettivamente in

memoria. L'accesso alla voce della tabella delle pagine con questo bit impostato a 0 causa un errore

di pagina.

I bit di protezione specificano quali tipi di accesso sono consentiti. Nella forma basilare questo

campo contiene 1 bit, con 0 che significa lettura/scrittura e 1 per la sola lettura.

Un'impostazione più complessa ha 3 bit, ogni bit per consentire lettura, scrittura ed esecuzione della

pagina.

I bit modificato e referenziato tengono traccia dell'uso della pagina. Quando viene scritta una

pagina, l'hardware imposta automaticamente il bit modificato. Questo bit è valorizzato quando il SO

decide di riutilizzare un frame. Se la sua pagina è stata modificata deve esser riscritto sul disco. Se

non è stata modificata può essere abbandonato, poichè la copia sul disco è ancora valida. Alcune

volte il bit è detto dirty bit poichè riflette lo stato "sporco" della pagina.

Il bit referenziato è impostato ogni volta che si faccia riferimento alla pagina, sia in lettura sia in

scrittura. Serve per aiutare il SO a scaricare una pagina quando si verifica un errore di pagina. Le

pagine inutilizzate sono le candidate migliori rispetto a quelle usate e questo bit ha un ruolo molto

importante negli algoritmi di sostituzione delle pagine.

Infine, l'ultimo bit consente di disabilitare la cache per pagina. Questa caratteristica è importante per

le pagine che mappano sui registri dei dispositivi piuttosto che in memoria. Se il SO è posizionato

in un ciclo stretto in attesa che qualche dispositivo di I/O risponda a un comando appena inviato, è

fondamentale che l'hardware tenga prelevata la parola da quel dispositivo e non usi quella vecchia

messa in cache. Con questo bit, l'utilizzo della cache può essere disabilitato. Le macchine che hanno

uno spazio di I/O separato e non gestiscono l'I/O mappato sulla memoria non hanno bisogno di

questo bit. L'indirizzo del disco utilizzato per mantenere la pagina quando questa non è in memoria,

non è all'interno della tabella delle pagine perchè la tabella delle pagine tiene solo le informazioni di

cui l'hardware necessita per tradurre un indirizzo virtuale in un indirizzo fisico. Le informazioni di

cui il SO ha bisogno per gestire gli errori di pagina sono conservate nelle tabelle software all'interno

del SO. L'hardware non ne ha bisgono.

Ciò che fa la memoria virtuale è creaee una nuova astrazione – gli spazi degli indirizzi – cioè

un'astrazione della memoria fisica, come come un processo è un'astrazione del processo fisico (la

CPU).

La memoria virtuale può essere implementata spezzando lo spazio virtuale degli indirizzi in pagine

e mappando ognuna su frame di memoria fisica o tenendole (momentaneamente) non mappate.

4.3.3 Velocizzare la paginazione

In ogni sistema di pagina si devono affrontare 2 questioni principali:

1. il mappaggio dall'indirizzo virtuale all'indirizzo fisico deve essere veloce;

2. se lo spazio virtuale degli indirizzi è grande, la tabella delle pagine sarà grande.

Il punto 1 deriva dal fatto che il mappaggio virtuale-fisico deve avvenire per ogni riferimento alla

memoria. Tutte le istruzioni devono alla fine raggiungere la memoria e molte di loro fanno

riferimento a operandi anch'essi in memoria, quindi è necessario fare, per ogni istruzione, 1, 2 o più

riferimenti alla tabella delle pagine. Se l'esecuzione di un'istruzione impiega 1 nanosecondo, la

ricerca all'interno della tabella delle pagine deve essere fatta in meno di 0,2 ns per evitare che il

mappaggio diventi il principale "collo di bottiglia".

Il punto 2 deriva dal fatto che tutti i computer moderni usano indirizzi virtuali a 32 bit (anche se

ormai i 64 bit sono di uso comune). Con una pagina di 4 KB, uno spazio degli indirizzi a 32 bit

dispone di 1 milione di pagine e uno spazio degli indirizzi a 64 bit ha uno spazio maggiore di

quanto si possa considerare.

Con 1 milione di pagine nello spazio degli indirizzi virtuali, la tabella delle pagine deve avere 1

milione di voci.

Ciascun processo ha bisogno della propria tabella delle pagine perchè ha il suo spazio degli

indirizzi personale.

La necessità di un mappaggio delle pagine grande e veloce è un limite significativo dovuto al modo

in cui sono costruiti i computer. La progettazione più semplice è di avere una sola tabella delle

pagine che consiste di un array di registri hardware veloci, con una sola voce per ogni pagina

virtuale, indicizzata per numero di pagina virtuale.

All'avvio di un processo, il SO carica i registri con la tabella delle pagine del processo, presa da una

copia che tiene in memoria. Durante l'esecuzione del processo non sono necessari altri riferimenti

alla memoria per la tabella delle pagine. Il vantaggio di questo metodo è che è semplice e non

richiede riferimenti di memoria durante il mappaggio. Lo svantaggio è che è dispendioso se la

tabella delle pagine è estesa. Un altro è che dover caricare l'intera tabella delle pagine a ogni cambio

di contesto compromette le prestazioni.

Nella situazione opposta, la tabella delle pagine può essere interamente caricata in memoria. Tutto

ciò di cui necessita l'hardware è un singolo registro che punti all'inizio della tabella delle pagine.

Questa progettazione consente che il mappaggio virtuale-fisico sia cambiato ad ogni cambio di

contesto ricaricando un solo registro. Ciò richiede uno o più riferimenti di memoria per la lettura

della tabella delle pagine durante l'esecuzione di ogni istruzione, rendendola molto lenta.

Translation lookaside buffer (TLB)

Esempio: consideriamo un'istruzione di 1 byte che copia un registro in un altro. In assenza di

paginazione, questa istruzione fa un solo riferimento alla memoria, per prelevare l'istruzione. Con la

paginazione, per accedere alla tabella delle pagine, è necessario almeno un altro riferimento alla

memoria. Poichè la velocità di esecuzione è generalmente limitata dalla velocità con cui la CPU può

prendere le istruzioni e i dati dalla memoria, dover fare 2 riferimenti alla memoria riduce le

prestazioni della metà (nessuno così userebbe la paginazione).

La soluzione è quella di equipaggiare i computer di un piccolo dispositivo hardware per mappare gli

indirizzi virtuali sugli indirizzi fisici senza passare dalla tabella delle pagine.

Il dispositivo è chiamato TLB (Translation Lookaside Buffer), o talvolta detto memoria

associativa. Si trova abitualmente dentro la MMU e consiste di un numero ridotto di voci che

raramente superano le 64 unità. Ciascuna voce contiene informazioni riguardo una pagina, tra cui il

numero di pagina virtuale, un bit impostato quando la pagina viene modificata, il codice di

protezione ed il frame fisico in cui si trova la pagina. Questi campi hanno una corrispondenza 1-a-1

con i campi nella tabella delle pagine, tranne che per il numero di pagina virtuale, che non è

necessario nella tabella delle pagine. Un altro bit indica se la voce è valida (in uso) o meno.

Valido Pagina virtuale Modificato Protezione Frame

1 140 1 RW 31

1 20 0 R X 38

1 130 1 RW 29

1 129 1 RW 62

1 19 0 R X 50

1 21 0 R X 45

1 860 1 RW 14

1 861 1 RW 75

Un esempio che potrebbe generare il TLB di questa figura è un processo in un ciclo che comprende

le pagine virtuali 19, 20 e 21, in modo tale che queste voci del TLB abbiano codici di protezione per

la lettura e l'esecuzione. I dati principali attualmente usati sono sulle pagine 129 e 130. La pagina

140 contiene gli indici usati nei calcoli dell'array che stiamo elaborando. Sulle pagine 860 e 861 c'è

lo stack.

Come funziona il TLB? Quando un indirizzo virtuale viene presentato alla MMU per la traduzione,

l'hardware prima guarda se il suo numero di pagina virtuale è presente nel TLB, confrontandolo

simultaneamente con tutte le voci. Se trova un riscontro valido e l'accesso non viola i bit di

protezione, il frame è preso direttamente dal TLB, senza andare nella tabella delle pagine. Se il

numero di pagina virtuale è presente nel TLB, ma l'istruzione prova a scrive su una pagina di sola

lettura, si generea un errore di protezione.

Quando la pagina virtuale non è nel TLB, la MMU rileva la TLB miss (fallimento di TLB) e fa

una normale ricerca sulla tabella delle pagine. Quindi sfratta una delle voci dal TLB e la rimpiazza

con la voce della tabella delle pagine appena cercata. In questo modo, se quella pagina è riusata a

breve, la seconda volta si avrà una TBL hit (successo di TLB) anzichè una TLB miss.

Quando una voce è eliminata dal TLB, il bit modificato è copiato di nuovo nella voce della tabella

delle pagine nella memoria. Gli altri valori sono già lì, eccetto il bit referenziato. Quando il TLB

viene caricato dalla tabella delle pagine, tutti i campi vengono presi dalla memoria.

Gestione software del TLB

Nella progettazione dove ogni macchina con la memoria virtuale paginata abbia delle tabelle delle

pagine riconosicute dall'hardware, più un TLB, la gestione di quest'ultimo e il trattamento dei suoi

errori sono interamente svolti dall'hardware della MMU. I trap al SO avvengono solo quando una

pagina non è in memoria.

Quanto detto era valido in passato. Le macchine RISC (Reduced Instruction Set Computer)

moderne eseguono quasi tutta questione delle pagine tramite software.

Su queste macchine, le voci del TLB sono caricate esplicitamente dal SO. Quando si verifica una

TLB miss, invece di avere la MMU che va alla tabella delle pagine per cercare e prelevare il

necessario riferimento alla pagina, viene generato soltanto un errore di TLB e il problema passa al

SO. Il sistema deve trovare la pagina, rimuovere una voce dal TLB, inserirne una nuova e riavviare

l'istruzione in errore. Tutto questo avviene con una manciata di istruzioni, poichè i TLB miss osno

più frequenti degli errori di pagine.

Se il TLB è grande (64 voci) la gestione software del TLB si rivela essere efficiente per ridurre la

frequenza di miss. In questo caso, il guadagno principale è una MMU molto più semplice, che

libera una quantità considerevole di spazio di chip sulla CPU per le cache e altre caratteristiche che

possono migliorare le prestazioni.

Per migliorare le prestazioni sulle macchine che fanno la gestione del TLB sono state sviluppate

varie strategie. Un approccio critica sia la riduzione delle TLB miss sia quella dei costi quando se

ne verificano. Per ridurre le TLB miss il SO può, a volte, cercare di dedurre quali pagine saranno

probabilmente usate come successive e caricare in anticipo le loro voci nel TLB. Quando un

processo client invia un messaggio a un processo server sulla stessa macchina è molto probabile che

il server sarà presto in esecuzione. Mentre processa il trap per fare la , il sistema può anche

send

controllare dove sono il codice del server, i dati e le pagine di stack per mapparli prima che abbiano

la possibilità di causare errori di TLB.

Il modo consueto di trattare una TLB miss, sia hw che sw, è andare alla tabella delle pagine e

compiere le operazioni di indicizzazione per localizzare la pagina referenziata. Il problema che

deriva da questa ricerca nel software è che le pagine contenenti la tabella delle pagine potrebbero

non essere nel TLB e ciò causerebbe ulteriori errori TLB durante il processo. Questi errori sono

riducibili mantenendo una cache software estesa di voci TLB in una posizione fissa, le cui pagine

siano sempre mantenute nel TLB. Il SO può sostanzialmente ridurre le TLB miss controllando

prima la cache software.

Con la gestione TLB via software è fondamentale capire la differenza fra 2 tipi di miss. Una soft

miss avviene quando la pagina di riferimento non è nel TLB ma è nella memoria e quindi basta

semplicemente aggiornare il TLB: non serve alcun I/O dal disco. Di solito per trattare una soft miss

ci vogliono 10-20 istruzioni macchina che possano essere completate in pochi nanosecondi.

All'opposto, una hard miss avviene quando la pagina stessa non è in memoria e quindi nemmeno

nel TLB. Per prendere la pagina serve un accesso al disco, il che implica parecchi millisecondi: una

hard miss è milioni di volte più lenta di una soft miss.

4.3.4 Tabelle delle pagine per grandi memorie

La gestione gerarchica delle tabelle associa una tabella delle pagine ad ogni processo e tale tabella

contiene un elemento per ogni pagina logica che il processo sta utilizzando.

Il pregio è il facile ritrovamento dell'indirizzo fisico poichè la tabella è ordinata per indirizzi logici.

Il difetto è la dimensione di ciascuna tabella che può occupare grandi quantità di memoria.

64

In un'architettura a 64 bit lo spazio di indirizzamento è 2 , la dimensione delle pagine è di

2 10 12 52 64 12

4KB=2 *2 =2 , la dimensione della tabella è di 2 =2 /2 con elementi a 8 byte (64 bit).

La tabella della pagina invertita ha un elemento per ogni pagina reale. Ogni elemento è costituito

dall'indirizzo logico della pagina memorizzata in una specifica locazione reale e dall'identificatore

del processo <PID, #Pg, Scostamento>

Come difetto ha tempi estremamente lunghi per il ritrovamento dell'indirizzo logico.

Esempio in un'architettura a 64 bit:

64

spazio di indirizzamento: 2 ;

– 2

dimensione pagine: 4KB=2 KB;

– 18

dimensione RAM: 256MB=2 KB

– 18 2 16

dimensione della tabella: 2 /2 =2 =65536 elementi a 8 byte (64 bit).

4.4 Algoritmi di rimpiazzamento delle pagine

Lo spazio di indirizzamento virtuale è sempre più grande dello spazio fisico. Quando non vi è più

memoria fisica disponibile da assegnare a una porzione di memoria virtuale, il SO effettua un fault

di pagina e sono predisposti i passi che il SO effettua per rimpiazzare la pagina di memoria.

Ci si chiede: quale pagina scaricare? La pagina da eliminare dalla memoria va conservata? Se sì, a

che condizione ?

Una soluzione semplice da descrivere, ma impossibile da realizzare, è un algoritmo che si basa sul

concetto di etichetta (valore numerico) da assegnare alla pagina: ogni volta che avviene un fault di

pagina il sistema scarica dalla memoria fisica la pagina che ha un'etichetta con valore più alto.

Il valore dell'etichetta è il numero di istruzioni che saranno eseguite prima che si faccia riferimento

a quella pagina per la prima volta:

Come?! Impossibile: non possiamo sapere il numero minimo delle istruzioni che si eseguiranno

prima che si faccia riferimento a quella pagina se non conosciamo quando si farà riferimento a tale

pagina!!

Quest'algoritmo è semplice da descrivere ma non si può realizzare, ma si può usare per dei test su

altri metodi di rimpiazzamento delle pagine.

Come fare il test:

Supponiamo di voler fare eseguire su di un elaboratore un certo numero di processi di test. Se alla

prima esecuzione teniamo traccia di come vengono eseguite le istruzioni pagina per pagina è

possibile etichettarle per utilizzarle in una seconda esecuzione.

Utilizzando questo algoritmo e confrontando i risultati con un nuovo algoritmo di rimpiazzamento è

possibile capire la sua bontà di esecuzione in termini di percentuale rispetto all'ottimale.

Quindi se il nuovo algoritmo di rimpiazzamento è peggiore dell'1% esso sarà sicuramente

accettabile, visto che quello ottimale è solo una teorizzazione non realizzabile.

Casi Reali

Gli algoritmi di rimpiazzamento delle pagine si dividono in:

1. (pagine) non usate di recente;

2. First In First Out (FIFO);

3. della seconda opportunità;

4. dell'orologio;

5. last recently used;

6. working-set.

Definiamo 2 bit assegnati a ciascuna pagina fisica:

R = bit che rappresenta l'informazione di pagina referenziata (1 = letta o scritta);

M = bit che rappresenta l'informazione di pagina modificata (1 = scritta).

NOTA: è importante comprendere che i bit R e M devono essere aggiornati ad ogni riferimento in

memoria.

I bit R e M formano 4 possibili classi e possono essere usati come segue:

il bit R viene azzerato periodicamente ad ogni interruzione dal clock e tale azzeramento stabilisce le

pagine che non sono state referenziate di recente.

Le classi formate dalla combinazione di R ed M sono:

0: R=0 M=0 => pagina non usata e non modificata;

1: R=0 M=1 => pagina non usata e modificata;

2: R=1 M=0 => pagina usata e non modificata;

3: R=1 M=1 => pagina usata e modificata.

NOTA: La classe 1 sembra che non si possa mai verificare, si manifesta quando una pagina è nella

classe 3 e un interrupt del clock riporta tutti i bit R delle pagine a 0.

Nella classe 2, il bit M non sarà mai azzerato dal clock in quanto è necessario conoscere se la

pagina è stata modificata per permettere la sua conservazione sul disco.

4.4.1 (Pagine) non usate di recente

Definite le classi, l'algoritmo di rimpiazzamento delle pagine non usate di recente rimuove una

pagina dalla classe di valore più basso (solitamente nella classe 0, 1, 2 o 3).

L'idea di fondo è che è meglio rimuovere una pagina modificata a cui non si è fatto riferimento per

un periodo di clock al posto di una pagina usata di frequente.

Quest'algoritmo è facile da comprendere, efficace nella sua implementazione e non è ottimale ma è

spesso soddisfacente.

4.4.2 FIFO: First In First Out

Quest'algoritmo si basa sulla scelta delle pagine in una lista concatenata contenente i riferimenti alle

pagine fisiche. In questa lista, la testa conterrà la pagina più vecchia in ordine di tempo, mentre in

coda sarà presente la più recentemente usata.

In termini tecnini, quando si attiva un fault di pagina, verrà scaricata dalla memoria la pagina che si

trova in testa alla lista e la nuova pagina sarà inserita in coda.

L'idea di fondo è quella di togliere la pagina più vecchia presente in memoria.

NOTA: l'algoritmo rischia di togliere pagine molto usate ma da molto tempo in memoria.

4.4.3 Della seconda opportunità

Quest'algoritmo è una variante dell'algoritmo FIFO: ha la stessa logica di esecuzione, ma tiene

conto dei bit R e M prima definiti.

Tecnicamente, l'algoritmo fa riferimento alla pagina in testa alla coda (quella più vecchia), inoltre

controlla il bit R che riporta che riporta se essa è stata usata recentemente: se è così (R=1) allora la

pagina viene spostata alla fine della coda ed R messo a 0 in modo che la pagina viene considerata

come inserita ex-novo.

L'idea è quella di cercare una pagina vecchia che non sia usata nel precedente periodo di clock.

NOTA: Se tutte le pagine risultano, l'algoritmo li passerà tutte in rassegna, mettendo per ciascuna

il bit R=0; alla fine del ciclo tutte le pagine avranno R=0 e l'algoritmo sarà uguaale a quello della

FIFO. R=1

A B C D E F G H

Pagina caricata Pagina che più è

per prima stata caricata di

recente

R=0

B C D E F G H A

È trattata come

una nuova

pagina caricata

4.4.4 Algoritmo dell'orologio

L'algoritmo dell'orologio è simile a quello della seconda opportunità, a differenza della sua

implementazione.

Piuttosto che considerare una lista lineare si considera una lista circolare; il puntatore punta alla

pagina più vecchia e dopo avere controllato il bit R decide se rimpiazzare la pagina con una nuova e

portare avanti il puntatore per la nuova ricerca.

Se R=1 azzera R e porta avanti il puntatore. Se R=0 sposta la pagina corrente sul disco per spazio

ad una nuova.

4.4.5 LRU: Last Recently Used

L'algoritmo LRU si basa sulla strategia di eliminare la pagina che non è stata usata da un tempo più

lungo.

Tecnicamente, l'implementazione di tale algoritmo richiede che ogni pagina abbia un registro

contenente un valore numerico (contatore, tempo trascorso,...) che rappresenta la persistenza della

pagina in memoria.

Quando un'istruzione viene referenziata, un contatore viene incrementato e il suo valore viene

assegnato alla pagina contenente l'istruzione referenziata.

Se si verifica un fault di pagina, il gestore della memoria scaricherà la pagina che ha il valore più

piccolo nel caso del contatore numerico o l'orario più vecchio nel caso in cui sia usato il timer.

L'idea è quella di togliere dalla memoria le pagine che sono state usate meno recentemente.

NOTA: Complesso, ma non impossibile da realizzare

Una sua possibile implementazione dell'algoritmo LRU può essere effettuata con una tabella nxn

dove n è il numero delle pagine della memoria fisica.

Quando viene referenziata la pagina i la tabella viene aggiornata nel modo seguente:

tutti gli elementi della riga i sono posta a 1;

– tutti gli elementi della colonna i sono posta a 0;

4.4.6 Working set

Il Working Set ( Insieme di Lavoro ) è l'insieme delle pagine utilizzate correttamente da un

processo.

NOTA: Se tutto l'insieme di lavoro fosse caricato in memoria, il processo girerebbe senza causare

troppi fault di pagina.

Molti SO tendono a caricare in memoria tutto l'insieme di lavoro del processo prima di concedergli

l'uso della CPU. Tale tecnica è basata sulla prepaginazione (il SO tende a predire quali pagine

saranno utilizzate dal processo). Inoltre, per far ciò, il sistema, per ogni processo, deve conoscere

all'istante di tempo t le pagine di tutti i riferimenti presenti in memoria.

In generale gli applicativi tendono a non riferire il loro spazio di indirizzamento in maniera

uniforme e globale, ma concentrano la loro attenzione in uno spazio di indirizzamento ristretto.

Per ogni istante t esiste un insieme costituito da tutte le pagine utilizzate dai K riferimenti più

recenti in memoria. Tale insieme è il Working Set.

In modo più semplice ma meno preciso il Working Set può essere definito come la raccolta di

pagine di memoria, attualmente proprietà di un processo e non swapped.

Il Working-Set può variare nel tempo sia in termini di dimensione che di contenuto delle pagine.

Quindi il WS può essere definito come una funzione a 2 variabili w(k,t) dove k rappresenta i

riferimenti più recenti in memoria e t il tempo in esame.

Tale funzione è una funzione monotòna non decrescente il cui limite per k->inf è finito (asintoto).

La rapida crescita della curva dipende dal fatto che i programmi in generale accedono in maniera

casuale ad un numero piccolo di pagine, e che questo insieme cambia lentamente nel tempo.

Dal grafico, ci si rende conto che, finito il periodo di transizione, esiste un intervallo di valori K per

cui l'insieme di lavoro non è cambiato.

Considerato che l'insieme di lavoro cambia lentamente nel tempo, si può supporre di conoscere

quali pagine saranno necessarie quando il processo verrà fatto partire, sulla base dell'insieme di

lavoro che è presente al momento dell'interruzione.

La prepaginazione consente di caricare tali pagine prima che il processa venga mandato in

esecuzione.

L'algoritmo si basa sulla ricerca di una pagina che non fa parte del Working-Set e quindi scaricarla.

.

.

.

2084 1

Tempo approssimato in cui

la pagina è stata 2003 1

usata l'utima volta 1980 1 R è il bit presente

in ogni pagina.

1213 0 Definisce

la pagina riferita

2014 1

2020 1

2032 1

1620 0

Tabella delle pagine

R=1 la pagina è stata referenziata dopo il tick di clock;

R=0 la pagina non è stata referenziata dopo il tick di clock.

Se R=1 la pagina non è candidata ad essere rimossa; viene aggiornato il valore del campo virtuale

della pagina, poichè esso indica che, in quell'istante, la pagina fu usata.

Se R=0 si controlla il tempo della pagina, sottraendo al tempo corrente il tempo trovato nella

pagina. Se questo valore è maggiore di T allora la pagina viene eliminata e sostituita dalla nuova.

Mentre, se il tempo è minore di T, allora la pagina è ancora presente nell'insieme di lavoro.

NOTA: Se tutta la tabella è stata esaminata e nessun valore è stato trovato a 0, allora tutte le

pagine fanno parte del working-set e si sceglierà una pagina, in modo casuale, per fare spazio alla

nuova pagina richiesta.

4.5 Segmentazione della memoria

Per ridurre gli sprechi di memoria o la ridondanza nell'uso della memoria, si possono organizzare i

programmi in modo da raccogliere a fattor comune alcune loro sottoparti da destinare a processi

distinti.

La struttura di un applicativo può essere suddivisa in 3 famiglie:

codice: contenente le istruzioni del programma;

– dati: contiene sia i dati statici che dinamici;

– stack: contiene i dati che il processo deve salvare durante la sua esecuzione (chiamata a

– procedura, cambio di contesto,...)

Vantaggi:

il SO può consentire a più processi di condividere lo stesso codice e, nel contempo, di

– operare su dati diversi;

lo swap agisce sui segmenti di memoria per spostare sul disco le parti dei processi non in

– uso.

La caratteristica principale di una memoria virtuale è di essere unidimensionale, cioè esiste un

indirizzo di partenza e uno finale.

L'idea di avere più aree di memoria perfino con dimensioni diverse può agevolare alcuni applicativi

che scindono il proprio in più compiti.

Per esempio, il compilatore scinde il proprio compito in almeno 5 processi con le relative tabelle:

1. testo sorgente;

2. tabella dei simboli;

3. tabella delle costanti;

4. albero dell'analisi sintattica;

5. lo stack per le chiamate a procedure nel compilatore.

Potrebbe verificarsi che, in compilazione, si possa avere un numero estremamente elevato di

variabili (cosa normale per il resto).

Il compilatore riempie la tabella dei simboli e non riesce ad andare avanti perchè lo spazio di

memoria è insufficiente. Da ciò scaturisce un messaggio di errore <memoria insufficiente>, ma

questo è un falso errore in quanto potrebbe esserci dell'altra memoria in qualche altra parte che

potrebbe essere recuperata.

Soluzione banale: compattare la memoria prima di mandare il messaggio di errore.

Soluzione ottimale: dividere la memoria in molti spazi di indirizzamento con diverse dimensioni,

chiamati segmenti.

Ciascun segmento ha una propria cardinalità ed una sequenza lineare di indirizzi che generalmente è

diversa dagli altri. In essi la lunghezza degli stack cambia dinamicamente liberando e concedendo

indirizzi di memoria.

NOTA: poichè ciascun segmento costituisce uno spazio di indirizzamento separato, esso può

crescere o contrarsi in maniera indipendente dagli altri.

Per specificare un indirizzo nella memoria segmentata, il programma deve dare un indirizzo

costituito da 2 parti: un numero rappresentante lo specifico segmento e un indirizzo all'interno del

segmento.

La memoria segmentata, oltre ad avere come vantaggio quello di semplificare la gestione dei dati

che crescono e si contraggono, semplifica anche le chiamate alle procedure:

le n procedure distinte possono risiedere sugli n segmenti distinti e, se 0 è l'indirizzo di

– partenza della procedura all'interno del segmento, allora la procedura sraà richiamata dalla

coppia (n,0);

poichè ogni procedura è inserita su di un segmento diverso, una sua modifica implica una

– sua compilazione, ma non la compilazione delle altre e ne tanto meno un loro un loro

riposizionamento;

la segmentazione facilita la condivisione delle risorse e/o dei dati fra i vari processi;

– facilita la protezione e la sicurezza dei dati

Implementazione della segmentazione

L'implementazione della segmentazione differisce da quella della pagina per un punto

fondamentale:

le pagine hanno dimensione fissa;

– i segmenti hanno dimensione variabile.

Segmentazione con paginazione

Se i segmenti sono grandi, può risultare poco conveniente, ma non impossibile, caricarli in memoria

nella loro interezza.

La paginazione è una tecnica che consente di risolvere questo problema in tal senso, secondo i

canoni della paginazione, in memoria sono residenti quelle porzioni di segmento che sono

necessarie.

Ciascun segmento rappresenta un normale spazio di indirizzamento virtuale e viene gestito tramite

paginazione allo stesso modo in cui era gestita la memoria virtuale.

NOTA: Il Pentium è un'architettura molto vicina a questo tipo di approccio.

L'algoritmo è attivato quando si verifica un riferimento alla memoria, quindi:

1. il numero del segmento viene usato per recuperare il descrittore del segmento all'interno del

segmento dei descritori;

2. si esegue un controllo per verificare se la tabella delle pagine relativa al segmento è presente

in memoria;

3. si esamina l'elemento della tabella delle pagine realtivo alla pagina virtuale richiesta;

4. si somma l'offset all'indirizzo di partenza della pagina per individuare l'indirizzo fisico;

5. si effettua la lettura o scrittura.

Esempio:

la memoria virtuale del Pentium è dotata di 2 tabelle: la LDT (Local Descriptor Table) e la GDT

(Global Descriptor Table).

Tutti i programmi hanno una loro LDT ma esiste una sola GDT. Per accedere ad un segmento, il

Pentium carica dapprima un selettore di quel segmento in uno dei suoi registri di segmento della

macchina.

Il registro CS (Code Segment) contiene il selettore per il segmento del codice del programma.

Il registro DS (Data Segment) quello per il segmento dei dati del programma.

Appena il microprogramma ha ricevuto la richiesta, questo è in grado di trovare il descrittore

completo che corrisponde a quel settore.

In seguito controlla se l'offset va a cadere oltre i limiti del segmento.

Calcolo della dimensione della pagina

P = dimensione delle pagine espressa in Byte;

S = dimensione media di un processo espressa in Byte;

E = richiesta delle pagine da ciascun elemento della tabella delle pagine.

Overhead (P) = S*E/P+P/2

S/P = numero approssimato di pagine richieste da ogni processo

S*E/P = numero di byte occupati nella tabella delle pagine;

P/2 = memoria sprecata nell'ultima pagina.

Deriviamo rispetto a P per il calcolo del minimo:

2

Overhead(P)' = -S*E/P +1/2

2 (1/2)

-S*E/P +1/2 = 0 ==> P = (2*S*E) 5 – INPUT/OUTPUT

5.1 Princìpi hardware dell'I/O

Una delle principali attività del SO è il controllo dei dispositivi di input/output:

inviare comandi ai dispositivi;

– catturare le interruzioni;

– trattare le condizioni di errore;

– fornire un'interfaccia tra i dispositivi fisici e il resto del sistema.

Per quanto riguarda l'hardware di I/O, vi sono 2 punti di vista differenti:

hardware visto come componenti elettronici, quindi circuiti integrati, fili, alimentatori,

– motori;

hardware visto come un insieme di moduli funzionali software, quindi comandi accettati

– dall'hardware, funzioni fornite a corredo, gestione degli errori, interfaccia software.

5.1.1 Dispositivi di I/O

I dispositivi di I/O si dividono in 3 grandi famiglie:

dispositivi a blocchi: un dispositivo a blocchi memorizza le informazioni in blocchi di

– lunghezza gissa, ognuno dei quali ha un proprio indirizzo la cui lunghezza varia da 512 a

32768 byte. Un dispositivo a blocchi può leggere o scrivere ciascun blocco in maniera

indipendente dagli altri: i dischi sono l'esempio più classico, ma anche le unità a nastro

possono essere considerate dispositivi a blocchi;

dispositivi a carattere: un dispositivo a carattere invia o riceve un flusso di caratteri senza

– tener conto di alcuna struttura di blocco, non è indirizzabile, e non può eseguire alcuna

operazione di posizionamento randomico;

dispositivi particolari:

– i clock non sono indirizzabili a blocchi, e non generano o ricevono caratteri, essi non

– fanno altro che causare interruzioni ad intervalli di tempo ben definiti;

i dispositivi a mappa di memoria non appartengono nè ai dispositivi a blocchi nè ai

– dispositivi a carattere.

5.1.2 Controller dei dispositivi

I dispositivi di I/O sono costituiti da 2 parti: meccanica ed elettronica. La parte meccanica è il

dispositivo stesso. La parte elettronica è detta controllore del dispositivo e si presenta sotto forma di

un circuito stampato o di una scheda.

La scheda del controllore generalmente contiene un connettore, nel quale può essere inserito il cavo

proveniente dal dispositivo stesso.

Esempio di controllore.

L'interfaccia tra dispositivo e controllore è a bassissimo livello.

Consideriamo, per esempio, il caso di un disco formattato con 256 settori di 512 byte per traccia:

invio: il dispositivo fisico manda al controllore una successione di bit (4096=512*8=un

– blocco) preceduti e seguiti da un certo numero di bit informativi rappresentanti il

preambolo (numero del cilindro e del settore, lunghezza, etc...) e il checksum (codice di

errore) rispettivamente;

controllo: compito del controllore è di convertire il flusso seriale di bit in un blocco di byte

– e di eseguire l'eventuale correzione d'errore valutando il checksum;

assemblaggio: il controllore assembla il blocco in un suo buffer interno e, successivamente,

– lo invia.

Dispositivo e CPU: comunicazioni

Dall'esempio fatto, si deduce che ogni controllore ha dei buffer o registri per la comunicazione con

la CPU.

Manipolando opportunamente tali registri, il SO può richiedere al controllore del dispositivo di:

spedire o ricevere dati;

– accendersi o spegnersi;

– conoscere lo stato del dispositivo;

– eseguire azioni alternative.

Attraverso il buffer dati il SO può legere o scrivere dati da e verso il dispositivo.

Esempio: le schede grafiche che gestiscono I/O da/per il terminale hanno una RAM video per

visualizzare i pixel sul monitor, ossia un buffer in cui il SO e i programmi possono scrivere o

leggere le informazioni da visualizzare sul monitor.

5.1.3 Comunicazione tra CPU e registri del controllore

Ogni registo è identificato da un numero di porta (intero a 1 o 2 byte).

Esempi di istruzioni per leggere o scrivere su un registro del controllore sono:

IN Reg, Porta (IN R0, 4)

– OUT Porta, Reg (OUT 14, R1)

Rispettivamente la CPU trasferisce nel o dal registro della CPU il valore presente sulla porta

identificata dal valore numerico.

Tale approccio consiste nel mappare i registri del controllore in memoria centrale: ad ogni registro

viene assegnato un indirizzo di memoria unico a cui non corrisponde nessuna parola della memoria.

L'I/O del buffer dati è mappato in memoria e le porte di I/O sono separate dai registri del

controllore.

Analisi dello schema di comunicazione.

Quando la CPU vuole leggere una parola sia da una porta sia dalla memoria, effettua i seguenti

passi: trasferisce l'indirizzo, di cui necessita, sulle linee di indirizzamento bus;

– imposta un segnale di READ sulla linea di controllo BUS;

– una linea parallela determina se la richiesta riguarda lo spazio di I/O o di memoria: se la

– richiesta è rivolta alla memoria, sarà la memoria a rispondere, in caso contrario sarà un

dispositivo a rispondere.

Nel caso di I/O mappato di memoria, ogni dispositivo confronterà le linee di indirizzamento come

gli spazi di memoria ad esso assegnati. Se riconoscerà l'indirizzo, risponderà alla richiesta.

NOTA: non si possono creare ambiguità o conflitti in quanto non è possibile che un indirizzo sia

assegnato contemporaneamente alla memoria e all'indirizzamento del dispositivo.

Virtù dell'I/O mappato in memoria

Facilità d'uso: con un I/O mappato in memoria i registri possono essere visti come generiche

variabili gestite comodamente con un qualsiasi linguaggio di programmazione di alto livello (come

il C), quindi il controllore del dispositivo può essere gestito da esso, contrariamente all'uso delle

porte in cui è preferibile usare l'Assembler per la loro compilazione.

Sicurezza: non occorrono meccanismi di protezione speciali per impedire ai processi utente di

eseguire dell'I/O:

conflittualità: il SO evita l'inserimento in uno spazio di indirizzamento virtuale dello spazio

– di indirizzamento contenente i registri del dispositivo;

suddivisione: il SO, definendo i registri dei diversi controllori in pagine diverse dello spazio

– di indirizzamento, può lasciare all'utente il controllo di certi dispositivi inibendo l'accesso ad

altri;

riduzione: assegnando spazi diversi ai controllori di specifici dispositivi, si può ridurre il

– kernel del SO ed inoltre evitare l'interferenza tra dispositivi analoghi.

Elasticità: ogni istruzione che fa riferimento alla memoria, può fare riferimento ai registri mappati

di un dispositivo, quindi istruzioni di test e/o confronto possono essere usate sui registri per valutare

il contenuto senza overhead.

Vizi dell'I/O mappato in memoria

Caching: supponiamo di essere in un sistema con cache e di volere testare l'indirizzo mappato in

memoria relativo ad un registro di un dispositivo che rappresenta l'attività o l'inattività del

dispositivo:

quando sarà effettuata la richiesta di lettura della memoria, i relativi indirizzi saranno inseriti

– nella cache e le successive letture di quell'indirizzo saranno effettuate dalla cache;

il sistema non si renderà conto della transazione in quanto il dispositivo cambierà il valore

– nella memoria e non nella cache.

Soluzione: cache selettiva sulla memoria, inserimento di overhead.

Un solo spazio di indirizzamento: tutti i moduli della memoria e i dispositivi devono analizzare i

riferimenti alla memoria e decidere a quali rispondere. Un bus singolo è facile da analizzare. Nel

caso di bus multiplo, i dispositivi non hanno modo di vedere gli indirizzi della memoria e quindi

non hanno modo di rispondere.

Si prospettano 3 soluzioni:

inviare la richiesta sul bus della memoria, se questa non risponde inviare la stessa richiesta

– sul bus dei dispositivi;

il dispositivo spia che controlla quali indirizzi sono destinati ai dispositivi;

– al boot del sistema, identificare e destinare una parte di indirizzamento ai dispositivi e

– marcarlo come non memoria. Gli indirizzi che cadono in questo spazio sono inviati al bus

dei dispositivi.

5.1.4 I/O Direct Memory Access

Il DMA è un controllore di accesso in memoria che permette di svincolare la CPU dalla

comunicazione con i dispositivi.

Il DMA può essere inserito all'interno dei dispositivi (ogni dispositivo ha il suo DMA), oppure un

unico DMA integrato nella scheda madre.

Dovunque si trovi, il DMA ha accesso al bus di sisiema indipendentemente dalla CPU e i suoi

registri possono essere letti o scritti dalla CPU:

registro di indirizzamento della memoria;

– registro contatore in byte;

– registro di controllo o di stato;

– registro di controllo per le porte di I/O;

– registro di controllo per la direzione (lettura o scrittura);

– registro di controllo sulla dimensione del dato (byte, parola);

– registro di controllo relativo al numero di byte da trasferire.

Come lavora il DMA:

1. la CPU programma il DMA (istruzione di lettura o scrittura, indirizzo di partenza e numero

di byte) in modo che esso conosca dove e quali dati trasferire, invia un comando al

controllore del disco per trasferire i dati dal disco al buffer interno del disco;

2. il DMA inizia il trasferimento effettuando una richiesta di lettura sul bus verso il controllore

del disco (richiesta convenzionale in quanto al controllore del disco risulta chiara la sua

provenienza: CPU o DMA);

3. il DMA pone sulle linee di indirizzamento l'indirizzo di memoria dove il controllore del

disco deve copiare il dato; il controllore del disco trasferisce il dato da o verso la memoria;

4. infine il controllore del disco dà un segnale di ricevuta (acknowledgement) al DMA di

operazione effettuata;

5. il DMA incrementa l'indirizzo di memoria da usare e decrementa il contatore dei byte;

6. if (contatorebyte==0) goto 2;

7. il DMA invia un'interruzione alla CPU per comunicarle che il trasferimento è terminato.

Trasferire i dati dal disco al buffer interno del disco è una strategia necessaria in quanto il

controllore del disco può controllare il CheckSum prima di iniziare il trasferimento. Inoltre, i bit del

disco arrivano ad una frequenza costante e, quando il bus di trasferimento è occupato, questi

possono risiedere da qualche parte senza essere perduti e senza appesantire il DMA di una eventuale

nuova gestione per tale anomalia.

DMA Singoli e DMA Multipli:

i DMA singoli possono gestire un'unità di I/O alla volta e la loro gestione avviene come già

– detto;

i DMA multipli gestiscono più dispositivi contemporaneamente. Al suo interno troviamo

– tanti insiemi di registri quanti sono i canali verso i dispositivi. La CPU carica i registri

relativi a ciascun dispositivo; ogni trasferimento deve riguardare un diverso controllore di

dispositivo e ogni volta che la parola o il byte è trasferito, il DMA decide quale dispositivo

servire. Il DMA può essere programmato con un modello Round-Robin o a priorità.

La modalità per il trasferimento dei dati è duplice:

singola parola o byte: il DMA prende possesso del BUS dati e, se la CPU necessita di esso

– devo aspettare. In questo caso la CPU viene leggermente rallentata da un'interruzione per il

trasferimento dei dati del DMA;

in modalità blocco: il DMA richiede al dispositivo di acquisire il bus, produce una serie di

– trasferimenti e, dopo, la rilascia (modo burst). Al costo di una singola richiesta di BUS si

trasferiscono più parole, più efficiente per il trasferimento, ma meno adatto per grosse mole

di dati (la CPU potrebbe stare bloccata per molto tempo).

DMA – Indirizzi virtuali

Modo alternativo: il controllore del dispositivo invia la parola al controllore del DMA (prima

richiesta di bus) e, dopo, il controllore del DMA scrive la parola al posto giusti (seconda richiesta di

bus). Questo metodo ha come difetto le 2 richieste di bus e come pregi le copie di dati tra dispositivi

e le copie tra memoria e memoria.

I DMA usano indirizzi fisici quando il SO deve convertire gli indirizzi da virtuali a fisici.

Schema alternativo: il DMA fa uso degli indirizzi virtuali e usa l'MMU per la conversione da

virutale a fisico.

Un buffer per il DMA serve per:

correzione dei dati: checksum;

– sincronizzazione:

– DMA non pronto a ricevere i dati;

– attesa del controllore del DMA per il bus;

– con un buffer si evitano le criticità temporali.

5.2 Princìpi del software di I/O

I principi del software di I/O sono:

indipendenza del dispositivo: scrivere programmi indipendenti dal dispositivo stesso, ossia

– che non necessitano di specificare il tipo di dispositivo con anticipo. Esempio: un

programma che deve usare un file deve accedere al file in maniera trasparente dal supporto

che lo contiene;

denominazione uniforme: il nome di un file o di un dispositivo deve essere indipendente dal

– dispositivo stesso e dovrebbe essere formato da una stringa di caratteri;

trattamento degli errori: deve essere effettuato quanto più vicino possibile all'hardware. In

– molti casi il recupero dell'errore si può realizzare a livelli bassi in modo trasparente per i

livelli alti;

trasferimento sincrono e asincrono: la maggior parte dell'I/O avviene in modo asincrono: la

– CPU fa partire il trasferimento e passa a fare altro. I programmi utente sono più facili da

gestire se le operazioni di I/O sono sincrone (read);

bufferizzazione: questo processo subentra quando i dati non possono essere trasferiti

– immediatamente e devono essere memorizzati in un contenitore, detto buffer, per un futuro

utilizzo.

Esistono 3 modi diversi per effettuare l'I/O:

I/O programmato;

– I/O guidato dalle interruzioni del dispositivo;

– I/O tramite DMA.

5.2.1 I/O programmato

L'I/O programmato è il metodo più semplice ed affida il compito di fare tutto il lavoro alla CPU:

questo metodo usa la CPU per pilotare il dispositivo, sia esso a caratteri sia esso a blocchi.

Esempio. Supponiamo che si voglia stampare una stringa di 8 caratteri su di una stampante:

1. assemblare la stringa in un buffer nello spazio utenti;

2. acquisizione, da parte del processo, della risorsa (stampante) in scrittura;

1. se la stampante è occupata il processo si interrompe sino all'ottenimento della risorsa;

2. ottenuta la risorsa il processo utente effettua una chiamata al sistema in cui comunica la

stringa da stampare.

3. il SO copia il buffer contenente la stringa nello spazio del kernel;

4. il SO copia il primo carattere nel registro dati della stampante, utilizzando, ad esempio, l'I/O

mappato in memoria, questa azione attiva la stampante;

5. dopo la stampa del carattere, la stampante modificherà il suo registro di stato per dare la

disponibilità di stampa al SO;

6. dopo avere stampato il primo carattere il SO controlla se la stampante è pronta per stampare

il secondo carattere.

Questo ciclo termina quando l'intera stringa sarà stampata.

L'I/O programmato è semplice, ma ha lo svantaggio di legare, a tempo pieno, la CPU al processo di

stampa, e ciò fino al completamento dell'operazione di I/O.

Se il tempo richiesto per la stampa è breve allora l'attesa attiva è accettabile. Nei sistemi embedded

in cui la CPU è dedicata a tale scopo, l'attesa attiva è ragionevole.

Nei sistemi in cui la CPU è occupata in maniera massiccia è opportuno usare altri metodi per

effettuare l'I/O è opportuno usare altri metodi per effettuare l'I/O.

5.2.2 I/O guidato dalle interruzioni

Tale metodo permette alla CPU di fare qualcos'altro mentre è in attesa che la stampante sia pronta a

ricevere il carattere da stampare.

Esempio: supponiamo che una stampante sia in grado di stampare 100 caratteri, quindi la stampa di

un carattere richiede un tempo di 10 ms. In questo tempo la CPU potrebbe processare altre

istruzioni.

Quando viene fatta la chiamata di sistema per la stampa, il buffer utente contenente la stringa viene

copiato nello spazio del kernel, e il primo carattere, quando la stampante è pronta a riceverlo, viene

inviato verso la stampante. A questo punto il SO chiama lo schedulatore e la CPU è usata per

elaborare altri processi.

Il processo che ha richiesto la stampa della stringa è bloccato fin quando tutta la stringa non sarà

stampata.

Quando la stampante ha stampato il carattere ed è pronta a ricevere il successivo, genera

un'interruzione, che ferma il processo corrente e viene eseguita la procedura di servizio delle

interruzioni delle stampanti.

NOTA: Lo svantaggio di tale metodo risiede nel richiedere tante interruzioni quanti sono i caratteri

da stampare. Tali interruzioni richiedono tempo sottratto alla CPU.

5.3.2 I/O tramite il DMA

Questo metodo tende ad eliminare lo spreco di tempo dovuto alle eccessive interruzioni. Il DMA

emette i caratteri e li passa alla stampante uno alla volta senza disturbare la CPU.

In pratica, l'I/O tramite DMA non è altro che un I/O programmato in cui non è la CPU a fare il

lavoro, bensì il DMA.

Pro: le frequenze di interruzioni passano da carattere a buffer stampato.

Ci sono alcune considerazioni da fare:

se sono presenti molti caratteri, le interruzioni rallentano notevolmente l'I/O; I/O tramite

– DMA può essere una buona alternativa;

se il DMA non è in grado di far andare la stampante alla sua massima velocità e la CPU non

– è eccessivamente utilizzata, allora l'I/O guidato dalle interruzioni o l'I/O programmato

possono essere alternative più adeguate.

5.3 I livelli del software dell'I/O Software di I/O a livello utente

Esistono 4 livelli per il software di I/O: Software del SO indipendente

dal dispositivo

1. gestore delle interruzioni;

2. drive di dispositivo; Drive di dispositivo

3. software del SO indipendente dal dispositivo;

4. software di I/O a livello utente. Gestore delle interruzioni

Le loro funzionalità variano nei diversi S. Operativi. Hardware

5.3.1 Gestione delle interruzioni

Le interruzioni di I/O sono estremamente costose ed è opportuno nasconderle nella parte più bassa

del SO, così da evitare possibili interferenze con i processori di più alto livello.

Quando un'interruzione è stata prodotta, la procedura che risolve tale interruzione farà in modo da

soddisfare l'interruzione, ossia fare ripartire il processo bloccato, in uno dei seguenti modi:

1. manderà un segnale UP su di un semaforo;

2. farà una SIGNAL su di una variabile condizionale;

3. manderà un messaggio al processo bloccato.

Quindi l'effetto sarà di far riprendere il processo bloccato.

Ecco alcuni passi:

1. salvare i registri che non sono stati salvati dall'hardware delle interruzioni;

2. impostare il contesto per la procedura che gestisce l'interruzione;

3. organizzare una pila per tale procedura;

4. mandare un segnale al controllore delle interruzioni e ripristinare queste ultime;

5. copiare i registri del processo corrente nella tabella dei processi;

6. eseguire la procedura di servizio delle interruzioni: essa estrarrà le informazioni dai registri

del controllore del dispositivo che ha prodotto l'interruzione;

7. scegliere quale processo eseguire: generalmente quello a priorità più alta;

8. organizzare la MMU e la TLB (Translation Lookaside Buffer: un buffer cache per la

conversione degli indirizzi virtuali) per il processo successivo;

9. caricare tutti i registri del processo;

10. eseguire di nuovo il processo.

Dopo aver fatto tutto ciò, il processore potrebbe essere "stanco", quindi:

Un'interruzione non è affatto semplice, nè noiosa, nè facile. Inoltre, le difficoltà crescono se la

macchina su cui sono presenti le interruzioni è una macchina virtuale a memoria virtuale.

Differenza tra chiamata di sistema e trap.

Se la segnalazione di un evento è causata da un dispositivo fisico si verifica un'interruzione.

Se la segnalazione di un evento è causata da un programma si verifia un segnale di eccezione

(Exception, Trap).

Chiamata di sistema.

La chiamate di sistema sono funzioni di servizio del kernel a cui fanno riferimento le applicazioni.

Una chiamata di di sistema controlla gli argomenti specificati dall'applicazione; definisce una

struttura dati dove inserire tali argomenti da passare al kernel; esegue la funzione nel kernel.

Le chiamate di sistema si possono classificare in:

controllo dei processi;

– gestione dei file;

– gestione dei dispositivi;

– gestione delle informazioni;

– gestione delle comunicazioni.

Interrupt

Il driver del dispositivo Avvia l'operazione di I/O

avvia l'operazione di I/O

La CPU rileva eventuali

INTERRUZIONI eseguendo un

controllo sulla linea delle

interruzioni dopo ogni istruzione - I dati sono disponibili

- La scrittura dei dati è terminata

- Si è verificato un errore

La CPU rileva l'INTERRUZIONE

e trasferisce il controllo al

gestore delle interruzioni Salto alla procedura di

gestione delle interruzioni

posta in un indirizzo di

Il gestore delle interruzioni memoria fissato

elabora i dati e termina

La CPU ripende l'esecuzione

prima interrotta

Il meccanismo delle interruzioni permette di rispondere ad un evento asincrono.

I compiti di CPU e gestore delle interruzioni sono:

garantire la gestione delle interruzioni durante le elaborazioni critiche;

– recapitare efficientemente un segnale di interruzione al corretto gestore delle interruzioni del

– dispositivo;

strutturare i segnali di interruzione a livelli per garantire i vari livelli di priorità.

Alcuni SO usano il meccanismo delle interruzioni per la gestione della memoria virtuale:

eccezione di pagina mancante;

– sospensione del processo corrente;

– esecuzione del relativo gestore del nucleo:

– memorizza le informazioni sullo stato del processo;

– sposta il processo nella coda d'attesa;

– compie le operazioni necessarie per la gestione della memoria virtuale;

– avvia le operazioni per prelevare la giusta pagina;

– restituisce il controllo derivante dall'interruzione;

– stabilisce la ripresa di un altro processo.

Le interruzioni possono essere:

mascherabili:

– errori numerici;

– indirizzamento errato di memoria.

non mascherabili:

– richiesta di un servizio da parte di un dispositivo.

In conclusione

TRAP: un'istruzione di trap effettua un cambio da modalità utente a modalità kernel, come ad

esempio: accesso non consentito in memoria, divisione per 0, disconnessioe dalla rete, errore nel

trasferimento dati.

INTERRUPT: richiesta spesso asincrona e di provenienza esterna al microprocessore che forza il

SO a interrompere il programma in esecuzione.

CHIAMATE DI SISTEMA: chiamate di un programma ad una funzione del SO. Le System Calls

permettono ai programmi utenti di richiamatre i servizi del SO: sono solitamente disponibili come

istruzioni assembler o come delle funzioni nei linguaggi che supportano direttamente la

programmazione di sistema.

5.3.2 Driver di dispositivo

Ogni dispositivo necessita di un codice specifico per il controllo del dispositivo stesso (mouse:

movimento del mouse, click; disco: settori, tracce, cilindri, testine, movimento del braccio, tempi di

posizionamento).

Per accedere all'hardware del dispositivo, ossia ai registri del controllore, un drive può essere

inserito o all'interno del kernel o nello spazio utente:

drive nello spazio utente:

– evita i crash del sistema, in quanto un drive così definito non interfereisce con il SO;

– duplicazione dei drive: lo stesso dispositivo verrà gestito da tanti drive quanti sono gli

– utenti interessati al dispositivo.

drive nel kernel:

– può interferire con il sistema provocando crash;

– riduce lo spazio di memoria utilizzato.

In alcuni casi i drive più comuni sono definiti all'interno del kernel del SO.

I driver dei dispositivi sono generalmente l'ultimo scalino dei livelli del SO e risiedono al di sotto

del SO.

Il SO suddivide i dispositivi in 2 grandi famiglie e si interfaccia con esse attraverso le opportune

librerie.

Le interfacce per la gestione dei dispositivi contengono le procedure per la manipolazione del

dispositivo.

Alcuni esempi riguardano la lettura di un blocco per quanto riguarda i dispositivi a blocco o la

scrittura di una stringa di caratteri per quando riguarda la scrittura di una stringa su un

dispositivo a carattere.

In molti sistemi di elaborazione il SO è un unico programma binario al cui interno sono inseriti tutti

i drive che il sistema può usare.

In alcuni SO l'inserimento di un nuovo dispositivo può implicare la ricompilazione del kernel o il

reboot del sistema prima di poter usare il nuovo dispositivo.

I program counter hanno un modello in cui i driver vengono caricati dinamicamente durante

l'esecuzione del SO.

Ogni drive di dispositivo ha alcune funzioni generiche che possono essere espresse come segue:

richiesta di lettura e/o scrittura da software diversi dal drive; in generale la richiesta è

– effettuata su valori virtuali;

inizializzare il dispositivo;

– gestire l'alimentazione;

– gestire il log degli eventi.

I passi che compie il driver di un dispositivo sono:

controllare i parametri di input e verificarne la loro validità;

– tradurre i dati virtuali in valori reali (dispositivo disco: tradurre l'indirizzo lineare in termini

– di testina, traccia, settore, cilindro);

controllare se il dispositivo è in uso o inattivo;

– controllare il funzionamento del dispositivo attraverso una lista di comandi caricati negli

– appositi registri del controllore del dispositivo;

attendere risposte dal controllore del dispositivo: se la risposta è immediata il drive non

– viene bloccato altrimenti sarà bloccato e sbloccato successivamente con un'interruzione;

se i controlli e le operazioni di lettura o scrittura sono andati in porto, il driver dovrà passare

– le informazioni al software che ne ha fatto richiesta.

Alcune complicazioni: consideriamo un SO in cui è permesso inserire o disinserire dispositivi a

caldo (e.g. device USB). Mentre il sistema è impegnato a leggere un blocco, l'utente può decidere di

spegnere il dispositivo. In questi casi si può abortire il trasferimento di I/O e rimuovere dal sistema

ogni richiesta pendente verso il dispositivo.

5.3.3 Software del SO indipendente dal dispositivo

La funzione principale del software indipendente dai dispositivi è di eseguire quelle operazioni di

I/O che sono comuni a tutti i dispositivi e, inoltre, fornire un'interfaccia uniforme al software di

livello utente.

Funzioni svolte dal software indipendente dai dispositivi:

1. interfaccia uniforme per driver di dispositivo;

2. bufferizzazione;

3. segnalazione degli errori;

4. allocazione e rilascio di dispositivi dedicati;

5. fornire una dimensione del blocco indipendente dal dispositivo.

Il confine tra il software indipendente dal dispositivo e i driver non è quasi mai ben delineato e

dipende fortemente sia dal SO sia dal dispositivo.

Interfaccia uniforme per driver di dispositivo

È un'interfaccia per rendere i dispositivi simili tra loro. Le interfacce si dividono in:

interfacce multiple: situazioni in cui ogni drive di dispositivo ha una propria interfaccia,

– impone chiamate che differiscono da drive a drive e, inoltre, le chiamate al kernel variano da

driver a driver. In questa configurazione, interfacciare un nuovo driver richiede un grande

sforzo di programmazione;

interfacce unificate: di contro l'inserimento di un driver che sia conforme a un'interfaccia

– comune può risultare estremamente semplice. I programmatori di drive sanno cosa poter

richiedere al kernel (set di istruzioni ammesse) e quali funzioni fornire al sistema (funzioni

operative del dispositovo).

Un altro aspetto dell'interfaccia comune è il modo in cui sono denominati e identificati i dispositivi.

In questo modo usando 2 indirizzi numerici:

numero principale di dispositivo: identifica il drive per il dispositivi;

– numero di dispositivo secondario: identifica il dispositivo o unità su cui si deve leggere o

– scrivere.

Si identificano tutte le unità o i dispositivi presenti nel sistema; inoltre la protezione di tali untià la

si ottiene con la stessa politica di protezione dei file.


PAGINE

128

PESO

684.16 KB

AUTORE

astrex

PUBBLICATO

4 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Palermo - Unipa
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher astrex 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à Palermo - Unipa o del prof Tegolo Domenico.

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 informatica

Informatica teorica: sintesi
Appunto
Sintesi basi dati
Appunto
Riepilogo di Metodi Matematici per Informatica
Appunto
Riepilogo JAVA Prima Parte
Appunto