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

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++ на самом деле неатомарный, или я гонки где-то не заметил?...


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


[info]ufm@lj
2011-09-15 14:08 (ссылка)
Я чота пропустил, а где обещали что ++ это атомарная операция?

(Ответить) (Ветвь дискуссии)


[info]dibr@lj
2011-09-15 14:27 (ссылка)
Так я не настоящий программист, я так, "каску одел", мне можно ошибаться.
То есть, инкремент-декремент в Си всё-таки неатомарные? А выглядят ну очень похоже...

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


[info]fobofilofob@lj
2011-09-15 14:30 (ссылка)
М-м, мне казалось, что стандарт Си вообще никогда не обещал про атомарность.

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


[info]dibr@lj
2011-09-15 14:35 (ссылка)
Так я Си изучал тогда, когда и слова-то такого "атомарность" не знал, за ненадобностью :-) На вид они вроде как должны были бы быть атомарными, а поскольку программистом я себя не считаю (так, что-то очень несложное "накодить"), то и уточнять в умных книгах не стал, понадеялся на ощущения...

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


[info]dimon_w@lj
2011-09-15 14:09 (ссылка)
lock
ИМХО Одновреммнно в 2х нитях lock из 0 в 1 преходит...

(Ответить) (Ветвь дискуссии)


[info]dibr@lj
2011-09-15 14:28 (ссылка)
Т.е. инкремент в Си таки неатомарный? А я на это надеялся...

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

InterlockedIncrement вам нужен
[info]alterf@lj
2011-09-15 14:30 (ссылка)
Win32, должен быть и в борланде,копайте приблизно тут:
http://msdn.microsoft.com/en-us/library/ms683614(v=vs.85).aspx

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

Re: InterlockedIncrement вам нужен
[info]dibr@lj
2011-09-15 14:37 (ссылка)
Спасибо, буду знать :-)

...но использовать вряд ли буду: системный вызов звать не хочется, чтобы в "быстро вращающейся" нити не делать лишнего оверхеда, а блокировку мы сейчас сделали по другому, с двумя переменными - пока не виснет :-)

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


[info]dimon_w@lj
2011-09-15 14:50 (ссылка)
А как иначе достичь эффекта "Зависают в while(lock==1)"?
(Да и настоящие программисты уже все вроде объяснили с ссылками и подробностями...)

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


[info]dibr@lj
2011-09-15 16:23 (ссылка)
Я мог пропустить где-нибудь гонки (впрочем, вряд ли - код в три строчки, понять вполне реально) :-) Но, в-общем, да - других вариантов особо нет...

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


[info]dibr@lj
2011-09-15 17:30 (ссылка)
> Я мог пропустить где-нибудь гонки

И, кстати, пропустил - см. комменты ниже. Относительно экзотическую ситуацию, но теоретически возможную.

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

угу, не атомарно
[info]fobofilofob@lj
2011-09-15 14:28 (ссылка)
Здесь почитать
http://www.memoryhole.net/kyle/2007/05/atomic_incrementing.html

а здесь практические знания
http://gcc.gnu.org/onlinedocs/gcc-4.6.0/gcc/Atomic-Builtins.html#Atomic-Builtins

(Ответить) (Ветвь дискуссии)

Re: угу, не атомарно
[info]dibr@lj
2011-09-15 14:31 (ссылка)
Понятно, я как-то так и подозревал.
Спасибо, ответ вполне исчерпывающий, "буду знать" :-)))

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

Re: угу, не атомарно
[info]a_gorb@lj
2011-09-15 15:10 (ссылка)
Замечательно, а мне завтра объяснишь:)

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

deadlock, если даже ++ исполняется атомарно
[info]vtrs@lj
2011-09-15 16:25 (ссылка)
1. Пусть обе нити стоят перед lock++;

2. Первая нить исполняет lock++

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

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

(Ответить) (Ветвь дискуссии)

Re: deadlock, если даже ++ исполняется атомарно
[info]dibr@lj
2011-09-15 16:28 (ссылка)
2!=1

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

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 (ссылка)
Ну, я же не говорю "невозможно", я говорю "маловероятно" :-) А именно в нашем случае - нити две, ядер четыре, а с гипертредингом вообще "как бы восемь", а что в винде внезапно возникнет семь активных фоновых потоков - конечно не невозможно, но весьма маловероятно.

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

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


[info]aaalex@lj
2011-09-15 17:01 (ссылка)
1. Откуда такая боязнь синхронизации средствами ОС? Нерекурсивные мютексы под линуксом и критические секции под виндами очень быстры. И еще вопрос, что эффективнее: эти вызовы или нить, которая крутится без дела в цикле и заставляят ОС заниматься ее скедулингом.

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

3. Для информации, для 64-битных значений у Интела даже присвоение не атомарно.

(Ответить) (Ветвь дискуссии)


[info]dibr@lj
2011-09-15 17:26 (ссылка)
1. Критические секции по-моему не совсем то: нам нужно не чтобы потоки обращались к данным "строго по очереди", а наоборот - чтобы всегда бежали вровень, а опережающий - ждал отстающего. Куда тут приткнуть критическую секцию - навскидку не вижу (разве что обнести ей lock++, но это как-то странно) :-)
А нить - пусть крутится. Она реально крутится очень недолго, поскольку счётный алгоритм в нитях одинаковый (фактически в одной copy/paste из другой), разные только данные, то есть нити и так идут почти вровень, нужно только не дать им разбежаться за счёт небольших отставаний/опережений). Плюс, как я уже писал - нить оборачивается очень быстро. Оверхед на системные вызовы я не оценивал, но на всякий случай решил обойтись без них... :-)

2. Эту мысль я думал :-) Не помню уже, почему решил сделать по другому. Сейчас сделана синхронизация с двумя флажками, по одному на нить, не уверен что она 100% корректна (мне вон внизу нашли дедлок даже с атомарным lock++), но "у нас работает".

3. Ого. Буду знать.

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


[info]ilya_314@lj
2011-09-15 17:11 (ссылка)
Про interlockedincrement уже тут писали. Кстати чего мудрить, на OpenMP все тривиально получается, ничего писать дополнительно не нужно:

#pragma omp parallel sections
{
#pragma omp section
{
// thread 1
}
#pragma omp section
{
// thread 2
}
}

Кстати для справки - локер как отдельный объект в openmp вызывает не помню уже какую стандартную библиотечную ф-ю, которая реализует spinlock и только через некоторое число циклов делает win32 вызов с полноценной остановкой. Т.е. вызов то дорогой и лучше немного подождать в цикле, вдруг уже пора.

(Ответить) (Ветвь дискуссии)


[info]dibr@lj
2011-09-15 17:17 (ссылка)
Хммм. Надо будет покурить этот openMP. Правда, тут есть нюанс под названием "есть программа - есть проблема": то, что уже написано, написано именно под "не очень свежий борланд" (в первую очередь под его интерфейсных элементов), переносить под другую среду разработки никто не будет (разве что совсем новую программу можно начать писать под новой средой), а тот борланд не факт что сможет принять в себя openMP.

А вот библиотечная функция - это интересно. Если она найдётся в нашем борланде - можно использовать: блокировка у нас обычно очень короткая по времени (нити работают почти с одной скоростью), spinlock должно хватить во всех случаях...

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


[info]ilya_314@lj
2011-09-15 17:20 (ссылка)
Вообще openmp великая вещь, поверх уже написанного кода очень удобно применять и конструкций там немного. Если что, справшивай, небольшой опыт есть.

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


[info]ilya_314@lj
2011-09-15 17:24 (ссылка)
Кстати помню, что с библиотечными функциями есть какая-то заморочка - если миксовать CRT функции работы с нитями и Win32. Вся параллельность хорошо расписана у Рихтера.

OpenMP хорош тем, что нет привязки к платформе и абстракции более высокого уровня. Опять же без pragma все работает прекрасно там где нет openmp.

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


[info]dibr@lj
2011-09-15 17:28 (ссылка)
Лишь бы оно в принципе было в конкретном компиляторе. Я ведь правильно понимаю - нельзя взять произвольный компилятор, и прилепить к нему жвачкой поддержку openMP?

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


[info]ilya_314@lj
2011-09-15 17:36 (ссылка)
Нет, потому как сам компилятор специальный код генерит, блоки кода перед которыми #pragma omp... стоит генерируют параллельный код по неким правилам.

В VS2008 и выше это так делается - достаточно выставить опцию компилятору, что разрешен openmp, в коде пишем #pragma omp и все. Правда там есть еще пачка функций для управления, include "omp.h" тогда нужен. Функции типа - дай мне текущий номер нити, задать явно сколько хотим нитей и пр. Функции тупые и на них элементарные заглушки есть в одно действие для компилеров без openmp. Кроме того функций чаще используется всего несколько.

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


[info]dibr@lj
2011-09-15 17:47 (ссылка)
Понятно, спасибо.
Но это мы видимо отложим до перехода на более свежий компилятор - переделывать программу под другую среду разработки не будут, а если просто взять "более свежий BCB" - проект может и развалиться (уже переносили, уже натыкались) :-)

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


[info]ilya_314@lj
2011-09-15 17:19 (ссылка)
Всмопнил, синхронизация по critical section реализована с гибридным использованием spinlock и системного вызова.

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


[info]vlkamov@lj
2011-09-16 03:03 (ссылка)
Ну что здесь небинарная логика уже ясно, но для дальнейшего диагностирования хорошо бы знать какое значение имеет lock при сбое, при исполнении какой части кода происходит сбой и т.п.

(Ответить) (Ветвь дискуссии)


[info]dibr@lj
2011-09-16 03:13 (ссылка)
«обе нити "зависают". Зависают в while(lock==1)»

Стало быть, зависают в while(lock==1) (это часть кода), lock при этом ==1 (иначе бы не зависали).
Но тут уже разобрались: во-первых, ++ не атомарен, а во-вторых - у меня есть пусть и не срабатыващее, но теоретически возможное, race condition.

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