|
Хитровывернутый вопрос про RTOS, с интервью.. |
|
|
|
Jul 31 2014, 01:00
|

Местный
  
Группа: Свой
Сообщений: 414
Регистрация: 8-06-06
Пользователь №: 17 897

|
Всем привет! Недавно был на интервью в одной компании и "застрял" на вопросе про 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
--------------------
Курильщик даташитов со стажем
|
|
|
|
|
 |
Ответов
(30 - 44)
|
Aug 5 2014, 09:57
|
Местный
  
Группа: Участник
Сообщений: 336
Регистрация: 7-03-07
Из: Петербург
Пользователь №: 25 961

|
QUOTE (InsolentS @ Jul 31 2014, 04:00)  Недавно был на интервью в одной компании и "застрял" на вопросе про 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. Очевидно, что это вполне практическая задача, такой результат может быть получен (и будет получен! при достаточно большом числе запусков) на практике. QUOTE (adnega @ Aug 1 2014, 08:59)  Резальтат, равный 2, печатается постоянно или нужно объяснить ситуацию с крайне низкой вероятностью, когда печатается 2 ? Абсолютное заблуждение. _Все_ возможные (см. выше) результаты равновероятны. Чем 2 хуже 7 или 16?
Сообщение отредактировал AndrewN - Aug 5 2014, 09:52
|
|
|
|
|
Aug 5 2014, 10:01
|

Ally
     
Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050

|
Цитата(AndrewN @ Aug 5 2014, 12:31)  P.S. Очевидно, что это вполне практическая задача, такой результат может быть получен (и будет получен! при достаточно большом числе запусков) на практике. Да, но условием было получить всегда 2 А тут у вас что угодно может получится. Где детерминизм получения 2 на реальном железе? Да и планировщик у вас совершенно нереалистичный. Здесь главное назвать алгоритм планировщика. В RTOS совершенно нормальная практика зная алгоритм планировщика не защищать переменные критическими секциями. Поскольку постановка простейшего семафора может длиться в десять раз дольше чем сама предметная часть задачи, что есть очень дорого.
|
|
|
|
|
Aug 5 2014, 10:04
|
Местный
  
Группа: Участник
Сообщений: 336
Регистрация: 7-03-07
Из: Петербург
Пользователь №: 25 961

|
QUOTE (psL @ Aug 4 2014, 00:53)  В реальности, естественно, переключать контекст после каждой инструкции накладно Ключевое, фундаментальное заблуждение. В реальности может быть _всё что угодно_. В том числе, если внешняя ситуация такова, то смена контекста может происходить на каждой инструкции. Чем эти инструкции так выделены? Ничем. Что мешает контекст переключить, если есть необходимость? Ничего. Что мы знаем о внешнем окружении экзаменационной задачи? Ничего.
|
|
|
|
|
Aug 5 2014, 10:04
|
Местный
  
Группа: Свой
Сообщений: 322
Регистрация: 2-07-04
Из: Minsk
Пользователь №: 240

|
QUOTE (AndrewN @ Aug 5 2014, 12:31)  Хорошая задачка на индетерминизм в системе конкурирующих процессов. Решается элементарно! Я удивлён, что ещё никто не догадался... решение правдоподобное, вот только мне непонятен в этом случае механизм работы планировщика. почему он вначале гоняет все задачи кроме двух? почему задача А то исполняется почти вся, то времени ей выделяется только на две команды? аналогично выделяется времени только на одну команду в задаче Б. это вот как?
|
|
|
|
|
Aug 5 2014, 10:07
|
Местный
  
Группа: Участник
Сообщений: 336
Регистрация: 7-03-07
Из: Петербург
Пользователь №: 25 961

|
QUOTE (AlexandrY @ Aug 5 2014, 13:01)  Да, но условием было получить всегда 2 Да бросьте вы. И близко не было такого в условии. Для меня совершенно очевидно (как и для экзаменатора), что такой результат (2) может быть получен только благодаря фундаментальному индетерминизму задачи.
|
|
|
|
|
Aug 5 2014, 10:09
|
Местный
  
Группа: Свой
Сообщений: 322
Регистрация: 2-07-04
Из: Minsk
Пользователь №: 240

|
QUOTE (AndrewN @ Aug 5 2014, 13:04)  Ключевое, фундаментальное заблуждение. В реальности может быть _всё что угодно_. В том числе, если внешняя ситуация такова, то смена контекста может происходить на каждой инструкции. Чем эти инструкции так выделены? Ничем. Что мешает контекст переключить, если есть необходимость? Ничего. Что мы знаем о внешнем окружении экзаменационной задачи? Ничего. это только в альтернативной реальности такое может быть. придумайте правдоподобную внешнюю ситуацию, которая приводит к такому странному переключению контекста задач.
|
|
|
|
|
Aug 5 2014, 10:09
|
Местный
  
Группа: Участник
Сообщений: 336
Регистрация: 7-03-07
Из: Петербург
Пользователь №: 25 961

|
QUOTE (AlexandrY @ Aug 5 2014, 13:01)  Да и планировщик у вас совершенно нереалистичный. Здесь главное назвать алгоритм планировщика Вы меня пугаете... Нет у меня никакого планировщика, я знать не знаю как он работает и какой у него алгоритм. Вся прелесть этой задачи в том, что это знать абсолютно не нужно!
|
|
|
|
|
Aug 5 2014, 10:14
|

Ally
     
Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050

|
Цитата(AndrewN @ Aug 5 2014, 13:07)  Да бросьте вы. И близко не было такого в условии. Для меня совершенно очевидно (как и для экзаменатора), что такой результат (2) может быть получен только благодаря фундаментальному индетерминизму задачи. Если бы "экзаминатор" не заикнулся о том, что видел это на живом железе, то никаких претензий. Если он действительно видел, то сами понимаете, ваша версия не выдерживает никакой критики. Что есть доля микросекунды против тика вытеснения в 10 мс? Это вероятность меньше 0.0001 , а для последовательных таких событий еще меньше. Если считать существенными такие вероятности то должны рухнуть все быза данных и реестр вашего компьютера поскольку они тоже построенны на случайно генерируемых индексах.
|
|
|
|
|
Aug 5 2014, 10:15
|
Местный
  
Группа: Участник
Сообщений: 336
Регистрация: 7-03-07
Из: Петербург
Пользователь №: 25 961

|
QUOTE (Mahagam @ Aug 5 2014, 13:04)  решение правдоподобное, вот только мне непонятен в этом случае механизм работы планировщика. почему он вначале гоняет все задачи кроме двух? почему задача А то исполняется почти вся, то времени ей выделяется только на две команды? аналогично выделяется времени только на одну команду в задаче Б. это вот как? Это приемлемый вопрос. Так происходит (ну или может произойти) из-за неизвестного _внешнего_ окружения нашей задачи. Мы же не знаем, какие есть в выч. системе ещё задачи, на какие прерывания система должна реагировать. Всё это создаёт хаос. А мы в этой мутной воде выуживаем, что нам надо. Задача ставилась на определение последовательности пропихивания наших ниточек так, что бы в итоге получился определённый результат = 2. Ну вот в такой последовательности, например, их можно пропихнуть. На практике она осуществима. Ну а уж сколько надо этого знаменательного события ждать - пока рак на горе не свистнет :-)
|
|
|
|
|
Aug 5 2014, 10:21
|
Местный
  
Группа: Участник
Сообщений: 336
Регистрация: 7-03-07
Из: Петербург
Пользователь №: 25 961

|
QUOTE (AlexandrY @ Aug 5 2014, 13:14)  Если бы "экзаминатор" не заикнулся о том, что видел это на живом железе, то никаких претензий. Я нечто подобное (и множество других, не менее любопытных ситуаций) видел своими глазами. Это мир параллельных процессов, здесь всё не так, как кажется и как нам говорит последовательный, фон-неймановский, опыт. Ваши цифры комментировать не хочу, ведь на самом деле мы сейчас обсуждали задачку из учебника - по программированию параллельных систем. Ну чего меня разубеждать в школьном материале?
|
|
|
|
|
Aug 5 2014, 10:24
|

Ally
     
Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050

|
Цитата(AndrewN @ Aug 5 2014, 13:15)  Мы же не знаем, какие есть в выч. системе ещё задачи, на какие прерывания система должна реагировать. Всё это создаёт хаос. Тик вытиснения! Задачи не вытисняются на любом прерывании, а только по тику. Иначе это уже не RTOS. Прерывания никакого хаоса в RTOS не вызывают. Цитата(AndrewN @ Aug 5 2014, 13:21)  Я нечто подобное (и множество других, не менее любопытных ситуаций) видел своими глазами. Это все из-за плохо портированых осей.
|
|
|
|
|
Aug 5 2014, 10:27
|
Местный
  
Группа: Участник
Сообщений: 336
Регистрация: 7-03-07
Из: Петербург
Пользователь №: 25 961

|
QUOTE (AlexandrY @ Aug 5 2014, 13:19)  Мне кажется вы подстраивайте условия под ответ. Планировщик это главное в RTOS. Байки про то что все может быть прервано и вытеснено в любом порядке никто в жизни не применяет. А то сейчас я вспомню мультиядерность и кэширование и таких версий наворочу... :biggrin: Совершенно справедливо, я подстраиваю условия под ответ - в этом-то и состояло задание, найти условия, при которых получим двойку в счётчике. Остальное - no comments. QUOTE (AlexandrY @ Aug 5 2014, 13:24)  Тик вытиснения! Задачи не вытисняются на любом прерывании, а только по тику. Иначе это уже не RTOS. Прерывания никакого хаоса в RTOS не вызывают. Простите, но это я точно комментировать не хочу. Могу написать в личку, но не интересно. Почитайте учебники по preemptive systems.
|
|
|
|
|
Aug 5 2014, 10:31
|

Ally
     
Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050

|
Цитата(AndrewN @ Aug 5 2014, 13:24)  Совершенно справедливо, я подстраиваю условия под ответ - в этом-то и состояло задание, найти условия, при которых получим двойку в счётчике.
Остальное - no comments. Да, вообщем верно. Но я бы этого "экзаминатора" ...  Цитата(AndrewN @ Aug 5 2014, 13:27)  Простите, но это я точно комментировать не хочу. Могу написать в личку, но не интересно. Почитайте учебники по preemptive systems. Напомню, что говорили о задачах с равным приоритетом.
|
|
|
|
|
  |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|