Задание и исходные данные

Задание

Вычислительная система располагает оперативной памятью (ОП) V и внешним объемом памяти Н (НМД). ОП память выделяется перемещаемым разделами, которые исключают влияние фрагментации. Реализуется режим мультипрограммирования: если одновременно выполняется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очередное задание поступает через время t_i, для простоты каждое задание состоит из одной задачи и требует объем ОП — v_i, объем внешней памяти h_i, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*h_i, после чего начинается счет. Однако закрепленные за каждым заданием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время Т_i = q*h_i + t_i. Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:

• 1) среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание, поступившее первым (правило FIFO);
• 2) среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание с наименьшим t_i (правило SJF).

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

.

гдевремя завершения задания,.

— время поступления задания в систему.

Для нормирования различных вариантов последовательностей заданий используется набор из 10 типов задач (см. таблицу 1). Каждое задание включает одну из этих 10 задач. В одном потоке заданий могут встретиться задания, содержащие одинаковые задачи. Номер задачи К_i для очередного задания определяется по формулам:

X_i = [7 * X_i-1 + 417] mod 1000;

K_i = [X_i / 7] mod 10, i=1M, X_o = N,.

где[c] - целая часть числа с,.

y mod z — остаток от деления y на z,.

Xo = N — шифр (последние три цифры из зачетной книжки; если четное число, то +1, чтобы получилось нечетное).

Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) t_i=k_i .

N = 711

X0=711.

X1 = [7 * 711 + 417] mod 1000 = 394.

K1 = [394/ 7] mod 10 = 6.

X2 = [7 * 394 + 417] mod 1000 = 175.

K2 = [175/ 7] mod 10 = 5.

X3 = [7 * 175+ 417] mod 1000 = 642.

K3 = [642 / 7] mod 10 = 1.

X4 = [7 * 642 + 417] mod 1000 = 911.

K4 = [911/ 7] mod 10 = 0.

X5 = [7 * 911 + 417] mod 1000 = 794.

K5 = [794 / 7] mod 10 = 3.

X6 = [7 * 794 + 417] mod 1000 = 975.

K6 = [975 / 7] mod 10 = 9.

X7 = [7 * 975 + 417] mod 1000 = 242.

K7 = [242/ 7] mod 10 = 4.

X8 = [7 * 242 + 417] mod 1000 = 111.

K8 = [111 / 7] mod 10 = 5.

X9 = [7 * 111 + 417] mod 1000 = 194.

K9 = [194 / 7] mod 10 = 7.

X10 = [7 * 194 + 417] mod 1000 = 775.

K10 = [775/ 7] mod 10 = 0.

Таблица 1.

Исходные данные

Последовательность заданий задается таблицей:

Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) t_i=k_i .