Основа построения приоритетных расписаний

Идея излагаемой концепции состоит в реализации дисциплин обслуживания реального времени с передачей прав по расписанию (ДОР), за счет смены относительных приоритетов (ОП) в рамках реализуемой в системе дисциплины обслуживания с относительными приоритетами (ДООП) по расписанию при каждом занятии ресурса абонентами системы.

Утверждение. В любой момент времени ОП не должен совпасть у заявок из нескольких очередей.

Доказательство. Если данное условие не будет выполнено, то в системе неминуем конфликт при занятии ресурса, т.к. несколько абонентов одновременно получат право занять ресурс после его освобождения.

Для описания ДООП используем матрицу приоритетов (МП), представляющую собою квадратную матрицу размерности по числу M абонентов [1]. Элемент матрицы задает ОП абонента i по отношению к j: 0 - нет приоритета, 1 - есть. Для описания ДОР (в общем случае ДОСП) используем граф изменения матрицы ОП в моменты времени занятия ресурса в соответствии с расписанием. Пример графа бесприоритетной ДОР, реализуемой методом динамической смены ОП, для случая , цикл расписания которой имеет вид (1, 2, 3, 4), представлен на рис. 2.5. Бесприоритетность расписания обеспечивается тем, что каждый абонент входит в расписание равное число раз, в общем случае может быть более одного, например (1, 1, 2, 2, 3, 3, 4, 4).

Рис. 2.5

Требования к МП. Элементы МП должны удовлетворять следующим требованиям:

- , т.к. между заявками одного класса не могут быть установлены приоритеты;

- если , то , т.е., если заявки класса i имеют приоритет по отношению к заявкам класса j, то последние не могут иметь приоритет по отношению к заявкам i;

- в МП не должны совпасть не любые две строки i, i' , не любые два столбца j, j'; , , , .

Требования к графу смены МП ДОР РМВ. В графе смены МП ДОР РМВ (в цикле расписания) по крайней мере по одному разу должны присутствовать МП, задающие высший ОП каждого из M абонентов системы. Утверждение. Для реализации приоритетной ДОР в цикле расписания по крайней мере двум абонентам системы высший ОП должен присваиваться различное число раз, например (1, 2, 1, 3, 1, 4).

Доказательство. В противном случае получим совпадение значений , т.е. при совпадении значений параметров получаем равный приоритет заявок - совпадают .

Изменение ОП заявок по расписанию в процессе функционирования системы должно быть реализовано по следующему правилу.

Правило изменения ОП. ОП в рамках ОР однозначно задаются расписанием, где в каждый момент времени приоритет заявок соответствует порядку передачи полномочий, исключая повторные передачи прав одной очереди в цикле ОР, например для расписания (1, 2, 1, 3) в момент - ОП [1, 2, 3], в - [2, 1, 3], в - [1, 3, 2], в - [3, 1, 2].

Для ДО с динамическими ОП, изменяемыми по расписанию, функция приоритетности заявки m, имеет вид

,

где - исходный ОП заявки поступающей в момент , соответствующий s-му состоянию цикла расписания, длиной G: ; - приращение (может иметь отрицательные значения) приоритета заявки, получаемое при смене состояний цикла расписания . Для заявок, обслуживаемых с ОП, для , и для , .