Повільний процесор і маленький обсяг ОЗП - це ще не означає, що на такій платформі не можна реалізувати багатозадачність, що витісняє. Більше того, головний сенс організації багатозадачного середовища - це ефективне використання процесорного часу, щоб процесор не простоював, поки одні програми чекають якоїсь події, а використовувався іншими програмами. Навіть на таких платформах, як ZX Spectrum (Z80 3.5МГц, 48-128кБ ОЗУ), або 8-бітні мікроконтролери AVR, організація витісняючої багатозадачності має великий сенс.
- Архітектура реалізованої багатозадачної системи
- Потоки (Threads)
- Об'єкти очікування (об'єкти синхронізації)
- IRQL
- Функції менеджера
- KeResetEvent
- KeSetNotifEvent
- KeSetNotifEventFromIsr
- KeSetSynchrEvent
- KeSetSynchrEventFromIsr
- KeWaitForObject
- User ISR
- Налаштування менеджера під певний проект
- Проблемні ситуації
- Початковий код
- Література
Пропоную вашій увазі власну реалізацію багатозадачного диспетчера на асемблері Z80 (ZX Spectrum), який не є частиною будь-якої ОС, а може використовуватися окремо. У ньому немає нічого зайвого - тільки організація виконання потоків і синхронізації між ними. Диспетчер можна використовувати як складову частину програмного проекту, як основу для створення більш серйозного диспетчера для ОС, або як навчальний матеріал.
Архітектура реалізованої багатозадачної системи
Архітектура була навіяна концепціями ядра Windows NT при вивченні мною вихідців ReactOS [2]. З цих концепцій був реалізований мінімум, який дає необхідні риси багатозадачності. Більш повна реалізація можлива, але починаючи з деякого моменту додаткові функції перестають себе виправдовувати через їх витратність на малих ЕВМ.
Потоки (Threads)
Потоки [1] є основними одиницями, якими керує диспетчер. Кожен потік має виконуваний код і власний стек, яким можна користуватися для зберігання адрес повернення з підпрограм та іншої інформації. Менеджер перемикає виконання з одного потоку на інший таким чином, щоб по можливості всі потоки виконали стільки коду, скільки бажають.
Кожен потік може перебувати в одному з трьох станів: очікування (waiting), готовність до виконання (ready) і виконання (running). У стані очікування диспетчер не дає коду потоку виконуватися до настання події, яку очікує потік. Потік, що знаходиться в стані готовності, отримає управління від диспетчера, як тільки це стане можливим. У стані виконання може знаходитися тільки один потік, оскільки в системі є тільки один процесор. Його код виконується процесором до тих пір, поки потік не перейде в стан очікування, або поки не відбудеться витіснення, тобто диспетчер з власної ініціативи не передасть управління іншому потоку.
Кількість потоків у системі фіксовано. Нові потоки не запускаються, а старі - не завершуються. Для мікроконтролерного застосування або в рамках окремої прикладної програми це обмеження несуттєве. Зате спрощується диспетчер і прискорюється його робота.
Кожному потоку відповідає пріоритет. Якщо є кілька потоків у стані готовності - то диспетчер вибирає до виконання той з них, пріоритет якого найвищий. У поточній версії менеджера пріоритет потоку не можна змінювати в процесі роботи. Динамічний пріоритет потоків затратний в реалізації, хоча ця можливість необхідна для вирішення проблеми інверсії пріоритету [1].
Пріоритет всіх потоків у системі різний. Це означає, що диспетчер не організовує псевдопараллельне виконання коду з однаковим пріоритетом, швидко перемикаючи процесор з одного потоку на інший («Round-Robin»). Але насправді це обмеження несуттєве. Псевдопараллельне виконання декількох потоків дає уповільнення кожного з них. Враховуючи обмежені ресурси пам'яті комп'ютера, краще організувати послідовне виконання таких програм. Головна користь від багатозадачності полягає не в можливості псевдопараллельного виконання, а в ефективному поділі процесора між короткочасними завданнями обробки запитів від важливих джерел (наприклад, реакція на натискання користувачем клавіші на клавіатурі) і тривалою роботою програм, час завершення яких некритично (компіляція, архівація). Якщо призначити для потоку, який обробляє натискання клавіш, високий пріоритет, а для потоку архівації - низький, то з точки зору користувача, який редагує текст, швидкість роботи редактора не впаде, але зате у фоновому режимі як бонус заархівується файл.
Об'єкти очікування (об'єкти синхронізації)
На їх основі потік може перейти в стан очікування шляхом виклику відповідної функції диспетчера. Об'єкт очікування може бути сигналізований або несигналізований. Якщо він сигналізований - то функція очікування повертається негайно, і потік продовжує виконання. Якщо ж об'єкт несигналізований - то потік переходить у стан очікування, а виконуватися починають інші потоки, які знаходяться в стані готовності. Як тільки об'єкт стане сигналізований, очікуючий потік повернеться в стан готовності і при першій можливості отримає управління від диспетчера. У операційних системах зазвичай є такі об'єкти очікування, як події (events), семафори (semaphores), мутекси (mutex) та ін. У розглянутому диспетчері реалізовано два типи Events: Notification Event (Manual Reset), и Synchronization Event (Auto-Reset).
IRQL
Стан процесора. Абревіатура в Windows NT розшифровується як «Interrupt Request Level» [3], хоча це не зовсім точно відображає сенс поняття. У описуваному диспетчері існує три рівні IRQL. PASSIVE_LEVEL - це коли в даний момент процесор виконує код одного з потоків. У цей час може відбутися витіснення виконуваного потоку іншим потоком, або процесор може почати обробляти апаратне переривання. DISPATCH_LEVEL - в цьому стані знаходиться процесор під час виконання критичного коду диспетчера. Наприклад, перемикання виконання між потоками - це операція, що складається з багатьох дій. У цей час не можна сказати, що процесор виконує той чи інший потік - він ніби знаходиться «між ними». У зв'язку з цим витіснення коду, виконуваного в режимі DISPATCH_LEVEL, неможливо. Нарешті, третій рівень - DIRQL - відповідає тому, що процесор в даний момент обробляє апаратне переривання.
На відміну від Windows NT, в моєму диспетчері немає такого місця, де б зберігався поточний рівень IRQL. Також немає функцій, що підвищують або знижують його в явному вигляді. Але IRQL як концепція мається на увазі в системі і об'єктивно існує в ній, хоч і неявно.
Користувацький код може виконуватися або в потоках (на PASSIVE_LEVEL), або в користувальницькій підпрограмі обробки переривань (ISR) на DIRQL. Набір доступних функцій диспетчера різний для різних IRQL. Порушення вимог щодо IRQL призводить до невдачі системи.
Користувацький код, що виконується в потоках, не повинен забороняти переривання. Код ISR виконується із забороненими перериваннями, і тому навпаки, їх не можна дозволяти. Що стосується DISPATCH_LEVEL - то в Windows NT в цьому режимі переривання не заборонені, а в моєму диспетчері, для простоти, на DISPATCH_LEVEL переривання заборонені.
Функції менеджера
Подається призначення функцій та опис їх роботи. Подробиці передачі параметрів у ці функції наведено в коментарях до вихідного коду і тут не дублюються, щоб не замикати текст. Імена функцій за можливості взяті ідентично іменам аналогічних функцій ядра Windows NT [2,3].
KeResetEvent
Зняти сигналізацію об'єкта очікування типу Event. Можна викликати на будь-якому рівні IRQL.
KeSetNotifEvent
Сигналізувати об'єкт очікування типу Notification Event (Manual Reset). Всі потоки, які очікували сигналізації цього об'єкта, перейдуть у стан готовності до виконання. Якщо серед них виявиться потік з більш високим пріоритетом, ніж поточний - то виконання поточного потоку буде витіснено на користь того, який має вищий пріоритет.
Об'єкт залишиться сигналізованим перед викликом KeResetEvent.
Функцію можна викликати тільки на IRQL = PASSIVE _ LEVEL.
KeSetNotifEventFromIsr
Те саме, але для виклику на IRQL > = DISPATCH _ LEVEL. При виклику цієї функції з ISR перемикання потоків, якщо відбудеться, то після завершення виконання ISR.
KeSetSynchrEvent
Сигналізувати об'єкт очікування типу Synchronization Event (Auto Reset). Якщо у цього об'єкта були очікувані потоки - то один з них перейде в стан готовності, а об'єкт відразу повернеться в несигналізований стан. Інші потоки продовжать очікування. Якщо очікуваних потоків не було - то об'єкт залишиться сигналізований до тих пір, поки який-небудь потік не викличе на ньому функцію очікування, або KeResetEvent.
Коли сигналізації такого об'єкта очікують кілька потоків, порядок їх виходу з очікування не визначено.
Якщо очікуваний потік, який перейшов у стан готовності, має вищий пріоритет, ніж поточний - то відбудеться витіснення.
Функцію можна викликати тільки на IRQL = PASSIVE _ LEVEL.
KeSetSynchrEventFromIsr
Те саме, але для виклику на IRQL > = DISPATCH _ LEVEL. При виклику цієї функції з ISR перемикання потоків, якщо відбудеться, то після завершення виконання ISR.
KeWaitForObject
Очікування сигналізації об'єкта (Event). Якщо на момент виклику цієї функції об'єкт був сигналізований - то функція негайно повертається. При цьому, у випадку Synchronization Event, відбудеться скидання об'єкта в несигналізований стан. Якщо ж об'єкт не був сигналізований - то поточний потік перейде в режим очікування, і диспетчер стане виконувати код з інших потоків, що знаходяться в стані готовності.
Функцію можна викликати тільки на IRQL = PASSIVE _ LEVEL.
User ISR
Під цим зрозуміло можливість виконання власної підпрограми обробки переривань. У вигляді функції не виділена, але у вихіднику диспетчера передбачено місце для її виклику або вставки. Для взаємодії з потоками ця підпрограма може використовувати функції KeSetNotifEventFromIsr і KeSetSynchrEventFromIsr і, таким чином, «розбудити» якийсь потік і призвести до витіснення іншого потоку.
При виконанні ISR використовується окрема область стека, яка не належить жодному з потоків. При обслуговуванні апаратного переривання в стек потоку розміщується тільки адреса повернення з переривання (2 байти). Інші функції диспетчера також не зловживають стіком. Тому на стеках потоків можна економити, резервуючи для них мінімальну кількість пам'яті.
Інші функції менеджера не призначені для виклику з програм користувача.
Налаштування менеджера під певний проект
Щоб використовувати диспетчер у будь-якому програмному проекті, необхідно його налаштувати. У вихідному тексті слід заповнити структуру даних threads для кожного потоку. Приклад заповнення наведено у вихідному. Головне, що слід заповнювати - це адреси склів потоків. Останні два байти стеку кожного потоку містять адресу його точки входу. Також слід вказати кількість потоків шляхом завдання константи NUM_THREADS. Максимальна кількість потоків у системі - 255.
При старті системи всі потоки повинні перебувати в стані готовності. Останній потік, який має найнижчий пріоритет, не повинен переходити в режим очікування. Цей потік являє собою аналог System Idle Process і не вирішує будь-яку задачу, а призначений для «спалювання» невикористовуваного часу процесора. У ньому рекомендується циклічно виконувати команду HALT.
Також слід налаштувати розміщення в пам'яті самого диспетчера, таблиці векторів переривань, і адресу ISR диспетчера. Користувацька ISR викликається з ISR диспетчера.
Виділення пам'яті під об'єкти очікування, яких в принципі може бути необмежена кількість, залишено на розсуд користувача. Ви можете зберігати ці об'єкти у стеку, у глобальних статичних змінних або з'єднати до проекту менеджер купи (heap) і виділяти пам'ять під зазначені об'єкти в купі.
Проблемні ситуації
Для середовища виконання, що реалізується диспетчером, характерні ситуації, проблемні для систем витісняючої багатозадачності взагалі [1]. До них належать: голодування (Starvation), гонки (Race Conditions) та інверсія пріоритету (Priority Inversion). Перші дві проблеми можуть бути вирішені правильним проектуванням системи, розумним розподілом завдань по потоках, розумного вибору їх пріоритету і використанням примітивів синхронізації (в першу чергу Auto-Reset Synchronization Events). Третя ситуація в моєму диспетчері не вирішується, оскільки відсутні динамічний пріоритет потоків і об'єкти синхронізації типу Mutex. Тому, якщо ця ситуація виникає в конкретному проекті, її слід врахувати і при необхідності додати в диспетчер вищевказані кошти.
Початковий код
Вихідний код менеджера разом з описом структур даних, параметрів функцій та іншої інформації, можна завантажити на GitHub.
Література
1. Вікіпедія. Стаття «Багатозадачність»
2. ReactOS. Початковий код, компонент «ntoskrnl»
3. Windows WDK Documentation. MSDN. Kernel-mode driver architecture