Урок № 93

(згідно навчальної робочої програми)

Тема: «Реалізація планування ОС WINDOWS XP та LINUX»

Питання:

1. Планування процесів реального часу в ядрі.

2. Традиційний алгоритм планування.

3. Умови виклику процедури планування.

4. Процедура планування.

5. Розрахунок динамічного пріоритету.

6. Програмний інтерфейс планування.

7. Реалізація планування у Windows ХР. Планування потоків у ядрі.

8. Пріоритети потоків і процесів.

9. Особливості завдання кванта часу.

10. Пошук потоку для виконання.

11. Динамічна зміна пріоритету і кванта часу.

12. Програмний інтерфейс планування.

Планування процесів реального часу в ядрі

Стосовно процесів реального часу, достатньо сказати, що:

• вони завжди матимуть під час планування пріоритет перед звичайними про­цесами;

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

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

Традиційний алгоритм планування

В основі алгоритму лежить розподіл процесорного часу на епохи (epochs). Упродовж епохи кожен процес має квант часу, довжину якого розраховують у момент початку епохи.

Здебільшого різні процеси мають кванти різної довжини. Коли процес вичерпав свій квант, його витісняють і протягом поточної епохи він більше не виконувати­меться. Керування передають іншому процесові. Якщо ж процес був призупине­ний для виконання введення-виведення або внаслідок синхронізації, його квант не вважають вичерпаним і він може бути вибраний планувальником упродовж поточної епохи. Епоха закінчується, коли всі готові до виконання процеси вичер­пали свої кванти. У цьому разі алгоритм планування перераховує кванти для всіх процесів і розпочинає нову епоху.

Квант, який задають на початку епохи, називають базовим квантом часу проце­су. Його значення можуть динамічно змінюватися системними викликами пі се() і setpriority(). Процес-нащадок завжди успадковує базовий квант свого предка.

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

Опишемо найважливіші поля структури даних процесу стосовно планування:

• роliсу — визначає, до якої групи відноситься процес;

• nісе — задає величину, на якій ґрунтується базовий квант часу процесу;

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

Умови виклику процедури планування

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

• За допомогою відкладеного запуску (lazy invocation). Відкладений запуск поля­гає в тому, що у певний момент часу спеціальному полю need_resched структури процесу надають значення 1. Це відбувається в таких випадках: коли поточний процес вичерпав свій квант; коли у стан готовності переходить процес, пріори­тет якого вищий, ніж у поточного; коли процес явно поступається своїм правом виконання через відповідний системний виклик. При цьому негайного перепла­нування не відбувається, але пізніше, коли цей процес повинен знову отримати керування після переривання, він перевіряє, чи не дорівнює поле needreschedодиниці. Якщо рівність виконується, запускають процедуру планування.

Процедура планування

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

Якщо жоден процес не був вибраний, поточний процес продовжує виконува­тися. Коли ж вибір відбувся, контекст перемикають на новий процес.

Розрахунок динамічного пріоритету

Тепер повернемося до обчислення динамічного пріоритету процесу. Для цього використовують функцію goodness(). Розглянемо можливі значення, які вона мо­же повернути.

С=p.counter+ р.nісе;

де р — покажчик на керуючий блок процесу.

Звідси випливає, що більше часу залишилося процесу для виконання і що довший його базовий квант, то вищий його пріоритет. Крім того, це значення до­датково збільшують на одиницю для процесів, які використовують ту саму па­м’ять, що й предки (наприклад, якщо процес відображає потік, створений за допо­могою функції clone()).

Перелічимо недоліки алгоритму.

• Вибір процесу для виконання відбувається внаслідок розрахунку динамічно­го пріоритету для всіх процесів у черзі готових процесів.

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

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

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

Програмний інтерфейс планування

Для зміни базового пріоритету процесу використовують виклик setpriority(): #include<sys/resource.h>

Int setpriority (int which, int who, int priority):

Зокрема, параметр which може набувати значення PRI0_PR0CESS або PRIOJJSER, відповідно показуючи, що параметр who буде інтерпретований як ідентифікатор процесу чи ідентифікатор користувача.

Параметр priority задає новий пріоритет. Пріоритет може варіюватися в ме­жах від -20 до 20, менші значення свідчать про вищий пріоритет. Значенням за замовчуванням є 0. Негативні значення priority можуть задавати лише користу­вачі з правами адміністратора.

Для отримання інформації про поточний базовий пріоритет використовують виклик getpriority():

int getpriority(int which, int who);

Цей виклик повертає значення пріоритету, параметри which і who для нього ма­ють той самий зміст, що й для функції setpriority().

Реалізація планування у Windows ХР.Планування потоків у ядрі

Ядро Windows ХР розв’язує під час планування дві основні задачі:

• облік відносних пріоритетів, присвоєних кожному потокові;

• мінімізацію часу відгуку інтерактивних застосувань.

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

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

Пріоритети потоків і процесів

Для визначення порядку виконання потоків диспетчер ядра використовує систе­му пріоритетів. Кожному потокові присвоюють пріоритет, заданий числом у діа­пазоні від 1 до 31 (що більше число, то вище пріоритет). Пріоритети реального часу — 16-31; їх резервує система для дій, час виконання яких є критичним чин­ником. Динамічні пріоритети — 1-15; вони можуть бути присвоєні потокам за­стосувань користувача.

Ядро системи може надати потоку будь-який динамічний пріоритет. Win32 АРІ не дає можливості зробити це з цілковитою точністю, у ньому використову­ють дворівневу систему, яка зачіпає як процес, так і його потоки: спочатку проце­су присвоюють клас пріоритету, а потім потокам цього процесу — відносний пріоритет, який відраховують від класу пріоритету процесу (називаного ще базо­вим пріоритетом). Під час виконання відносний пріоритет може змінюватися.

Розрізняють такі класи пріоритету процесів: реального часу (real-time, приблиз­но відповідає пріоритету потоку 24); високий (high, 13); нормальний (normal, 8); невикористовуваний(idle, 4).

Відносні пріоритети потоку бувають такі: найвищий (+2 до базового); вище за нормальний (+1 до базового); нормальний (дорівнює базовому); нижче за нор­мальний (-1 від базового); найнижчий (-2 від базового).

Є два додаткових модифікатори відносного пріоритету: критичний за часом (time-critical) і невикористовуваний(idle). Перший модифікатор тимчасово за­дає для потоку пріоритет 15 (найвищий динамічний пріоритет), другий аналогіч­ним чином задає пріоритет 1.

Особливості завдання кванта часу

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

У Windows ХР інтерактивно можна задавати таку довжину кванта:

• короткі кванти змінної довжини. Можлива довжина кванта - 10 або 30 мс, при цьому застосування, з яким починає працювати користувач, автоматично переходить до використання довших квантів;

• довгі кванти фіксованої довжини. Довжина кванта фіксована й дорівнює 120 мс.

Пошук потоку для виконання

Для виконання новий потік вибирається, коли:

• минув квант часу для потоку;

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

• потік перейшов у стан готовності до виконання.

Планувальник підтримує спеціальну структуру даних — список готових пото­ків(dispatcher ready list). У цьому списку зберігається 31 елемент — по одному для кожного рівня пріоритету. З кожним елементом пов’язана черга готових по­токів, всі потоки з однаковим пріоритетом перебувають у черзі, яка відповідає їх­ньому рівню пріоритету.

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

Якщо подивитися на ситуацію з боку потоку, що виконується, то важливо знати, коли він може бути витиснений. Це трапляється коли:

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

• минув квант часу потоку;

• потік із вищим пріоритетом перейшов у стан готовності до виконання;

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

Динамічна зміна пріоритету і кванта часу

Під час виконання потоків динамічний пріоритет і довжина кванта часу можуть бути скориговані ядром системи. Розрізняють два види такої динамічної зміни: підтримка(boosting) і ослаблення(decay).

• Під час завершення операції введення-виведення підвищення пріоритету залежить від типу операції.

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

• Вихід з будь-якого стану очікування для потоків інтерактивних застосувань призводить до підвищення пріоритету на 2, таке саме підвищення відбувається під час переходу в стан готовності потоків, пов’язаних із відображенням інтер­фейсу користувача.

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

Програмний інтерфейс планування

Для зміни класу пріоритету процесу використовують функцію SetPriority- Class(), для визначення поточного класу пріоритету — функцію GetPriorityClassO:

BOOL SetPriorityClass(HANDLE ph, DWORD pclass);

DWORD GetPriorityClass(HANDLE ph);

Параметр ph визначає дескриптор процесу, для якого задають клас пріорите­ту, а параметр pclass— клас пріоритету. Можливі такі значення pclass:

• REALTIME_PRIORITY_CLASS (реального часу);

• HIGH_PRIORITY_CLASS (високий);

• NORMAL_PRIORITY_CLASS (нормальний);

• IDLE_PRIORITY_CLASS (невикористовуваний).

Щоб задати відносний пріоритет потоку, використовують функцію SetThreadPriority(), а щоб задати його значення — GetThreadPriority().

BOOL SetThreadPriorityCHANDLE th, int priority);

intGetThreadPriorityCHANDLEth);

Параметр th є дескриптором потоку, параметр priority (і повернуте GetThread­PriorityO) може набувати одного з таких значень:

• THREAD_PRIORITY_TIME_CRITICAL (критичний за часом);

• THREAD_PRIORITY_HIGHEST (найвищий);

• THREAD_PRIORIТ Y_AB0 V E_N 0RMAL (вищий за нормальний);

• THREAD_PRІОRITY_N0RMAL (нормальний);

• THREAD_PRIORITY_BELOW_NORMAL (нижчий за нормальний);

• THREAD_PRIORITY_LOWEST (найнижчий);

• THREAD_PRIORITY_IDLE (невикористовуваний).

Контрольні питання:

1. Як реалізується ?анування процесів реального часу в ядрі.

2. Які умови виклику процедури планування?

3. Що таке процедура планування?

4. Як проводиться розрахунок динамічного пріоритету?

5. Як реалізовано програмний інтерфейс планування?

6. Реалізація планування у Windows ХР. Планування потоків у ядрі?

7. Що таке пріоритети потоків і процесів?

8. Які обливості завдання кванта часу?

9. Як проходить пошук потоку для виконання?

10. Що таке динамічна зміна пріоритету і кванта часу?

11. Як реалізовано програмний інтерфейс планування.

Література: Шеховцов В.А. Операційні системи. – К.: Видавнича група BHV, 2005. – 576 с.: іл., стор. 99-110.