La mise en œuvre d'une barrière de processus en utilisant des sémaphores N

Question

Je suis actuellement en formation pour un examen du système d'exploitation avec des itérations précédentes et je suis tombé sur ceci:

Mettre en oeuvre un "N Process Barrier", qui est, en veillant à ce que chacun des processus d'un groupe d'entre eux attend, à un certain point de son exécution respective, par les autres processus pour atteindre leur point donné.

Vous disposez ops disponibles:

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

N est un nombre arbitraire. Je peux faire en sorte que cela fonctionne pour un certain nombre de processus, mais pas pour tout nombre.

Toutes les idées? Il est OK pour répondre avec le pseudo-code, ce n'est pas une mission, juste étude personnelle.

Answer 1

Ceci est bien présenté dans Le Petit Livre de sémaphores .

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

Answer 2

Utilisation de N sémaphores. Pas très sûr ...

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])

Answer 3

Seulement 2 sémaphores barrière, mais pas sûr ...

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])