Увод у оперативне системе

Хеј Хабр! Желео бих да вам скренем пажњу на серију чланака-превода једне по мени занимљиве литературе – ОСТЕП. У овом материјалу се прилично дубоко разматра рад оперативних система сличних униксу, односно рад са процесима, разним планерима, меморијом и другим сличним компонентама које чине савремени ОС. Овде можете видети оригинал свих материјала овде. Напомињемо да је превод урађен нестручно (прилично слободно), али се надам да сам задржао опште значење.

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

Остали делови:

Такође можете погледати мој канал на telegram =)

Планирање: Ред за повратне информације на више нивоа

У овом предавању говорићемо о проблемима развоја једног од најпознатијих приступа
планирање, које се зове Ред за повратне информације на више нивоа (МЛФК). МЛФК планер је први описао Фернандо Ј. Цорбато 1962. године у систему тзв.
Компатибилни систем дељења времена (ЦТСС). Ови радови (укључујући и каснији рад на
Мултицс) су касније номиновани за Турингову награду. Планер је био
накнадно побољшана и стекла изглед који се већ налази у
неки савремени системи.

МЛФК алгоритам покушава да реши 2 фундаментална проблема који се преклапају.
Прво, покушава да оптимизује време обрта, које је, као што смо говорили у претходном предавању, оптимизовано методом стартовања на почетку реда највише
кратки задаци. Међутим, ОС не зна колико дуго ће одређени процес трајати, а ово
неопходна знања за рад СЈФ, СТЦФ алгоритама. Друго, МЛФК покушава
учините да систем одговара корисницима (на пример, за оне који седе и
буљи у екран чекајући да се задатак заврши) и на тај начин минимизирају време
одговор. Нажалост, алгоритми попут РР побољшавају време одговора, али изузетно
имају лош утицај на метрику времена обрта. Отуда наш проблем: Како дизајнирати
планер који ће испунити наше захтеве, а да не зна ништа о томе
природу процеса уопште? Како планер може научити карактеристике задатака,
које покреће и тако доноси боље планске одлуке?

Суштина проблема: Како планирати постављање задатака без савршеног знања?
Како дизајнирати планер који истовремено минимизира време одговора
за интерактивне задатке и истовремено минимизира време обрта без знања
познавање времена извршења задатка?

Напомена: учимо из претходних догађаја

МЛФК ред је одличан пример система који учи
прошлих догађаја за предвиђање будућности. Слични приступи су често
налази у ОС (и многим другим гранама рачунарске науке, укључујући гране
хардверска предвиђања и алгоритми за кеширање). Слична путовања
се покрећу када задаци имају фазе понашања и стога су предвидљиви.
Међутим, са овом техником треба бити опрезан јер су предвиђања веома лака
може се показати нетачним и довести систем до доношења лошијих одлука од
био би уопште без знања.

МЛФК: Основна правила

Погледајмо основна правила МЛФК алгоритма. И мада имплементације овог алгоритма
Има их неколико, основни приступи су слични.
У имплементацији коју ћемо гледати, МЛФК ће имати неколико
одвојени редови, од којих ће сваки имати другачији приоритет. било када,
задатак спреман за извршење је у једном реду. МЛФК користи приоритете,
да одлучи који задатак да покрене на извршење, тј. задатак са вишим
приоритет (задатак из реда са највећим приоритетом) ће бити покренут први
куеуе.
Наравно, може бити више од једног задатка у датом реду, тако да
па ће имати исти приоритет. У овом случају ће се користити механизам
РР да закаже трчање између ових задатака.
Тако долазимо до два основна правила за МЛФК:

Правило 1: Ако приоритет(А) > Приоритет(Б), задатак А ће бити покренут (Б неће)
Правило 2: Ако је приоритет(А) = Приоритет(Б), А&Б се покрећу коришћењем РР

На основу наведеног, кључни елементи за планирање МЛФК-а
су приоритети. Уместо да сваком дате фиксни приоритет
задатак, МЛФК мења свој приоритет у зависности од уоченог понашања.
На пример, ако задатак непрестано баца посао на ЦПУ док чека унос са тастатуре,
МЛФК ће задржати висок приоритет процеса јер је тако
треба да функционише интерактивни процес. Ако је, напротив, задатак стално и
користи ЦПУ у великој мери током дужег периода, МЛФК ће га смањити
приоритет. Дакле, МЛФК ће проучавати понашање процеса док су покренути
и користе понашања.
Хајде да нацртамо пример како би редови могли да изгледају у неком тренутку
време и онда добијете нешто овако:

У овој шеми, 2 процеса А и Б су у реду са највећим приоритетом. Процес
Ц је негде у средини, а процес Д је на самом крају реда. Према наведеном
Према описима МЛФК алгоритма, планер ће извршавати задатке само са највишим
приоритет према РР, а задаци Ц, Д ће бити ван посла.
Наравно, статички снимак неће дати потпуну слику о томе како МЛФК функционише.
Важно је тачно разумети како се слика мења током времена.

Покушај 1: Како променити приоритет

У овом тренутку морате да одлучите како ће МЛФК променити ниво приоритета
задатке (а тиме и позицију задатка у реду) како напредује кроз свој животни циклус. За
ово је неопходно да се има у виду ток посла: одређени износ
интерактивни задаци са кратким временом рада (а самим тим и честим издавањем
ЦПУ) и неколико дуготрајних задатака који користе ЦПУ све своје радно време, док
Време одговора није важно за такве задатке. И на овај начин можете направити свој први покушај
имплементирајте МЛФК алгоритам са следећим правилима:

Правило 3: Када задатак уђе у систем, он се ставља у ред са највишим
приоритет.
Правило 4а: Ако задатак користи цео временски оквир који му је додељен, онда он
приоритет је смањен.
Правило 4б: Ако задатак ослободи ЦПУ пре него што му истекне временски оквир, онда је
остаје са истим приоритетом.

Пример 1: Један дуготрајни задатак

Као што се може видети у овом примеру, задатак за пријем је постављен са највишим
приоритет. Након временског оквира од 10 мс, процес је деградиран у приоритету
планер. Након следећег временског периода, задатак је коначно деградиран на
најнижи приоритет у систему, где остаје.

Пример 2: Испоручио кратак задатак

Сада да видимо пример како ће МЛФК покушати да приступи СЈФ-у. У томе
на пример, два задатка: А, који је дуготрајан задатак стално
заузимају ЦПУ и Б, што је кратак интерактивни задатак. Претпоставимо
да је А већ радио неко време када је стигао задатак Б.

Овај графикон приказује резултате сценарија. Задатак А, као и сваки задатак,
Употреба ЦПУ-а је била на самом дну. Задатак Б ће стићи у време Т=100 и хоће
стављен у ред са највећим приоритетом. Пошто је његово време рада кратко, онда
завршиће се пре него што стигне до последњег реда.

Из овог примера треба схватити главни циљ алгоритма: пошто алгоритам не
зна да ли је задатак дуг или кратак, онда пре свега претпоставља да је задатак
кратко и даје му највиши приоритет. Ако је ово заиста кратак задатак, онда
брзо ће се завршити, у супротном ако је дуг задатак, полако ће се кретати
приоритет доле и ускоро ће доказати да је она заиста дуг задатак који то не чини
захтева одговор.

Пример 3: Шта је са И/О?

Сада погледајмо И/О пример. Као што је наведено у правилу 4б,
ако процес ослобађа процесор без коришћења целог времена процесора,
онда остаје на истом нивоу приоритета. Сврха овог правила је прилично једноставна
- ако интерактивни посао обавља много И/О операција, на пример, чека
од корисничког тастера или притиска миша, такав задатак ће ослободити процесор
пре додељеног прозора. Не бисмо желели да снизимо приоритет таквог задатка,
и тиме ће остати на истом нивоу.

Овај пример показује како ће алгоритам радити са таквим процесима - интерактивни посао Б, којем је ЦПУ потребан само 1мс пре извршења
И/О процес и дуготрајни посао А, који све своје време проводи користећи ЦПУ.
МЛФК држи процес Б на највишем приоритету јер се наставља
ослободите ЦПУ. Ако је Б интерактивни задатак, онда је алгоритам постигнут
Ваш циљ је да брзо покренете интерактивне задатке.

Проблеми са тренутним МЛФК алгоритмом

У претходним примерима направили смо основну верзију МЛФК-а. И чини се да он
ради свој посао добро и поштено, поштено распоређујући ЦПУ време између
дуге задатке и омогућавање кратких или великих задатака
брзо раде на И/О. Нажалост, овај приступ садржи неколико
озбиљни проблеми.
Прво, проблем глади: ако систем има много интерактивних
задатака, онда ће потрошити сво процесорско време, а самим тим ни једно дуго времена
задатак неће моћи да се изврши (они гладују).

Друго, паметни корисници би могли да пишу своје програме тако да
преварити планера. Превара лежи у томе да се нешто присили
Планер даје процесу више ЦПУ времена. Алгоритам који
горе описано је прилично рањиво на сличне нападе: пре него што је временски прозор практично
завршила, потребно је да извршите И/О операцију (за неке, без обзира на фајл)
и тако ослободити ЦПУ. Такво понашање ће вам омогућити да останете у истом
сам ред и опет добити већи проценат ЦПУ времена. Ако урадиш
ово је тачно (на пример, извршите 99% времена прозора пре него што пустите ЦПУ),
такав задатак може једноставно монополизовати процесор.

Коначно, програм може да промени своје понашање током времена. Ти задаци
која је користила ЦПУ може постати интерактивна. У нашем примеру, слично
задаци неће добити третман који заслужују од планера као други
(почетни) интерактивни задаци.

Питање за публику: који напади на планер могу да се изврше у савременом свету?

Покушај 2: Повећање приоритета

Хајде да покушамо да променимо правила и видимо да ли можемо да избегнемо проблеме са
пост. Шта можемо учинити да осигурамо да је то повезано
ЦПУ задаци ће добити своје време (чак и ако не дуго).
Као једноставно решење проблема, можете периодично предложити
подићи приоритет свих таквих задатака у систему. Постоји много начина
Да бисмо то постигли, покушајмо да применимо нешто једноставно као пример: преведите
свим задацима се одмах даје највиши приоритет, отуда и ново правило:

Правило5: Након одређеног периода С, померите све задатке у систему у највиши ред чекања.

Наше ново правило решава два проблема одједном. Прво, процеси
гарантовано да неће гладовати: задаци који су у највећем приоритету биће подељени
ЦПУ време према РР алгоритму и тиме ће сви процеси добити
ЦПУ време. Друго, ако је неки процес који је претходно коришћен
само процесор постаје интерактиван, он ће остати у реду са највишим
приоритет након добијања једнократног повећања приоритета на највиши.
Погледајмо пример. У овом сценарију, размотрите коришћење једног процеса

ЦПУ и два интерактивна, кратка процеса. Са леве стране на слици, слика показује понашање без приоритетног унапређења, па тако дуготрајни задатак почиње да гладује након што два интерактивна задатка стигну у систем. На слици са десне стране, повећање приоритета се врши сваких 50 мс и тако је загарантовано да ће сви процеси добити ЦПУ време и периодично ће се покретати. 50мс у овом случају је узет као пример, у стварности је овај број нешто већи.
Очигледно, додавање периодичног времена повећања С доводи до
логично питање: коју вредност треба поставити? Један од почашћених
системски инжењери Џон Оустерхаут назвао је такве количине у системима као ву-ду
постојани, пошто им је на неки начин потребна црна магија за исправан
излажући. И, нажалост, С има такав мирис. Ако поставите и вредност
велики - дуги задаци ће почети да гладују. А ако поставите прениску вредност,
Интерактивни задаци неће добити одговарајуће ЦПУ време.

Покушај 3: Боље рачуноводство

Сада имамо још један проблем за решавање: како да не
дозволити да наш планер буде преварен? Људи који су криви за ову могућност су
правила 4а, 4б, која дозвољавају послу да задржи приоритет, ослобађајући процесор
пре истека предвиђеног времена. Како се носити са овим?
Решење у овом случају може се сматрати бољим обрачуном ЦПУ времена на сваком
МЛФК ниво. Уместо да заборавите време које је програм користио
процесор за додељени период, треба га узети у обзир и сачувати. После
процес је потрошио додељено време, требало би да буде деградиран на следећи
ниво приоритета. Сада није важно како ће процес искористити своје време - како
стално рачунајући на процесору или као број позива. Тако,
правило 4 треба преписати у следећи облик:

Правило4: Након што задатак потроши своје додељено време у тренутном реду (без обзира колико пута је ослободио ЦПУ), приоритет тог задатка се снижава (помера се низ ред).

Погледајмо пример:
»

Слика показује шта се дешава ако покушате да преварите планер, на пример
да је било са претходним правилима 4а, 4б резултат би се добио са леве стране. Срећна Нова
правило је резултат на десној страни. Пре заштите, било који процес је могао да позове И/О пре завршетка и
тако доминирају ЦПУ-ом, након омогућавања заштите, без обзира на понашање
И/О, он ће се и даље кретати доле у реду и стога неће моћи непоштено
преузети ресурсе процесора.

Побољшање МЛФК-а и других проблема

Са горе наведеним побољшањима долазе нови проблеми: један од главних
Питања - како параметризовати такав планер? Оне. Колико би требало да буде
куеуес? Колика треба да буде величина прозора програма у реду чекања? како
Приоритет програма често треба повећати како би се избегло гладовање и
узети у обзир промену понашања програма? Не постоји једноставан одговор на ова питања
одговор и само експерименте са оптерећењима и накнадном конфигурацијом
планер може довести до неке задовољавајуће равнотеже.

На пример, већина МЛФК имплементација вам омогућава да доделите различите
временски интервали за различите редове. Редови са високим приоритетом обично
прописани су кратки интервали. Ови редови се састоје од интерактивних задатака,
пребацивање између којих је прилично осетљиво и требало би да траје 10 или мање
Госпођа. Насупрот томе, редови ниског приоритета састоје се од дуготрајних задатака који користе
ПРОЦЕСОРИ. И у овом случају, дуги временски интервали се веома добро уклапају (100мс).

У овом примеру постоје 2 задатка који су радили у реду 20 високог приоритета
мс, подељено на прозоре од 10 мс. 40мс у средњем реду (20мс прозор) и у ниском приоритету
Временски прозор реда је постао 40 мс када су задаци завршили свој посао.

Имплементација МЛФК-а за Соларис ОС је класа планера за дељење времена.
Планер ће обезбедити скуп табела које дефинишу тачно онако како треба
приоритет процеса се мења током његовог живота, колика би требало да буде величина
додељени прозор и колико често треба да повећавате приоритете задатака. Администратор
системи могу да ступе у интеракцију са овом табелом и изазову понашање планера
другачије. Ова табела подразумевано има 60 редова са постепеним повећањем
величина прозора од 20 мс (високи приоритет) до неколико стотина мс (ниски приоритет), и
такође са појачањем свих задатака једном у секунди.

Други МЛФК планери не користе табелу или било шта специфично
правила која су описана у овом предавању, напротив, рачунају приоритете користећи
математичке формуле. На пример, ФрееБСД планер користи формулу за
израчунајте тренутни приоритет задатка на основу тога колико дуго траје процес
користи ЦПУ. Поред тога, употреба ЦПУ-а опада током времена, итд
Дакле, повећање приоритета се дешава нешто другачије него што је горе описано. Ово је истина
који се називају алгоритми распадања. Од верзије 7.1, ФрееБСД користи УЛЕ планер.

Коначно, многи планери имају и друге функције. На пример, неки
планери резервишу највише нивое за рад оперативног система и на тај начин
Дакле, ниједан кориснички процес не може добити највећи приоритет у
система. Неки системи вам омогућавају да дате савет за помоћ
планер може исправно поставити приоритете. На пример, коришћењем команде лепо
можете повећати или смањити приоритет задатка и тако повећати или
смањити шансе програма да користи ЦПУ време.

МЛФК: Резиме

Описали смо приступ планирању под називом МЛФК. Његово име
затворен у принципу рада - има неколико редова и користи повратне информације
да одреди приоритет задатка.
Коначни облик правила ће бити следећи:

Правило1: Ако приоритет(А) > Приоритет(Б), задатак А ће бити покренут (Б неће)
Правило2: Ако је приоритет(А) = Приоритет(Б), А&Б се покрећу коришћењем РР
Правило3: Када задатак уђе у систем, ставља се у ред са највећим приоритетом.
Правило4: Након што задатак потроши своје додељено време у тренутном реду (без обзира колико пута је ослободио ЦПУ), приоритет тог задатка се снижава (помера се низ ред).
Правило5: Након одређеног периода С, померите све задатке у систему у највиши ред чекања.

МЛФК је занимљив из следећег разлога – уместо да захтева знање о
природу задатка унапред, алгоритам проучава прошло понашање задатка и скупова
приоритети у складу са тим. Тако покушава да седи на две столице одједном - да постигне продуктивност за мале задатке (СЈФ, СТЦФ) и да поштено трчи дуго,
Послови учитавања ЦПУ-а. Стога, многи системи, укључујући БСД и њихове деривате,
Соларис, Виндовс, Мац користе неки облик алгоритма као планер
МЛФК као основа.

Додатни материјали:

Извор: ввв.хабр.цом

Оперативни системи: три лака комада. Део 5: Планирање: ред за повратне информације на више нивоа (превод)