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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примери су 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

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