Выбор дисциплины обслуговання заявок

    При выборе дисциплины обслуживания заявок в ЦУС предполагается дисциплина обслуживания со смешанными приоритетами. Последнюю будем задавать матрицами приоритетов Q размером (n x n). Элементами q_ij данной матрицы могут быть только числа из множества { 0,1,2 }. Если q_ij = 0, то i-я заявка не имеет приоритета перед j-й заявкой. Если q_ij = 1, то i-я заявка имеет относительный приоритет перед j-й заявкой. Если q_ij = 2, то i-я заявка имеет абсолютный приоритет перед j-й заявкой. Очевидно, что элементы q_ij, расположенные на главной диагонали матрицы приоритетов, равны 0. Если q_ij=1 или q_ij=2, то q_ji=0.

    Не всякая матрица, составленная из элементов множества { 0,1,2 }, является матрицей приоритетов с корректной дисциплиной обслуживания. Примером матрицы с некорректной дисциплиной обслуживания является матрица вида:

                                                   Матрица (5)

    Некорректные дисциплины обслуживания обычно приводят к тому, что время пребывания заявок в ЦУС стремится к бесконечности.

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

    Каноническая матрица с корректной дисциплиной обслуживания обладает следующими свойствами:

    правило строки - при просмотре строки матрицы слева направо   после  

                                     значащих элементов не могут стоять нулевые элементы;

    правило столбца - при просмотре столбца матрицы снизу вверх элементы

                                     столбца   матрицы должны образовывать неубывающую 

                                      последовательность значений;

    правило группы строк - если при просмотре данной строки матрицы слева

                                      направо после   диагонального элемента расположено m

                                      нулевых элементов, то следующие m строк матрицы

                                      должны совпадать с просматриваемой строкой.

    Если дисциплина обслуживания заявок задана в виде матрицы приоритетов, то время ожидания заявки k-го потока w_k ЦУС определяется из выражения:

                               (6)

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

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

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

    Критерием необходимости изменения дисциплины обслуживания может служить соотношение:

                                 (i = 1,2,...,n)                   (7)

которое характеризует относительный запас по времени ожидания. При удовлетворительной дисциплине обслуживания относительный запас по времени для всех потоков примерно одинаков.