На главную | Содержание | Назад | Вперёд
Наши друзья

 

 

Построение и использование эффективных приоритетных расписаний

Основы построения приоритетных расписаний
Основные понятия
Идея рассматриваемого подхода состоит в реализации дисциплин обслу­живания реального времени с передачей прав по расписанию (ДОР), по средством смены относительных приоритетов (ДООП) по расписанию.
При этом система должна быть построена таким образом, чтобы в лю­бой момент времени /, относительный приоритет (ОП) не мог совпасть у заявок из нескольких очередей. Если данное условие не будет выпол­нено, то в системе неминуем конфликт при занятии ресурса, т.к. несколь­ко абонентов одновременно получат право занять ресурс после его осво­бождения.
Для описания ДООП используем матрицу приоритетов (МП), пред­ставляющую собою квадратную матрицу Q = [д„] размерности МхМ по числу М абонентов. Элемент матрицы gv задает ОП заявки / по отношению кj (здесь и далее имеется в виду очередь или, соответ­ственно, класс заявок): «О» — нет приоритета, «1» — есть приоритет. Например, первая строка первой таблицы «0111» означает, что пер­вая заявка имеет более высокий приоритет чем вторая, третья и чет­вертая заявки. Для описания ДОР (в общем случае ДОСП) исполь­зуем граф изменения матрицы ОП в моменты времени ts — моменты занятия ресурса в соответствии с расписанием.
На рис 18.3 представлен пример графа бесприоритетной ДОР, реали­зуемой методом динамической смены ОП, для случая М = 4 , цикл рас­писания которой имеет вид. Соответственно, в каждый мо­мент времени состояние системы описывается своей МП.
Бесприоритетность расписания обеспечивается тем, что каждый абонент входит в расписание равное число раз. Причем это число в общем слу­чае может быть более одного, например.
Требования к матрице приоритетов
Элементы МП должны удовлетворять следующим требованиям:
* = т.к. между заявками одного класса не могут быть установле­ны приоритеты;
» если </,v = 1 , то = 0 , т.е., если заявки класса имеют приоритет по отношению к заявкам класса j, то последние не могут иметь приори­тет по отношению к заявкам /;
* в матрице приоритетов не должны совпасть любые две строки любые два столбца у, /« i = \,...,М, 1*т, /,/= l,-,M, j */.
В графе смены МП (в цикле расписания), по крайней мере, по одному разу должны присутствовать МП, задающие высший ОП каждого из М классов заявок.
Правило высших относительных приоритетов
Для реализации приоритетной ДОР в цикле расписания по крайней мере двум классам заявок высший относительный приоритет должен присва­иваться различное число раз, например (1, 2, 1, 3, 1, 4).
В противном случае получим совпадение значений т.е. при совпа­дении значений параметров Тфя получаем равный приоритет заявок - -совпадают ТгрСт.
Правило изменения относительных приоритетов
Изменение ОП заявок по расписанию в процессе функционирования системы должно быть реализовано по следующему правилу.
Относительные приоритеты (ОП) в рамках ДОР однозначно задаются рас­писанием, где в каждый момент времени t, приоритет заявок соответ­ствует порядку передачи полномочий, исключая повторные передачи прав одной очереди в цикле ОР (эта возможность реализуется изменением длины кванта времени). Например, для расписания (1,2, 1, 3) в момент времени tl — ОП [1, 2, 3], в момент времени t2 — [2, 1, 3], в момент времени t} - [1, 3, 2], в tt - [3, 1, 2].
Для дисциплин обслуживания с динамическими ОП, изменяемыми по рас­писанию, функция изменения приоритета заявки т, т = \...,М имеет вид:
= ««Л S Г < fm) + ny^j ,d = \,...,G) ,
где: ои - - исходный ОП заявки поступающей в момент t", соответству­ющий 5-му состоянию цикла расписания, длиной G: t, s = l,...,G ;
&<xmd — приращение приоритета заявки, получаемое при смене состо­яний цикла расписания t, d = \...,G (может иметь отрица­тельные значения).
Для заявок, обслуживаемых с ОП, для V/rf, Дос^ =0 и для Vr" = t„, s = l,...,G, ams = const.
Режимы использования относительного приоритета
Рассмотренный подход позволяет комбинировать в одной системе обслу­живание заявок и по расписаниям и с относительным приоритетом (по­средством смены относительных приоритетов). Естественно, что если какой-либо заявке относительный приоритет не изменять в процессе функционирования системы, то запросы данной заявки будут тем самым исключены из расписания. В дальнейшем будем обозначать дисциплину осблуживания со смешанными приоритетами (относительного и реаль­ного времени) квадратными скобками.
Можно выделить два режима использования относительного приори­тета, которые определяются его отношением к приоритетам реально­го времени:
Первый режим предполагает задание относительного приоритета за­явки относительно заявок, обслуживаемых в реальном времени, на­пример. Данный режим может выделяться для внеочер-
дного обслуживания каких-либо заявок (в нашем примере заявка 1
всегда приоритетнее, чем заявки 2, 3, 4, которые обслуживаются меж­ду собой по бесприоритетному расписанию).
Этот режим может использоваться для задания относительного при­оритета задаче, осуществляющей диспетчеризацию заявок. » Второй режим предполагает задание относительного приоритета зая­вок реального времени относительно остальных заявок, например (в нашем примере заявка 4 всегда менее приоритетна,
чем заявки 1, 2, 3, которые обслуживаются между собой по бесприо­ритетному расписанию).
Данный режим может выделяться для фонового обслуживания каких-либо заявок (в нашем примере заявка 4 будет обслуживаться в фоно­вом режиме, например, в фоновом режиме могут обслуживаться заяв­ки приложений).
Теоретические основы синтеза приоритетных расписаний
Детерминированная задача синтеза расписаний реального времени
Выше отмечалось, что под приоритетным понимается расписание, в цикле которого различные классы или очереди заявок встречаются различное чис­ло раз. Возникает вопрос сравнения между собой приоритетных расписаний
с целью выработки требований к их оптимальности. Например, рассмотрим два расписания (1, 1, 2, 3) и (1, 2, 1, 3). В обоих расписаниях первый абонент имеет более высокий приоритет (в 2 раза чаще встречается в цикле, чем вто­рой и третий абоненты). Возникает вопрос — одинаковы или различны эти расписания с точки зрения эффективности их применения в системах реаль­ного времени. Попытаемся проанализировать данный вопрос и выработать требования к оптимальному приоритетному расписанию [22].
Пусть имеем R различных приоритетов заявок в системе, обслуживаемых по расписанию. Соответственно, г = \,...,R, и Мг заявок имеют равный г приоритет mr = l,...,Mr: 5m _m. = 1, тг * т'г, тг,т'г = \,...,МГ. Таким об­разом, система содержит М очередей заявок, которым соответствует R уровней приоритетов.
Детерминированная задача синтеза расписаний реального времени мо­жет быть сформулирована следующим образом : М\\\Т01Пг -^шах, Т„т, ^Тгоп,,, mr = \,...,Mr,r = \,...,R, где T0„r - характеристика обслужи­вания очереди заявок приоритета, - ограничение, накла­дываемое на время обслуживания заявки системой, функционирующей
в реальном масштабе времени.
Оптимальное приоритетное расписание и радиальный граф
С учетом сформулированной задачи синтеза расписаний реального вре­мени дадим определение канонического (в данном случае — оптималь­ного) расписания.
Под каноническим (оптимальным) расписанием будем понимать расписа­ние, обеспечивающее минимальные значения характеристик в рам­ках заданного разбиения М классов заявок на R уровней приоритета, получаемое поочередной передачей прав очередям заявок в рамках ра­диального графа.
Под радиальным графом передачи прав понимается граф, удовлетворяю­щий следующим условиям:
» Этот граф содержит М, вершин приоритета r, r = \,...,R, причем в каждую вершину нижестоящего приоритета входит только одна дуга от одной вершины вышестоящего приоритета.
♦ Из каждой вершины всех приоритетов, кроме R-ro, выходит | М,,,/Л/,.| дуг, где [а] — есть большее целое числа а.
* Все вершины приоритета R соединяются дугой с вершиной приорите­та 1 (из вершин R выходит только одна дуга) — в этом случае дуга направлена в сторону вершины 1, в то время как в остальных случаях дуга направлена в вершину, соответствующую очереди заявки с более низким приоритетом.
Радиальный граф передачи прав представлен 4.
Радиальный граф, у которого по крайней мере одна вершина (не Я-ю) уровня приоритета соединена только с одной вершиной приоритета уров­ня г + 1, назовем вырожденным. Соединение двух вершин одной дугой является альтернативным способом задания равного приоритета двум абонентам системы. Под предельно вырожденным понимаем граф, в ко­тором из каждой вершины только одна дуга выходит и в каждую верши­ну только одна дуга входит — этот граф задает бесприоритетное распи­сание, соответствующее обслуживанию в циклическом порядке.
Радиальный граф с поочередной передачей прав
Под поочередной будем понимать такую передачу прав на занятие ресур­са заявками, при которой заявки одного приоритета получают полномо­чия на доступ к ресурсу с равной частотой или бесприоритетно друг от­носительно друга. Для радиального графа такая очередность может быть
определена в результате выполнения приведенной ниже итерационной
процедуры. При этом, в общем случае реализуется R итераций.
1. Произвольным образом через одну вершину каждого приоритета проводится первый путь.
2. Второй путь должен пройти через вершины всех приоритетов, кроме первого (через первый путь проходит всегда), не соединенные пер­вым путем; третий — не соединенные первыми двумя путями и т.д.
3. Если не осталось на рассмотрении вершин г-го приоритета, через которые не прошел по крайней мере один путь (для невырожден­ного графа прежде всего это приоритет 2) из проведенных г путей (2 путей). Дуга г + 1 проходит как и первая, но уже через другие вершины приоритета г + 1 и т.д., вплоть до соединения путями вершины первого приоритета со всеми вершинами приоритета R.
4. Все вершины R приоритета соединяются дугой с вершиной высше­го приоритета.
5. Нумеруются пути в соответствии с очередностью их получения. Именно в соответствии с этой нумерацией (с этим порядком) в системе должны передаваться полномочия на доступ к ресурсу.
6. Для каждого полученного пути определяется очередность передачи полномочий между вершинами графа (очередями заявок) перечис­лением очередности появления соответствующих вершин на пути.
Иллюстрация получения поочередной передачи прав, с использованием приведенной процедуры представлена 5.
Свойства канонических (оптимальных) расписаний реального времени
Можно выделить следующие свойства канонических расписаний реаль­ного времени:
1. В общем случае для каждой очереди заявок в цикле расписания может быть несколько очередностей передачи прав на доступ к ресурсу s=l,...,S, например, (1, 2, 1, 3, 4). При этом параметры обслуживания заявок определяются гарантированной продолжитель­ностью обслуживания Тг0т5:
и средней продолжительностью гарантированного обслуживания тре­бований с учетом различных очередностей S:
Таким образом, в общем случае при нескольких очередностях в систе­ме, дисциплина обслуживания реального времени задается параметра­ми Т'Л1    и 7,„    Д.ц> канонического расписания значения и "соответственно совпадают для заявок всех R приоритетов.
2. В системе реализуются минимально возможные значения для всех Мг заявок всех R приоритетов.
3. Относительный уровень (коэффициент) приоритетности заявок шг , mr: 8r_r. вырожденного графа при минимальных ТЛя составляет:
(RM,-\) (RM,-\)-
Соответственно, ограничением на общность построения радиаль­ного графа будет:
Выводы
Из анализа свойств канонических расписаний можем сделать следующие выводы:
1. В основе синтеза расписаний реального времени должно находиться построение канонического расписания, с последующей его модифи­кацией, учитывающей особенности конкретной задачи синтеза.
2. При минимизации значений параметра для всех очередей за­явок всех уровней приоритета системы R (эффективное использо­вание ресурса) строго задается соотношение уровней коэффициен­та приоритетности заявок.
3. Исходное соотношение коэффициентов приоритетности может быть изменено либо подбором соответствующих значений параметров Тгр и Тг„„ в рамках канонического расписания, либо изменением значений Т¥т или ГД, (в общем случае они могут не совпадать), путем их увеличения для заявок отдельных уровней приоритета (уменьшить их уже невозможно, что следует из второго свойства
канонических расписаний).

 

На главную | Содержание | Назад | Вперёд
 
Яндекс.Метрика