Рандеву. Задачка на синхронизацию.

Столкнулся недавно со следующей задачкой. Два часа промучался, пока пришло решение.

Есть два потока (X и Y), в разделяемой памяти которых есть ровно две (ни больше, ни меньше) переменные: a и b. Разделяемого кода нет. Нужно организовать барьер (или рандеву: кому как удобнее), т.е. написать для обоих потоков некоторые области кода, которые ни один из потоков не покинет, пока оба потока не будут каждый в своей области. После этого оба потока должны покинуть барьер, не важно в каком порядке (т.е. дэдлок, разумеется, не является правильным решением).
Дополнительные условия:
1) Разрешается использовать только два примитива (в основном, с целью унификации решений): write(variable,value) и wait(variable,value). Например, write(a,0) поместит нуль в переменную a; wait(b,10) затормозит поток до тех пор, пока у b не будет значения 10.
2) Начальные значения переменных a и b неизвестны и могут быть любыми.
3) Необходимо гарантировать, что ни один из потоков не покинет свой барьер, пока обе переменные a и b не примут предопределённые значения. Пусть, например, обе должны принять значение 10.

Пример решения:

Код (Text):

1.     X              Y
2. write(a,10)    write(b,10)
3. wait(b,10)      wait(a,10)

Это был бы правильно написанный барьер, если бы не пункт 2: в случае, если одна из переменных (или обе) была изначально инициализирована значением 10, рандеву может не состояться.

Все желающие скромно приглашены к барьеру решению.

 

write(a,a+1) write(b,b+1)
wait(b,b+1) wait(a,a+1)

 

intel_x128
Условие до середины хотя бы дочитали?
Во-первых, обе переменные должны иметь значение 10 на выходе. Это замечание к внимательности.
А во-вторых, один из потоков в Вашем варианте гарантировано не выйдет из барьера.

 

Код (Text):

1. Code:
2.  
3.     X              Y
4. wait(b,0)      write(b,0)
5. write(a,0)     wait(a,0)
6. wait(b,10)     write(b,10)
7. write(a,10)     wait(a,10)

 

Booster
Пусть значение в a изначально нулевое, и поток Y приходит первым. Он останавливается на wait(a,10). Тогда поток X даже первую строчку не пройдёт. Дэдлок.

 

используйте блокировку не одним значением, а разными. как это, семафор, чтоли. и используйте эти значения для управления автоматом рандеву.

скажем,

0 - нет никто
1 - первое прибыло ждет рандеву
2 - второе прибыло
3 - передача адреса буфера, начального смещения и размера буфера от читателя к писателю
4 - заполнение буфера писателем
5 - буфер заполнен и возвращено начальное смещение и колво байт
6 - чтение буфера читателем
... далее повторяем с 3
7 - конец данных от писателя к читателюв
8 - конец рандеву от читателя к писателю

9 - вспомогательное состояние. нужно для некоторых спинблокировок на нем просто ждем пока оно не сменится

если передача двунаправленная или предполагает многие передачи, то колво состояний надо будет увеличить

 

qqwe
Советы — это, конечно, круто. Но ожидается решение в указанном синтаксисе. Так что решение не засчитано.
Хотя судя по числу предложенных значений, оно у Вас уж слишком большое бы получилось.

 

Тогда так.

Код (Text):

1. Code:
2.  
3.     X              Y
4. write(a,0)      write(b,0)
5. wait(b,0)     wait(a,0)
6. write(a,10)     wait(a,10)
7. wait(b,10)      write(b,10)

 

l_inc

1 свитч + 1 переменная автомата + 1 спинлок
количество значений можно уменьшить для единовременной передачи всех данных. также, можно уменьшить если буфер передачи будет фиксированный или будет выделен на передающей стороне

 

Booster
Возможна ситуация идентичная предыдущей, только поменяйте потоки местами. Теперь X первым пробегает до wait(b,10) и виснет навсегда. Y не пройдёт вторую строчку.

 

qqwe
Где решение в указанном синтаксисе? Судя по Вашим постам, Вы даже не начали читать условие. Какая ещё передача данных?

 

l_inc

ага. я понял. вас не рандеву, а именно случайность начальнвх данных.
а почему их не инициализовать где нибудь вначале? есть ограничение на начальную, те задолго до рандеву, инициализацию?

 

qqwe

В данном контексте, потому что таково условие задачи. В контексте задачи, которую я решал, потому что потоки не мои, а нужно вклиниваться в середину чужого периодически исполняющегося кода, который меняет значения этих переменных.

 

l_inc
Невозможно. Как минимум ещё нужно читать, но не уверен достаточно ли этого.

 

Booster
Возможно. Скопируйте первые два предложения из заглавного поста.

 

Чего? Куда?

 

Booster
Не обращайте внимания. Это я так... настроение пошаливает. В общем, подожду утра.

 

Как-то так, "a" на выходе будет 10, "b" может не быть, но рандеву есть.

Код (Text):

1.     X              Y
2. write(a,0)    write(a,10)
3. wait(a,10)    wait(a,0)
4. write(a,0)    write(a,10)
5. write(b,0)    write(b,10)
6. wait(b,10)    wait(b,0)
7. write(a,10)    write(a,10)
8. write(b,0)      write(b,10)

 

Booster
Это в любом случае не было бы засчитано по указанной Вами причине. Кроме того:
Нет... Всё-таки никаких кроме. Но тем не менее.

 

l_inc

Эта причина преодолима, раз "а" на выходе будет иметь уже известное/нужное значение, то можно будет аналогично привести и "b" . Никаких дедлоков я там не вижу.