Teoria dei sistemi operativi - utilizzando il numero minimo di semafori

Question

Teoria dei sistemi operativi - utilizzando il numero minimo di semafori

#1 da (1 voti)

1

Questa situazione è soggetta a deadlock dei processi in un sistema operativo e mi piacerebbe risolverlo con il minimo di semafori. Fondamentalmente ci sono tre processi che cooperano che tutti leggono i dati dallo stesso dispositivo di input. Ogni processo, quando riceve il dispositivo di input, deve leggere due dati consecutivi. Voglio usare l'esclusione reciproca per farlo. I semafori dovrebbero essere usati per sincronizzare:

P1:                     P2:                     P3:
input(a1,a2)            input (b1,b2)           input(c1,c2)
Y=a1+c1                 W=b2+c2                 Z=a2+b1
Print (X)               X=Z-Y+W

La dichiarazione e l'inizializzazione che penso possa funzionare qui sono:

semaphore s=1

sa1 = 0, sa2 = 0, sb1 = 0, sb2 = 0, sc1 = 0, sc2 = 0

Sono sicuro che tutti i programmatori del kernel che si verificano in questo modo possono eliminarlo in un minuto o 2.

Diagramma dei processi cooperanti e un dispositivo di input:

Sembra che P1 e P2 possano iniziare come:

wait(s)

input (a1/b1, a2/b2)

signal(s)

operating-systems theory algorithms resources signals

posta stackuser 29.10.2013 - 09:06

fonte

1 risposta

Leggi altre domande sui tag operating-systems theory algorithms resources signals

Diagramma di classe UML: l'oggetto aggregato può far parte di due classi aggregate? Acquisizione ricorsiva dei dati della tabella relazionale in XML

score 1 · Accepted Answer

La descrizione del processo sembra suggerire che P1 ha bisogno di dati letti da P3 (c1), P2 ha bisogno di dati letti da P3 (c2), e P3 ha bisogno di dati letti da P1 e P2 (a2 e b1).

Quindi, questo è ciò che deve accadere (dove * può verificarsi in qualsiasi momento dopo 2):

P1 < - leggi a1
P3 < - leggi c1
P3 < - leggi c2
P2 < - leggi b1 e b2 *. P1 < - leggi a2

O P1, P2 e P3 usano una cache dell'ultimo valore letto nell'altro processo?

Se quest'ultimo, hai solo bisogno di un semaforo di mutua esclusione per controllare l'accesso al dispositivo. Se si tratta del primo, è possibile avere un quarto processo che gestisce la lettura di tutti i dati e sincronizzarsi quando un set valido è disponibile per tutti gli usi e quando il set di dati è stato letto da tutte le parti.

Il quarto processo non deve sapere in anticipo quali siano i dati da leggere, può semplicemente implementare una coda messaggi in cui P1, P2 e P3 inviano i parametri per i dati da leggere. Quindi incrementa un semaforo di conteggio ogni volta che completa le letture da ciascun processo. Dopo aver inviato il loro messaggio di lettura, tutti aspettano che il semaforo "pronto per i dati" raggiunga il valore 3, quindi sa che è disponibile un set valido di dati. Dopo aver fatto una lettura, a loro volta incrementano un semaforo "data read" e aspettano che raggiunga 3. Quando lo fanno, attendono quindi il semaforo "data ready" per andare a 0 (il quarto processo lo gestisce dopo che tutti hanno hanno segnalato la loro lettura, riportando il semaforo "pronto per i dati" su 0, il semaforo "read data" torna a 0. e l'intero processo si ripete. Nota, non avresti mai un caso in cui un processo potrebbe perdere la transizione a zero (deadlock) poiché ogni processo deve segnalare che la loro lettura è completa prima che l'attesa dei "dati pronti" vada a zero nel momento in cui il terzo processo va in giro per farlo leggere.

Quindi, in fondo, dovresti essere in grado di implementarlo con 1 semaforo o 2 a seconda di quali sono i tuoi requisiti per un insieme di dati simultanei.

EDIT - Esaminando questo, il semaforo "pronto per i dati" non ha bisogno di essere un conteggio in quanto il thread con la proprietà esclusiva del dispositivo di input può semplicemente mantenere un conteggio interno e solo segnalare una volta quando è pronto un set di dati completo .