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
|
Максимальный коэффициент мультипрограммирования, который равен 3, был получен на участках времени: 138-179, 199-275, 285-393, 423-448.
Средневзвешенное время обращения Wср = 4,34.
ДО SJF
Временная диаграмма мультипрограммной работы ЭВМ при исходных данных для до SJF (см. табл. 5) показана на рисунке 3.
Таблица 5. Последовательность событий в системе (SJF).
Время
|
Событие
|
Свободный объем ОП=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 и его ресурсы освобождены. Из очереди выбирается задание 7(6,2), начинается ввод задания. Процессор простаивает.
|
2
|
5
|
0
|
0
|
120
|
Завершен ввод задания 5. Задания на процессоре: 5.
|
2
|
5
|
1
|
2
|
125
|
Завершен ввод задания 3. Задания на процессоре: 3, 5.
|
2
|
5
|
2
|
2,5
|
128
|
Завершен ввод задания 7. Задания на процессоре: 3, 5, 7.
|
2
|
5
|
3
|
1
|
184
|
Завершено задание 3 и его ресурсы освобождены. Из очереди выбирается задание 8(4,6), начинается ввод задания. Задания на процессоре: 5, 7.
|
0
|
2
|
2
|
28
|
214
|
Завершен ввод задания 8. Задания на процессоре: 5, 7, 8.
|
0
|
2
|
3
|
10
|
275
|
Завершено задание 5 и его ресурсы освобождены. Из очереди выбирается задание 4(3,4), начинается ввод задания. Задания на процессоре: 7, 8.
|
3
|
0
|
2
|
30,5
|
287
|
Завершено задание 7 и его ресурсы освобождены. Задания на процессоре: 8.
|
9
|
2
|
1
|
12
|
295
|
Завершен ввод задания 4. Задания на процессоре: 4,8.
|
9
|
2
|
2
|
4
|
306
|
Завершено задание 8 и его ресурсы освобождены. Из очереди выбираются задания 6(3,4), 10(7,4) начинается ввод задания. Задания на процессоре: 4.
|
3
|
0
|
1
|
11
|
326
|
Завершен ввод заданий 6, 10. Задания на процессоре: 4, 6, 10.
|
3
|
0
|
3
|
6,67
|
520
|
Завершено задание 4 и его ресурсы освобождены. Из очереди выбирается задание 9(3,4), начинается ввод задания. Задания на процессоре: 6,10.
|
3
|
0
|
2
|
97
|
531
|
Завершено задание 10 и его ресурсы освобождены. Задания на процессоре: 6.
|
10
|
4
|
1
|
11
|
540
|
Завершен ввод задания 9. Задания на процессоре: 6, 9.
|
10
|
4
|
2
|
4,5
|
562
|
Завершено задание 6 и его ресурсы освобождены.. Задания на процессоре: 9.
|
13
|
8
|
1
|
22
|
641
|
Завершено задание 9 и его ресурсы освобождены.. Заданий на процессоре нет.
|
16
|
12
|
0
|
0
|
Рисунок 3. Временная диаграмма выполнения алгоритма SJF.
Рисунок 4. Временная диаграмма использования ресурсов по алгоритму SJF.
Tпроц. = (641-120) + (118-38) = 601, τобщ. = 40 * 3 + 60 * 2 + 90 * 3 + 20 + 70 =600
Трудоемкость обеспечена верно.
Таблица 6. Результаты работы до SJF.
№
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
Время поступления
|
8
|
16
|
18
|
19
|
19
|
20
|
20
|
28
|
29
|
35
|
Начало загрузки
|
8
|
16
|
110
|
275
|
110
|
306
|
118
|
184
|
520
|
306
|
Начало выполнения
|
38
|
46
|
125
|
295
|
120
|
326
|
128
|
214
|
540
|
326
|
Конец выполнения
|
110
|
118
|
184
|
520
|
275
|
562
|
287
|
306
|
641
|
531
|
Время нахождения в системе
|
72
|
72
|
59
|
225
|
155
|
236
|
159
|
92
|
101
|
205
|
Wi
|
1,03
|
1,03
|
1,69
|
2,05
|
2,21
|
2,15
|
2,27
|
1,31
|
0,92
|
2,28
|
Максимальный коэффициент мультипрограммирования, который равен 3, был получен на участках времени: 125-184, 214-275, 326-520.
Средневзвешенное время обращения Wср = 1,69.
Выводы
Максимальный коэффициент мультипрограммирования у обоих алгоритмов 4, но в режиме максимального коэффициента мультипрограммирования алгоритм FIFO(192) находится дольше, чем алгоритм SJF(161). Это является плюсом в пользу использования алгоритма FIFO в данном случае.
При использовании алгоритма SJF(1250) общее время выполнения пакета заданий меньше, чем у алгоритма FIFO(1283) при обработке данного задания.
Дисциплина обслуживания FIFO(2.2546) обладает большим значением средневзвешенного времени обращения по сравнению с SJF(2,132), следовательно, для такой последовательности заданий выгоднее использовать дисциплину обслуживания SJF.
Раздел 2
|
Скачать 3.46 Mb.