Пример построения временной диаграммы мультипрограммной работы ЭВМ (дисциплина обслуживания FIFO)

Примем, что в нашем распоряжении имеются 9 Kb оперативной памяти и 5 внешних устройств. Характеристики заданий приведены в таблице 1.

Таблица 1. Характеристики заданий.

Номер задания	Время поступления	Необходимое процессорное время	Требования к ОП	Требования к ВУ

Время ввода каждого задания определим по формуле:

t_ввода = q Ч N, где

q – время работы одного внешнего устройства (q=5 ед.времени), N – число внешних устройств.

Таким образом, если бы задания выполнялись по одному, то на каждое задание было бы затрачено время

T = t_ввода + t_проц., где

T – время выполнения задания,

t_проц. – процессорное время, затраченное для выполнения задания.

В ЭВМ поступает поток заданий, поэтому при одновременном выполнении нескольких заданий процессорное время распределяется между ними равномерно. Т.о. реально затраченное время для выполнения задания ≥ необходимого процессорного времени.

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

Временная диаграмма мультипрограммной работы ЭВМ при приведенных выше исходных данных изображена на рис.3

Рис. 3. Временная диаграмма мультипрограммной работы ЭВМ
(Дисциплина обслуживания FIFO).

Процесс построения временной диаграммы рассмотрен в таблице 2.

Таблица 2. Описание построения временной диаграммы.

Время	Событие
t = 0	Поступило задание 1. Т.к. свободных ресурсов (ОП и ВУ) заданию хватает, оно назначается на выполнение. (Начинается ввод).
t = 5	Ввод завершен и все процессорное время отдается для выполнения задания 1.
t = 7	Поступило задание 2. Свободных ресурсов для выполнения задания недостаточно, поэтому оно помещается в очередь.
t = 12	Поступило задание 3. Свободных ресурсов для выполнения задания недостаточно, поэтому оно также помещается в очередь. В очереди сейчас находятся задания 2 и 3.
t = 20	Поступило задание 4. Т.к. свободных ресурсов заданию хватает, оно назначается на выполнение. Первые 5 ед. времени процессорное время заданию 4 не требуется и его полностью получает задание 1.
t = 25	Завершился ввод задания 4. С этого момента времени процессор необходим обоим заданиям. Процессор начинает работать в мультипрограммном режиме. Каждое из заданий получает 10 ед. процессорного времени. В сумме процессорного времени затрачено 20 ед.
t = 45	Завершено выполнение задания 1. Ресурсы, занятые им, освобождены. Теперь свободных ресурсов достаточно для назначения на выполнение задания 2 или 3 (но не одновременно). В действие вступает дисциплина обслуживания FIFO. На выполнение назначается задание 2 – оно поступило первым (задание 3 остается в очереди).
t = 50	Те 5 ед. времени, в течение которых выполнялся ввод задания 2, все процессорное время (5 ед.) получило задание 4. Вновь процессор начинает работать в мультипрограммном режиме. 10 ед. процессорного времени распределяются между заданиями 4 и 2.
t = 60	Выполнение задания 4 завершено, но освободившихся ресурсов недостаточно для назначения на выполнение задания 3. Задание 3 остается в очереди.
t = 65	Завершилось выполнение задания 2. освободившихся ресурсов достаточно для назначения на выполнение задания 3. Задание 3 выполняется в однопрограммном режиме.
t = 85	Завершилось выполнение задания 3.

Каким образом можно проверить правильность построения времен­ной диаграммы?

Для этого необходимо определить по временной диаграмме, сколько времени работал процессор. Это временные интервалы с t=5 до t=65 и с t=75 до t=85. В интервале с t=65 до t=75 процессор простаивал. Таким образом, процессор работал в течение 70 ед. времени.

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

T_{процессора} = 30+10+10+20=70 ед.

Значения равны, следовательно, диаграмма построена верно.

Для оценки эффективности дисциплины обслуживания найдет средневзвешенное время обращения. Согласно формуле . Необходимо найти взвешенные времена выполнения каждого задания (данные берем из временной диаграммы и таблицы):

1. W₁ = (t_З – t_П) / T = (t_З – t_П) / (t_ввода + t_проц) = (t_З – t_П) / (q Ч N + t_проц) = (45 – 0) / (5 Ч 1 + 40) =
= 1.00

2. W₂ = (65 – 7) / (5 Ч 1 + 15) = 2.90

3. W₃ = (82 – 12) / (5 Ч 2 + 10) = 3.65

4. W₄ = (60 – 20) / (5 Ч 1 + 35) = 1.00

Т.о. W_ср = (W₁ + W₂ + W₃ + W₄) / 4 = 2.14.

.