Sistemi Operativi: Appunti delle Lezioni

P(S).

prima il decremento e se il valore è negativo blocchiamo il processo sulla lista dei processi bloccati

su quel semaforo.

V(S). Faccio l’incremento. Se ora S≤0 ovvero c’è un processo nella lista dei processi in coda, viene

rimosso e risvegliato con un wakeup();

Problema: maggior lavoro dovuto alla gestione della lista

Esempio produttore consumatore metodo enter():

while count= buffersize; Se inseriamo un semaforo mutex.P() prima

mutex.P() dell’incremento e mutex.V() dopo

++count; l’incremento non funziona perchè dopo

Buffer[in]=item; l’incremento potrebbe esserci un context

In=[in+1]%buffersize; switch ma anche perchè non è stata

Mutex.V() considerate la varbiale in, che è condivisa.

Potremmo pensare di allargare la sezione

critica a tutto il codice, ma ciò non andrebbe

comunque bene perché, come detto sopra,

essa deve essere il più stretta possibile e

inoltre non verrebbe eliminato il busy waitint

potremmo inserire più semafori:

Soluzione:

1) empty= mi indica le celle vuote del buffer

2) full= mi indica le celle piene del buffer

Problema dei lettori-scrittori. Con lettori-scrittori ci riferiamo a due thread che utilizzano una

base di dati per la lettura e scrittura di dati.

1) Dobbiamo assicurarci che l’acceso alla base di dati sia corretto.

2) Vogliamo che suddetta base di dati sia il più efficiente possibile, ovvero avere il più alto livello

di parallelismo possibile, ovvero più persone devono accedere alla base di dati.

Possono accedere a essa più lettori, ma non un lettore e uno scrittore o più scrittori

contemporaneamente; questo perché quando ci sono modifiche alla base di dati nessuno vi deve

accedere

Sergio Malavolti 18

Appunti delle Lezioni di “Sistemi Operativi”. 2005-06

Scienze di Internet

Problema: si può presentare la starvation in quanto, dando la precedenza ai lettori, uno scrittore

rischierebbe di non scrivere mai. Ma è un rischio che possiamo correre in quanto le possibilità che

si verifichi attesa indefinita sono molto basse.

Il caso inverso invece (ammettere più scrittori) comprometterebbe l’efficienza e l’integrità dei dati.

Nessuna delle 2 scelte è perfetta e bisogna quindi venire a un punto d’incontro.

Il problema consiste nel controllare i lettori

StartRead() presenti nella base di dati in modo tale che

quando non ve ne sono al suo interno

S.(P) possiamo far entare uno scrittore che era

++count; momentaneamente in attesa. Per evitare che la

if count=1 then db.P() variabile ‘count’ venga mal modificata

S.(V) dobbiamo inserire un semaforo S che mi

controlla le modifiche. Ma questo non basta

EndRead() perché, dopo la modifica di ‘count’, potrebbe

S.(P) esserci in context switch che mi creerebbe la

--count; situazione in cui uno scrittore e un lettore

if count=0 then db.V() vogliono accedere contemporaneamente alla

S.(V) base di dati. Di conseguenza conviene la

sezione critica delimitata dal semaforo ‘S’

anche l’if.

Sergio Malavolti 19

Appunti delle Lezioni di “Sistemi Operativi”. 2005-06

Scienze di Internet

7. Gestione Memoria

In genere un programma risiede in disco sotto forma di file binario eseguibile. Quando deve essere

eseguito viene caricato in memoria e inserito all’interno di un processo. L’insieme dei processi

presenti nei dischi e che attendono di essere trasferiti nella memoria per essere eseguiti formano la

coda di ingresso. Nella maggior parte dei casi un programma utente, prima di essere eseguiti, deve

passare attraverso vai stadi in cui gli indirizzi possono essere rappresentati in modi diversi.

Generalmente l’associazione di istruzioni e dati a indirizzi di memoria si può compiere in qualsiasi

fase del seguente percorso:

• Compilazione. Se in questa fase si sa dove il processo risiederà in memoria si può generare

codice assoluto.

• Caricamento. Se il punto sopra non è soddisfatto il compilatore deve generare codice

rilocabile. In questo caso si ritarda l’associazione finale degli indirizzi a questa fase. Se

l’indirizzo iniziale cambia è sufficiente ricaricare il codice d’utente per incorporare il valore

modificato.

• Esecuzione. Se durante questa fase il processo può essere spostato da un segmento di

memoria ad un altro, si deve ritardare l’associazione degli indirizzi fino a questa fase.

Dynamic loading. Una procedura viene caricata solo quando viene richiamata. Tutte le procedure

si tengono nella memoria secondaria in un formato di caricamento rilocabile. In generale viene

caricato il programma principale nella memoria e se, durante l’esecuzione, una procedura deve

richiamare un’altra procedura, si controlla che essa non sia già presente in memoria centrale,

altrimenti vi viene caricata. Il vantaggio è dato dal fatto che una procedura che non si adopera non

viene caricata.

Dyinamic linking. Simile al caricamento dinamico utilizzato soprattutto per le librerie di sistema.

Per ogni riferimento ad una procedura di libreria, si inserisce all’interno dell’immagine eseguibile

del programma di sistema una piccola porzione di codice (stub) che fa appunto riferimento alla

giusta procedura di libreria.

Overlays. Tecnica utilizzata per permettere a un processo di essere più grande della memoria che

gli si assegna. Questo concetto si fonda sulla possibilità di mantenere nella memoria soltanto le

istruzioni e i dati che si usano con maggiore frequenza. Quando sono necessarie altre istruzioni,

queste si caricano nello spazio precedentemente occupato dalle istruzioni che non sono più in uso.

Tipi di indirizzi.

• Logico. Indirizzo generato dalla CPU (da ‘0’ a ‘max’).

• Fisici. Indirizzo visto dall’unità di memoria, cioè caricato nel registro dell’indirizzo di

memoria (da ‘r+0’ a ‘r+max’).

I metodi di associazione degli indirizzi nelle fasi di compilazione e caricamento producono indirizzi

logici e fisici identici, mentre nella fase di esecuzione non coincidono e qui gli indirizzi logici

vengono anche detti virtuali.

Sergio Malavolti 20

Appunti delle Lezioni di “Sistemi Operativi”. 2005-06

Scienze di Internet

MMU. Siccome la traduzione degli indirizzi comporta del lavoro da parte della macchina è

possibile ovviare a questa cosa facendo riferimento a questa unità che appunto effettua conversioni

degli indirizzi logici a fisici. Tramite un registro di rilocazione.

Questa è l’idea: quando un processo utente

genera un indirizzo, prima dell’invio all’unità di

memoria, si somma a tale indirizzo il valore

contenuto nel registro di rilocazione

Allocazione contigua. In questo sistema di

gestione i programmi sono contenuti in una

singola sezione contigua della memoria.

Chiaramente il sistema operativo deve gestire

gli spazi liberi e vuoti (detti buchi). Il neo di

questo sistema di gestione è proprio il fatto che

lo spazio ai programmi deve essere assegnato

contiguamente.

Problema della frammentazione: esso si presenta quando lo spazio libero di memoria è sufficiente

per soddisfare una richiesta ma non è contiguo. Questo può essere dovuto al fatto che assegnando

porzioni di memoria poco più grandi a un processo, la parte rimanente rimane inutilizzata perché

tropo piccola per contenere un altro processo.

Una possibile soluzione può essere spezzare il processo in tre parti (programma, dati e stack) e

distribuirlo negli spazi liberi, sperando di far diminuire la frammentazione esterna. Di conseguenza

i registri di rilocazione saranno tre. Questa soluzione migliora la frammentazione esterna ma non la

risolve.

Algoritmi di scelta dei buchi liberi. Possiamo pensare che il sistema operativo gestisca una lista

contenente i puntatori di dove sono situati gli spazi liberi di memoria. Ogni elemento alla lista

contiene un puntatore all’indirizzo di memoria e uno che riporta la dimensione del buco. I criteri per

scegliere un buco libero sono tre:

1) First-fit. Viene scelto il primo buco in grado di contenere il processo. A questo punto, per i

processi successivi, si può scegliere se riscorrere la lista sempre daccapo oppure continuare

da dove si era arrivati (soluzione migliore, in quanto intendiamo la lista come circolare).

2) Best-fit. Viene scelto il buco più piccolo tra quelli in grado di contenere il processo.

L’inconveniente di questo metodo è dato dal fatto che la lista deve essere scorsa tutta.

3) Worst-fit. Viene scelto il buco più grande tra quelli in grado di contenere il processo. Amche

qui la lista deve essere scorsa tutta. Sebbene possa sembrare assurdo questo metodo è

efficace in quanto può lasciare porzioni di memoria abbastanza grandi da contenere altri

processi.

Problema: Tutti questi algoritmi soffrono di frammentazione esterna.

Soluzione con la compattazione: interrompiamo l’attività corrente e rimettiamo insieme tutti i

piccoli buchi liberi in modo da averne uno grande, in grado di contenere un processo che richieda di

essere caricato in memoria.

Sergio Malavolti 21

Appunti delle Lezioni di “Sistemi Operativi”. 2005-06

Scienze di Internet

Il costo del compattamento è

proporzionale alla memoria che stiamo

spostando, quindi vogliamo quello più

veloce, come proposto nella figura

accanto: per ricompattare 900kb di

memoria l’ultima soluzione è la più

conveniente in quanto sposto solamente

200kb.

Paginazione. L’idea di questa tecnica di gestione è memorizzare lo spazio per un certo processo in

posizione non contigua, ovvero dividerlo in tre parti come spiegato precedentemente (programma,

dati e stack con tre registri di rilocazione) in modo da sfruttare meglio i buchi piccoli. Inoltre la

memoria viene suddivisa in blocchi e ad ogni processo vengono assegnati un’insieme di blocchi.

Il processo che vogliamo inserire in memoria viene suddiviso in blocchi logici (detti pagine) mentre

la memoria centrale è divisa in blocchi fisici (detti frame), e accettiamo che i singoli blocchi siano

memorizzati su frame non necessariamente contigui. Le dimensioni delle pagine e dei frames varia

da 512 byte a 8 kb. Con questa tecnica la frammentazione esterna scompare.

Problema frammentazione interna: siccome lo spazio di memoria assegnato a un processo non è

multiplo della dimensione delle pagine, l’ultimo blocco di memoria assegnato non sarà

completamente pieno. Se la dimensione del processo è indipendente dalla dimensione della pagina

ci dobbiamo aspettare una frammentazione interna di mezza pagina per processo.

Schema della paginazione.

P