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

Хей Хабр! Бих искал да предложа на вашето внимание поредица от статии-преводи на една интересна според мен литература - OSTEP. Този материал обсъжда доста дълбоко работата на unix-подобни операционни системи, а именно работата с процеси, различни планировчици, памет и други подобни компоненти, които съставляват съвременна операционна система. Можете да видите оригинала на всички материали тук тук. Моля, имайте предвид, че преводът е направен непрофесионално (съвсем свободно), но се надявам да съм запазил общия смисъл.

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

• оригинала
• оригинала
• моята лична адаптация

Други части:

• Част 1: Въведение
• Част 2: Абстракция: Процесът
• Част 3: Въведение в API на процеса
• Част 4: Въведение в Scheduler
• Част 5: Планировчик на MLFQ

Можете също да разгледате канала ми на телеграма =)

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

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

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

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

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

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

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

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

• Правило 1: Ако приоритет (A) > приоритет (B), задача A ще се изпълни (B няма)
• Правило 2: Ако приоритет(A) = Приоритет(B), A&B се стартират с помощта на RR

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


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

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

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

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

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

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


Пример 2: Избрах кратка задача

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


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

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

Пример 3: Какво ще кажете за I/O?

Сега нека да разгледаме I/O пример. Както е посочено в правило 4b,
ако даден процес освободи процесора, без да е използвал напълно своето процесорно време,
след това остава на същото ниво на приоритет. Целта на това правило е доста проста.
- ако интерактивното задание извършва много I/O, например чака
от натискането на клавишите или мишката на потребителя, такава задача ще освободи процесора
преди определения прозорец. Не бихме искали да пропуснем такава приоритетна задача,
и по този начин ще остане на същото ниво.


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

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

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

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

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

Въпрос към публиката: какви атаки срещу планировчика могат да бъдат направени в съвременния свят?

Опит 2: Увеличете приоритета

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

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

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


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

Опит 3: По-добро счетоводство

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

• Правило4: След като дадена задача изчерпи определеното й време в текущата опашка (независимо колко пъти е освободила процесора), приоритетът на такава задача се намалява (тя се премества надолу в опашката).

Да разгледаме един пример:
»

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

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

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

Например, повечето реализации на MLFQ ви позволяват да зададете различни
времеви интервали за различни опашки. Опашките с висок приоритет обикновено са
кратки интервали. Тези опашки се състоят от интерактивни задачи,
превключването между които е доста чувствително и трябва да отнеме 10 или по-малко
Госпожица. Обратно, опашките с нисък приоритет се състоят от дълго изпълнявани задачи, които използват
ПРОЦЕСОР. И в този случай дългите времеви интервали пасват много добре (100ms).


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

Внедряването на MLFQ в операционната система Solaris е клас програмисти за споделяне на време.
Планировчикът ще предостави набор от таблици, които определят точно как трябва
промяна на приоритета на процеса в хода на живота му, какъв трябва да бъде размерът
прозорец, който да бъде разпределен и колко често да се повишават приоритетите на задачите. Администратор
системата може да взаимодейства с тази таблица и да накара планировчика да се държи
различно. По подразбиране тази таблица има 60 опашки с постепенно увеличаване
размер на прозореца от 20 ms (висок приоритет) до няколкостотин ms (най-нисък приоритет) и
също и с усилване на всички задачи веднъж в секунда.

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

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

MLFQ: Резюме

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

• Правило1: Ако приоритет (A) > Приоритет (B), задача A ще се изпълни (B няма)
• Правило2: Ако приоритет(A) = Приоритет(B), A&B се стартират с помощта на RR
• Правило3: Когато дадена задача влезе в системата, тя се поставя в опашката с най-висок приоритет.
• Правило4: След като дадена задача изчерпи определеното й време в текущата опашка (независимо колко пъти е освободила процесора), приоритетът на такава задача се намалява (тя се премества надолу в опашката).
• Правило5: След известен период S прехвърлете всички задачи в системата на най-високата опашка.

MLFQ е интересен поради следната причина - вместо да изисква знания за
естеството на задачата предварително, алгоритъмът научава миналото поведение на задачата и задава
съответно приоритети. Така той се опитва да седне на два стола едновременно - да постигне производителност за малки задачи (SJF, STCF) и честно да изпълнява дълги,
Задачи за натоварване на процесора. Следователно много системи, включително BSD и техните производни,
Solaris, Windows, Mac използват някаква форма на алгоритъм като планировчик
MLFQ като базова линия.

Допълнителни материали:

1. manpages.debian.org/stretch/manpages/sched.7.en.html
2. en.wikipedia.org/wiki/Scheduling_(Компютри)
3. pages.lip6.fr/Julia.Lawall/atc18-bouron.pdf
4. www.usenix.org/legacy/event/bsdcon03/tech/full_papers/roberson/roberson.pdf
5. chebykin.org/freebsd-process-scheduling

Източник: www.habr.com