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

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

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

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

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

• T₁(3, 0.5)
• T₂(4, 1)
• T₃(6, 2)

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

• T₁(3, 0.5)
• T₂(4, 1, 2)
• T₃(6, 2)

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

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 задач

• T₁(2, 1)
• T₂(5, 2.5)

Коэффициент использования процессорного времени для данной системы равен единице, следовательно, корректное расписание для данной системы существует. Вот такое расписание:

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 порождают некорректное расписание, что и доказывает утверждение теоремы.

Определение.
Система {T_j} периодических задач называется системой с простой периодичностью, если для любой пары T_i, T_k (при этом p_i < p_k) имеет место равенство p_k mod p_i = 0. Иными словами, периоды всех задач системы попарно делятся нацело друг на друга.

Например, система

• T₁(2, 1)
• T₂(4, 1)
• T₃(8, 1)

есть система с простой периодичностью, а система

• T₁(2, 1)
• T₂(5, 1)
• T₃(10, 1)

таковой не является (5 mod 2 = 1 # 0).

Для систем с простой периодичностью имеет место следующая

Теорема.
Система {T_j} независимых вытесняемых задач с простой периодичностью с периодами, не превышающими относительные крайние сроки планируется на одном процессоре тогда и только тогда, когда коэффициент использования процессорного времени этой системы не превышает единицы.

Доказательство.
....

Для систем с произвольными соотношениями между периодами задач имеет место следующая теорема (критерий проверки планируемости системы алгоритмом RMS):

Теорема.
Система {T_j} n независимых вытесняемых периодических задач с периодами, равными относительным крайним срокам, планируется на одном процессоре _если_ коэффициент использования процессорного времени этой системы не превышает величины U_RM = n(2^1/n - 1).

Это условие является достаточным, но не необходимым.

Дата последней модификации: 2009-07-25