cifa
17-01-2012, 00:07
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 :)
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 :)