Увод у оперативне системе
Хеј Хабр! Желео бих да вам скренем пажњу на серију чланака-превода једне по мени занимљиве литературе – ОСТЕП. У овом материјалу се прилично дубоко разматра рад оперативних система сличних униксу, односно рад са процесима, разним планерима, меморијом и другим сличним компонентама које чине савремени ОС. Овде можете видети оригинал свих материјала . Напомињемо да је превод урађен нестручно (прилично слободно), али се надам да сам задржао опште значење.
Лабораторијски рад на ову тему можете пронаћи овде:
Остали делови:
Такође можете погледати мој канал на =)
Увод у Планер
Суштина проблема: Како развити политику планера
Како треба да буду дизајнирани основни оквири политике планера? Које би требало да буду кључне претпоставке? Које метрике су важне? Које су основне технике коришћене у раним рачунарским системима?
Претпоставке радног оптерећења
Пре него што разговарамо о могућим политикама, хајде да прво направимо неколико поједностављених дигресија о процесима који се одвијају у систему, који се заједнички називају оптерећења. Дефинисање радног оптерећења је критичан део израде смерница, и што више знате о радном оптерећењу, то боље смернице можете написати.
Хајде да направимо следеће претпоставке о процесима који се покрећу у систему, који се понекад називају Послови (задаци). Готово све ове претпоставке нису реалне, али су неопходне за развој мисли.
- Сваки задатак траје исто време,
- Сви задаци се постављају истовремено,
- Додељени задатак ради до његовог завршетка,
- Сви задаци користе само ЦПУ,
- Време извођења сваког задатка је познато.
метрика планера
Поред неких претпоставки о оптерећењу, потребан је још један алат за поређење различитих смерница планирања: метрика планера. метрика је само нека мера нечега. Постоји низ метрика које се могу користити за упоређивање планера.
На пример, користићемо метрику тзв Смањено (Смањено). Време преокрета задатка се дефинише као разлика између времена завршетка задатка и времена доласка задатка у систем.
Ттурнароунд=Тцомплетион−Тарривал
Пошто смо претпоставили да су сви задаци стигли у исто време, онда је Та=0 и тиме Тт=Тц. Ова вредност ће се природно променити када променимо горње претпоставке.
Још једна метрика - поштење (праведност, поштење). Продуктивност и правичност су често супротне карактеристике у планирању. На пример, планер може да оптимизује перформансе, али по цену чекања да се други задаци покрену, чиме се смањује правичност.
ПРВИ УЛАЗИО ПРВИ ОУТ (ФИФО)
Најосновнији алгоритам који можемо имплементирати зове се ФИФО или први ушао (ушао), први услужен (изишао). Овај алгоритам има неколико предности: веома је лак за имплементацију и уклапа се у све наше претпоставке и ради посао прилично добро.
Погледајмо једноставан пример. Рецимо да су постављена 3 задатка истовремено. Али претпоставимо да је задатак А стигао мало раније од свих осталих, па ће се појавити на листи извршења раније од осталих, баш као Б у односу на Ц. Претпоставимо да ће сваки од њих бити извршен 10 секунди. Колико ће бити просечно време за обављање ових задатака у овом случају?
Пребројавањем вредности - 10+20+30 и дељењем са 3, добијамо просечно време извршавања програма једнако 20 секунди.
Покушајмо сада да променимо наше претпоставке. Конкретно, претпоставка 1 и стога више нећемо претпостављати да је сваком задатку потребно исто време да се изврши. Како ће ФИФО наступити овог пута?
Како се испоставило, различита времена извршавања задатака имају изузетно негативан утицај на продуктивност ФИФО алгоритма. Претпоставимо да ће задатку А бити потребно 100 секунди да се заврши, док ће Б и Ц и даље трајати по 10 секунди.
Као што се може видети са слике, просечно време за систем ће бити (100+110+120)/3=110. Овај ефекат се зове ефекат конвоја, када ће неки краткорочни потрошачи ресурса стајати у реду за великим потрошачем. То је као ред у продавници када је испред вас муштерија са пуним колицима. Најбоље решење проблема је да покушате да промените касу или да се опустите и дубоко удахнете.
Најкраћи посао прво
Да ли је могуће некако решити сличну ситуацију са тешким процесима? Сигурно. Друга врста планирања се зовеНајкраћи посао прво (СЈФ). Његов алгоритам је такође прилично примитиван - као што назив говори, најкраћи задаци ће бити покренути први, један за другим.
У овом примеру, резултат покретања истих процеса биће побољшање просечног времена обртања програма и оно ће бити једнако 50 umesto 110, што је скоро 2 пута боље.
Дакле, за дату претпоставку да сви задаци стижу у исто време, СЈФ алгоритам изгледа као најоптималнији алгоритам. Међутим, наше претпоставке и даље не делују реално. Овог пута мењамо претпоставку 2 и овог пута замислимо да задаци могу бити присутни у било ком тренутку, а не сви у исто време. До каквих проблема то може довести?
Замислимо да задатак А (100ц) стигне први и почне да се извршава. У т=10 стижу задаци Б и Ц, од којих ће сваки трајати 10 секунди. Дакле, просечно време извршења је (100+(110-10)+(120-10))3 = 103. Шта би планер могао да уради да ово побољша?
Најкраће време до првог завршетка (СТЦФ)
Да бисмо побољшали ситуацију, изостављамо претпоставку 3 да је програм покренут и да траје до завршетка. Поред тога, биће нам потребна хардверска подршка и, као што можете претпоставити, користићемо тимер да прекине радни задатак и пребацивање контекста. Дакле, планер може да уради нешто у тренутку када задаци Б, Ц стигну - заустави извршавање задатка А и стави задатке Б и Ц у обраду и, након њиховог завршетка, настави са извршавањем процеса А. Такав планер се зове СТЦФили Превентивни посао прво.
Резултат овог планера биће следећи резултат: ((120-0)+(20-10)+(30-10))/3=50. Дакле, такав планер постаје још оптималнији за наше задатке.
Метричко време одзива
Дакле, ако знамо време извршавања задатака и да ови задаци користе само ЦПУ, СТЦФ ће бити најбоље решење. И једном у раним временима, ови алгоритми су радили прилично добро. Међутим, корисник сада већину свог времена проводи на терминалу и очекује продуктивно интерактивно искуство. Тако је рођена нова метрика - Време одзива (одговор).
Време одговора се израчунава на следећи начин:
Треспонсе=Тфирструн−Тарривал
Тако ће за претходни пример време одзива бити: А=0, Б=0, Ц=10 (абг=3,33).
И испоставило се да СТЦФ алгоритам није тако добар у ситуацији када 3 задатка стижу у исто време - мораће да сачека док се мали задаци потпуно не заврше. Дакле, алгоритам је добар за метрику времена обрта, али лош за метрику интерактивности. Замислите да седите за терминалом и покушавате да унесете знакове у едитор и морате да чекате више од 10 секунди јер је неки други задатак заузимао ЦПУ. Није баш пријатно.
Дакле, суочени смо са још једним проблемом - како да направимо планер који је осетљив на време одговора?
разигравање
За решавање овог проблема развијен је алгоритам разигравање (РР). Основна идеја је прилично једноставна: уместо покретања задатака док се не заврше, ми ћемо покренути задатак у одређеном временском периоду (који се назива временски одсек), а затим се пребацити на други задатак из реда. Алгоритам понавља свој рад док се сви задаци не заврше. У овом случају, време рада програма мора бити вишеструко од времена након којег ће тајмер прекинути процес. На пример, ако тајмер прекида процес сваких к=10мс, тада би величина прозора за извршавање процеса требало да буде вишеструка од 10 и да буде 10,20 или к*10.
Погледајмо пример: АБЦ задаци стижу истовремено у систем и сваки од њих жели да се покрене 5 секунди. СЈФ алгоритам ће завршити сваки задатак пре него што започне други. Насупрот томе, РР алгоритам са прозором за покретање = 1с ће проћи кроз задатке на следећи начин (слика 4.3):
(СЈФ поново (лоше за време одзива)
(Роунд Робин (добро за време одговора)
Просечно време одзива за РР алгоритам је (0+1+2)/3=1, док је за СЈФ (0+5+10)/3=5.
Логично је претпоставити да је временски прозор веома важан параметар за РР; што је мањи, то је време одговора веће. Међутим, не би требало да буде премало, јер ће време промене контекста такође играти улогу у укупним перформансама. Дакле, избор времена прозора за извршавање поставља архитекта ОС-а и зависи од задатака који се планирају у њему извршити. Пребацивање контекста није једина сервисна операција која губи време – покренути програм ради на многим другим стварима, на пример, разним кеш меморијама, а са сваким прекидачем потребно је сачувати и вратити ово окружење, што такође може потрајати време.
РР је одличан планер ако говоримо само о метрици времена одговора. Али како ће се метрика времена обртања задатка понашати са овим алгоритмом? Размотримо горњи пример, када је време рада А, Б, Ц = 5с и стиже у исто време. Задатак А ће се завршити у 13, Б у 14, Ц у 15 секунди, а просечно време преокрета ће бити 14 секунди. Дакле, РР је најгори алгоритам за метрику промета.
Уопштеније говорећи, било који алгоритам типа РР је поштен; он дели ЦПУ време подједнако између свих процеса. И стога, ове метрике се стално сукобљавају једна са другом.
Дакле, имамо неколико супротстављених алгоритама и истовремено остаје још неколико претпоставки – да је време задатка познато и да задатак користи само ЦПУ.
Мешање са И/О
Пре свега, уклонимо претпоставку 4 да процес користи само ЦПУ; наравно, то није случај и процеси могу приступити другој опреми.
У тренутку када било који процес захтева И/О операцију, процес улази у блокирано стање, чекајући да се И/О заврши. Ако се И/О пошаље на чврсти диск, онда таква операција може потрајати до неколико мс или дуже, а процесор ће у овом тренутку бити неактиван. Током овог времена, планер може заузети процесор било којим другим процесом. Следећа одлука коју ће планер морати да донесе је када ће процес завршити свој И/О. Када се то догоди, доћи ће до прекида и ОС ће ставити процес који је позвао И/О у стање спремности.
Погледајмо пример неколико проблема. Сваки од њих захтева 50мс ЦПУ времена. Међутим, први ће приступити И/О сваких 10мс (који ће се такође извршавати сваких 10мс). А процес Б једноставно користи процесор од 50 мс без И/О.
У овом примеру користићемо СТЦФ планер. Како ће се понашати планер ако се на њему покрене процес попут А? Урадиће следеће: прво ће у потпуности разрадити процес А, а затим процес Б.
Традиционални приступ решавању овог проблема је да се сваки подзадатак од 10 мс процеса А третира као посебан задатак. Дакле, када се почне са СТЈФ алгоритмом, избор између задатка од 50 мс и задатка од 10 мс је очигледан. Затим, када је подзадатак А завршен, процес Б и И/О ће бити покренути. Након што се И/О заврши, биће уобичајено да се поново покрене процес А од 10мс уместо процеса Б. На овај начин је могуће имплементирати преклапање, где ЦПУ користи други процес док први чека на И/О. И као резултат, систем је боље искоришћен – у тренутку када интерактивни процеси чекају на И/О, други процеси се могу извршити на процесору.
Оракула више нема
Покушајмо сада да се ослободимо претпоставке да је време извршавања задатка познато. Ово је генерално најгора и најнереалнија претпоставка на целој листи. У ствари, у просечном обичном ОС-у, сам ОС обично зна врло мало о времену извршавања задатака, па како онда можете да направите планер, а да не знате колико дуго ће задатку бити потребно да се изврши? Можда бисмо могли користити неке РР принципе да решимо овај проблем?
Укупан
Погледали смо основне идеје планирања задатака и погледали 2 породице планера. Први први започиње најкраћи задатак и тиме повећава време преокрета, док се други подједнако раскида између свих задатака, повећавајући време одговора. Оба алгоритма су лоша тамо где су алгоритми друге породице добри. Такође смо погледали како паралелна употреба ЦПУ-а и И/О-а може побољшати перформансе, али нисмо решили проблем са видовитошћу ОС-а. А у следећој лекцији ћемо погледати планер који гледа у непосредну прошлост и покушава да предвиди будућност. И то се зове ред за повратне информације на више нивоа.
Извор: ввв.хабр.цом