Prog1999 < Lab_so_1/AL

Tags: view all tags

<html>
<body>

<h1>
<font size=+2>Laboratorio II: Sistemi Operativi - a.a. 1999/2000</font></h1>
<b><blink><font size=+1>La consegna va effettuata entro il 24 gennaio 2000
(nuova consegna 9 marzo 2000)</font></blink></b>
<p><b><font size=+1>Scambio di messaggi a lunghezza variabile</font></b>
<p><b><font size=+1>Introduzione</font></b>
<p>Un messaggio e' una stringa di al piu' 200 caratteri. I messaggi vengono
scambiati da un insieme di processi (<i>thread</i>) mediante un buffer
condiviso con capacita' massima di 200 caratteri. Le sole operazioni consentite
sul buffer sono quelle di put e get, mediante le quali e' possibile rispettivamente
inserire ed estrarre messaggi dal buffer secondo una opportuna politica
(vedi sotto). In particolare,
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; - <b>put</b>: un processo
P che voglia scrivere un messaggio msg nel buffer B esegue B.put(msg);
se al momento dell'esecuzione non vi e' in B spazio sufficiente per contenere
msg, P viene messo in attesa che un processo destinatario estragga un messaggio
(mediante una get), liberando cosi' spazio in B.
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; - <b>get</b>: viene eseguita
da un processo P che voglia leggere un messaggio dal buffer. Se B e' correntemente
vuoto, P viene messo in attesa che un mittente ne depositi uno (mediante
una put); a completamento dell'operazione, un messaggio viene estratto
da B e restituito come valore dell'espressione B.get().
<p>Diverse scelte sono possibili nella gestione dei processi in attesa
di accedere al buffer (mittenti con buffer pieno o destinatari con buffer
vuoto). La piu' semplice e' la gestione <i>elementare</i> (mancanza di
politica): quando viene liberato spazio nel buffer a seguito di una get,
uno a caso tra i processi mittenti eventualmente in attesa (e il cui messaggio
non superi in lunghezza lo spazio disponibile) viene riattivato (ed analogamente
per l'attesa dei processi destinatari). Questa politica non impedisce l'<b>attesa
indefinita</b> dei processi, cioe' non e' possibile stabilire un limite
superiore al tempo che un generico processo potrebbe aspettare per accedere
al buffer.
<p>In alternativa, la politica FIFO, in cui i processi in attesa vengono
gestiti attraverso una coda first-in-first-out, elimina il problema dell'attesa
indefinita, ma introduce la possibilita' di attese non necessarie: un processo
mittente il cui messaggio superi in lunghezza lo spazio correntemente disponibile
blocchera' tutti i processi che, sebbene arrivati piu' tardi, intendono
tuttavia scrivere un messaggio sufficientemente corto da poter entrare
nel buffer, e che potrebbero percio' proseguire.
<p>L'efficienza di una politica di accesso al buffer puo' essere misurata
in base al tempo medio di attesa di un processo per completare le operazioni
di lettura e scrittura. In un programma di simulazione, lo scorrere del
tempo puo' essere espresso in modo virtuale in termini dell'occorrenza
di <i>eventi</i>. Nel nostro caso e' ragionevole scegliere come nozione
di evento l'invocazione da parte di un qualunque processo di una operazione
sul buffer. Dunque, un processo impieghera' una unita' di tempo ad eseguire
una operazione (put o get) se questa non comportera' attesa; se pero' questa
comporta un'attesa durante la quale si registrino altri n accessi al buffer
(non necessariamente completati), allora il tempo virtuale di esecuzione
dell'operazione sara' di n+1.
<p>Va notato che il tempo medio di attesa puo' anche essere influenzato
dalla politica scelta per il consumo dei messaggi memorizzati nel buffer.
Maggiore efficienza puo' derivare dall'estrarre i messaggi in ordine decrescente
di lunghezza, in modo da liberare sempre il maggior spazio possibile. Questo
tuttavia non garantisce che, una volta scritto, un messaggio venga necessariamente
letto con la conseguente attesa indefinita del messaggio nel buffer, che
va evitata.
<h3>
Scopo del progetto</h3>
Lo scopo del progetto e' lo studio e la realizzazione in Java di un simulatore
per l'analisi di politiche di accesso ad un buffer a capacita' limitata
condiviso fra processi destinatari e mittenti che si scambiano messaggi
a lunghezza variabile. In particolare, si richiede di:
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1. Realizzare il tipo di
dato astratto buffer (struttura dati e operazioni put e get) con gestione
elementare dei processi in attesa.
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2. Realizzare due politiche
di gestione dei processi che evitino l'attesa indefinita. Come prima politica
si puo' adottare la politica FIFO. Nella seconda si dovrebbe sperimentare
una tecnica piu' sofisticata che riduca, ad esempio, il numero delle attese
inutili.
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3. Realizzare un programma
simulatore che lanci un insieme di processi destinatari e mittenti che
interagiscono sul buffer, e che misuri il tempo medio di attesa, in modo
da poter confrontare le diverse realizzazioni. Opportuni parametri devono
essere previsti per il simulatore in modo da poter svolgere una adeguata
sperimentazione. Ad esempio, il simulatore potrebbe prendere come input
un array di stringhe, una strofa dell'Orlando Furioso (*), e lanciare (ad
intervalli casuali) tanti processi mittenti quante sono le parole in essa
contenute, ed altrettanti processi destinatari. Si assume che il tempo
medio di esecuzione dei destinatari e' maggiore di quello dei mittenti
di un fattore <i>alpha</i>>1.
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4. Si misuri almeno il tempo
medio di attesa di un processo per completare le operazioni di lettura
e scrittura.
<br>Facoltativo: le misure dipendono sia dalla distribuzione della lunghezza
dei messaggi, sia dal tempo di interarrivo dei processi, e sia dalla velocita'
relativa dei mittenti e destinatari (alpha). Si analizzi il comportamento
del sistema al variare di questi tre parametri.
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 5. Facoltativo. Si ottimizzi
il codice del simulatore e se ne misuri l'efficienza. Ad esempio, si valuti
il numero di eventi che si riescono a simulare in un secondo.
<p>A completamento del progetto ogni gruppo dovra' consegnare una documentazione
su carta con chiara l'indicazione dei componenti del gruppo (nome, matricola,
anno accademico e recapito). La documentazione dovra' almeno contenere
le informazioni dettagliate di seguito:
<ul>
<li>
Lo scopo del progetto (problema da risolvere, possibili soluzioni...)</li>

<li>
Le scelte di progetto effettuate (politiche adottate, distribuzioni statistiche
degli eventi, eventuali parametri...)</li>

<li>
L'organizzazione del codice e delle strutture dati</li>

<li>
Descrizione dei test effettuati per dimostrare l'affidabilita' del prototipo
ed analisi dei risultati (includere opportuni grafici e tabelle)</li>

<li>
Procedure di installazione ed utilizzo. Per questa parte si dovra' usare
uno stile analogo a quello dei manuali UNIX</li>

<br>&nbsp;
<p>&nbsp;
<br>&nbsp;
<br>&nbsp;
<br>&nbsp;
<br>&nbsp;
<p>Come appendice del documento dovra' essere incluso il codice sorgente
Java (<b>commentato!).</b>
<p>(*) Diro' d'Orlando in un medesmo tratto
<br>&nbsp;&nbsp;&nbsp; Cosa non detta in prosa mai ne' in rima,
<br>&nbsp;&nbsp;&nbsp; Che per amor venne in furore e matto
<br>&nbsp;&nbsp;&nbsp; D'uom che si` saggio era stimato prima,
<br>&nbsp;&nbsp;&nbsp; Se da colei che tal quasi m'ha fato
<br>&nbsp;&nbsp;&nbsp; E che'l poco ingegno ad or ad or mi lima
<br>&nbsp;&nbsp;&nbsp; Me ne sara' pero' tanto concesso
<br>&nbsp;&nbsp;&nbsp; <b>Che mi basti a finir quanto ho promesso.</b></ul>

</body>
</html>

-- Users.AntonioValletta - 14 Nov 2001 <br>