Алгоритм планування процесів Shortest-Job-First (невитісняючі) - розділ Освіта, Екзаменаційні питання по курсу Операційні системи При Розгляді Алгоритмів Fcfs І Rr Ми бачили, Наскільки Істотним Для Н.
При розгляді алгоритмів FCFS і RR ми бачили, наскільки істотним для них є порядок розташування процесів в черзі процесів, готових до виконання. Якщо короткі завдання розташовані в черзі ближче до її початку, то загальна продуктивність цих алгоритмів значно зростає.
Якби ми знали час наступних CPU burst для процесів, що знаходяться в стані готовність, то могли б вибрати для виконання не процес з початку черги, а процес з мінімальною тривалістю CPU burst. Якщо ж таких процесів два або більше, то для вибору одного з них можна використовувати вже відомий нам алгоритм FCFS. Квантування часу при цьому не застосовується.
Описаний алгоритм отримав назву "найкоротша робота першої" або Shortest Job First (SJF).
SJF-алгоритм короткострокового планування може бути як витісняє, так і невитісняючі.
При невитісняючі SJF-плануванні процесор надається обраному процесу на все необхідне йому час, незалежно від подій, що відбуваються в обчислювальній системі.
Розглянемо приклад роботи невитісняючі алгоритму SJF. Нехай в стані готовність знаходяться чотири процесу, p0, p1, p2 і p3, для яких відомі часи їх чергових CPU burst. Ці часи наведені в таблиці.
Як і раніше, будемо вважати, що вся діяльність процесів обмежується використанням лише одного проміжку CPU burst, що процеси не роблять операцій введення-виведення і що часом перемикання контексту можна знехтувати
При використанні невитісняючі алгоритму SJF першим для виконання буде обраний процес p3, що має найменше значення тривалості чергового CPU burst. Після його завершення для виконання вибирається процес p1, потім p0 і, нарешті, p2.
Як ми бачимо, середній час очікування для алгоритму SJF становить
(4 + 1 + 9 + 0) / 4 = 3,5 одиниці часу.
Для алгоритму FCFS при порядку процесів p0, p1, p2, p3 середній час очікування буде дорівнювати
(0 + 5 + 8 + 15) / 4 = 7 одиницям часу,
т. е. буде в два рази більше, ніж для алгоритму SJF.
Можна показати, що для заданого набору процесів (якщо в черги не з'являються нові процеси) алгоритм SJF є оптимальним з точки зору мінімізації середнього часу очікування серед класу невитисняючих алгоритмів
Основну складність при реалізації алгоритму SJF представляє неможливість точного знання тривалості чергового CPU burst для виконуються процесів.
У пакетних системах кількість процесорного часу, необхідне завданням для виконання, вказує користувач при формуванні завдання. Ми можемо брати цю величину для здійснення довгострокового SJF-планування.
Якщо користувач вкаже більше часу, ніж йому потрібно, він буде чекати результату довше, ніж міг би, так як завдання буде завантажено в систему пізніше.
Якщо ж він вкаже меншу кількість часу, завдання може не дорахуватися до кінця.
Таким чином, в пакетних системах рішення задачі оцінки часу використання процесора перекладається на плечі користувача.
При короткостроковому плануванні ми можемо робити тільки прогноз тривалості наступного CPU burst, виходячи з передісторії роботи процесу
Всі теми даного розділу:
Дослідження об'єкта як системи, ознаки якої складності системи
Об'єктом пізнання є частина реального світу, яка виділяється і сприймається як єдине ціле протягом тривалого часу. Об'єкт може бути матеріальним або абстрактним, природ
Факторні підсистеми складних систем, принципи системного підходу.
Складні системи можна поділити на такі факторні підсистеми: 1) вирішальну, яка приймає глобальні рішення у взаємодії із зовнішнім середовищем і розподіляє локальні завдання
Архітектура процесора з точки зору програміста
Для програміста будь-який процесор складається з набору регістрів пам'яті різного призначення, які певним чином пов'язані між собою і обробляються відповідно до деякої системою прав
Основні етапи еволюції обчислювальних систем
Існують різні класифікації ВС. Найбільш часто вони класифікуються за елементній базі. Відповідно до цієї класифікації в еволюції ВС виділяються 4 етапи: 1. Перший період (1945
Організація ефективного використання ресурсів комп'ютера. Полегшення процесів експлуатації апаратних і програмних засобів обчислювальної системи
До числа основних ресурсів сучасних ОС можна віднести процесори, ОЗУ, таймери, набори даних, диски, накопичувачі на магнітних стрічках, принтери, мережеві пристрої і т.д. Ресурси повинні бути розбраті
Можливості розвитку ОС, вимоги до ОС, засоби апаратної підтримки ОС
Необхідність розвитку обумовлена наступними причинами: ¾ оновлення і виникнення нових видів апаратного забезпечення ¾ поява нових сервісів (для задовольнив
Основні принципи розробки архітектури ОС
Архітектура - це базова організація системи, втілена в її компонентах, їхні стосунки між собою і з оточенням, а також принципи, що визначають проектування і розвиток системи [IEE [1 471].
Монолітна архітектура ОС
У монолітної архітектури ОС вже присутня якась структурованість, яка визначається набором процедур. Тут кожна процедура має добре певний інтерфейс і може викликати лю
Багаторівнева архітектура ОС
Багаторівнева архітектура з'явилася у відповідь на обмеження монолітної архітектури в плані розширюваності, переносимості та сумісності. Основна її ідея полягає в наступному: 1. П
Поняття процесу, стану процесу, модель процесу
Процес є фундаментальним поняттям, що відбиває функціонування ОС. За своєю суттю це динамічний об'єкт, над яким ОС виконує певні дії. Розглянемо моделі процесо
Планування процесів. рівні планування
Процеси - діяльність ОС. Однією зі складових процесів є ресурси. Вони обмежені. Оскільки процесів багато, необхідно організувати координацію їх використання. Крім того, процеси -
Критерії планування і вимоги до алгоритмів
Зрозуміло, що можуть існувати різні алгоритми планування. І хотілося б, щоб вони були універсальні, але реально цього не відбувається. Найчастіше той чи інший алгоритм підходить до виразно
параметри планування
При планування ОС спирається на два класи параметрів об'єкта. Перший клас відображає статистичні параметри, другий - динамічні. Статистичні параметри не змінюються в ході функціонування
Невитісняючаі витісняюча планування
Процес планування здійснюється частиною ОС, званої планувальником. Він може приймати рішення про вибір для виконання нового процесу з числа що знаходяться в стані готовність в наступних 4
Алгоритм планування процесів First-Come, First-Served (FCFS)
Реально існує безліч різноманітних алгоритмів планування. Кожен з них ефективний для певного класу задач. Існують алгоритми, які можна застосовувати на різних рівнів
Алгоритм планування процесів Round Robin (RR)
Зазначені недоліки усуваються в наступному алгоритмі: Round Robin (RR). В цілому він схожий на попередній алгоритм, але додатково вводиться механізм витісняє планування.
Алгоритм планування процесів Shortest-Job-First (витісняє)
При витісняє SJF-плануванні враховується поява нових процесів в черзі готових до виконання (з числа знову народилися або розблокованих) під час роботи обраного процесу.
Потоки. Мультипрограмування на рівні потоків
Щоб підтримувати мультипрограмування (багатозадачність), ОС повинна визначити і оформити для себе ті внутрішні одиниці роботи, між якими буде розділятися процесор і інші ресурси комп
Загальні характеристики зв'язку між процесами
* Напрямок зв'язку. Зв'язок буває однонаправлена (симплексна) і двунаправленная (напівдуплексна для почергової передачі інформації і дуплексная з можливістю одночасної передачі та
Семафори, м'ютекси. Використання семафорів для синхронізації процесів
Узагальненням блокуючих змінних є так звані семафори Дійкстра. Замість довічних змінних Дійкстра (Dijkstra) запропонував використовувати змінні, які можуть приймати цілі
Функції ОС по управлінню пам'яттю
Під пам'яттю (memory) в даному випадку мається на увазі оперативна (основна) пам'ять комп'ютера. У однопрограмних операційних системах основна пам'ять раз-деляется на дві частини. Одна частина - для оп
Віртуальна пам'ять
Об'єм оперативної пам'яті істотно позначається на характері протікання ви- числівника процесу, так як він обмежує число одночасно виконуються програм, т. Е. Урове
Програмна підтримка механізмів віртуальної пам'яті
52. Загальна характеристика пристроїв введення - виведення Зовнішні пристрої, що виконують операції введення-виведення, можна розділити на три групи: · пристрої, що працюють з
Призначення і завдання підсистеми введення-виведення
Обмін даними між користувачами, додатками і периферійними уст-ройствамі комп'ютера виконує спеціальна підсистема ОС - підсистема вводу-ви-вода. Власне для виконання цього завдання і був
Драйвери пристроїв введення виведення
Спочатку термін «драйвер» застосовувався в досить вузькому сенсі; під драйвером розуміється програмний модуль, який: · входить до складу ядра ОС, працюючи в привілейованому режимі;
Багатошарова модель підсистеми введення-виведення
При великій різноманітності пристроїв введення-виведення, що володіють істотно різними характеристиками, ієрархічна структура підсистеми введення-виведення по-зволяет дотримати баланс між двома суперечать
Архітектура файлової системи
Класична схема організації програмного забезпечення файлової системи представлена на рис.
Логічна організація файлів
Логічний введення-виведення надає додаткам і користувачам доступ до записів. Метод доступу Найбільш близький користувачеві рівень файлової системи. Він забезпечує стандартний
каталоговий системи
Сполучною ланкою між системою управління файлами і набором файлів слу-жит файловий каталог. Найпростіша форма системи каталогів полягає в тому, що має-ся один каталог, в якому містяться всі ф
Фізична організація файлової системи
Інформаційна структура магнітних дисків Подання користувачів про файлову систему як про ієрархічно організовує-ванном безлічі інформаційних блоків має мало спільного з порядком хр
S - номер сектора
На кожній стороні кожної пластини розмічені тонкі концентричні кільця -дорожкі (tracks), на яких зберігаються дані. Нумерація доріжок починається з 0 від зовнішнього краю до
Фізична організація FAT
Для забезпечення доступу додатків до файлів операційна система з файлової системою FAT використовує такі структури: · завантажувальні сектора головного і додаткових разде
Основні особливості файлової системи NTFS 5 в порівнянні з попередніми файловими системами Microsoft.
Файлова система NTFS була повністю розроблена заново і досить складна. Кожен том NTFS (т. Е. Дисковий розділ) містить файли, каталоги, бітові масиви і інші структури даних. кожен том
Набір API для Win 32.
Цей набір інтерфейсів прикладного програмування дозволяє виконувати шифрування файлів, дешифрування і відновлення зашифрованих файлів, а також їх імпорт і експорт (без попереднього деші