$ головоломка для мыщъх'а

Тема в разделе "WASM.HEAP", создана пользователем PROFi, 28 сен 2008.

  1. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    Mika0x65

    Поток который опять попытается захватить спинлок повиснет - так как не будет корректоного освобождения спинлока. Т.е. A не будет содержать 0.
     
  2. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    Почему повиснет? Так или иначе 0х0 ляжет в А, пусть и частями.
     
  3. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    Mika0x65

    Предполагается, что после MOV A, 0 ; Release lock A == FALSE или равно нулю, и следующий поток может захватить спинлок только в этом случае, а как я уже показал выше, после MOV A, 0, A вполне может быть не 0
     
  4. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    PROFi
    А это возможно? Обращение к A уже не первое ведь.
    И к тому же. Давайте рассмотрим подробнее, что происходит, если mov A,0 разорвана.
    1) Поток на первом процессоре, выходящий из критической секции, выставляет незалоченой инструкцией mov A,0 первый байт в нуль. Или я чего-то не знаю, и в случае разрыва инструкции mov могут быть выставлены сначала старшие байты A, а потом только младшие?
    2) После этого второй поток попадает на инструкцию XCHG EAX, A и выставляет первый байт в 1, но при этом в EAX попадает нуль (все остальные байты A, кроме первого, всегда нулевые)
    3) Первый поток выходит из критической секции, а второй всё равно заходит.
    В чём проблема?
     
  5. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    А, кажется, понял.

    Первый выполняет 'mov dword [A], 0x0'. В [A] лежит 0xFFFFFF00. Допустим, первый пока заткнулся. Второй вытается захватить 'xchg eax, A', 'cmp eax, 0x1'. В [A] лежит 0х1, в eax тоже. Переходим на SpinLoop. Управление получает второй. Он "докладывает" в [A] недостающие 0х0, не меняя младший байт, где лежит единица. И уходит на 'jmp Continue'. Второй поток пойман.

    Так?

    Update0:
    Не уверен правда, что такая ситуация возможна с т.з. аппаратуры, но чисто логически, вроде, получается ошибка.

    Update1:
    Так, я наврал. Откуда в [A] может быть 0xFFFFFFFF? Там либо 0, либо 1.
     
  6. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    l_inc

    Проблема в том что если рассматривать сам код, а не алгоритм работы, то он отработает. В примере вообще не рассмаривается правильность работы конкретного кода, суть не в этом - или я не услышан?

    - Спасибо, да интелы сначала меняют младший байт, потом старший - исправился - но суть от этого не меняется.
     
  7. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    PROFi
    В смысле не меняется? Суть в том, можно ли подобрать такое состояние процессора (или нескольких процессоров), которое приведёт к одному из следующих вариантов:
    1) В критическую секцию попадёт более одного потока.
    2) Хотя бы один поток попадёт в бесконечный цикл, ожидая освобождения и так свободной критической секции.
    Учитывая архитектурные особенности интеловских процессоров, такую ситуацию подобрать нельзя. Поэтому формально в коде ошибок нет.
    А в Ваших рассуждениях мы учитываем одну архитектурную особенность процессоров (что mov может быть разорвана), но не учитываем другую (что запись сначала происходит в младший байт).
     
  8. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    Mika0x65

    Последний раз повторяю - я ставлю под сомнение правильность работы конкретного кода - я ставлю под сомнение реализацию алгоритма спинлока.
     
  9. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    l_inc

    и что меняется?
    Получим 000000FFh, 0000FFFFh, 00FFFFFFh вместо
    FFFFFF00h, FFFF0000h, FF000000h?
     
  10. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    PROFi
    Мы никак не получим ни одно из этих значений. После первой части разорванного mov в A попадёт нуль (потому как все байты кроме младшего нулевые). После XCHG изменится опять таки только один байт A — младший, на единицу (остальные останутся нулевыми). Ну и наконец вторая часть mov запишет нули поверх нулей.
    Да... и поток, выполнивший XCHG, зайдёт в критическую секцию, т.к. в eax попал нуль.
     
  11. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    l_inc

    Неужели?
     
  12. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    PROFi
    Именно. И не потому, что xchg, не атомарна (это неправда, и я уже писал, что она атомарна), а потому что она записывает значение 1 в A. Это значит, что меняется только младший байт. Остальные нулями были, нулями и остались.
     
  13. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    l_inc

    По этому поводу я уже писал -
     
  14. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    PROFi
    Прошу прощения. Не вник в смысл. :) Тогда это вообще нечестно. Когда мы рассматриваем код так близко к архитектуре процессора, разница между алгоритмом и кодом стирается. Это одно и то же. И Вы не можете просто так заменить предложенный интелом 1 на 0FFFFFFFFh (типа и то, и то true) и сказать, что алгоритм при этом не меняется. Мало того, ещё и говорить, что у intel ошибка в алгоритме.
     
  15. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    l_inc

    Ок - надеюсь я понят. Код очень интересен и тем, что практически на любом процессоре можно упустить ошибку из вида. И самое интересное - это неуловимый баг будет - в одном случае все будет работать, в другом нет. А так похожий алгоритм используется и для мьютекса с множественным захватом в одном треде.
     
  16. zorro

    zorro New Member

    Публикаций:
    0
    Регистрация:
    8 ноя 2008
    Сообщения:
    33
    имхо в задаче следовало вместо 1 написать imm32 :derisive:
     
  17. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    zorro
    Ага. Нуль, например. :)
     
  18. zorro

    zorro New Member

    Публикаций:
    0
    Регистрация:
    8 ноя 2008
    Сообщения:
    33
    )))))))))