Файл: Новосибирский государственный технический университет факультет автоматики и вычислительной техники кафедра вычислительной техники.docx

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

Средневзвешенное время обращения:



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

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

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

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

K_i = [X_i / 7] mod 10, i=1M, Xo = N,

где

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

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

Xo = N = 135

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

K	0	1	2	3	4	5	6	7	8	9
v	6	3	2	4	3	5	7	9	4	1
h	2	4	3	1	2	0	4	1	6	3
τ	60	90	20	10	60	30	70	30	40	20

Таблица последовательностей.

Используя индивидуальный расстановочный код: X0=N=873, были рассчитаны K_i номера

задач:

X0=N=135

X1=[7*135+417] mod 1000=620

K1=[620/7] mod 10=8

X2=[7*620+417] mod 1000=757

K2=[757/7] mod 10=8

X3=[7*757+417] mod 1000=716

K3=[716/7] mod 10=2

X4=[7*716+417] mod 1000=429

K4=[429/7] mod 10=1

X5=[7*729+417] mod 1000=420

K5=[420/7] mod 10=0

X6=[7*420+417] mod 1000=357

K6=[357/7] mod 10=1

---

X7=[7*357+417] mod 1000=916

K7=[916/7] mod 10=0

X8=[7*916+417] mod 1000=829

K8=[829/7] mod 10=8

X9=[7*829+417] mod 1000=220

K9=[220/7] mod 10=1

X10=[7*220+417] mod 1000=957

K10=[957/7] mod 10=6

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

№	Xi	Ki	vi	hi	τ i	ti	q*hi	Тi
1	620	8	4	6	40	8	30	70
2	757	8	4	6	40	8	30	70
3	716	2	2	3	20	2	15	35
4	429	1	3	4	90	1	20	110
5	420	0	6	2	60	0	10	70
6	357	1	3	4	90	1	20	110
7	916	0	6	2	60	0	10	70
8	829	8	4	6	40	8	30	70
9	220	1	3	4	90	1	20	110
10	957	6	7	4	70	6	20	90

---

---

2.3. Временные диаграммы использования FIFO и SJF. Таблицы результатов.
ДО FIFO
Временная диаграмма мультипрограммной работы ЭВМ при исходных данных для до FIFO (см. табл. 3) показана на рисунке 1.

Таблица 3. Последовательность событий в системе (FIFO).

Время	Событие	Свободный объем ОП=16	Свободный объем НМД=12	Km	Квант времени на ЦП
8	Поступило задание 1(4,6), начинается ввод задания. Процессор простаивает.	12	6	0	0
16	Поступило задание 2(4,6), начинается ввод задания. Процессор простаивает.	8	0	0	0
18	Поступило задание 3(2,3), нехватка ресурсов – задание помещено в очередь. Процессор простаивает.	8	0	0	0
19	Поступило задание 4(3,4), 5(6,2) нехватка ресурсов – задания помещены в очередь. Процессор простаивает.	8	0	0	0
20	Поступило задание 6(3,4), 7(6,2) нехватка ресурсов – задания помещены в очередь. Процессор простаивает.	8	0	0	0
28	Поступило задание 8(4,6), нехватка ресурсов – задание помещено в очередь. Процессор простаивает.	8	0	0	0
29	Поступило задание 9(3,4), нехватка ресурсов – задание помещено в очередь. Процессор простаивает.	8	0	0	0
35	Поступило задание 10(7,4), нехватка ресурсов – задание помещено в очередь. Процессор простаивает.	8	0	0	0
38	Завершен ввод задания 1. Задания на процессоре: 1.	8	0	1	3
46	Завершен ввод задания 2. Задания на процессоре: 1,2.	8	0	2	4
110	Завершено задание 1 и его ресурсы освобождены. Из очереди выбирается задание 3(2,3), 5(6,2) начинается ввод заданий. Задания на процессоре: 2	4	1	1	64
118	Завершено задание 2 и его ресурсы освобождены. Из очереди выбирается задание 4(3,4), начинается ввод задания. Процессор простаивает.	5	3	0	0
120	Завершен ввод задания 5. Задания на процессоре: 5.	5	3	1	2
125	Завершен ввод задания 3. Задания на процессоре: 3, 5.	5	3	2	2,5
138	Завершен ввод задания 4. Задания на процессоре: 3, 4, 5.	5	3	3	4,33
179	Завершено задание 3 и его ресурсы освобождены. Из очереди выбирается задание 6(3,4), начинается ввод задания. Задания на процессоре:4, 5.	4	2	2	20,5
199	Завершен ввод задания 6. Задания на процессоре: 4, 5, 6.	4	2	3	6,67
275	Завершено задание 5 и его ресурсы освобождены. Из очереди выбирается задание 7(6,2), начинается ввод задания. Задания на процессоре: 4, 5.	4	2	2	38
285	Завершен ввод задания 7. Задания на процессоре: 4, 6, 7.	4	2	3	3,33
393	Завершено задание 4 и его ресурсы освобождены. Из очереди выбирается задание 8(4,6), начинается ввод задания. Задания на процессоре: 6, 7.	3	0	2	54
423	Завершен ввод задания 8. Задания на процессоре: 6, 7, 8.	3	0	3	10
448	Завершено задание 6 и его ресурсы освобождены. Из очереди выбирается задание 9(3,2), начинается ввод задания. Задания на процессоре: 7, 8.	3	2	2	12,5
449	Завершено задание 7 и его ресурсы освобождены. Задания на процессоре: 8.	9	4	1	1
468	Завершен ввод задания 9. Задания на процессоре: 8, 9.	9	4	2	9,5
491	Завершено задание 8 и его ресурсы освобождены. Из очереди выбирается задание 10(7,4), начинается ввод задания. Задания на процессоре: 9.	6	6	1	23
511	Завершен ввод задания 10. Задания на процессоре: 9, 10.	6	6	2	10
627	Завершено задание 9 и его ресурсы освобождены. Задания на процессоре: 10.	9	10	1	116
639	Завершено задание 10 и его ресурсы освобождены. Заданий на процессоре нет.	16	12	0	0

---

Рисунок 1. Временная диаграмма выполнения алгоритма FIFO.



Рисунок 2. Временная диаграмма использования ресурсов по алгоритму FIFO.

T_проц. = (639-120) + (118-38)= 599, τ_общ. = 40 * 3 + 60 * 2 + 90 * 3 + 20 + 70 =600

Трудоемкость обеспечена верно.

Таблица 4. Результаты работы до FIFO.

№	1	2	3	4	5	6	7	8	9	10
Время поступления	8	16	18	19	19	20	20	28	29	35
Начало загрузки	8	16	110	118	110	179	275	393	448	491
Начало выполнения	38	46	125	138	120	199	285	423	468	511
Конец выполнения	110	118	179	393	275	448	449	491	627	639
Время нахождения в системе	72	72	54	255	155	249	164	68	159	128
Wi	1,46	1,46	4,60	3,40	3,66	3,89	6,13	6,61	5,44	6,71

---