Головна

Shortest-Job-First (SJF)

При розгляді алгоритмів FCFS і RR ми бачили, наскільки істотним для них є порядок розташування процесів в черзі процесів готових до виконання. Якщо короткі завдання розташовані в черзі ближче до її початку, то загальна продуктивність цих алгоритмів значно зростає. Якби ми знали час наступних CPU burst для процесів, що знаходяться в стані готовність, То могли б вибрати для виконання не процес з початку черги, а процес з мінімальною тривалістю CPU burst. Якщо ж таких процесів два або більше, то для вибору одного з них можна використовувати вже відомий нам алгоритм FCFS. Квантування часу при цьому не застосовується. Описаний алгоритм отримав назву "найкоротша робота першої" або Shortest Job First (SJF).

SJF алгоритм короткострокового планування може бути як витісняє, так і невитісняючі. При невитісняючі SJF плануванні процесор надається обраному процесу на все потрібне йому час, незалежно від подій, що відбуваються в обчислювальній системі. При витісняє SJF плануванні враховується поява нових процесів в черзі готових до виконання (з числа знову народилися або розблокованих) під час роботи обраного процесу. Якщо CPU burst нового процесу менше, ніж залишок CPU burst у що виконується, то що виконується процес витісняється новим.

Розглянемо приклад роботи невитісняючі алгоритму SJF. Нехай в стані готовність знаходяться чотири процесу p0, p1, p2 і p3, Для яких відомі часи їх чергових CPU burst. Ці часи наведені в таблиці 3.4. Як і раніше, будемо вважати, що вся діяльність процесів обмежується використанням лише одного проміжку CPU burst, що процеси не роблять операцій введення-виведення, і що час перемикання контексту дуже малий.

 процес p0 p1 p2 p3
 Тривалість чергової CPU burst

Таблиця 3.4.

При використанні невитісняючі алгоритму SJF першим для виконання буде обраний процес p3, Що має найменше значення чергового CPU burst. Після його завершення для виконання вибирається процес p1, Потім p0 і, нарешті, p2. Вся ця картина зображена в таблиці 3.5.

 час
p0 Г Г Г Г И И И И И              
p1 Г И И И                        
p2 Г Г Г Г Г Г Г Г Г И И И И И И И
p3 И                              

Таблиця 3.5.

Як бачимо, середній час очікування для алгоритму SJF становить (4 + 1 + 9 + 0) / 4 = 3,5 одиниці часу. Легко порахувати, що для алгоритму FCFS при порядку процесів p0, p1, p2, p3 ця величина буде дорівнювати (0 + 5 + 8 + 15) / 4 = 7 одиницям часу, т. е. буде в 2 рази більше, ніж для алгоритму SJF. Можна показати, що для заданого набору процесів (якщо в черги не з'являються нові процеси) алгоритм SJF є оптимальним з точки зору мінімізації середнього часу очікування серед класу всіх невитисняючих алгоритмів.

Для розгляду прикладу витісняє SJF планування ми візьмемо ряд процесів p0, p1, p2 і p3з різними часом CPU burst і різними моментами їх появи в черзі процесів готових до виконання (див. таблицю 3.6.).

 процес  Час появи в черзі  Тривалість чергової CPU burst
p0
p1
p2
p3

Таблиця 3.6.

У початковий момент часу в стані готовність знаходяться тільки два процеси p0 і p3. Менший час чергового CPU burst виявляється у процесу p3, Тому він і вибирається для виконання (див. Таблицю 3.7.). Після 2-х одиниць часу в систему надходить процес p1. Час його CPU burst менше, ніж залишок CPU burst у процесу p3, Який витісняється зі стану виконання і перетворюється на стан готовність. Після ще 2-х одиниць часу процес p1 завершується, і для виконання знову вибирається процес p3. У момент часу t = 6 в черзі процесів готових до виконання з'являється процес p2, Але оскільки йому для роботи потрібно 7 одиниць часу, а процесу p3 залишилося працювати всього 2 одиниці часу, то процес p3 залишається в стані виконання. Після його завершення в момент часу t = 7 в черзі знаходяться процеси p0 і p2, З яких вибирається процес p0. Нарешті, останнім отримає можливість виконуватися процес p2.

 час
p0 Г Г Г Г Г Г Г И И И
p1     И И            
p2             Г Г Г Г
p3 И И Г Г И И И      
 час
p0 И И И              
p1                    
p2                    
p3 Г Г Г И И И И И И И

Таблиця 3.7.

Основну складність при реалізації алгоритму SJF представляє неможливість точного знання часу чергового CPU burst для виконуються процесів. У пакетних системах кількість процесорного часу, що вимагається завданням для виконання, вказує користувач при формуванні завдання. Ми можемо брати цю величину для здійснення довгострокового SJF планування. Якщо користувач вкаже більше часу, ніж йому потрібно, він буде чекати отримання результату довше, ніж міг би, так як завдання буде завантажено в систему пізніше. Якщо ж він вкаже меншу кількість часу, завдання може не дорахуватися до кінця. Таким чином, в пакетних системах рішення задачі оцінки часу використання процесора перекладається на плечі користувача. При короткостроковому плануванні ми можемо робити тільки прогноз тривалості наступного CPU burst, виходячи з передісторії роботи процесу. Нехай t (n) - Величина n-го CPU burst, T (n + 1) - пророкує значення для n + 1-го CPU burst, a - деяка величина в діапазоні від 0 до 1.

Визначимо рекурентне співвідношення

T (0) покладемо довільній константою. Перший доданок враховує останнім поведінку процесу, тоді як другий доданок враховує його передісторію. При a = 0 ми перестаємо стежити за останніми поведінкою процесу, фактично вважаючи

тобто оцінюючи все CPU burst однаково, виходячи з деякого початкового припущення.

Поклавши a = 1, ми забуваємо про передісторію процесу. В цьому випадку ми вважаємо, що час чергового CPU burst буде збігатися з часом останнього CPU burst:

зазвичай вибирають

для рівноцінного обліку останнього поведінки і передісторії. Треба відзначити, що такий вибір a зручний і для швидкої організації обчислення оцінки T (n + 1). Для підрахунку нової оцінки потрібно взяти стару оцінку, скласти з виміряним часом CPU burst і отриману суму розділити на 2, наприклад, за допомогою її зсуву на 1 біт вправо. Отримані оцінки T (n + 1) застосовуються як тривалості чергових проміжків часу безперервного використання процесора для короткострокового SJF планування.

гарантоване планування

При інтерактивній роботі N користувачів в обчислювальній системі можна застосувати алгоритм планування, який гарантує, що кожен із користувачів матиме в своєму розпорядженні ~ 1 / N частину процесорного часу. Пронумеруємо всіх користувачів від 1 до N. Для кожного користувача з номером i введемо дві величини: Ti - Час перебування користувача в системі, або, іншими словами тривалість сеансу його спілкування з машиною, і ti - Сумарне процесорний час вже виділене всім його процесів протягом сеансу. Справедливим для користувача було б отримання Ti/ N процесорного часу. якщо

то i - Й користувач несправедливо обділений процесорним часом. Якщо ж

то система явно благоволить до користувача з номером i. Обчислимо для кожного користувача процесу значення коефіцієнта справедливості

і будемо надавати черговий квант часу процесу з найменшою величиною цього відношення. Запропонований алгоритм називають алгоритмом гарантованого планування. До недоліків цього алгоритму можна віднести неможливість передбачити поведінку користувачів. Якщо деякий користувач відправиться на пару годин пообідати і поспати, не перериваючи сеансу роботи, то після повернення його процеси будуть отримувати невиправдано багато процесорного часу.

пріоритетне планування

Алгоритми SJF і гарантованого планування є окремі випадки пріоритетного планування. При пріоритетному плануванні кожному процесу присвоюється певний числове значення - пріоритет, відповідно до якого йому виділяється процесор. Процеси з однаковими пріоритетами плануються в порядку FCFS. Для алгоритму SJF як такого пріоритету виступає оцінка тривалості наступного CPU burst. Чим менше значення цієї оцінки, тим вищий пріоритет має процес. Для алгоритму гарантованого планування пріоритетом служить обчислений коефіцієнт справедливості. Чим він менше, тим більше пріоритет у процесу.

Принципи призначення пріоритетів можуть спиратися як на внутрішні критерії обчислювальної системи, так і на зовнішні по відношенню до неї. Внутрішні використовують різні кількісні та якісні характеристики процесу для обчислення його пріоритету. Це можуть бути, наприклад, певні обмеження за часом використання процесора, вимоги до розміру пам'яті, число відкритих файлів і використовуваних пристроїв введення-виведення, ставлення середніх тривалостей I / O burst до CPU burst і т. Д. Зовнішні критерії виходять з таких параметрів, як важливість процесу для досягнення будь-яких цілей, вартість сплаченого процесорного часу і інших політичних чинників. Високий зовнішній пріоритет може бути присвоєно завданню лектора або того, хто заплатив $ 100 за роботу протягом однієї години.

Планування з використанням пріоритетів може бути як витісняє, так і невитісняючі. При витісняє плануванні процес з більш високим пріоритетом, що з'явився в черзі готових процесів, витісняє що виконується процес з більш низьким пріоритетом. У разі невитісняючі планування він просто стає в початок черги готових процесів. Давайте розглянемо приклади використання різних режимів пріоритетного планування.

Нехай в чергу процесів, що знаходяться в стані готовність, надходять ті ж процеси, що і в прикладі з розділу 3.5.3. для витісняє алгоритму SJF, тільки їм додатково ще присвоєні пріоритети (див. таблицю 3.8.). В обчислювальних системах не існує певної угоди, яке значення пріоритету - 1 або 4 вважати більш пріоритетним. Щоб уникнути плутанини, у всіх наших прикладах ми будемо припускати, що більше значення відповідає меншому пріоритету, тобто найбільш пріоритетним в нашому прикладі є процес p3, А найменш пріоритетним - процес p0.

 процес  Час появи в черзі  Тривалість чергової CPU burst  пріоритет
p0
p1
p2
p3

Таблиця 3.8.

Як поводитимуться процеси при використанні невитісняючі пріоритетного планування? Першим для виконання в момент часу t = 0 вибирається процес p3, Як володіє найвищим пріоритетом. Після його завершення в момент часу t = 5 в черзі процесів готових до виконання виявляться два процеси p0 і p1. Більший пріоритет з них у процесу p1 він і почне виконуватися (див. таблицю 3.9.). Потім в момент часу t = 8 для виконання буде обраний процес p2 і лише потім процес p0.

 час
p0 Г Г Г Г Г Г Г Г Г Г
p1     Г Г Г И И      
p2             Г И И И
p3 И И И И И          
 час
p0 Г Г Г Г И И И И И И
p1                    
p2 И И И И            
p3                    

Таблиця 3.9.

Іншим буде надання процесора процесам в разі витісняє пріоритетного планування (див. Таблицю 3.10.). Першим, як і в попередньому випадку, виконуватися почне процес p3, А по його закінченні процес p1. Однак в момент часу t = 6 він буде витіснений процесом p2 і продовжить своє виконання тільки в момент часу t = 13. Останнім, як і раніше буде виконаний процес p0.

 час
p0 Г Г Г Г Г Г Г Г Г Г
p1     Г Г Г И Г Г Г Г
p2             И И И И
p3 И И И И И          
 час
p0 Г Г Г Г И И И И И И
p1 Г Г Г И            
p2 И И И              
p3                    

Таблиця 3.10.

У розглянутому вище прикладі пріоритети процесів не змінювалися з плином часом. Такі пріоритети прийнято називати статичними. Механізми статичної пріоритетності легко реалізувати, і вони пов'язані з відносно невеликими витратами на вибір найбільш пріоритетного процесу. Однак статичні пріоритети не реагують на зміни ситуації в обчислювальній системі, які можуть зробити бажаною коригування порядку виконання процесів. Більш гнучкими є динамічні пріоритети процесів, які змінюють свої значення по ходу виконання процесів. Початкове значення динамічного пріоритету, присвоєне процесу, діє протягом лише короткого періоду часу, після чого йому призначається нове, більш відповідне значення. Зміна динамічного пріоритету процесу є єдиною операцією над процесами, яку ми до сих пір не розглянули. Як правило, зміна пріоритету процесів проводиться узгоджено з вчиненням будь-яких інших операцій: при народженні нового процесу, при розблокуванні або блокуванні процесу, після закінчення певного кванта часу або після його завершення. Прикладами алгоритмів з динамічними пріоритетами є алгоритм SJF і алгоритм гарантованого планування. Схеми з динамічної пріоритетністю набагато складніше в реалізації і пов'язані з великими витратами в порівнянні зі статичними схемами. Однак їх використання передбачає, що ці витрати виправдовуються поліпшенням поведінки системи.

Головна проблема пріоритетного планування полягає в тому, що при неналежному виборі механізму призначення та зміни пріоритетів низькопріоритетні процеси можуть бути не запущені невизначено довгий час. Зазвичай трапляється одне з двох. Або вони все ж чекають своєї черги на виконання (о дев'ятій годині ранку в неділю, коли всі пристойні програмісти лягають спати). Або обчислювальну систему доводиться вимикати, і вони губляться (при зупинці IBM 7094 в Массачусетському технологічному інституті в 1973 році були знайдені процеси, запущені в 1967 році і жодного разу з тих пір не виконувалися). Вирішення цієї проблеми може бути досягнуто за допомогою збільшення з часом значення пріоритету процесу, що знаходиться в стані готовність. Нехай спочатку процесам присвоюються пріоритети від 128 до 255. Кожен раз, після закінчення певного проміжку часу, значення пріоритетів готових процесів зменшуються на 1. Процесу, що побував в стані виконання, Відновлюється первісне значення пріоритету. Навіть така груба схема гарантує, що будь-який процес в розумні терміни буде надано право на виконання.




 Структура обчислювальної системи |  Що таке ОС |  Коротка історія еволюції обчислювальних систем |  Системні виклики |  виняткові ситуації |  Монолітне ядро |  Листкові системи (Layered systems) |  Віртуальні машини |  Мікроядерна архітектура. |  змішані системи |

© um.co.ua - учбові матеріали та реферати