Реализация барьера процесса N с использованием семафоров

В настоящее время я готовлюсь к экзамену по ОС с предыдущими итерациями, и я наткнулся на это:

Реализуйте N-процессный барьер, то есть убедитесь, что каждый процесс из группы ожидает в какой-то момент своего соответствующего выполнения, пока другие процессы не достигнут своей заданной точки.

Вам доступны следующие операции:

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

N — произвольное число. Я могу сделать так, чтобы он работал для заданного количества процессов, но не для любого числа.

Любые идеи? Можно ответить псевдокодом, это не задание, а личное изучение.


operating-system semaphore computer-science barrier systems-programming
person F. P.    schedule 13.06.2011    source источник

Ответы (3)


arrow_upward
46
arrow_downward

Это хорошо показано в Маленькой книге семафоров.

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
person cnicutar    schedule 13.06.2011
comment
Спасибо! Я думал о чем-то ОЧЕНЬ близком. - person F. P.; 13.06.2011
comment
Не лучше ли поместить if count... в блок мьютекса, чтобы убедиться, что он введен только один раз? В том виде, в каком он стоит сейчас, похоже, что вы потенциально можете ввести его дважды. - person Jean-Bernard Pellerin; 19.10.2011
comment
nvm - посмотрел на маленькую книжку, и это нормально, что она сигнализируется дважды, поскольку этот барьер не используется повторно, поэтому его конечное состояние не имеет значения, если он достиг своей цели. - person Jean-Bernard Pellerin; 19.10.2011
comment
если вы захотите использовать его повторно, вам придется снова получить свой мьютекс сразу после последнего барьера.signal() и уменьшить переменную count. не забудьте разблокировать мьютекс после этого. но почему нет необходимости удерживать мьютекс, пока if выполняет проверку подсчета? - person Hafnernuss; 08.05.2015
comment
чтобы привести пример: скажем, поток 5 захватывает мьютекс, увеличивает счетчик и освобождает мьютекс. Теперь планировщик переключается на другой поток, который снова захватывает мьютекс, увеличивает счетчик и освобождает мьютекс. count теперь равен 6, и барьер никогда не будет сигнализировать о своем потоке. - person Hafnernuss; 08.05.2015
comment
Проголосовал за ссылку на Маленькую книгу семафоров. Это здорово! Спасибо! - person rocarvaj; 09.05.2016

arrow_upward
2
arrow_downward

Использование N семафоров. Не очень уверен...

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])
person Sergio.Uma    schedule 18.12.2015
comment
Это приведет к ошибке. Должно быть while (i<N). То же самое для следующего цикла while: while (j<N). - person MPKenning; 10.01.2017

arrow_upward
0
arrow_downward

Только 2 барьерных семафора, но не уверен...

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])
person Sergio.Uma    schedule 18.12.2015