[andrewn 0]

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

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

 

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

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

 

INSTR I

INSTR I+1

INSTR I+2

 

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

 

 

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

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

Изменено 5 августа, 2014 пользователем AndrewN

[Mahagam 0]

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

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

 

 

[AlexandrY 3]

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

 

Чес говоря, я припоминаю тот учебник.

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

 

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

[andrewn 0]

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

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

 

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

 

 

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

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

 

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

 

[Mahagam 0]

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

 

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

 

вы точно про RTOS?? точно про микроконтроллеры??

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

 

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

[AlexandrY 3]

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

 

 

Кстати, а как же эта подсказка "результат не зависит ни от количества потоков, ни от количества итераций в цикле for"

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

 

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

[den_po 0]

Тик вытиснения!

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

Прерывания никакого хаоса в RTOS не вызывают.

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

[andrewn 0]

вы точно про RTOS?? точно про микроконтроллеры??

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

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

 

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

 

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

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

 

Кстати, а как же эта подсказка "результат не зависит ни от количества потоков, ни от количества итераций в цикле for"

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

 

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

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

 

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

 

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

Изменено 5 августа, 2014 пользователем AndrewN

[AlexandrY 3]

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

 

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

Это уже никак не round-robin планирование.

[andrewn 0]

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

Это уже никак не round-robin планирование.

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

 

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

Изменено 5 августа, 2014 пользователем AndrewN

[AlexandrY 3]

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

 

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

 

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

 

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

 

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

[adnega 11]

 задача А               задача В    задача Х
 | 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 0]

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

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

[andrewn 0]

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

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

 

[juvf 10]

аш 4 страници настучали....

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

 

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