Увядзенне ў аперацыйныя сістэмы
Прывітанне, Хабр! Жадаю прадставіць вашай увазе серыю артыкулаў-перакладаў адной цікавай на мой погляд літаратуры - OSTEP. У гэтым матэрыяле разглядаецца досыць глыбока праца unix-падобных аперацыйных сістэм, а менавіта - праца з працэсамі, рознымі планавальнікамі, памяццю і іншымі падобнымі кампанентамі, якія складаюць сучасную АС. Арыгінал усіх матэрыялаў вы можаце паглядзець вось . Прашу ўлічыць, што пераклад выкананы непрафесійна (дастаткова вольна), але спадзяюся агульны сэнс я захаваў.
Лабараторныя працы па дадзеным прадмеце можна знайсці вось тут:
Іншыя часткі:
А яшчэ можаце зазіраць да мяне на канал у =)
Планаванне: Multi-Level Feedback Queue
У гэтай лекцыі мы пагаворым аб праблемах распрацоўкі аднаго з самых вядомых падыходаў да
планаванні, які называецца Multi-Level Feedback Queue (MLFQ). Упершыню MLFQ планавальнік быў апісаны ў 1962 году Fernando J. Corbató у сістэме, званай
Compatible Time-Sharing System (CTSS). Гэтыя працы (у тым ліку і познія працы над
Multics) пасля былі прадстаўлены да ўзнагароды Turing Award. Планавальнік быў
пасля ўдасканалены і набыў аблічча, якое можна сустрэць ужо ў
некаторых сучасных сістэмах.
Алгарытм MLFQ спрабуе вырашыць 2 фундаментальныя перасякальныя праблемы.
Па-першае, ён спрабуе аптымізаваць час абароту, якое як мы разглядалі ў папярэдняй лекцыі, аптымізуецца метадам запуску ў пачатку чаргі найбольш
кароткіх задач. Аднак, АС не ведае як доўга будзе працаваць той ці іншы працэс, а гэта
неабходнае веданне для працы алгарытмаў SJF, STCF. Па-другое, MLFQ спрабуе
зрабіць сістэму спагаднай для карыстальнікаў (напрыклад для такіх, якія сядзяць і
тарашчацца ў экран у чаканні завяршэння задачы) і такім чынам мінімізаваць час
водгуку. Нажаль, алгарытмы накшталт RR памяншаюць час водгуку, але вельмі
дрэнна ўплываюць на метрыку часу абароту. Адсюль наша праблема: Як праектаваць
планавальнік, які будзе адказваць нашым патрабаванням і пры гэтым нічога не ведаць пра
характары працэсу, увогуле? Як планавальнік зможа вывучыць характарыстыкі задач,
якія ён запускае і такім чынам прымаць лепш рашэнні аб планаванні?
Сутнасць праблемы: Як планаваць пастаноўку задач без ідэальных ведаў?
Як распрацаваць планавальнік, які адначасова мінімізуе час водгуку
для інтэрактыўных задач і пры гэтым мінімізуе час абарачэння без свядомага
веданне часу выканання задачы?
Нататка: навучаемся па папярэдніх падзеях
Чарга MLFQ з'яўляецца выдатным прыкладам сістэмы, якая навучаецца на
якія прайшлі падзеях, каб прадказаць будучыню. Падобныя падыходы часта
сустракаюцца ў АС (І шматлікіх іншых галінах у інфарматыцы, уключаючы галінкі
прадказанняў у абсталяванні і алгарытмы кэшавання). Падобныя паходы
спрацоўваюць, калі ў задач ёсць паводніцкія фазы і такім чынам яны прадказальныя.
Аднак з такой тэхнікай трэба быць асцярожным, таму што прадказанні вельмі лёгка
могуць аказацца няправільнымі і прывесці сістэму да прыняцця горшых рашэнняў, чым
былі б без ведаў увогуле.
MLFQ: Basic Rules
Разгледзім базавыя правілы алгарытму MLFQ. І хаця рэалізацый гэтага алгарытму
існуе некалькі, базавыя падыходы падобныя.
У той рэалізацыі, якую мы будзем разглядаць, у MLFQ будзе некалькі
асобных чэргаў, кожная з якіх будзе мець розны прыярытэт. У любы час,
задача, гатовая да выканання знаходзіцца ў адной чарзе. MLFQ выкарыстоўвае прыярытэты,
каб вырашыць, якую задачу запускаць на выкананне, г.зн. задача з больш высокім
прыярытэтам (задача з чаргі з вышэйшым прыярытэтам) будзе запушчана ў першую
чаргу.
Несумненна, у канкрэтнай чарзе можа знаходзіцца больш за адну задачу, такім
чынам у іх будзе аднолькавы прыярытэт. У гэтым выпадку будзе выкарыстоўвацца механізм
RR для планавання запуску сярод гэтых задач.
Такім чынам мы прыходзім да двух базавых правіл для MLFQ:
- Rule1: Калі прыярытэт(А) > Прыярытэт(Б), будзе запушчана задача А (Б не будзе)
- Rule2: Калі прыярытэт(А) = Прыярытэт(Б), АіБ запускаюцца з выкарыстаннем RR
Зыходзячы з вышэйпералічанага, ключавымі элементамі да планавання MLFQ
з'яўляюцца прыярытэты. Замест таго, каб задаваць фіксаваны прыярытэт кожнаму
заданні, MLFQ змяняе яго прыярытэт у залежнасці ад назіраных паводзін.
Напрыклад, калі задача ўвесь час кідае працу на CPU у чаканні ўводу з клавіятуры,
MLFQ будзе падтрымліваць прыярытэт працэсу на высокім узроўні, таму што менавіта так
павінен працаваць інтэрактыўны працэс. Калі ж наадварот задача пастаянна і
інтэнсіўна выкарыстоўвае CPU на працягу доўгага перыяду, MLFQ будзе паніжаць яго
прыярытэт. Такім чынам, MLFQ будзе вывучаць паводзіны працэсаў у момант іх працы.
і выкарыстоўваць паводзін.
Намалюем прыклад таго, як маглі б выглядаць чэргі ў некаторы момант.
часу і тады атрымаецца нешта накшталт гэтага:
У дадзенай схеме 2 працэсу А і B знаходзяцца ў чарзе з найвышэйшым прыярытэтам. Працэс
З недзе пасярэдзіне, а працэс D у самым канцы чаргі. Згодна з прыведзеным вышэй
апісанням алгарытму MLFQ планавальнік будзе выконваць задачы толькі з найвышэйшым
прыярытэтам паводле RR, а задачы C,D будуць не ў спраў.
Натуральна статычны снапшот не дасць поўную карціну таго як працуе MLFQ.
Важна разумець, як менавіта мяняецца карціна з цягам часу.
Спроба 1: Як змяняць прыярытэт
У гэты момант неабходна вырашыць, як MLFQ будзе мяняць узровень прыярытэту
задачы (і такім чынам становішчы задачы ў чарзе) па ходзе яе жыццёвага цыклу. Для
гэтага неабходна трымаць у галаве працоўны працэс: некаторая колькасць
інтэрактыўных задач з кароткім часам працы (і такім чынам частае вызваленне
CPU) і некалькі доўгіх задач, якія выкарыстоўваюць CPU увесь свой працоўны час, пры гэтым
час водгуку для такіх задач не важна. І такім чынам можна зрабіць першую спробу
рэалізаваць алгарытм MLFQ з наступнымі правіламі:
- Rule3: Калі задача паступае ў сістэму, яна змяшчаецца ў чаргу з найвышэйшым
- прыярытэтам.
- Rule4a: Калі задача выкарыстоўвае цалкам адведзенае ёй часавае акно, то яе
- прыярытэт паніжаецца.
- Rule4b: Калі Задача вызваляе CPU да заканчэння свайго часавага акна, то яна
- застаецца з ранейшым прыярытэтам.
Прыклад 1: Адзіночная доўгапрацуючая задача
Як бачна ў гэтым прыкладзе, задача пры паступленні ставіцца з найвышэйшым.
прыярытэтам. Пасля часовага акна ў 10мс працэс паніжаецца ў прыярытэце
планавальнікам. Пасля наступнага часовага акна задача, нарэшце, паніжаецца да
найнізкага прыярытэту ў сістэме, дзе і застаецца.
Прыклад 2: Падвезлі кароткую задачу
Цяпер паглядзім прыклад таго, як MLFQ паспрабуе наблізіцца да SJF. У гэтым
прыкладзе дзве задачы: А, якая з'яўляецца доўгайграючай задачай пастаянна
займаючай CPU і B, якая з'яўляецца кароткай інтэрактыўнай задачай. Выкажам здагадку,
што А ўжо працавала некаторы час да моманту, калі паступіла задача B.
На дадзеным графіку бачныя вынікі сцэнара. Задача А, як і любая задача,
выкарыстоўвалая CPU апынулася ў самым нізе. Задача Ў прыбудзе падчас Т=100 і будзе
змешчана ў чаргу з найвышэйшым прыярытэтам. Паколькі час яе працы невялікі, то
яна завершыцца да таго як дасягне апошняй чаргі.
З гэтага прыкладу варта зразумець галоўную мэту алгарытму: паколькі алгарытм не
ведае доўгая задача ці кароткая, то ў першую чаргу ён мяркуе, што задача
кароткая і выдае ёй найвышэйшы прыярытэт. Калі гэта сапраўды кароткая задача, то
яна выканаецца хутка, інакш калі гэта доўгая задача, то яна будзе павольна рухацца
у прыярытэце ўніз і неўзабаве дакажа, што яна сапраўды доўгая задача, якая не
патрабуе водгуку.
Прыклад 3: Што ж пра ўвод-вывад?
Зараз зірнем на прыклад з уводам-вывадам. Як сцвярджалася ў правіле 4b,
калі працэс вызваляе працэсар, не выкарыстоўваўшы цалкам яго працэсарны час,
то ён застаецца на ранейшым узроўні прыярытэту. Намеры гэтага правіла даволі простыя
- калі інтэрактыўнае заданне выконвае шмат аперацый уводу-высновы, напрыклад, чакаючы
ад карыстальніка націскаў клавішы ці мышы, такое заданне будзе вызваляць працэсар
раней адведзенага акна. Мы не хацелі б апускаць такое заданне па прыярытэце,
і такім чынам яно застанецца на ранейшым узроўні.
Гэты прыклад паказвае як будзе працаваць алгарытм з такімі працэсамі - інтэрактыўнае заданне У, якое мае патрэбу ў CPU толькі на 1мс перад выкананнем
працэсу ўводу-вываду і доўгае заданне А, якое ўвесь свой час выкарыстоўвае CPU.
MLFQ трымае працэс У з найвышэйшым прыярытэтам, паколькі ён увесь час працягвае
вызваляць CPU. Калі B - інтэрактыўнае заданне, то алгарытм у такім выпадку дасягнуў
сваёй мэты запускаць інтэрактыўныя задачы хутка.
Праблемы з бягучым алгарытмам MLFQ
У папярэдніх прыкладах мы пабудавалі базавы варыянт MLFQ. І здаецца што ён
выконвае сваю працу добра і сумленна, размяркоўваючы працэсарны час сумленна паміж
доўгімі задачамі і дазваляючы кароткім задачам або задачам, якія інтэнсіўна звяртаюцца
да ўводу-вываду адпрацоўваць хутка. На жаль, такі падыход змяшчае некалькі
сур'ёзных праблем.
Па-першае, праблема голаду: калі ў сістэме будзе мноства інтэрактыўных
задач, то яны будуць спажываць увесь працэсарны час і такім чынам ніводнае доўгі
заданне не атрымае магчымасці выконвацца (яны галадаюць).
Па-другое, разумныя карыстальнікі маглі б пісаць свае праграмы так, каб
падмануць планавальнік. Падман крыецца ў тым, каб зрабіць нешта такое, каб прымусіць
планавальнік выдаваць працэсу больш працэсарнага часу. Алгарытм, які
апісаны вышэй суцэль уразлівы да падобных нападаў: перад тым як акно часу практычна
скончылася неабходна выканаць аперацыю ўводу-вываду (да нейкага, усё роўна якому файлу)
і такім чынам вызваліць CPU. Падобныя паводзіны дадуць магчымасць заставацца ў той жа
самай чаргі і зноў атрымаць большы працэнт працэсарнага часу. Калі зрабіць
гэта правільна (напрыклад, выконвацца 99% часу акна перад вызваленнем CPU),
такая задача папросту можа манапалізаваць працэсар.
Нарэшце, праграма можа мяняць свае паводзіны з часам. Тыя задачы,
якія выкарыстоўвалі CPU, могуць стаць інтэрактыўнымі. У нашым прыкладзе падобныя
задачы не атрымаюць належнага звароту ад планавальніка, бо атрымалі б іншыя.
(пачатковыя) інтэрактыўныя задачы.
Пытанне да залы: якія атакі на планавальнік можна было здзяйсняць у сучасным свеце?
Спроба 2: Павышэнне прыярытэту
Паспрабуем памяняць правілы і паглядзім ці атрымаецца пазбегнуць праблем з
галаданнем. Што б мы маглі зрабіць для таго, каб гарантаваць, што звязаныя з
CPU задачы атрымаюць свой час (нават калі і не доўгі).
У якасці простага рашэння праблемы можна прапанаваць перыядычна
павялічваць прыярытэт усіх такіх задач у сістэме. Існуе мноства спосабаў
дасягненні гэтага, паспрабуем увасобіць у якасці прыкладу нешта простае: перакладаць
адразу ўсе задачы ў найвышэйшы прыярытэт, адсюль новае правіла:
- Правіла5: Па сканчэнні некаторага перыяду S перавесці ўсе задачы ў сістэме ў найвышэйшую чаргу.
Наша новае правіла вырашае дзве праблемы адразу. Па-першае, працэсы
гарантавана не галадаюць: задачы, якія знаходзяцца ў вышэйшай чарзе будуць дзяліць
працэсарны час паводле алгарытму RR і такім чынам усе працэсы атрымаюць
працэсарны час. Па-другое, калі нейкі працэс, які раней выкарыстоўваў
толькі працэсар, становіцца інтэрактыўным, то ён будзе заставацца ў чарзе з вышэйшай
прыярытэтам пасля таго як аднойчы атрымае павышэнне прыярытэту да найвышэйшага.
Разгледзім прыклад. У гэтым сцэнары разгледзім адзін працэс, які выкарыстоўвае
CPU і два інтэрактыўных, кароткіх працэсу. Злева на малюнку малюнак дэманструе паводзіны без павышэння прыярытэту, і такім чынам доўгая задача пачынае галадаць пасля прыбыцця ў сістэму дзвюх інтэрактыўных задач. На малюнку справа кожныя 50мс выконваецца падвышэнне прыярытэту і такім чынам усе працэсы гарантавана атрымліваюць працэсарны час і будуць перыядычна запускацца. 50мс у дадзеным выпадку ўзята для прыкладу, рэальна гэты лік некалькі большы.
Відавочна, што даданне часу перыядычнага падвышэння S прыводзіць да
заканамернаму пытанню: якое значэнне павінна быць выстаўлена? Адзін з заслужаных
сістэмных інжынераў John Ousterhout называў падобныя велічыні ў сістэмах як voo-doo
канстанта, паколькі яны ў некаторым родзе патрабавалі чорнай магіі для карэктнага
выстаўлення. І, нажаль S мае такі водар. Калі выставіць значэнне занадта
вялікім - доўгія задачы пачнуць галадаць. А калі выставіць занізкае значэнне,
інтэрактыўныя задачы не атрымаюць належнага працэсарнага часу.
Спроба 3: Лепшы ўлік
Цяпер у нас ёсць яшчэ адна праблема, якую неабходна вырашыць: як не
дазваляць падманваць наш планавальнік? Вінаватымі ў гэтай магчымасці аказваюцца
правілы 4a, 4b, якія дазваляюць заданню захоўваць прыярытэт, вызваляючы працэсар
да заканчэння выдзеленага часу. Як жа з гэтым зладзіцца?
Рашэннем у гэтым выпадку можна лічыць найлепшы ўлік часу CPU на кожным
узроўні MLFQ. Замест таго каб забываць час, які праграма выкарыстоўвала
працэсар за адведзены прамежак, варта ўлічваць і захоўваць яго. Пасля таго як
працэс выдаткаваў адведзены яму час варта паніжаць яго да наступнага
ўзроўню прыярытэту. Цяпер усё роўна як працэс будзе выкарыстоўваць свой час - як
стала які вылічае на працэсары або як мноства выклікаў. Такім чынам,
варта перапісаць правіла 4 да наступнага ўвазе:
- Правіла4: Пасля таго як задача выдаткавала выдзелены ёй час у бягучай чарзе (незалежна ад таго колькі разоў яна вызваляла CPU) прыярытэт такой задачы паніжаецца (яна рухаецца ўніз чарзе).
Паглядзім на прыклад:
»
На малюнку паказана што здараецца, калі паспрабаваць ашукаць планавальнік, як
калі б было з папярэднімі правіламі 4a, 4b атрымаецца рэзультат злева. З новым
правілам - вынік справа. Да абароны любы працэс мог выклікаць I/O да завяршэння і
такім чынам дамінаваць на CPU, пасля ўключэння абароны, незалежна ад паводзін
I/O, ён будзе ўсё роўна апускацца ў чэргі ўніз і такім чынам не зможа несумленна
завалодаць рэсурсамі CPU.
Паляпшаем MLFQ і іншыя праблемы
З прыведзенымі вышэй паляпшэннямі ўзнікаюць новыя праблемы: адзін з галоўных
пытанняў - як параметрызаваць падобны планавальнік? Г.зн. Колькі павінна быць
чэргаў? Які павінен быць памер акна працы праграмы ў межах чаргі? Як
часта варта падвышаць прыярытэт праграмы для таго каб пазбегнуць галаданні і
прыняць да ўвагі змена паводзінаў праграмы? На гэтыя пытанні, няма простага
адказу і толькі эксперыменты з нагрузкамі і наступнае канфігураванне
планавальніка можа прывесці да нейкага здавальняючага балансу.
Напрыклад, большасць рэалізацый MLFQ дазваляюць прызначаць розныя.
часовыя інтэрвалы розным чэргам. Высокапрыярытэтным чэргам звычайна
прызначаюцца кароткія інтэрвалы. Гэтыя чэргі складаюцца з інтэрактыўных задач,
пераключэнне паміж якімі даволі адчувальна і павінна займаць 10 ці менш
мс. У процівагу нізкапрыярытэтныя чэргі складаюцца з доўгіх задач, якія выкарыстоўваюць
CPU. І ў гэтым выпадку доўгія часавыя інтэрвалы падыходзяць вельмі добрае (100мс).
У гэтым прыкладзе ёсць 2 задачы, якія прапрацавалі ў высокапрыярытэтнай чарзе.
мс, разбітыя на вокны па 10мс. 40мс у сярэдняй чарзе (акно ў 20мс) і ў нізкапрыярытэтнай
чарзе часовае акно стала 40мс, дзе задачы завяршылі сваю працу.
Рэалізацыя MLFQ у АС Solaris - клас планавальнікаў, якія падзяляюць па часе.
Планавальнік прадаставіць набор табліц, якія вызначаюць у дакладнасці, як павінен
мяняцца прыярытэт працэсу з цягам яго жыцця, якім павінен быць памер
які выдаткоўваецца акна і як часта трэба паднімаць прыярытэты задачы. Адміністратар
сістэмы можа ўзаемадзейнічаць з гэтай табліцай і прымушаць планавальнік паводзіць сябе
па іншаму. Па-змаўчанні ў гэтай табліцы 60 чэргаў з паступовым павелічэннем
памеру акна з 20мс (высокі прыярытэт) да некалькіх сотняў мс (ніжэйшы прыярытэт), а
таксама з бустам усіх задач раз у секунду.
Іншыя MLFQ планавальнікі не выкарыстоўваюць табліцу ці нейкія канкрэтныя
правілы, якія апісаны ў гэтай лекцыі, насупраць яны вылічаюць прыярытэты, выкарыстоўваючы
матэматычныя формулы. Так, напрыклад планавальнік у FreeBSD выкарыстоўвае формулу для
вылічэнні бягучага прыярытэту задачы, грунтуючыся на тым, колькі працэс
выкарыстоўваў CPU. У дадатак, выкарыстанне CPU з часам загнівае, і такім
чынам павышэнне прыярытэту адбываецца некалькі інакш, чым апісана вышэй. Гэта так
званыя decay алгарытмы. З версіі 7.1 у FreeBSD выкарыстоўваецца планавальнік ULE.
Нарэшце, многія планавальнікі маюць іншыя асаблівасці. Напрыклад, некаторыя
планавальнікі рэзервуюць вышэйшыя ўзроўні для працы аперацыйнай сістэмы і такім
чынам, ніякі карыстацкі працэс не зможа атрымаць найвышэйшы прыярытэт у
сістэме. Некаторыя сістэмы дазваляюць даваць парады для таго каб дапамагчы
планавальніку карэктна выстаўляць прыярытэты. Так напрыклад, з дапамогай каманды прыемна
можна павялічваць або памяншаць прыярытэт задачы і такім чынам падвышаць або
паніжаць шанцы праграмы на працэсарны час.
MLFQ: Вынікі
Мы апісалі падыход да планавання, які называецца MLFQ. Яго назва
заключана ў прынцыпе працы - ён мае некалькі чэргаў і выкарыстоўвае зваротную сувязь
для вызначэння прыярытэту задачы.
Выніковы від правіл будзе наступным:
- Правіла1: Калі прыярытэт(А) > Прыярытэт(Б), будзе запушчана задача А (Б не будзе)
- Правіла2: Калі прыярытэт(А) = Прыярытэт(Б), АіБ запускаюцца з выкарыстаннем RR
- Правіла3: Калі задача паступае ў сістэму, яна змяшчаецца ў чаргу з найвышэйшым прыярытэтам.
- Правіла4: Пасля таго як задача выдаткавала выдзелены ёй час у бягучай чарзе (незалежна ад таго колькі разоў яна вызваляла CPU) прыярытэт такой задачы паніжаецца (яна рухаецца ўніз чарзе).
- Правіла5: Па сканчэнні некаторага перыяду S перавесці ўсе задачы ў сістэме ў найвышэйшую чаргу.
MLFQ цікавы па наступнай прычыне - замест таго каб патрабаваць веданне аб
прыродзе задачы загадзя, алгарытм вывучае мінулае паводзіны задачы і выстаўляе
прыярытэты адпаведна. Такім чынам ён імкнецца ўседзець адразу на двух крэслах - дасягнуць прадукцыйнасці для маленькіх задач (SJF, STCF) і сапраўды запускаць доўгія,
загружаюць CPU заданні. Таму многія сістэмы, у тым ліку BSD і іх вытворныя,
Solaris, Windows, Mac выкарыстоўваюць у якасці планавальніка некаторую форму алгарытму
MLFQ у якасці базавай асновы.
Дадатковыя матэрыялы:
- (Computing)
Крыніца: habr.com