Планування в системах реального часу
Справедливе планування
Лотерейне планування
Процесам лунають "лотерейні квитки" на доступ до ресурсів. Планувальник може вибрати будь-який квиток, випадковим чином. Чим більше квитків у процесу, тим більше у нього шансів захопити ресурс.
Процесорний час розподіляється серед користувачів, а не процесів. Це справедливо якщо у одного користувача декілька процесів, а у іншого один.
Системи реального часу діляться на:
· жорсткі (жорсткі терміни для кожного завдання) - управління рухом
· гнучкі (порушення тимчасового графіка не бажані, але допустимі) - управління відео і аудіо
Зовнішні події на які система повинна реагувати, діляться:
· періодичні - потокове відео і аудіо
· неперіодичні (непередбачувані) - сигнал про пожежу
Що б систему реального часу можна було планувати, потрібне щоб виконувалася умова:
m- число періодичних подій
i- номер події
P(i) - період надходження події
T(i) - час, який йде на обробку події
Тобто переобтяжена система реального часу є не планованою
4.4.1 Планування однорідних процесів
Як однорідні процеси можна розглянути відео сервер з декількома відео потоками (декілька користувачів дивляться фільм).
Оскільки всі процеси важливі можна використовувати циклічне планування.
Але оскільки кількість користувачів і розміри кадрів можуть мінятися, для реальних систем він не підходить.
Використовується модель, коли кожен процес бореться за процесор з своїм завданням і графіком його виконання.
Планувальник повинен знати:
· частота, з якою повинен працювати кожен процес
· об'єм робіт, який йому належить виконати
· найближчий термін виконання чергової порції завдання
Розглянемо приклад з трьох процесів.
Процес А запускається кожні 30мс, обробка кадру 10мс
Процес В частота 25 кадрів, тобто кожні 40мс, обробка кадру 15мс
Процес С частота 20 кадрів, тобто кожні 50мс, обробка кадру 5мс
Три періодичні процеси
Перевіряємо, чи можна планувати ці процеси.
10/30+15/40+5/50=0.808<1
Умова виконується, планувати можна.
Плануватимемо ці процеси статичним (пріоритет наперед призначається кожному процесу) і динамічнимметодами.
4.4.3 Статичний алгоритм планування RMS (Rate Monotonic Scheduling)
Процеси повинні задовольняти умовам:
· Процес повинен бути завершений за час його періоду
· Один процес не повинен залежати від іншого
· Кожному процесу потрібен однаковий процесорний час на кожному інтервалі
· У неперіодичних процесів немає жорстких термінів
· Переривання процесу відбувається миттєво
Пріоритет в цьому алгоритмі пропорційний частоті.
· Процесу А він рівний 33 (частота кадрів)
· Процесу В він рівний 25
· Процесу С він рівний 20
Процеси виконуються по пріоритету.
4.4.4 Динамічний алгоритм планування EDF (Earliest Deadline First)
Найбільший пріоритет виставляється процесу у якого залишився найменший час виконання.
При великих завантаженнях системи EDFмає переваги.
Розглянемо приклад, коли процесу А потрібний для обробки кадру 15мс.
Перевіряємо, чи можна планувати ці процеси.
15/30+15/40+5/50=0.975<1
Завантаження системи 97.5%
Алгоритм планування RMSтерпить невдачу.
Коли користувач запускає програму на виконання, створюється новий процес який забезпечує її виконання. Процес існує в системі доти, поки він не буде перерваний: або самим собою добровільно, або ядром, або за вимогою користувача. Процес сам є абстракцією, що надає ядро для керування програмою під час її виконання. Процес може до деякої міри контролюватися через системні виклики, що впливають, наприклад, на пріоритет виконання процесу.
Через абстракцію процесу ядро дає програмі ілюзію, що вона сама безпосередньо виконується апаратурою. Користувальницька програма не зобов'язана тепер піклуватися про взаємодію з іншими програмами, виконуваними системою, якщо тільки їй явно не буде потрібно зв'язок між ними яким-небудь способом. Кожен процес має свій власний віртуальний адресний простір і роздроблений у часі так, що кілька процесів можуть розділяти між собою апаратні ресурси. Існування інших процесів у системі прозоро для користувальницької програми. Це спрощує розробку нових програм і допомагає підтримувати переносимість програм на інші комп'ютерні системи.
Поділ часу між процесами, забезпечуваний ядром протягом усього періоду активності системи, незалежного від того, на якому рівні - користувача чи ядра, виконується в рамках контексту деякого процесу. При використанні традиційної політики поділу часу , виконання процесу на рівні користувача може бути роздроблене в будь-який момент, для того, щоб забезпечити використання ресурсів ЦП більш-менш рівномірно між усіма процесами. Процеси, що виконуються на рівні ядра виключаються з дроблення за часом. Переключення до іншого процесу при виконанні на рівні ядра відбувається тільки якщо поточний процес ядра явно дозволяє цьому відбутися.
Одним з виключень із правила, що вся активність системи відбувається в рамках процесів, є виконання оброблювачів переривань. Переривання генеруються пристроями введення/виводу, коли в них виникає інформація про статус, що повинна бути передана операційній системі. Інформація про статус може включати, наприклад, код закінчення операції введення/виводу. Переривання виконуються асинхронно стосовно процесів, у тім змісті, що вони можуть виникнути без попередження в будь-який момент часу. Коли вони виникають, ядро дозволяє їм перервати виконання поточного процесу. Система потім виконує оброблювач переривань до його завершення, чи доти, поки він не буде перерваний перериванням більш високого пріоритету. Процеси рівня ядра мають привілей блокування переривань, якщо це необхідно. Це робиться тільки для захисту цілісності структур даних, поділюваних між рівнем процесу і кодом оброблювача переривань.
Інше виключення з цього правила виникає у випадку сервісних процедур обслуговуючих потоки введення/виводу (streams - не плутати з потоками керування - threads у процесі). Механізм потоків уведення/виводу складає основу для реалізації мережних протоколів, і ці сервісні процедури виконуються поза контекстом якого-небудь процесу, майже як оброблювачі переривань, з розумінь підвищення продуктивності й ефективності системи.
Адресний простір процесу
Ядро забезпечує кожен процес своїм власним віртуальним адресним простором. Як правило, процес не може безпосередньо одержати доступ до чужого адресного простору; це забезпечує високий ступінь від втручання іншого процесу який виконується в системі. Деякі операційні системи надають можливість розділяти деяку область пам'яті між різними процесами Майже всі операційні системи використовують підкачування сторінок для керування резервуванням фізичної пам'яті.
3. Взаємодія процесів. Користувальницький рівень.
Спільно виконувані процеси можуть бути або незалежними (independed processes), або взаємодіючими (cooperating processes). Взаємодія процесів часто розуміється в змісті взаємного обміну даними через загальний буфер даних.
Взаємодія процесів зручно розглядати в схемі виробник - споживач (produces - consumer). Наприклад, програма виводу на печатку робить послідовність символів, що споживаються драйвером принтера чи компілятор робить асемблерний текст, що потім споживається асемблером.
Для того, щоб процес - виробник і процес - споживач могли заповнювати спільно необхідний буфер, заповнюваний процесом - виробником і споживаним процесом - споживачем.
Буфер має фіксовані розміри, і отже процеси можуть знаходитися в стані чекання, коли:
буфер заповнений; очікує процес - виробник
буфер порожній; очікує процес - споживач
Буфер може надаватися і підтримуватися самої ОС, наприклад за допомогою засобів комунікації процесів (IPC - Inter Process Communication), або організувати прикладним програмістом. При цьому обидва процеси використовують загальну ділянку пам'яті
Контрольні запитання:
- Які види переривань існують?
- Назвіть функції механізмі переривань.
- Дайте визначення процесу. Стану процесу. Планування процесу.
- Охарактеризуйте поняття черги процесу.
- Назвіть критерії планування процесу.
- Які стратегії планування процесів вам відомі. Яка стратегія планування найбільш універсальна.
- Через абстракцію процесу, яку ілюзію створює ядро програмі?
- Чи завжди все в системі відбувається в рамках процесів?
- Охарактеризуйте адресний простір процесу.
- Охарактеризуйте взаємодію процесів. Користувальницький рівень.
