Освоение методов анализа и выбора дисциплины обслуживания заявок в цифровой управляющей системе ( ЦУС ), определение быстродействия процессора, которые обеспечивают заданное качество функционирования системы реального времени.
Для математического описания процессов, протекающих в ЦУС, используют аппарат теории массового обслуживания. В данной лабораторной работе требуется выполнить анализ и синтез ЦУС с относительными ограничениями на время ожидания заявки в вычислительной системе.
Синтез ЦУС включает три этапа :
1. определение необходимого минимального быстродействия процессора ;
2. выбор рациональной дисциплины обслуживания ;
3. выбор оптимального быстродействия процессора.
Последний этап синтеза ЦУС в данной работе не выполняется.
Исходными данными для выполнения синтеза ЦУС являются :
n - количество потоков заявок различного типа ;
li ( i = 1,2,...,n ) - интенсивность поступления заявок i-го потока ;
qi ( i = 1,2,...,n ) - среднее значение трудоемкости i-й прикладной задачи ;
ni ( i = 1,2,...,n ) - коэффициент вариации времени обслуживания i-й заявки ;
wi* ( i = 1,2,...,n ) - предельно допустимое среднее время ожидания i-й заявки в ЦУС.
При выполнении лабораторной работы предполагается, что количество потоков заявок n=5. Остальные данные берутся из табл.1 в соответствии с номером варианта.
Определение минимального быстродействия
процессора
Определение минимального быстродействия процессора осуществляется на основе закона сохранения времени ожидания :
(1)
где ri - коэффициент загрузки процессора со стороны i-го потока заявок ;
wi - среднее время ожидания заявок i-го потока.
Закон сохранения времени ожидания (1) справедлив для любой дисциплины обслуживания. Ограничения на время ожидания
wi < wi*
должно выполняться для какой-либо конкретной дисциплины, в качестве которой выберем бесприоритетную дисциплину обслуживания. С учетом этого должно выполняться условие :
(2)
где - коэффициент загрузки ЦУС всеми потоками заявок ;
w0 - среднее время ожидания заявок при бесприоритетной дисциплине обслуживания.
Учитывая, что
из условия (2) следует :
(3)
Решая последнее неравенство относительно быстродействия процессора B, получим :
(4)
где
Выбор дисциплины обслуживания
заявок
При выборе дисциплины обслуживания заявок в ЦУС предполагается дисциплина обслуживания со смешанными приоритетами. Последнюю будем задавать матрицами приоритетов Q размером (n x n). Элементами qij данной матрицы могут быть только числа из множества { 0,1,2 }. Если qij = 0, то i-я заявка не имеет приоритета перед j-й заявкой. Если qij = 1, то i-я заявка имеет относительный приоритет перед j-й заявкой. Если qij = 2, то i-я заявка имеет абсолютный приоритет перед j-й заявкой. Очевидно, что элементы qij, расположенные на главной диагонали матрицы приоритетов, равны 0. Если qij=1 или qij=2, то qji=0.
Не всякая матрица, составленная из элементов множества { 0,1,2 }, является матрицей приоритетов с корректной дисциплиной обслуживания. Примером матрицы с некорректной дисциплиной обслуживания является матрица вида :
Q =
Матрица (5)
Некорректные дисциплины обслуживания обычно приводят к тому, что время пребывания заявок в ЦУС стремится к бесконечности.
Корректные дисциплины обслуживания проще всего назначить в том случае, если матрица приоритетов является канонической. Для получения канонической матрицы приоритетов потоки заявок должны быть перенумерованы таким образом, чтобы заявки с более высоким приоритетом имели меньший номер. В этом случае все значащие элементы будут собраны над диагональю матрицы.
Каноническая матрица с корректной дисциплиной обслуживания обладает следующими свойствами :
правило строки - при просмотре строки матрицы слева направо после
значащих элементов не могут стоять нулевые элементы;
правило столбца - при просмотре столбца матрицы снизу вверх элементы
столбца матрицы должны образовывать неубывающую
последовательность значений;
правило группы строк - если при просмотре данной строки матрицы слева
направо после диагонального элемента расположено m
нулевых элементов, то следующие m строк матрицы
должны совпадать с просматриваемой строкой.
Если дисциплина обслуживания заявок задана в виде матрицы приоритетов, то время ожидания заявки k-го потока wk ЦУС определяется из выражения:
(6)
В настоящее время строго доказанных правил назначения дисциплины обслуживания, за исключением частных случаев, не существует. Поэтому эта задача в общем случае решается методом полного перебора всех вариантов, что весьма трудоемко при большом количестве потоков заявок. Наиболее общие рекомендации выглядят следующим образом.
При отсутствии ограничений на время ожидания или время пребывания заявок в ЦУС более высокий приоритет следует присваивать потокам с меньшей трудоемкостью ( эта рекомендация известна под названием “правило оперативной обработки” ).
При наличии относительных ограничений более высокий приоритет присваивают заявкам с меньшим предельно допустимым временем пребывания или временем ожидания.
Критерием необходимости изменения дисциплины обслуживания может служить соотношение :
( i = 1,2,...,n ) (7)
которое характеризует относительный запас по времени ожидания. При удовлетворительной дисциплине обслуживания относительный запас по времени для всех потоков примерно одинаков.
Порядок выполнения работы
1. Из табл.1 выбираются исходные данные и по формуле (4) вычисляется минимальное быстродействие процессора. Остальные расчеты ведутся с помощью программы определения характеристик обслуживания.
w1*,w2*,...,wn* - предельно допустимое время ожидания, сек. ;
q11,q22,...,qnn - элементы матрицы приоритетов по строкам.
Таблица 1 - Исходные данные для выполнения синтеза ЦУС
№ п/п
l, 1/сек
q, опер.
n
w*, сек.
1.8
1.0
0.1
1.7
0.95
0.2
1.6
0.90
1.3
1.5
0.85
0.4
1.4
0.80
0.5
1.3
0.75
2.4
1.2
0.80
0.3
1.1
0.85
0.2
1.0
0.90
3.1
0.9
0.95
0.2
0.8
1.0
0.3
0.7
0.95
2.4
0.6
0.90
0.5
0.5
0.85
0.4
0.4
0.80
1.3
1.8
0.90
0.1
1.7
0.95
2.0
1.6
1.0
1.3
1.5
0.95
4.5
1.4
0.90
0.5
1.3
0.85
6.0
1.2
0.80
5.0
1.1
0.75
0.4
1.0
0.80
3.0
0.9
0.75
2.0
0.8
0.80
0.15
0.7
0.85
2.0
0.6
0.90
3.0
0.5
0.95
4.5
0.4
1.0
0.5
Результаты расчетов оформляются в виде нескольких таблиц с различным быстродействием процессора ( например - рис.1 ). Под запасом времени ожидания понимается величина ( wi* - wi ). Вероятность пребывания вычисляется по формуле :
P(wi > wi*) = R · EXP( -R · wi*/wi)
и представляет собой вероятность превышения допустимого времени ожидания для бесприоритетной дисциплины обслуживания. Функция штрафа ( вероятностная ) F определяется из выражения :
Смысл остальных значений ясен из наименований граф таблицы.
2. В соответствии с вышеописанным готовятся данные для бесприоритетной дисциплины обслуживания и пропускаются через ЭВМ.
3. В соответствии с рекомендациями готовятся исходные данные для дисциплины обслуживания с относительными приоритетами и характеристики обслуживания рассчитываются на ЭВМ.
4. На ЭВМ рассчитываются характеристики обслуживания при дисциплине с абсолютными приоритетами. В пунктах 3 и 4 матрица приоритетов может быть не канонической, но дисциплина обслуживания - обязательно корректной.
5. На основе анализа полученных результатов необходимо попытаться улучшить дисциплину обслуживания в соответствии с критерием (7), путем двух-трех изменений матрицы приоритетов.
6. Входные данные формируются в следующем виде:
0.04 0.04 0.04 0.04 0.04 l
100000 100000 100000 100000 100000 Q
0 0 0 0 0 n
3 3 3 3 3 w
0 2 2 2 2
0 0 2 2 2
0 0 0 2 2 Матрица приоритетов
0 0 0 0 2
0 0 0 0 0
7. Полученные результаты анализируются и оформляются в виде отчета.
Быстродействие процессора 50000 операций в секунду.
Рис.1 - Результаты расчета характеристик обслуживания
Контрольные вопросы
1. Какие допущения приняты при разработке математической модели ЦУС ?
2. Что такое простейший поток заявок ?
3. Что представляет собой очередь в вычислительной системе ?
4. Что такое приоритет ?
5. При каких условиях справедлив закон сохранения времени ожидания заявок в системах массового обслуживания ?
6. Дать вывод выражений (3) и (4).
7. Что будет с выражением (4) при wi*, стремящемся к бесконечности ?
8. Изобразите некорректную матрицу (5) в виде графической схемы.
9. Почему время пребывания заявок в ЦУС при некорректной дисциплине обслуживания стремится к бесконечности ?
10.Докажите правило строки.
11.Докажите правило столбца.
12.Докажите правило группы строк.
13.На основании выражения (6) выведите формулы для расчета времени ожидания для бесприоритетной дисциплины обслуживания, дисциплин обслуживания с относительными и абсолютными приоритетами.
14.Найти минимальное быстродействие процессора при ограничениях на время пребывания в ЦУС.
15.Каковы методики назначения дисциплин обслуживания ?
16.О чем свидетельствует di < 0 и что в этом случае необходимо делать ?
17.Какие проверки исходных данных осуществляются в программе расчета характеристик обслуживания ? Как реагирует программа на ошибки в исходных данных ?
Литература
Основы теории вычислительных систем / Под ред. С.А. Майорова. - М.: Высшая школа, 1978. - 408 стр.
(1)
(2)
- коэффициент загрузки ЦУС всеми потоками заявок ;
(3)
(4)
(6)
