Всем привет!
Недавно был на интервью в одной компании и "застрял" на вопросе про RTOS. После недели поисков ответ так и не был найден..
Условие задачи такое: есть 5 потоков, каждый из них увеличивает в цикле общую переменную count на 1. После завершения работы этих потоков, значение count выводится на экран.

Внимание вопрос: почему программа печатает 2??
Договорились с интервьювером, что операция count++ состоит из 3х ассемблерных команд:

Т.к. переменная count не защищена ни мьютексом, ни критической секцией, самый пессимистичный вариант, который я "раскрутил" выглядит так:

т.е. в результате один поток делает override результата второго потока и count = 1 после выполнения всех потоков (а не 5, как было бы с мьютексом).
Но: хоть один из потоков все равно увеличит count на 1 в этой схеме, т.е. в результате работы программы count будет не меньше, чем 5.
Как же получается 2? (со слов интервьювера, он наблюдал такой эффект в реальном железе). Подсказка от интервьювера: результат не зависит ни от количества потоков, ни от количества итераций в цикле for

Хорошая задачка на индетерминизм в системе конкурирующих процессов. Решается элементарно! Я удивлён, что ещё никто не догадался...

Сначала несколько замечаний:

a) результат не зависит ни от количества потоков (> 2), ни от количества итераций в цикле for (> 2)
b) задача на алгоритм планировщика очевидно (count ничем не защищён), поэтому планируем задачи как нам _надо_ (кстати, в реальном железе такой алгоритм (или стратегия) планировщика вполне возможна)
c) атрибут volatile конечно хорошо помянуть, но совершенно необязательно, поскольку из условия известно, что перед модификацией значение счётчика всегда читается (что эквивалентно volatile):

отсюда же видно, что операция модификации счётчика неатомарна, а состоит из трёх фаз, каждая из которых может быть прервана. Вот на этом игра с планированием задач и может быть построена.
d) Решение для значения count = 2, легко обобщается для произвольного значения count, от 2 до суммы инкрементов (каждая задача может совершать произвольное число итераций в цикле)

Алгоритмов, естественно, несколько. Например так:

1) Выбираем произвольно две задачи, А и В.
Каждая читает начальное значение счётчика = 0 и
ставится в ожидание на инструкции ADD.

2) Ждём когда завершатся остальные N-2 задач.
Они больше не нужны, на решение не влияют.

3) Задача В инкрементирует регистр (reg = 1) и
ставится в ожидание на инструкции STR.

4) Задача А продолжает работу и ставится в
ожидание на _последней_ итерации _перед_
инструкцией LDR.

5) Задача В исполняет инструкцию STR
(записывает в ячейку count 1) и ставится в
ожидание.

6) Задача А исполняет инструкцию LDR. В
регистре значение = 1. Инкрементирует
значение регистра = 2 и ставится в ожидание
на инструкции STR.

7) Задача В продолжает работу до завершения!
(Блин, наконец-то, надоело!)

8) Задача А исполняет инструкцию STR, записывает
в ячейку count 2. И завершается! (Блин, наконец-то,
ну жуть как надоело!)

------

Уфф... Очевидно, что розыгрышей в планировании вспомогательной В и остальных N-2 задач может быть несколько, соответственно и алгоритмов решения тоже много. 3) можно "растянуть" объединив с STR, так, что бы в итоге получалось 3, 4, ...

P.S. Очевидно, что это вполне практическая задача, такой результат может быть получен (и будет получен! при достаточно большом числе запусков) на практике.


Абсолютное заблуждение. _Все_ возможные (см. выше) результаты равновероятны. Чем 2 хуже 7 или 16?


Сообщение отредактировал AndrewN - Aug 5 2014, 09:52

Да, но условием было получить всегда 2
А тут у вас что угодно может получится. Где детерминизм получения 2 на реальном железе?
Да и планировщик у вас совершенно нереалистичный.
Здесь главное назвать алгоритм планировщика.

В RTOS совершенно нормальная практика зная алгоритм планировщика не защищать переменные критическими секциями.
Поскольку постановка простейшего семафора может длиться в десять раз дольше чем сама предметная часть задачи, что есть очень дорого.

Ключевое, фундаментальное заблуждение. В реальности может быть _всё что угодно_. В том числе, если внешняя ситуация такова, то смена контекста может происходить на каждой инструкции. Чем эти инструкции так выделены? Ничем. Что мешает контекст переключить, если есть необходимость? Ничего. Что мы знаем о внешнем окружении экзаменационной задачи? Ничего.

решение правдоподобное, вот только мне непонятен в этом случае механизм работы планировщика.
почему он вначале гоняет все задачи кроме двух?
почему задача А то исполняется почти вся, то времени ей выделяется только на две команды? аналогично выделяется времени только на одну команду в задаче Б. это вот как?

Да бросьте вы. И близко не было такого в условии. Для меня совершенно очевидно (как и для экзаменатора), что такой результат (2) может быть получен только благодаря фундаментальному индетерминизму задачи.

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

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

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

Что есть доля микросекунды против тика вытеснения в 10 мс? Это вероятность меньше 0.0001 , а для последовательных таких событий еще меньше.

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

Это приемлемый вопрос. Так происходит (ну или может произойти) из-за неизвестного _внешнего_ окружения нашей задачи. Мы же не знаем, какие есть в выч. системе ещё задачи, на какие прерывания система должна реагировать. Всё это создаёт хаос. А мы в этой мутной воде выуживаем, что нам надо.

Задача ставилась на определение последовательности пропихивания наших ниточек так, что бы в итоге получился определённый результат = 2. Ну вот в такой последовательности, например, их можно пропихнуть. На практике она осуществима. Ну а уж сколько надо этого знаменательного события ждать - пока рак на горе не свистнет :-)

Мне кажется вы подстраивайте условия под ответ. Планировщик это главное в RTOS.
Байки про то что все может быть прервано и вытеснено в любом порядке никто в жизни не применяет.
А то сейчас я вспомню мультиядерность и кэширование и таких версий наворочу...

Я нечто подобное (и множество других, не менее любопытных ситуаций) видел своими глазами. Это мир параллельных процессов, здесь всё не так, как кажется и как нам говорит последовательный, фон-неймановский, опыт.

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

Тик вытиснения!
Задачи не вытисняются на любом прерывании, а только по тику. Иначе это уже не RTOS.
Прерывания никакого хаоса в RTOS не вызывают.



Это все из-за плохо портированых осей.

Совершенно справедливо, я подстраиваю условия под ответ - в этом-то и состояло задание, найти условия, при которых получим двойку в счётчике.

Остальное - no comments.


Простите, но это я точно комментировать не хочу. Могу написать в личку, но не интересно. Почитайте учебники по preemptive systems.

Ну, теоретически (практически тоже) можно допустить, что тактовая частота процессора 1 Гц. И задачи переключаются после каждой команды.
Но вопрос был задан так, что результат 2 получается обязательно. А для этого необходимо слишком странная последовательность выполнения задач.

Да, вообщем верно. Но я бы этого "экзаминатора" ...



Напомню, что говорили о задачах с равным приоритетом.