andrewn 0 5 августа, 2014 Опубликовано 5 августа, 2014 (изменено) · Жалоба говорили о задачах с равным приоритетомДа, в условии явно это не сказано, но подразумевается достаточно определённо - из семантики вызовов create(). Однако же окружение модельной задачи остаётся полностью неопределённым и неизвестным. Отсюда и хаос и индетерминизм. А планировщик может использовать совершенно детерминированный алгоритм, реального времени в том числе. В РТОСе я чюдеса всякие и наблюдал... трудно себе представить RTOS планировщик которой работает после каждой инструкции CPU. К вопросу о прерываниях. Может ли последовательность инструкций INSTR I INSTR I+1 INSTR I+2 быть прервана подряд на каждой инструкции - т.е. три раза подряд. Да элементарно может. Это только кажется, что между ними (инструкциями) время обратное частоте ЦПУ, и, соответственно, бешеная частота потока прерываний. Так бы было без прерываний. А нужно учитывать время, потраченное на обработку прерывания в ISR, на последующий вызов драйвера или приоритетной задачи - в итоге частота прерываний невелика, а процесс прерывается на каждой инструкции. Или, поскольку прерывания распределены по времени _неравномерно_ (как-то по пуассону, грубо говоря, или по бернулли), то через неопределённое число инструкций, но в том числе и через раз и через два и через три... Но вопрос был задан так, что результат 2 получается обязательно.Я надеюсь, что нет, не обязательно. Иначе экзаменатора действительно надо казнить тяжёлым шершавым холодным мьютексом... Изменено 5 августа, 2014 пользователем AndrewN Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Mahagam 0 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба Это приемлемый вопрос. Так происходит (ну или может произойти) из-за неизвестного _внешнего_ окружения нашей задачи. Мы же не знаем, какие есть в выч. системе ещё задачи, на какие прерывания система должна реагировать. Всё это создаёт хаос. А мы в этой мутной воде выуживаем, что нам надо. какое, блеать, неизвестное внешнее окружение? в первом посте приведена функция main. из неё видно, что кроме энного количества потоков вычисления счётчика не запущено ровным счётом ничего. читайте по буквам: Николай, Иван, Харитон, Ульяна Яков. Ни один вменяемый планировщик не будет переключать задачи так хаотично как вам бы хотелось. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AlexandrY 3 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба какое, блеать, неизвестное внешнее окружение? в первом посте приведена функция main. из неё видно, что кроме энного количества потоков вычисления счётчика не запущено ровным счётом ничего. читайте по буквам: Николай, Иван, Харитон, Ульяна Яков. Ни один вменяемый планировщик не будет переключать задачи так хаотично как вам бы хотелось. Чес говоря, я припоминаю тот учебник. Кажется это был сам Кнут, где приводились такие абсурдные ситуации с многопоточностью, но на машинах с придуманым ассемблером. Но если исходить из того что "'экзаминатор" был провокатором, то версия "хаотичного" планировщика тоже могла быть упомянута. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andrewn 0 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба Ни один вменяемый планировщик не будет переключать задачи так хаотично как вам бы хотелось.Это была всего лишь экзаменационная задача... А планировщик - это Я. :-) приведена функция main. из неё видно, что кроме энного количества потоков вычисления счётчика не запущено ровным счётом ничего. Увы, задачи по параллельным процессам так не формулируются. Есть процессы, которы формируются явно, исходя из условий задачи. И, кроме этого, неявно предполагается, что в вычислительной системе есть внешние, неизвестные процессы, которые занимают время ЦПУ, но не взаимодействуют с процессами задачи. Алгоритм планировщика предполагается неизвестным, и более того, предполагается недетерминистским. Т.е. никак нельзя сказать в каком порядке могут быть спланированы два равноприоритетных процесса. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Mahagam 0 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба Увы, задачи по параллельным процессам так не формулируются. Есть процессы, которы формируются явно, исходя из условий задачи. И, кроме этого, неявно предполагается, что в вычислительной системе есть внешние, неизвестные процессы, которые занимают время ЦПУ, но не взаимодействуют с процессами задачи. Алгоритм планировщика предполагается неизвестным, и более того, предполагается недетерминистским. Т.е. никак нельзя сказать в каком порядке могут быть спланированы два равноприоритетных процесса. вы точно про RTOS?? точно про микроконтроллеры?? какой нафик, "недетерминистским" планировщик в RTOS?? да он в большинстве случаев вообще в исходниках идёт. и его поведение прозрачно аки слезинка ребёнка. какие нафик неизвестные процессы в МК ? попривыкали к глючному линуксу, который может "недетерминированно" тупануть, и теперь переносите свои влажные фантазии в мир нормальных RTOS. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AlexandrY 3 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба Алгоритм планировщика предполагается неизвестным, и более того, предполагается недетерминистским. Т.е. никак нельзя сказать в каком порядке могут быть спланированы два равноприоритетных процесса. Кстати, а как же эта подсказка "результат не зависит ни от количества потоков, ни от количества итераций в цикле for" Даже при "хаотичном" планировщике мы бы увидели корреляцию. А тут нет, не зависит. Рискну предположить что с увеличением конкурентов и с увеличением количества циклов средняя величина получаемого результата при "хаотичном" планировщике будет стремиться к увеличению, а не концентрироваться вокруг двойки. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
den_po 0 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба Тик вытиснения! Задачи не вытисняются на любом прерывании, а только по тику. Иначе это уже не RTOS. Прерывания никакого хаоса в RTOS не вызывают. Например обработчик прерывания может принудительно разблокировать ожидающую задачу с большим чем у текущей приоритетом, и в этом нет криминала. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andrewn 0 5 августа, 2014 Опубликовано 5 августа, 2014 (изменено) · Жалоба вы точно про RTOS?? точно про микроконтроллеры?? какой нафик, "недетерминистским" планировщик в RTOS?? да он в большинстве случаев вообще в исходниках идёт. и его поведение прозрачно аки слезинка ребёнка. какие нафик неизвестные процессы в МК ? Неизвестные процессы не в МК, а в условии исходной задачи. Они, естественно, не заданы, но их присутствие в выч. системе, естественно, неявно подразумевается. Кроме всего прочего, термин МК в условиях не фигурирует. Я попытался пересчитать решение для детерминистского алгоритма планировщика, такого, который бы без оговорок мог использоваться в RTOS. Для preemptive round robin для равноприоритетных процессов планировки решение абсолютно возможное (feasible). Ход своих рассуждений опускаю, они очевидные. попривыкали к глючному линуксу, который может "недетерминированно" тупануть, и теперь переносите свои влажные фантазии в мир нормальных RTOS. Об ослинуксе не было ни слова. Насчет "[...] фантазий" - полегче на поворотах, почтеннейший, не в рыбной лавке. Кстати, а как же эта подсказка "результат не зависит ни от количества потоков, ни от количества итераций в цикле for" Даже при "хаотичном" планировщике мы бы увидели корреляцию. А тут нет, не зависит. Рискну предположить что с увеличением конкурентов и с увеличением количества циклов средняя величина получаемого результата при "хаотичном" планировщике будет стремиться к увеличению, а не концентрироваться вокруг двойки. Я эту подсказку воспринял в смысле, что двойку можно получить (не обязательно получить, а возможно) независимо от числа процессов и независимо от числа итераций. В моём решении это явно видно: три процесса стартуют и завершаются ни на что не влияя, остальные два явно используют отсылку только к первой итерации, предпоследней итерации и последней итерации. А статистику копить - такого в условии не было. Пока даже предположить не берусь, какое было бы распределение результатов и как оно зависисело бы от загрузки выч. системы. Гипотетически - распределение скорее всего равномерное. Ребята, а дайте мне грант на месяц (пару миллионов сов. рупий) и я это поисследую :-) Изменено 5 августа, 2014 пользователем AndrewN Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AlexandrY 3 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба Я попытался пересчитать решение для детерминистского алгоритма планировщика, такого, который бы без оговорок мог использоваться в RTOS. Для preemptive round robin для равноприоритетных процессов планировки решение абсолютно возможное (feasible). Ну очень интересно, как это из изначально последовательно поставленных в круг N задач остаются только две одна из которых не получила времени когда все остальные выполнились. Это уже никак не round-robin планирование. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andrewn 0 5 августа, 2014 Опубликовано 5 августа, 2014 (изменено) · Жалоба Ну очень интересно, как это из изначально последовательно поставленных в круг N задач остаются только две одна из которых не получила времени когда все остальные выполнились. Это уже никак не round-robin планирование. RR это, RR. Посмотрите на 1) в решении - А и В прочитали нулевой счётчик. И встали в хвост. А потом три пробежали до упора. P.S. Для ясности облегчу себе участь - скажем, что тайм-слайс очень большой. И только внешние события, над которыми у нас власти нет, заставляют планировщик менять задачи. И, если задача прерывается, то планировщик ставит её в хвост. Изменено 5 августа, 2014 пользователем AndrewN Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AlexandrY 3 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба Ребята, а дайте мне грант на месяц (пару миллионов сов. рупий) и я это поисследую :-) Нет уж, здесь честная битва телепатов. :smile3009: RR это, RR. Посмотрите на 1) в решении - А и В прочитали нулевой счётчик. И встали в хвост. А потом три пробежали до упора. P.S. Для ясности облегчу себе участь - скажем, что тайм-слайс очень большой. И только внешние события, над которыми у нас власти нет, заставляют планировщик менять задачи. И, если задача прерывается, то планировщик ставит её в хвост. Да, теперь красиво. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
adnega 11 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба задача А задача В задача Х | 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 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба Неизвестные процессы не в МК, а в условии исходной задачи. Они, естественно, не заданы, но их присутствие в выч. системе, естественно, неявно подразумевается. Кроме всего прочего, термин МК в условиях не фигурирует. с такими условиями я тогда выдаю самое достоверное решение: один из неизвестных процессов, который неявно подразумевается, отследил что завершились все вычислительные потоки и нагло вставил в переменную двойку прям под носом у принтфа. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andrewn 0 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба отследил что завершились все вычислительные потоки и нагло вставил в переменную двойку прям под носом у принтфа.А ещё лучше принтфом прикинуться, и как только видишь, что экзаменатор count собрался печатать, так сразу хлобысь и печатаешь двойку (болдом!) :-) И переменную портить не надо - наследить лишний раз... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
juvf 17 5 августа, 2014 Опубликовано 5 августа, 2014 · Жалоба аш 4 страници настучали.... 1) а кто пробовал это на реальном железе реализовать? может и вправду 2 будет. дебагом пошагаете, истину увидите 2) я думаю это задача без правильного ответа. она расчитана на то, чтобы заставить кондидата мыслить и попытаться найти решение, тем самым интервьювер узнает насколько кондидать владеет темой. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться