progetto2000-2001
Laboratorio II: Sistemi Operativi - a.a. 2000/2001
Problema lettori-scrittori
Introduzione
Un archivio DB contiene un insieme di coppie (chiave, valore) ed e'
condiviso fra piu' processi (thread). Ad esempio, il DB potrebbe
contenere le coppie (utente, password). I processi (thread) possono
comportarsi da lettori, accedendo il DB solo per leggere, oppure da scrittori,
accedendo il DB solo per scrivere. Per garantire la consistenza dei
dati è necessario che i processi scrittori accedano al DB in mutua
esclusione, sia fra di loro, sia nei confronti dei lettori. Le sole operazioni
consentite sul DB sono quelle di read o write, mediante le
quali e' possibile rispettivamente leggere, aggiungere, togliere, e modificare
un elemento.
Diverse scelte sono possibili nella gestione dei processi in attesa
di accedere al DB. La piu' semplice e' la gestione elementare: i
lettori che lo richiedono ottengono immediatamente l'accesso al DB in tutti
i casi eccetto quello in cui vi stia accedendo uno scrittore. 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 DB.
L'efficienza di una politica di accesso al buffer puo' essere misurata
in base al tempo medio che un processo impiega 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 DB. Dunque, un processo impieghera' una unita' di tempo ad eseguire
una operazione (read o write) se questa non comportera' attesa; se pero'
questa comporta un'attesa durante la quale si registrino altri n accessi
(non necessariamente completati), allora il tempo virtuale di esecuzione
dell'operazione sara' di n+1.
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 DB condiviso fra processi lettori
e scrittori. In particolare, si richiede di:
-
Realizzare le classi Java DB e gestoreAccessoDB. Il DB realizza la struttura
dati e almeno le operazioni read e write, mentre il gestoreAccessoDB
regola l'accesso al DB e realizza almeno le operazioni accesoRead, fineRead,
accessoWrite e fineWrite.
-
Realizzare una politica di gestione elementare dei processi.
-
Realizzare una politica di gestione dei processi che eviti l'attesa indefinita
sia degli scrittori sia dei lettori.
-
Realizzare un programma simulatore che lanci un insieme di processi lettori
e scrittori che interagiscono sul DB, 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 dovrebbe almeno permettere
di variare il rapporto fra il numero di lettori e di scrittori e la lunghezza
delle singole operazioni di lettura e di scrittura.
-
Si misuri almeno il tempo virtuale medio che un processo impiega per completare
le operazioni di lettura e scrittura (dal momento della richiesta al momento
del completamento, turnaround time medio)
-
Facoltativo. Realizzare una politica di gestione dei processi che aumenti
il grado di concorrenza fra lettori e scrittori, ad esempio si potrebbe
pensare di partizionare il DB in modo da permettere scritture concorrenti
su ciascuna partizione.
-
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 di tempo machina.
-
E' facoltativo lo sviluppo di un'interfacia grafica per il simulatore.
Il programma Java dovra' comunque prevedere l'uso in modalita' non grafica.
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 (e' scoraggiato l'uso di cartelline
o copertine di plastica):
-
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 l'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!).