Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет dibr ([info]dibr)
@ 2011-09-15 21:03:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
синхронизация
     На работе пишем счётную программу, обсчитывающую нечто в двух нитях. Нити должны быть синхронизованы - одна не должна обгонять другую. Сделали так: ("псевдокод" на Си):
volatile int lock;

main()
{
 lock=0;
 create_thread(&thread1);
 create_thread(&thread2);
 {ждём и время от времени рисуем графики}
}


thread1()
{
while(1)
 {
  {что-то считаем}
  lock++;
  while(lock==1);
  lock=0;
 }
}

thread2()
{
while(1)
 {
  {что-то считаем}
  lock++;
  while(lock==1);
  lock=0;
 }
}

     Идея ясна: первая нить, досчитав, увеличивает lock, он становится равен 1, нить встаёт в цикл while и ждёт. Вторая нить, досчитав, увеличивает lock, он становится равен 2, нить сбрасывает lock в 0 и идёт на второй круг, первая нить, увидев 0, тоже идёт считать дальше. При желании это легко масштабируется на N нитей, заменой while(lock==1); на while(lock!=0 && lock!=N);. Да, я понимаю. что while(); грузит ядро на 100% - но разница в скорости работы нитей небольшая, да и ядро это всё равно простаивало бы, в ожидании соседней нити. Да, я знаю что "системными функциями было бы надёжнее", но нити крутятся очень быстро, вызывать относительно тяжеловесные системные функции как-то не хочется, такой вот spinlock побыстрее будет.
     Так вот. После нескольких десятков-сотен тысяч "оборотов" обе нити "зависают". Зависают в while(lock==1);. Почему - я так и не понял, volatile вроде не забыл, "гонок" я не вижу. Кто-нибудь может понять, на какие грабли мы тут наступили? Компилятор - какой-то не очень свежий borland C++ builder, какой точно - на работе посмотрю, навскидку не помню.
     Вопрос сейчас уже теоретический - блокировку переписали по другому, "так что работает", а поскольку задача счётная и "для себя", то и пофиг, лишь бы работало. Но чисто теоретически - какого фига? Что тут может быть, lock++ на самом деле неатомарный, или я гонки где-то не заметил?...


(Читать комментарии) - (Добавить комментарий)

Re: deadlock, если даже ++ исполняется атомарно
[info]vtrs@lj
2011-09-15 16:50 (ссылка)
Да, виноват, ошибся. Другое условие.

1. Пусть обе нити стоит перед lock = 0

2. Первая нить исполняет включая lock++ // lock == 1

3. Вторая нить исполняет lock = 0 // lock == 0

4. Вторая нить продолжает и исполняет включая lock++ // lock == 1

4. lock == 1 и обе ждут вечно

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: deadlock, если даже ++ исполняется атомарно
[info]dibr@lj
2011-09-15 17:12 (ссылка)
> Пусть обе нити стоит перед lock = 0

Ok

> Первая нить исполняет включая lock++

Чтобы попасть от lock=0 на lock++ ей надо сначала выполнить блок {что-то считаем}, его время выполнения намного больше времени на lock=0 или lock++, а процессор не перегружен (у нас четыре ядра, в этой задаче два потока) - столько времени нить стоять не может.

> Вторая нить продолжает и исполняет включая lock++ // lock == 1

Теоретически да - если одна нить успела пролететь от while() до lock++ пока другая тормозила между while() и lock=0 - будет deadlock (то есть блокировку надо переписать как-то по другому - с {lock--;lock--;} вместо lock=0 например). Практически - это маловероятно, а в наших условиях (процессор загружен не полностью, есть относительно длинный счётный блок) - вообще не должно происходить.

Но спасибо за бдительность - такую возможность дедлока я у себя не заметил :-)

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: deadlock, если даже ++ исполняется атомарно
[info]aaalex@lj
2011-09-16 18:38 (ссылка)
И практически запросто бывает. Винда надумает вдруг что-то фоном сделать, и, если ядер 2, одна нить пойдет считать и насчитает один цикл, а другая замрет на месте.

Когда нитей больше 1, всегда нужно учитывать худьшый вариант.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: deadlock, если даже ++ исполняется атомарно
[info]dibr@lj
2011-09-17 03:01 (ссылка)
Ну, я же не говорю "невозможно", я говорю "маловероятно" :-) А именно в нашем случае - нити две, ядер четыре, а с гипертредингом вообще "как бы восемь", а что в винде внезапно возникнет семь активных фоновых потоков - конечно не невозможно, но весьма маловероятно.

Но в серьёзном коде, такое, конечно, недопустимо: мало ли в каких условиях его будут запускать...

(Ответить) (Уровень выше)


(Читать комментарии) -