Введення в операційні системи
Привіт, Хабре! Хочу представити вашій увазі серію статей-перекладів однієї цікавої на мою думку літератури — OSTEP. У цьому матеріалі розглядається досить глибоко робота unix-подібних операційних систем, а саме робота з процесами, різними планувальниками, пам'яттю та іншими подібними компонентами, які складають сучасну ОС. Оригінал всіх матеріалів ви можете подивитись ось . Прошу врахувати, що переклад виконаний непрофесійно (досить вільно), але сподіваюся, загальний зміст я зберіг.
Лабораторні роботи з даного предмета можна знайти ось тут:
Інші частини:
А ще можете заглядати до мене на канал у =)
Введення в планувальник
Суть проблеми: Як розробити політику планувальника
Як мають розроблятися базові фреймворки політик планувальника? Які мають бути ключові припущення? Які метрики важливі? Які базові техніки використовувалися у ранніх обчислювальних системах?
Припущення робочого навантаження
Перед тим як обговорити можливі політики, спершу зробимо кілька спрощених відступів про процеси, запущені в системі, які всі разом називаються робочим навантаженням. Визначаючи робоче навантаження, як критичну частину побудови політик і чим більше ви знаєте про навантаження, тим якіснішу політику ви зможете написати.
Зробимо наступні припущення про процеси запущені в системі, іноді ще званих роботи (Завданнями). Майже всі ці припущення не реалістичні, але необхідні розвитку думки.
- Кожне завдання запущено однакову кількість часу,
- Всі завдання ставляться одночасно,
- Поставлене завдання працює до свого завершення,
- Всі завдання використовують лише CPU,
- Час роботи кожного завдання відомий.
Метрики Планувальника
Крім деяких припущень про навантаження, необхідно ще деякий інструмент порівняння різних політик планування: метрики планувальника. Метрика це лише деякий захід чогось. Існує кілька метрик, які можна використовувати для порівняння планувальників.
Для прикладу будемо використовувати метрику, яка називається час обороту (Turnaround time). Час обороту завдання визначається як різниця між часом завершення задачі та час надходження завдання до системи.
Tturnaround=Tcompletion−Tarrival
Оскільки ми припустили, що це завдання надійшли одночасно, то Ta=0 і отже Tt=Tc. Це значення природно зміниться, коли ми змінимо перераховані вище припущення.
Інша метрика справедливість (Справедливість, чесність). Продуктивність та чесність часто є протидіючими характеристиками у плануванні. Наприклад, планувальник може оптимізувати продуктивність, але очікування запуску іншими завданнями, таким чином, знижується чесність.
FIRST IN FIRST OUT (FIFO)
Найбільш базовий алгоритм, який ми можемо втілити називається FIFO або first come (in), first served (out). Цей алгоритм має кілька переваг: він дуже простий у реалізації і він підходить під наші припущення, виконуючи роботу досить добре.
Розглянемо найпростіший приклад. Допустимо 3 завдання було поставлено одночасно. Але припустимо, що завдання А прийшло трохи раніше всіх інших, тому в списку виконання стоятиме раніше інших, так само як і Б щодо В. Припустимо, що кожна з них виконуватиметься 10 секунд. Який у цьому випадку буде середній час виконання цих завдань?
Підрахувавши значення - 10 +20 +30 і розділивши на 3, отримаємо середній час виконання програми 20 секунд.
Тепер спробуємо змінити наші припущення. Зокрема припущення 1 і таким чином більше не припускатимемо, що кожне завдання виконується однакову кількість часу. Як покаже себе FIFO цього разу?
Як виявляється, різні часи виконання завдань вкрай негативно позначаються на продуктивності алгоритму FIFO. Припустимо, що завдання А буде виконуватися 100 секунд, тоді як Б і В, як і раніше, будуть по 10 кожна.
Як очевидно з малюнка, середній час для системи вийде (100+110+120)/3=110. Такий ефект називається ефектом конвою, коли деякі короткочасні споживачі будь-якого ресурсу стоятимуть у черзі за важким споживачем. Це схоже на чергу у продуктовому магазині, коли перед вами покупець з повним візком. Найкраще вирішення проблеми — спробувати змінити касу або розслабитися і дихати глибоко.
Спочатку найкоротша робота
Чи можна якось вирішити подібну ситуацію з великоваговими процесами? Звичайно. Інший тип планування називаєтьсяСпочатку найкоротша робота (SJF). Його алгоритм також досить примітивний - як зрозуміло з назви, першими будуть запущені найкоротші завдання одне за одним.
У цьому прикладі результатом запуску тих самих процесів буде поліпшення середнього часу обороту програм і воно буде рівним. 50 замість 110, Що практично вдвічі краще.
Таким чином, для заданого припущення, що всі завдання прибувають одночасно, алгоритм SJF здається найбільш оптимальним алгоритмом. Однак наші припущення все ще не здаються реалістичними. На цей раз змінимо припущення 2 і цього разу уявімо, що завдання можуть перебувати в будь-який час, а не одночасно. До яких проблем це може спричинити?
Уявімо, що завдання А (100с) прибуває найпершою і починає виконуватися. У момент t=10 прибувають завдання Б, кожна з яких займатиме 10 секунд. Отже, середній час виконання це (100+(110-10)+(120-10))3 = 103. Що міг планувальник зробити, щоб поліпшити становище?
Shortest Time-to-Completion First (STCF)
Для того, щоб покращити положення опустимо припущення 3 про те, що програма запущена і працює до завершення. Крім того, нам знадобиться підтримка обладнання і як ви могли здогадатися ми будемо використовувати таймер для переривання працюючої задачі та перемикання контекстів. Таким чином, планувальник може щось зробити в момент надходження завдань Б, В — припинити виконання завдання А і поставити в обробку завдання Б і В і після їх закінчення продовжити виконання процесу А. Такий планувальник називається STCFабо Preemptive Job First.
Результатом роботи цього планувальника буде такий результат: ((120-0) + (20-10) + (30-10)) / 3 = 50. Таким чином, такий планувальник стає ще оптимальнішим для наших завдань.
Метрика Час відгуку (Response Time)
Таким чином, якщо ми знаємо час роботи задач і те, що ці завдання використовують лише CPU, STCF буде найкращим рішенням. І колись у ранні часи ці алгоритми працювали і досить непогано. Однак тепер користувач проводить основний час за терміналом і чекає від неї продуктивної інтерактивної взаємодії. Так народилася нова метрика. час відповіді (Відгуку).
Час відгуку вважається так:
Tresponse=Tfirstrun−Tarrival
Таким чином, для попереднього прикладу час відгуку буде таким: А = 0, Б = 0, = 10 (abg = 3,33).
І виявляється алгоритм STCF не такий вже й хороший у ситуації, коли 3 завдання прибудуть одночасно - йому доведеться дочекатися, поки маленькі завдання повністю не завершаться. Таким чином, алгоритм є хорошим для метрики часу обороту, але поганий для метрики інтерактивності. Уявіть, що сидячи за терміналом у спробі надрукувати символи в редакторі, вам довелося б чекати більше 10 секунд, тому що якесь інше завдання займає процесор. Це не дуже й приємно.
Таким чином ми стикаємося з іншою проблемою — як ми можемо побудувати планувальник, який був чутливий до часу відгуку?
Round Robin
Для вирішення цієї проблеми було розроблено алгоритм Round Robin (RR). Основна ідея досить проста: замість запуску завдань до повного завершення, запускатимемо завдання на деякий проміжок часу (названий квантом часу) і потім перемикатимемося на інше завдання з черги. Алгоритм повторює свою роботу доти, доки всі завдання не завершаться. При цьому час роботи програми має бути кратним часу, через який таймер перерве процес. Наприклад, якщо таймер перериває процес кожні х=10мс, то розмір вікна виконання процесу повинен бути кратний 10 і бути 10,20 або х*10.
Розглянемо приклад: Завдання АБВ прибувають одночасно в систему і кожна хоче працювати 5 секунд. Алгоритм SJF виконуватиме кожну задачу до кінця, перш ніж запустити іншу. У протиставлення алгоритм RR з вікном запуску = 1с пройдеться за завданням в такий спосіб (рис. 4.3):
(SJF Again (Bad for Response Time)
(Round Robin (Good For Response Time)
Середній час відгуку для алгоритму RR (0+1+2)/3=1, тоді як SJF (0+5+10)/3=5.
Логічно припустити, що вікно часу є дуже важливим параметром для RR, чим менше воно, тим вищий час відповіді. Однак, не можна робити його і надто маленьким, оскільки час на перемикання контексту також відіграватиме свою роль у загальній продуктивності. Таким чином, вибір часу вікна виконання виставляється архітектором ОС і залежить від завдань, які плануються в ній. Перемикання контексту не єдина службова операція, яка витрачає час — запущена програма багато чим ще оперує, наприклад, різними кешами і при кожному перемиканні необхідно зберігати та відновлювати це середовище, що також може вимагати багато часу.
RR — чудовий планувальник, якби йшлося лише про метрику часу відгуку. Але як поведеться метрика часу обороту завдання у цьому алгоритмі? Розглянемо приклад вище, коли час роботи А, Б, В = 5с і надходять в один і той же час. Завдання А завершиться о 13, Б 14, В 15с і середній час обороту вийде 14с. Таким чином, RR є найгіршим алгоритмом для метрики обороту.
Загалом, будь-який алгоритм типу RR — чесний, він ділить час роботи на CPU порівну між усіма процесами. І таким чином ці метрики постійно конфліктують між собою.
Тим самим у нас є кілька протипоставлених алгоритмів і при цьому ще залишається кілька припущень — про те, що час завдання відомий і що завдання лише використовує CPU.
Змішування з I/O
В першу чергу приберемо припущення 4, що процес тільки використовує CPU, звичайно це не так і процеси можуть звертатися і до іншого обладнання.
У момент, коли будь-який процес запитує операцію введення-виведення, процес переходить у стан блокованого, очікуючи завершення I/O. Якщо I/O посилається до жорсткого диска, то така операція може займати до декількох мс або довше, і процесор в цей момент простоюватиме. У цей час планувальник може зайняти процесор будь-яким іншим процесом. Наступне рішення, яке доведеться приймати планувальнику - коли процес завершить свій I/O. Коли це станеться, відбудеться переривання і ОС переведе викликаний I/O процес у стан ready.
Розглянемо приклад із кількох завдань. Кожна з них потребує 50мс процесорного часу. Однак перша кожні 10мс звертатиметься до I/O (який теж буде виконуватися по 10мс). А процес Б просто використовує 50мс процесор без I/O.
У цьому прикладі будемо використовувати STCF планувальник. Як поведеться планувальник, якщо запустити на ньому такий процес як А? Він надійде в такий спосіб — спочатку повністю відпрацює процес А, та був процес Б.
Традиційний підхід для вирішення цієї проблеми - інтерпретувати кожну 10-мс підзавдання процесу А як окреме завдання. Таким чином, при старті з алгоритмом STJF вибір між 50-мс завданням і 10-мс завданням очевидний. Потім, коли підзавдання А завершиться, буде запущено процес Б і I/O. Після завершення I/O буде прийнято знову запустити 10-мс процес А замість процесу Б. Таким чином, можливо реалізувати перекриття, коли CPU використовується іншим процесом, поки перший очікує I/O. І як результат система краще утилізується — у момент коли інтерактивні процеси очікують на I/O на процесорі можуть виконуватися й інші процеси.
Оракула більше немає
Тепер спробуємо позбутися припущення, що час роботи завдання відомий. Це загалом найгірше і нереальне припущення з усього списку. Фактично в середньостатистичних звичайних ОС, сама ОС зазвичай дуже мало знає про час виконання завдань, як тоді будувати планувальник без знання того скільки часу завдання буде виконуватися? Можливо, ми могли б використовувати деякі принципи RR для вирішення цієї проблеми?
Підсумок
Ми розглянули базові ідеї планування завдань та розглянули 2 сімейства планувальників. Перший запускає найкоротше завдання спочатку і таким чином підвищує час обороту, другий же розривається між усіма завданнями однаково, підвищуючи час відгуку. Обидва алгоритми погані там, де хороші алгоритми іншої родини. Також ми розглянули як паралельне використання CPU та I/O можуть покращити продуктивність, але так і не вирішили проблему із ясновидінням ОС. І на наступному занятті ми розглянемо планувальник, який дивиться у найближче минуле та намагається передбачити майбутнє. І називається він multi-level feedback queue.
Джерело: habr.com