Распоређивање (рачунарство)

У информатици, распоређивање је метод по ком се нитима, процесима или токовима података даје приступ системским ресурсима (нпр. процесорском времену, опсегу комуникација). Ово се углавном ради у сврху ефективног балансирања оптерећењем на систему или постизања циљаног квалитета услуге. Потреба за алгоритмима распоређивања је произашла из потребе веђине модерних система да изводе више послова истовремено (више процеса истовремено) и мултиплексирање (одашиљу вишеструке токове истовремено).

Распоређивач углавном манипулише:

• Проток - Укупан број процеса који завршавају своје извршавање у јединици времена.
• Кашњење, специфично:
  • Време окрета - укупно време између издавања процеса и његовог завршетка.
  • Време одзива - време које је потребно од слања захтева до првог одговора.
• Правичност / Време чекања - Једнако процесорско време сваком процесу (или општије прикладна времена у односу на приоритет процеса). Време током кога је процес у реду чекања.

У пракци, ови циљеви су често у конфликту (нпр. проток и кашњење), стога ће распоређивач имплементирати прикладни компромис.

Предност се даје било којој од горенаведених ставки на основу потреба и жеље корисника.

Код окружења у реалном времену, као што су уграђени системи за аутоматску контролу у индустрији (нпр. роботика), распоређивач такође мора да осигура да процеси испуне временски рок ; ово је пресудно у циљу одржања система стабилним. Распоређени задаци се шаљу мобилним уређајима и контролишу кроз административни панел.

Типови распоређивача оперативних система

Оперативни системи могу имати и до три различита типа распоређивача, дуготрајни распоређивач (познат и као распоређивач високог нивоа), средњорочни распоређивач и краткорочни распоређивач. Ова имена сугеришу релативну учесталост са којом се ове функције изводе.

Распоређивач је модул оперативног система који бира који ће следећи посао бити предат систему и следећи процес за обраду.

Распоређивач процеса

Дугорочно распоређивање

Дугорочни, или пријемни распоређивач, одлучује који ће се послови или процеси прихватити у ред спремних (у главној меморији); то значи, при покушају извршења програма, његов пријем у скуп тренутно извршних процеса је или ауторизован или одложен од стране дугорочног распоређивача. Стога, овај распоређивач диктира који процеси ће се извршавати на систему, и степен конкурентности који ће бити подржан у било ком тренутку - нпр: која количина процеса ће се извршавати истовремено, и како ће се руковати односом улазно/излазних и процесорски интензивних процеса. Дугорочни распоређивач је одговоран за контролу степена мултипрограмирања. Код модерних оперативних система, ово се користи као осигурање да процеси у реалном времену добијају довољно процесорског времена да заврше свој задатак. Без доброг распоређивача у реалном времену, модерни графички кориснички интерфејси би изгледали тромо.

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

Средњорочно распоређивање

Распоређивач привремено уклања процесе из главне меморије и смешта их на секундарну меморију (као што је диск) и обрнуто. Ово се често назива сваповање (такође и непгравилно "страничење"). Краткорочни распоређивач може одлучити да замени процес који није активан неко време, или процес ниског приоритета, или процес који често промашује странице, или процес који заузима превише меморије да би ослободио главну меморију за друге процесе, и да га врати касније када меморија буде доступна, или када се процес одблокира и више не чека на ресурс.

У пуно данашњих система (који подржавају мапирање виртуелног адресног простора на секундарно складиште осим свап фајла), срењорочни распоређивач може практично да преузме улогу дугорочног распоређивача, третирајући бинарне датотеке као "сваповане процесе" по њиховом извршењу. На овај начин, када се захтева сегмент бинарне датотеке он може бити одсвапован на захтев, или "лењо учитан“.

Краткорочни распоређивач

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

Превентивни распоређивач се ослања на програмабилни часовник који позива опслуживач прекида који ради у кернел режиму и имплементира распоређивачку функцију.

Диспечер

Друга компонента која је укључена у функцију процесорског распоређивања је диспечер. То је модул који даје контролу процесора процесу изабраном од стране краткорочног распоређивача. Ова функција укључује:

• Замену контекста
• Пребацивање у кориснички режим
• Скок на исправну локацију у корисничком програму ради рестарта програма.

Диспечер анализира вредности из програмског бројача и дохвата инструкције, учитава податке у регистре.

Диспечер би требало буде што бржи, с обзиром да се позива током сваке смене процеса. Током смене контекста, процесор је незаузет у делићу времена. Стога, непотребне смене контекста треба избегавати. Време које је потребно диспечеру да заустави један процес и започне други је познато као диспечерско кашњење. [Galvin, 155].

Мрежни распоређивач

Главни чланак: Мрежни распоређивач

Распоређивач диска

Главни чланак: I/O распоређивање

Распоређивач послова

Главни чланак: Распоређивач послова

Примери су cron, at, systemd.

Распоређивачке дисциплине

Распоређивачке дисциплине су алгоритми коришћени за дистрибуцију ресурса међу странкама које их симултано и асинхроно траже. Распоређивачке дисциплине се користе код рутера (рукују саобрађајем пакета) као и код оперативних система (да дели процесорско време и међу нитима и међу процесима), диск уређаја (улазно/излазно распоређивање), штампача, већине уграђених система, итд.

Главна сврха распоређивачких алгоритама је да се минимизује изгладњивање ресурса и да се осигура правичност међу странкама које користе ресурсе. Распоређивање се бави проблемом одлуке који од пристиглих захтева ће добити ресурсе. Постоји пуно различитих алгоритама распоређивања. У овој секцији представљамо неколико.

Код рачунарских мрежа са пакетним преносом и другим статистичким мултиплексирањем, нотација распоређивачког алгоритма се кориси као алтернатива за први-дошао први-услужен ређање пакета података.

Најједноставнији најбоље-могуђе распоређивачки алгоритми су кружно опслуживање, правично ређање (алгоритам max-min правичности), распоређивање пропорционалне правичности и максимална пропусност. Уколико је понуђен диференцирани или гарантовани квалитет услуге, супротно најбоље-могуће комуникацији, може се користити ређање процењене правичности.

Код напредних пакетних бежичних радио мрежа као што је HSDPA (High-Speed Downlink Packet Access ) 3.5G систем, канал-зависно распоређивање може бити коришћено да искористи предност информације о стању канала. Ако су услови канала добри, пропусност и спектрална ефикасност система могу бити повећане. Код још напреднијих система као што је LTE, распоређивање се комбинује канал-зависном пакет-по-пакет динамичком алокацијом канала, или додељивањем OFDMA вишеструких-оператера или других компоненти равнања фреквентних домена корисницима који их најбоље могу искористити.

Први дошао први изашао

Такође познато и као First­ Come, First ­Served (FCFS), је најједноставнији алгоритам распоређивања, FIFO једноставно ређа процесе по реду доласка у ред.

• С обзиром да се смене контекста дешавају само по завршетку процеса, и није потребна реорганизација реда процеса, губитак при распоређивању је минималан.
• Пропустност може бити ниска, с обзиром да дугачки процеси могу задржавати процесор
• Време окрета, време чекања и време одзива могу бити високи из истих разлога
• Нема приоретизације, стога овај систем има проблема са временским роковима.
• Недостатак приоретизације значи да док год се сваки процес евентуално завршава, нема изгладњивања. У окружењу где се неки процеси не завршавају, има изгладњивања.
• Базирано је на реду
• Ово је C-код за FCFS

Најкраће преостало време

Слично са Shortest­ Job­ First (SJF). Са овом стратегијом распоређивач ређа процесе по најмањем процењеном процесном времену које ће бити следеће у реду. Ово захтева напредно познавање или прогнозу о времену потребном да се процес заврши.

• Ако краћи процес наиђе током извршења другог процеса, тренутни процес може бити превентивно прекинут, дељењем тог процеса у два раздвојена рачунарска блока. Ово ствара губитке услед додатне замене контекста. Распоређивач такође мора ставити сваки надолазећи процес у специфично место у реду, што ствара додатне губитке.
• Овај алгоритам је дизајниран за максималну пропусност у већини случајева.
• Време чекања и одзива се повећавају заједно са рачунарским захтевима процеса. С обзриом да је време окрета базирано на збиру времена чекања и извршења, дугачки процеси су значајно погођени овим. Укупно време чекања ја мање него код FIFO, јер ниједан процес не мора да чека завршетак најдужег процеса.
• Роковима се не даје посебна пажња, програмер може само покушати да програме са роковима учини што краћим.
• Излгадњивање је могуће, поготово у заузетом систему са пуно малих процеса.
• Овај концепт се више не користи.
• За овај концепт су нам потребна бар два процеса различитих приоритета

Превентивно распоређивање фиксног приоритета

OS додељује фиксан приоритет сваком процесу, и распоређивач распоређује процесе у реду спремних по нивоу приоритета. Процеси нижег приоритета бивају прекинути при надоласку процеса вишег приоритета.

• Губици нису минимални, али нису ни значајни.
• FPPS нема посену предност у смислу пропустности у односу на FIFO.
• Ако је број нивоа приоритета ограничен, може се окарактерисати као колекција FIFO редова, један за сваки ниво. Процеси у редовима нижег приоритета су изабрани само када су редови вишег приоритета празни.
• Време чекања и одзива зависи од приоритета процеса. Процеси вишег приоритета имају мања времена.
• Рокови се могу постићи давањем процесима са роковима виши приоритет.
• Изгладњивање процеса нижег приоритета је могућност код великог броја високоприоритетних процеса.

Кружно распоређивање

Распоређивач додељује фиксну јединицу времена по процесу, и само пролази кроз њих.

• Кружно распоређивање укључује велике губитке, посебно код мале јединице времена.
• Балансирана пропустност између FCFS и SJF, краћи послови се завршавају брже него код FCFS а дужи процеси брже него код SJF.
• Слабо просечно време одзива, време чекања је зависно од броја процеса, а не просечне дужине процеса.
• Због дугачких времена чекања, рокови се тешко достижу код овог система.
• Изгладњивање не постоји, с обзиром да нема приоритета. Временска јединица се одређује на основу брзине пристизања процеса, слично као код FCFS.

Редно распоређивање на више нивоа

Ово се користи у ситуацијама код којих се процеси лако деле у различите групе. На пример, честа расподела се прави између предњих (интерактивних) процеса и позадинских (серијских) процеса. Ова два типа процеса имају различите захтеве за време одзива и самим тиме и различите захтеве по питању распоређивања. Корисно је за проблеме дељене меморије.

Проблеми оптимизације распоређивања

• Open-shop scheduling
• Job Shop Scheduling
• Flow Shop Scheduling Problem

Ручно распоређивање

Чест метод код уграђених система је ручно распоређивање послова. Ово се може постићи мултиплексирањем времена. Понекад је кернел подељен у три или више делова: ручно распоређивање, превентивни и прекидни ниво. Прецизни методи за распоређивање су углавном затвореног кода.

• Нема проблема изладњивања.
• Велика предвидљивост; омогућује имплементацију система у реалном времену.
• Скоро потпуно без губитака.
• Није оптимално за све апликације.
• Ефективност потпуно зависи од имплементације.

Како изабрати алгоритам распоређивања

При дизајнирању оперативног система, програмер мора узети у обзир који алгоритам распоређивања ће се најбоље понашати за сврху система. Не постоји универзално “најбољи” алгоритам распоређивања, и пуно оперативних система користе проширене или комбинације горњих алгоритама распоређивања. На пример, Windows NT/XP/Vista користи ред у више нивоа са повратном спрегом, комбинацију превентивног распоређивања са фиксним приоритетима, кружне расподеле, и први дошао први услужен.

Код овог система, нитима се динамички може мењати приоритет у зависности од тога да ли је већ услужена, или да ли је предуго чекала. Сваки ниво приоритета има свој ред, са кружним распоређивањем међу високоприоритетним нитима и FIFO међу нископриоритетним. У овом смислу, време одзива је мало за већину нити, а кратке и критичне системске нити се завршавају јако брзо. С обзиром да нити могу користити само по једну јединицу времена кружне расподеле у реду највишег приоритета, изгладњивање може бити проблем за дуже високоприоритетне процесе.

Имеплемтације распоређивача процеса код оперативних система

Алгоритам може бити једноставан као кружна расподела које које сваки процес добија јединицу времена (на пример 1 ms, углавном између 1 ms и 100 ms) у цикличној листи. Тако да, процес A се извршава 1 ms, затим процес B, затим C, и на крају опет A.

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

Windows

Први MS-DOS и Microsoft Windows системи нису могли обављати више операција истовремено, и као такви нису имали распоређивач. Windows 3.1x је користио непревентивни распоређивач, што значи да није прекидао програме. Ослањао се на сам програм да се заврши или каже систему да му не треба процесор те може прећи на следећи процес. Ово се углавном зове кооперативно обављање више задатака истовремено. Windows 95 је представио основни превентивни распоређивач; међутим, због компатибилности је дозвољено 16-битним апликацијама да раде без превентивних прекида.

Windows NT-базирани оперативни системи користе систем редова у више нивоа са повратном спрегом. 32 нивоа приоритета су дефинисана, од 0 до 31, где су приоритети од 0 до 15 "нормални" а приоритети од 16 до 31 приоритети у скоро реалном времену, који захтевају доделу привилегија. 0 је резервисана за оперативни систем. Корисници могу изабрати 5 од ових приоритета за доделу апликацијама из Task Manager апликације, или кроз API-је за управљање нитима. Кернел може променити ниво приоритета нити у зависности од њене употребе улаза/излаза и процесора и да ли је интерактивна (нпр. прихвата и одговара на упит човека), дижући приоритет за интерактивне и улазно/излазне процесе а спуштајући за процесорски захтевне процесе, ради повеђања одзива интерактивних апликација. Распоређивач је модификован у Windows Vista да користи регистре бројача циклуса модерних процесора и прати тачно колико циклуса нит извршава, радије него да користи само прекид на основу временских интервала. Vista такође користи приоритетни распоређивач за улаз/излаз тако да се диск дефрагментери и други слични програми не мешају са главним апликацијама.

Mac OS

Mac OS 9 користи кооперативни распоређивач за нити, где један процес контролише вишеструке кооперативне нити, и такође обезбеђује превентивно распоређивање за MP задатке. Кернел распоређује MP задатке коришћењем превентивног алогритма. Сви Process Manager процеси раде у оквиру посебног MP задатка, званог "плави задатак“. Ти процеси се распоређују кооперативно, коришћењем кружног распоређивања; процес добровољно предају контролу над процесором другом процесу позивајући функцију као што је WaitNextEvent. Сваки процес има своју копију управљача нитима који распоређује нити тог процеса кооперативно; нит предаје контролу другој нити позивом YieldToAnyThread или YieldToThread.

Mac OS X користи ред у више нивоа са повратном спрегом, са четири нивоа приоритета за нити - нормални, системски висок приоритет, само кернелски режим, и реално време. Нити се распоређују превентивно; Mac OS X такође подржава кооперативно распоређиване нити у својој имплементацији управљача нитима у Carbon-у.

AIX

У AIX верзији 4 има три могуће вредности за полису распоређивања нити:

• Први унутра први напоље: Када се распореди нит са овом полисом, она ради до краја осим ако није блокирана, самовољно даје контролу над процесором, или нит вишег приоритета постане спремна. Само нити фиксног приоритета могу имати FIFO распоређивачку политику.
• Кружно распоређивање: Ово је слично AIX верзији 3 шеми кружног распоређивача базираног на делићима времена од 10ms. Када кружна нит има контролу при крају временског одсечка, она се помера на крај реда спремних нити свог приоритета. Само нити фиксног приоритета могу имати кружно распоређивање.
• Остало: Ова полиса је дефинисана POSIX1003.4a стандардом као имплементационо дефинисана. У AIX верзији 4, ова полиса је дефинисана као еквивалентна кружном распоређивању, осим што се односи на нити без фиксног приоритета. Прорачун приоритета покренуте нити при сваком такту значи да нит може изгубити контролу јер јој је приоритет постао виши од друге спремне нити. Ово је понашање AIX верзије 3.

Нити су примарни интерес апликација које конкурентно извршавају више асинхроних процеса. Ове апликације могу бити лакше за систем ако се пребаце у вишенитну структуру.

AIX 5 имплементира следеће распоређивачке политике: FIFO, кружно распоређивање, и правично кружно. FIFO политика има три различите имплементације: FIFO, FIFO2, и FIFO3. Кружна политика је названа SCHED_RR код AIX, а правична кружна SCHED_OTHER. Овај линк обезбеђује додатне инфорамције о AIX 5 распоређивању: http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html#N100F6 .

Linux

Linux 2.4

Код Линукса 2.4, O(n) распоређивач са редом у више нивоа и повратном спрегом је коришћен са приоритетима од 0-140. 0-99 су резервисани за задатке у реалном времену, а 100-140 се сматрају финим нивоима. За задатке у реалном времену, време смене процеса је било око 200 ms, а за фине задатке око 10 ms. Распоређивач је пролазио кроз ред свих спремних процеса, пуштајући процесе највишег приоритета прве, након чега се стављају у ред истеклих. Када се активни ред испразни, истекли ред постаје активни и обрнуто.

Међутим, неке Enterprise Дистрибуција Линукса као што је SUSE Linux Enterprise Server су замениле овај распоређивач са O(1) распоређивачем (који је одржавао Alan Cox у својој Linux 2.4-ac Kernel серији) у Linux 2.4 кернелу који су користили.

Linux 2.6.0 до Linux 2.6.22

Од верзије 2.6 до 2.6.22, кернел је користио O(1) распоређивач развијен од стране Ingo Molnar и других програмера кернела током развоја Linux-а 2.5. За доста кернела тог времена, Con Kolivas је развио скуп исправки које су побољшавале интерактивност са овим распоређивачем или га чак мењале његовим личним.

Од Linux-а 2.6.23

Рад Conа Kolivasа, поготово његова имплементација правичног распоређивања звана "Рок ротирајућих степеница", инспирисала је Ingоа Molnárа да развије потпуно правични распоређивач као замену за претходни O(1) распоређивач, помињући Kolivasа у својој најави.

Потпуно правични распоређивач (CFS) користи добро проучени класични распоређивачки алгоритам зван правично ређање првобитно направљен за мреже пакетног преноса. Правично распоређивање је претходно примењивано на процесорско распоређивање под називом распоређивање у корацима.

Потпуно правични распоређивач има сложеност од O(log N), где је N број задатака у реду спремних. Одабир задатка се може урадити у константном времену, али врађање задатка након његовог извршења захтева O(log N) операција, јер је ред спремних имеплемтниран као црвено-црно стабло.

CFS је прва имлементација правичног ређања популарно коришћена у опште наменским оперативним системима.

Brain Fuck распоређивач (BFS) је алтернатива CFS-у.

FreeBSD

FreeBSD користи ред у више нивоа са повратном спрегом са приоритетима од 0-255. 0-63 су резервисани за прекиде, 64-127 су за горњу половину кернела, 128-159 су за корисничке нити у реалном времену, 160-223 су за временски дељене корисничке нити, а 224-255 су за беспослене корисничке нити. Такође, као и Линукс, користи активни ред, али има и ред беспослених.

NetBSD

NetBSD користи ред у више нивоа са повратном спрегом са приоритетима од 0-223. 0-63 су резервисани за временски дељене нити (default, SCHED_OTHER политика), 64-95 су за корисничке нити у кернелском простору, 96-128 за кернелске нити, 128-191 су за корисничке нити у реалном времену (SCHED_FIFO и SCHED_RR политика), и 192-223 за софтверске прекиде.

Solaris

Solaris користи ред у више нивоа са повратном спрегом са приоритетима од 0-169. 0-59 су резервисани за временски дељене нити, 60-99 за системске нити, 100-159 за нити у реалном времену, и 160-169 за прекиде ниског приоритета. За разлику од Линукса, када процесор заврши са својим делом времена, даје му се нови приоритет и врађа у ред.

Преглед

Оперативни систем	Превентивно	Алгоритам
Amiga OS	Да	Приоретски кружан
FreeBSD	Да	Ред у више нивоа са повратном спрегом
Линукс pre-2.6	Да	Ред у више нивоа са повратном спрегом
Линукс 2.6-2.6.23	Да	O(1) распоређивач
Линукс post-2.6.23	Да	Потпуно правични распоређивач
Mac OS pre-9	Не	Кооперативни распоређивач
Mac OS 9	Делимично	Превентивни за MP задатке, кооперативни за процесе и нити
OS X	Да	Ред у више нивоа са повратном спрегом
NetBSD	Да	Ред у више нивоа са повратном спрегом
Solaris	Да	Ред у више нивоа са повратном спрегом
Windows 3.1x	Не	Кооперативни распоређивач
Windows 95, 98, Me	Делимично	Превентивно за 32-битне процесе, кооперативно за 16-битне процесе
Windows NT (укључујући 2000, XP, Vista, 7, и Server)	Да	Ред у више нивоа са повратном спрегом

Види још

• Процес (рачунарство)

Литература

• Błażewicz, Jacek; Ecker, K.H.; Pesch, E.; Schmidt, G.; Weglarz, J. (2001). Scheduling computer and manufacturing processes (2 изд.). Berlin [u.a.]: Springer. ISBN 978-3-540-41931-0. 
• Stallings, William (2004). Operating Systems Internals and Design Principles (fifth international edition). Prentice Hall. ISBN 978-0-13-147954-8. 
• Stallings, William (2004). Operating Systems Internals and Design Principles (fourth edition). Prentice Hall. ISBN 978-0-13-031999-9. 
• Information on the Linux 2.6 O(1)-scheduler
• Brief discussion of Job Scheduling algorithms
• Understanding the Linux Kernel: Chapter 10 Process Scheduling
• Kerneltrap: Linux kernel scheduler articles
• AIX CPU monitoring and tuning
• Josh Aas' introduction to the Linux 2.6.8.1 CPU scheduler implementation
• Peter Brucker, Sigrid Knust. Complexity results for scheduling problems [1]
• TORSCHE Scheduling Toolbox for Matlab is a toolbox of scheduling and graph algorithms.
• [2] A survey on cellular networks packet scheduling