синхронизация потоков в Линуксе

asseevdm

Беру книжку Богачев К.Ю. Основы параллельного программирования. - М.: Изд-во "БИНОМ. Лаборатория знаний", 2003. - 342 с. (http://study.qwe123.info/Bogachev%20K.%20Yu./)
На странице 182 пример синхронизации потоков. (Извините, что не текстом)




Вызывает интерес три вопроса. Особенно первый.
1. Зачем все-таки считать пришедших и вышедших? Я понимаю, что если считать только пришедшие потоки, то один борзый может запросто успеть зайти в следующий вызов функции synchronize до того, как его товарищи выйдут из предыдущего. Но что в этом плохого? Может ли кто-то привести пример, когда использование "упрощенного" synchtonize приводит к неожиданным эффектам?
2. Почему threads_in не сделан volatile? Есть ли гарантия, что оно вообще будет работать?
3. Почему мы в цикле ожидаем?

while (treads_in < total_treads)
thread_cond_wait(...);

После того, как выполнен cond.broadcast, все висевшие в thread_cond_wait треды начнут лочить мутекс и только один его получит. Теоретически этот удачливый тред перед тем, как отдать мутекс, может попортить значение treads_in. Тогда следующий тред, который выйдет из thread_cond_wait, не может полагаться, что threads_in < total_threads. Благодаря циклу он это проверит и в случае чего опять заснет на threads_cond_wait. Но в текущей программе остальные треды не могут нарушить threads_in < total_threads.
Вроде, еще есть объяснение, что wait может словить какой-нить sigint и выйти по нему.
Еще это все вызывает ассоциации с семантикой Mesa.

komarov

По поводу п. 3, цитата из SUS v2 про pthread_cond_wait
When using condition variables there is always a boolean predicate involving shared variables associated with each condition wait that is true if the thread should proceed. Spurious wakeups from the pthread_cond_wait or pthread_cond_timedwait functions may occur. Since the return from pthread_cond_wait or pthread_cond_timedwait does not imply anything about the value of this predicate, the predicate should be re-evaluated upon such return.

это не годится как объяснение необходимости цикла?

asseevdm

О, это достаточно, чтобы писать while И не парится. Но все же любопытно, что за механизм spurious wakeup`а?

Vikuschechka9

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

komarov

Говорят в linux оно сделано через futex, а он прерывается сигналами с возвратом EITNR:
Signals (or other spurious wakeups) cause FUTEX_WAIT to return EINTR.

obushmelev

Multiple Awakenings by Condition Signal
On a multi-processor, it may be impossible for an implementation of pthread_cond_signal to avoid the unblocking of more than one thread blocked on a condition variable. For example, consider the following partial implementation of pthread_cond_wait and pthread_cond_signal executed by two threads in the order given. One thread is trying to wait on the condition variable, another is concurrently executing pthread_cond_signal while a third thread is already waiting.
pthread_cond_wait(mutex, cond):
value = cond->value; /* 1 */
pthread_mutex_unlock(mutex); /* 2 */
pthread_mutex_lock(cond->mutex); /* 10 */
if (value == cond->value) { /* 11 */
me->next_cond = cond->waiter;
cond->waiter = me;
pthread_mutex_unlock(cond->mutex);
unable_to_run(me);
} else
pthread_mutex_unlock(cond->mutex); /* 12 */
pthread_mutex_lock(mutex); /* 13 */
pthread_cond_signal(cond):
pthread_mutex_lock(cond->mutex); /* 3 */
cond->value++; /* 4 */
if (cond->waiter) { /* 5 */
sleeper = cond->waiter; /* 6 */
cond->waiter = sleeper->next_cond; /* 7 */
able_to_run(sleeper); /* 8 */
}
pthread_mutex_unlock(cond->mutex); /* 9 */
The effect is that more than one thread can return from its call to pthread_cond_wait or pthread_cond_timedwait as a result of one call to pthread_cond_signal. This effect is called "spurious wakeup". Note that the situation is self-correcting in that the number of threads that are so awakened is finite; for example, the next thread to call pthread_cond_wait after the sequence of events above blocks.
While this problem could be resolved, the loss of efficiency for a fringe condition that occurs only rarely is unacceptable, especially given that one has to check the predicate associated with a condition variable anyway. Correcting this problem would unnecessarily reduce the degree of concurrency in this basic building block for all higher-level synchronization operations.
An added benefit of allowing spurious wakeups is that applications are forced to code a predicate-testing-loop around the condition wait. This also makes the application tolerate superfluous condition broadcasts or signals on the same condition variable that may be coded in some other part of the application. The resulting applications are thus more robust. Therefore, IEEE Std 1003.1-2001 explicitly documents that spurious wakeups may occur.

Jakov

1. Зачем все-таки считать пришедших и вышедших? Я понимаю, что если считать только пришедшие потоки, то один борзый может запросто успеть зайти в следующий вызов функции synchronize до того, как его товарищи выйдут из предыдущего. Но что в этом плохого? Может ли кто-то привести пример, когда использование "упрощенного" synchtonize приводит к неожиданным эффектам?
ну там же снизу написано
это делается чтобы обнулить threads_in ПОСЛЕ того как все проснулись, но ДО того как все вышли из функции
потому что при двух подряд
synchronize
synchronize
со threads_in возникают проблемы в простой схеме

obushmelev

1. Зачем все-таки считать пришедших и вышедших? Я понимаю, что если считать только пришедшие потоки, то один борзый может запросто успеть зайти в следующий вызов функции synchronize до того, как его товарищи выйдут из предыдущего. Но что в этом плохого? Может ли кто-то привести пример, когда использование "упрощенного" synchtonize приводит к неожиданным эффектам?
Чтобы можно было вызывать функцию в цикле или два раза подряд, как в предыдущем примере, в какой-то момент нам нужно обнулить счетчик threads_in, чтобы мог начать работать следующий раз. В упрощенном варианте это можно сделать в двух местах:
1. Где threads_out выставляется в 0 перед broadcast'ом (или после него когда последний поток вошел в функцию.
2. После всего if'а, где threads_out++, т.е. каждый выходящий поток будет обнулять счетчик.
Других вариантов нет.
Второй вариант сразу отпадает из-за ситуации, когда еще не все вышли, а один поток уже опять зашел - он увеличит счетчик, а последующий выходящий поток снова его сбросит. Значит остается первый вариант, который не работает в следующей ситуации:
Последний поток выставляет threads_in в 0, делает броадкаст, потоки начинают просыпаться, а т.к. wait, как обычно, стоит в цикле, то они обнаруживают, что threads_in < total_threads и снова впадают в спячку на cond_wait. В итоге, только последний поток прорвется сквозь функцию.
Если же мы сбрасываем threads_in после броадкаста, то есть шанс, что какой-то поток застанет, что threads_in == threads_total и выскочит из цикла. Но здесь поведение становится совсем недетерминированным - кто-то проснется, а кто-то - нет.
Выводы:
все проблемы вызникают из-за того, что мы ждем сигнала в цикле (в данном случае только из-за случайных пробуждений). Чтобы избавиться от этой проблемы нам нужно гарантировать, что все потоки увидят, что случилось состояние threads_in == threads_total. Для этого и используется другая условная переменная.

obushmelev

2. Почему threads_in не сделан volatile? Есть ли гарантия, что оно вообще будет работать?
Вроде как, должно работать в данном случае даже без volatile, если реализация pthreads и оптимизатор удовлетворяют стандарту phtreads на memory visibility:
2. Whatever memory values a thread can see when it unlocks a mutex, either
directly or by waiting on a condition variable, can also be seen by any
thread that later locks the same mutex. Again, data written after the mutex
is unlocked may not necessarily be seen by the thread that locks the
mutex, even if the write occurs before the lock.
4. Whatever memory values a thread can see when it signals or broadcasts a
condition variable can also be seen by any thread that is awakened by that
signal or broadcast. And, one more time, data written after the signal or
broadcast may not necessarily be seen by the thread that wakes up, even if
the write occurs before it awakens.

Судя по этим гарантиям, оптимизатор никак не должен соптимизировать threads_in, и кэши должны обновиться корректно

ramses1971

То есть получается, что компилятор должен знать о pthreads, знать о том, что несколько операций - особенные, и перед ними нужно вывести _все_ переменные из регистров? Плюс memory barrier в коде mutex_*.
Я как-то представлял себе pthread более компиляторо-независимым...

Elena12345

То есть получается, что компилятор должен знать о pthreads, знать о том, что несколько операций - особенные, и перед ними нужно вывести _все_ переменные из регистров?
Наоборот :)
Во первых, не все переменные, а только те, состояние которых можно наблюдать из других тредов, например, глобальные и статические; upd: забыл упомянуть динамически аллоцируемые объекты; их тоже. Не нужно записывать, например, локальные (не статические) переменные, у которых не брался адрес: их нельзя наблюдать извне использующей их функции в любом случае.
Во вторых, такие переменные компилятор должен записывать перед вызовом неизвестной ему функции в любом случае, т.к. эта неизвестная функция может их читать.
В третьих, раз уж пошла такая пьянка, модель памяти, используемая в стандарте языка Си неявно предполагает однопоточное исполнение, так что есть несколько неприятных случаев, когда компилятор таки делает неправильные (для многопоточных программ) преобразования.

obushmelev

То есть получается, что компилятор должен знать о pthreads, знать о том, что несколько операций - особенные, и перед ними нужно вывести _все_ переменные из регистров? Плюс memory barrier в коде mutex_*.
Я как-то представлял себе pthread более компиляторо-независимым...
Я не знаю, как там устроено взаимодействие, но оно есть. Вот что говорит msdn по этому поводу:
Optimizing compilers, such as the Microsoft C compiler, sometimes eliminate or reorder read and write instructions if the optimizations do not break the logic of the routine being compiled. In addition, certain hardware architectures sometimes reorder read and write instructions to improve performance. Furthermore, on multiprocessor architectures, the sequence in which read and write operations are executed can appear different from the perspective of different processors.
Most of the time, reordering by the compiler or the hardware is completely invisible and has no effect on results other than generating them more efficiently. However, in a few situations, you must prevent or control reordering. The volatile keyword in C and the Windows synchronization mechanisms can ensure program order of execution in nearly all situations . In some rare instances, the executable code must contain memory barriers to prevent hardware reordering.

Так что примитивы синхронизации как-то сообщают компилятору, что этот код нужно оптимизировать как-то по-особенному

ramses1971

Во вторых, такие переменные компилятор должен записывать перед вызовом неизвестной ему функции в любом случае, т.к. эта неизвестная функция может их читать.
Точно, не подумал.
В третьих, раз уж пошла такая пьянка, модель памяти, используемая в стандарте языка Си неявно предполагает однопоточное исполнение, так что есть несколько неприятных случаев, когда компилятор таки делает неправильные (для многопоточных программ) преобразования.
Можешь немного подробнее?

ramses1971


Optimizing compilers, such as the Microsoft C compiler, sometimes eliminate or reorder read and write instructions if the optimizations do not break the logic of the routine being compiled. In addition, certain hardware architectures sometimes reorder read and write instructions to improve performance. Furthermore, on multiprocessor architectures, the sequence in which read and write operations are executed can appear different from the perspective of different processors.
Most of the time, reordering by the compiler or the hardware is completely invisible and has no effect on results other than generating them more efficiently. However, in a few situations, you must prevent or control reordering. The volatile keyword in C and the Windows synchronization mechanisms can ensure program order of execution in nearly all situations . In some rare instances, the executable code must contain memory barriers to prevent hardware reordering.

Так что примитивы синхронизации как-то сообщают компилятору, что этот код нужно оптимизировать как-то по-особенному
Нет, это говорит о том, что если переменная volatile, то после memory barrier она гарантированно оказывается на планке памяти.

Elena12345

Можешь немного подробнее?
Ну вот простой пример:

for (...)
{
...
if (...)
s = 1;
}

Пусть этот код выполняется в двух тредах, переменная s — общая, и программист может доказать, что в одном из тредов условие в if (...) всегда false. Тогда, с точки зрения программиста, приведённый псевдокод не содержит race condition относительно s.
Компилятор же, предполагая однопоточное исполнение, строит программисту капкан таким образом:

register r = s;
for (...)
{
...
if (...)
r = 1;
}
s = r;

Откуда ни возьмись, в результате оптимизации появился рейс. Это один из багов в багзилле gcc
>> модель памяти, используемая в стандарте языка Си неявно предполагает однопоточное исполнение
Proving this is left as an exercise to the reader :p

ramses1971

Офигенно, не знал. В таком случае, очень многие многопоточные программы на C содержат рэйсы, и программа, которую ты привел - тоже, потому что это преобразование, согласно стандарту, не меняет результат исполнения программы. Или, правильнее говорить, многопоточный C недостаточно стандартизован.
По-хорошему, нужно чаще ставить volatile.
Оставить комментарий
Имя или ник:
Комментарий: