Динамические алгоритмы планирования со статическими приоритетами

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

Существует 2 распространенных способа назначения приоритетов:

• RMS (rate monotonic scheduling). Правило назначения приоритетов таково: чем меньше период задачи, тем выше у нее приоритет. Иными словами, чем чаще (отсюда rate) задача переходит в состояние готовности, тем ее приоритет выше.

• DMS (deadline monotonic scheduling). В этом алгоритме приоритеты назначаются по немного другому правилу: чем меньше относительный крайний срок задачи, тем выше ее приоритет.

Ниже приведен пример расписания, составленного RMS-планировщиком для синхронной системы 3-х периодических задач со следующими параметрами:

• T₁(3, 0.5)

• T₂(4, 1)

• T₃(6, 2)

• T₁:

• r r r r r

• | | | | |

• ## ## ## ## |

• --+--+--+--+--+--+--+--+--+--+--+--+--+--> t

• 0 1 2 3 4 5 6 7 8 9 10 11 12

• T₂:

• r r r r

• | | | |

• | #### #### #### |

• --+--+--+--+--+--+--+--+--+--+--+--+--+--> t

• 0 1 2 3 4 5 6 7 8 9 10 11 12

• T₃:

• 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-планировщиком для следующей системы задач:

• T₁(3, 0.5)

• T₂(4, 1, 2)

• T₃(6, 2)

Отличие этой системы от предыдущей только в том, что у второй задачи относительный крайний срок не равен периоду, а меньше его в два раза. Согласно правилу назначения приоритетов, самый высокий приоритет будет иметь вторая задача, а самый низкий - третья.

DMS-планировщик для такой системы задач сформирует следующее расписание:

T₁:

r r r r r

| | | | |

| ## ## ## ## |

--+--+--+--+--+--+--+--+--+--+--+--+--+--> t

0 1 2 3 4 5 6 7 8 9 10 11 12

T₂:

r d r d r d r

| | | | | | |

#### | #### | #### | |

--+--+--+--+--+--+--+--+--+--+--+--+--+--> t

0 1 2 3 4 5 6 7 8 9 10 11 12

T₃:

r r r

| | |

##### ## | ##### ## |

--+--+--+--+--+--+--+--+--+--+--+--+--+--> t

0 1 2 3 4 5 6 7 8 9 10 11 12