2. Розрахунок трудомісткості заявок

Для розрахунку трудомісткості заявок необхідно намалювати для кожної заявки схеми алгоритмів, графи алгоритмів і мінімальні графи алгоритмів заявок. Після цього визначити середню трудомісткість алгоритмів заявок засобами теорії марківських ланцюгів або за допомогою мереженого підходу.

3 Визначення мінімальної швидкодії процесора

Визначення мінімальної швидкодії процесора здійснюється на основі закону збереження часу ждання:

(1)

де _i - коефіцієнт завантаження процесора з боку i-го потоку заявок;

_i - середній час ждання заявок i-го потоку.

Закон збереження часу ждання (1) справедливий для будь-якої дисципліни обслуговування. Обмеження на час ждання _i _i* повинно виконуватися для будь-якої конкретної дисципліни, в якості якої виберемо безпрiоритетну дисципліну обслуговування. З урахуванням цього повинно виконуватися умова:

(2)

де - коефіцієнт завантаження ЦКС всіма потоками заявок;

₀ - середній час ждання заявок при беспрiоритетної дисципліні

обслуговування.

Враховуючи, що

З умови (2) слідує:

(3)

Вирішуючи остання нерівність відносно швидкодії процесора B, отримаємо:

(4)

де

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

При виборі дисципліни обслуговування заявок в ЦКС припускається дисципліна обслуговування зі змішаними пріоритетами. Останню будемо задавати матрицями пріоритетів 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}, є матрицею пріоритетів з коректною дисципліною обслуговування. Прикладом матриці з некоректною дисципліною обслуговування є матриця вигляду:

		1	2	3
	1	0	2	0
Q=	2	0	0	2
	3	2	0	0

Некоректні дисципліни обслуговування звичайно призводять до того, що час перебування заявок в ЦКС прагне до нескінченності.

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

Канонічна матриця з коректною дисципліною обслуговування володіє наступними властивостями:

Правило рядки - при перегляді рядка матриці ліворуч праворуч після елементів ,що значать не можуть стояти нульові елементи;