Въведение в операционните системи

Здравейте, Хабр! Искам да ви представя серия от статии-преводи на интересна, според мен, литература — OSTEP. В този материал се разглежда дълбоко работата на Unix-подобни операционни системи, а именно — работа с процеси, различни планиратели, памет и други подобни компоненти, които съставят съвременната ОС. Оригиналът на всички материали можете да видите тук тук. Моля, имайте предвид, че преводът е направен непрофесионално (достатъчно свободно), но се надявам, че общият смисъл е запазен.

Лабораторните работи по този предмет можете да намерите тук:

Други части:

И можете да посещавате канала ми в Телеграм =)

Планиране: Многостепенна обратна опашка

В тази лекция ще говорим за проблемите при разработването на един от най-известните подходи към
планирането, познат като Многостепенна обратна опашка (MLFQ). За първи път планиращият MLFQ е описан през 1962 година от Fernando J. Corbató в система, наречена
Совместима система за споделяне на време (CTSS). Тези работи (включително по-късните работи върху
Multics) по-късно бяха предложени за наградата Turing Award. Планиращият бе
впоследствие ус усъвършенстван и придоби форма, която можем да срещнем в
някои съвременни системи.

Алгоритъмът MLFQ се опитва да реши 2 основни взаимосвързани проблема.
На първо място, той се опитва да оптимизира времето за оборот, което, както разгледахме в предишната лекция, се оптимизира чрез стартиране в началото на опашката на най-кратките задачи. Въпреки това, ОС не знае колко дълго ще работи определен процес, а това
е необходимо знание за работа на алгоритмите SJF, STCF.
На второ място , MLFQ се опитвада направи системата отзивчива на потребителите (например на тези, които седят и
гледат в екрана в очакване на завършването на задачата) и по този начин да минимизира времето
за реакция. За съжаление, алгоритми подобни на RR намаляват времето за реакция, но много
лошо влияят на метриката на времето за оборот. Оттук и нашият проблем: Как да проектираме
планиращ, който ще отговаря на нашите изисквания и в същото време да не знае нищо за
планирач, който да отговаря на нашите изисквания и в същото време да не знае нищо за
характер на процеса, по принцип? Как планировщик може да изследва характеристиките на задачите,
които стартира, и по този начин да взема по-добри решения за планиране?

Същността на проблема: Как да планирате поставянето на задачи без идеално знание?
Как да разработим планировчик, който едновременно минимизира времето за отговор
за интерактивни задачи и едновременно с това минимизира времето за обработка без предварително
знание за времето за изпълнение на задачата?

Забележка: учим се от предходни събития

Опашката MLFQ е чудесен пример за система, която се учи от
изминали събития, за да предскаже бъдещето. Подобни подходи често
се срещат в ОС (и в много други области на информатиката, включително клоновете
на предсказания в оборудването и алгоритмите за кеширане). Подобни подходи
работят, когато задачите имат поведенчески фази и така са предсказуеми.
Въпреки това, с тази техника трябва да се внимава, защото предсказанията много лесно
може да се окажат неверни и да доведат системата до вземане на по-лоши решения, отколкото
биха били без знания изобщо.

MLFQ: Основни правила

Нека да разгледаме основните правила на алгоритъма MLFQ. И въпреки че съществуват няколко реализации на този алгоритъм, основните подходи са сходни.
В реализацията, която ще разгледаме, MLFQ ще има няколко
отделни опашки, всяка от които ще има различен приоритет. По всяко време,
задача, готова за изпълнение, се намира в една опашка. MLFQ използва приоритети,
за да реши, коя задача да стартира за изпълнение, т.е. задачата с по-висок
приоритет (задача от опашка с по-висок приоритет) ще бъде стартирана първа.
Несъмнено, в конкретна опашка може да има повече от една задача, така
че те ще имат един и същи приоритет. В този случай ще се използва механизма
RR за планиране на старта между тези задачи.
Така стигаме до две основни правила за MLFQ:
Правило 1: Ако приоритет(А) > Приоритет(Б), ще бъде стартирана задача А (Б няма да бъде)
Правило 2: Ако приоритет(А) = Приоритет(Б), А и Б се стартират с използване на RR

Основавайки се на посоченото по-горе, ключовите елементи за планиране на MLFQ
са приоритети. Вместо да задаваме фиксиран приоритет на всяка

Основавайки се на гореизложеното, ключовите елементи на планирането на MLFQ
са приоритетите. Вместо да задаваме фиксиран приоритет на всяка
в задачата MLFQ променява приоритета в зависимост от наблюдаваното поведение.
Например, ако задача постоянно изчаква вход от клавиатурата,
MLFQ ще поддържа приоритета на процеса на високо ниво, тъй като така
трябва да работи интерактивен процес. Ако обаче задачата постоянно и
интензивно използва CPU за дълъг период, MLFQ ще понижи
нейния приоритет. По този начин MLFQ изучава поведението на процесите в момента на тяхната работа
и използва поведението.
Нека начертаем пример как могат да изглеждат опашките в определен момент
от време и тогава ще се получи нещо подобно:

В тази схема 2 процеса A и B се намират в опашката с най-висок приоритет. Процесът
C е някъде по средата, а процес D е в края на опашката. Според горепосочените
описания на алгоритъма MLFQ, планировчикът ще изпълнява задачи само с най-висок
приоритет според RR, а задачите C и D ще останат незаети.
Естествено, статичен снимък не дава пълната картина на това как работи MLFQ.
Важно е да разберем как точно се променя картината с течение на времето.

Опит 1: Как да променим приоритета

В този момент е необходимо да решим как MLFQ ще променя нивото на приоритет
на задачата (и по този начин позицията на задачата в опашката) в хода на нейния жизнен цикъл. За
това е необходимо да имаме предвид работния поток: известно количество
интерактивни задачи с кратко време за работа (и по този начин често освобождаване
на CPU) и няколко дълги задачи, които използват CPU през всичкото си работно време, при това
времето за отговор за такива задачи не е важно. И така, можем да направим първия опит
да реализираме алгоритма MLFQ с следните правила:

Правило 3: Когато задача постъпи в системата, тя бива поставена в опашката с най-висок
приоритет.
Правило 4а: Ако задачата използва целия назначен й времеви прозорец, то нейният
приоритет се понижава.
Правило 4б: Ако задачата освобождава CPU преди изтичането на времевия си прозорец, тя
остава с предишния си приоритет.

Пример 1: Една дългосрочна задача

Както се вижда в този пример, задачата при постъпването си се поставя с най-висок
приоритет. След времеви прозорец от 10мс, процесът се понижава в приоритета от
планировчика. След следващия времеви прозорец задачата, най-накрая, се понижава до
най-нисък приоритет в системата, където и остава.

Пример 2: Получихме кратка задача

Сега ще разгледаме пример за това как MLFQ ще се опита да се доближи до SJF. В този
пример има две задачи: A, която е дългосрочна задача, постоянно
използваща CPU, и B, която е кратка интерактивна задача. Нека предположим,
че A вече е работила известно време, когато е постъпила задача B.

На този график са показани резултатите от сценария. Задача A, както всяка задача,
използваща CPU, се оказва в най-долната част. Задача B ще пристигне в момент T=100 и ще бъде
поставена в опашка с най-висок приоритет. Поради краткото време на изпълнение,
тя ще завърши, преди да достигне последната опашка.

От този пример можем да разберем основната цел на алгоритъма: тъй като алгоритъмът не
знае дали задачата е дълга или кратка, първо предполага, че задачата
е кратка и й дава най-висок приоритет. Ако наистина е кратка задача, тя
ще бъде изпълнена бързо, иначе, ако е дълга задача, тя ще се движи бавно
в приоритета надолу и скоро ще докаже, че наистина е дълга задача, която не
изисква отговор.

Пример 3: А какво за вход-изход?

Сега да погледнем пример с вход-изход. Както беше посочено в правило 4b,
ако процесът освобождава процесора, без напълно да е използвал времето си на CPU,
той остава на същото ниво на приоритета. Намерението на това правило е доста простичко
— ако интерактивната задача извършва много операции вход-изход, например, очаквайки
натискания на клавиши или мишки от потребителя, такава задача ще освобождава процесора
по-рано от предвиденото време. Ние не бихме искали да понижаваме приоритета на такава задача,
така че тя ще остане на същото ниво.

Този пример показва как алгоритмът ще работи с такива процеси — интерактивната задача B, която се нуждае от CPU само за 1мс преди изпълнението
на процеса вход-изход и дългата задача A, която използва целия си време на CPU.
MLFQ държи процес B с най-висок приоритет, тъй като той постоянно
освобождава CPU. Ако B е интерактивна задача, алгоритъмът е успял
да стартира интерактивните задачи бързо.

Проблеми с текущия алгоритъм MLFQ

В предишните примери създадохме основен вариант на MLFQ. И изглежда, че той
въпреки това си върши работата добре и справедливо, разпределяйки процесорното време между
дългите задачи и позволявайки на кратките задачи или задачите с интензивен
вход-изход да се изпълняват бързо. За съжаление, такъв подход има няколко
сериозни проблема.
На първо място, проблемът с глада: ако в системата има множество интерактивни
задачи, те ще изяждат всичкото процесорно време и по този начин нито една дълга
задача няма да има възможност да се изпълни (те гладуват).

, MLFQ се опитва, умни потребители биха могли да напишат своите програми така, че
да мамят планировщика. Мамят в това да правят нещо, за да накарат
планировщика да предоставя на процеса повече процесорно време. Алгоритъмът, който
е описан по-горе, е напълно уязвим на подобни атаки: преди почти
да изтече времето за работа, е необходимо да се извърши операция по вход-изход (към някой, не е важно какъв файл)
и по този начин да се освободи CPU. Такова поведение ще позволи на задачата да остане в същата
опашка и отново да получи по-голям процент от процесорното време. Ако го направим
правилно (например, да изпълняваме 99% от времето на прозореца преди освобождаването на CPU),
такава задача просто може да монополизира процесора.

Накрая, програмата може да променя своето поведение с времето. Тези задачи,
които са използвали CPU, могат да станат интерактивни. В нашия пример подобни
задачи няма да получат адекватно внимание от планировщика, тъй като биха получили други
(първоначални) интерактивни задачи.

Въпрос към залата: какви атаки на планировщика е възможно да се извършват в съвременния свят?

Опит 2: Повишаване на приоритета

Нека опитаме да променим правилата и да видим дали можем да избегнем проблемите с
гладуването. Какво можем да направим, за да гарантираме, че свързаните с
CPU задачи ще получат времето си (дори и ако не за дълго).
Като простичко решение на проблема можем да предложим периодично
да повишаваме приоритета на всичките такива задачи в системата. Има много начини
да се постигне това, нека пробваме да реализираме нещо просто за пример: да преведем
веднага всички задачи в най-висок приоритет, от тук новото правило:

Rule5: След известно време S да прехвърли всички задачи в системата в най-висок приоритет.

Нашето ново правило решава два проблема наведнъж. Първо, процесите
гарантирано не остават гладни: задачите в най-висок приоритет ще делят
процесорното време според алгоритъма RR, и така всички процеси ще получат
процесорно време. На второ място, ако някой процес, който преди е използвал
само процесора, стане интерактивен, той ще остане в опашката с най-висок
приоритет след като веднъж получи повишение на приоритета до най-висок.
Нека разгледаме пример. В този сценарий ще имаме един процес, който използва

CPU и два интерактивни, кратки процеса. Вляво на изображението се демонстрира поведението без повишаване на приоритета, и по такъв начин дългата задача започва да гладува след пристигането на две интерактивни задачи в системата. На изображението вдясно, на всеки 50мс се извършва повишаване на приоритета, и така всички процеси гарантирано получават процесорно време и периодично ще бъдат стартирани. 50мс в случая е взето за пример, реално това число е малко по-голямо.
Очевидно е, че добавянето на време за периодично повишаване S води до
логичния въпрос: каква стойност трябва да бъде поставена? Един от уважаваните
системни инженери John Ousterhout наричаше подобни стойности в системите voo-doo
константи, тъй като те по един или друг начин изискваха черна магия за коректно
определяне. И, за съжаление, S има такъв аромат. Ако зададете стойността твърде
голяма — дългите задачи започват да гладуват. А ако зададете твърде ниска стойност,
интерактивните задачи няма да получат достатъчно процесорно време.

Опит 3: Най-добро отчитане

Сега имаме още един проблем, който трябва да решим: как да не
позволим да измамят нашия планировчик? Виновни за тази възможност са
правилата 4a, 4b, които позволяват на задачата да запази приоритета си, освобождавайки процесора
преди изтичането на зададеното време. Как да се справим с това?
Решението в този случай може да бъде по-доброто отчитане на времето на CPU на всеки
нивото на MLFQ. Вместо да забравя времето, което програмата е използвала.
Когато процесът изразходва определеното му време, трябва да се вземе под внимание и да се запази. След като
процесът е изразходвал отделеното му време, трябва да се понижи до следващото
ниво на приоритета. Сега е незначително как процесът ще използва времето си — дали
постоянно ще изчислява на процесора, или ще прави множество извиквания. По този начин,
правило 4 следва да бъде пренаписано по следния начин:

Rule4: След като задачата е изразходвала определеното време в текущата опашка (независимо от това колко пъти е освободила CPU), приоритетът на такава задача се понижава (тя се движи надолу в опашката).

Нека да разгледаме пример:
»

На изображението е показано какво се случва, ако се опитате да измамите планировчика, както
в случая с предишните правила 4a, 4b, ще получите резултатът отляво. С новото
правило — резултатът е вдясно. Преди активирането на защитата, всеки процес можеше да извика I/O до завършване и
по този начин да доминира в CPU-то, след активирането на защитата, независимо от поведението на
I/O, той все пак ще бъде понижен в опашката и по този начин няма да може нечестно
да завладява ресурсите на CPU.

Подобряване на MLFQ и други проблеми

С горепосочените подобрения възникват нови проблеми: един от основните
въпроси — как да параметризиране подобен планировчик? Т.е. Колко трябва да има
опашки? Какъв трябва да бъде размерът на работния прозорец на програмата в рамките на опашката? Как
често следва да се повишава приоритета на програмата, за да се избегне гладуване и
да се вземе под внимание промяната в поведението на програмата? На тези въпроси няма прост
отговор, и само експерименти с натоварвания и последваща конфигурация
на планировчика може да доведат до задоволителен баланс.

Например, повечето реализации на MLFQ позволяват назначаване на различни
временни интервали на различни опашки. Високоприоритетните опашки обикновено
получават кратки интервали. Тези опашки съдържат интерактивни задачи,
между които превключването е доста чувствително и трябва да отнема 10 или по-малко
мс. В противовес на тях, низкопривилегированите опашки се състоят от дълги задачи, които използват
CPU. И в този случай дългите времеви интервали са много подходящи (100мс).

В този пример има 2 задачи, които работиха в високоприоритетната опашка 20
ms, разбити на прозорци по 10мс. 40мс в средната опашка (прозорец от 20мс) и в нископриоритетната
опашка временното прозорче стана 40мс, където задачите завършиха своята работа.

Реализация на MLFQ в ОС Solaris — клас планиращи, които разделят по време.
Планиращият предоставя набор от таблици, които определят точно как трябва
да се променя приоритетът на процеса с течение на живота му, какъв трябва да бъде размерът
на отпусканото прозорче и как често трябва да се повишават приоритетите на задачата. Администраторът
на системата може да взаимодействва с тази таблица и да накара планиращия да се държи
по различен начин. По подразбиране в тази таблица има 60 опашки с постепенно увеличаване
размера на прозорчето от 20мс (висок приоритет) до няколко стотин мс (нисък приоритет), а
така също и с увеличаване на всички задачи веднъж в секунда.

Други MLFQ планиращи не използват таблица или някакви конкретни
правила, описани в тази лекция, а напротив, изчисляват приоритетите, използвайки
математически формули. Така например, планиращият в FreeBSD използва формула за
изчисляване на текущия приоритет на задачата, основавайки се на това колко процесът
е използвал CPU. В допълнение, използването на CPU с времето загнива и по този
начин повишаването на приоритета става малко иначе, отколкото е описано по-горе. Това са
така наречените decay алгоритми. От версия 7.1 в FreeBSD се използва планиращият ULE.

Накрая, много планиращи имат и други особености. Например, някои
планиращи резервират най-високите нива за работа на операционната система и по този
начин, нито един потребителски процес не може да получи най-високия приоритет в
системата. Някои системи позволяват даване на съвети, за да помогне
на планиращия правилно да установява приоритетите. Така например, с помощта на команда nice
може да се увеличи или намали приоритета на задачата и по този начин да се повишат или
понижат шансът на програмата за процесорно време.

MLFQ: Резюме

Описание на подхода към планирането, наречен MLFQ. Името му
е свързано с принципа на работа — той има няколко опашки и използва обратна връзка
за определяне приоритета на задачата.
Итоговият вид правила ще бъде следният:

Правило1: Ако приоритет(А) > Приоритет(Б), задачата А ще бъде стартирана (Б няма да бъде)
Правило2: Ако приоритет(А) = Приоритет(Б), А и Б се стартират с използване на RR
Правило 3: Когато задачата постъпи в системата, тя се поставя в опашката с най-висок приоритет.
Rule4: След като задачата е изразходвала определеното време в текущата опашка (независимо от това колко пъти е освободила CPU), приоритетът на такава задача се понижава (тя се движи надолу в опашката).
Rule5: След известно време S да прехвърли всички задачи в системата в най-висок приоритет.

MLFQ е интересен по следната причина — вместо да изисква предварително знание за
природата на задачата, алгоритъмът изучава предишното поведение на задачата и определя
приоритети съответно. По този начин той се опитва да угоди на две страни — да постигне производителност за малки задачи (SJF, STCF) и честно да стартира дълги,
изискващи CPU задания. Затова много системи, включително BSD и техните деривати,
Solaris, Windows, Mac използват някаква форма на алгоритъм
MLFQ като основа на планирането.