Лекція 6

Планування завдань. Алгоритми планування без перемикання і з перемиканням. Схеми призначення пріоритетів. FIFO диспетчеризація. Карусельна диспетчеризація. Адаптивна диспетчеризація.

Необхідність планування завдань з'являється, як тільки в черзі активних (готових) завдань з'являються більше одного завдання (у багатопроцесорних системах - більше число наявних процесорів). Алгоритм планування завдань є основною відмінністю систем реального часу від "звичайних" операційних систем. В останніх метою планування є забезпечення виконання всіх завдань із черги готових завдань, забезпечуючи ілюзію їхньої паралельної роботи й не допускаючи монополізацію процесора якого-небуть із завдань. В ОСРЧ же метою планування є забезпечення виконання кожного готового завдання до певного моменту часу, при цьому часто "паралельність" роботи завдань не допускається, оскільки тоді час виконання завдання буде залежати від наявності інших завдань.

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

Означення. Планувальник завдань (scheduler) - це модуль (програма), який відповідає за розподіл часу наявних процесорів між завданнями, що виконуються. Відповідає за комутацію завдань зі стану блокування в стан готовності, і за вибір завдання (завдань - за числом процесорів) із числа готових для виконання процесором (ами).

Ключовим питанням планування є вибір моменту прийняття рішення:

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

По-друге, планування необхідно, коли процес завершує роботу. Цей процес уже не існує, отже, необхідно з набору готових процесів вибрати й запустити наступний.

По-третє, коли процес блокується з якої-небудь причини, необхідно вибрати й запустити інший процес.

По-четверте, рішення по диспетчеризації повинне прийматися після розблокування процесу.

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

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

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

Пріоритетом називається число, приписане операційною системою (а саме, планувальником завдань) кожному процесу й завданню. Існують кілька схем призначення пріоритетів.

• Фіксовані пріоритети - пріоритет завданню призначається при його створенні й не міняється протягом її життя. Ця схема з різними доповненнями застосовується в
більшості систем реального часу. У схемах планування ОСРЧ часто потрібно,
щоб пріоритет кожного завдання був унікальним, тому часто ОСРЧ мають велику
кількість пріоритетів (звичайно 255 і більше).

• Турнірне визначення пріоритету - пріоритет останнього завдання, що виконувалося, знижується.

• Визначення пріоритету по алгоритму round robin - пріоритет завдання визначається її початковим пріоритетом і часом його обслуговування. Чим більше завдання обслуговується процесором, тим менше його пріоритет (але не опускається нижче деякого граничного значення). Ця схема полягає в тому або іншому вигляді застосовується в більшості UNIX системах.

Відзначимо, що в різних системах різні алгоритми планування завдань можуть вводити нові схеми зміни пріоритетів. Наприклад, у системі OS-9 пріоритети завдань, що очікують, збільшуються для запобігання занадто великих часів очікування.

Як видно з рисунка, процеси A-F перебувають у стані готовності. Процеси G-Z блоковані. Процеси A, B, C мають найвищий пріоритет. Тому саме ці процеси будуть розділяти процесор відповідно до алгоритмів диспетчеризації. Розглянемо їх.

«Першим прийшов – першим обслужений» (алгоритм FIFO). Є алгоритмом планування без перемикань. Процесам надається доступ до процесора в тому порядку, у якому вони його запитують. При FIFO диспетчеризації процес продовжує виконання, поки не наступить момент, коли він:

· добровільно звільняє керування (закінчується, блокується й т.п.);

· витісняється процесом з більше високим пріоритетом.

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

Процес A виконується доти, поки не блокується.

Процес A блокується, процес B виконується.

«Найкоротше завдання – перше». Цей алгоритм без перемикань припускає, що тимчасові відрізки роботи відомі заздалегідь. У цьому алгоритмі першим вибирається не найперша, а саме коротке завдання. Приведемо приклад.

A

B

C

D

a

B

C

D

A

b

Нехай процеси A,B,C,D мають час виконання 8,4,4,4 одиниць часу (наприклад, секунд). По алгоритму FIFO вони повинні бути запущені в тому же порядку, у якому вони розташовані у черзі (варіант a). Тоді час виконання процесу A буде дорівнює 8, B - 12, C - 16 і D - 20. Середній час виконання для цих 4 процесів буде дорівнює 14. Розглянемо тепер чергу, відсортовану за часом виконання (варіант b). Тепер час виконання процесу B буде дорівнює 4, C - 8, D - 12, A - 20. Середній час у даному варіанті буде дорівнює 11.

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

«Найменший час виконання, який залишився». Є версією попереднього алгоритму з перемиканнями. Відповідно до цього алгоритму планувальник щоразу вибирає процес із найменшим часом виконання, що залишився. У цьому випадку також необхідно знати заздалегідь час виконання кожного процесу. Коли надходить новий процес, його повний час виконання рівняється із часом, що залишився, виконання поточного процесу. Якщо час виконання нового процесу менший, часу, що виконується, процес припиняється й керування передається новому процесу. Ця схема дозволяє швидко обслуговувати короткі процеси.

«Карусельна диспетчеризація (циклічне планування)». При карусельній диспетчеризації процес продовжує виконання, поки не наступить момент, коли він:

· добровільно передає керування (тобто блокується);

· витісняється процесом з більше високим пріоритетом;

· використовував свій квант часу (timeslice). Після того, як процес використовував свій квант часу, керування передається наступному процесу, що перебуває в стані готовності й має такий же рівень пріоритету.

Карусельна диспетчеризація. Процес A виконується доти, поки він не використовував свій квант часу; потім виконується наступний процес, що перебуває в стані готовності (процес B).

«Адаптивна диспетчеризація». При адаптивній диспетчеризації процес поводиться в таким способом:

· Якщо процес використовував свій квант часу (тобто він не блокувався), то його пріоритет зменшується на 1. Це одержало назву зниження пріоритету (priority decay). "Знижений" процес не буде продовжувати "знижуватися", навіть якщо він використовував ще один квант часу й не блокувався - він знизиться тільки на один рівень нижче свого вихідного пріоритету.

· Якщо процес блокується, то йому повертається первісне значення пріоритету.

Адаптивна диспетчеризація. Процес A використовував свій квант часу; його пріоритет знизився на 1. Виконується наступний процес у стані готовності (процес B).

У системах реального часу найпоширенішими є алгоритми FIFO, адаптивній диспетчеризації, карусельній диспетчеризації і їхньому різновиду.

Дата добавления: 2013-12-14