3.3. Витісняючі і невитісняючі алгоритми планування

Існує два основних типи процедур планування процесів - витісняючі (preemptive) і невитісняючі (non-preemptive).

Non-preemptive multitasking - невитісняюча багатозадачність - це спосіб планування процесів, при якому активний процес виконується доти, поки він сам, за власною ініціативою, не віддасть керування планувальнику ОС для того, щоб той вибрав з черги інший, готовий до виконання процес.

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

Поняття preemptive і non-preemptive іноді ототожнюються з поняттями пріоритетних і безприорітетних дисциплін, що зовсім невірно, а також з поняттями абсолютних і відносних пріоритетів, що невірно. Невитісняюча і витісняюча багатозадачність - це більш широкі поняття, чим типи пріоритетності. Пріоритети задач можуть як використовуватися, так і не використовуватися і при витісняючіх, і при невитисняючих способах планування. Так, у випадку використання пріоритетів дисципліна відносних пріоритетів може бути віднесена до класу систем із не витісняючої багатозадачності, а дисципліна абсолютних пріоритетів - до класу систем із витісняючої багатозадачності. А безпріорітетна дисципліна планування, заснована на виділенні рівних квантів часу для всіх задач, відноситься до витісняючих алгоритмів.

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

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

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

Однак розподіл функцій планувальника між системою і додатками не завжди є недоліком, а за певних умов може бути і перевагою, тому що дає можливість розроблювачу додатків самому проектувати алгоритм планування, найбільш придатний для даного фіксованого набору задач. Тому що розроблювач сам визначає в програмі момент часу віддачі керування, то при цьому виключаються нераціональні переривання програм у "незручні" для них моменти часу. Крім того, легко дозволяються проблеми спільного використання даних: задача під час кожної ітерації використовує їхній монопольно й упевнена, що протягом цього періоду ніхто іншої не змінить ці дані. Істотною перевагою non-preemptive систем є більш висока швидкість переключення з задачі на задачу.

Прикладом ефективного використання невитісняючої багатозадачності є файл-сервер NetWare, у якому, у значній мірі завдяки цьому, досягнута висока швидкість виконання файлових операцій. Менш удалим виявилося використання невитісняючої багатозадачності в операційному середовищі Windows 3.х.

Однак майже у всіх сучасних ОС, орієнтованих на високопродуктивне виконання додатків (UNIX, Windows NT, OS/2, VAX/VMS), реалізована витісняюча багатозадачність. Останнім часом дійшла черга і до ОС класу настільних систем, наприклад, OS/2 Warp і Windows 95. Можливо в зв'язку з цим що витісняє багатозадачність часто називають щирою багатозадачністю.

Взаємодія процесів. Транспортери, сигнали, семафори, черги.

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

Буфер має фіксовані розміри, тому процеси можуть знаходитись в стані очікування, коли:

буфер заповнений – очікує процес виробник;

буфер вільний – очікує процес користувач.

Буфер може надаватися і підтримуватися самою ОС, наприклад з допомогою засобів міжпроцесорної комунікації, або повинен бути організованим прикладним програмістом. При цьому обидва процеси використовують спільну ділянку пам’яті. Взаємодія заключається в передачі даних між процесами, або сумісному використанні деяких ресурсів, і, як правило реалізується з допомогою таких механізмів, як: транспортери (канали), черги, сигнали, семафори.

Транспортери (канали) – є засобом взаємодії споріднених процесів, представляють собою область пам’яті, яка має файлову організацію, для якої забезпечується запис і зчитування даних транспортерів. Реалізується черга обслуговування, порядок запису даних на транспортер не змінний, не допускається повторне зчитування даних. Обмін даними виконується не безпосередньо, а через транспортер. Дочірні процеси можуть використовувати батьківський транспортер.

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

Створення черги;

Зчитування черги;

Перегляд черги;

Закриття черги.

Записуючий процес виконує слідуючи дії:

Відкрити чергу;

Записати в чергу;

Закрити чергу;

Сигнали. Сигнал є механізмом передачі вимоги від одного процесу до іншого на негайне виконання дії.