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

[psL]

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

[Lagman]

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

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

[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);
}