Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

in caso di sospensione del processo, si esce una prima volta dalla regione critica mediante signal(mutex)

che si trova all’interno della condizione if not <…>. Se, invece, la cond. di sinc. è soddisfatta, la regione

critica viene liberata direttamente dalla signal che si trova in chiusura della procedura (Acquisizione).

Dopo si richiede che venga eseguita la procedura d’uso.

13. Illustrare il concetto di separazione della politica di gestione di una risorsa dai possibili

meccanismi di gestione e come questa separazione possa essere realizzata da un gestore di

risorse di tipo risorsa.

Per politica di gestione di una risorsa si intende il criterio in base al quale, nel caso in cui più processi

richiedono di usufruire della stessa risorsa, si sceglie quale servire per primo e in che modo servire poi

gli altri. Un meccanismo di gestione invece è una specifica soluzione logica al problema della gestione di

una risorsa che può essere poi implementata a livello di SW o HW. Un esempio di meccanismo di

gestione, per il modello a memoria globale, è quello dei semafori;un altro meccanismo più complesso e

realizzabile a sua volta mediante i semafori, è quello dei monitor. Le politiche di gestione possibili sono

diverse e possono andare dalle elementari LIFO e FIFO alle più sofisticate politiche a priorità. Un

inconveniente del meccanismo semaforico elementare è che esso permette di realizzare una sola politica

di gestione, quella di tipo FIFO, strettamente legata al meccanismo stesso, in quanto la primitiva

SIGNAL, utilizzata per il rilascio delle risorse, non fa altro che sbloccare, di volta in volta, il processo in

testa alla coda, cioè il primo arrivato, senza la possibilità di sceglierne un altro, magari a maggior

priorità. La soluzione al problema della separazione tra politica e meccanismo di gestione di una risorsa,

nel modello a memoria globale, può essere data dai semafori privati. Si tratta di semafori su cui un solo

processo può eseguire una wait, mentre tutti gli altri possono sbloccarlo con una signal. Il fatto che ad

ogni semaforo possa attendere un solo processo permette di adottare di volta in volta la politica di

scheduling più adatta, anche in considerazione della risorsa che si sta gestendo, in quanto i processi non

si trovano tutti in un’unica coda FIFO. Un costrutto, più evoluto, che consente al programmatore di

distogliere la propria attenzione da meccanismi di gestione di basso livello, come i semafori (attraverso i

quali, tra l’altro, il costrutto si può realizzare), per concentrarsi sulle politiche di gestione, è il monitor.

In questo caso, per ottenere una politica di gestione differente dalla FIFO, che è sempre quella di

default, basta modificare le procedure signal o wait che agiscono su variabili di tipo condition (cond) e

fanno parte dell’oggetto monitor. La signal può risvegliare, invece del processo da più tempo in coda,

quello a maggior priorità, secondo criteri stabiliti. In alternativa, si pùò trasformare la wait in una wait

condizionale, la quale riceve in ingresso un parametro intero, che è proprio la posizione in coda in cui

va messo il processo chiamante e dipende ovviamente dal suo livello di priorità: in questo modo la

signal sbloccherà automaticamente i processi in coda in ordine di priorità decrescente.

14. Descrivere la soluzione dei problemi di “mutua esclusione” e “produttore/consumatore”

mediante gestore di risorse di tipo risorsa.

Nel modello a memoria globale, o comune, si pone il problema della mutua esclusione, dovuto alla

competizione di più processi per l’accesso ad un insieme di variabili comuni localizzata in un’area di

memoria allocata staticamente e che si suppone rappresentino delle risorse ad uso esclusivo, cioè

utilizzabili da un solo processo per volta. Perciò bisogna evitare la sovrapposizione temporale degli

accessi alle risorse comuni da parte dei vari processi: il problema si risolve facilmente con l’uso di un

semaforo. Supponendo che sem sia il semaforo associato alla risorsa comune in questione, un processo,

per accedere ad essa deve compiere le seguenti operazioni: wait (sem) – uso – signal (sem).

La wait, come è noto, mette il processo in attesa che il semaforo diventi verde (sem = 1) e lo fa tornare

rosso (sem = 0) non appena riesce a passare e ad occupare la risorsa. Se a questo punto arriva un altro

processo che richiede di accedere alla risorsa, rimane in coda al semaforo, finchè il primo processo non

la rilascia eseguendo la signal, che incrementa la variabile sem e rende, così, verde il semaforo. Questa

semplice soluzione del problema della mutua esclusione è alla base della gestione di una risorsa

condivisa e allocata staticamente, o anche di un insieme di risorse equivalenti allocata dinamicamente

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

(sempre nel caso di risorse ad uso esclusivo). Il problema del produttore/consumatore rappresenta la

forma più sofisticata di cooperazione tra due processi, in cui due o più processi si scambiano

informazioni attraverso uno o più buffer. Il produttore è un processo che genera un messaggio e lo

deposita in un’area di memoria, mentre il consumatore è un processo che preleva da un buffer un

messaggio e lo utilizza. Sono previsti i seguenti vincoli di cooperazione:

1) il produttore non può depositare un nuovo messaggio in un buffer pieno;

2) il consumatore non può prelevare un messaggio da un buffer vuoto;

I vincoli, così formulati, si riferiscono al caso più generale, in cui un buffer può contenere più messaggi.

Il buffer sarà dunque una risorsa condivisa e, poiché i messaggi devono essere ricevuti nello stesso

ordine di invio, sarà in particolare una coda di messaggi a cui vengono associati due semafori,

spazio_disponibile e messaggio_disponibile, attraverso i quali i due processi si scambiano informazioni

sull’avvenuto deposito e prelievo di messaggi. La struttura dati del buffer sarà del tipo:

Type messaggio =…….

Var coda_di_messaggi : …., messaggio_disponibile: semaphore initial(0), spazio_disponibile:

semaphore initial(n);

Le procedure di invio e ricezione eseguite rispettivamente dal produttore e dal consumatore saranno

invece:

Procedure Invio ( x: msg)

Begin

Wait(spazio_disponibile);

<deposito del messaggio x nella coda dei messaggi>;

signal(messaggio_disponibile);

end.

Procedure Ricezione ( x: msg)

Begin

Wait(messaggio_disponibile);

<prelievo di un messaggio dalla coda e sua assegnazione al parametro X>;

signal(spazio_disponibile);

end.

Nel caso in cui il buffer è implementato con un vettore circolare gestito con due puntatori testa e coda,

la struttura dati diventa:

Var vettore: array[0..n-1] of messaggio;

testa:0..n-1 initial(0)

coda:0..n-1 initial(0)

messaggio_disponibile: semaphore initial(0);

spazio_disponibile: semaphore initial(0);

Procedure Invio (x:msg) Procedure Ricezione (x:msg)

Begin Begin

Wait(spazio_disponibile); wait(messaggio_disponibile);

vettore[coda] = x; x = vettore[testa];

coda = (coda+1)mod N; testa = (testa+1)mod N;

signal (messaggio_disponibile); signal (spazio_disponibile);

end. End.

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

La soluzione vista permette ad un produttore di produrre più messaggi di seguito e lo stesso vale per il

consumatore, che può prelevare più messaggi uno dopo l’altro, ma non va bene nel caso in cui ci siano

più produttori e più consumatori. E’ evidente infatti che in tal caso bisogna garantire la condizione di

mutua esclusione nella modifica della struttura dati, in particolare per quanto riguarda i puntatori testa e

coda (più processi potrebbero tentare di aggiornarli contemporaneamente, provocando dei

malfunzionamenti). Ecco la soluzione:

Procedure Deposito (x:msg); Procedure Prelievo(x:msg);

begin begin

wait(spazio_disponibile); wait(messaggio_disponibile);

wait(mutex1); wait(mutex2);

i = coda; i = testa;

coda = (coda+1)mod N; testa = (testa+1)mod N;

signal(mutex1); signal(mutex2);

vettore(i) = x; x = vettore(i);

signal(messaggio_disponibile); signal(spazio_disponibile);

end. End.

E’ stata, dunque, inserita in entrambe le procedure una regione critica che impedisce a più processi di

aggiornare i puntatori testa e coda contemporaneamente, mentre il salvataggio dei loro valori in i, prima

dell’incremento, permette di garantire l’accesso agli spazi giusti sia in lettura che scrittura, senza

interferenze. Il deposito e il prelievo veri e propri dei messaggi rimangono fuori dalle rispettive regioni

critiche e quindi non serializzati, in quanto conviene fornire il parallelismo, una volta scongiurate le

possibili interferenze.

16. Illustrare il concetto di monitor come gestore di risorse e descrivere una sua possibile

implementazione mediante primitive del kernel.

Il costrutto monitor rappresenta una primitiva di sincronizzazione di più alto livello rispetto ai semafori

e può essere visto, in un certo senso, come un’estensione del costrutto classe, tipico dei linguaggi di

programmazione ad oggetti. Dal punto di vista sintattico, anzi, un monitor è identico ad una classe,

essendo costituito come questa da una struttura dati e da alcuni metodi per l’accesso a tale struttura

dati. Sia un monitor che una classe possono inoltre istanziare oggetti. Le proprietà che differenziano i

due costrutti sono invece le seguenti: 1)più processi possono condividere un oggetto di tipo monitor,

ma possono accedere alla struttura dati solo attraverso i suoi metodi; 2) un solo processo per volta può

essere attivo nel monitor (va cioè garantita la mutua esclusione tra i processi nell’accesso alle funzioni

del monitor); 3) un processo che si trova all’interno del monitor e non può più proseguire per qualche

motivo deve essere bloccato, in modo da far posto ad altri processi che vogliono accedere al monitor.

Quest’ultimo requisito si può ottenere attraverso una variabile cond di tipo condition sulla quale si

possono eseguire due operazioni: cond.wait è cond.signal, da non confondere con la wait e la signal che

agiscono sui semafori. La cond.wait permette ad un processo che non possa proseguire, essendo

risultato falsa una certa condizione di sinc., di sospendersi e di mettersi in attesa nella cosa associata alla

variabile cond, finchè un altro processo non lo sblocca, eseguendo una signal sulla stessa variabile.

Poiché la cond.signal può essere eseguita solo da un processo P, che si trova all’interno del monitor, si

pone il problema di quale processo, tra P e un processo sbloccato Q, debba proseguire la sua

esecuzione. Il nodo si scioglie a favore di Q, per evitare che P possa continuare a modificare una

condizione di sincronizzazione che possa compromettere la ripartenza di Q. Tuttavia, non appena Q

uscirà dal monitor, sarà P a rientrarvi e non un altro processo che può essersi messo in coda nel

frattempo. Da quanto detto, si evince come un monitor possa realizzare, di fatto, un gestore di risorsa

di tipo risorsa, che presenta, rispetto al meccanismo semaforico, il vantaggio di togliere al

programmatore l’onere di garantire la sincronizzazione dei processi e la mutua esclusione, risolvendo i

due problemi in maniera automatica. Tuttavia, se il costrutto monitor non è previsto dal linguaggio di

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

programmazione adottato, si può pensare di realizzarlo ugualmente mediante primitive del kernel, e in

particolare attraverso i semafori. La mutua esclusione può essere assicurata da un semaforo mutex

inizializzato a 1, su cui ogni processo fa una wait per richiedere l’uso del monitor. La condizione al

punto tre viene invece garantita da un semaforo ungent inizializzato a zero su cui ogni processo si

sospende con una wait al momento di lasciare il monitor e di sbloccare un altro processo in coda. Prima

di lasciare il monitor, però, un processo deve verificare se vi sono processi in coda su urgent ed

eventualmente sbloccarne uno, in accordo con quanto detto prima. Un contatore urgent_count

memorizza, invece, il numero di processi in tale coda. La variabile condition viene invece realizzata con

un semaforo cond.sem inizializzato a zero, sul quale un processo si può sospendere con la nota

primitiva wait e con un contatore cond.count che conta i processi in attesa su cond.sem. La struttura

dati del monitor sarà allora corredata da quattro metodi, così definiti:

1) procedure enter_monitor 2) procedure leave_monitor

begin begin

wait(mutex); if urgent.count >0 then

end. Signal(urgent);

else

signal(mutex)

end.

3) procedure cond.wait 4) procedure cond.signal

begin begin

cond.count = cond.count +1; urgent.count + +;

if urgent.count>0 then if cond.count>0 then

signal(urgent); begin

else signal(cond.sem);

signal(mutex); wait(urgent);

wait(cond.sem); end;

cond.count - -; urgent.count - -;

end. End.

Se si suppone che ogni processo esegue la cond.signal sempre ultima (ipotesi non troppo restrittiva ma

notevolmente esemplificativa), si può eliminare il semaforo urgent e il contatore urgent.count poiché

nessun nuovo processo potrà essere sbloccato ed entrare nel monitor finchè il processo attivo non avrà

finito di usarlo. La cond.wait, cond.signal e la leave_monitor diventano allora:

procedure cond.wait procedure cond.signal procedure leave_monitor

begin begin begin

cond.count = cond.count +1; if cond.count>0 then signal(mutex);

signal(mutex); signal(cond.sem); end.

wait(cond.sem); else

cond.count - -; signal(mutex);

end. End.

Il monitor è, in definitiva un’astrazione che permette al programmatore di concentrarsi sulle politiche di

gestione delle risorse, ignorando i meccanismi di basso livello (semafori), che di fatto le realizzano.

Conviene perciò ragionare in termini di monitor anche quando il linguaggio di programmazione non

prevede questo costrutto: si può pensare a tale scopo, di raccogliere la struttura dati e i metodi in una

libreria che possa essere usata all’occorrenza. Politiche di gestione diverse dalla solita FIFO e basate su

livelli di priorità si possono applicare modificando la cond.signal secondo i criteri scelti, in modo che

risvegli il processo a priorità maggiore, o sostituendo alla cond.wait una wait condizionale che metta il

processo bloccato nella posizione (in coda) ricevuta come parametro di ingresso: in questo modo la

signal abiliterà automaticamente per primo il processo a maggior priorità.

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

17.Descrivere il problema dei “lettori – scrittori” e la sua soluzione mediante un monitor.

Innanzitutto, un processo è lettore se esegue un’operazione di lettura su un insieme di dati, mentre è

detto scrittore se esegue un’operazione di scrittura su un insieme di dati. Esistono alcuni insiemi di dati

che possono essere condivisi da più processi. Ora se su un insieme di dati vengono effettuati più

processi lettori, non esistono problemi, mentre se un processo scrittore agisce su un dato insieme di

dati e contemporaneamente anche un altro processo (scrittore o lettore che sia) cerca di accedere allo

stesso insieme di dati, si genera una situazione caotica. Per evitare l’insorgere di questa situazione

caotica, è necessario che gli scrittori abbiano accesso esclusivo all’insieme di dati condiviso. Nasce

quindi un problema di sincronizzazione detto problema dei lettori – scrittori.

E’ facile intuire come esiste un vincolo di mutua esclusione tra i lettori e scrittori: un lettore può

accedere ad un area di memoria mentre uno scrittore lo sta modificando e uno scrittore non può

aggiornare una struttura dati che un lettore sta leggendo. La mutua esclusione va assicurata anche tra

diversi scrittori, che non possono modificare contemporaneamente lo stesso buffer, mentre,

ovviamente non è necessaria per i lettori, che possono accedere senza problemi alla stessa struttura dati

nello stesso istante. Le politiche di assegnazione della risorsa possono essere diverse. Supponiamo di

stabilire i seguenti vincoli: 1) un nuovo lettore non può impossessarsi della risorsa se c’è uno scrittore in

attesa; 2) al termine dell’operazione di scrittura, tutti i lettori sospesi hanno la precedenza sullo scrittore

successivo. Prima di scrivere la soluzione mediante monitor, definiamo delle variabili:

- num_lettori: numero lettori attivi sulla risorsa; - occupato: variabile booleana che indica se la risorsa è

occupata da uno scrittore; - ok_lettura, ok_scrittura: variabili condition su cui si mettono in attesa

rispettivamente lettori e scrittori.

Ecco di seguito riportato l’algoritmo risolutivo del sopradescritto problema:

type LETTORI_SCRITTORI=monitor

var num_lettori:integer; //Numero di processi lettori attivi sulla risorsa

occupato:boolean; //Indica se la risorsa è occupata da uno scrittore

ok_lettura,ok_scrittura:condition; //Variabili condition su cui si sospendono lettori

o scrittori

procedure entry Inizio_Lettura;

begin if occupato or ok_scrittura.queue then

ok_lettura.wait

num_lettori:=num_lettori+1;

ok_lettura.signal; //Sblocca un lettore in attesa e a catena si sbloccano anche gli

altri

end

procedure entry Fine_Lettura;

begin num_lettori:=num_lettori-1;

if num_lettori=0 then

ok_scrittura.signal //Sblocca uno scrittore in attesa solo se non ci sono più

lettori attivi

end

procedure entry Inizio_Scrittura;

begin if occupato or num_lettori<>0 then

ok_scrittura.wait;

occupato:=true; //Blocca la risorsa perché lo scrittore ha accesso

esclusivo

end

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

procedure entry Fine_Scrittura;

begin occupato:=false; //Sblocca la risorsa perché lo scrittore ha terminato

if ok_lettura.queue then

ok_lettura.signal

else ok_scrittura.signal;

end

Il monitor si inizializza ponendo num_lettori = 0 e occupato = false. La funzione cond.queue ci dice se

ci sono processi in attesa nella coda associata alla variabile cond di tipo condition. Ogni lettore, quando

viene sbloccato su ok_lettura.wait, libera subito un altro lettore: in questo modo si soddisfa il vincolo

2). Quando poi hanno finito tutti i lettori è sufficiente liberare un eventuale scrittore in attesa: per la

politica di gestione adottata, se non ci sono scrittori in attesa, non ci saranno neanche lettori. Il

problema dei lettori/scrittori si può dunque risolvere con tre strati SW: 1) Implementazione del

monitor generico con i suoi metodi; 2) implementazione della libreria di funzioni necessaria alla

risoluzione del problema specifico; 3) main che genera i lettori e scrittori, e usa la libreria del passo 2).

18. Descrivere il concetto di risorsa, i possibili attributi di una risorsa e la struttura di un

processo gestore di risorse.

Una risorsa si definisce come un qualunque oggetto, fisico o logico, di cui un processo necessita per

proseguire la sua evoluzione. Poiché un processo evolve eseguendo delle istruzioni su degli operandi,

una risorsa, fisica o logica, è u oggetto costituito da una struttura dati allocata in memoria su cui

operano delle procedure. Allocare una risorsa ad un processo significa renderla visibile e quindi

utilizzabile dal processo stesso. L’allocazione è statica quando un processo vede la risorsa per tutto il

tempo che intercorre tra la sua creazione e la sua terminazione; è dinamica se lo vede solo in certi

intervalli di tempo. In relazione al modo in cui viene allocata, una risorsa può essere:

dedicata: se è visibile in ogni istante da un solo processo;

condivisa: se è visibile da più processi contemporaneamente;

privata o locale: se è dedicata e allocata staticamente;

comune o globale: se è condivisa e/o allocata dinamicamente;

ad uso esclusivo: se è usata da un solo processo per volta.

Al concetto di risorsa è strettamente legato quello di gestore, che per le risorse fisiche è sempre un

componente del S.O., mentre per quelle logiche può anche essere un componente del programma

utente, o il programmatore stesso. Il gestore può regolare l’accesso dei processi alle risorse comuni,

garantendone il corretto utilizzo e risolvendo il problema della mutua esclusione, oppure eseguire le

varie operazioni sulle risorse per conto dei processi stessi. Quando il gestore non è il programmatore

ma un componente dell’elaborazione, esso può essere una risorsa condivisa o un processo. Nel modello

a memoria globale o comune, il gestore di fatto, è sempre una risorsa, mentre in quello a memoria

locale è sempre un processo. Nel modello a memoria locale (a scambio di messaggi) non esiste una

memoria comune e tutte le risorse sono, almeno dal punto di vista fisico, private, per cui non si pone il

problema della competizione per l’uso delle risorse e la cooperazione si realizza attraverso lo scambio di

messaggi con il gestore, che è anche detto processo servitore in quanto la sua funzione è proprio quella

di servire le richieste degli altri processi. Ogni risorsa, anche se logicamente comune, appartiene

fisicamente ad un solo processo, il processo gestore, che è l’unico ad averne visibilità diretta. Esso

riceve messaggi di richiesta dagli altri processi memorizzandoli in un’apposita struttura dati e li serve

secondo strategie opportune operando sulla risorsa per loro conto e fornendo, di volta in volta, le

risposte del caso. E’ anche possibile scindere in processi servitori distinti la politica di gestione della

risorsa dai meccanismi con cui si realizza. Le primitive messe a disposizione dal kernel per lo scambio

di messaggi tra processi sono di due tipi (send, receive) e si possono distinguere per il tipo di

sincronizzazione realizzato tra i processi comunicanti o per il modo in cui vengono individuate

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

destinazione e provenienza di un messaggio. Per quanto detto, questo modello si presta particolarmente

alla gestione dei sistemi distribuiti (e.g. reti di calcolatori) in cui le risorse fisiche sono per lo più private

per i vari processi (a seconda della macchina su cui si trovano).

19. Illustrare il concetto di separazione della politica di gestione di una risorsa da i possibili

meccanismi di gestione e come questa separazione possa essere realizzata da un gestore di

risorse di tipo processo.

Per politica di gestione di una risorsa si intende il criterio in base al quale, nel caso in cui più processi

richiedano di usufruire della stessa risorsa, si sceglie quale (processo) servire per primo e in che ordine

servire gli altri. Un meccanismo di gestione si può invece definire come una particolare soluzione logica

al problema della gestione di una risorsa, che può essere poi implementata a livello SW o HW. I

meccanismi usati nel modello a memoria locale (o scambio di messaggio) sono, ad esempio, le primitive

send e receive che si distinguono a loro volta per il tipo di sincronizzazione esistente tra i processi

comunicanti (send sincrona, asincrona, bloccante, receive bloccante, non bloccante) e per il modo in cui

si individua la provenienza o la destinazione di un messaggio (comunicazione diretta simmetrica, diretta

asimmetrica, indiretta). In questo modello come è noto, il gestore di risorse è un processo detto

processo servitore, che si occupa di comunicare, attraverso le primitive già citate, con i processi clienti,

dai quali riceve richieste di utilizzo della risorsa per poi rispondere in maniera opportuna ed

eventualmente soddisfarla operando per loro conto sulla risorsa stessa. Dopo questo schema, è facile

comprendere come la separazione della politica di gestione dai meccanismi di gestione della risorsa

possa essere semplicemente realizzata scindendo il processo servitore in due processi di cui uno (il

gestore propriamente detto) si occupa di scegliere l’ordine con cui vanno servite le varie richieste, a

seconda dei casi e dei tipi di risorsa, mentre l’altro ha il solo compito di operare direttamente sulla

risorsa, mettendo in atto la scelta fatta dal primo. In questo modo si possono applicare politiche di

gestione diverse dalla solita FIFO (e.g. LIFO oppure a priorità).

20. Mettere a confronto le possibili soluzioni realizzative di un gestore di risorse illustrandone

pregi e difetti.

Un gestore di risorse può avere il compito di regolare gli accessi dei processi alle risorse comuni,

garantendone il corretto utilizzo e risolvendo il problema della mutua esclusione per quelle ad uso

esclusivo o anche quello di operare sulla risorsa per conto dei processi stessi. Il gestore può essere il

programmatore o un componente dell’elaborazione (se la risorsa è fisica deve essere necessariamente

un componente del S.O.), in quest’ultimo caso il gestore può essere a sua volta una risorsa (e svolgere la

prima funzione di cui si è parlato) o processo (e svolgere la seconda funzione). La risorsa gestore è la

soluzione tipica del modello a memoria comune (o globale): le risorse comuni risiedono nella memoria

comune ai processi, i quali, interagiscono tra di loro per competere nell’accesso ad una risorsa ad uso

esclusivo o che comunque prevede un numero massimo di utilizzatori, oppure per cooperare

scambiandosi informazioni per mezzo di risorse comuni. La risorsa gestore è anch’essa comune a tutti i

processi e mette a loro disposizione delle procedure d’uso, di richiesta e rilascio, che, se richiamate,

permettono di virtualizzare una risorsa, cioè di far apparire privata ad un processo una risorsa che in

realtà è comune. Queste procedure operano ovviamente su una struttura dati del gestore che

memorizza lo stato della risorsa gestita e gli identificatori dei processi che la utilizzano o che hanno

richiesto di utilizzarla. Il processo gestore è invece la soluzione adottata nel modello a scambio di

messaggi (o a memoria locale): le risorse, anche quelle logicamente comuni, sono in realtà tutte private,

per cui ci può essere il problema della competizione tra i vari processi per l’accesso a risorse comuni

(che non esistono), mentre la cooperazione avviene attraverso scambio di messaggi col processo

gestore. Quest’ultimo, che è detto anche processo servitore, in quanto la sua funzione principale è

quella di ricevere richieste di utilizzo delle risorse da parte dei processi clienti, servendole quando

possibile, e di fornire eventualmente risposte, deve comprendere una struttura dati di gestione, che

memorizza lo stato della risorsa gestita e gli identificatori dei processi che si sta servendo o che

attendono di essere serviti, la struttura dati della risorsa gestita (privata per il gestore stesso) e le

procedure che, operando sulla struttura dati della risorsa, consentono di utilizzarla. Anche in questo

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

modello le risorse sono in un certo senso virtualizzate, perché ogni processo le vede come private, ma,

nella realtà dei fatti, esse non sono affatto comuni bensì private per il processo gestore. Il processo

cliente non deve preoccuparsi di testare lo stato delle risorse a cui vuole accedere, perché di queste si

occupa il server ma solo di comunicare col gestore mediante due fondamentali tipi di primitive messe a

disposizione dal kernel (send, receive), che si distinguono ulteriormente per il tipo di sincronizzazione

tra i processi comunicanti e per il modo in cui vengono determinate provenienza e destinazione di un

messaggio. Lo sforzo di programmazione, dunque, è forse minore in questo caso, poiché si limita

all’implementazione dei diversi protocolli di comunicazione possibili, ignorando la struttura dati di

gestione della risorsa, ma il modello per come è concepito (risorse tutte private), si presta più a gestire

un sistema distribuito (e.g. rete di calcolatori), in cui si può pensare di avere un SERVER con delle

risorse private e molti CLIENT che devono utilizzarle senza possederle, che a far funzionare un singolo

elaboratore, in cui tutte le risorse possono essere viste come comuni. Un vantaggio della soluzione con

processo gestore può essere, poi, la maggiore facilità con cui si riesce a realizzare la separazione tra

politiche e meccanismi di gestione delle risorse, per la quale basta dividere ogni processo servitore in

più processi, di cui alcuni operano direttamente sulle risorse mentre altri si occupano delle sole politiche

di gestione. Lo stesso risultato si può ottenere, nel modello a memoria globale, con meccanismi

complessi come i semafori privati o i monitor.

21. Illustrare le modalità di sincronizzazione possibili tra mittente e destinatario nel modello a

scambio di messaggio e l’algoritmo di una send asincrona.

Quando dei processi interagiscono fra loro, devono essere sincronizzati per garantire la mutua

esclusione, e hanno bisogno di scambiarsi info per cooperare. Un modo per soddisfare entrambi è lo

scambio di messaggi, che in più ha il vantaggio di un’implementazione semplice sia su sistemi

multiprocessore che monoprocessore. In questo modello ciascun processo dispone della propria

memoria locale, evolve in un ambiente proprio che non è comune ad altri processi. Ne segue che non è

possibile che i processi entrino in competizione su strutture dati condivise. Ne consegue, anche, che se

due processi devono interagire, non possono farlo tramite la memoria comune, ma solo tramite lo

scambio di messaggi attraverso il kernel del S.O.: ogni volta che un processo desidera ricevere

informazioni riguardo un altro, deve fare una richiesta al kernel. Le modalità di sincronizzazione che i

due processi adottano sono: send e receive nelle loro varie sfaccettature. La send è la primitiva di invio,

mentre la receive è la primitiva di ricezione. Le varie primitive send, receive si distinguono fra loro per

due motivi fondamentali: 1) il modo in cui i meccanismi di trasmissione e ricezione si sincronizzano tra

loro; 2) il modo in cui vengono designati il processo destinatario della send e il processo mittente della

receive. Tali primitive possono essere classificate così:

send asincrona: il processo mittente non attende la consegna del msg e continua nella propria

esecuzione; send bloccante: il processo mittente attende la trasmissione del msg sulla rete; send

sincrona: il processo mittente attende la consegna del msg al destinatario; receive bloccante: il

destinatario si blocca fino a quando non gli viene inviato il msg; receive non bloccante: il destinatario

prosegue comunque e gli viene segnalato se il msg è stato recapitato.

Una possibile implementazione della send asincrona è la seguente:

Var buca_post, buffer_liberi: mailbox;

flag: boolean;

procedure send_asinc(bica_post, mess, flag);

begin

flag = true;

if buca_post.contatore < 0 then

begin

<copia mess nel buffer di ricezione mes1 del primo processo proc in attesa di un msg>

<poni proc nella coda dei processi Ready>

end;

else if buffer_libero.contatore > 0 then

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

<copia mess in un buffer e collegalo a buca_post.primo>

else flag = false;

end.

Il tipo mailbox incontrato all’inizio del codice è implementabile attraverso un record con due campi:

contatore che è un intero che esprime il numero di elementi in coda alla mailbox e un campo primo di

tipo coda che esprime la coda dei msg nella mailbox o dei processi in attesa di msg nella stessa. La send

asincrona effettuata dal mittente consta di due parametri: l’indirizzo del buffer della propria area di

memoria il cui contenuto deve essere inviato al destinatario, e l’identificatore del destinatario. A questo

punto, il kernel accede all’area di memoria del mittente, copia il buffer indicato in un buffer della

propria area dati, e restituisce il controllo al mittente, il quale riscontra che il proprio è stato liberato. In

questa versione di send, il mittente invia il suo msg senza preoccuparsi dello stato del destinatario; a

tempo debito, il destinatario riceverà il msg senza interessarsi dello stato attuale del mittente. Il suo

vantaggio evidente è che ottimizza il parallelismo; tuttavia presenta anche degli svantaggi: trattandosi di

un meccanismo a basso livello, il cercare di realizzare schemi complessi è complicato. Inoltre, il kernel

dovrebbe avere un buffer illimitato, dato che il mittente potrebbe fare infinite send senza attendere

alcuna receive.

22. Illustrare le modalità di sincronizzazione possibili tra mittente e destinatario nel modello a

scambio di messaggio e l’algoritmo di una receive bloccante.

Quando dei processi interagiscono fra loro, devono essere sincronizzati per garantire la mutua

esclusione, e hanno bisogno di scambiarsi info per cooperare. Un modo per soddisfare entrambi è lo

scambio di messaggi, che in più ha il vantaggio di un’implementazione semplice sia su sistemi

multiprocessore che monoprocessore. In questo modello ciascun processo dispone della propria

memoria locale, evolve in un ambiente proprio che non è comune ad altri processi. Ne segue che non è

possibile che i processi entrino in competizione su strutture dati condivise. Ne consegue, anche, che se

due processi devono interagire, non possono farlo tramite la memoria comune, ma solo tramite lo

scambio di messaggi attraverso il kernel del S.O.: ogni volta che un processo desidera ricevere

informazioni riguardo un altro, deve fare una richiesta al kernel. Le modalità di sincronizzazione che i

due processi adottano sono: send e receive nelle loro varie sfaccettature. La send è la primitiva di invio,

mentre la receive è la primitiva di ricezione. Le varie primitive send, receive si distinguono fra loro per

due motivi fondamentali: 1) il modo in cui i meccanismi di trasmissione e ricezione si sincronizzano tra

loro; 2) il modo in cui vengono designati il processo destinatario della send e il processo mittente della

receive. Tali primitive possono essere classificate così:

send asincrona: il processo mittente non attende la consegna del msg e continua nella propria

esecuzione; send bloccante: il processo mittente attende la trasmissione del msg sulla rete; send

sincrona: il processo mittente attende la consegna del msg al destinatario; receive bloccante: il

destinatario si blocca fino a quando non gli viene inviato il msg; receive non bloccante: il destinatario

prosegue comunque e gli viene segnalato se il msg è stato recapitato.

Una possibile implementazione della receive bloccante è la seguente:

procedure receive_blocc(buca_post,mess);

begin

if buca_post.contatore > 0 then

<preleva un msg da buca_post.primo, copialo in mess e collega il buffer liberato a

buffer_liberi.primo>;

else begin

<poni il processo running in attesa in buca_post.primo>;

context_switch;

end;

end.

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

La receive bloccante è una system call caratterizzata da due parametri: l’indirizzo del buffer del

destinatario in cui il msg deve essere memorizzato, nome della mailbox. Poiché più mittenti possono

voler inviare messaggi ad uno stesso destinatario, può essere previsto uno spazio apposito nell’area di

memoria del kernel, che è la mailbox del destinatario in questione, nella quale i msg in arrivo vengono

sistemati in una coda. Il vantaggio di questa soluzione è l’attesa passiva del processo che attende un

messaggio, lo svantaggio consiste nell’impossibilità di memorizzare messaggi di tipo differente in una

stessa mailbox.

23. Illustrare le modalità di sincronizzazione possibili tra mittente e destinatario nel modello a

scambio di messaggio e l’algoritmo di una send sincrona.

Quando dei processi interagiscono fra loro, devono essere sincronizzati per garantire la mutua

esclusione, e hanno bisogno di scambiarsi info per cooperare. Un modo per soddisfare entrambi è lo

scambio di messaggi, che in più ha il vantaggio di un’implementazione semplice sia su sistemi

multiprocessore che monoprocessore. In questo modello ciascun processo dispone della propria

memoria locale, evolve in un ambiente proprio che non è comune ad altri processi. Ne segue che non è

possibile che i processi entrino in competizione su strutture dati condivise. Ne consegue, anche, che se

due processi devono interagire, non possono farlo tramite la memoria comune, ma solo tramite lo

scambio di messaggi attraverso il kernel del S.O.: ogni volta che un processo desidera ricevere

informazioni riguardo un altro, deve fare una richiesta al kernel. Le modalità di sincronizzazione che i

due processi adottano sono: send e receive nelle loro varie sfaccettature. La send è la primitiva di invio,

mentre la receive è la primitiva di ricezione. Le varie primitive send, receive si distinguono fra loro per

due motivi fondamentali: 1) il modo in cui i meccanismi di trasmissione e ricezione si sincronizzano tra

loro; 2) il modo in cui vengono designati il processo destinatario della send e il processo mittente della

receive. Tali primitive possono essere classificate così:

send asincrona: il processo mittente non attende la consegna del msg e continua nella propria

esecuzione; send bloccante: il processo mittente attende la trasmissione del msg sulla rete; send

sincrona: il processo mittente attende la consegna del msg al destinatario; receive bloccante: il

destinatario si blocca fino a quando non gli viene inviato il msg; receive non bloccante: il destinatario

prosegue comunque e gli viene segnalato se il msg è stato recapitato.

Var buca_post: mailbox;

procedure send_sinc(bica_post, mess, flag);

begin

if buca_post.contatore < 0 then

begin

<copia mess nel buffer di ricezione mes1 del primo processo proc in attesa di un msg>

<poni proc nella coda dei processi Ready>

end;

else

begin <poni il processo running in attesa in buca_post.primo>;

context_switch;

end;

end.

I parametri della send sincrona sono due: indirizzo del buffer della propria area di memoria il cui

contenuto deve essere inviato al destinatario e l’identificatore del destinatario. Quando il mittente

esegue una send viene effettuata una system call e interviene il kernel del S.O. A questo punto, si

presentano due alternative: il destinatario ha già eseguito una receive e quindi il mittente viene

temporaneamente sospeso attendendo il msg di avvenuta ricezione, ma poiché non vi è alcun ostacolo

l’operazione viene portata rapidamente a compimento con la liberazione dei due processi, oppure il

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

destinatario non ha ancora eseguito la receive e, quindi, il mittente viene sospeso finchè il destinatario

non effettua la receive. Uno dei vantaggi di questa soluzione è che non si pone il problema della

lunghezza del buffer del kernel e non vi è possibilità di perdita di msg. Lo svantaggio più evidente

consiste nella perdita di parallelismo, poiché il mittente deve aspettare che il destinatario abbia ricevuto

il msg prima di continuare la sua esecuzione.

24. Illustrare le modalità di sincronizzazione possibili tra mittente e destinatario nel modello a

scambio di messaggio e l’algoritmo di una receive non bloccante.

Quando dei processi interagiscono fra loro, devono essere sincronizzati per garantire la mutua

esclusione, e hanno bisogno di scambiarsi info per cooperare. Un modo per soddisfare entrambi è lo

scambio di messaggi, che in più ha il vantaggio di un’implementazione semplice sia su sistemi

multiprocessore che monoprocessore. In questo modello ciascun processo dispone della propria

memoria locale, evolve in un ambiente proprio che non è comune ad altri processi. Ne segue che non è

possibile che i processi entrino in competizione su strutture dati condivise. Ne consegue, anche, che se

due processi devono interagire, non possono farlo tramite la memoria comune, ma solo tramite lo

scambio di messaggi attraverso il kernel del S.O.: ogni volta che un processo desidera ricevere

informazioni riguardo un altro, deve fare una richiesta al kernel. Le modalità di sincronizzazione che i

due processi adottano sono: send e receive nelle loro varie sfaccettature. La send è la primitiva di invio,

mentre la receive è la primitiva di ricezione. Le varie primitive send, receive si distinguono fra loro per

due motivi fondamentali: 1) il modo in cui i meccanismi di trasmissione e ricezione si sincronizzano tra

loro; 2) il modo in cui vengono designati il processo destinatario della send e il processo mittente della

receive. Tali primitive possono essere classificate così:

send asincrona: il processo mittente non attende la consegna del msg e continua nella propria

esecuzione; send bloccante: il processo mittente attende la trasmissione del msg sulla rete; send

sincrona: il processo mittente attende la consegna del msg al destinatario; receive bloccante: il

destinatario si blocca fino a quando non gli viene inviato il msg; receive non bloccante: il destinatario

prosegue comunque e gli viene segnalato se il msg è stato recapitato.

Var buca_post, buffer_liberi:mailbox, flag: boolean;

procedure receive_non_blocc(buca_post,mess,flag);

begin

if buca_post.contatore > 0 then

begin

flag = true;

<preleva un msg da buca_post.primo, copialo in mess e collega il buffer liberato a

buffer_liberi.primo>;

end;

else flag = false;

end;

end.

Quando si esegue questa system call il destinatario non viene bloccato anche se non c’è nessun msg

disponibile. Questo tipo di receive serve per realizzare un polling di mailbox. Supponiamo che un

processo abbia la possibilità di attingere da più mailbox, è evidente che l’uso di una receive non

bloccante è consigliato poiché è inutile rimanere bloccato il destinatario su di una mailbox quando il

msg potrebbe arrivare in un’altra mailbox. Per esigenze di programmazione, potrebbe essere necessario

fare in modo che un processo ricevente si blocchi in seguito ad una receive e fino a quando giunge un

msg; per rendere possibile questo in S.O. che implementano la receive non bloccante, si fa così: il

processo effettua la receive e se il risultato è negativo si blocca su di un semaforo temporale (un

semaforo che automaticamente diventa verde dopo un certo intervallo di tempo). Quando viene

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

risvegliato, il processo riesegue la receive non bloccante, la quale restituirà ogni volta un parametro che

indica se il buffer è pieno o vuoto.

25. Illustrare le modalità di sincronizzazione possibili tra mittente e destinatario nel modello a

scambio di messaggio e l’algoritmo di una send asincrona che impiega una delle modalità di

identificazione del destinatario illustrate.

Quando dei processi interagiscono fra loro, devono essere sincronizzati per garantire la mutua

esclusione, e hanno bisogno di scambiarsi info per cooperare. Un modo per soddisfare entrambi è lo

scambio di messaggi, che in più ha il vantaggio di un’implementazione semplice sia su sistemi

multiprocessore che monoprocessore. In questo modello ciascun processo dispone della propria

memoria locale, evolve in un ambiente proprio che non è comune ad altri processi. Ne segue che non è

possibile che i processi entrino in competizione su strutture dati condivise. Ne consegue, anche, che se

due processi devono interagire, non possono farlo tramite la memoria comune, ma solo tramite lo

scambio di messaggi attraverso il kernel del S.O.: ogni volta che un processo desidera ricevere

informazioni riguardo un altro, deve fare una richiesta al kernel. Le modalità di sincronizzazione che i

due processi adottano sono: send e receive nelle loro varie sfaccettature. La send è la primitiva di invio,

mentre la receive è la primitiva di ricezione. Le varie primitive send, receive si distinguono fra loro per

due motivi fondamentali: 1) il modo in cui i meccanismi di trasmissione e ricezione si sincronizzano tra

loro; 2) il modo in cui vengono designati il processo destinatario della send e il processo mittente della

receive. La primitiva send richiede di specificare quale processo deve ricevere il msg; analogamente

molte implementazioni permettono al processo ricevente di specificare il mittente del msg da ricevere.

Gli schemi per la realizzazione delle primitive send e receive sono due: indirizzamento diretto e

indiretto. Con l’indirizzamento diretto, la primitiva send contiene il pid del destinatario. La receive si

può gestire in due modi: si richiede di indicare esplicitamente il pid del mittente (comunicazione diretta

simmetrica), oppure di esplicitare nella receive come parametro di uscita il pid del mittente

(comunicazione diretta asimmetrica). L’altro approccio è l’indirizzamento indiretto, nel quale, i msg non

viaggiano direttamente dal mittente al destinatario ma sono inviati ad una struttura dati condivisa

(mailbox) che si compone di code che contengono temporaneamente i msg, finché un processo non ne

preleva qualcuno. Utilizzando il metodo di indirizzamento indiretto, l’algoritmo di una send asincrona

può essere il seguente:

var pid: integer /* pid del destinatario */, buca_post, buffer_liberi: mailbox, flag: boolean;

procedure send_asinc(buca_post, mess, pid, flag);

begin

flag = true;

if buca_post.contatore < 0 then

begin

< copia mess e pid nel buffer di ricezione mess1 del primo processo proc in attesa di un msg>;

<poni proc nella coda dei processi Ready>;

end;

else if buffer_liberi.contatore > 0 then

<copia mess e pid in un buffer e collegalo a buca_post.primo>;

else flag =false;

end;

end.

26. Illustrare le modalità di sincronizzazione possibili tra mittente e destinatario nel modello a

scambio di messaggio e l’algoritmo di una send sincrona che impiega una delle modalità di

identificazione del destinatario illustrate.

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

Quando dei processi interagiscono fra loro, devono essere sincronizzati per garantire la mutua

esclusione, e hanno bisogno di scambiarsi info per cooperare. Un modo per soddisfare entrambi è lo

scambio di messaggi, che in più ha il vantaggio di un’implementazione semplice sia su sistemi

multiprocessore che monoprocessore. In questo modello ciascun processo dispone della propria

memoria locale, evolve in un ambiente proprio che non è comune ad altri processi. Ne segue che non è

possibile che i processi entrino in competizione su strutture dati condivise. Ne consegue, anche, che se

due processi devono interagire, non possono farlo tramite la memoria comune, ma solo tramite lo

scambio di messaggi attraverso il kernel del S.O.: ogni volta che un processo desidera ricevere

informazioni riguardo un altro, deve fare una richiesta al kernel. Le modalità di sincronizzazione che i

due processi adottano sono: send e receive nelle loro varie sfaccettature. La send è la primitiva di invio,

mentre la receive è la primitiva di ricezione. Le varie primitive send, receive si distinguono fra loro per

due motivi fondamentali: 1) il modo in cui i meccanismi di trasmissione e ricezione si sincronizzano tra

loro; 2) il modo in cui vengono designati il processo destinatario della send e il processo mittente della

receive. La primitiva send richiede di specificare quale processo deve ricevere il msg; analogamente

molte implementazioni permettono al processo ricevente di specificare il mittente del msg da ricevere.

Gli schemi per la realizzazione delle primitive send e receive sono due: indirizzamento diretto e

indiretto. Con l’indirizzamento diretto, la primitiva send contiene il pid del destinatario. La receive si

può gestire in due modi: si richiede di indicare esplicitamente il pid del mittente (comunicazione diretta

simmetrica), oppure di esplicitare nella receive come parametro di uscita il pid del mittente

(comunicazione diretta asimmetrica). L’altro approccio è l’indirizzamento indiretto, nel quale, i msg non

viaggiano direttamente dal mittente al destinatario ma sono inviati ad una struttura dati condivisa

(mailbox) che si compone di code che contengono temporaneamente i msg, finché un processo non ne

preleva qualcuno. Utilizzando il metodo di indirizzamento indiretto, l’algoritmo di una send sincrona

può essere il seguente:

var pid: integer /* pid del destinatario */, buca_post: mailbox;

procedure send_sinc(buca_post, mess, pid, flag);

begin

if buca_post.contatore < 0 then

begin

< copia mess e pid nel buffer di ricezione mess1 del primo processo proc in attesa di un msg>;

<poni proc nella coda dei processi Ready>;

end;

else

begin

<metti il processo running in attesa in buca_post.primo>;

context_switch;

end;

end.

27. Mettere a confronto, elencandone vantaggi e svantaggi, la tecnica di scambio di messaggio

mediante mailbox e quella che prevede che il destinatario riceva con il messaggio

l’identificatore del mittente.

La differenza sostanziale tra lo scambio di messaggi tra due processi tramite una mailbox e tramite il

passaggio del pid del mittente insieme al messaggio sta nel fatto che nella prima non c’è una interazione

vera e propria tra i due processi mentre nella seconda soluzione i due processi “lavorano” a stretto

contatto. Il vantaggio più evidente dell’uso dell’indirizzamento indiretto (scambio di messaggi tramite

mailbox) è che, separando il mittente e il ricevente, permette una maggiore flessibilità nell’uso dei

messaggi. Inoltre si ha un incremento di parallelismo dato che più processi possono inviare più

messaggi alla mailbox senza creare problemi di ricezione per i destinatari. Uno dei svantaggi più

evidenti riguarda il possesso della mailbox stessa: nella maggior parte dei casi la mailbox per un sistema

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

client/server, detta nello specifico “porta”, appartiene al processo ricevente ed è, quindi, facile capire

che se si termina questo processo, viene distrutta anche la porta (mailbox) impossibilitando l’invio e il

recapito dei messaggi. Tale inconveniente, nella seconda soluzione che prevede che il destinatario riceva

con il messaggio il pid del mittente, è del tutto assente visto che i due processi si sincronizzano per

scambiarsi i messaggi in modo autonomo senza l’utilizzo di terze strutture.

28. Descrivere l’implementazione delle procedure send e receive di tipo sincrono mediante

primitive asincrone.

Delle cinque primitive fondamentali (send asincrona, send sincrona, send bloccante, receive bloccante,

receive non bloccante), le due tipicamente messe a disposizione dai S.O. sono la send asincrona e la

receive bloccante. Volendo comunque disporre anche di send e receive sincrone, si può pensare di

poterle realizzare mediante primitive asincrone. In realtà il risultato da ottenere è che, una volta che il

messaggio sia passato dal mittente al destinatario, i due processi siano subito pronti a partire insieme,

ossia siano resi ready dal kernel. In presenza di una send asincrona e di una receive bloccante ciò può

avvenire solo se la receive precede sempre la send; in tal modo il destinatario si blocca sulla receive e

nel momento in cui il mittente esegue la send asincrona, il kernel (vedendo il destinatario in attesa)

manda il messaggio dal buffer del mittente a quello del destinatario e subito sblocca i due. A tale scopo

è fondamentale assicurarsi che, quando il mittente esegue una send, il destinatario abbia a sua volta già

eseguito una receive. Il problema viene risolto con l’introduzione di due messaggi: “pronto ad inviare” e

“pronto a ricevere”. In particolare il “pronto ad inviare” viene effettuato dal ricevente, mentre il

“pronto a ricevere” viene effettuato dal mittente. Gli algoritmi che realizzano la send e la receive

sincrone, mediante primitive asincrone possono essere implementate come di seguito:

procedure send_sincrona(buca_post, mess)

begin

send_asincrona(buca1_post, mess1);

/* mess1 è un msg di “pronto ad inviare” */

receive_bloccante(buca2_post, mess2);

/* mess2 è un msg di “pronto a ricevere” */

send_asincrona(buca_post, mess);

end.

Procedure receive_bloccante_sincrona(buca_post, mess)

Begin

receive_bloccante(buca1_post, mess1);

send_asincrona(buca2_post, mess2);

receive_bloccante(buca_post, mess);

end.

29. Illustrare l’algoritmo di scheduling della CPU Shortest Process First e quello usato da

Unix.

L’entità del S.O. che si occupa di eseguire gli algoritmi di scheduling della CPU è lo schedulatore a

breve termine (CPU scheduler). Questo componente interviene nel momento in cui un processo passa

fra gli stati running e waiting, oppure quando termina definitivamente la propria esecuzione, o ancora

nei sistemi time-sharing in caso di prerilascio. Gli algoritmi di scheduling della CPU hanno lo scopo di

migliorare il throughput (numero di lavori per unità di tempo), turnaround (tempo di attesa relativo ai

lavori batch), tempo di attesa (la quantità di tempo che un processo deve aspettare nella coda di una

certa risorsa) e tempo di risposta (tempo che passa tra l’input e il primo carattere di output). Lo SJF è

un algoritmo di scheduling della CPU basato sul concetto di priorità, legato alla quantità di tempo di

utilizzo della risorsa da parte del processo. Nella fattispecie, il processo che usufruirà della CPU sarà

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

quello che impegnerà per il minor tempo la CPU stessa. Tale soluzione presenta, però, un notevole

problema: quello di dover preconoscere il tempo di utilizzo di una risorsa per ciascun processo in attesa

sulla medesima. Di questo tempo, di solito, se ne fa una stima tramite la media esponenziale:

Tn+1 = A* tn + (1-A)*Tn , dove tn è il tempo effettivo di utilizzo della CPU (CPU burst), Tn è una

stima di tale CPU burst; A è un parametro che varia tra 0 e 1. Quando un processo va in esecuzione,

occupa la CPU per qualche istante, dopodiché se mette in attesa sul semaforo di una risorsa. Se il

processo è I/O bound, sarà caratterizzato da CPU burst brevi. Viceversa se il processo è CPU burst,

monopolizzerà la CPU per parecchio tempo e potrà essere interrotto solo grazie ad un timer. Per

esempio, geniale è la soluzione di UNIX: nel descrittore di ogni processo è presente un contatore,

incaricato di contare il tempo durante il quale il processo è running (tale contatore viene incrementato

ogni 20 ms da un Daemon). Un secondo contatore, situato sempre nel medesimo descrittore, viene

incrementato ogni secondo, ma periodicamente viene dimezzato, indipendentemente dal fatto che il

processo sia running o meno. Ne deriva che avere un valore piccolo di questo secondo contatore

significa che ultimamente il processo ha usato poco la CPU e quindi cicli di CPU burst molto brevi,

diventando I/O bound. A tali processi si assegna una priorità elevata; se invece il valore del secondo

contatore è alto, significa che gli ultimi CPU burst sono stati lunghi e quindi a tali processi va attribuita

una priorità bassa.

30. Illustrare le modalità di sincronizzazione del processo che esegue un driver con l’attività

svolta dalla relativa periferica.

Un Driver è una particolare unità di programma che dirige a basso livello le operazione di I/O. Si può

pensare che esso sia un processo del kernel del S.O.; di conseguenza, il processo driver può essere

eseguito solo attraverso una SVC. Un’altra possibilità, è che il driver sia eseguito nel contesto di un

processo specifico, detto processo Driver, al quale un processo utente, che desidera effettuare

un’operazione di I/O, invia un messaggio mediante apposite procedure del kernel del S.O.

Successivamente il processo utente si metterà in attesa che il driver esegua il proprio compito, il quale

spedirà un messaggio al processo sospeso. Su di una macchina nella quale il processo driver è parte del

kernel del S.O. esiste uno stretto legame tra le istruzioni del driver stesso e del kernel. Nel momento in

cui arriva un’interruzione al driver sospeso, parte una ISR contenente la routine del driver specifica per

quella richiesta di I/O. I S.O. per i quali si adotta questa tecnica devono essere rigenerati ad ogni

aggiunta di nuove periferiche (questo è il caso d UNIX). In S.O., in cui un’operazione di I/O lancia un

processo driver, quest’ultimo deve attendere che venga iinviato un segnale di interrupt dalla periferica

da esso controllata, mettendosi in attesa mediante una wait su di un semaforo inizializzato a zero.

All’arrivo della interruzione parte una ISR che, a sua volta, effettua una signal sbloccando il driver.

Questa seconda soluzione è a volte preferita per il motivo della sua maggiore leggerezza: infatti, nel

caso di aggiunta di una periferica nuova bisogna soltanto “caricare” il driver nella fase di boot, senza

modificare il S.O. (è il caso della famiglia MS Windows). Ogni driver, a prescindere dall’ambiente in cui

si trova (utente o Kernel), ha sempre bisogno di una procedura del Kernel mediante la quale possa

sospendersi una volta che sia iniziata l’operazione di I/O. Ad esempio, il driver chiede un dato alla

periferica e poi si mette in attesa fin quando non lo riceve. La particolare procedura del Kernel che

viene eseguita in questo caso è detta WAIT FOR INTERRUPT. Nel modello in cui il processo driver è

direttamente accessibile agli altri processi, essa viene implementata a mezzo di una wait su un semaforo

privato del driver. Per uscire da questa wait, occorre trasformare l’interrupt HW, che arriva dalla

periferica, in una SWI che sblocca il driver. A tal fine, basta inserire una signal nel relativo ramo della

ISR. Anche nel caso di un driver gestito a livello Kernel, la ISR avrà tanti rami quanti sono i driver, ma

questa volta ogni ramo contiene direttamente la routine del driver: tale routine comincia le operazioni

di I/O e poi si autosospende, per riprendere dopo che è arrivato l’interrupt dalla periferica.

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

31. Descrivere il concetto di virtualizzazione di una periferica e come la virtualizzazione si

implementata da un S.O.

La virtualizzazione di una risorsa consiste nel fare apparire privata una risorsa comune. Data una risorsa

e più processi che la condividono, è immediato comprendere che per una corretta competizione è

necessario che le procedure di accesso vengano eseguite in mutua esclusione. Si indica, a tal proposito,

col termine sezione critica una sequenza di istruzioni che devono essere eseguite in modo mutuamente

esclusivo con altre sezioni critiche. A tal fine basta associare alla struttura dati che rappresenta la risorsa

un semaforo inizializzato a 1, e far precedere e seguire ogni sezione critica da una wait e una signal su

tale semaforo; in questo modo un solo processo per volta potrà trovarsi all’interno della sezione critica.

Detti Richiesta e Rilascio le procedure della risorsa gestore, è possibile virtualizzare per i processi utenti

la risorsa gestita definendo, per ogni possibile procedura d’uso proc_uso della risorsa, una procedura

proc_uso_virtuale in questo modo:

procedure proc_uso_virtuale

begin

richiesta;

proc_uso; /* procedura d’uso reale */

rilascio;

end.

32. Descrivere la funzione dello swapper o schedulatore a medio termine in un S.O.

Tra i vari tipi di scheduling esiste lo schedulatore a medio termine, il cui nome si riferisce alla frequenza

relativa con cui le funzioni sono eseguite. Lo scheduling a medio termine è una parte della funzione di

trasferimento sul disco dei processi, infatti si decide di aggiungere un processo a quelli che sono

parzialmente nella memoria principale e perciò pronti ad essere eseguiti. Generalmente, la decisione di

introdurre un processo in memoria (swap in) è basata sulla necessità di gestire il gradi di

multiprogrammazione. La decisione di trasferire un processo in memoria considererà lo spazio di

memoria che un processo può occupare. Tale tecnica consiste nel lavorare con un quantitativo di

processi attivi maggiore di quello che potrebbe essere consentito con le tradizionali tecniche dì gestione

della memoria. Se il kernel ha un certo numero di processi aperti, ma non c’è abbastanza spazio in

memoria centrale, alcuni di essi vengono spostati nella memoria di massa; tale spostamento viene

chiamato swapping. Ad esempio, un processo può essere svuotato in memoria di massa quando si

mette in attesa del completamento di un’operazione di I/O: questa è l’operazione di swap-out. I

processi ready dovrebbero trovarsi tutti in memoria centrale per velocizzare al massimo il loro

passaggio a running. Ovviamente se deve essere eseguito un processo residente in memoria di massa

occorre dapprima effettuare lo swap-in di tale processo in memoria centrale e contemporaneamente lo

swap-out di un processo residente in memoria centrale, affinché quest’ultima si liberi. Anche Unix

utilizza lo swapping per consentire che i processi non risiedano in memori di massa in alcune fasi: un

processo viene swappato su disco se chiede memoria dopo una fork, se cerca di espandere la propria

area dati oppure se il suo stack supera lo spazio riservato. Tale swapping viene effettuato dal Daemon

Swapper; quest’ultimo interviene ogni pochi secondi per effettuare lo swap-in dei processi pronti ad

essere inseriti nella cosa dei Ready cominciando da quello residente da più tempo. Lo swap-out dei

processi viene invece effettuato a partire da quelli meno prioritari e quindi residenti da più tempo su

disco. Lo Swapper si arresta in due casi: 1) Non ci sono più processi pronti su disco (Ready); 2)Non è

possibile effettuare swap-out.

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

33. Descrivere la tecnica della gestione della memoria a partizioni variabili evidenziandone i

difetti e motivando perché tale tecnica è idonea alla gestione di una partizione di disco

dedicata a fungere da area swap.

La gestione della memoria a partizioni variabili rientra in quelle tipologie di gestione della memoria che

prevedono che l’immagine di un processo in stato running sia caricata completamente in memoria

centrale (nel qual caso corrisponde soltanto alla RAM). La tecnica a partizioni variabili prevede che il

numero delle partizioni (fette di memoria) venga determinato dinamicamente a seconda delle esigenze

dell’utente. In tal caso questo numero sarà legato alla quantità di processi che è necessario mantenere

nello stesso tempo in memoria e dalle esigenze in termini di spazio di memoria di ciascuno di essi. Un

caso banale di questa tecnica è l’allocazione con partizione singola. In questo modello il S.O. risiede

nella “memoria bassa” ed un singolo processo utente è in esecuzione, all’interno della propria

partizione, nella “memoria alta”. Il problema più immediato di questa tecnica è che si potrebbe avere

una sovrapposizione dell’area di memoria occupata dal S.O. da parte della partizione del processo

utente, ma si può facilmente risolvere mediante l’uso di un opportuno registro base e di un registro

limite di memoria. Invece, la tecnica più usata oggi è quella a partizioni variabili multiple: ovvero, a

ciascun processo viene associata una partizione di memoria ad indirizzi consecutivi, in modo che vi

possano essere contenuti codice, stack, e dati del processo stesso. La traduzione degli indirizzi logici in

quelli fisici viene fatta tramite un registro base in questo modo: se ind. Logico < Reg. Limite allora ind.

Fisico = Reg. base + ind. Logico, altrimenti il processo va in ABORT. Dato che non c’è ordine di

terminazione dei processi, in memoria possono rimanere dei “buchi” (partizioni vuote), lasciate dai

processi che terminano aleatoriamente. Le tecniche di gestione delle partizioni vuote sono tre:

FIRST FIT – alloca il primo buco sufficientemente grande. Viene allocata al processo la prima

partizione che può contenerlo; la ricerca non onerosa dato che non si scandiscono tutte le partizioni

vuote. BEST FIT – alloca il più piccolo buco capace di contenere il processo. La ricerca va effettuata su

tutta la lista e poi si sceglie quella più piccola. WORST FIT – alloca la fetta più grande, ricercandola in

tutta la lista delle partizioni. Tale strategia produce le partizioni più grandi del processo stesso con la

speranza di lasciare spazio abile per “arruolare” l’immagine di un altro processo. Il primo criterio tende

a far perdere meno tempo, il secondo a ridurre gli spazi vuoti, mentre l’ultimo tende a lasciare più

spazio libero per altri eventuali processi. La tecnica a partizioni variabili soffre di frammentazione

interna, dovuta al fatto che un processo potrebbe occupare un buco che è di poco più grande rispetto al

processo stesso, e lo spazio che rimane è troppo piccolo per essere gestito dato che la sua gestione

richiederebbe più spazio del buco stesso. Inoltre soffre di frammentazione esterna, ovvero della

frantumazione dello spazio libero di memoria in piccole fette inutilizzabili. Può succedere cioè che non

sia possibile allocare memoria ad un processo, dato che non c’è al momento un “buco” abbastanza

grande, nonostante il fatto che il totale della memoria libera sia sufficiente per le esigenze del processo

in questione. Per risolvere il problema della frammentazione esterna si può utilizzare un sistema di

compattazione (Garbage Collector) che recupera lo spazio riorganizzando la disposizione dei processi

in memoria. In pratica questo sistema accorpa i vari “buchi” liberi in un unico spazio vuoto. Questa

tecnica è adottata alla gestione di un’area di swap, poiché mediante un canale DMA (direct memory

access) si può gestire, in modo indipendente dalla CPU, il passaggio dei processi da RAM a HDD e Da

HDD a RAM ad indirizzi diversi: in poche parole i processi vengono presi dalla memoria e swappati su

disco e poi da disco vengono portati in memoria in altre locazioni, risistemando la dislocazione delle

immagini dei processi nella RAM. Questa tecnica si può applicare solo se il programma in questione è

rilocabile, ovvero espresso mediante indirizzi relativi, in pratica è impossibile applicare la compattazione

se l’allocazione del programma viene fatta in fase di compilazione, assemblaggio o caricamento.

Un’alternativa alla compattazione consiste nel disporre di più registri base, in modo che uno stesso

programma possa essere suddiviso in memoria in più parti, ad esempio allocando l’area di programma,

l’area stack, e l’area dati in punti differenti della RAM. In questo caso, però, bisogna fare uso dei registri

speciali, detti registri Fence, che servono ad impedire che nella fase di mapping un indirizzo possa

“fuoriuscire” dall’area associata al processo.

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it

34. Illustrare la tecnica della gestione della memoria a pagine, i possibili supporti HW che un

processore deve rendere disponibili per la sua realizzazione ed il meccanismo di protezione

utilizzato.

La tecnica della gestione a pagine consiste nel suddividere la memoria fisica in blocchi di dimensioni

fisse, detti FRAME, e la memoria logica in blocchi di uguale dimensione detti pagine. Quando un

processo deve essere eseguito le sue pagine vengono caricate nei frame della memoria. Ogni indirizzo

generato dalla CPU è diviso in due parti: un numero di pagina (p) e un offset di pagina (d). Il primo

serve da indice per la tabella delle pagine, che contiene l’indirizzo di ogni pagina nella memoria fisica.

L’insieme di questo numero di pagina e dell’offset di pagina permette di definire l’indirizzo

dell’informazione desiderata nella memoria fisica, mediante il seguente supporto HW: si legge il numero

di pagina dell’indirizzo logico, si accede al corrispondente indirizzo nella tabella delle pagine, si preleva

l’indirizzo fisico, il quale viene giustapposto all’offset per formare l’indirizzo vero e proprio. Dal punto

di vista pratico, il mapping viene eseguito a tempo di esecuzione (dinamicamente) mediante un

dispositivo HW che ricava la pagina fisica da quella logica. Questa tecnica è possibile, però, sole se le

pagine fisiche sono disgiunte (non sovrapposte). In sistemi meno recenti, il componente incaricato di

sostituire l’indice di pagina logica con l’indirizzo di pagina fisica era realizzato da una batteria di registri

contenenti le corrispondenze fra pagine logiche e fisiche; esso era detto MMU, il quale ad ogni

context_switch veniva caricato con dei nuovi valori. I registri della batteria sono tanti quanto deve

essere lunga la tabella delle pagine. Se le pagine non sono disgiunte il problema va risolto all’interno

della CPU; in questa soluzione la tabella delle pagine è contenuta nella memoria stessa, e l’HW è ridotto

ad un solo registro speciale del processore che punta in memoria alla posizione di tale tabella. Per

ottenere quindi l’indirizzo di un frame occorre sommare al contenuto di questo registro l’indirizzo della

pagina richiesta e accedere in memoria all’indirizzo che ne consegue. Ogni processo possiede una

propria tabella delle pagine, quindi al cambiare del processo running cambia dinamicamente il

contenuto del registro, il quale punterà così ad un’altra tabella. Lo svantaggio evidente di questa

alternativa sta nel suo richiedere degli accessi supplementari in memoria, la quale, come è noto,

comporta tempi di accesso più lunghi rispetto ai registri HW dedicati. D’altro si ha il vantaggio di

eliminare il limite fisico per quanto riguarda il numero di pagine occupabili, eccetto ovviamente quello

della dimensione fisica della memoria. Una soluzione intermedia è quella della memoria associativa: una

memoria nella quale l’accesso avviene per chiave e non per indirizzo. Quando ai registri associativi si

presenta un elemento, esso viene confrontato contemporaneamente con tutte le chiavi; nella colonna

“chiave” figureranno le pagine logiche e nella colonna “dato” quelle fisiche. La ricerca è estremamente

veloce ma il costo è elevato. Tuttavia la memoria associativa può essere utilizzata per contenere solo

una parte della tabella delle pagine; nel migliore dei casi la chiave richiesta sarà presente in uno dei

registri associativi e verrà restituito l’indirizzo del corrispondente frame. In caso contrario non resta che

rivolgersi alla tabella completa situata in memoria centrale. Il massimo della velocità si ha costruendo un

dispositivo HW che ricerca contemporaneamente sia nella memoria associativa che nella memoria

centrale: se la chiave viene trovata nella memoria associativa si manda un segnale di abort alla ricerca in

memoria centrale, se non viene trovata si continua con la ricerca (più lenta) che accede alla memoria

principale. La protezione della memoria è garantita dal metodo in sé; infatti non può verificarsi

un’invasione verso altra pagine, poiché le dimensioni di pagina logica e fisica sono uguali. L’unico

registro Fence di protezione occorrente è quello che impedisce all’indice di pagina logica di fuoriuscire

dalla tabella delle pagine presente in memoria centrale. Inoltre questa tecnica non presenta

frammentazione esterna (le pagine sono più piccole dell’immagine di processo), ma denuncia una forte

frammentazione interna (le pagine sono più grandi dell’immagine di processo), in quanto mediamente

l’ultima pagina di ogni processo è occupata per metà.

Quelli di informatica www.quellidiinformatica.tk - Scaricato da www.cplusplus.it


ACQUISTATO

4 volte

PAGINE

40

PESO

349.29 KB

AUTORE

Menzo

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Menzo 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à Napoli Federico II - Unina o del prof Cotroneo 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 Sistemi operativi

Sistemi operativi - Appunti
Appunto
Sistemi operativi - Problema dei produttori e dei consumatori
Appunto
Sistemi operativi - Esercitazioni varie Linux
Esercitazione
Sistemi operativi - Implementazione programma in C
Appunto