Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

Планувальники з пріоритетами

У багатозадачних системах часто виникає питання: у якому порядку виконувати готові процеси? Як правило, буває очевидно, що одні з процесів важливіше за інших. Наприклад, в системі може існувати три процеси, що мають готові до виконання нитки: процес — мережевий файловий сервер, інтерактивний процес — текстовий редактор і процес, що займається плановим резервним копіюванням з диска на стрічку. Очевидно, що хотілося б в першу чергу розібратися з мережевим запитом, потім — відреагувати на натиснення клавіші в текстовому редакторові, а резервне копіювання може почекати сотню-другую мілісекунд. З іншого боку, ми повинні захистити користувача від ситуацій, в яких якийсь процес вообше не отримує управління, бо система постійно зайнята пріоритетнішими завданнями.
Дійсно, ви запустили те ж саме резервне копіювання, і сіли грати в тетріс або писати лист улюбленій жінці, а після півгодини гри виявили, що жодного байта не скопійовано — процесор весь час був зайнятий.
Найпростішим і найбільш поширеним способом розподілу процесів по пріоритетам є організація декількох черг відповідно до пріоритетів. При цьому процес з низькопріоритетної черги отримує управління тоді і лише тоді, коли всі черги з вищим пріоритетом порожні.

Пріоритети процесів в трансп'ютері
Простим випадком такої організації є трансп'ютер, що має дві черги. У трансп'ютері при цьому планувальник не може відібрати управління у високопріоритетного процесу. У цьому сенсі низькопріоритетні завдання вимушені покладатися на "порядність" високопріоритетних, тобто на те, що ті визволяють процесор в розумний час.
Частково схожим чином організований планувальник системи Vax/vms. Він має 32 пріоритетних черги, з яких старші 16 називаються процесами реального часу, а молодші — розділеного.
При цьому процес реального часу виконується завжди, коли готовий до виконання, і в системі немає пріоритетніших процесів. ОС і процеси розділеного часу також вимушені покладатися на його порядність. Тому привілей запускати такі процеси контролюється адміністратором системи.

Легко зрозуміти, що розділення часу забезпечує більш менш справедливий доступ до процесора для завдань з однаковим пріоритетом. В разі трансп'ютера, який має лише один пріоритет і, відповідно, одну чергу для завдань розділеного часу, цього виявляється досить. Проте сучасні ОС як спільного призначення, так і реального часу, мають багато рівнів пріоритету. Для чого це потрібно і як досягається в цьому випадку справедливий розподіл часу процесора?
Річ у тому, що в системах такого типа пріоритет процесів розділеного часу є динамічним величиною. Він змінюється залежно від того, наскільки активно завдання використовує процесор і інші системні ресурси.
У системах з пакетною обробкою, коли для завдання вказують верхній кордон часу процесора, який вона може використовувати, часто коротші завдання йдуть з вищим пріоритетом. Крім того, вищий пріоритет дають завданням, які вимагають менше пам'яті. У системах розділеного часу часто виявляється складно заздалегідь визначити час, протягом якого працюватиме завдання. Наприклад, ви відладжуєте програму. Для цієї мети ви запускаєте символьний відладчик і починаєте виконувати вашу програму в покроковому режимі. Природно, що ви не можете навіть приблизно передбачити як астрономічний час відладки, так і час центрального процесора, зайнятий при цьому. Тому зазвичай такі системи не обмежують час виконання завдання і інші ре-сурси і вимушені прогнозувати поведінку програми в майбутньому на підставі її поведінки у минулому.
Так, якщо програма початку обчислення, що не перериваються жодними зверненнями до зовнішньої пам'яті або терміналу, ми можемо передбачити, що вона займатиметься такими обчисленнями і далі. Навпаки, якщо програма зробила декілька запитів на уведення-виведення, слід чекати, що вона і далі активно видаватиме такі запити. Переважними для системи будуть ті програми, які захоплюють процесор на короткий час і швидко віддають його, переходячи в достаток чекання зовнішньої або внутрішньої події. Таким процесам система прагне привласнити вищий пріоритет. Якщо програма чекає завершення запиту на звернення до диска, то це також вигідно для системи — адже на більшості машин читання з диска і запис на нього відбуваються паралельно з роботою центрального процесора.
Таким чином, система динамічно підвищує пріоритет тим завданням, які визволили процесор в результаті запиту на уведення-виведення або чекання події і, навпаки, знижує тим завданням, які були зняті після закінчення кванта часу. Проте пріоритет не може перевищити певного значення — стартового пріоритету завдання.
При цьому найбільш високий пріоритет автоматично отримують інтерактивні завдання і програми, зайняті інтенсивним введенням-виводом. Під час виконання таких програм процесор часто виявляється вільний, і управління отримують низькопріоритетні обчислювальні завдання. Тому системи сімейства UNIX і Vax/vms навіть при дуже високому завантаженні забезпечують як прийнятний час реакції для інтерактивних програм, так і прийнятний астрономічний час виконання для пакетних завдань. Завдяки наявності класу планерування реального часу, ці ж ОС можна використовувати і в завданнях реального часу таких, як управління атомним реактором.
Система VMS підвищує пріоритет також і тим завданням, які зупинилися в очікуванні підкочування сторінки. Це зроблено тому, що якщо програма кілька разів вискочила за межі свого робочого набору (тобто зажадала ще сторінку, коли її робочий набір весь зайнятий), то вона, швидше за все, робитиме це і далі, а процесор на час підкочування вона визволяє.
Потрібно відзначити, що процес розділеного часу може підвищити свій пріоритет до максимального в класі розділення часу, але ніколи не зможе стати процесом реального часу. А для процесів реального часу динамічна зміна пріоритетів зазвичай не застосовується.

Управління пріоритетами в Os-9
Цікаво реалізована динамічна зміна пріоритету в Os-9. У цій ОС кожен процес має статично певний пріоритет і вік
(age) — кількість переглядів черги з того моменту, коли цей процес востаннє отримував управління. Обидві ці характеристики представлені 16-розрядними беззнаковими числами. Процес може підвищити або знизити свій пріоритет, виконавши відповідний системний виклик, але система за власною ініціативою ніколи не міняє його. При цьому управління кожного разу отримує процес з найбільшою сумою статичного пріоритету і віку, що динамічно змінюється (мал. 8.1 — в змальованій на малюнку ситуації буде вибраний процес 12). Якщо в двох процесів такі суми рівні, то береться процес з великим пріоритетом. Якщо у них рівні і пріоритети, то береться той, який виявився ближчим на початок черги.

Мал. 8.1. Пріоритети і вік в Os/9

Цей алгоритм гарантує, що будь-який низькопріоритетний процес рано чи пізно отримає управління. Якщо ж нам потрібно, щоб він отримував управління раніше, то ми повинні просто підвищити його пріоритет.
Крім того, можна заборонити виконання процесів із статичним пріоритетом нижче заданого. Це може зменшити завантаження процесора і, наприклад, дозволить високопріоритетним процесам обробити потік зовнішніх подій, що збільшився. Зрозуміло, що таку заборону можна вводити лише на невеликий час, щоб не порушити справедливий розподіл процесора.
Можливе і тонше регулювання — системний виклик, який забороняє збільшувати вік процесу більше заданого значення. Тобто, процес, стоячи в черзі, може досягти цього максимального віку, після чого він як і раніше залишається в черзі, але його вік вже не збільшується.
Схема розподілу часу процесора, що виходить в результаті, частково схожа на двошарову організацію Vax/vms, коли виконання процесів із статичним пріоритетом, що перевищує кордон, не може бути перерване низькопріоритетним процесом.

 

:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017