Диспетчеризація потоків

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

1. FІFO (First In First Out) – Перший Увійшов – Перший Вийшов. Першою виконується задача, яка першою зайшла в чергу, при цьому вона виконується доти, поки не закінчить свою роботу або не буде заблокована в очікуванні звільнення деякого ресурсу або події. Після цього керування передається наступній у черзі задачі.

2. Карусельна багатозадачність (round robin). При цьому методі диспетчеризації в системі задається спеціалізована константа, що визначає тривалість безперервного виконання потоку, так називаний квант часу виконання (time slice). Таким чином, виконання потоку може бути перервано або закінченням його роботи, або блокуванням в очікуванні ресурсу або події, або завершенням кванта часу (того самого time slice). Після цього керування передається наступному за чергою потоку. По закінченні часу останнього потоку керування передається першому потоку, що знаходиться у стані готовності. Таким чином, виконання кожного потоку розбито на послідовність часових циклів.

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

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

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

3. У задачах реального часу пред’являються специфічні вимоги до методів диспетчеризації, оскільки передача керування потоку повинна визначатися критичним строком його обслуговування (так званим deadline-driven scheduling). Найбільшою мірою цій вимозі відповідає витисняюча пріоритетна багатозадачність. Суть цього методу полягає у тому, що як тільки потік з більш високим, чим у активного потоку, пріоритетом переходить у стан готовності, активний потік витісняється (тобто з активного стану примусово переходить у стан готовності) і керування передається більш пріоритетному потоку.

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

Для СРЧ, що застосовуються в обробці періодичних подій, у 1970 році був запропонований математичний апарат, що дозволяє визначити, чи є система диспетчируємою. Цей апарат називається "Частотний монотонний аналіз" (ЧМА) (Rate Monotonic Analyzing). Ефективність даного математичного апарата призвела до того, що ЧМА був прийнятий як стандарт багатьма провідними організаціями галузі (Boeing, NASA, US Navy, European Space Agency та ін.). Це примусило розробників ОСРЧ враховувати вимоги по застосуванню ЧМА при розробці своїх систем. Можливість застосування ЧМА обмежена декількома умовами, першою з яких є диспетчеризація потоків методом витисняючої пріоритетної багатозадачності.

Таким чином, з урахуванням стандартів, прийнятих провідними виробниками, можна сформувати першу вимогу до ОСРЧ: ОСРЧ повинна реалізовувати можливість багатозадачності, причому з підтримкою витисняючої пріоритетної методики диспетчеризації.

Дата добавления: 2014-01-07