Курсовая работа Операционные системы НГТУ АВТФ. Новосибирский государственный технический университет факультет автоматики и вычислительной техники кафедра вычислительной техники

Название	Новосибирский государственный технический университет факультет автоматики и вычислительной техники кафедра вычислительной техники
Анкор	Курсовая работа Операционные системы НГТУ АВТФ
Дата	25.05.2023
Размер	3.29 Mb.
Формат файла
Имя файла	AI-02_Kursovaya_rabota_Operatsionnye_sistemy_drugaya_versia.docx
Тип	Курсовая #1158996
страница	2 из 3

1 2 3

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

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

Время	Событие	Свободный объем ОП=16	Свободный объем НМД=12	Km	t_пр
1	Поступило задание 1(3,4) начинается ввод задания. Процессор простаивает.	13	8	0	0
8	Поступило задание 2(9,1), начинается ввод задания. Процессор простаивает.	4	7	0	0
13	Завершен ввод задания 2. Задания на процессоре: 2.	4	7	1	3
16	Поступило задание 3(4,6), начинается ввод задания. Задания на процессоре: 2.	0	1	1	5
21	Завершен ввод задания 1. Задания на процессоре: 1, 2.	0	1	2	2
24	Поступило задание 4(4,6), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4.	0	1	2	2
28	Поступило задание 5(3,2), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5.	0	1	2	1,5
31	Поступило задание 6(4,1), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5, 6.	0	1	4	0,5
32	Поступило задание 7(3,4), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5, 6, 7.	0	1	2	4
40	Поступило задание 8(4,6), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5, 6, 7, 8.	0	1	2	2
44	Поступило задание 9(3,2), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5, 6, 7, 8, 9.	0	1	2	1
46	Завершен ввод задания 3. Задания на процессоре: 1, 2, 3.	0	1	3	0,3
47	Поступило задание 10(4,1), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2, 3. Очередь заданий: 4, 5, 6, 7, 8, 9, 10.	0	1	3	9,7
76	Завершено задание 2 и его ресурсы освобождены. Задания на процессоре: 1, 3. Очередь заданий: 4, 5, 6, 7, 8, 9, 10.	9	2	2	5
76	Из очереди выбирается задание 5(3,2), начинается ввод задания. Задания на процессоре: 1, 3. Очередь заданий: 4, 6, 7, 8, 9, 10.	6	0	2	5
86	Завершен ввод задания 5. Задания на процессоре: 1, 3, 5. Очередь заданий: 4, 6, 7, 8, 9, 10.	6	0	3	53,7
161	Завершено задание 3 и его ресурсы освобождены. Задания на процессоре: 1, 5. Очередь заданий: 4, 6, 7, 8, 9, 10.	10	6	2	15
161	Из очереди выбирается задание 4(4,6), начинается ввод задания. Задания на процессоре: 1, 5. Очередь заданий: 6, 7, 8, 9, 10.	4	6	2	15
191	Завершен ввод задания 4. Задания на процессоре: 1, 4, 5	6	0	3	20
251	Завершено задание 5 и его ресурсы освобождены. Задания на процессоре: 1, 4. Очередь заданий: 6, 7, 8, 9, 10.	9	2	2	2,5
251	Из очереди выбирается задания 6(4,1) и 10(4,1), начинается ввод задания. Задания на процессоре: 1, 4. Очередь заданий: 7, 8, 9.	1	0	2	2,5
256	Завершен ввод заданий 6 и 10. Завершено задание 1 и его ресурсы освобождены. Задания на процессоре: 4, 6, 10. Очередь заданий: 7, 8, 9.	4	4	3	6,7
256	Из очереди выбирается задание 7(3,4), начинается ввод задания. Задания на процессоре: 4, 6, 10. Очередь заданий: 8, 9.	1	0	3	6,7
276	Завершен ввод задания 7. Задания на процессоре: 4, 6, 7, 10	1	0	4	3,5
290	Завершены задания 6 и 10 и их ресурсы освобождены. Задания на процессоре: 4, 7. Очередь заданий: 8, 9.	9	2	2	5
290	Из очереди выбирается задание 9(3,2), начинается ввод задания. Задания на процессоре: 4, 7. Очередь заданий: 8.	6	0	2	5
300	Завершен ввод задания 9. Задания на процессоре: 4, 7, 9.	6	0	3	2
306	Завершено задание 4 и его ресурсы освобождены. Задания на процессоре: 7, 9. Очередь заданий: 8.	10	6	2	15
306	Из очереди выбирается задание 8(4,6), начинается ввод задания. Задания на процессоре: 7, 9. Заданий в очереди нет	6	0	2	15
336	Завершен ввод задания 8. Задания на процессоре: 7, 8, 9.	6	0	2	60
456	Завершено задание 8 и его ресурсы освобождены. Задания на процессоре: 7, 9.	10	6	1	6
462	Завершено задание 9 и его ресурсы освобождены. Задания на процессоре: 7, 9.	13	8	1	22
484	Завершено задание 7 и его ресурсы освобождены.	16	12	0	0

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

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

T_проц. = 483-13 = 470, τ_общ. = 90*2+30+40*3+60*2+10*2 = 470

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

Для оценки эффективности дисциплины обслуживания найдем средневзвешенное время обращения. Воспользуемся следующими формулами:

где

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

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

M - количество заданий в потоке, который поступает в систему.

Для начала рассчитаем Т_i– время, потраченное на ввод и работу задания.

T₁=20+235=255 T₆=5+34=39

T₂=5+63=68 T₇=20+208=228

T₃=30+115=145 T₈=30+120=150

T₄=30+115=145 T₉=10+162=172

T₅=10+165=75 T₁₀=5+34=39

Теперь для каждого задания рассчитаем взвешенное время обращения.

Составим таблицу, в которой отразим время поступления, начало загрузки, начало и конец выполнения, а также время нахождения в системе и взвешенное время обращения i задания (Wi).

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

№	1	2	3	4	5	6	7	8	9	10
Время поступления	1	8	16	24	28	31	32	40	44	46
Начало загрузки	1	8	16	161	76	251	256	306	290	251
Начало выполнения	21	13	46	191	86	256	276	336	300	256
Конец выполнения	256	76	161	306	251	290	484	456	462	290
Время нахождения в системе	235	63	115	115	165	34	208	120	162	32
W_i	1,13	1	1	2	1,2	6,64	1,98	2,64	2,43	6,25

Найдем средневзвешенное время обращения:

Максимальный коэффициент мультипрограммирования, который равен 4, был получен на участке времени: 276-296.

Средневзвешенное время обращения W_ср= 2,6.

Т_ож= 1346;

ДО SJF

Временная диаграмма мультипрограммной работы ЭВМ при исходных данных для до SJF (см. табл. 5) показана на рисунке 3.

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

Время	Событие	Свободный объем ОП=16	Свободный объем НМД=12	Km	t_пр
1	Поступило задание 1(3,4) начинается ввод задания. Процессор простаивает.	13	8	0	0
8	Поступило задание 2(9,1), начинается ввод задания. Процессор простаивает.	4	7	0	0
13	Завершен ввод задания 2. Задания на процессоре: 2.	4	7	1	3
16	Поступило задание 3(4,6), начинается ввод задания. Задания на процессоре: 2.	0	1	1	5
21	Завершен ввод задания 1. Задания на процессоре: 1, 2.	0	1	2	2
24	Поступило задание 4(4,6), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4.	0	1	2	2
28	Поступило задание 5(3,2), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5.	0	1	2	1,5
31	Поступило задание 6(4,1), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5, 6.	0	1	2	0,5
32	Поступило задание 7(3,4), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5, 6, 7.	0	1	2	4
40	Поступило задание 8(4,6), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5, 6, 7, 8.	0	1	2	2
44	Поступило задание 9(3,2), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2. Очередь заданий: 4, 5, 6, 7, 8, 9.	0	1	2	1
46	Завершен ввод задания 3. Задания на процессоре: 1, 2, 3.	0	1	3	0,3
47	Поступило задание 10(4,1), нехватка ресурсов – задание помещено в очередь. Задания на процессоре: 1, 2, 3. Очередь заданий: 4, 5, 6, 7, 8, 9, 10.	0	1	3	9,6
76	Завершено задание 2 и его ресурсы освобождены. Задания на процессоре: 1, 3. Очередь заданий: 4, 5, 6, 7, 8, 9, 10.	9	2	2	2,5
76	Из очереди выбираются задания 6(4,1) и 10(4,1), начинается ввод заданий. Задания на процессоре: 1, 3. Очередь заданий: 4, 5, 7, 8, 9.	1	0	2	2,5
81	Завершен ввод заданий 6 и 10. Задания на процессоре: 1, 3, 6, 10.	1	0	4	10
121	Завершены задания 6 и 10 и их ресурсы освобождены. Задания на процессоре: 1, 3. Очередь заданий: 4, 5, 7, 8, 9.	9	2	2	5
121	Из очереди выбирается задание 5(3,2), начинается ввод задания. Задания на процессоре: 1, 3. Очередь заданий: 4, 7, 8, 9.	6	0	2	5
131	Завершен ввод задания 5. Задания на процессоре: 1, 3, 5.	6	0	3	12,5
168	Завершено задание 3 и его ресурсы освобождены. Задания на процессоре: 1, 5. Очередь заданий: 4, 7, 8, 9.	10	6	2	15
168	Из очереди выбирается задание 4(4,6), начинается ввод задания. Задания на процессоре: 1, 5. Очередь заданий: 7, 8, 9.	6	0	2	15
198	Завершен ввод задания 4. Задания на процессоре: 1, 4, 5.	6	0	3	22,6
266	Завершено задание 1 и его ресурсы освобождены. Задания на процессоре: 4, 5. Очередь заданий: 4, 7, 8, 9.	9	4	2	5
266	Из очереди выбирается задание 9(3,2), начинается ввод задания. Задания на процессоре: 4, 5. Очередь заданий: 7, 8.	6	2	2	5
276	Завершен ввод задания 9. Задания на процессоре: 4, 5, 9.	6	2	3	8,3
291	Завершено задание 5 и его ресурсы освобождены. Задания на процессоре: 4, 9. Очередь заданий: 7, 8.	9	4	2	7,5
291	Из очереди выбирается задание 7(3,4), начинается ввод задания. Задания на процессоре: 4, 9. Очередь заданий: 8.	6	0	2	7,5
306	Завершено задание 4 и его ресурсы освобождены. Задания на процессоре: 9. Очередь заданий: 8.	10	4	1	2,5
306	Из очереди выбирается задание 8(4,6), начинается ввод задания. Задания на процессоре: 4, 9. Заданий в очереди нет.	6	0	1	2,5
311	Завершен ввод задания 7. Задания на процессоре: 7, 9.	6	0	2	12,5
336	Завершен ввод задания 8. Задания на процессоре: 7, 8, 9.	6	0	3	30
426	Завершено задание 9 и его ресурсы освобождены. Задания на процессоре: 7, 8.	9	2	2	10
446	Завершено задание 7 и его ресурсы освобождены. Задания на процессоре: 8.	12	6	1	38
484	Завершено задание 8 и его ресурсы освобождены.	16	12	0	0

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

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

T_проц. = 483-13 = 470, τ_общ. = 90*2+30+40*3+60*2+10*2 = 470

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

Аналогично ДО FIFO оценим эффективность дисциплины обслуживания, найдя средневзвешенное время обращения. Воспользуемся следующими формулами:

, где

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

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

M - количество заданий в потоке, который поступает в систему.

Для начала рассчитаем Т_i– время, потраченное на ввод и работу задания.

T₁=20+245=265 T₆=5+40=45

T₂=5+63=68 T₇=20+170=190

T₃=30+122=152 T₈=30+110=140

T₄=30+108=138 T₉=10+156=166

T₅=10+165=175 T₁₀=5+5=10

Теперь для каждого задания рассчитаем взвешенное время обращения.

№	1	2	3	4	5	6	7	8	9	10
Время поступления	1	8	16	24	28	31	32	40	44	47
Начало загрузки	1	8	16	168	121	76	291	306	266	76
Начало выполнения	21	13	46	198	161	81	311	336	276	81
Конец выполнения	266	76	168	306	296	121	484	446	426	121
Время нахождения в системе	245	63	122	108	165	40	170	110	150	40
W_i	1	1	1	2,04	1,53	2	2,38	2,9	2,3	3,5

Максимальный коэффициент мультипрограммирования, который равен 4, был получен на участках времени: 81-121.

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

Т_ож= 1056;

2.4 Выводы

Максимальный коэффициент мультипрограммирования у обоих алгоритмов 4, но в режиме максимального коэффициента мультипрограммирования алгоритм SJF(40) находится дольше, чем алгоритм FIFO(20). Это является плюсом в пользу использования алгоритма SJF в данном случае.
При использовании алгоритма SJF(1213) общее время выполнения пакета заданий меньше, чем у алгоритма FIFO(1249) при обработке данного задания.
Дисциплина обслуживания FIFO(2,8) обладает большим значением средневзвешенного времени обращения по сравнению с SJF(1,965), следовательно, для такой последовательности заданий выгоднее использовать дисциплину обслуживания SJF.
Суммарное времени ожидания предоставления ресурсов Т_ож для алгоритма FIFO(1346) больше времени ожидания Т_ож для алгоритма SJF(1056), вследствие того, что обе дисциплины обслуживания по разному распределяют ресурсы системы и взаимодействуют с заданиями.

Раздел 2

1 2 3