Алгоритми, що базуються на квантуванні

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

Зміна активного потоку відбувається, якщо:

• потік завершився та залишив систему;

• потік перейшов у стан очікування;

• вичерпано квант процесорного часу, відведений даному потоку.

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

Мал. 4. Граф станів потоку в системі із квантуванням.

Кванти, що виділяються потоками, можуть бути однаковими для всіх потоків або різними. Розглянемо, наприклад, випадок, коли всі потоки надаються кванти однакової довжини q (рис. 5). Якщо в системі є n потоків, той час, який потік проводить в очікуванні наступного кванта, можна грубо оцінити як q(n-l). Чим більше потоків у системі, тим більше часу очікування, тим менше можливості вести одночасну інтерактивну роботу кільком користувачам. Але якщо величина кванта обрана дуже невеликий, то значення твору q(n-l) все одно буде досить мало для того, щоб користувач не відчував дискомфорт від присутності в системі інших користувачів. Типове значення кванта у системах поділу часу становить десятки мілісекунд.

Мал. 5. Ілюстрація розрахунку часу очікування у черзі.

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

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

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

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

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

Мал. 6. Квантування з перевагою потоків, що інтенсивно звертаються

3.4.2 Алгоритми планування, що ґрунтуються на пріоритетах

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

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

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

Багато ОС передбачається можливість зміни пріоритетів протягом життя потоку.

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

Від того, які пріоритети призначені потокам, суттєво залежить ефективність роботи всієї обчислювальної системи. У сучасних ОС, щоб уникнути розбалансування системи, яка може виникнути при неправильному призначенні пріоритетів,можливості користувачів впливати на пріоритети процесів і потоків намагаються обмежувати.При цьому звичайні користувачі, як правило, не мають права підвищувати пріоритети своїм потокам, це дозволено робити (та й то у певних межах) лише адміністраторам. У більшості випадків ОС надає пріоритети потокам за умовчанням. Як приклад розглянемо схему призначення пріоритетів потоків, прийняту операційній системі Windows NT (рис. 7). У системі визначено 32 рівні пріоритетів та два класи потоків — потоки реального часу та потоки зі змінними пріоритетами. Діапазон від 1 до 15 включно відведений для потоків зі змінними пріоритетами, а від 16 до 31 - для більш критичних на час потоків реального часу (пріоритет 0 зарезервований для системних цілей).

Мал. 7. Схема призначення пріоритетів у Windows NT

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