Хитровывернутый вопрос про RTOS, с интервью.. Опции

[InsolentS]

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

Код

unsigned int count = 0;
void thread(void)
{
  unsigned int i;
  for(i = 0; i < 5; i++)
  {
    count++;
  }
}

void main(void)
{
  thread_create(thread, 5); // Создаём 5 экземпляров потока thread и запускаем их
  thread_join(); // Ждём пока все 5 потоков завершатся
  printf("%u", count); // Выводим значение count на экран
}

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

Код

  LDR reg, count
  ADD reg, #1
  STR reg, count

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

Код

// начало работы thread1
  LDR reg, count // count = 0, thread1.reg = 0
  ADD reg, #1 // thread1.reg = 1
// thread1 вытеснен планировщиком, начало работы thread2
  LDR reg, count // count = 0, thread2.reg = 0
  ADD reg, #1 // thread2.reg = 1
  STR reg, count // count = 1
// thread2 завершил работу, управление возвращается к thread1
  STR reg, count // count = 1

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

[AndrewN]

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

Как же получается 2? (со слов интервьювера, он наблюдал такой эффект в реальном железе). Подсказка от интервьювера: результат не зависит ни от количества потоков, ни от количества итераций в цикле for

Задача имеет чисто алгоритмическое, логическое решение.

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

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

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

CODE

  LDR reg, count
  ADD reg, #1
  STR reg, count

отсюда же видно, что операция модификации счётчика неатомарна, а состоит из трёх фаз, каждая из которых может быть прервана. Вот на этом игра с планированием задач и может быть построена.
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, печатается постоянно или нужно объяснить ситуацию с крайне низкой вероятностью, когда печатается 2 ?

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


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

[Mahagam]

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

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

[AndrewN]

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

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

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

[Mahagam]

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

какое, блеать, неизвестное внешнее окружение? в первом посте приведена функция main. из неё видно, что кроме энного количества потоков вычисления счётчика не запущено ровным счётом ничего. читайте по буквам: Николай, Иван, Харитон, Ульяна Яков. Ни один вменяемый планировщик не будет переключать задачи так хаотично как вам бы хотелось.

[AndrewN]

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

Это была всего лишь экзаменационная задача...

А планировщик - это Я. :-)

приведена функция main. из неё видно, что кроме энного количества потоков вычисления счётчика не запущено ровным счётом ничего.

Увы, задачи по параллельным процессам так не формулируются. Есть процессы, которы формируются явно, исходя из условий задачи. И, кроме этого, неявно предполагается, что в вычислительной системе есть внешние, неизвестные процессы, которые занимают время ЦПУ, но не взаимодействуют с процессами задачи.

Алгоритм планировщика предполагается неизвестным, и более того, предполагается недетерминистским. Т.е. никак нельзя сказать в каком порядке могут быть спланированы два равноприоритетных процесса.

[Mahagam]

Увы, задачи по параллельным процессам так не формулируются. Есть процессы, которы формируются явно, исходя из условий задачи. И, кроме этого, неявно предполагается, что в вычислительной системе есть внешние, неизвестные процессы, которые занимают время ЦПУ, но не взаимодействуют с процессами задачи.

Алгоритм планировщика предполагается неизвестным, и более того, предполагается недетерминистским. Т.е. никак нельзя сказать в каком порядке могут быть спланированы два равноприоритетных процесса.

вы точно про RTOS?? точно про микроконтроллеры??
какой нафик, "недетерминистским" планировщик в RTOS?? да он в большинстве случаев вообще в исходниках идёт. и его поведение прозрачно аки слезинка ребёнка. какие нафик неизвестные процессы в МК ?

попривыкали к глючному линуксу, который может "недетерминированно" тупануть, и теперь переносите свои влажные фантазии в мир нормальных RTOS.

[AndrewN]

вы точно про RTOS?? точно про микроконтроллеры??
какой нафик, "недетерминистским" планировщик в RTOS?? да он в большинстве случаев вообще в исходниках идёт. и его поведение прозрачно аки слезинка ребёнка. какие нафик неизвестные процессы в МК ?

Неизвестные процессы не в МК, а в условии исходной задачи. Они, естественно, не заданы, но их присутствие в выч. системе, естественно, неявно подразумевается. Кроме всего прочего, термин МК в условиях не фигурирует.

Я попытался пересчитать решение для детерминистского алгоритма планировщика, такого, который бы без оговорок мог использоваться в RTOS. Для preemptive round robin для равноприоритетных процессов планировки решение абсолютно возможное (feasible). Ход своих рассуждений опускаю, они очевидные.

попривыкали к глючному линуксу, который может "недетерминированно" тупануть, и теперь переносите свои влажные фантазии в мир нормальных RTOS.

Об ослинуксе не было ни слова. Насчет "[...] фантазий" - полегче на поворотах, почтеннейший, не в рыбной лавке.

Кстати, а как же эта подсказка "результат не зависит ни от количества потоков, ни от количества итераций в цикле for"
Даже при "хаотичном" планировщике мы бы увидели корреляцию. А тут нет, не зависит.

Рискну предположить что с увеличением конкурентов и с увеличением количества циклов средняя величина получаемого результата при "хаотичном" планировщике будет стремиться к увеличению, а не концентрироваться вокруг двойки.

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

А статистику копить - такого в условии не было. Пока даже предположить не берусь, какое было бы распределение результатов и как оно зависисело бы от загрузки выч. системы.

Гипотетически - распределение скорее всего равномерное. Ребята, а дайте мне грант на месяц (пару миллионов сов. рупий) и я это поисследую :-)

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

[AlexandrY]

Я попытался пересчитать решение для детерминистского алгоритма планировщика, такого, который бы без оговорок мог использоваться в RTOS. Для preemptive round robin для равноприоритетных процессов планировки решение абсолютно возможное (feasible).

Ну очень интересно, как это из изначально последовательно поставленных в круг N задач остаются только две одна из которых не получила времени когда все остальные выполнились.
Это уже никак не round-robin планирование.

[AndrewN]

Ну очень интересно, как это из изначально последовательно поставленных в круг N задач остаются только две одна из которых не получила времени когда все остальные выполнились.
Это уже никак не round-robin планирование.

RR это, RR. Посмотрите на 1) в решении - А и В прочитали нулевой счётчик. И встали в хвост. А потом три пробежали до упора.

P.S. Для ясности облегчу себе участь - скажем, что тайм-слайс очень большой. И только внешние события, над которыми у нас власти нет, заставляют планировщик менять задачи. И, если задача прерывается, то планировщик ставит её в хвост.

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