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


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

INSTR I
INSTR I+1
INSTR I+2

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


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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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


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


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

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

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

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

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

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

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

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

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



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

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

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

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

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

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