Лекція 5.

Міжпроцесорна взаємодія. Повідомлення. Проксі. Сигнали.

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

Розглянемо особливості міжпроцесорної взаємодії (IPC) в ОСРЧ на прикладі QNX. Мікроядро QNX підтримує три найважливіші форми зв'язку між процесами: повідомлення, проксі і сигнали:

· Повідомлення - це основна форма IPC в QNX. Вони забезпечують синхронний зв'язок між взаємодіючими процесами, коли процесу, що посилає повідомлення, потрібно одержати підтвердження того, що воно отримано й, можливо, відповідь.

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

· Сигнали - це традиційна форма IPC. Вони використовуються для асинхронного зв'язку між процесами.

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

Для безпосереднього зв'язка один з одним взаємодіючі процеси використовують наступні функції:

Ці функції можуть бути використані як локально, тобто для зв'язку між процесами на одному комп'ютері, так і в межах мережі, тобто для зв'язку між процесами на різних вузлах.

Рис. 1. Процес A посилає повідомлення процесу B, що одержує його, обробляє й посилає відповідь

На Рис. 1 зображена послідовність подій, що мають місце, коли два процеси використовують функції Send(), Receive()і Reply() для зв'язку один з одним:

1. Процес A посилає повідомлення процесу B, викликавши функцію Send(), що передає відповідний запит ядру. У цей момент часу процес A переходить в SEND-Блокований стан і залишається в цьому стані доти, поки процес B не викличе функцію Receive() для одержання повідомлення.

2. Процес B викликає Receive() і одержує повідомлення від процесу A. При цьому стан процесу A змінюється на REPLY-Блокований. Процес B при виклику функції Receive() у цьому випадку не блокується, тому що до цього моменту його вже очікувало повідомлення від процесу A. Зауважимо, що якби процес B викликав Receive() до того, як йому було послане повідомлення, то він би потрапив у стан RECEIVE-Блокований до одержання повідомлення. У цьому випадку процес-відправник повідомлення негайно після посилки повідомлення потрапив би в стан REPLY-Блокований.

3. Процес B виконує обробку отриманого від процесу A повідомлення і потім викликає функцію Reply(). Відповідне повідомлення передається процесу A, яке переходить у стан готовності до виконання. Виклик Reply() не блокує процес B, який також готовий до виконання. Який із цих процесів буде виконуватися, залежить від їхніх пріоритетів.

Таким чином, передача повідомлень не тільки дозволяє процесам обмінюватися даними, але й надає механізм синхронізації виконання декількох взаємодіючих процесів.

Розглянемо наведений вище рисунок. Після того як процес A викликав функцію Send(), він не може продовжувати виконання доти, поки не одержить відповідь на послане повідомлення. Це гарантує, що виконувана процесом B по запиту процесу A обробка даних буде завершена перш, ніж процес A продовжить виконання. Більше того, після виклику процесом B запиту на одержання даних Receive(), він не може продовжувати виконання доти, поки не одержить наступне повідомлення.

Зміна станів процесів під час передачі повідомлень наведено на Рис. 2.

Рис. 2 Зміна стану процесів у типовому випадку передачі повідомлення.

Розглянутий приклад обміну повідомленнями ілюструє найпоширеніший випадок використання повідомлень - випадок, коли для процесу, що виконує функції сервера, нормальним є стан RECEIVE-Блокований чекаючи яких-небудь запитів клієнта. Це називається send-керований обмін повідомленнями: процес-клієнт ініціює дію, посилаючи повідомлення, відповідь сервера на повідомлення завершує дія. Існує й інша модель обміну повідомленнями, не настільки розповсюджена, як розглянута вище, хоча в деяких ситуаціях вона навіть більше краща: reply-керований обмін повідомленнями, при якому дія ініціюється викликом функції Reply(). У цьому випадку процес-"працівник" посилає серверу повідомлення, що говорить про те, що він готовий до роботи. Сервер не відповідає відразу, а "запам'ятовує", що працівник готовий виконати його завдання. Сервер може ініціювати дія, відповівши працівникові, що очікує завдання. Процес-Працівник виконає завдання й завершить дію, пославши серверу повідомлення, що містить результати своєї роботи.

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

Використовуючи проксі, процес або оброблювач переривання може послати повідомлення іншому процесу, не блокуючись і не очікуючи відповіді.

Проксі може бути використаний у наступних випадках:

· процес бажає сповістити інший процес про настання якої-небудь події, але при цьому не може дозволити собі посилку повідомлення (у цьому випадку він залишався б блокованим доти, поки одержувач не викличе Receive() і Reply());

· процес хоче послати дані іншому процесу, але при цьому йому не потрібно ні відповіді, ні якого-небудь іншого підтвердження того, що адресат (одержувач) одержав повідомлення;

· оброблювач переривання хоче сповістити процес про надходження нових даних.

Для створення проксі використовується функція qnx_proxy_attach(). Будь-який інший процес або оброблювач переривання, якому відомий ідентифікатор проксі, може скористатися функцією Trigger() для того, щоб змусити проксі передати заздалегідь задане повідомлення. Проксі може бути "запущене" неодноразово - щораз при цьому воно посилає повідомлення. Проксі може накопичувати чергу довжиною до 65535 повідомлень.

Рис. 3. Процес-Клієнт запускає проксі 3 рази, у результаті чого сервер одержує 3 "консервованих" повідомлення від проксі.

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

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

· при обробці виключень (ділення на 0, використання невірної адреси й ін.);

· для повідомлення про асинхронну подію (про закінчення операції введення/виведення, спрацьовуванні таймера й ін.);

· для організації взаємодії потоків керування.

Сигнали можуть генеруватися (посилати процесу) як операційною системою, так і процесом.

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

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

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

· процес може ігнорувати сигнал. Якщо процес ігнорує сигнал, то сигнал не робить на процес ніякого впливу;

· процес може передбачити оброблювач сигналу - функцію, що буде викликатися при прийманні сигналу. Якщо процес містить оброблювач для якого-небудь сигналу, говорять, що процес може "піймати" цей сигнал. Будь-який процес, що "ловить" сигнал, фактично одержує особливий вид програмного переривання. Ніякі дані із сигналом не передаються.

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

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

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

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

У випадку синхронної обробки сигналів потік припиняється доти, поки не прийде сигнал. Говорять, що сигнал був прийнятий, якщо він був оброблений синхронним способом.

Сигнали можна розбити на дві групи:

• звичайні сигнали,
• сигнали реального часу.

Розглянемо відмінності сигналів реального часу від звичайних сигналів. Нехай повторний сигнал з тим же ім'ям прийшов раніше, ніж був оброблений попередній. У цьому випадку повторний сигнал реального часу буде поставлений у чергу, а звичайний сигнал загублений.

У випадку звичайного сигналу функція обробки сигналу одержує тільки один аргумент - номер сигналу. У випадку сигналу реального часу є другий аргумент - значення пов'язане із сигналом (ціле число або покажчик). Значення сигналу вказується при породженні сигналу.

Тема. Аналіз продуктивності проекту паралельної системи

Аналіз продуктивності проекту особливо важливий для систем реального часу. Якщо така система не справляється зі своїми завданнями протягом відведеного інтервалу, наслідки можуть бути катастрофічними.

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

Нижче мова йтиме про спосіб аналізу продуктивності проекту ПЗ, заснованому на теорії планування в реальному часі. Цей метод прекрасно працює для систем реального часу, які повинні витримувати тверді тимчасові обмеження [24]. Він дозволяє визначити, чи будуть виконані накладені обмеження.

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

1. Теорія планування в реальному часі

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

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

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

Періодичне завдання характеризується періодом Т (частота запуску) і часом виконання С (час ЦП, необхідний для завершення одного запуску). Коефіцієнт використання ЦП для його дорівнює U = С/Т. Завдання називається планованим (schedulable), якщо вона задовольняє всім тимчасовим обмеженням, тобто його виконання завершується до закінчення періоду. Група завдань називається планованою, коли планованими є кожне вхідне в неї завдання.

Якщо дано безліч незалежних періодичних завдань, то алгоритм монотонних частот призначає кожному завданню фіксований пріоритет, що обчислюється на основі її періоду: чим коротший період, тим вищий пріоритет. Розглянемо завдання t_a, t_b і t_c з періодами 10, 20 і 30 відповідно. Найвищий пріоритет буде призначений завданню t_a із самим коротким періодом, середній пріоритет - завданню t_b а найнижчий – завданню t_c, період якого максимальний.

1.2. Теорема про верхню границю коефіцієнта використання ЦП. Користуючись теорією планування, можна показати, що група незалежних періодичних завдань завжди задовольняє тимчасовим обмеженням за умови, що сума відношень С/Т по всіх завданнях менша деякого граничного значення.

Теорема про верхню границю коефіцієнта використання ЦП (теорема 1) говорить:

Множина із п незалежних періодичних завдань, планованих відповідно за алгоритмом монотонних частот, завжди задовольняє тимчасовим обмеженням, якщо

де С_i і Т_i – час виконання й період завдання t_i відповідно.

Верхня границя U(n) прямує до 69% (ln 2), якщо число завдань прямує до нескінченності. Значення верхньої границі для числа завдань від 1 до 9 наведені в табл. 1. Це оцінка для гіршого випадку, але, як показано в роботі [22], для випадково обраної групи завдань імовірна верхня границя дорівнює 88%. Якщо періоди завдань гармонічні (є кратними один одному), то верхня границя виявляється ще вищою.

Таблиця 1

Теорема про верхню границю коефіцієнта використання

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

Застосуємо теорему про верхню границю коефіцієнта використання до трьох завдань із наступними характеристиками (час усюди виражений у мілісекундах):

Завдання t₁: С₁ ⁼ 20; Т₁ ⁼ 100; U₁= 0,2.

Завдання t₂: C₂ = 30; Т₂ = 150; U₂= 0,2.

Завдання t₃: З₃ = 60; Т₃ = 200; U₃= 0,3.

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

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

Але спробуємо змінити характеристики третього завдання:

Завдання t₃: C₃ = 90; Т₃ = 200; U₃= 0,45.

Тепер повний коефіцієнт використання ЦП дорівнює 0,85, тобто вище, ніж 0,779. Отже, теорема про верхню границю не дає гарантії, що завдання зможуть задовольнити тимчасовим обмеженням. Далі потрібно перевірити, чи не так це для перших двох завдань.

Беручи до уваги стабільність алгоритму монотонних частот, для подібної перевірки припустимо застосувати теорему про верхню границю коефіцієнта використання ЦП. Для перших двох завдань повний коефіцієнт дорівнює 0,4, тобто набагато нижче значення, отриманого з теореми (0,828). Виходить, ці завдання завжди задовольняють тимчасовим обмеженням. З огляду на, що теорему про верхню границю дає песимістичну оцінку, ми можемо перевірити, чи є завдання t₃ планованим, за допомогою більш точної теореми про час завершення.

1.3. Теорема про час завершення. Якщо для деякої множини завдань повний коефіцієнт використання більший, ніж вимагає теорема про верхню границю, то можна використати теорему про час завершення [22], що дає більше достовірний критерій. Вона дозволяє точно визначити, чи є дана множина незалежних періодичних завдань планованими. У цій теоремі передбачається гірший випадок, коли всі періодичні завдання готові до виконання одночасно. Якщо в зазначених умовах виконання завдання завершується до закінчення її першого періоду, то вона завжди буде задовольняти тимчасовим обмеженням [22]. Таким чином, теорема про час завершення перевіряє, чи здатне кожне завдання завершитися до закінчення свого першого періоду.

Теорема про час завершення (теорема 2) говорить:

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

Щоб переконатися у виконанні умов теореми, необхідно перевірити момент завершення першого періоду для даного завдання t_i, а також моменти завершення періодів всіх завдань із більш високим пріоритетом. Відповідно до алгоритму монотонних частот, періоди подібних завдань будуть менші, ніж для завдання t_i. Ці періоди називаються точками планування. Завдання t_i один раз займе ЦП на час С_i протягом свого періоду Т_i. Але більше пріоритетні завдання будуть виконуватися частіше й можуть принаймні один раз витиснути t_i. Тому потрібно врахувати також час ЦП, витрачений на більш пріоритетні завдання.

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

Завдання t₁: С₁ = 20; Т ₁= 100; U₁= 0,2.

Завдання t₂: C₂ = 30; T₂ = 150; U₂= 0,2.

Завдання t₃: C₃ = 90; T₃ = 200; U₃= 0,45.

Їхнє виконання показане на тимчасовій діаграмі на рис. 1. У методі COMET тимчасова діаграма – це діаграма послідовності з тимчасовими мітками. Заштриховані ділянки позначають інтервали часу, протягом яких реалізується дане завдання. Оскільки в наведеному прикладі є всього один процесор, то в кожний момент часу виконується тільки одне завдання.

У найгіршому разі, коли всі три завдання готові до роботи одночасно, першим запускається t₁, тому що в нього самий короткий період і, виходить, найвищий пріоритет. Воно завершується по закінченні 20 мс, після чого протягом 30 мс виконується завдання t₂ а потім t₃ Наприкінці перші точки планування Т₁ = 100, що відповідає терміну завершення t₁; t₁ уже завершена й, отже, задовольняє тимчасовим обмеженням. Завдання t₂ також завершило роботу задовго до терміну, а завдання t₃ витратило 50 мс із необхідних 90.

На початку другого періоду t₁ завдання t₃ витісняється завданням t₃. Проробивши 20 мс, t₂ завершується й уступає процесор завданню t₃. Завдання t₃ виконується до кінця періоду Т₂ (150 мс), що відповідає другій точці планування, обумовленій часом завершення t₂. Оскільки t₂ завершилася до моменту Т₁ (меншого, чим Т₂), то вона вклалася у відведений для неї строк. У цей момент t₃ використовувала 80 мс із необхідних 90.

На початку другого періоду завдання t₂ воно витісняє завдання t₃ Проробивши 30 мс, t₂ завершується й повертає процесор завданню t₃ Завдання t₃виконується ще 10 мс, і в цей момент закінчуються його 90 мс, тобто воно встигло завершитися до закінчення свого терміну. На рис.1 зображена третя точка планування, що розташована наприкінці другого періоду t₁ (2T₁= 200) і одночасно наприкінці перші періоди t₃ (T₃ = 200). З рисунка видно, що кожне завдання завершує виконання до кінця свого першого періоду, так що всі разом вони задовольняють тимчасовим обмеженням.

На рис. 1 показано, що ЦП простоює 10 мс перед початком третього періоду t₁ (цей момент збігається з початком другого періоду t₃). Відзначимо, що протягом інтервалу тривалістю 200 мс процесор працював 190 мс, тобто був задіяний на 95%, хоча повний коефіцієнт використання дорівнює 0,85. Після закінчення часу, рівного найменшому загальному кратному трьох періодів (для даного приклада 600 мс) середній коефіцієнт використання виявляється рівним 0,85.

Рис. 1. Тимчасова діаграма (діаграма послідовності з тимчасовими мітками)

1.4. Жорстке формулювання теореми про час завершення.

Теорему про час завершення можна строго сформулювати так [24] (теорема 3):

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

,

де С_i і Т_i– час виконання й період завдання t_j відповідно, а

R_i = {(k,p): l≤k≤i, p=l,...,[T_i/T_k]}.

У цій формулі t_i – завдання, що перевіряється, a t_k – будь-яке з більш пріоритетних завдань, що впливають на час виконання t_i. Для даної пари завдань t_i і t_k кожне значення р представляє деяку точку планування завдання t_k. У кожній точці планування необхідно розглянути один раз час ЦП С_i, який витрачається на завдання t_i, а також час, який витрачається на більш пріоритетні завдання. Це дозволить визначити, чи встигне t_i завершити виконання до даної точки планування.

Розглянемо застосування теореми 3 до трьох завдань, показаним на рис. 1. Тимчасова діаграма – це графічне подання обчислень, які виконуються у теоремі 3. Знову звернемося до гіршого випадку, коли всі три завдання одночасно готові до виконання. З теореми 3 випливає нерівність для першої точки планування Т₁ = 100:

С₁ + C₂+ С₃ < Т₁;

20 + 30 + 90 > 100;

p=l, k=l.

Щоб ця нерівність виконувалась, всі три завдання повинні завершитися протягом першого періоду Т₁ завдання t₁. Це не так: перш ніж завдання t₃ встигає завершитися, її витісняє завдання t₁ на початку свого другого періоду.

Теорема 3 дає також нерівність для другої точки планування Т₂=150:

2С₁ + С₂ +С₃≤ Т₂;

40 + 30 + 90 > 150;

p=l, k=2.

Щоб отримана нерівність виконувалась, завдання t₁ повинне завершитися двічі, а завдання t₂ і t₃ – по одному разу протягом періоду Т₂ завдання t₂. І це не так, оскільки завдання t₃ витісняється завданням t₂ на початку другого періоду t₂.

Нерівність для третьої точки планування, що перебуває наприкінці другого періоду t₁ (2Т₁ = 200) і одночасно наприкінці першого періоду t₃ (T₃ = 200), виглядає так:

2С₁ + 2С₂ + C₃ ≤ 2Т1 = Т₃;

40 + 60 + 90 < 200;

р = 2, k = 1 або р = 1, k = 3.

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

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

Якщо в додатку є багато аперіодичних завдань, потрібно скористатися алгоритмом спорадичного сервера [25]. З погляду аналізу планування аперіодичне завдання (яке називається спорадичним сервером) еквівалентне періодичному завданню з періодом, рівним мінімального часу між виникненнями подій, які активізують аперіодичне завдання. Тому Т_a зручно вважати періодом еквівалентного періодичного завдання. Кожному аперіодичному завданню виділяється бюджет, рівний С_a одиниць часу процесора, що може бути використаний у будь-який момент протягом періоду Т_a. Таким чином, аперіодичним завданням припустимо призначити різні рівні пріоритету відповідно до еквівалентних періодів і розглядати їх як періодичні.

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

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

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

Щоб запобігти затримці високопріиритетних завдань низькопріиритетними на довгий час, застосовується корекція пріоритетів. Коли низькопріиритетне завдання t₁ виявляється в критичній області, воно може блокувати високопріиритетне завдання, якому потрібен той же ресурс. Якщо це відбувається, то пріоритет t₁ підвищується до максимального із пріоритетів блокуючих завдань. Мета полягає в тому, щоб прискорити виконання низькопріиритетних завдання й скоротити час очікування для високопріиритетних.

Граничний пріоритет Р двійкового семафора S – максимум із пріоритетів всіх завдань, які можуть зайняти даний семафор. Таким чином, низькопріиритетне завдання, що захопило S, здатне підвищити свій пріоритет до Р у залежності від того, які завдання вона блокує.

Ще одна можлива проблема – це тупикова ситуація (deadlock), що виникає, коли двом завданням потрібно захопити по два ресурси. Якщо кожне завдання захопить по одному ресурсі, то жодне не зможе завершитися, оскільки буде чекати, поки інше звільнить ресурс. Протокол граничного пріоритету справляється і з такими труднощами [24].

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