Введення в операційні системи
Привіт, Хабре! Хочу представити вашій увазі серію статей-перекладів однієї цікавої на мою думку літератури — OSTEP. У цьому матеріалі розглядається досить глибоко робота unix-подібних операційних систем, а саме робота з процесами, різними планувальниками, пам'яттю та іншими подібними компонентами, які складають сучасну ОС. Оригінал всіх матеріалів ви можете подивитись ось . Прошу врахувати, що переклад виконаний непрофесійно (досить вільно), але сподіваюся, загальний зміст я зберіг.
Лабораторні роботи з даного предмета можна знайти ось тут:
Інші частини:
А ще можете заглядати до мене на канал у =)
Планування: Multi-Level Feedback Queue
У цій лекції ми поговоримо про проблеми розробки одного з найвідоміших підходів до
планування, який називається Multi-Level Feedback Queue (MLFQ). Вперше MLFQ планувальник був описаний в 1962 Fernando J. Corbató в системі, званої
Compatible Time-Sharing System (CTSS). Ці роботи (у тому числі й пізні роботи над
Multics) згодом були представлені до нагороди Turing Award. Планувальник був
згодом удосконалений і набув вигляду, який можна зустріти вже в
деяких сучасних системах.
Алгоритм MLFQ намагається вирішити 2 фундаментальні проблеми, що перетинаються.
По-першеВін намагається оптимізувати час обороту, який, як ми розглядали в попередній лекції, оптимізується методом запуску на початку черги.
коротких завдань. Однак, ОС не знає, як довго працюватиме той чи інший процес, а це
необхідне знання до роботи алгоритмів SJF, STCF. По-друге, MLFQ намагається
зробити систему чуйною для користувачів (наприклад для таких, що сидять і
витріщаються в екран в очікуванні завершення завдання) і таким чином мінімізувати час
відгуку. На жаль, алгоритми на кшталт RR зменшують час відгуку, але вкрай
погано впливають на метрику часу обігу. Звідси наша проблема: Як проектувати
планувальник, який відповідатиме нашим вимогам і при цьому нічого не знатиме про
характер процесу, загалом? Як планувальник зможе вивчити характеристики завдань,
які він запускає і таким чином краще приймати рішення про планування?
Як планувати постановку завдань без ідеального знання?
Як розробити планувальник, який одночасно мінімізує час відгуку
для інтерактивних завдань та при цьому мінімізує час обороту без явного
знання часу виконання завдання?
Нотатка: навчаємося за попередніми подіями
Черга MLFQ є чудовим прикладом системи, яка навчається на
минулих подіях, щоб передбачити майбутнє. Подібні підходи часто
зустрічаються в ОС (І багатьох інших галузях в інформатиці, включаючи гілки
передбачень в обладнанні та алгоритми кешування). Подібні походи
спрацьовують, коли завдання мають поведінкові фази і таким чином вони передбачувані.
Однак з такою технікою слід бути обережним, тому що передбачення дуже легко
можуть виявитися неправильними і привести систему до прийняття гірших рішень, ніж
були б без знань взагалі.
MLFQ: Basic Rules
Розглянемо основні правила алгоритму MLFQ. І хоча реалізацій цього алгоритму
Існує кілька, базові підходи схожі.
У тій реалізації, яку ми розглядатимемо, у MLFQ буде кілька
окремих черг, кожна з яких матиме різний пріоритет. В будь-який час,
Завдання, готове до виконання знаходиться в одній черзі. MLFQ використовує пріоритети,
щоб вирішити, яке завдання запускати виконання, тобто. завдання з вищим
пріоритетом (завдання із черги з вищим пріоритетом) буде запущено в першу
черга.
Безсумнівно, у конкретній черзі може бути більше одного завдання, таким
у них буде однаковий пріоритет. У цьому випадку використовуватиметься механізм
RR для планування запуску серед цих завдань.
Таким чином ми приходимо до двох базових правил для MLFQ:
- Rule1: Якщо пріоритет(А) > Пріоритет(Б), буде запущено завдання А (Б не буде)
- Rule2: Якщо пріоритет(А) = Пріоритет(Б), АіБ запускаються за допомогою RR
Виходячи з перерахованого вище, ключовими елементами до планування MLFQ
є пріоритети. Замість того, щоб задавати фіксований пріоритет кожному
Завдання, MLFQ змінює його пріоритет в залежності від поведінки, що спостерігається.
Наприклад, якщо завдання постійно кидає роботу на CPU в очікуванні введення з клавіатури,
MLFQ буде підтримувати пріоритет процесу на високому рівні, тому що саме так
має працювати інтерактивний процес. Якщо ж навпаки завдання постійно і
інтенсивно використовує CPU протягом тривалого періоду, MLFQ буде знижувати його
пріоритет. Таким чином, MLFQ вивчатиме поведінку процесів у момент їх роботи
та використовувати поведінки.
Намалюємо приклад того, як могли б виглядати черги в деякий момент.
часу і тоді вийде щось на кшталт цього:
У цій схемі 2 процесу А і В знаходяться у черзі з найвищим пріоритетом. Процес
З десь посередині, а процес D у самому кінці черги. Згідно з наведеними вище
описам алгоритму MLFQ планувальник виконуватиме завдання лише з найвищим
пріоритетом відповідно до RR, а завдання C,D будуть не при справ.
Звичайно статичний снапшот не дасть повну картину того, як працює MLFQ.
Важливо розуміти, як змінюється картина з часом.
Спроба 1: Як змінювати пріоритет
У цей момент необхідно вирішити, як MLFQ змінюватиме рівень пріоритету
Завдання (і таким чином положення задачі в черзі) по ходу її життєвого циклу. Для
цього необхідно пам'ятати робочий процес: деяка кількість
інтерактивних завдань з коротким часом роботи (і таким чином часте звільнення
CPU) та кілька довгих завдань, які використовують CPU весь свій робочий час, при цьому
час відгуку для таких завдань не має значення. І таким чином можна зробити першу спробу
реалізувати алгоритм MLFQ з такими правилами:
- Rule3: Коли завдання надходить у систему, воно міститься в чергу з найвищим
- пріоритетом.
- Rule4a: Якщо завдання використовує повністю відведене тимчасове вікно, то її
- пріоритет знижується.
- Rule4b: Якщо Завдання звільняє CPU до закінчення свого тимчасового вікна, то воно
- залишається з колишнім пріоритетом.
Приклад 1: Поодиноке довгострокове завдання
Як бачимо в цьому прикладі, завдання при вступі ставиться з найвищим
пріоритетом. Після тимчасового вікна в 10мс процес знижується у пріоритеті
планувальником. Після наступного часового вікна завдання нарешті знижується до
нижчого пріоритету у системі, де й залишається.
Приклад 2: Підвезли коротке завдання
Тепер подивимося приклад того, як MLFQ спробує наблизитись до SJF. В цьому
прикладі двох задач: А, яка є довгограючою задачею постійно
займає CPU і B, яка є коротким інтерактивним завданням. Припустимо,
А що працювала деякий час до моменту коли надійшла завдання B.
На цьому графіку видно результати сценарію. Завдання А, як і будь-яке завдання,
використовуюча CPU опинилася в самому низу. Завдання прибуде під час Т=100 і буде
поміщена у чергу з найвищим пріоритетом. Оскільки час її роботи невеликий, то
вона завершиться до того, як досягне останньої черги.
З цього прикладу слід зрозуміти головну мету алгоритму: оскільки алгоритм не
знає довге завдання або коротке, то в першу чергу він припускає, що завдання
коротка та видає їй найвищий пріоритет. Якщо це справді коротке завдання, то
вона виконається швидко, інакше якщо це довге завдання, то вона повільно рухатиметься
у пріоритеті вниз і незабаром доведе, що вона справді довге завдання, яке не
вимагає відгуку.
Приклад 3: Що ж про введення-виведення?
Тепер поглянемо на приклад із введенням-виводом. Як стверджувалося у правилі 4b,
якщо процес звільняє процесор, не використавши повністю його процесорний час,
то він залишається на колишньому рівні пріоритету. Наміри цього правила досить прості
— якщо інтерактивне завдання виконує багато операцій введення-виводу, наприклад, очікуючи
від користувача натискання клавіші або миші, таке завдання буде звільняти процесор
раніше відведеного вікна. Ми не хотіли б опускати таке завдання за пріоритетом,
і таким чином воно залишиться на колишньому рівні.
Цей приклад показує як працюватиме алгоритм з такими процесами — інтерактивне завдання В, яке потребує CPU лише на 1мс перед виконанням
процесу введення-виводу та довге завдання А, яке весь свій час використовує CPU.
MLFQ тримає процес В із найвищим пріоритетом, оскільки він весь час продовжує
звільняти CPU. Якщо B — інтерактивне завдання, то алгоритм у такому разі досяг
своєї мети запускати інтерактивні завдання швидко.
Проблеми з поточним алгоритмом MLFQ
У попередніх прикладах ми збудували базовий варіант MLFQ. І здається, що він
виконує свою роботу добре і чесно, розподіляючи процесорний час чесно між
довгими завданнями і дозволяючи коротким завданням або завданням, що інтенсивно звертаються
до введення-виведення відпрацьовувати швидко. На жаль, такий підхід містить декілька
серйозні проблеми.
По-першепроблема голоду: якщо в системі буде безліч інтерактивних
задач, то вони будуть споживати весь процесорний час і таким чином жоден довгий
завдання не матиме можливості виконуватися (вони голодують).
По-друге, розумні користувачі могли б писати свої програми так, щоб
обдурити планувальник. Обман у тому, щоб зробити щось таке, щоб змусити
планувальник видавати процесу більше процесорного часу. Алгоритм, який
описаний вище цілком вразливий до подібних атак: перед тим, як вікно часу практично
закінчилося необхідно виконати операцію введення-виведення (до якогось, будь-якого файлу)
і таким чином звільнити CPU. Подібна поведінка дозволить залишатися в тій же
самої черги і знову одержати більший відсоток процесорного часу. Якщо зробити
це правильно (наприклад, виповнюватися 99% часу вікна перед звільненням CPU),
таке завдання може монополізувати процесор.
Зрештою, програма може змінювати свою поведінку з часом. Ті завдання,
які використовували CPU можуть стати інтерактивними. У нашому прикладі подібні
завдання не отримають належного звернення від планувальника, тому що отримали б інші
(Початкові) інтерактивні завдання.
Питання до зали: які атаки на планувальник можна було здійснювати у сучасному світі?
Спроба 2: Підвищення пріоритету
Спробуємо змінити правила і подивимося чи вдасться уникнути проблем з
голодуванням. Що б ми могли зробити для того, щоб гарантувати, що пов'язані з
CPU завдання отримають свій час (навіть якщо не довгий).
Як простий вирішення проблеми можна запропонувати періодично
підвищувати пріоритет всіх таких завдань у системі. Існує безліч способів
досягнення цього, спробуємо втілити як приклад щось просте: перекладати
відразу всі завдання у найвищий пріоритет, звідси нове правило:
- Правило5: Після деякого періоду S перевести всі завдання в системі в найвищу чергу.
Наше нове правило вирішує дві проблеми одразу. По-перше, процеси
гарантовано не голодують: завдання, які перебувають у вищій черзі, ділитимуть
процесорний час згідно з алгоритмом RR і таким чином усі процеси отримають
процесорний час. По-друге, якщо якийсь процес, який раніше використав
тільки процесор стає інтерактивним, то він залишатиметься в черзі з вищим
пріоритетом після того, як одного разу отримає підвищення пріоритету до найвищого.
Розглянемо приклад. У цьому сценарії розглянемо один процес, який використовує
CPU та два інтерактивні, короткі процеси. Зліва малюнку демонструє поведінка без підвищення пріоритету, і таким чином довге завдання починає голодувати після прибуття до системи двох інтерактивних завдань. На малюнку праворуч кожні 50мс виконується підвищення пріоритету і таким чином всі процеси гарантовано отримують процесорний час і періодично запускатимуться. 50мс у разі взято для прикладу, реально це число трохи більше.
Очевидно, що додавання часу періодичного підвищення S призводить до
закономірному питанню: яке значення має бути виставлено? Один із заслужених
системних інженерів John Ousterhout називав подібні величини в системах як voo-doo
константа, оскільки вони певною мірою вимагали чорної магії для коректного
виставлення. І, на жаль, S має такий аромат. Якщо виставити значення занадто
більшим – довгі завдання почнуть голодувати. А якщо виставити занадто низьке значення,
інтерактивні завдання отримають належного процесорного часу.
Спроба 3: Найкращий облік
Тепер у нас є ще одна проблема, яку необхідно вирішити: як не
дозволяти обманювати наш планувальник? Виновними у цій можливості виявляються
правила 4a, 4b, які дозволяють завданням зберігати пріоритет, звільняючи процесор
до закінчення виділеного часу. Як же із цим впоратися?
Рішенням у цьому випадку можна вважати найкращий облік часу CPU на кожному
рівні MLFQ. Замість того, щоб забувати час, який програма використовувала
процесор за відведений проміжок слід враховувати і зберігати його. Після того як
процес витратив відведений час слід знижувати його до наступного
рівня пріоритету. Тепер байдуже як процес використовуватиме свій час — як
що постійно обчислює на процесорі або як безліч викликів. Таким чином,
слід переписати правило 4 до такого виду:
- Правило4: Після того як завдання витратила виділений їй час у поточній черзі (незалежно від того скільки разів вона звільняла CPU), пріоритет такого завдання знижується (вона рухається вниз черги).
Подивимося на приклад:
»
На малюнку показано що трапляється, якщо спробувати обдурити планувальник, як
якби було з попередніми правилами 4a, 4b вийде результат зліва. З новим
правилом – результат праворуч. До захисту будь-який процес міг викликати I/O до завершення та
таким чином домінувати на CPU, після включення захисту, незалежно від поведінки
I/O, він все одно опускатиметься в черзі вниз і таким чином не зможе нечесно
оволодіти ресурсами CPU.
Поліпшуємо MLFQ та інші проблеми
З наведеними вище поліпшеннями виникають нові проблеми: одна з головних
питань – як параметризувати подібний планувальник? Тобто. Скільки має бути
черг? Яким має бути розмір вікна роботи програми у межах черги? Як
часто слід підвищувати пріоритет програми для того, щоб уникнути голодування та
взяти до уваги зміну поведінки програми? На ці питання немає простого
відповіді і лише експерименти з навантаженнями та подальше конфігурування
планувальника може призвести до певного задовільного балансу.
Наприклад, більшість реалізацій MLFQ дозволяють призначати різні
тимчасові інтервали різним чергам. Високопріоритетним чергам зазвичай
призначаються короткі інтервали. Ці черги складаються з інтерактивних завдань,
перемикання між якими досить чутливе і повинне займати 10 або менше
мс. На противагу низькопріоритетні черги складаються з довгих завдань, які використовують
CPU. І в цьому випадку довгі часові інтервали підходять дуже добре (100мс).
У цьому прикладі є 2 завдання, які пропрацювали у високопріоритетній черзі.
мс, розбиті на вікна 10мс. 40мс у середній черзі (вікно у 20мс) та в низькопріоритетній
У черзі тимчасове вікно стало 40мс, де завдання завершили свою роботу.
Реалізація MLFQ в ОС Solaris - клас планувальників, що поділяють за часом.
Планувальник надасть набір таблиць, які визначають точно, як повинен
змінюватися пріоритет процесу з плином його життя, яким має бути розмір
вікна і як часто потрібно піднімати пріоритети завдання. Адміністратор
системи може взаємодіяти з цією таблицею і змушувати планувальник поводитися
по іншому. За замовчуванням у цій таблиці 60 черг із поступовим збільшенням
розміру вікна з 20мс (високий пріоритет) до кількох сотень мс (нижчий пріоритет), а
також з бустом всіх завдань раз на секунду.
Інші MLFQ планувальники не використовують таблицю або якісь конкретні
правила, які описані в цій лекції, навпаки, вони обчислюють пріоритети, використовуючи
математичні формули. Так, наприклад планувальник у FreeBSD використовує формулу для
обчислення поточного пріоритету завдання, ґрунтуючись на тому, що процес
використав CPU. Крім того, використання CPU з часом загниває, і таким
Таким чином, підвищення пріоритету відбувається дещо інакше, ніж описано вище. Це так
звані decay алгоритми. З версії 7.1 у FreeBSD використовується планувальник ULE.
Зрештою, багато планувальників мають інші особливості. Наприклад, деякі
планувальники резервують вищі рівні для роботи операційної системи і таким чином
Таким чином, ніякий користувальницький процес не зможе отримати найвищий пріоритет у
системі. Деякі системи дозволяють давати поради для того, щоб допомогти
планувальнику коректно виставляти пріоритети. Так, наприклад, за допомогою команди приємно
можна збільшувати або зменшувати пріоритет завдання і таким чином підвищувати або
знижувати шанси програми на процесорний час.
MLFQ: Підсумки
Ми описали підхід до планування, який називається MLFQ. Його назва
укладено в принципі роботи - він має кілька черг і використовує зворотний зв'язок
визначення пріоритету задачи.
Підсумковий вигляд правил буде наступним:
- Правило1: Якщо пріоритет(А) > Пріоритет(Б), буде запущено завдання А (Б не буде)
- Правило2: Якщо пріоритет(А) = Пріоритет(Б), АіБ запускаються з використанням RR
- Правило3: Коли завдання надходить у систему, воно міститься у чергу з найвищим пріоритетом.
- Правило4: Після того як завдання витратила виділений їй час у поточній черзі (незалежно від того скільки разів вона звільняла CPU), пріоритет такого завдання знижується (вона рухається вниз черги).
- Правило5: Після деякого періоду S перевести всі завдання в системі в найвищу чергу.
MLFQ цікавий з наступної причини — замість вимагати знання про
природі задачі заздалегідь, алгоритм вивчає минулу поведінку задачі та виставляє
пріоритети відповідно. Таким чином він намагається всидіти відразу на двох стільцях - досягти продуктивності для маленьких завдань (SJF, STCF) і чесно запускати довгі,
завантаження CPU завдання. Тому багато систем, включаючи BSD та їх похідні,
Solaris, Windows, Mac використовують як планувальник деяку форму алгоритму
MLFQ як базова основа.
Додаткові матеріали:
- (обчислення)
Джерело: habr.com