Напомним, что принцип работы любого планировщика на основании приоритета состоит в том, что в каждый момент времени исполняется та задача, которая имеет наивысший приоритет. В случае динамических планировщиков со статическими приоритетами задач приоритет задачи, будучи однажды ей назначен, не изменяется с течением времени. Рассматриваемые далее способы назначения приоритетов ориентированы на системы периодических задач.
Существует 2 распространенных способа назначения приоритетов:
Ниже приведен пример расписания, составленного RMS-планировщиком для синхронной системы 3-х периодических задач со следующими параметрами:
T1: r r r r r | | | | | ## ## ## ## | --+--+--+--+--+--+--+--+--+--+--+--+--+--> t 0 1 2 3 4 5 6 7 8 9 10 11 12 T2: r r r r | | | | | #### #### #### | --+--+--+--+--+--+--+--+--+--+--+--+--+--> t 0 1 2 3 4 5 6 7 8 9 10 11 12 T3: r r r | | | ##### ## | ##### ## | --+--+--+--+--+--+--+--+--+--+--+--+--+--> t 0 1 2 3 4 5 6 7 8 9 10 11 12
В соответствии с вышеприведенным правилом самый высокий приоритет имеет первая задача, а самый низкий - третья. В момент времени 0 имеется 3 готовых задачи, процессорное время получает первая. В момент времени 0.5 готовы 2 задачи (2 и 3), управление получает вторая. В момент времени 3 снова становится готовой первая задача, поэтому третья ею вытесняется. В момент времени 3.5 управление вновь получает третья задача как единственно готовая. В момент времени 4.0 готова только задача 2, она и получает управление. В момент времени 6 готовы 2 задачи (1 и 3), управление отдается первой. Далее работает третья задача, но в момент времени 8 она вытесняется второй. В момент 9 опять готова первая задача, она отрабатывает и, наконец, в момент 9.5 получает управление третья задача. Затем все повторяется сначала (при условии, разумеется, что число задач в системе остается неизменным).
Пример расписания, составленного DMS-планировщиком для следующей системы задач:
Отличие этой системы от предыдущей только в том, что у второй задачи относительный крайний срок не равен периоду, а меньше его в два раза. Согласно правилу назначения приоритетов, самый высокий приоритет будет иметь вторая задача, а самый низкий - третья.
DMS-планировщик для такой системы задач сформирует следующее расписание:
T1: r r r r r | | | | | | ## ## ## ## | --+--+--+--+--+--+--+--+--+--+--+--+--+--> t 0 1 2 3 4 5 6 7 8 9 10 11 12 T2: r d r d r d r | | | | | | | #### | #### | #### | | --+--+--+--+--+--+--+--+--+--+--+--+--+--> t 0 1 2 3 4 5 6 7 8 9 10 11 12 T3: r r r | | | ##### ## | ##### ## | --+--+--+--+--+--+--+--+--+--+--+--+--+--> t 0 1 2 3 4 5 6 7 8 9 10 11 12
По поводу обеих рассматриваемых правил назначения приоритетов имеет место следующая теорема:
Теорема.
Алгоритмы DMS и RMS не являются оптимальными.
Доказательство.
Рассмотрим систему 2 задач
Коэффициент использования процессорного времени для данной системы равен единице, следовательно, корректное расписание для данной системы существует. Вот такое расписание:
T1: r r r r r r | | | | | | #### #### | ####| #### #### --+--+--+--+--+--+--+--+--+--+--+--+-> t 0 1 2 3 4 5 6 7 8 9 10 11 12 T2: r r r | | | | #### ######|###### #### | --+--+--+--+--+--+--+--+--+--+--+--+-> t 0 1 2 3 4 5 6 7 8 9 10 11 12
Алгоритм же RMS (равно как и DMS) сгенерирует для этой системы следующее расписание:
T1: r r r r r r | | | | | | #### #### #### | | | --+--+--+--+--+--+--+--+--+--+--+--+-> t 0 1 2 3 4 5 6 7 8 9 10 11 12 T2: r r r | | | | #### #### xx | --+--+--+--+--+--+--+--+--+--+--+--+-> t 0 1 2 3 4 5 6 7 8 9 10 11 12
Как видно, задача 2 пропустила свой крайний срок. Таким образом, существует, по крайней мере, одна система задач, для которой корректное расписание существует, а алгоритмы RMS/DMS порождают некорректное расписание, что и доказывает утверждение теоремы.
Определение.
Система {Tj} периодических задач называется системой
с простой периодичностью, если для любой пары Ti,
Tk (при этом pi < pk)
имеет место равенство pk mod pi = 0.
Иными словами, периоды всех задач системы попарно делятся нацело
друг на друга.
Например, система
есть система с простой периодичностью, а система
таковой не является (5 mod 2 = 1 # 0).
Для систем с простой периодичностью имеет место следующая
Теорема.
Система {Tj} независимых вытесняемых задач
с простой периодичностью с периодами, не превышающими
относительные крайние сроки планируется на одном
процессоре тогда и только тогда, когда коэффициент
использования процессорного времени этой системы не
превышает единицы.
Доказательство.
....
Для систем с произвольными соотношениями между периодами задач имеет место следующая теорема (критерий проверки планируемости системы алгоритмом RMS):
Теорема.
Система {Tj} n независимых вытесняемых периодических задач
с периодами, равными относительным
крайним срокам, планируется на одном процессоре _если_
коэффициент использования процессорного времени этой системы не
превышает величины URM = n(21/n - 1).
Это условие является достаточным, но не необходимым.
Дата последней модификации: 2009-07-25