Хитровывернутый вопрос про 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

[AlexandrY]

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

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

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

[AndrewN]

Да, но условием было получить всегда 2

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

[AlexandrY]

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

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

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

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

[AndrewN]

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

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

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