Может ли многопоточная программа быть детерминированной?

Question

Обычно говорят, что многопоточные программы недетерминированы, а это означает, что в случае сбоя будет почти невозможно воссоздать ошибку, вызвавшую условие.Никто даже не знает, какой поток будет запущен следующим, и когда он снова будет вытеснен.

Конечно, это связано с алгоритмом планирования потоков ОС и тем фактом, что никто не знаеткакой поток будет запущен следующим, и как долго он будет работать эффективно.Порядок выполнения программы также играет свою роль, и т.д ...

Но что, если бы у вас был алгоритм, используемый для планирования потоков, и что, если бы вы могли знать, когда какой поток выполняется, многопоточная программа могла бы стать"детерминированный", например, вы сможете воспроизвести сбой?

Answer 1

Знание алгоритма не позволит вам предсказать, что произойдет, когда.Все виды задержек, возникающих при выполнении программы или потока, зависят от условий среды (свободная оперативная память -> подкачка, другие занятые задачи, поступающие прерывания и т. Д.).

Если вы должны отобразитьмногопоточная программа для последовательного выполнения, и ваши потоки сами по себе являются детерминированными в своем поведении, тогда вся ваша программа может быть детерминированной и проблемы «параллелизма» могут быть воспроизведены.Конечно, в этот момент у них больше не будет проблем с параллелизмом.

Если вы хотите узнать больше, http://en.wikipedia.org/wiki/Process_calculus - очень интересное чтение.

Answer 2

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

Answer 3

Можно было бы запустить программу на виртуальной многопоточной машине, где распределение виртуальных циклов для каждого потока было выполнено через какой-то полностью детерминированный процесс, возможно, с использованием псевдослучайного генератора (который можно было бы засечь с помощью константы перед каждым запуском программы). Другая, возможно, более интересная, возможность состояла бы в том, чтобы иметь виртуальную машину, которая переключалась бы между запущенными потоками в режиме «разбрызгивания» (где почти любая переменная, к которой они прикасались, имела бы значение, неизвестное другим потокам) и режиме «очистки» ( где результаты операций с известными операндами будут видны и известны другим потокам). Я ожидаю, что ситуация, вероятно, будет несколько аналогична аппаратному моделированию: если выход каждого шлюза рассматривается как «неизвестный» между его минимальным и максимальным временем распространения, но моделирование работает в любом случае, это хороший признак того, что конструкция надежна, но Есть много полезных конструкций, которые не могут быть сконструированы для работы в таких симуляциях (состояния будут гарантированно превращаться в действительную комбинацию, хотя нельзя гарантировать, какая из них). Тем не менее, это может быть интересный путь исследования, поскольку большая часть многих программ может быть написана для правильной работы даже в виртуальной машине с «режимом разбрызгивания».

Answer 4

Существуют некоторые инструменты (в разработке), которые попытаются создать условия гонки несколько предсказуемым образом, но речь идет о перспективном тестировании, а не о восстановлении «ошибки в дикой природе».

ШАХМАТ является примером.

Answer 5

Множество сбоев в многопоточных программах не имеют ничего общего с самой многопоточностью (или с конфликтом ресурсов).

Answer 6

Я не думаю, что это практически осуществимо.Для принудительного чередования определенного потока нам необходимо установить блокировки на общие переменные, чтобы потоки обращались к ним в определенном порядке.Это может привести к серьезному снижению производительности.

Воспроизведение ошибок параллелизма обычно обрабатывается системами записи и воспроизведения.Поскольку запись такого большого количества информации также снижает производительность, самые последние системы выполняют частичное ведение журнала, а затем завершают чередование потоков, используя SMT-решение.Я считаю, что самым последним достижением в этом типе систем является симбиоз (опубликованный на конференции PLDI этого года).В этом URL можно найти реализации с открытым исходным кодом:

http://www.gsd.inesc -id.pt / ~ nmachado / software / Symbiosis_Tutorial.html

Answer 7

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

Я полностью не согласен с этим, конечно, многопоточные программы недетерминированы, но в то же время однопоточные, учитывая пользовательский ввод, прокачку сообщений, работу с мышью / клавиатурой и многие другие факторы. Многопоточная программа обычно затрудняет воспроизведение ошибки, но определенно не невозможна. По каким-то причинам выполнение программы не является полностью случайным, есть некоторая повторяемость (но не предсказуемость), я обычно могу довольно быстро воспроизводить многопоточные ошибки в своих приложениях, но тогда у меня есть много подробных входов в мои приложения действия конечных пользователей.

Кроме того, если вы получаете сбои, разве вы не можете получить журналы сбоев с информацией о стеке вызовов? Это очень поможет в процессе отладки.