Laboratorio II: Sistemi Operativi - a.a. 1999/2000

La consegna va effettuata entro il 24 gennaio 2000 (nuova consegna 9 marzo 2000)

Scambio di messaggi a lunghezza variabile

Introduzione

Un messaggio e' una stringa di al piu' 200 caratteri. I messaggi vengono scambiati da un insieme di processi (thread) 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,

        - put: 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.

        - get: 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().

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 elementare (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'attesa indefinita dei processi, cioe' non e' possibile stabilire un limite superiore al tempo che un generico processo potrebbe aspettare per accedere al buffer.

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.

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 eventi. 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.

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.

Scopo del progetto

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:

        1. Realizzare il tipo di dato astratto buffer (struttura dati e operazioni put e get) con gestione elementare dei processi in attesa.

        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.

        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 alpha>1.

        4. Si misuri almeno il tempo medio di attesa di un processo per completare le operazioni di lettura e scrittura.
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.

        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.

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:

• Lo scopo del progetto (problema da risolvere, possibili soluzioni...)
• Le scelte di progetto effettuate (politiche adottate, distribuzioni statistiche degli eventi, eventuali parametri...)
• L'organizzazione del codice e delle strutture dati
• Descrizione dei test effettuati per dimostrare l'affidabilita' del prototipo ed analisi dei risultati (includere opportuni grafici e tabelle)
• Procedure di installazione ed utilizzo. Per questa parte si dovra' usare uno stile analogo a quello dei manuali UNIX


 

 
 
 
 
 

Come appendice del documento dovra' essere incluso il codice sorgente Java (commentato!).

(*) Diro' d'Orlando in un medesmo tratto
    Cosa non detta in prosa mai ne' in rima,
    Che per amor venne in furore e matto
    D'uom che si` saggio era stimato prima,
    Se da colei che tal quasi m'ha fato
    E che'l poco ingegno ad or ad or mi lima
    Me ne sara' pero' tanto concesso
    Che mi basti a finir quanto ho promesso.

-- AntonioValletta - 14 Nov 2001