Архітектура операційної системи UNIX
- 8.1.1 Алгоритм
- 8.1.2 Параметри диспетчеризації
- 8.1.3 Приклади диспетчеризації процесів
- 8.1.4 Управління пріоритетами
- 8.1.5 Планування на основі справедливого розподілу
- 8.1.6 Робота в режимі реального часу
Планувальник процесів в системі UNIX належить до загального класу планувальників, що працюють за принципом "каруселі з багаторівневою зворотним зв'язком". Відповідно до цього принципу ядро надає процесу ресурси ЦП на квант часу, після закінчення якого вивантажує цей процес і повертає його в одну з декількох черг, регульованих пріоритетами. Перш ніж процес завершиться, йому може знадобитися безліч разів пройти через цикл зі зворотним зв'язком. Коли ядро виконує перемикання контексту і відновлює контекст процесу, процес відновлює виконання з точки приостанова.
8.1.1 Алгоритм
Відразу після перемикання контексту ядро запускає алгоритм планування виконання процесів ( малюнок 8.1 ), Вибираючи на виконання процес з найвищим пріоритетом серед процесів, що знаходяться в станах "резервування" і "готовності до виконання, будучи завантаженим в пам'ять". Розглядати процеси, не завантажені в пам'ять, не має сенсу, оскільки не будучи завантажений, процес не може виконуватися. Якщо найвищий пріоритет мають відразу кілька процесів, ядро, використовуючи принцип кільцевого списку (каруселі), вибирає серед них той процес, який знаходиться в стані "готовності до виконання" довше за інших. Якщо жоден з процесів не може бути обраний для виконання, ЦП простоює до моменту отримання наступного переривання, яке відбудеться не пізніше ніж через один таймерний тик; після обробки цього переривання ядро знову запустить алгоритм планування.
алгоритм schedule_process вхідна інформація: відсутня вихідна інформація: відсутній {виконувати поки (для запуску не буде обраний один з процессов) {для (кожного процесу в черзі готових до виконання) вибрати процес з найвищим пріоритетом з загру- дені в пам'ять; якщо (жоден з процесів не може бути обраний для виконання) призупинити машину; / * Машина виходить зі стану простою по прери- / * ванию * /} видалити вибране процес з черги готових до виконан- ня; переключитися на контекст обраного процесу, возобно- вити його виконання; }
Малюнок 8.1. Алгоритм планування виконання процесів
8.1.2 Параметри диспетчеризації
У кожного запису таблиці процесів є поле пріоритету, що використовується планувальником процесів. Пріоритет процесу в режимі завдання залежить від того, як цей процес перед цим використовував ресурси ЦП. Можна виділити два класи пріоритетів процесу ( малюнок 8.2 ): Пріоритети виконання в режимі ядра і пріоритети виконання в режимі завдання. Кожен клас включає в себе ряд значень, з кожним значенням логічно асоційована деяка чергу процесів. Пріоритети виконання в режимі завдання оцінюються для процесів, вивантажених після повернення з режиму ядра в режим завдання, пріоритети виконання в режимі ядра мають сенс тільки в контексті алгоритму sleep. Пріоритети виконання в режимі завдання мають верхнє граничне значення, пріоритети виконання в режимі ядра мають нижнє граничне значення. Серед пріоритетів виконання в режимі ядра далі можна виділити високі і низькі пріоритети: процеси з низьким пріоритетом поновлюються після отримання сигналу, а процеси з високим пріоритетом продовжують залишатися в стані приостанова (див. розділ 7.2.1 ).
Граничне значення між пріоритетами виконання в режимах ядра і завдання на малюнку 8.2 відзначено подвійною лінією, що проходить між пріоритетом очікування завершення нащадка (в режимі ядра) і нульовим пріоритетом виконання в режимі завдання. Пріоритети процесу підкачки, очікування введення-виведення, пов'язаного з диском, очікування буфера і індексу є високими, що не допускають переривання системними пріоритетами, з кожним з яких пов'язана чергу з 1, 3, 2 і 1 процесу, відповідно, в той час як пріоритети очікування введення з терміналу, виведення на термінал і завершення нащадка є низькими, що допускають переривання системними пріоритетами, з кожним з яких пов'язана чергу з 4, 0 і 2 процесів, відповідно. На малюнку представлені також рівні пріоритетів виконання в режимі завдання ( * ).
Ядро обчислює пріоритет процесу в наступних випадках:
- Безпосередньо перед переходом процесу в стан приостанова ядро призначає йому пріоритет виходячи з причини приостанова. Пріоритет не залежить від динамічних характеристик процесу (тривалості введення-виведення або часу рахунки), навпаки, це постійна величина, жорстко встановлюється в момент приостанова і залежить тільки від причини переходу процесу в даний стан. Процеси, які були припинені алгоритмами низького рівня, мають тенденцію породжувати тим більше вузьких місць в системі, чим довше вони знаходяться в цьому стані; тому їм призначається вищий пріоритет у порівнянні з іншими процесами. Наприклад, процес, який був загальмований в очікуванні завершення введення-виведення, пов'язаного з диском, має більш високий пріоритет у порівнянні з процесом, що очікують звільнення буфера, з кількох причин. Перш за все, у першого процесу вже є буфер, тому не виключена можливість, що коли він відновиться, він встигне звільнити і буфер, і інші ресурси. Чим більше ресурсів вільно, тим менше шансів для виникнення взаємного блокування процесів. Системі не доведеться часто перемикати контекст, завдяки чому скоротиться час реакції процесу і збільшиться продуктивність системи. По-друге, буфер, звільнення якого очікує процес, може бути зайнятий процесом, очікують в свою чергу завершення введення-виведення. По завершенні вводу-виводу будуть відновлені обидва процеси, оскільки вони були припинені по одному і тому ж адресою. Якщо першим запустити на виконання процес, який чекає звільнення буфера, він в будь-якому випадку знову призупиниться до тих пір, поки буфер не буде звільнений; отже, його пріоритет повинен бути нижче.
- Після повернення процесу з режиму ядра в режим завдання ядро знову обчислює пріоритет процесу. Процес міг до цього перебувати в стані приостанова, змінивши свій пріоритет на пріоритет виконання в режимі ядра, тому при переході процесу з режиму ядра в режим завдання йому повинен бути повернутий пріоритет виконання в режимі завдання. Крім того, ядро "штрафує" виконується процес на користь інших процесів, відбираючи які він використовував цінні системні ресурси.
- Пріоритети всіх процесів в режимі завдання з інтервалом в 1 секунду (у версії V) перераховує програма обробки переривань за таймером, спонукаючи тим самим ядро виконувати алгоритм планування, щоб не допустити монопольного використання ресурсів ЦП одним процесом.
Малюнок 8.2. Діапазон пріоритетів процесу
Протягом кванта часу таймер може послати процесу кілька переривань; при кожному перериванні програма обробки переривань за таймером збільшує значення, що зберігається в поле таблиці процесів, яке описує тривалість використання ресурсів центрального процесора (ІЦВ). У версії V кожну секунду програма обробки переривань переустановлює значення цього поля, використовуючи функцію напіврозпаду (decay):
decay (ІЦВ) = ІЦВ / 2;
Після цього програма перераховує пріоритет кожного процесу, що знаходиться в стані "зарезервований, але готовий до виконання", за формулою
пріоритет = (ІЦВ / 2) + (базовий рівень пріоритету завдання)
де під "базовим рівнем пріоритету завдання" розуміється граничне значення, розташоване між пріоритетами виконання в режимах ядра і завдання. Високому пріоритету планування відповідає кількісно низьке значення. Аналіз функцій перерахунку тривалості використання ресурсів ЦП і пріоритету процесу показує: чим нижче швидкість напіврозпаду значення ІЦВ, тим повільніше пріоритет процесу досягає значення базового рівня; тому процеси в стані "готовності до виконання" мають тенденцію займати велике число рівнів пріоритетів.
Результатом щосекундного перерахунку пріоритетів є переміщення процесів, що знаходяться в режимі завдання, від однієї черги до іншої, як показано на малюнку 8.3 . Порівняно з малюнком 8.2 один процес перейшов з черги, яка відповідає рівню 1, в чергу, відповідну нульового рівня. У реальній системі всі процеси, що мають пріоритети виконання в режимі завдання, поміняли б своє місце розташування в чергах. При цьому слід вказати на неможливість зміни пріоритету процесу в режимі ядра, а також на неможливість перетину порогової риси процесами, що виконуються в режимі завдання, до тих пір, поки вони не звернуться до операційної системи і не перейдуть в стан приостанова.
Ядро прагне здійснити перерахунок пріоритетів всіх активних процесів щомиті, проте інтервал між моментами перерахунку може злегка варіюватися. Якщо переривання по таймеру надійшло тоді, коли ядро виконувало критичний відрізок програми (іншими словами, в той час, коли пріоритет роботи ЦП був підвищений, але, очевидно, не настільки, щоб перешкодити перериванню даного типу), ядро не перераховуються пріоритети, інакше йому довелося б надовго затриматися на критичному відрізку. Замість цього ядро запам'ятовує те, що йому слід зробити перерахунок пріоритетів, і робить це при першому ж перериванні по таймеру, що надходить після зниження пріоритету роботи ЦП. Періодичний перерахунок пріоритету процесів гарантує проведення стратегії планування, заснованої на використанні кільцевого списку процесів, що виконуються в режимі завдання. При цьому звичайно ж ядро відгукується на інтерактивні запити таких програм, як текстові редактори або програми форматного введення: процеси, їх реалізують, мають високий коефіцієнт простою (відношення часу простою до тривалості використання ЦП) і тому природно було б підвищувати їх пріоритет, коли вони готові для виконання (див. [Thompson 78], стр.1937). В інших механізмах планування квант часу, що виділяється процесу на роботу з ресурсами ЦП, динамічно змінюється в інтервалі між 0 і 1 сек. в залежності від ступеня завантаження системи. При цьому час реакції на запити процесів може скоротитися за рахунок того, що на очікування моменту запуску процесів вже не потрібно відводити по цілій секунді; однак, з іншого боку, ядру доводиться частіше вдаватися до перемикання контекстів.
Малюнок 8.3. Перехід процесу з однієї черги до іншої
8.1.3 Приклади диспетчеризації процесів
на малюнку 8.4 показана динаміка змін пріоритетів процесів A, B і C у версії V при наступних припущеннях: всі ці процеси були створені з початковим пріоритетом 60, який є найвищим пріоритетом виконання в режимі завдання, переривання по таймеру надходять 60 раз в секунду, процес не використовує виклик системних функцій, в системі немає інших процесів, готових до виконання. Ядро обчислює піврозпад показника ІЦВ за формулою:
ІЦВ = decay (ІЦВ) = ІЦВ / 2;
а пріоритет процесу за формулою:
пріоритет = (ІЦВ / 2) + 60;
Якщо припустити, що першим запускається процес A і йому виділяється квант часу, він виконується протягом 1 секунди: за цей час таймер посилає системі 60 переривань і стільки ж раз програма обробки переривань збільшує для процесу A значення поля, що містить показник ІЦВ (з 0 до 60). Після секунди ядро перемикає контекст і, зробивши перерахунок пріоритетів для всіх процесів, вибирає для виконання процес B. Протягом наступного секунди програма обробки переривань за таймером 60 разів підвищує значення поля ІЦВ для процесу B, після чого ядро перераховує параметри диспетчеризації для всіх процесів і знову перемикає контекст. Процедура повторюється багаторазово, супроводжуючись почерговим запуском процесів на виконання.
Малюнок 8.4. Приклад диспетчеризації процесів
Тепер розглянемо процеси з пріоритетами, наведеними на малюнку 8.5 , І припустимо, що в системі є й інші процеси. Ядро може вивантажити процес A, залишивши його в стані "готовності до виконання", після того, як він отримає підряд кілька квантів часу для роботи з ЦП і знизить таким чином свій пріоритет виконання в режимі завдання ( малюнок 8.5а ). Через деякий час після запуску процесу A в стан "готовності до виконання" може перейти процес B, пріоритет якого в той момент виявиться вище пріоритету процесу A ( малюнок 8.5б ). Якщо ядро за цей час не запланувало до виконання будь-якої іншої процес (з тих, що не показані на малюнку), обидва процеси (A і B) за певних обставин можуть на деякий час опинитися на одному рівні пріоритетності, хоча процес B потрапить на цей рівень першим з-за того, що його первісний пріоритет був ближче ( Малюнок 8.5в і 8.5г ). Проте, ядро запустить процес A попереду процесу B, оскільки процес A знаходився в стані "готовності до виконання" більш тривалий час ( малюнок 8.5д ) - це вирішальна умова, якщо вибір виробляється з процесів з однаковими пріоритетами.
В розділі 6.4.3 вже говорилося про те, що ядро запускає процес на виконання після перемикання контексту: перш ніж перейти в стан приостанова або завершити своє виконання процес повинен переключити контекст, крім того він має можливість перемикати контекст в момент переходу з режиму ядра в режим завдання. Ядро вивантажує процес, який збирається перейти в режим завдання, якщо є готовий до виконання процес з більш високим пріоритетом. Така ситуація виникає, якщо ядро вивело зі стану приостанова процес з пріоритетом, що перевищує пріоритет поточного процесу, або якщо в результаті обробки переривання по таймеру змінилися пріоритети всіх готових до виконання процесів. У першому випадку поточний процес не може виконуватися в режимі завдання, оскільки є процес з більш високим пріоритетом виконання в режимі ядра. У другому випадку програма обробки переривань за таймером вирішує, що процес використовував виділений йому квант часу, і оскільки безліч процесів при цьому змінюють свої пріоритети, ядро виконує перемикання контексту.
8.1.4 Управління пріоритетами
Процеси можуть управляти своїми пріоритетами за допомогою системної функції nice:
nice (value);
де value - значення, в процесі перерахунку додаємо до пріоритету процесу:
пріоритет = (ІЦВ / константа) + (базовий пріоритет) + (значення nice)
Системна функція nice збільшує або зменшує значення поля nice в таблиці процесів на величину параметра функції, при цьому тільки суперкористувачеві дозволено вказувати значення, що збільшують пріоритет процесу. Крім того, тільки привілейований користувач може вказувати значення, що лежать нижче певного порогу. Користувачі, що викликають системну функцію nice для того, щоб знизити пріоритет під час виконання інтенсивних обчислювальних робіт, "зручні, приємні" (nice) для інших користувачів системи, звідси назва функції. Процеси успадковують значення nice у свого батька при виконанні системної функції fork. Функція nice діє тільки для процесів, що виконуються; процес не може скинути значення nice в іншого процесу. З практичної точки зору це означає, що якщо адміністратору системи знадобилося знизити пріоритети різних процесів, що вимагають для свого виконання занадто багато часу, у нього не буде іншого способу зробити це швидко, крім як викликати функцію видалення (kill) для всіх них відразу.
Малюнок 8.5. Планування на основі кільцевого списку і пріоритети процесів
8.1.5 Планування на основі справедливого розподілу
Вищеописаний алгоритм планування не бачить ніякої різниці між користувачами різних класів (категорій). Іншими словами, неможливо виділити певної сукупності процесів, наприклад, половину сеансу роботи з ЦП. Проте, така можливість має важливе значення для організації роботи в умовах обчислювального центру, де група користувачів може побажати купити тільки половину машинного часу на гарантованої основі і з гарантованим рівнем реакції. Тут ми розглянемо схему, яка іменується "Плануванням на основі справедливого розподілу" (Fair Share Scheduler) і реалізовану на обчислювальному центрі Indian Hill фірми AT & T Bell Laboratories [Henry 84].
Принцип "планування на основе справедливого розподілу" складається в розподілі сукупності Користувачів на групи, Які є об'єктами обмежень, что накладаються Звичайно планувальніком на обробка процесів з кожної групи. При цьом система віділяє годину ЦП пропорційно числу груп, Незалежності від того, скільки процесів віконується в групі. Нехай, например, в системе є Чотири плановані групи, шкірні з якіх завантажує ЦП на 25% и містіть, відповідно, 1, 2, 3 і 4 процесса, что реалізують рахункові завдання, Які Ніколи з власної Волі НЕ поступляться ЦП. За умови, что в системе более немає ніякіх других процесів, КОЖЕН процес при вікорістанні традіційного алгоритму планування получил бі 10% часу ЦП (оскількі Всього процесів 10 и между ними не робиться ніякіх відмінностей). При використанні алгоритму планування на основі справедливого розподілу процес з першої групи отримає в два рази більше часу ЦП в порівнянні з кожним процесом з другої групи, в 3 рази більше в порівнянні з кожним процесом з третьої групи і в 4 рази більше в порівнянні з кожним процесом з четвертої. У цьому прикладі всім процесам в групі виділяється рівний час, оскільки тривалість циклу, що реалізується кожним процесом, заздалегідь не встановлена.
Реалізація цієї схеми досить проста, що і робить її привабливою. У формулі розрахунку пріоритету процесу з'являється ще один термін - "пріоритет групи справедливого розділу". У просторі процесу також з'являється нове поле, яке описує тривалість ІЦВ на основі справедливого розподілу, загальну для всіх процесів з групи. Програма обробки переривань за таймером збільшує значення цього поля для поточного процесу і щомиті перераховує значення відповідних полів для всіх процесів в системі. Нова компонента формули обчислення пріоритету процесу являє собою нормалізоване значення ІЦВ для кожної групи. Чим більше процесорного часу виділяється процесам групи, тим вище значення цього показника і нижче пріоритет.
Як приклад розглянемо дві групи процесів ( малюнок 8.6 ), В одній з яких один процес (A), в іншій - два (B і C). Припустимо, що ядро першим запустило на виконання процес A, протягом секунди збільшуючи відповідають цьому процесу значення полів, що описують індивідуальне та групове ІЦВ. В результаті перерахунку пріоритетів після закінчення секунди процеси B і C матимуть найвищі пріоритети. Припустимо, що ядро вибирає на виконання процес B. Протягом наступного секунди значення поля ІЦВ для процесу B піднімається до 60, точно таке ж значення приймає поле групового ІЦВ для процесів B і C. Таким чином, після закінчення другої секунди процес C отримає пріоритет, рівний 75 (порівняйте з малюнком 8.4 ), І ядро запустить на виконання процес A з пріоритетом 74. Подальші дії можна простежити на малюнку: ядро по черзі запускає процеси A, B, A, C, A, B і т.д.
8.1.6 Робота в режимі реального часу
Режим реального часу має на увазі можливість забезпечення достатньої швидкості реакції на зовнішні переривання і виконання окремих процесів в темпі, порівнянній з частотою виникнення викликають переривання подій. Прикладом системи, що працює в режимі реального часу, може служити система управління життєзабезпеченням пацієнтів лікарень, миттєво реагує на зміну стану пацієнта. Процеси, подібні текстових редакторах, які не вважаються процесами реального часу: в них швидка реакція на дії користувача є бажаною, але не необхідною (нічого страшного не станеться, якщо користувач, який виконує редагування тексту, почекає відповіді кілька зайвих секунд, хоча у користувача на цей рахунок можуть бути і свої міркування). Вищеописані алгоритми планування виконання процесів призначені спеціально для використання в системах поділу часу і не годяться для умов роботи в режимі реального часу, оскільки не гарантують запуск ядром кожного процесу протягом фіксованого інтервалу часу, що дозволяє говорити про взаємодію обчислювальної системи з процесами в темпі, порівнянній з швидкістю протікання цих процесів. Інший перешкодою в підтримці роботи в режимі реального часу є невигружаемость ядра; ядро не може планувати виконання процесу реального часу в режимі завдання, якщо воно вже виконує інший процес в режимі ядра, без внесення в роботу істотних змін. В даний час системним програмістам доводиться переводити процеси реального часу в режим ядра, щоб забезпечити достатню швидкість реакції. Правильне рішення цієї проблеми - дати таким процесам можливість динамічного протікання (іншими словами, вони не повинні бути вбудовані в ядро) з наданням відповідного механізму, за допомогою якого вони могли б повідомляти ядру про свої потреби, що випливають з особливостей роботи в режимі реального часу. На сьогоднішній день в стандартній системі UNIX така можливість відсутня.
Малюнок 8.6. Приклад планування на основі справедливого розподілу, в якому використовуються дві групи з трьома процесами
(*) Найвищим значенням пріоритету в системі є нульове значення. Таким чином, нульовий пріоритет виконання в режимі завдання вище пріоритету, що має значення, рівне 1, і т.д.
Попередня глава|| Зміст || Наступна глава
Спонсори:
Хостинг:
