Файл: Новосибирский государственный технический университет факультет автоматики и вычислительной техники кафедра вычислительной техники.docx
Добавлен: 23.11.2023
Просмотров: 100
Скачиваний: 10
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
2.3. Временные диаграммы использования FIFO и SJF. Таблицы результатов.
ДО FIFO
Временная диаграмма мультипрограммной работы ЭВМ при исходных данных для до FIFO (см. табл. 3) показана на рисунке 1.
Таблица 3. Последовательность событий в системе (FIFO).
Рисунок 3. Временная диаграмма выполнения алгоритма FIFO.
Рисунок 4. Временная диаграмма использования ресурсов по алгоритму FIFO.
Tпроц. = 483-13 = 470, τобщ. = 90*2+30+40*3+60*2+10*2 = 470
Трудоемкость обеспечена верно.
Для оценки эффективности дисциплины обслуживания найдем средневзвешенное время обращения. Воспользуемся следующими формулами:
где
- время завершения задания,
- время поступления задания в систему,
M - количество заданий в потоке, который поступает в систему.
Для начала рассчитаем Тi – время, потраченное на ввод и работу задания.
T1=20+235=255 T6=5+34=39
T2=5+63=68 T7=20+208=228
T3=30+115=145 T8=30+120=150
T4=30+115=145 T9=10+162=172
T5=10+165=75 T10=5+34=39
Теперь для каждого задания рассчитаем взвешенное время обращения.
Составим таблицу, в которой отразим время поступления
, начало загрузки, начало и конец выполнения, а также время нахождения в системе и взвешенное время обращения i задания (Wi).
Таблица 4. Результаты работы до FIFO.
Найдем средневзвешенное время обращения:
Максимальный коэффициент мультипрограммирования, который равен 4, был получен на участке времени: 276-296.
Средневзвешенное время обращения Wср = 2,6.
Тож = 1346;
ДО SJF
Временная диаграмма мультипрограммной работы ЭВМ при исходных данных для до SJF (см. табл. 5) показана на рисунке 3.
Таблица 5. Последовательность событий в системе (SJF).
Рисунок 5. Временная диаграмма выполнения алгоритма SJF.
Рисунок 6. Временная диаграмма использования ресурсов по алгоритму SJF.
Tпроц. = 483-13 = 470, τобщ. = 90*2+30+40*3+60*2+10*2 = 470
Трудоемкость обеспечена верно.
Аналогично ДО FIFO оценим эффективность дисциплины обслуживания, найдя средневзвешенное время обращения. Воспользуемся следующими формулами:
, где
- время завершения задания,
- время поступления задания в систему,
M - количество заданий в потоке, который поступает в систему.
Для начала рассчитаем Тi – время, потраченное на ввод и работу задания.
T1=20+245=265 T6=5+40=45
T2=5+63=68 T7=20+170=190
T3=30+122=152 T8=30+110=140
T4=30+108=138 T9=10+156=166
T5=10+165=175 T10=5+5=10
Теперь для каждого задания рассчитаем взвешенное время обращения.
Составим таблицу, в которой отразим время поступления, начало загрузки, начало и конец выполнения, а также время нахождения в системе и взвешенное время обращения i задания (Wi).
Таблица 6. Результаты работы до 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 |
| Из очереди выбирается задание 5(3,2), начинается ввод задания. Задания на процессоре: 1, 3. Очередь заданий: 4, 6, 7, 8, 9, 10. | 6 | 0 | |||
| 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 |
| Из очереди выбирается задание 4(4,6), начинается ввод задания. Задания на процессоре: 1, 5. Очередь заданий: 6, 7, 8, 9, 10. | 4 | 6 | |||
| 191 | Завершен ввод задания 4. Задания на процессоре: 1, 4, 5 | 6 | 0 | 3 | 20 |
| 251 | Завершено задание 5 и его ресурсы освобождены. Задания на процессоре: 1, 4. Очередь заданий: 6, 7, 8, 9, 10. | 9 | 2 | 2 | 2,5 |
| Из очереди выбирается задания 6(4,1) и 10(4,1), начинается ввод задания. Задания на процессоре: 1, 4. Очередь заданий: 7, 8, 9. | 1 | 0 | |||
| 256 | Завершен ввод заданий 6 и 10. Завершено задание 1 и его ресурсы освобождены. Задания на процессоре: 4, 6, 10. Очередь заданий: 7, 8, 9. | 4 | 4 | 3 | 6,7 |
| Из очереди выбирается задание 7(3,4), начинается ввод задания. Задания на процессоре: 4, 6, 10. Очередь заданий: 8, 9. | 1 | 0 | |||
| 276 | Завершен ввод задания 7. Задания на процессоре: 4, 6, 7, 10 | 1 | 0 | 4 | 3,5 |
| 290 | Завершены задания 6 и 10 и их ресурсы освобождены. Задания на процессоре: 4, 7. Очередь заданий: 8, 9. | 9 | 2 | 2 | 5 |
| Из очереди выбирается задание 9(3,2), начинается ввод задания. Задания на процессоре: 4, 7. Очередь заданий: 8. | 6 | 0 | |||
| 300 | Завершен ввод задания 9. Задания на процессоре: 4, 7, 9. | 6 | 0 | 3 | 2 |
| 306 | Завершено задание 4 и его ресурсы освобождены. Задания на процессоре: 7, 9. Очередь заданий: 8. | 10 | 6 | 2 | 15 |
| Из очереди выбирается задание 8(4,6), начинается ввод задания. Задания на процессоре: 7, 9. Заданий в очереди нет | 6 | 0 | |||
| 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 – время, потраченное на ввод и работу задания.
T1=20+235=255 T6=5+34=39
T2=5+63=68 T7=20+208=228
T3=30+115=145 T8=30+120=150
T4=30+115=145 T9=10+162=172
T5=10+165=75 T10=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 |
| Wi | 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 |
| Из очереди выбираются задания 6(4,1) и 10(4,1), начинается ввод заданий. Задания на процессоре: 1, 3. Очередь заданий: 4, 5, 7, 8, 9. | 1 | 0 | |||
| 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 |
| Из очереди выбирается задание 5(3,2), начинается ввод задания. Задания на процессоре: 1, 3. Очередь заданий: 4, 7, 8, 9. | 6 | 0 | |||
| 131 | Завершен ввод задания 5. Задания на процессоре: 1, 3, 5. | 6 | 0 | 3 | 12,5 |
| 168 | Завершено задание 3 и его ресурсы освобождены. Задания на процессоре: 1, 5. Очередь заданий: 4, 7, 8, 9. | 10 | 6 | 2 | 15 |
| Из очереди выбирается задание 4(4,6), начинается ввод задания. Задания на процессоре: 1, 5. Очередь заданий: 7, 8, 9. | 6 | 0 | |||
| 198 | Завершен ввод задания 4. Задания на процессоре: 1, 4, 5. | 6 | 0 | 3 | 22,6 |
| 266 | Завершено задание 1 и его ресурсы освобождены. Задания на процессоре: 4, 5. Очередь заданий: 4, 7, 8, 9. | 9 | 4 | 2 | 5 |
| Из очереди выбирается задание 9(3,2), начинается ввод задания. Задания на процессоре: 4, 5. Очередь заданий: 7, 8. | 6 | 2 | |||
| 276 | Завершен ввод задания 9. Задания на процессоре: 4, 5, 9. | 6 | 2 | 3 | 8,3 |
| 291 | Завершено задание 5 и его ресурсы освобождены. Задания на процессоре: 4, 9. Очередь заданий: 7, 8. | 9 | 4 | 2 | 7,5 |
| Из очереди выбирается задание 7(3,4), начинается ввод задания. Задания на процессоре: 4, 9. Очередь заданий: 8. | 6 | 0 | |||
| 306 | Завершено задание 4 и его ресурсы освобождены. Задания на процессоре: 9. Очередь заданий: 8. | 10 | 4 | 1 | 2,5 |
| Из очереди выбирается задание 8(4,6), начинается ввод задания. Задания на процессоре: 4, 9. Заданий в очереди нет. | 6 | 0 | |||
| 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 – время, потраченное на ввод и работу задания.
T1=20+245=265 T6=5+40=45
T2=5+63=68 T7=20+170=190
T3=30+122=152 T8=30+110=140
T4=30+108=138 T9=10+156=166
T5=10+165=175 T10=5+5=10
Теперь для каждого задания рассчитаем взвешенное время обращения.
Составим таблицу, в которой отразим время поступления, начало загрузки, начало и конец выполнения, а также время нахождения в системе и взвешенное время обращения i задания (Wi).
Таблица 6. Результаты работы до SJF.
| № | 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 |
| Wi | 1 | 1 | 1 | 2,04 | 1,53 | 2 | 2,38 | 2,9 | 2,3 | 3,5 |