СРВ    

  Практика ~ 
  Тема 01 ~ 
  Тема 02 ~ 
  Тема 03 ~ 
  Тема 04 ~ 
  Тема 05 ~ 
  Тема 06 ~ 
  Тема 07 ~ 
  Тема 08 ~ 
  Тема 09 ~ 
  Тема 10 ~ 
  Тема 11 ~ 
/Студентам/СРВ/Тема 04

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

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

Далее мы рассмотрим 2 разновидности планировщиков с динамическими приоритетами:

При этом имеются 2 модификации алгоритма EDF:

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

Для алгоритма EDF с вытеснением задач имеет место следующая

Теорема. Алгоритм EDF оптимален для любого набора задач (периодические с любым соотношением между периодами и крайними сроками, спорадические) если:

Доказательство основывается на следующей идее. Если для какого-то набора задач можно составить корректное расписание, то это расписание всегда можно привести к такому виду (и при этом оно останется корректным), что порядок исполнения задач будет таким, какой получился бы при использовании EDF.

Для алгоритма LLF имеет место такая же теорема. Поясним здесь понятие "резерв времени" (laxity).

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

L(t) = (d - t) - e(rem)

Нижеприведенная диаграмма иллюстрирует это понятие:


	  r					  d
	  |					  |
	  #########   #############   #####       * 
	--+---+---+---+---+---+---+---+---+---+---+---+-----> t
	  0   1   2   3   4   5   6   7   8   9   10  11  
d - t :   10  9   8   7   6   5   4   3   2   1   0
e(rem):   6   5   4   4   3   2   1   1   0
Laxity:   444444444...3333333333333...22222....11110

На этой диаграмме показана некая работа какой-то задачи, которая стала готовой в момент времени 0 и имеет крайний срок в момент времени 10. Задача отработала с вытеснениями. Значком "#" отмечены те промежутки времени, когда эта задача исполнялась. Пока задача выполняет свою работу, запас времени остается постоянным, так как уменьшается и время до крайнего срока, и количество времени, которое еше нужно проработать, разумеется, на одну и ту же величину. Если же задача простаивает по причине вытеснения ее другими, более приоритетными задачами, то крайний срок приближается, а время, которое еще нужно проработать, остается постоянным, поэтому в такие промежутки запас времени, естественно, уменьшается.

Для алгоритма EDF БЕЗ вытеснения имеет место следующая

Теорема. Алгоритм EDF без вытеснения НЕоптимален.

Доказать эту теорему можно, приведя один-единственный контр-пример, то есть такой набор задач, для которого, в принципе, можно составить корректное расписание, а алгоритм планирования EDF без вытеснения дает некорректное расписание.

Рассмотрим такой пример. Пусть у нас имеется три задачи со следующими параметрами:

Для данного набора можно составить (неважно, каким именно образом) следующее корректное расписание:


                                                       
  1       2       3                       1       3       2
  *       *       *                       x       x       x
  1111111111111   33333333333333332222222222222222222222222
--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-> t 
  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14

Алгоритм EDF без вытеснения даст следующее расписание (отметим для ясности, что моменты принятия решений планировщиком - это моменты, когда либо появляется задача в состоянии готовности, либо какая-то задача завершает свою очередную работу):


                                                       
  1       2       3                       1       3       2
  *       *       *                       x       x       x
  11111111111122222222222222222222222233333333333333333
--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-> t 
  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14

В момент времени 3 готова только задача 2, поэтому она и выбирается для исполнения и не вытесняется до тех пор, пока полностью не сделает свою работу несмотря на то, что в момент времени 4 в состояние готовности переходит задача номер 3, у которой крайний срок наступает раньше, чем у задачи номер 2. Как видим, из-за этого задача номер 3 пропускает свой крайний срок. Таким образом, алгоритм EDF без вытеснения оптимальным не является.

Для сравнения приведем расписание, которое бы составил EDF-планировщик с возможностью вытеснения задач:


                                                       
  1       2       3                       1       3       2
  *       *       *                       x       x       x
  11111111111122223333333333333333222222222222222222222
--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-> t 
  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14

Как видим, в данном случае все задачи успели завершить свои работы до крайних сроков. В момент времени 2 стала готовой задача 2, но она не вытесняет задачу 1, так как у задачи 2 крайний срок наступает позже, чем у задачи 1. Задача 2 получает управление только в момент времени 3. Но появившаяся в момент времени 4 задача 3 вытесняет задачу 2, так как у задачи 3 крайний срок наступает ранше, чем у задачи 2. В момент времени 8, когда задача 3 завершит свою работу, управление вновь получает задача 2.

Из вышесказанного, однако, не следует делать вывод, что EDF без вытеснения безусловно хуже EDF с вытеснением, поскольку доказательство оптимальности последнего проведено в предположении, что собственно само вытеснение задач (в частности, переключение контекстов) не требует никакого времени, что, подчеркнем еще раз, никак с действительностью не согласуется. Поэтому при анализе алгоритмов планирования нужно учитывать накладные расходы на планирование, например, включать их во времена исполнения задач e.

Для EDF-планировщика с вытеснением имеет место следующее утверждение о проверке системы периодических задач на предмет возможности составления расписания для нее таким планировщиком:

Теорема. Для того, чтобы система {Tj} независимых вытесняемых периодических задач таких, что для любого j имеет место Dj >= pj, была планируема EDF-планировщиком, необходимо и достаточно, чтобы коэффициент использования процессорного времени системы U не превышал единицы.

Если же относительные крайние сроки меньше периодов, то данное условие является необходимым, но не достаточным. Например, система двух задач

T1/p,e,D = 2,1,1.9
и
T2/p,e,D = 2,1,1.9

заведомо не может быть корректно распланирована никаким алгоритмом, хотя U для нее равен единице. Для таких случаев вместо понятия "коэффициент использования процессорного времени" используют понятие "плотность δ задачи", определяемую как

δ = e/min(D,p)

Суммарная плотность системы задач определяется как сумма плотностей всех задач системы:

Δ = ∑δj = ∑ej/min(pj,Dj)

Для систем такого рода имеет место несколько иное утверждение относительно возможности составления корректного расписания:

Теорема. Для того, чтобы система {Tj} независимых вытесняемых периодических задач таких, что для некоторых j имеет место Dj < pj, была планируема EDF-планировщиком, достаточно, чтобы суммарная плотность системы Δ не превышала единицы.

Отметим, что это условие не является необходимым. Это значит, что если оно выполняется, то для системы можно составить корректное расписание; если же это условие не выполняется, то это не значит, что корректное расписание составить нельзя (может быть, можно, а может быть, нельзя - неизвестно).

Пример системы задач, для которой условие Δ <= 1 не выполняется, но корректное расписание существует:

T1(2, 0.6, 1)
T2(5, 2.3)

Для этой системы Δ = 0.6/1 + 2.3/5 = 1.06 > 1, но, тем не менее, корректное расписание составить можно.

Дата последней модификации: 2012-09-19


/Студентам/СРВ/Тема 04

Содержимое данного сайта может быть использовано кем угодно, когда угодно, как угодно и для каких угодно целей. Автор сайта не несёт абсолютно никакой ответственности за землетрясения, наводнения, финансовые кризисы, глобальные потепления/похолодания, разбитые тарелки, зуд/онемение в левой/правой пятке читателя, эпидемии/пандемии свинячьего/птичьего/тараканьего и иных гриппов, а также за прочие негативные, равно как и позитивные, последствия, вызванные прямым или косвенным использованием материалов данного сайта кем бы то ни было, включая самого автора. При копировании/цитировании материалов данного сайта любым технически возможным в настоящее время способом, а также способом, могущим стать возможным в будущем, указание (либо неуказание) ссылки на первоисточник лежит, блин, тяжким грузом на совести копирующего/цитирующего.

Valid HTML 4.0 Strict Valid CSS!