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

[RobFPGA]

Приветствую!

Скорее всего он "разводил" Вас с результатами работы программы пытаясь понять насколько Вы разбираетесь в принципах функционирования RTOS.
Суда по результатам анализа - "развод" ему удался
Поскольку трудно себе представить RTOS планировщик которой работает после каждой инструкции CPU.

Успехов! Rob.

[Fat Robot]

Переменная count не является volatile, поэтому предположение о том, во что компилируется count++ неверно.
Далее в связи с этим совершенно непонятно, во что вся эта милая конструкция превратилась после оптимизатора.

Проверял ли задающий вопрос правильность работы железа? Таблицы размещения? Может у него сегмент data размещен в непотребном месте. И далее в таком вот духе..

В общем "почему неправльно написанная программа работает неправильно?" В интервью это называется open-ended question. Ответ на такой вопрос не обязательно должен быть правильным. Он должен показать ход ваших мыслей и/или дать потенциальному работодателю формальный повод для отказа ("он ответил так, а надо было сяк").

Не переживайте. Кстати, какой результат в итоге? Сделали вам предложение?

[wangan]

Может у него был 8 битный микроконтроллер, а у него count типа int. Пока один меняет один полубайт, то другой поток меняет другой полубайт.

Принимайте меня на работу, а то я немогу найти работу в своем городе.

[gerber]

Неправильно реализована функция printf на железке, а точнее stdout.
В терминал отправляется правильное число 25 и приложение тут же завершается.
В сдвиговый регистр (если терминал на COM-порте) только и успели положить один символ "2", и пока этот символ выдвигался в линию - приложение закрылось, закрыв за собой все открытые устройства, и терминал в том числе, очистив при этом передающий буфер.

Сообщение отредактировал gerber - Jul 31 2014, 13:44

[Mahagam]

Неправильно реализована функция printf на железке, а точнее stdout.
В терминал отправляется правильное число 25 и приложение тут же завершается.
В сдвиговый регистр (если терминал на COM-порте) только и успели положить один символ "2", и пока этот символ выдвигался в линию - приложение закрылось, закрыв за собой все открытые устройства, и терминал в том числе, очистив при этом передающий буфер.

похоже. только а) принтф может стоять и тупить пока всё не отправится. б) не согласовывается с уточнением, что результат не зависит от числа потоков и величины фора. а там не 25 может получится, а и 80, к примеру.

[Lagman]

25. Почему? Патамушта! (кооперативная, вытесняющая, гибридная) Патамушта! (возьмете, расскажу )

[InsolentS]

Прошу прощения, по условиям задачи RTOS вытесняющая, процессор 32бит, count++ компилируется именно в те 3 ассемблерные команды, которые приведены и дело точно не в printf. Даже ежу понятно, что этот код никуда не годится, так не делают и т.п. Но вопрос был именно почему работа определённой программы приводит к определённому результату, шаг за шагом..

Кстати, какой результат в итоге? Сделали вам предложение?

Жду..

[ViKo]

Для начала неплохо бы понять, в какой ОС есть функция thread_join() и как она работает.

[InsolentS]

Для начала неплохо бы понять, в какой ОС есть функция thread_join() и как она работает.

Это условная RTOS. thread_join() просто ждёт пока все потоки завершатся

[Fedor]

Нагло врет ваш интервьюер, если поток будет 1 все будет нормально ))))

[DASM]

99.9 % дело не вытеснении, на 32 разрядном проце каждая такая задача, уверен, успеет завершится, прежде чем будет вытеснена. Что и подтвердил мой комп - 25 ответ . Хотя код еще некорректен еще и потому, что счетчик не объявлен как volatile (а это, на самом деле, обязательно, только сегодня обсуждали на работе). Но причина вывода "2", вряд ли в этом. Хотя несколько забавно просить найти ошибку в псевдокода с псевдооперационкой. А может оператор ++ где-то переопределен как "присвоить 2" ?

Переменная count не является volatile, поэтому предположение о том, во что компилируется count++ неверно.
Далее в связи с этим совершенно непонятно, во что вся эта милая конструкция превратилась после оптимизатора.

Совершенно верно

[ViKo]

Условная ОС не может быть проверена в железе, как сказано в первом сообщении.

[InsolentS]

Тут дело не в особенностях какого-то конкретного железа или RTOS (как кстати частота тиков планировщика связана с разрядностью процессора?). Есть определённая последовательность действий, которая в итоге приводит к результату 2. Какие это могут быть действия описаны в листинге в условии задачи. Тут вопрос исключительно на логику.

Условная ОС не может быть проверена в железе, как сказано в первом сообщении.

Не уклоняйтесь от решения задачи, вдруг тоже такое когда-нибудь попадётся

[ViKo]

Тут вопрос исключительно на логику.
Не уклоняйтесь от решения задачи, вдруг тоже такое когда-нибудь попадётся

А разве можно решить нерешаемое?

[adnega]

Подсказка от интервьювера: результат не зависит ни от количества потоков, ни от количества итераций в цикле for

А если потоков 0?
А если потоков 1, а итераций 0?

Резальтат, равный 2, печатается постоянно или нужно объяснить ситуацию с крайне низкой вероятностью, когда печатается 2 ?

[ZASADA]

что возвращает вызываемая функция
void thread(void)

[ViKo]

что возвращает вызываемая функция
void thread(void)

разве не "ничего"?

[DASM]

А какой это язык программирования ?

[ZASADA]

типа с

[InsolentS]

На работу всё-таки взяли, попробую найти там этого интервьювера и докопаться до истины..

[x893]

Всё гораздо проще - просто посмотрите дебаггером - всё зависит от оптимизации - и ваш интервьюер просто не сказал вам все данные. но если добавить volatile - проблем бы было меньше. Это называется - срубить не разбираясь. Если вы сразу не задали вопрос про оптимизацию и volatile - значит понимания нет - а код тут не при чем

[InsolentS]

Всё гораздо проще - просто посмотрите дебаггером - всё зависит от оптимизации - и ваш интервьюер просто не сказал вам все данные. но если добавить volatile - проблем бы было меньше. Это называется - срубить не разбираясь. Если вы сразу не задали вопрос про оптимизацию и volatile - значит понимания нет - а код тут не при чем

Спасибо за участие в обсуждении)) Но, мне кажется, что дело не в этом совершенно. Задача имеет чисто алгоритмическое, логическое решение. Результат и решение не имеют привязки к аппаратной платформе, компилятору, оптимизатору и т.п. Этот код предоставлен as-is и вопрос не в том, как сделать из него нормальный код (кстати, если бы переменная была volatile, это разве что-нибудь бы поменяло?).

[psL]

Типа ОСь очень реального времени Видимо 2, потому что первый поток из пула успевает инкрементировать счетчик, поскольку пока еще нет потоков, способных ему помешать, последний поток из пула инкрементирует счетчик, поскольку потоки, способные ему помешать уже завершились.

[Lagman]

Типа ОСь очень реального времени Видимо 2, потому что первый поток из пула успевает инкрементировать счетчик, поскольку пока еще нет потоков, способных ему помешать, последний поток из пула инкрементирует счетчик, поскольку потоки, способные ему помешать уже завершились.

Планировщик переключает задачи после каждой инструкции!?

[psL]

Планировщик переключает задачи после каждой инструкции!?

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

[andrew_b]

А разве можно решить нерешаемое?

— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.

[AlexandrY]

Спасибо за участие в обсуждении)) Но, мне кажется, что дело не в этом совершенно. Задача имеет чисто алгоритмическое, логическое решение. Результат и решение не имеют привязки к аппаратной платформе, компилятору, оптимизатору и т.п. Этот код предоставлен as-is и вопрос не в том, как сделать из него нормальный код (кстати, если бы переменная была volatile, это разве что-нибудь бы поменяло?).

Похоже алгоритмического решения не будет.
Интернет не знает таких функций как thread_create(thread, 5) и thread_join() с такими типами аргументов, а потому потом можно будет грузить на их счет все что угодно.
Это подстава.

Можно предположить, что имелись в виду POSIX функции pthread_create и pthread_join, но они не умеют работать без аргументов и с массивами потоков.

[kolobok0]

Планировщик переключает задачи после каждой инструкции!?

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

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

[AlexandrY]

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

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

Что это за загадочная "синхронная фаза"?

Если код основан на POSIX, то можно кое что восстановить.

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

Рассматриваем что могло быть на реальном железе:

До вытеснения тут явно не дойдет. Тик осей редко бывает короче 10 мс.
Значит вся работа задач начнется после вызова thread_join
Без аргументов thread_join не бывает, возможно это переопределение оригинальной функции и в этой реализации ожидание всех задач производится по очереди с помощью семафоров.
Но возможно реализован механизм ожидания маски флагов от всех задач сразу.
В любом случае задачи выполнятся последовательно не вытесняя друг друга, поскольку имеют одинаковый приоритет.
Случится прерыванию во время выполнения тех задач крайне мала, поскольку все задачи выполнятся менее чем за микросекунду.

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

И тогда произойдет неожиданный выход из thread_join.
Далее заход в функцию printf и там возможно где-то ось не на долго переключится на одну из оставшихся активных задач во время ожидания прерывания по готовности чего-то периферийного.
Вот тут и успеет какая-то из задач инкрементировать count до прерывания и переключения контекста на драйвер printf.

Во всяком случае у меня аналогичный код под MQX работает идеально при любом уровне оптимизации и всегда выдает 25

Код

const TASK_TEMPLATE_STRUCT  MQX_template_list[] =
{
  /* Task Index,    Function,                 Stack,  Priority,          Name,         Attributes,                                                         Param, Time Slice */
  { MAIN_IDX,        Main_task,                1500,   MAIN_ID_PRIO,      "Main",      MQX_FLOATING_POINT_TASK + MQX_AUTO_START_TASK,                       0,     0 },
  { TST_TSK_IDX,     Test_Task,                1500,   MAIN_ID_PRIO,      "TestTask",  MQX_FLOATING_POINT_TASK,                                             0,     0 },
  { 0 }
};

unsigned int count = 0;

LWEVENT_STRUCT lwevg;

/*-------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------*/
void Test_Task(unsigned int initial_data)
{
  unsigned int i;
  for(i = 0; i < 5; i++)
  {
    count++;
  }
  _lwevent_set(&lwevg, initial_data);
}
/*-------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------*/
void Main_task(unsigned int initial_data)
{
  _lwevent_create(&lwevg, LWEVENT_AUTO_CLEAR);

  _task_create(0, TST_TSK_IDX, 1);
  _task_create(0, TST_TSK_IDX, 2);
  _task_create(0, TST_TSK_IDX, 4);
  _task_create(0, TST_TSK_IDX, 8);
  _task_create(0, TST_TSK_IDX, 16);

  _lwevent_wait_for(&lwevg, 1+2+4+8+16,TRUE,NULL);
  printf("Count =%u  \r\n", count);
}

[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]

В реальности, естественно, переключать контекст после каждой инструкции накладно

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

[Mahagam]

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

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

[AndrewN]

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

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

[Mahagam]

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

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

[AndrewN]

Да и планировщик у вас совершенно нереалистичный.
Здесь главное назвать алгоритм планировщика

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

[AlexandrY]

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

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

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

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

[AndrewN]

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

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

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

[AlexandrY]

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

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

[AndrewN]

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

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

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

[AlexandrY]

Мы же не знаем, какие есть в выч. системе ещё задачи, на какие прерывания система должна реагировать. Всё это создаёт хаос.

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

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

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

[AndrewN]

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

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

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

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

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

[ViKo]

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

[AlexandrY]

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

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

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

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

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

[AndrewN]

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

Да, в условии явно это не сказано, но подразумевается достаточно определённо - из семантики вызовов create(). Однако же окружение модельной задачи остаётся полностью неопределённым и неизвестным. Отсюда и хаос и индетерминизм. А планировщик может использовать совершенно детерминированный алгоритм, реального времени в том числе. В РТОСе я чюдеса всякие и наблюдал...

трудно себе представить RTOS планировщик которой работает после каждой инструкции CPU.

К вопросу о прерываниях. Может ли последовательность инструкций

INSTR I
INSTR I+1
INSTR I+2

быть прервана подряд на каждой инструкции - т.е. три раза подряд. Да элементарно может. Это только кажется, что между ними (инструкциями) время обратное частоте ЦПУ, и, соответственно, бешеная частота потока прерываний. Так бы было без прерываний. А нужно учитывать время, потраченное на обработку прерывания в ISR, на последующий вызов драйвера или приоритетной задачи - в итоге частота прерываний невелика, а процесс прерывается на каждой инструкции. Или, поскольку прерывания распределены по времени _неравномерно_ (как-то по пуассону, грубо говоря, или по бернулли), то через неопределённое число инструкций, но в том числе и через раз и через два и через три...

Но вопрос был задан так, что результат 2 получается обязательно.

Я надеюсь, что нет, не обязательно. Иначе экзаменатора действительно надо казнить тяжёлым шершавым холодным мьютексом...

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

[Mahagam]

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

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

[AlexandrY]

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

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

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

[AndrewN]

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

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

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

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

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

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

[Mahagam]

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

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

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

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

[AlexandrY]

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

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

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

[den_po]

Тик вытиснения!
Задачи не вытисняются на любом прерывании, а только по тику. Иначе это уже не 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

[AlexandrY]

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

Нет уж, здесь честная битва телепатов.

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

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

Да, теперь красиво.

[adnega]

CODE

задача А задача В задача Х
| LDR \ 1| LDR [0] | LDR \
3| ADD } x (COUNT-1) | ADD [1] 2| ADD } x COUNT
| STR / | STR /
4| STR [1]
5| LDR [1]
| ADD [2] | LDR \
6| ADD } x (COUNT-1)
7| STR [2] | STR /

где цифра слева от вертикальной черты номер в очереди исполнения.
Удачные пять вытеснений и реультат 2 может быть получен.
2 и 3 могут выполнятся в любой последовательности (в том числе и внутри).
Головоломка имеет очень далекое отношение к реальной системе, т.к. вероятность очень мала.
При увеличении COUNT и числа задач вероятность события "=2" стремится к вероятности события
"все молекулы контроллера полетели в одном направлении, и контроллер оказался на Луне".

[Mahagam]

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

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

[AndrewN]

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

А ещё лучше принтфом прикинуться, и как только видишь, что экзаменатор count собрался печатать, так сразу хлобысь и печатаешь двойку (болдом!) :-) И переменную портить не надо - наследить лишний раз...

[juvf]

аш 4 страници настучали....
1) а кто пробовал это на реальном железе реализовать? может и вправду 2 будет. дебагом пошагаете, истину увидите

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

[AlexandrY]

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

Хм, в MQX это не сработает.
Там задача с планировщиком round robin не отдаст таким же другим задачам управление пока не кончится ее time slice.
Но правда time slice считается не как общее время работы задачи, а как общее время ее активности (и в ожидании в том числе) поэтому это время все может быть занято более приритетными задачами.
Вот тут и возникнет эффект как-бы вытеснения задачами друг друга в round robin планировщике.
Т.е. time slice надо как раз уменьшать чтобы на результат более вероятно повлияли сторонние приоритетные задачи в системе.

[AndrewN]

Жаль, что не удалось узнать, что думает экзаминатор по поводу своей задачи... ОР молчит...

[InsolentS]

Жаль, что не удалось узнать, что думает экзаминатор по поводу своей задачи... ОР молчит...

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