Увядзенне ў аперацыйныя сістэмы
Прывітанне, Хабр! Жадаю прадставіць вашай увазе серыю артыкулаў-перакладаў адной цікавай на мой погляд літаратуры - OSTEP. У гэтым матэрыяле разглядаецца досыць глыбока праца unix-падобных аперацыйных сістэм, а менавіта - праца з працэсамі, рознымі планавальнікамі, памяццю і іншымі падобнымі кампанентамі, якія складаюць сучасную АС. Арыгінал усіх матэрыялаў вы можаце паглядзець вось . Прашу ўлічыць, што пераклад выкананы непрафесійна (дастаткова вольна), але спадзяюся агульны сэнс я захаваў.
Лабараторныя працы па дадзеным прадмеце можна знайсці вось тут:
Іншыя часткі:
А яшчэ можаце зазіраць да мяне на канал у =)
Увядзенне ў планавальнік
Сутнасць праблемы: Як распрацаваць палітыку планавальніка
Як павінны распрацоўвацца базавыя фрэймворкі палітык планавальніка? Якія павінны быць ключавыя здагадкі? Якія метрыкі важныя? Якія базавыя тэхнікі выкарыстоўваліся ў ранніх вылічальных сістэмах?
Здагадкі працоўнай нагрузкі
Перад тым як абмеркаваць магчымыя палітыкі, для пачатку зробім некалькі якія спрашчаюць адступленняў аб працэсах, запушчаных у сістэме, якія ўсё разам завуцца працоўнай нагрузкай. Вызначаючы працоўную нагрузку, як крытычную частку пабудовы палітык і чым больш вы ведаеце аб нагрузцы, тым больш якасную палітыку вы зможаце напісаць.
Зробім наступныя здагадкі аб працэсах запушчаных у сістэме, часам яшчэ званых. працоўных месцаў (задачамі). Практычна ўсе гэтыя здагадкі не рэалістычныя, але патрэбны для развіцця думкі.
- Кожная задача запушчана аднолькавую колькасць часу,
- Усе задачы ставяцца адначасова,
- Пастаўленая задача працуе да свайго завяршэння,
- Усе задачы выкарыстоўваюць толькі CPU,
- Час працы кожнай задачы вядомы.
Метрыкі планавальніка
Акрамя некаторых здагадак аб нагрузцы неабходна яшчэ некаторая прылада параўнання розных палітык планавання: метрыкі планавальніка. Метрыка гэта ўсяго толькі некаторая мера чагосьці. Існуе некаторую колькасць метрык, якія можна выкарыстоўваць для параўнання планавальнікаў.
Для прыкладу будзем выкарыстоўваць метрыку, якая называецца час абароту (Turnaround time). Час абароту задачы вызначаецца як розніца паміж часам завяршэння задачы і час паступлення задачы ў сістэму.
Tturnaround=Tcompletion−Tarrival
Паколькі мы выказалі здагадку, што ўсе задачы паступілі ў адзін час, то Ta=0 і такім чынам Tt=Tc. Гэта значэнне натуральна памяняецца, калі мы зменім вышэйпералічаныя здагадкі.
Іншая метрыка - справядлівасць (справядлівасць, сумленнасць). Прадукцыйнасць і сумленнасць часта з'яўляюцца супрацьдзейнымі характарыстыкамі ў планаванні. Напрыклад, планавальнік можа аптымізаваць прадукцыйнасць, але коштам чакання запуску іншымі задачамі, такім чынам, змяншаецца сумленнасць.
FIRST IN FIRST OUT (FIFO)
Самы базавы алгарытм, які мы можам ўвасобіць называецца FIFO або first come (in), first served (out). Гэты алгарытм мае некалькі пераваг: ён вельмі просты ў рэалізацыі і ён падыходзіць пад усе нашыя здагадкі, выконваючы працу даволі добра.
Разгледзім просты прыклад. Дапусцім 3 задачы былі пастаўлены адначасова. Але выкажам здагадку што задача А прыйшла крыху раней за ўсіх астатніх, таму ў спісе выканання будзе стаяць раней за астатніх, сапраўды таксама як і Б адносна В. Выкажам здагадку што кожная з іх будзе выконвацца 10 секунд. Які ў гэтым выпадку будзе сярэдні час выканання гэтых задач?
Падлічыўшы значэнні - 10 20 30 і падзяліўшы на 3, атрымаем сярэдні час выканання праграмы роўнае 20 секундам.
Цяпер паспрабуем змяніць нашы здагадкі. У прыватнасці здагадка 1 і такім чынам не будзем больш меркаваць, што кожная задача выконваецца аднолькавая колькасць часу. Як пакажа сябе FIFO на гэты раз?
Як аказваецца розныя часы выканання задач вельмі негатыўна адбіваюцца на прадуктыўнасці алгарытму FIFO. Выкажам здагадку што задача А будзе выконвацца 100 секунд, тады як Бы і Ў па-ранейшаму будуць па 10 кожная.
Як відаць з малюнка, сярэдні час для сістэмы атрымаецца (100 110 120) / 3 = 110. Такі эфект называецца эфектам канвою, Калі некаторыя кароткачасовыя спажыўцы якога-небудзь рэсурсу будуць стаяць у чарзе ўслед за цяжкім спажыўцом. Гэта падобна на чаргу ў прадуктовай краме, калі перад вамі пакупнік з поўнай каляскай. Лепшае рашэнне праблемы - паспрабаваць змяніць касу ці ж расслабіцца і дыхаць глыбока.
Shortest Job First
Ці можна неяк вырашыць падобную сітуацыю з цяжкавагавымі працэсамі? Канечне. Іншы тып планавання называеццаShortest Job First (SJF). Яго алгарытм таксама дастаткова прымітыўны - як зразумела з назвы, першымі будуць запушчаны самыя кароткія задачы адна за адной.
У дадзеным прыкладзе вынікам запуску тых жа самых працэсаў, будзе паляпшэнне сярэдняга часу абарачэння праграм і яно будзе роўна. 50 замест 110, Што практычна ў 2 разы лепш.
Такім чынам, для зададзенай здагадкі, што ўсе задачы прыбываюць у адно і тое ж час, алгарытм SJF здаецца найболей аптымальным алгарытмам. Аднак нашыя здагадкі ўсё яшчэ не здаюцца рэалістычнымі. У гэты раз зменім здагадку 2 і ў гэты раз уявім, што задачы могуць знаходзіцца ў любы час, а не ўсе адначасова. Да якіх праблем гэта можа прывесці?
Уявім, што задача А (100с) прыбывае самай першай і пачынае выконвацца. У момант t=10 прыбываюць задачы Б, У, кожная з якіх будзе займаць 10 секунд. Такім чынам, сярэдні час выканання гэты (100+(110-10)+(120-10))3 = 103. Што б мог планавальнік зрабіць, каб палепшыць становішча?
Shortest Time-to-Completion First (STCF)
Для таго каб палепшыць становішча апусцім здагадку 3 аб тым, што праграма запушчана і працуе да завяршэння. Акрамя таго нам спатрэбіцца падтрымка абсталявання і як вы маглі здагадацца мы будзем выкарыстоўваць таймер для перапынення працавальнай задачы і пераключэнні кантэкстаў. Такім чынам планавальнік можа нешта зрабіць у момант паступлення задач Б, У - спыніць выкананне задачы А і паставіць у апрацоўку задачы Б і Ў і пасля іх канчатка працягнуць выкананне працэсу А. Такі планавальнік завецца STCFабо Preemptive Job First.
Вынікам працы гэтага планавальніка будзе такі вынік: ((120-0)+(20-10)+(30-10))/3=50. Такім чынам, такі планавальнік становіцца яшчэ больш аптымальным для нашых задач.
Метрыка Час водгуку (Response Time)
Такім чынам, калі мы ведаем час працы задач і тое, што гэтыя задачы выкарыстоўваюць толькі CPU, STCF будзе найлепшым рашэннем. І калісьці ў раннія часы гэтыя алгарытмы працавалі і даволі нядрэнна. Аднак зараз карыстач праводзіць асноўны час за тэрміналам і чакае ад яе прадукцыйнага інтэрактыўнага ўзаемадзеяння. Так нарадзілася новая метрыка. час адказу (водгуку).
Час водгуку лічыцца наступным чынам:
Tresponse=Tfirstrun−Tarrival
Такім чынам, для папярэдняга прыкладу час водгуку будзе такім: А = 0, Б = 0, У = 10 (abg = 3,33).
І аказваецца алгарытм STCF не так ужо і добры ў сітуацыі, калі 3 задачы прыбудуць адначасова – яму давядзецца дачакацца, пакуль маленькія задачы цалкам не завершацца. Такім чынам, алгарытм добры для метрыкі часу абароту, але дрэнны для метрыкі інтэрактыўнасці. Прадстаўце, што седзячы за тэрміналам у спробе надрукаваць знакі ў рэдактары вам прыйшлося б чакаць больш за 10 секунд, таму што нейкая іншая задача займае працэсар. Гэта не вельмі і прыемна.
Такім чынам мы сутыкаемся з іншай праблемай - як мы можам пабудаваць планавальнік, які б быў адчувальны да часу водгуку?
Round Robin
Для вырашэння гэтай праблемы быў распрацаваны алгарытм Round Robin (RR). Асноўная ідэя даволі простая: замест запуску задач да поўнага завяршэння, будзем запускаць задачу на некаторы прамежак часу (званы квантам часу) і затым пераключацца на іншую задачу з чаргі. Алгарытм паўтарае сваю працу да таго часу, пакуль усе задачы не завершацца. Пры гэтым час працы праграмы павінна быць кратна часу, праз якое таймер перапыніць працэс. Напрыклад, калі таймер перарывае працэс кожныя х=10мс, то памер акна выканання працэсу павінен быць краты 10 і быць 10,20 ці х*10.
Разгледзім прыклад: Задачы АБВ прыбываюць адначасова ў сістэму і кожная з іх жадае працаваць 5 секунд. Алгарытм SJF будзе выконваць кожную задачу да канца, перад тым як запусціць іншую. У супрацьпастаўленне алгарытм RR c акном запуску = 1с пройдзе па задачах наступным чынам (мал. 4.3):
(SJF Again (Bad for Response Time)
(Round Robin (Гады на Response Time)
Сярэдні час водгуку для алгарытму RR (0+1+2)/3=1, тады як для SJF (0+5+10)/3=5.
Лагічна меркаваць, што акно часу вельмі важны параметр для RR, чым менш яно, тым вышэй час адказу. Аднак, нельга рабіць яго і залішне маленькім, паколькі час на пераключэнне кантэксту будзе таксама гуляць сваю ролю ў агульнай прадукцыйнасці. Такім чынам, выбар часу акна выканання выстаўляецца архітэктарам АС і залежыць ад задач, якія ў ёй плануюцца выконвацца. Пераключэнне кантэксту не адзіная службовая аперацыя, якая марнуе час - запушчаная праграма шмат чым яшчэ аперуе, напрыклад розным кэшамі і пры кожным пераключэнні неабходна захоўваць і аднаўляць гэтае асяроддзе, што таксама можа патрабаваць шмат часу.
RR - выдатны планавальнік, калі б гаворка ішла толькі аб метрыцы часу водгуку. Але як павядзе сябе метрыка часу абароту задачы пры гэтым алгарытме? Разгледзім прыклад вышэй, калі час работы А, Б, В = 5с і паступаюць у адзін і той жа час. Задача А завершыцца ў 13, Б у 14, Ва ў 15с і сярэдні час абароту атрымаецца 14с. Такім чынам, RR з'яўляецца самым дрэнным алгарытмам для метрыкі абароту.
Больш агульнымі словамі, любы алгарытм тыпу RR – сумленны, ён дзеліць час працы на CPU пароўну паміж усімі працэсамі. І такім чынам, гэтыя метрыкі ўвесь час канфліктуюць паміж сабой.
Тым самым, у нас ёсць некалькі супрацьпастаўленых алгарытмаў і пры гэтым яшчэ застаецца некалькі здагадак - аб тым, што час задачы вядома і што задача толькі выкарыстоўвае CPU.
Змешванне з I/O
У першую чаргу прыбяром здагадка 4, што працэс толькі выкарыстоўвае CPU, натуральна гэта не так і працэсы могуць звяртацца і да іншага абсталявання.
У момант, калі які-небудзь працэс запытвае аперацыю ўводу-высновы, працэс пераходзіць у стан blocked, чакаючы завяршэнні I/O. Калі I/O пасылаецца да цвёрдай кружэлкі, то такая аперацыя можа займаць аж да некалькіх мс ці даўжэй, і працэсар у гэты момант будзе прастойваць. Тым часам планавальнік можа заняць працэсар любым іншым працэсам. Наступнае рашэнне якое прыйдзецца прымаць планавальніку - калі працэс завершыць свой I/O. Калі гэта здарыцца, адбудзецца перапыненне і АС перавядзе які выклікаў I/O працэс у стан ready.
Разгледзім прыклад з некалькіх задач. Кожная з іх мае патрэбу ў 50мс працэсарнага часу. Аднак першая будзе кожныя 10мс звяртацца да I/O (які таксама будзе выконвацца па 10мс). А працэс Бы проста выкарыстоўвае 50мс працэсар без I/O.
У дадзеным прыкладзе будзем выкарыстоўваць STCF планавальнік. Як павядзе сябе планавальнік, калі запусціць на ім такі працэс як А? Ён паступіць наступным чынам - спачатку цалкам адпрацуе працэс А, а потым працэс Б.
Традыцыйны падыход для вырашэння гэтай праблемы - інтэрпрэтаваць кожную 10-мс падзадачу працэсу А як асобную задачу. Такім чынам, пры старце з алгарытмам STJF, выбар паміж 50-мс задачай і 10-мс задачай відавочны. Затым калі падзадача А завершыцца будзе запушчаны працэс Б і I/O. Пасля завяршэння I/O будзе прынята зноў запусціць 10-мс працэс А замест працэсу Б. Такім чынам магчыма рэалізаваць перакрыцце, калі CPU выкарыстоўваецца іншым працэсам, пакуль першы чакае I/O. І як вынік сістэма лепш утылізуецца – у момант калі інтэрактыўныя працэсы чакаюць I/O на працэсары могуць выконвацца і іншыя працэсы.
Аракула больш няма
Цяпер паспрабуем пазбавіцца аб здагадцы, што час працы задачы вядомы. Гэта ў цэлым самая дрэнная і нерэальная здагадка з усяго спісу. Фактычна ў сярэднестатыстычных звычайных АС, сама АС звычайна вельмі мала ведае аб часе выканання задач, як жа тады будаваць планавальнік без ведання таго колькі часу задача будзе выконвацца? Быць можа мы маглі б выкарыстоўваць некаторыя прынцыпы RR для вырашэння гэтай праблемы?
Вынік
Мы разгледзелі базавыя ідэі планавання задач і разгледзелі 2 сямействы планавальнікаў. Першы запускае найкароткую задачу спачатку і такім чынам павялічвае час абарачэння, другі ж разрываецца паміж усімі задачамі аднолькава, падвышаючы час водгуку. Абодва алгарытму дрэнныя там, дзе добрыя алгарытмы іншага сямейства. Таксама мы разгледзелі як паралельнае выкарыстанне CPU і I/O могуць палепшыць прадукцыйнасць, але так і не вырашылі праблему з празорлівасцю АС. І на наступным занятку мы разгледзім планавальнік, які глядзіць у бліжэйшае мінулае і спрабуе прадбачыць будучыню. І называецца ён multi-level feedback queue.
Крыніца: habr.com