1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

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

Тема в разделе "WASM.HEAP", создана пользователем l_inc, 7 авг 2011.

  1. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Столкнулся недавно со следующей задачкой. Два часа промучался, пока пришло решение.

    Есть два потока (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, рандеву может не состояться.

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

    intel_x128 New Member

    Публикаций:
    0
    Регистрация:
    17 май 2009
    Сообщения:
    345
    write(a,a+1) write(b,b+1)
    wait(b,b+1) wait(a,a+1)
     
  3. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    intel_x128
    Условие до середины хотя бы дочитали?
    Во-первых, обе переменные должны иметь значение 10 на выходе. Это замечание к внимательности.
    А во-вторых, один из потоков в Вашем варианте гарантировано не выйдет из барьера.
     
  4. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Код (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)
     
  5. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Booster
    Пусть значение в a изначально нулевое, и поток Y приходит первым. Он останавливается на wait(a,10). Тогда поток X даже первую строчку не пройдёт. Дэдлок.
     
  6. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    используйте блокировку не одним значением, а разными. как это, семафор, чтоли. и используйте эти значения для управления автоматом рандеву.

    скажем,

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

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

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

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    qqwe
    Советы — это, конечно, круто. Но ожидается решение в указанном синтаксисе. Так что решение не засчитано. :-)
    Хотя судя по числу предложенных значений, оно у Вас уж слишком большое бы получилось.
     
  8. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Тогда так.
    Код (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)
     
  9. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    l_inc
    1 свитч + 1 переменная автомата + 1 спинлок
    количество значений можно уменьшить для единовременной передачи всех данных. также, можно уменьшить если буфер передачи будет фиксированный или будет выделен на передающей стороне
     
  10. l_inc

    l_inc New Member

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

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    qqwe
    Где решение в указанном синтаксисе? Судя по Вашим постам, Вы даже не начали читать условие. Какая ещё передача данных?
     
  12. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    l_inc
    ага. я понял. вас не рандеву, а именно случайность начальнвх данных.
    а почему их не инициализовать где нибудь вначале? есть ограничение на начальную, те задолго до рандеву, инициализацию?
     
  13. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    qqwe
    В данном контексте, потому что таково условие задачи. В контексте задачи, которую я решал, потому что потоки не мои, а нужно вклиниваться в середину чужого периодически исполняющегося кода, который меняет значения этих переменных.
     
  14. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    l_inc
    Невозможно. Как минимум ещё нужно читать, но не уверен достаточно ли этого.
     
  15. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Booster
    Возможно. Скопируйте первые два предложения из заглавного поста. :derisive:
     
  16. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Чего? Куда?
     
  17. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Booster
    Не обращайте внимания. Это я так... настроение пошаливает. В общем, подожду утра.
     
  18. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Как-то так, "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)
     
  19. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Booster
    Это в любом случае не было бы засчитано по указанной Вами причине. Кроме того:
    Нет... Всё-таки никаких кроме. Но тем не менее.
     
  20. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    l_inc
    Эта причина преодолима, раз "а" на выходе будет иметь уже известное/нужное значение, то можно будет аналогично привести и "b" . Никаких дедлоков я там не вижу.