Approccio a problemi di concorrenza

[cifa]

Salve,
Vi scrivo perchè a breve avrò un esame di SO nel quale ci sarà un esercizio di programmazione concorrente. Purtroppo guardando le dispense di esercizi fornite dal professore trovo molti problemi nell'approcciarmi a questi problemi, in particolare non so proprio come affrontare un ragionamento risolutivo.
Ho anche notato che viene sempre richiesto l'uso di semafori, di questi ho capito la funzione di "mutua esclusione", ma mi sfugge il loro utilizzo per una sincronizzazione dei process.

Per farvi capire la tipologia dei problemi che sono proposti:

Un piccolo chiosco serve panini con tonno e pomodoro, freddi, e panini con broccoli e salsicce, caldi. I panini vengono preparati
nel retro da un garzone, in teglie da 30 panini l’una, e i panini col tonno non possono stare nella stessa teglia dei panini con le
salsicce.
I panini vengono serviti sul davanti dalla padrona, che sul banco ha spazio per due sole teglie, una per ripieno. Normalmente
la padrona serve i clienti in ordine di arrivo. Quando una delle teglie si esaurisce avverte il garzone, che entro qualche minuto
sostituir` la teglia vuota con una piena di panini dello stesso tipo precedente.
a
Nel frattempo, la padrona va avanti a servire, facendo aspettare temporaneamente quei clienti che chiedono il ripieno mancante.
`
Quando la teglia e stata sostituita, la padrona serve i clienti che precedentemente aveva fatto attendere prima di riprendere il
normale servizio in ordine di arrivo. Se mentre il garzone prepara la nuova teglia la padrona esaurisce anche l’altra, dopo aver
avvertito il garzone, sospende temporaneamente il servizio.
Scrivere in pseudo-codice i processi garzone, padrona e cliente generico, utilizzando i semafori per la sincronizzazione e tenendo
presente che:
- si puo` trascurare l’avvio delle attivita` e considerare le due teglie gia` piene all’avvio;
- e proibito il ricorso all’attesa attiva (busy waiting);
- il generico cliente sceglie a caso quale ripieno chiedere;
- il processo garzone ha una priorit` alta, per cui quando viene attivato solo una teglia pu` essere vuota, ma la preparazione della
nuova teglia richiede un tempo finito (inferiore rispetto al tempo necessario affich` si presentino 30 clienti), parte del quale lo trascorre in stato di blocked;
- quando il garzone sostituisce una teglia sul banco lo fa senza disturbare la padrona (i.e. ordinando correttamente le operazioni non e necessario ricorrere a mutua esclusione).

Un incrocio di due grandi viali (uno in direzione Nord-Sud, l’altro in direzione Est-Ovest) e regolato da un vigile. Il vigile
lascia passare le macchine su uno dei due viali (in ambedue i sensi di percorrenza) per un tempo T, poi blocca il transito
da quel viale, attende che l’incrocio si liberi degli automezzi che lo avevano gi` impegnato, e quindi d` via libera ai mezzi di trasporto in attesa sull’altro viale, lasciandoli transitare per un tempo T, e cos` via indefinitamente. I due viali sono cos`ampi che nell’incrocio non si verifica mai un ingorgo ed il flusso di traffico e sempre scorrevole. Scrivere in pseudo-codice
i generici processi ”vigile”, ”automezzo sulla direttrice Nord-Sud”, ”automezzo sulla direttrice Est-Ovest”, utilizzando per la
sincronizzazione il meccanismo dei semafori. All’avvio del vigile, l’impegno dell’incrocio dovr` essere gi` stato assegnato alle macchine in transito sulla direttrice Nord-Sud.

Ovviamente non vi chiedo una soluzione a questi, anche perchè già la ho, ma solamente un modo per approcciarmi a tali problemi e inziare a ragionarci correttamente

Mi scuso se la domanda è malposta o se fuoriluogo, ringrazio comunque anticipatamente tutti

[bububu]

Te lo dico per esperienza (anche io ne so qualcosa di esami di SO) una volta che entri nel "meccanismo" dei semafori il risolvere gli esercizi proposti è una cavolata (o quasi).

Nel link [http://www.2shared.com/file/f5Q6qL2t/Altro.html] trovi delle dispense che ho fatto assieme ad un mio amico. Una parte sono solo teoria (c'è un pò di tutto: kernel, processi, thread, programmazione concorrente, deadlock e posticipazione indefinita, scheduling, gestione memoria), una parte solo di esercizi risolti (in alcuni ci sono degli errori stupidi come il nome sbagliato in alcuni semafori me ne sono accorto ora). Spero ti siano di aiuto

Comunque per farla breve, breve, breve, anzi brevissima, il problema della mutua esclusione si verifica quando una qualsiasi risorsa viene letta/scritta da due "entità" (thread o chi per loro) in maniera contemporanea (parallelamente per intenderci).

Le casistiche di "risoluzione" di questo tipo di problemi a mio avviso sono solamente 3 (o comunque riconducibili ad una di queste)

1) Mutua esclusione (MUTEX): l'accesso ad una risorsa è esclusivo, quando leggo/scrivo nessun'altro ha accesso (semaforo inizializzato a 1)

Soluzione:
// codice uguale ad entrambi i thread
wait(S)
<regione critica>
signal(s)


2) Sincronizzazione completa: avvio il thread2 quando il thread1 ha finito di fare quel che deve fare (semafori incrociati uno inizializzato a 0 ed uno a 1)

Soluzione:
Thread 1
loop{
wait(S)
<regione critica>
signal(p)
}

Thread 2
loop{
wait(p)
<regione critica>
signal(s)
}

3) Sincronizzazione: (può essere ricondotto al caratteristico problema del buffer circolare). Voglio che il thread1 faccia qualcosa ogni N giri del thread2 (inizializzo un semaforo a 0 ed uno ad N)

(stesso codice del caso 2)


Spero di esserti stato di aiuto e di non aver scritto troppe gastronerie. In bocca al lupo per l'esame