Процеси

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

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

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

На Слици 3.1. је илустровано псеудопаралелно извршавање четири процеса на једном процесору. Временски интервали које процеси добијају за извршавање не морају бити једнаки и одређује их оперативни систем.

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

Задатак оперативних система је да обезбеде ефикасне механизме за:

• креирање и брисање процеса;

• управљање процесима;

• комуникација између процеса;

• синхронизацију процеса.

Процес у меморији

Док је програм пасиван и описује секвенцу инструкција које треба извршити, процес је активан и извршава се, корак по корак, по алгоритму који је имплементиран у програму. Програмски бројач за сваки процес води рачуна о томе докле се стигло са извршавањем. Инструкције се налазе у меморији заједно са осталим подацима који су потребни процесу за извршавање. Део меморије намењен за извршавање процеса се може организовати на различите начине, а најчешће је приказан у даљем тексту.

По покретању и учитавању у меморију програми, односно тада већ процеси, обично располажу са 4 дела меморије, који се називају сегменти:

• Стек сегмент;

• Хип сегмент;

• Сегмент података;

• Код сегмент.

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

Стања процеса

Процеси се налазе у једном од следећих стања.

• Нови – процес је управо креиран, оперативни систем је направио документацију која се односи на њега и он прелази у спремно стање.

• Спреман – просес чека да оперативни систем донесе одлуку да му буде додељен процесор.

• Извршавање – процес се извршава на процесору.

• Чекање – процес се извршавао али је за његов даљи рад потребан неки ресурс који није слободан тако да он чека да се створе услови да би могао да настави са радом.

• Завршен – процес је завршио са извршавањем и требало би га избацити из система.

Имамо четири преласка између различитих стања.

1. Процес прелази из стања Спреман у стање Извршавање када се процесор ослободи а оперативни систем, по неком критеријуму, изабере њега из листе спремних процеса и додели му процесор.

2. Процесор прелази из стања Извршавање у стање Чекање у тренутку када су му за даље извршавање потребни ресурси који тренутно нису доступни. На пример, ако жели да одштампа резултате, а штампач је у том тренутку заузет.

3. Процес прелази из стања Извршавање у стање Спреман када истекне време које му је унапред одређено приликом додељивања процесора или ако оперативни систем донесе одлуку да се процес прекине да би неки други процес дошао до процесора. Тада процес прелази у листу процеса који чекају на процесор.

4. Процес прелази из стања Чекање у стање Спреман, када дође до потребних ресурса и спреман је за даљи рад. Пошто се у том тренутку не зна да ли је процесор слободан, процес се ставља у листу спремних процеса а оперативном систему се препушта одлука када ће му дозволити да поново добије процесор.

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

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

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

Прекидање суспензије процеса које иницира корисник или оперативни систем реализује се његовим преласком из стања Суспендован и чека у стање Чекање и из стања Суспендован и спреман у стање Спреман.

Контролни блок процеса

Контролни блок процесора је део радне меморије у којој се налазе сви значајни подаци о процесу и у којој се чувају информације о сваком покренутом процесу. Захваљујући подацима који се чувају у контролном блоку, рад процеса се може прекидати и настављати више пута.

Контролни блок процеса садржи неке важне информације о процесима.

• Јединствени идентификатор процеса (Process ID – PID) – број који процес добија у тренутку покретања. Сви процеси имају различите PID-ове чиме је омогућено да их систем разликује на једноставан начин.

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

• Програмски бројач – чува информацију о следећој инструкцији коју процес треба да изврши.

• Садржај регистара процесора – вредности које се налазе у регистрима како би процес после губитка права да користи процесор могао да настави са радом тамо где је заустављен.

• Приоритет процеса – информација о важности процеса у односу на остале процесе у систему.

• Адреса меморије где се налази процес – показивачи на адресе у меморији где се налазе сегменти процеса.

• Адресе заузетих ресурса – како би оперативни систем имао информацију о томе на којим локацијама треба да тражи потребне податке.

Оперативни системи обезбеђују ефикасне механизме за манипулацију контролним блоковима процеса како би се брзо и ефикасно реализовали наведени задаци процеса.

• Креирање новог процеса (креирањем PCB-a);

• Уништавање процеса (брисањем PCB-а из листе);

• Мењање стања процеса;

• Мењање приоритета процеса;

• Избор процесора за извршавање (додела процесора неком процесу, context switch);

• Синхронизација процеса;

• Комуникација процеса.

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

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

• Почетни ред у који се смештају процеси по покретању назива се ред послова и он садржи скуп свих процеса у систему.

• Ред спремних процеса садржи процесе који су изабрани по неком критеријуму који је одређен на нивоу оперативног система. Процеси у овом реду су спремни за извршавање и смештени су у главној меморији. Избор процеса који ће ући у ред спремних зависи од процене да ли ће у току свог извршавања више користити процесор или ће више времена проводити у раду са улазно-излазним уређајима, јер је пожељно да се направи добра селекција процеса како би систем био продуктивнији.

• Оперативни системи воде рачуна и о редовима процеса који чекају на неке од уређаја. Процеси који се налазе у овим редовима су у стању чекања.

Планери

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

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

• Краткорочни пранери имају задатак да доносе одлуке о томе који ће се од спремних процеса извршавати.

• Средњорочни планери – у неким ситуацијама је корисније уклонити неке од процеса из меморије него форсирати виши степен мултипрограмирања. После извесног времена, када се стекну одређени услови, уклоњени процеси се могу поново вратити у меморију. Ова шема се назива пребацивање, и за задатке овог типа имплементира се посебан планер који се назива средњорочни.

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

Диспечер је изабран од стране краткорочног планера.

Нити

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

На почетку извршавања сваки процес добија свој меморијски простор и контролну нит. Њен задатак је да обави потребне иницијализације и креира остале нити које су потребне за ивршавање процеса.

Употреба нити може се илустровати на примеру веб прегледача. Могу се имплементрати тако да користе бар три нити. Једна нит служи за приказивање хипертекста у оквиру прозора, друга учитава податке са неког сервера, трећа преузима податке преко мреже (Слика 3.5.2.).

Коришћење нити доноси многе предности као што су:

• брже време одзива;

• дељење ресурса;

• економичност;

• боље искоришћење вишепроцесорске архитектуре – више нити се може извршавати истовремено.

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

Најзначајније врсте нити су: POSIX Pthreads, Mach C-threads i Solaris UI-threads. Нити језгра директно подржава оперативни систем. Конкретно, језгро извршава операције стварања нити, распоређивања нити и управљања нитима у простору језгра. Примери: Windows 95/98/NT/2000, Solaris, Tru64 UNIX, BeOS, Linux.

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

• пресликавање више у једну;

• пресликавање једна у једну;

• пресликавање више у више.

Пресликавање више нити у једну (many-to-one) подразумева да се више корисничких нити мапира у једну нит језгра (Слика 3.5.3.). Управљање нитима се одвија на корисничком нивоу и може бити ефикасно, али има недостатке. Ако нека од нити обави било који блокирајући системски позив, блокираће се цео процес, то јест све његове нити. С обзиром на то да само једна нит може приступити језгру у једном тренутку, у режиму језгра неће моћи да се искористи вишепроцесорска архитектура. Овај модел користи оперативни систем Solaris и библиотеку Green threads.

Пресликавање једна у једну (one-to-one) подразумева да се свака корисничка нит мапира у једну нит језгра (Слика 3.5.4.). Овај модел обезбеђује много боље конкурентно извршавање нити, дозвољавајући да друге нити наставе активности у случају када једна нит обави блокирајући системски позив. Такође се омогућава да се више нити језгра извршавају паралелно на вишепроцесорској архитектури. Како се много времена губи при стварању и одржавању нити језгра, многи оперативни системи ограничавају максималан број нити језгра. Овај модел је карактеристичан за оперативне системе Windows NT, Windows 2000/XP/2003 и OS/2.

Пресликавање више у више (many-to-many) је комбинација претходна два приступа јер подразумева да се више корисничких нити мапира у мањи или исти број нити језгра, при чему мапирање зависи од оперативног система а нарочито од броја процесора (Слика 3.5.5). Ово је најкомплекснији и најквалитетнији модел јер може да се прилагоди и апликацији и процесорском окружењу. Овај модел заступљен је у системима Solaris-2, IRIX, HP-UX и True64 UNIX.

Вишепроцесорски системи

Вишепроцесорски системи дозвољавају већу флексибилност када је у питању рад са нитима и процесима.

Планери оперативних система који подржавају само процесе и извршавају се на системима са једним процесором имају задатак да изаберу процесе који ће се извршавати и да при томе одреде трајање њихових активности на процесору.

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

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

Савремени рачунари углавном имају процесоре са више језгара, а постоје и они који имају и више независних процесора. Вишепроцесорски системи су ефикаснији, али захтевају комплексније алгоритме распоређивања. Постоје две методе распоређивања.

1. Симетрично мултипроцесирање – подразумева се да су сви процесори равноправни и да се процеси распоређују на било који од њих у зависности од примљеног алгоритма за распоређивање. Овде сви процесори деле заједничку меморију, сви имају приступ улазно-излазним уређајима и оператвни систем их третира равноправно;

2. Асиметрично мултипроцесирање – подразумева се да неки процесори могу бити задужени за одређене функције. Може се прогласити један процесор главним и њему се може поверити извршавање кода језгра оперативног система, тада остали процесори имају задатак да извршавају само корисничке процесе који су им додељени од стране главног процесора. Овај приступ је углавном неефикасан због спорих операција.

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

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

Балансирање оптерећења је поступак којим се тежи да се што равномерније поделе послови између процесора. То се може вршити на два начина.

1. Преношење миграције – подразумева да се из реда процеса оптерећеног процесора неки од процеса пошаљу у редове беспослених или мање заузетих процесора;

2. Преузимање миграције – подразумева се да ред слободнијег процесора преузме процесе из редова оптерећенијих процесора.

Балансирање оптерећења обично доводи до тога да се процес да се у целости не изврши на једном процесору и тиме се повећава временска сложеност извршавања. Из тог разлога се процесу може доделити афинитет ка одређеном процесору. Афинитет према процесору може бити:

• јак – подразумева да оперативни систем допушта да се процесу прецизно одреди подскуп процесора на коме може да се извршава и

• слаб – подразумева да оперативни систем омогућава, али и не гарантује да ће процес наставити извршавање на истом процесору.

Квалитет алгоритама распоређивања се оцењује на основу следећих критеријума:

• искоришћеност процесора – проценат колико је процесор био запослен у одређеном временском периоду;

• пропусна моћ – број процеса који се могу завршити у јединици времена;

• време обраде – време које протекне од момента покретања процеса до његовог завршетка;

• време чекања – укупно време које процес проведе чекајући у реду спремних процеса;

• време одзива – време које протекне од пријављивања процеса до тренутка када се произведе први излаз програма;

• количник дужине времена обраде и трајања извршавања процеса;

Добро решење ће одликовати:

• максимална искоришћеност процесора;

• максимална пропусна моћ;

• минимално време обраде;

• минимално време чекања;

• минимално време одзива;

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

Алгоритми планирања

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

FCFS алгоритам

Основна идеја FCFS (First Come, First Served) алгоритама је да се процесор додељује процесима оним редом којим су пристизали у ред чекања. Ред чекања функционише по стандардном FIFO (First in, First Out) принципу. Процес који је ушао у ред чекања на процесор се поставља на крај реда. У тренутку када се процесор ослободи, тада процес који је на почетку реда добија право да користи процесор и избацује се из реда. FCFS алгоритам не дозвољава прекидање процеса.

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

SPF алгоритам

SPF (Shortest Process First) алгоритам предност даје процесима чији је следећи захтев за процесорским временом мањи. Код овог алгоритма сваки процес има своје очекивано време за следеће извршавање на процесору. Процесор се додељује редом процесима чије је очекивано време мање. Уколико је очекивано време за два процеса исто, FCFS алгоритам одлучује који се процес први извршава.

SPF алгоритам се може имплементирати у верзијама које дозвољавају и које не дозвољавају прекидање процеса који се извршавају на процесору. У верзији која дозвољава прекидање процеса, уколико је време потребно за извршавање новог процеса краће од времена потребног за завршетак активности текућег процеса, процесор ће бити додељен новом процесу.

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

Дужина трајања следеће активности просеца се може апроксимирати следећим изразом: \( \tau_{n+1} = \alpha t_n + (1-\alpha) \tau_n, 0\leq \alpha \leq1\)

При чему је \(t_n \) време које је потребно да се изврши n–та активност процеса на процесору, а \( \tau \) очекивано време које је било предвиђено за извршавање n–те активности процеса на процесору. Параметар \(\alpha\) управља релативним тежинама недавне и давне прошлости у предвиђању. Ако је \(\alpha=0\), тада је \(\tau_{n+1}=\tau_n\), и недавна прошлост нема ефекта. За вредност параметра \(\alpha=1\), \(\tau_{n+1}= \alpha\tau_n\) па је само најскорија активност процесора од важности.

Алгоритам са приоритетима

Код алгоритма са приоритетима, сваком процесу се додељује приоритет, после чега алгоритам бира процес са највећим приоритетом. Ако два процеса имају исти приоритет, бира се онај који је први дошао у систем. SPF алгоритам је специјалан случај алгоритма са приоритетима где је приоритет обрнуто пропорционалан очекиваном времену извршавања процеса. Тиме се постиже да краћи процеси добијају виши приоритет у односу на дуже. FCFS алгоритам је специјални случај алгоритма са приоритетима јер се време доласка у систем може узети као приоритет при рангирању процеса.

Приоритети се могу дефинисати интерно или екстерно. Интерно дефинисани приоритети користе неку мерљиву величину за израчунавање приоритета процеса. Мерљиве величине могу бити: временске границе, меморијски захтеви, просечно трајање активности на процесору, просечно трајање улазно-излазних операција и број отворених фајлова. На пример, процеси који су више оријентисани ка улазно-излазним операцијама би требао да имају већи приоритет јер њима треба мање процесорског времена, а често блокирани чекају на неки уређај. Екстерно дефинисани критеријуми се намећу на основу критеријума који су спољашњи у односу на оперативни систем а то су: временски рокови, важност клијента и важност пројекта.

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

За алгоритам са приоритетом постоји верзија са и без прекидања. Ако је прекидање дозвољено, и у систему се појави нови процес вишег приоритета од процеса који се у том тренутку извршава, тренутни процес се прекине а процес вишег приоритета почне да се извршава.

Кружни алгоритам

Кружни алгоритам (Round Robin) се заснива на идеји да сваки процес има унапред задати временски интервал коришћења процесора. Тај временски интервал се назива квантум времена(time quantum). Када то време истекне или ако се процес изврши до краја, процес се прекида а процесор добија следећи процес (на квантум врeмена) из реда спремних процеса. У ситуацијама када се процес прекине, а није се извршио до краја, ставља се на крај реда спремних процеса. Кружни алгоритам је фер према процесима јер сви процеси добијају процесор на коришћење, равномерно и равноправно. Ако има n спремних процеса, а временски квантум је дужине q, онда сваки процес добија најмање \(1 \over n\) процесорског времена, највише по q у једном пролазу. При томе, ниједан процес не чека више од \((n-1)q\) процесорског времена.

Успешност употребе овог алгоритма зависи од квантума времена. Уколико је тај квантум времена тежи бесконачности, овај алгоритам се понаша као FCFS алгоритам. Уколико је временски квантум веома мали, кружни алгоритам се назива дељење процесора и изгледа као да сваки од n процеса у реду има сопствени процесор који је n пута спорији од процесора који се налази у систему.

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

Редови у више нивоа

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

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

Планирање крајњег рока

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

Алгоритам за планирање монотоном стопом

Алгоритам за планирање монотоном стопом користи фиксиран приоритет за сваки од процеса базиран на његовом периоду извршавања. Највиши приоритет има процес са најкраћим периодом. Прекида се сваки процес извршавањем процеса са вишим приоритетом.

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

EDF (Earliest Deadline First) алгоритам

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

Теоретски је супериоран у односу на алгоритам за планирање са монотоном стопом и гарантује распоређивање за оптерећење процесора од 100% и мање.

Мане овог алгоритма су: сложенија имплементација, понашање преоптерећеног система је непредвидиво, не гарантује се да ће процеси вишег приоритета бити извршени пре крајњег рока.

LLFT (Least Laxity Time First) алгоритам

Овај алгоритам користи динамичко додељивање приоритета. Највиши приоритет иде најмање релаксираном процесу, при чему се релаксираност процеса L мери са \(L = T_d – T_{re}\), где је \(T_d\) тренутак истека крајњег рока, а \(T_{re}\) преостало време потребно да би се процес завршио. За разлику од прошлог алгоритма, узима у обзир и крајњи рок и преостало време потребно да се процес заврши.

MLLF (Modified Least Laxity First) алгоритам

LLF алгоритам није практичан за имплементацију јер у ситуацијама када постоји „једнака релаксираност” два или више процеса води ка честим заменама контекста и знатном опадању перформанси система.

МLLF алгоритам решава овај тако што смањује број замена контекста. У тренутку када се изједначе релаксираности два или више процеса, процес који се тренутно извршава наставља да се извршава све док није угрожен крајњи рок осталих процеса. На овај начин МLLF одлаже замену контекста све док то није неопходно и потпуно је безбедан чак и у ситуацијама када настане „једнака релаксираност” процеса.

Овај алгоритам дозвољава инверзију релаксираности, при којој процес са најмањом релаксираношћу не мора тренутно бити одабран за извршавање.