Алгоритми вибору чергової обробки

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

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

конання процесу завершено; процес перейшов у стан очікування; центральний процесор знадобився для обслуговування процесу з вищим пріоритетом; завершився виділений процесу квант часу; сталася помилка в системі.

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

планування черговості обробки. В даний час найбільш відомими є:

• алгоритм циклічної обробки;

• алгоритм черг зі зворотним зв'язком;

• алгоритм вибору за характером використання попереднього кванта;

• алгоритм вибору з пріоритетом за характером блокування.

Практично всі алгоритми планування черговості обробки мають евристичний характер. Сигналом до початку

роботи цих алгоритмів служать зазначені вище події, що настали у системі:

• якщо попередній процес закінчився, то виконуються дії по його виведення з системи:

• якщо попередній процес перейшов у стан очікування, то він переміщається в чергу блокованих процесів;

• якщо попередній процес перерваний операційною системою через те, що ЦП знадобився для обслуговування іншого процесу з вищим пріоритетом, то перерваний процес міститься в чергу перерваних процесів;

• якщо попередній процес вичерпав виділений йому квант часу, то він надходить в чергу готових процесів;

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

Логіка роботи всіх алгоритмів планування черговості обробки практично збігається. Розрізняються вони лише

реалізаціями блоків "Вибір довжини кванта" і "Вибір чергового процесу".

Розглянемо алгоритми реалізації блоку "вибір чергового процесу".

Алгоритм циклічної обробки процесів не використовує жодної інформації про пріоритети оброблюваних

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

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

Алгоритм черг зі зворотним зв'язком організовує деяку кількість М черг, кожна з яких обслуговується в порядку надходження. Новий процес, що надійшов в систему, потрапляє в чергу № 1. Після закінчення використання чергового кванта часу процес переходить з черги з номером m в чергу з номером m + 1.

Алгоритм вибору за характером використання попереднього кванта розрізняє два типи стану готовності процесів: низькопріоритетною і високопріоритетною готовністю.

Якщо процес повністю використав попередній виділений квант часу ЦП, то йому присвоюється стан

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

АЛГОРИТМИ ВИБОРУ ВЕЛИЧИНИ КВАНТА

Вибір величини кванта є принципово необхідним у режимі поділу часу. Процедура квантування

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

поширеними є:

- Алгоритм рівномірного квантування;

- Алгоритм квантування по пріоритету процесу;

- Алгоритм мінімізації кількості перемикань між процесами.

Алгоритм рівномірного квантування - найпростіший із згаданих вище алгоритмів. Відповідно до цього алго-

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

собою. Алгоритм квантування по пріоритету процесу здійснює регулювання тривалості кванта qi для i-го про-

цесу залежно від його поточного пріоритету pi. Функціональна залежність qi = qi (pi) може мати будь допустимий вид і повинна мати такі основні характеристики: монотонність, позитивна визначеність, обмеженість. Алгоритм квантування з мінімізацією кількості перемикань полягає в тому, що активізується процес займає не тільки свій квант, але і залишки квантів процесів, які перейшли до цього моменту часу в стан сподіваня.

Засоби управління ресурсами

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

Основними функціями управління ресурсами є:

- Облік наявності та стану ресурсів;

- Прийом і облік заявок на ресурси від завдань і процесів;

- Розподіл ресурсів між завданнями та процесами;

- Організація використання ресурсів, виділених кожній задачі чи процесу;

- Повернення ресурсу в систему по мірі його звільнення споживачем.

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

такі основні дані:

• для ресурсів:

- Облікова інформація про ресурс (ідентифікатор, клас, кількість каналів тощо);

- Код стану ресурсу;

- Ідентифікатор процесу-власника і т.п.;

• для заявок на ресурси:

- Ідентифікатор процесу-заявника;

- Пріоритет процесу;

- Ідентифікатор і необхідний обсяг ресурсу тощо

У ході організації використання ресурсів формуються таблиці, в яких зазначаються списки розподілених і

вільних ресурсів, зв'язку між ресурсами і процесами.

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

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

Системна тупикова ситуація, або ситуація "зависання" системи - це ситуація, коли один або більше процесів

опиняються в стані безвиході.

В операційних системах тупики виникають в більшості випадків як результат конкуренції процесів за облада-

ня монопольно використовуваними ресурсами (рис. 3.1).

Сформульовані наступні чотири необхідних умови наявності тупика:

1) процеси вимагають надання їм монопольного права керування ресурсом, які їм виділяються (умова

взаимоисключения);

2) процеси утримують за собою ресурси, вже виділені їм, очікуючи в той же час виділення додаткових ре-

сурсов (умова очікування ресурсів);

3) ресурси не можна відібрати у процесів, що утримують їх, ці ресурси не будуть використані для завершення роботи (умова неперераспределяемості);

4) існує кільцева зв'язок процесів, в якій кожен процес утримує за собою один або більше ресурсів,

потрібних наступного процесу ланцюга (умова кругового очікування).

У проблемі тупиків виділяють наступні чотири основних напрямки: запобігання тупиків, обхід тупиків, виявлення тупиків, відновлення після тупиків.

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

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

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