НОУ ІНТУІТ, Лекція, Мутекси
Додаток. Інверсія пріоритету та боротьба з нею
Гендальф: Це Балрог! Тікаємо. Гімлі: Але ми все одно не можемо бігти швидше за демона! Леголас: Нам достатньо бігти швидше за тебе!
Анонімна пародія
У системах з пріоритетним плануванням при взаємодії процесів та ниток з різними пріоритетами виникає низка специфічних проблем, що об'єднуються назвою інверсія пріоритету (priority inversion).
Один із наочних прикладів цієї проблеми можна спостерігати, якщо редагувати великий документ у текстовому процесорі Microsoft Word 2000 із включеним автозбереженням. Проблема відтворюється лише якщо вставляти текст на початок або в середину документа, змушуючи Word перерозбивати текст на сторінки. У разі збереження документа Word повинен завершити розбиття на сторінки, а для цього він змушений зупинити редагування, інакше є ризик, що перерозбиття на сторінки ніколи не завершиться. Таким чином, при редагуванні великого документа з увімкненим автозбереженням користувач більшу частину часу взаємодіє з високопріоритетним і дійсно швидко реагує потоком, що відповідає за редагування - але іноді виявляється змушений чекати завершення роботи низькопріоритетного фонового потоку. Це виглядає як раптове "зависання" Word. Якщо в інтерактивних програмах інверсія пріоритету лише дратує, у системах жорсткого реального часу вона може призводити до справді серйозних проблем.
При розрахунку часу реакції на подію, розробник системи реального часу повинен брати до уваги не тільки час виконання коду, що безпосередньо обробляє цю подію, але й часи роботи всіх критичних секцій у всіх нитках, які можуть утримувати мутекси, необхідні обробнику - адже обробник не зможепродовжити виконання, поки не захопить ці мутекси, а довільно знімати їх не можна, тому що вони сигналізують, що ресурс, що ними поділяється, знаходиться в неузгодженому стані.
Якщо високопріоритетна нитка намагається захопити мутекс, зайнятий низьким пріоритетом, то в певному сенсі вийде, що ця нитка буде працювати зі швидкістю низькопріоритетного процесу.
В умовах, коли планувальник не забезпечує справедливого розподілу часу центрального процесора, а в системі нарівні з високопріоритетною ниткою (робота якої нас цікавить) та низькопріоритетною (яка тримає мутекс) існують ще середньопріоритетні нитки, може виявитися, що низькопріоритетна нитка не отримуватиме управління протягом значного часу. На цей час буде заблокована і високопріоритетна нитка.
Особливо серйозна ця проблема, коли високо-і низькопріоритетні нитки відносяться до різних класів планування - а в системах реального часу так воно і є.
Інверсія пріоритету у Mars Pathfinder
При розробці ПЗ для бортового комп'ютера космічного апарату Mars Pathfinder, була прийнята архітектура, яку самі розробники називали "загальною шиною" - глобальна область пам'яті, що розділяється, яку всі процеси в системі використовували для комунікації. Доступ до цієї галузі захищався мутексом.
У системі існувала високопріоритетна нитка, що займалася керуванням шиною, яка періодично запускалася за сигналами таймера і збирала з "шини" деяку важливу для неї інформацію. Ця ж нитка мала скидати сторожовий таймер, підтверджуючи, що система функціонує нормально.
Крім того, в системі існувало ще кілька ниток, які здійснювали доступ до шини, зокрема нитка зборуметеорологічних даних Ця нитка також запускалася за розкладом і копіювала дані буфер " шини " , зрозуміло, захоплюючи у своїй мутекс.
Таким чином, якщо нитка управління "шиною" запускалася під час роботи "метеорологічної" нитки, то вона мала чекати деякий додатковий час. У моменти, коли в системі не було інших активних ниток, це не призводило до проблем.
Однак коли накладалося виконання трьох ниток, інтервал очікування сильно збільшувався, і це призводило до спрацьовування сторожового таймера і скидання бортового комп'ютера - в даному випадку помилковому, тому що система все-таки залишалася працездатною.
При тестуванні на Землі скиди такого роду кілька разів відбувалися, але розробники не змогли відтворити умови їх виникнення (спрацьовування помилки вимагає накладання трьох ниток, кожна з яких сама по собі більшу частину часу заблокована) і відправили на Марс апарат з недіагностованою проблемою. При експлуатації непередбачувані і що відбуваються в середньому раз на кілька днів скидання бортового комп'ютера завдавали багато незручностей центру управління польотом; до того ж фахівці центру змушені були пояснювати те, що відбувається журналістам. На копії системи Землі скидання довгий час не вдавалося відтворити; нарешті, під ранок, коли в лабораторії залишався лише один розробник, скидання все-таки відбулося і з аналізу налагоджувального дампа системи проблему вдалося вирішити.
Основним засобом боротьби з інверсією пріоритету є наслідування пріоритету (priority inheritance). Зазвичай успадкування контролюється прапором у параметрах мутексу або параметрах системного виклику, що захоплює мутекс. Якщо високопріоритетна нитка намагається захопити мутекс із таким прапором, то пріоритет нитки, що утримуєцей мутекс прирівнюється пріоритету нашої нитки. Таким чином, у кожен момент часу реальний пріоритет нитки, що утримує мутекс, дорівнює найвищому з пріоритетів ниток, що очікують цього мутексу.
Більш радикальне рішення називається стелею пріоритету (priority ceiling). Воно полягає в тому, що пріоритет нитки, що утримує мутекс, дорівнює найвищому з пріоритетів ниток, які можуть захопити цей мутекс. Зрозуміло, під час виконання визначити стелю пріоритету неможливо, він повинен встановлюватись програмістом як параметр мутексу.
Легко зрозуміти, що під час роботи в критичних секціях, захищених такими мутексами, завдання - навіть низькопріоритетні - повинні підкорятися всім обмеженням, які можуть накладатися на виконання в режимі реального часу. Якщо ми в якомусь сенсі не довіряємо низькі пріоритетні нитки (зокрема, не можемо оцінити час, протягом якого вона буде утримувати мутекс), нам слід відмовитися від використання пам'яті, що розділяється, для взаємодії з цією ниткою і перейти до будь-яких буферизованих засобів обміну. даними. При цьому достатньо забезпечити гарантований час передачі в буфер; для того, щоб уникнути переповнення буфера, достатньо того, щоб середній темп генерації даних високопріоритетною ниткою був нижчим від середнього можливого темпу їх обробки низькопріоритетним споживачем. Втім, якщо темп такої обробки схильний до великих флуктуацій (наприклад, через наявність у системі інших процесів), може виявитися необхідно передбачити можливість скидання частини даних для боротьби з переповненням буфера - саме так борються з навантаженнями мережні маршрутизатори та комутатори.
І спадкування, і стеля пріоритету застосовні тільки до мутексів та іншихпримітивам синхронізації, котрим можна зазначити, яка саме нитка їх утримує. Точніше, для боротьби з інверсією пріоритету необхідно, щоб пріоритет підвищувався для нитки, яка звільнятиме семафор. Для мутексів це завжди та сама нитка, яка його захоплювала, але для семафорів-лічильників це, взагалі кажучи, не так.
Тому навіть ті системи, які надають успадкування чи стелі пріоритетів для мутексів, не надають аналогічних засобів для семафорів-лічильників. У книзі [QNX 2004] наводяться результати експериментів над системою реального часу QNX, з яких видно, що ця ОС реалізує наслідування пріоритетів на мутексах, але при використанні семафорів-лічильників можна отримати класичний випадок інверсії пріоритету.