Операції планування та диспетчеризації

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

У більшості операційних систем універсального призначення планування здійснюється динамічно (on — line), тобто рішення приймаються під час роботи системи на основі аналізу поточної ситуації. ОС працює в умовах невизначеності — потоки і процеси з'являються у випадкові моменти часу і також непередбачувано завершуються. Динамічні планувальники можуть гнучко пристосовуватися до ситуації, що змінюється, і не використовують ніяких припущень про мультипрограмну суміш. Інший тип планування — статичний — може бути використаний в спеціалізованих системах, в яких увесь набір одночасно виконуваних завдань визначений заздалегідь, наприклад в системах реального часу. Планувальник називається статичним (чи попереднім планувальником), якщо він приймає рішення про планування не під час роботи системи, а заздалегідь (off — line).

Диспетчеризація полягає в реалізації знайденого в результаті планування (динамічного або статистичного) рішення, тобто в перемиканні процесора з одного потоку на інший. Перш ніж перервати виконання потоку, ОС запам'ятовує його контекст, з тим щоб згодом використовувати цю інформацію для подальшого відновлення виконання цього потоку. Диспетчеризація зводиться до наступного: збереження контексту поточного потоку, який вимагається змінити; завантаження контексту нового потоку, вибраного в результаті планування; запуск нового потоку на виконання.

Автоматичне планування і диспетчеризація (англ. Automated planning and scheduling, APS) — область завдань штучного інтелекту, що стосується виконання стратегії або послідовності дій, зазвичай для інтелектуальних агентів, автономних роботів і безпілотних апаратів. На відміну від класичних проблем управління і класифікації, рішення завдань цієї області комплексні, невідомі і повинні розроблятися і оптимізуватися у багатовимірному просторі.

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

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

перационная система повинна грати активну роль в організації обробки переривань. Переривання виконують дуже корисну для обчислювальної системи функцію — вони дозволяють реагувати на асинхронні але відношенню до обчислювального процесу події. В той же час переривання створюють додаткові труднощі для ОС в організації обчислювального процесу. Ці труднощі пов'язані з непередбаченими переходами управління від однієї процедури до іншої, що виникають в результаті переривань від контроллерів зовнішніх пристроїв. Можливо також виникнення в непередбачені моменти часу виключень, пов'язаних з помилками під час виконання інструкцій. Ускладнюють завдання планування обчислювальних робіт і запити на виконання системних функцій (системні виклики) від призначених для користувача застосувань, виконувані за допомогою програмних переривань. Самі модулі ОС також часто викликають один одного за допомогою програмних переривань, ще більше заплутуючи картину обчислювального процесу.

Операційна система не може втрачати контроль над ходом виконання системних процедур, що викликаються по перериваннях. Вона повинна упорядковувати їх в часі так само, як планувальник упорядковує численні призначені для користувача потоки. Крім того, сам планувальник потоків є системною процедурою, що викликається по перериваннях (апаратним — від таймера або контроллера облаштування введення-виводу, або програмним — від додатка або модуля ОС). Тому правильне планування процедур, що викликаються по перериваннях, є необхідною умовою правильного планування призначених для користувача потоків. Інакше в системі можуть виникати, наприклад, такі ситуації, коли операційна система тривалий час займатиметься завданням управління, що не вимагає миттєвої реакції, стримером, що архівує дані, в той час, коли високошвидкісний диск простоюватиме і гальмуватиме роботу численних застосувань, що обмінюються даними з цим диском. Ще один приклад такої ситуації ілюструє мал. 4.12. В даному випадку обробник переривань принтера блокує на тривалий час обробку переривання від таймера, внаслідок чого системний час на деякий час «завмирає» і потік 2, критично важливий для користувача, не отримує управління в запланований час. Гостроту проблеми дещо пом'якшує та обставина, що у багатьох випадках обробка переривання пов'язана з виконанням всього декількох операцій введення-виводу і тому має дуже невелику тривалість. Проте ОС завжди повинна контролювати ситуацію і виконувати критичну роботу вчасно, а не покладатися на волю випадку.

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

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

Мал. 4.12. неврегульована обробка переривань

Витісняючі і не витісняючі алгоритми диспетчеризації

Диспетчеризація без перерозподілу процесорного часу, тобто не витісняюча багатозадачність - це такий спосіб диспетчеризації процесів, при якому активний процес виконується до тих пір, поки він сам, за своєю ініціативою, не віддасть управління диспетчерові завдань для вибору з черги іншого, готового до виконання процесу. Дисципліни обслуговування FCFS, SJN, SRT відносяться до тих, що не витісняють.

Диспетчеризація з перерозподілом процесорного часу між завданнями, тобто витісняюча багатозадачність - це такий спосіб, при якому рішення про перемикання процесора з виконання одного процесу на виконання іншого процесу приймається диспетчером завдань, а не найактивнішим завданням. Механізм диспетчеризації зосереджений в самій ОС і програміст не повинен піклуватися про паралельне виконання свого застосування з іншими застосуваннями.

Операційна система виконує наступні функції:

- визначає момент зняття з виконання поточного завдання;

- зберігає контекст поточного завдання в дескрипторі завдання;

- вибирає з черги готових до виконання завдань наступну;

- завантажує контекст вибраного завдання;

- запускає вибране завдання на виконання.

Дисципліна RR і аналогічні їй відносяться до тих, що витісняють.

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

Контрольні запитання

1. У чому полягає основна відмінність між плануванням процесів і диспетчеризацією завдань?
2. Які дисципліни диспетчеризації завдань ви знаєте? Поясните їх основні ідеї, перерахуєте достоїнства і недоліки.
3. Розкажіть, які дисципліни диспетчеризації слід віднести до тих, що витісняють, а які — до тих, що не витісняють.

Література

Їв.ресурс: http://ru.wikipedia.org/wiki/Автоматическое планирование_