Теоретична частина.
1) Поняття дисциплін планування. Дисципліна планування - одна з ключових концепцій в багатозадачності і багатопроцесорних систем, як в операційних системах загального призначення, так і вопераційних системах реального часу.
2) Необхідність використання дисциплін планування. Дисципліни планування потрібні для того, щоб ефективно навантажувати систему. Для забезпечення продуктивності системи потрібно дати завдання процесору.
Вимоги до дисципліни планування: - Справедливість, - Макс. пропускна здатність, - Прийнятий час реакції, - Гарантований час реакції, - Передбачуваність, - Врахування зовнішніх пріоритетів, - Мінімальні накладні витрати по реалізації дисципліни комплексного використання ресурсів.
3) Базові дисципліни планування. PSJN (preemptive SJN - SJN з витісненням) - поточний активний процес уривається, якщо його час виконання, щозалишився, більший, ніжуновоприбулогопроцесу. Дисципліна забезпечує ще більшу перевагу коротким процесам перед довгими. Зокрема, в ній усувається те зростання штрафного відношення для найкоротших процесів, яке має місце в SJN.
HPRN (highest penalty ratio next - з найбільшим штрафним відношенням - наступний) - дисципліна без витіснення, що забезпечує якнайкращі показники справедливості. Це досягається за рахунок динамічного перевизначення пріоритетів. Всякий раз при звільненні ЦП для всіх готових процесів обчислюється поточне штрафне відношення: p[i]=(w[i]+t[i]) / t[i] де i - номер процесу; w[i] - час, витрачений процесом на очікування; t[i] - тривалість процесу - передзадана або прогнозована. Для процесу p[i], що тільки що поступив=1. ЦП віддається процесу, що
справедливості, що і SJN, для довгих - ближчі до FCFS. На великому діапазоні середньої тривалості процесів показники, забезпечувані HPRN, представляють середнє між SJN і FCFS і слабо залежать від тривалості. Ще одна гідність HPRN - в тому, що в часі очікування може враховуватися (з деякими ваговими коефіцієнтами) і очікування в інших чергах і, таким чином, виконується більш комплексний облік завантаження системи. Істотним недоліком методу є необхідність перевычисления штрафного відношення для всіх процесів при кожному перемиканні, що погано узгоджується із загальною політикою мінімізації накладних витрат в дисциплінах без витіснення.
SRR (selfish RR - егоїстичний RR) – метод з витісненням, що дає додаткові переваги виконуваним процесам, що дозволяє підвищити пропускну спроможність. Всі процеси розділяються на дві категорії - нові і вибрані. Новими вважаються ті процеси, які не отримали ще жодного кванта часу ЦП, решта всіх процесів - вибрані. Під час вступу до системи кожному процесу дається деякий пріоритет P0, однаковий для всіх процесів, який надалі зростає. В кінці кожного кванта часу перераховуються пріоритети всіх процесів, причому пріоритети нових процесів зростають на величину dA, а вибраних - на величину dB. ЦП віддається процесу з найвищим пріоритетом, а при рівності пріоритетів - тому, який раніше поставлений в чергу. Показники дисципліни істотно залежать від вибраного співвідношення між dA і dB. При dB/dA=1 дисципліна вироджується в звичайну RR, при dB >> dA - в FCFS. Власне дисципліна SRR забезпечується в діапазоні значень 0<dB/dA<1. FB (foreground-background - передний-задний плани) - черга готових процесів розщеплюється на дві підчерги - черга переднього плану і черга заднього плану. Черги обслуговуються по дисципліні RR, але чергу переднього плану має абсолютний пріоритет: поки в ній є процеси, черга заднього плану не обслуговується. Новий процес прямує в чергу переднього плану. Якщо процес використовував встановлене число N квантів в черзі переднього плану, але не завершився, він переводиться в чергу заднього плану.
MLFB (multiply level feed back - багаторівневі черги із зворотним зв'язком). Розщеплювання черги готових процесів на дві і більш за підчергу забезпечує селекцію процесів по тривалості - довші процеси потрапляють в черзі з великими номерами і, відповідно, з меншими пріоритетами. Дисципліна MLFB дуже ефективна для систем, що працюють в інтерактивному режимі. 4)
Планування процесів реального часу в ядрі: • вони завжди матимуть під час планування пріоритет над звичайними процесами; Традиційний алгоритм планування. Розглянемо алгоритм планування звичайних процесів. В основі алгоритму лежить розподіл процесорного часу на епохи (epochs). Упродовж епохи кожен процес має квант часу, довжину якого розраховують у момент початку епохи. Здебільшого різні процеси мають кванти різної довжини. Коли процес вичерпав свій квант, його витісняють і протягом поточної епохи він більше не виконуватиметься. Керування передають іншому процесові. Якщо ж процес був призупинений для виконання введення-виведення або внаслідок синхронізації, його квант не вважають вичерпаним і він може бути вибраний планувальником упродовж поточної епохи. Епоха закінчується, коли всі готові до виконання процеси вичерпали свої кванти. У цьому разі алгоритм планування перераховує кванти для всіх процесів і розпочинає нову епоху. Квант, який задають на початку епохи, називають базовим квантом часу процесу. Його значення можуть динамічно змінюватися системними викликами PC і setpriorityO. Процес-нащадок завжди успадковує базовий квант свого предка. Пріоритет процесу буває двох видів: Динамічний пріоритет будь-якого звичайного процесу завжди нижчий за будь-який пріоритет процесу реального часу.
• nice — задає величину, на якій ґрунтується базовий квант часу процесу (надалі для спрощення вважатимемо nice рівним базовому кванту, насправді це не зовсім так); • counter — містить кількість переривань таймера, що залишилися до вичерпання кванта часу процесу. На початку епохи counter надають значення базового кванта і зменшують його на одиницю в обробнику переривання таймера. Процедура планування 5) Опис дисципліни у відповідності до варіанту номера студента Ni. Недолік дисципліни планування. Дисципліна планування SJN (shortest job next, що означає: наступним буде виконуватись найкоротше завдання) потребує, щоб для кожного завдання була відома оцінка в потребах машинного часу. Необхідність повідомляти ОС характеристики задач, в яких описувались би потреби в ресурсах обчислювальної системи, привела к тому, щоб були розроблені відповідні мовні засоби. Зокрема, мова JCL (job control language, мова управління завданнями) була однією з самих відомих. Користувачі вимушені були указувати припустимий час виконання, и для того, щоб вони не зловживали можливістю встановлювати завідомо менший час виконання (з ціллю отримати результати раніше інших), ввели підрахунок реальних потреб. Диспетчер задач порівнював запрошуваний час і час виконання і в випадку перевищення вказаної оцінки в даному ресурсі встановлював дануе завдання не в початок, а в кінець черги. Ще в деяких ОС в таких випадках використовувалась система штрафів, при яких у випадку
Недолік дисципліни планування - завдання, яким потрібно дуже мало часу для свого завершення, вимушені очікувати процесор нарівні з довготривалими роботами.
|
