Круговое планирование: два разных решения — как это возможно?

Проблема:

Пять пакетных заданий от A до E поступают в вычислительный центр почти одновременно. Они оценили время выполнения 10, 6, 2, 4 и 8 минут. Их (определяемые извне) приоритеты равны 3, 5, 2, 1 и 4 соответственно, причем 5 является наивысшим приоритетом. Определить среднее время оборота процесса. Игнорировать накладные расходы на переключение процессов. Для циклического планирования предположим, что система является мультипрограммной и что каждое задание получает свою справедливую долю ЦП. Все задания полностью привязаны к ЦП.

Решение №1 Следующее решение взято из этого страница :

Для циклического перебора в течение первых 10 минут каждое задание получает 1/5 часть ЦП. По истечении 10 минут С финиширует. В течение следующих 8 минут каждое задание получает 1/4 ЦП, после чего время D завершается. Затем каждое из трех оставшихся заданий получает 1/3 процессора на 6 минут, пока B не завершится и так далее. Время завершения пяти заданий составляет 10, 18, 24, 28, 30, в среднем 22 минуты.

Решение №2. Следующее решение предоставлено Корнельским университетом, его можно найти здесь, и явно отличается от предыдущей, хотя задача дана в точно виде (это решение, кстати, имеет больше смысла для меня) :

Помните, что время оборота — это количество времени, которое проходит между поступлением задания и завершением задания. Поскольку мы предполагаем, что все задания поступают в момент времени 0, время оборота будет просто временем их завершения. (a) Циклический алгоритм: в приведенной ниже таблице показано, какие задания будут обрабатываться в течение каждого кванта времени. * указывает, что задание завершается в течение этого такта.

1 2 3 4 5  6 7 8  9 10  11 12 13 14  15 16 17 18  19 20 21  22 23 24  25 26  27 28  29 30  
A B C D E  A B C* D E   A  B  D  E   A  B  D* E   A  B  E   A  B* E   A  E   A  E*  A  A*

Результаты различаются: например, в первом C заканчивает через 10 минут, тогда как во втором C заканчивает через 8 минут.

Какой из них правильный и почему? Я в замешательстве.. Заранее спасибо!


operating-system scheduling round-robin
person Community    schedule 28.03.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

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

person David Schwartz    schedule 28.03.2012
comment
Вы можете предположить (просто ради упражнения), что квант равен 1 минуте. Я знаю, что это нереально, и это должно быть что-то вроде 1 мс, но просто для облегчения вычислений решение, по-видимому, использует 1-минутный квант. Если это так, верно ли второе решение? Что касается 1-го решения, поскольку мы имеем дело не с 1-минутным квантом, почему C завершается через 10 минут, а не через 3 или 2 минуты? Не могли бы вы предоставить мне формулу / рассуждение, которое дает этот результат, чтобы помочь мне понять? - person ; 29.03.2012
comment
Если вы предполагаете 1-минутные кванты, второе решение верно (за исключением того, что оно игнорирует приоритеты, но это уже другая история). Но это необоснованное предположение, и вы не должны его делать, если проблема не говорит об этом. C завершается через 10 минут, потому что ему требуется 2 минуты процессорного времени, и он получает 1/5 часть процессорного времени. Таким образом, требуется 10 минут, чтобы получить 2 минуты процессорного времени. В это время все процессы получили по 2 минуты процессорного времени, и вы можете подсчитать, сколько еще нужно каждому из них. С этого момента они получают 1/4, пока не завершится другой процесс. И так далее. - person David Schwartz; 29.03.2012
comment
В задаче четко указано, что мы должны предположить, что все 5 заданий прибывают почти в одно и то же время. Кроме того, Round Robin не имеет отношения к приоритетам по определению. Однако второе решение, по-видимому, подразумевает некоторый порядок выполнения и прерывания заданий: начиная с A, затем B, затем C, затем D, затем E, затем обратно к A и т. д. Разве это не противоречит тому факту, что все задания поступают вместе (так что никакого порядка не существует) и что RR не навязывает никаких приоритетов? - person ; 29.03.2012
comment
Я согласен. Второе решение, ИМО, действительно странное. - person David Schwartz; 29.03.2012
comment
Что касается решения 1, если бы все задания выполнялись одновременно параллельно, C, очевидно, завершился бы через 2 минуты. Однако он завершается через 10 минут, что означает, что задания выполняются последовательно. Если это так, то возможно, что какое-то другое задание из четырех других выполняется до того, как C будет выполняться каждый раз, когда ему дается его доля процессорного времени, так почему же C завершается через 10 минут, а не через 10 минут + кто знает? -через-сколько минут после 5 работы Алла приехала в центр в первый раз?? - person ; 29.03.2012
comment
Я не понимаю ваших рассуждений. В среднем он получает 1/5 процессора. Поскольку это круговой алгоритм, ЦП чередует задачи, давая каждой очень небольшой квант. C завершит работу, как только пройдёт 2 минуты. Это произойдет через 10 минут плюс-минус квант времени или около того, что намного меньше минуты. (Мы понимаем, что цифры не совсем точны. Мы должны сделать много предположений, например предположить, что переключение задач имеет нулевую стоимость.) Пока все пять задач готовы к запуску, задача C будет получать 1/5 каждой минуты времени. время стены. - person David Schwartz; 29.03.2012
comment
хм.. кажется, я понимаю, что вы имеете в виду.. я понимаю, почему для C потребуется 10 минут, чтобы иметь 2 минуты времени выполнения, но в то же время время движется вперед, поэтому, когда C закончит, время будет 10 минут + время, затраченное друг на друга задачей до сих пор. Но я думаю, основываясь на том, что вы сказали, мы должны игнорировать это время (и я говорю не о времени переключения задач, а о фактическом времени выполнения другой задачи до завершения C. - person ; 29.03.2012
comment
И последнее, что касается второго решения: если я хочу использовать квант для своего RR (скажем, 50 мс..), поскольку все задания поступают почти в одно и то же время, с чего мне начать? Какая работа идет первой, затем какая вторая и т. д., чтобы я мог рассчитать время, необходимое для завершения каждой? Выполняется ли A в течение 50 мс, затем B в течение 50 мс, затем E, затем C, затем D, затем обратно в A или это ACBED или EDCBA и т. д....?? - person ; 29.03.2012
comment
Когда C закончит, время будет 10 минут. C получит ЦП на 2 из этих 10 минут. Другие задачи получат процессор на оставшиеся 8 минут. Это время уже истекло на отметке 10 минут. (Мы понятия не имеем, в каком порядке выполняются задачи или как долго они выполняются без прерывания, но нам все равно. Все дело в накладных расходах на переключение задач, которые мы должны игнорировать. Таким образом, мы можем действовать так, как если бы они выполнялись одновременно. ) - person David Schwartz; 29.03.2012
comment
Я только что прочитал ваше редактирование относительно 2-го решения. Итак, если все задания должны поступать одновременно и не заданы приоритеты, то 2-е решение практически невозможно применить, верно? (если только мы не предполагаем произвольно, что порядок ABCDE). - person ; 29.03.2012
comment
Да, это должно быть секретное соглашение. - person David Schwartz; 29.03.2012
comment
Большое спасибо, Давид, ты очень помог! :) - person ; 29.03.2012
comment
Что произойдет, если в первом решении указан квант (скажем, 50 мс)? Как будет выглядеть решение? - person ; 29.03.2012
comment
Первое решение было бы таким же, если бы вы не предполагали определенный порядок задач (как это было сделано во втором). - person David Schwartz; 29.03.2012

arrow_upward
0
arrow_downward

На самом деле не существует такого понятия, как «правильный» алгоритм RR. RR — это просто семейство алгоритмов, основанных на общей концепции планирования нескольких задач в циклическом порядке. Реализации могут различаться (например, вы можете учитывать приоритеты задач или отбрасывать их, или вы можете вручную установить приоритет в зависимости от длины задачи или что-то еще).

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

person iehrlich    schedule 28.03.2012