Использование бинарного семафора в коде

Question

Определенное вычисление генерирует два массива a а также b такой, что
a[i]=f(i) for 0 ≤ i < n and b[i] = g(a[i]) for 0 ≤ i < n, Предположим, что это вычисление разбито на два параллельных процесса X а также Y такой, что X вычисляет массив a а также Y вычисляет массив b, Процессы используют два двоичных семафора R а также Sоба инициализируются в ноль. Массив a разделяется двумя процессами. Структура процессов показана ниже.

Process X:                         
private i;                         
for (i=0; i < n; i++) {            
    a[i] = f(i);                       
    ExitX(R, S);                       
 }                                 

Process Y:
private i;
for (i=0; i < n; i++) {
    EntryY(R, S);
    b[i]=g(a[i]);
}

Какой из следующих представляет ПРАВИЛЬНЫЕ реализации ExitX а также EntryY?

(А)

ExitX(R, S) {
    P(R);
    V(S);
}

EntryY (R, S) {
    P(S);
    V(R);
}

(В)

ExitX(R, S) {
    V(R);
    V(S);
}

EntryY(R, S) {
    P(R);
    P(S);
}

(С)

ExitX(R, S) {
    P(S);
    V(R);
}

EntryY(R, S) {
    V(S);
    P(R);
}

(D)

ExitX(R, S) {
    V(R);
    P(S);
}
EntryY(R, S) {
    V(S);
    P(R);
}

Я считаю, что ответ должен быть (B), потому что критический раздел в процессе Y не должен выполняться до критического раздела в X выполняется (a[i] заполняется первым, который должен быть использован для b[i]), так после X выполняется в соответствии с опцией (B) на входе критического раздела в Y мы найдем R=1, S=1 теперь критический раздел Y может быть выполнен

Вопрос: Правильный ответ (С), где я не прав?

Answer 1

Прежде всего, рассмотрим, почему нам здесь даже нужны два семафора. Причина в том, что у нас есть две вещи для координации,

1. Y цикл не может начаться i до окончания цикла X i
2. X петля не может начаться i+1 до того, как Y заканчивает i,

Итак, есть два семафора, каждый из которых управляет одним пунктом выше.

Семафор достигает 1, нужно будет позвонить P от ExitX, А также EntryY нужно позвонить V, так что Б уже здесь. Чтобы достичь 2, нам нужно V в ExitX а также P в EntryY,

Посмотрите на А, никто ничего не увеличивает, так что это тупик.

С делает работу.

D не совсем прав, потому что оба X а также Y может ударить V дважды перед любым P этого семафора называется.

Answer 2

"B" сработало бы, если бы они не были двоичными семафорами: в этом случае X мог бы создать элемент, увеличить один семафор, а Y мог бы ожидать этого семафора и использовать эти элементы. Семафор может подсчитать, сколько элементов доступно для обработки. И одного семафора будет достаточно для этого.

Однако у вас есть двоичные семафоры. Таким образом, вы можете считать только до одного, например, X может создать элемент, сигнализировать семафор, но затем не может продолжать создавать элементы, так как он не может повысить значение этого семафора до "2" (или более). Поэтому он должен ждать, пока этот единственный элемент будет распознан Y. И это ожидание вводит второй семафор, сигнализирующий X, когда текущий элемент обрабатывается. Важно помнить, что P ожидает увеличения семафора, если это необходимо (а V увеличивает), поэтому X не может ждать, пока один семафор вернется к 0, поскольку такой операции нет.

И это то, что делает "С", S практически является сигналом "готовности данных", а R - "подтверждением". X говорит, что готово, затем ждет подтверждения. Пока Y ждет готовности и отправляет подтверждение.