[Esercizio] Monitor per la gestione delle prioritàprocessi

[imported_BlackLight]

Studiando per l'esame di principi di sistemi operativi (laurea specialistica), mi sono ritrovato a fare esercizi interessanti per la gestione degli accessi a un numero finito di risorse da parte di un numero qualsiasi di processi e problemi di mutua esclusione nell'accesso a sessioni critiche. Problemi tipici nella progettazione di un sistema operativo. Vi lascio qui un problema abbastanza interessante:

Un campo da golf ha a disposizione P palline. Il campo è frequentato da giocatori
esperti e principianti. Gli esperti noleggiano 2 palline e hanno la priorità sui
principianti; i principianti noleggiano un numero maggiore di palline, compreso tra 3
e N (N < P). I giocatori, una volta terminato di giocare, devono restituire il numero
esatto di palline noleggiate all’inizio del gioco.
Si implementi una soluzione usando il costrutto monitor per modellare il campo da
golf e i processi per modellare i giocatori e si descriva la sincronizzazione tra i
processi.
Nel rispettare i vincoli richiesti, si cerchi di massimizzare l'utilizzo delle risorse. Si
discuta se la soluzione proposta può presentare starvation e in caso positivo per quali
processi, e si propongano modifiche e/o aggiunte per evitare starvation.

In pratica si tratta di modellare, nel linguaggio che si preferisce, un'entità "Giocatore" (esperto o principiante) come processo o thread, caratterizzato dal numero di palline richieste, ed eventualmente dal tempo per cui trattiene queste risorse. E un'entità "Campo" che faccia da monitor, ovvero si occupi di gestire le code di attesa dei processi (vanno bene anche normali FIFO), i loro accessi alle risorse e le relative priorità. È un problema interessante perché mette in risalto le problematiche legate sia alla gestione della mutua esclusione delle risorse, sia alla priorità dei processi in coda.

La soluzione ovviamente può essere codata nel linguaggio che si preferisce. Io l'ho implementata in Java. Per chi la volesse implementare in Java, qui trova una piccola libreria, preparata per il corso universitario, per la gestione di monitor e code di attesa (con wait() e signal() implementate per gestire le code). Oppure volendo si può implementare in C/C++ con gestione dinamica delle code o uso dei semafori.

 

[kr1pn0$]

[ot]a natale ti postero il code....[/ot]

 

[stoner]

Si.. ma è tutto da simulare, bisogna simulare l'arrivo dei giocatori (quindi un thread lento che genera un giocatore con un certo livello di esperienza, e se è principiante genera un numero casuale di palline da 'prelevare'). Poi bisogna simulare la partita del giocatore, quindi altri thread che agiscono non appena il giocatore riceve la 'risorsa' (in questo caso il campo) e poi simulare la sua partita ... tra un po è più la simulazione che l'algoritmo. Comunque il problema dello starvation si ha sempre. Un modo per risolvere sarebbe quello di dare, ogni 5 esperti per esempio, la priorità ad un principiante nel caso in cui la coda dei principianti abbia almeno un giocatore, oppure sia lunga (per esempio più di 5 persone), e poi una volta che ha ottenuto la priorità non è nemmeno detto che riesca ad ottenere la risorsa visto che necessita di un numero di palline più alto di quelli degli esperti, ipotizzando un numero di palline pari a 20, se ci sono in campo 5 esperti hanno in totale 10 palline, se il principiante ne vuole 11 rimane attaccato, poi nel frattempo magari arriva un nuovo esperto che ha la priorità sul principiante e quello rimane sempre li.. se poi estremizziamo il caso e ipotizziamo un principiante che vuole tutte le palline la coda non si muove mai, quindi bisognerebbe 'inventarsi' qualcosa... comunque l'esercizio è carino, una sorta di mini scheduler, apparentemente facile però non è banale.
Comunque appena ho tempo lo farò, forse, non è detto, questa settimana sono impegnato con l'uni che ho gli esami...

 

[Whivel]

eghete.... come esercizio di programmazione è abbastanza complicato.....
a questo punto per complicarlo un po userei i semafori.... ^^

 

[R4z0r_Cr4sH]

già già...complesso ma non impossibile...se si studia (all'uni o alle superiori) informatica si studiano anche i thread e i classici esercizi tipo il problemi del barbiere.Appena ho tempo lo sviluppo...in java !

 

[Whivel]

io l'ho studiato alle superiori però a sistemi.... ci ha fatto fare esercizi tipici come quelli del barbiere più altri che si inventava.....

 

[imported_BlackLight]

@stoner: Beh è chiaro che il comportamento del sistema nella classe di test è tutto da emulare...io sinceramente preferisco, ad esempio, inizializzare quanti più valori casuali possibili nell'inizializzazione dei thread, in modo da testarne la robustezza in casi molto diversi fra loro.