webentwicklung-frage-antwort-db.com.de

Implementierung einer N-Prozessbarriere mit Semaphoren

Ich trainiere zurzeit für eine OS-Prüfung mit vorherigen Iterationen und bin auf Folgendes gestoßen:

Implementieren Sie eine "N-Prozessbarriere", dh stellen Sie sicher, dass jeder Prozess aus einer Gruppe von Prozessen zu einem bestimmten Zeitpunkt in der jeweiligen Ausführung darauf wartet, dass die anderen Prozesse den angegebenen Punkt erreichen.

Sie haben folgende Möglichkeiten:

init(sem,value), wait(sem) and signal(sem)

N ist eine beliebige Zahl. Ich kann es so machen, dass es für eine bestimmte Anzahl von Prozessen funktioniert, aber nicht für eine beliebige Anzahl.

Irgendwelche Ideen? Es ist in Ordnung, mit dem Pseudocode zu antworten, dies ist keine Aufgabe, sondern nur eine persönliche Studie.

19
Francisco P.

Dies ist gut dargestellt in Das kleine Buch der Semaphoren .

n = the number of threads
count = 0
mutex = Semaphore(1)
barrier = Semaphore(0)


mutex.wait()
count = count + 1
mutex.signal()

if count == n: barrier.signal() # unblock ONE thread

barrier.wait()
barrier.signal() # once we are unblocked, it's our duty to unblock the next thread
38
cnicutar

Verwendung von N Semaphoren. Nicht sehr sicher ...

semaphore barr[N]
semaphore excl=1
int count=0

int i=1
while (i<=N)
   barr[i]=0 #initialization
   i=i+1

# use, each thread (tid)
wait(excl)
count=count+1
if (count==N)
   int j=1
   while (j<=N)
       signal(barr[j])
       j=j+1
   count=0
signal(excl)
wait(barr[tid])
2
Sergio.Uma

Nur 2 Barriere-Semaphore, aber nicht sicher ...

semaphore barr[0..1] # two semaphores: barr[0] and barr[1]
semaphore excl=1
int count=0
int whichOne=0 # select semaphore to avoid race conditions

barr[0]=0 #initialization
barr[1]=0

# sample use
int current   #local for each thread
wait(excl)
current=whichOne
count=count+1
if (count==N)
   int j=1
   while (j<=N)
       signal(barr[current])
       j=j+1
   count=0
   whichOne=1-whichOne # swap barrier to avoid race conditions
signal(excl)
wait(barr[current])
0
Sergio.Uma