Вовед во оперативни системи
Здраво, Хабр! Би сакал да ви претставам низа написи-преводи на една според мене интересна литература - ОСТЕП. Овој материјал прилично длабоко ја испитува работата на оперативните системи слични на Unix, имено, работата со процеси, различни распоредувачи, меморија и други слични компоненти кои го сочинуваат модерен оперативен систем. Оригиналот на сите материјали можете да го видите овде . Имајте предвид дека преводот е направен непрофесионално (сосема слободно), но се надевам дека го задржав општото значење.
Лабораториска работа на оваа тема може да се најде овде:
Други делови:
Можете исто така да го проверите мојот канал на =)
Планирање: Ред за повратни информации на повеќе нивоа
Во ова предавање ќе зборуваме за проблемите на развивање на еден од најпознатите пристапи кон
планирање, кое се нарекува Ред за повратни информации на повеќе нивоа (MLFQ). Распоредувачот на MLFQ првпат беше опишан во 1962 година од Фернандо Ј. Корбато во систем наречен
Компатибилен систем за споделување време (CTSS). Овие дела (вклучувајќи подоцнежна работа на
Multics) потоа беа номинирани за наградата Тјуринг. Планерот беше
последователно се подобри и се здоби со изглед што веќе може да се најде во
некои модерни системи.
Алгоритмот MLFQ се обидува да реши 2 фундаментални проблеми со преклопување.
Прво, се обидува да го оптимизира времето на пресврт, кое, како што дискутиравме на претходното предавање, е оптимизирано со методот на започнување на почетокот на редот најмногу
кратки задачи. Сепак, оперативниот систем не знае колку долго ќе работи одреден процес, и ова
потребни знаења за функционирање на SJF, STCF алгоритмите. Второ, MLFQ се обидува
направете го системот одговорен за корисниците (на пример, за оние кои седат и
зјапајте во екранот чекајќи да заврши задачата) и на тој начин минимизирајте го времето
одговор. За жал, алгоритмите како RR го подобруваат времето на одговор, но исклучително
имаат лошо влијание врз метриката за време на пресврт. Оттука нашиот проблем: Како да дизајнираме
распоредувач кој ќе ги исполни нашите барања без да знаеме ништо за тоа
природата на процесот воопшто? Како може распоредувачот да ги научи карактеристиките на задачите,
кои ги лансира и на тој начин донесува подобри одлуки за планирање?
Суштината на проблемот: Како да се планира поставување на задачи без совршено знаење?
Како да дизајнирате распоредувач кој истовремено го минимизира времето на одговор
за интерактивни задачи и во исто време го минимизира времето на пресврт без да знае
познавање на времето на извршување на задачата?
Забелешка: учиме од претходните настани
Редот MLFQ е одличен пример за систем од кој учи
минати настани за да се предвиди иднината. Слични пристапи се често
пронајдени во ОС (И многу други гранки на компјутерската наука, вклучувајќи ги и гранките
хардверски предвидувања и алгоритми за кеширање). Слични патувања
се активираат кога задачите имаат фази на однесување и затоа се предвидливи.
Сепак, треба да бидете внимателни со оваа техника бидејќи предвидувањата се многу лесни
може да испадне дека е неточен и да го наведе системот да донесува полоши одлуки од
би бил воопшто без знаење.
MLFQ: Основни правила
Да ги погледнеме основните правила на алгоритмот MLFQ. И иако имплементации на овој алгоритам
Има неколку, основните пристапи се слични.
Во имплементацијата што ќе ја разгледаме, MLFQ ќе има неколку
посебни редици, од кои секоја ќе има различен приоритет. Во секое време,
задача подготвена за извршување е во една редица. MLFQ користи приоритети,
да одлучи која задача да ја изврши за извршување, т.е. задача со повисоко
приоритет (задача од редот со најголем приоритет) ќе се активира прво
редица.
Се разбира, може да има повеќе од една задача во дадена редица, така
па ќе имаат ист приоритет. Во овој случај, механизмот ќе се користи
RR да закаже трчање меѓу овие задачи.
Така, доаѓаме до две основни правила за MLFQ:
- Правило 1: Ако приоритет (А) > Приоритет (Б), задачата А ќе се стартува (Б нема)
- Правило 2: Ако приоритет(А) = Приоритет(Б), А&Б започнуваат со користење на RR
Врз основа на горенаведеното, клучните елементи за планирање на MLFQ
се приоритети. Наместо да се даде фиксен приоритет на секој
задача, MLFQ го менува својот приоритет во зависност од набљудуваното однесување.
На пример, ако некоја задача постојано фрла работа на процесорот додека чека влез од тастатурата,
MLFQ ќе го задржи приоритетот на процесот висок бидејќи така
треба да функционира интерактивен процес. Ако, напротив, задачата е постојано и
користи процесорот во голема мера во текот на долг период, MLFQ ќе го намали
приоритет. Така, MLFQ ќе го проучува однесувањето на процесите додека се извршуваат
и користат однесувања.
Ајде да нацртаме пример за тоа како би можеле да изгледаат редиците во одреден момент
време, а потоа добивате нешто како ова:
Во оваа шема, 2 процеси А и Б се во редот со највисок приоритет. Процес
C е некаде во средината, а процесот D е на самиот крај од редот. Според горенаведеното
Според описите на алгоритмот MLFQ, распоредувачот ќе извршува задачи само со највисоките
приоритет според RR, а задачите В, Г ќе бидат без работа.
Секако, статичната слика нема да даде целосна слика за тоа како функционира MLFQ.
Важно е да се разбере точно како сликата се менува со текот на времето.
Обид 1: Како да го промените приоритетот
Во овој момент треба да одлучите како MLFQ ќе го промени нивото на приоритет
задачи (а со тоа и позицијата на задачата во редот) додека таа напредува низ нејзиниот животен циклус. За
ова е неопходно за да се има предвид работниот тек: одредена сума
интерактивни задачи со кратко траење (а со тоа и често објавување
CPU) и неколку долготрајни задачи кои го користат процесорот целото свое работно време, додека
Времето на одговор не е важно за такви задачи. И на овој начин можете да го направите вашиот прв обид
имплементирајте го алгоритмот MLFQ со следниве правила:
- Правило 3: Кога задачата влегува во системот, таа се става во редот со највисоката
- приоритет.
- Правило 4а: Ако задачата го користи целиот временски прозорец што и е доделен, тогаш тоа
- приоритетот е намален.
- Правило 4б: Ако задачата го ослободи процесорот пред да истече временскиот прозорец, тогаш тој
- останува со истиот приоритет.
Пример 1: Единствена долготрајна задача
Како што може да се види во овој пример, задачата за прием е поставена со највисоката
приоритет. По временски прозорец од 10 ms, процесот се намалува во приоритет
планер. По следниот временски прозорец, задачата конечно е симната на
најнизок приоритет во системот, каде што останува.
Пример 2: Испорача кратка задача
Сега да видиме пример за тоа како MLFQ ќе се обиде да му пристапи на SJF. Во тоа
на пример, две задачи: А, што е долготрајна задача постојано
окупирање на процесорот и B, што е кратка интерактивна задача. Да претпоставиме
дека А веќе работел некое време додека пристигнала задачата Б.
Овој графикон ги прикажува резултатите од сценариото. Задача А, како и секоја задача,
Употребата на процесорот беше на самото дно. Задачата Б ќе пристигне во време Т=100 и ќе
сместени во редот со највисок приоритет. Затоа што неговото време на работа е кратко
ќе заврши пред да стигне до последната редица.
Од овој пример, треба да се разбере главната цел на алгоритмот: бидејќи алгоритмот не го прави тоа
знае дали задачата е долга или кратка, тогаш пред сè тој претпоставува дека задачата
краток и му дава најголем приоритет. Ако ова е навистина кратка задача, тогаш
брзо ќе се заврши, инаку ако е долга задача, полека ќе се движи
приоритет надолу и наскоро ќе докаже дека таа е навистина долга задача што не го прави тоа
бара одговор.
Пример 3: Што е со I/O?
Сега да погледнеме на пример I/O. Како што е наведено во правилото 4б,
ако некој процес го ослободува процесорот без да го искористи целото негово процесорско време,
тогаш останува на исто ниво на приоритет. Целта на ова правило е прилично едноставна
- ако интерактивната работа извршува многу I/O операции, на пример, чекање
од притискање на корисничкото копче или глувчето, таквата задача ќе го ослободи процесорот
пред доделениот прозорец. Не би сакале да го намалиме приоритетот на таква задача,
и со тоа ќе остане на исто ниво.
Овој пример покажува како алгоритмот ќе работи со такви процеси - интерактивна работа Б, на која му треба само процесорот за 1ms пред извршување
I/O процес и долготрајна Job A, која целото свое време го поминува користејќи го процесорот.
MLFQ го задржува процесот Б на највисок приоритет бидејќи продолжува
ослободете го процесорот. Ако Б е интерактивна задача, тогаш алгоритмот е постигнат
Вашата цел е брзо да извршувате интерактивни задачи.
Проблеми со тековниот алгоритам MLFQ
Во претходните примери изградивме основна верзија на MLFQ. И се чини дека тој
добро и чесно ја врши својата работа, распределувајќи го времето на процесорот прилично помеѓу
долги задачи и дозволување на кратки или големи задачи
брзо работете на I/O. За жал, овој пристап содржи неколку
сериозни проблеми.
Прво, проблемот со гладот: ако системот има многу интерактивни
задачи, тогаш тие ќе го потрошат целото време на процесорот и со тоа ниту една долго време
задачата нема да може да се изврши (умат од глад).
Второ, паметните корисници би можеле да ги напишат своите програми така што
измамете го распоредувачот. Измамата лежи во тоа да се направи нешто за да се присили
Распоредувачот му дава на процесот повеќе време на процесорот. Алгоритам кој
опишан погоре е доста ранлив на слични напади: пред временскиот прозорец да биде практично
заврши, треба да извршите I/O операција (на некои, без разлика која датотека)
и на тој начин да се ослободи процесорот. Таквото однесување ќе ви овозможи да останете на истото
самиот ред и повторно добивате поголем процент од времето на процесорот. Ако направиш
ова е точно (на пример, извршете 99% од времето на прозорецот пред да го ослободите процесорот),
таквата задача едноставно може да го монополизира процесорот.
Конечно, програмата може да го промени своето однесување со текот на времето. Тие задачи
кој го користел процесорот може да стане интерактивен. Во нашиот пример, слично
задачите нема да добијат третман што го заслужуваат од распоредувачот како што би го добиле другите
(почетни) интерактивни задачи.
Прашање до публиката: какви напади на распоредувачот би можеле да се извршат во современиот свет?
Обид 2: Зголемување на приоритетот
Ајде да се обидеме да ги промениме правилата и да видиме дали можеме да избегнеме проблеми со
постот. Што можеме да направиме за да се осигураме дека е поврзано
Задачите на процесорот ќе го добијат своето време (дури и ако не долго).
Како едноставно решение за проблемот, можете периодично да предлагате
подигнете го приоритетот на сите такви задачи во системот. Постојат многу начини
За да го постигнеме ова, ајде да се обидеме да имплементираме нешто едноставно како пример: преведи
На сите задачи веднаш им се дава најголем приоритет, па оттука и новото правило:
- Правило 5: По одреден период S, преместете ги сите задачи во системот во највисоката редица.
Нашето ново правило решава два проблема одеднаш. Прво, процесите
се гарантира дека нема да гладуваат: задачите што се во најголем приоритет ќе бидат поделени
Време на процесорот според алгоритмот RR и на тој начин ќе добијат сите процеси
Време на процесорот. Второ, ако некој процес што претходно се користел
само процесорот станува интерактивен, тој ќе остане во редот со највисоката
приоритет по добивањето еднократно зголемување на приоритетот до највисокото.
Ајде да погледнеме на пример. Во ова сценарио, размислете за користење на еден процес
Процесорот и два интерактивни, кратки процеси. Лево на сликата, фигурата го прикажува однесувањето без приоритетна промоција и на тој начин долготрајната задача почнува да гладува откако ќе пристигнат две интерактивни задачи во системот. На сликата од десната страна, се врши зголемување на приоритетот на секои 50 ms и на тој начин сите процеси се загарантирани да добиваат време на процесорот и периодично ќе се стартуваат. 50ms во овој случај се земени како пример; во реалноста оваа бројка е малку поголема.
Очигледно, додавањето на времето на периодично зголемување S доведува до
логично прашање: која вредност треба да се постави? Еден од почестените
системските инженери Џон Оустерхаут ги нарече таквите количини во системите како ву-ду
постојана, бидејќи тие на некој начин бараа црна магија за правилно
изложување. И, за жал, S има таков мирис. Ако ја поставите и вредноста
големи - долги задачи ќе почнат да гладуваат. И ако ја поставите вредноста премногу ниска,
Интерактивните задачи нема да добијат соодветно време на процесорот.
Обид 3: Подобро сметководство
Сега имаме уште еден проблем да решиме: како да не
дозволиме нашиот распоредувач да биде измамен? Луѓето кои се виновни за оваа можност се
правила 4а, 4б, кои дозволуваат работата да го задржи приоритетот, ослободувајќи го процесорот
пред истекот на даденото време. Како да се справите со ова?
Решението во овој случај може да се смета за подобро пресметување на времето на процесорот на секој
Ниво на MLFQ. Наместо да го заборавите времето што го користеше програмата
процесор за доделениот период, треба да се земе предвид и да се зачува. По
процесот го потрошил даденото време, треба да се деградира на следниот
ниво на приоритет. Сега не е важно како процесот ќе го искористи своето време - како
постојано пресметување на процесорот или како бројни повици. Така,
правило 4 треба да се преработи во следнава форма:
- Правило 4: Откако задачата ќе го потроши своето доделено време во тековната редица (без разлика колку пати го ослободи процесорот), приоритетот на таа задача се намалува (се движи по редот).
Ајде да погледнеме на пример:
»
Сликата покажува што се случува ако се обидете да го измамите распоредувачот, како
да беше со претходните правила 4а, 4б резултатот лево ќе се добие. Среќна Нова
правилото е резултатот од десната страна. Пред заштита, секој процес може да повика I/O пред да заврши и
со што доминираат во процесорот, откако ќе се овозможи заштита, без оглед на однесувањето
I/O, тој сепак ќе се движи надолу во редот и со тоа нема да може нечесно
ги преземе ресурсите на процесорот.
Подобрување на MLFQ и други проблеми
Со горенаведените подобрувања доаѓаат нови проблеми: еден од главните
Прашања - како да параметризирате таков распоредувач? Оние. Колку треба да биде
редици? Која треба да биде големината на програмскиот прозорец во редот? Како
Приоритетот на програмата често треба да се зголемува за да се избегне гладување и
да ја земе предвид промената во однесувањето на програмата? Не постои едноставен одговор на овие прашања
одговор и само експерименти со оптоварувања и последователна конфигурација
планерот може да доведе до некоја задоволителна рамнотежа.
На пример, повеќето имплементации на MLFQ ви дозволуваат да доделите различни
временски интервали за различни редици. Редици со висок приоритет обично
се пропишуваат кратки интервали. Овие редици се состојат од интерактивни задачи,
префрлувањето помеѓу кое е доста чувствително и треба да трае 10 или помалку
Госпоѓица. Спротивно на тоа, редиците со низок приоритет се состојат од долготрајни задачи кои користат
Процесорот. И во овој случај, долгите временски интервали се вклопуваат многу добро (100ms).
Во овој пример има 2 задачи кои работеа во редот 20 со висок приоритет
ms, поделени на прозорци од 10 ms. 40 ms во средната редица (прозорец 20 ms) и во низок приоритет
Прозорецот за време на редот стана 40 ms каде задачите ја завршија својата работа.
Имплементацијата на Solaris OS на MLFQ е класа на распоредувачи за споделување време.
Планерот ќе обезбеди збир на табели кои точно дефинираат како што треба
приоритетот на процесот се менува во текот на неговиот животен век, која треба да биде големината
доделен прозорец и колку често треба да ги подигате приоритетите на задачите. Администратор
системите можат да комуницираат со оваа табела и да предизвикаат однесување на распоредувачот
поинаку. Стандардно, оваа табела има 60 редици со постепено зголемување
големина на прозорецот од 20ms (висок приоритет) до неколку стотици ms (низок приоритет) и
исто така со засилување на сите задачи еднаш во секунда.
Другите MLFQ планери не користат табела или некоја специфична
правила кои се опишани во ова предавање, напротив, тие ги пресметуваат приоритетите користејќи
математички формули. На пример, распоредувачот на FreeBSD користи формула за
пресметајте го моменталниот приоритет на задачата врз основа на тоа колку е долг процесот
користен процесор. Покрај тоа, употребата на процесорот се распаѓа со текот на времето, и така
Така, зголемувањето на приоритетот се случува малку поинаку отколку што е опишано погоре. Ова е вистина
наречени алгоритми на распаѓање. Од верзијата 7.1, FreeBSD го користи распоредувачот ULE.
Конечно, многу распоредувачи имаат и други карактеристики. На пример, некои
распоредувачите ги резервираат највисоките нивоа за работа на оперативниот систем и на тој начин
Така, ниту еден кориснички процес не може да добие највисок приоритет во
систем. Некои системи ви дозволуваат да давате совети за помош
планерот може правилно да ги постави приоритетите. На пример, користејќи ја командата убаво
можете да го зголемите или намалите приоритетот на задачата и на тој начин да го зголемите или
намалете ги шансите на програмата да го користи времето на процесорот.
MLFQ: Резиме
Го опишавме пристапот за планирање наречен MLFQ. Неговото име
затворен во принципот на работа - има неколку редици и користи повратни информации
да се одреди приоритетот на задачата.
Конечната форма на правилата ќе биде како што следува:
- Правило 1: Ако приоритет (А) > Приоритет (Б), задачата А ќе се активира (Б нема)
- Правило 2: Ако приоритет(А) = Приоритет(Б), А&Б започнуваат со користење на RR
- Правило 3: Кога задачата влегува во системот, таа се става во редот со највисок приоритет.
- Правило 4: Откако задачата ќе го потроши своето доделено време во тековната редица (без разлика колку пати го ослободи процесорот), приоритетот на таа задача се намалува (се движи по редот).
- Правило 5: По одреден период S, преместете ги сите задачи во системот во највисоката редица.
MLFQ е интересен поради следната причина - наместо да бара знаење за
природата на задачата однапред, алгоритмот го проучува минатото однесување на задачата и поставува
приоритети соодветно. Така, тој се обидува да седне на две столчиња одеднаш - да постигне продуктивност за мали задачи (SJF, STCF) и искрено да трча долго,
Работи со вчитување на процесорот. Затоа, многу системи, вклучувајќи го BSD и нивните деривати,
Solaris, Windows, Mac користат некоја форма на алгоритам како распоредувач
MLFQ како основна линија.
Дополнителни материјали:
- (пресметување)
Извор: www.habr.com