У овом водичу ћемо научити важан концепт у алгоритмима за планирање процеса ЦПУ. Важан назив концепта је Фирст Цоме Фирст Серве. Ово је основни алгоритам који сваки ученик мора научити да би разумео све основе алгоритама за планирање процеса ЦПУ.
Фирст Цоме Фирст Серве отвара пут за разумевање других алгоритама. Овај алгоритам може имати много недостатака. Али ови недостаци су створили веома нове и ефикасне алгоритме. Дакле, наша је одговорност да научимо о алгоритмима планирања процеса први дође први служи.
Важне скраћенице
- ЦПУ - - - > Централна процесорска јединица
- ФЦФС - - - > Фирст Цоме Фирст Серве
- АТ - - - > Време доласка
- БТ - - - > Бурст Тиме
- ВТ - - - > Време чекања
- ТАТ - - - > Турн Ароунд Тиме
- ЦТ - - - > Време завршетка
- ФИФО - - - > Први ушао, први изашао
Први дође први послужи
Алгоритам планирања ЦПУ-а први дође први, кратко познат као ФЦФС је први алгоритам ЦПУ-овог алгоритма за планирање процеса. У алгоритму „први дође први послужи“ оно што радимо је да дозволимо да се процес извршава на линеарни начин.
То значи да који год процес уђе у процес који први уђе у ред спреман, први се извршава. Ово показује да алгоритам „први дође први сервира“ следи принцип „први дође први изађе“ (ФИФО).
Алгоритам Фирст Цоме Фирст Серве се може извршити на начин унапред и без превенције. Пре него што уђемо у примере, хајде да разумемо шта је приступ пре него што се искључује и шта је приступ у планирању ЦПУ процеса.
Превентивни приступ
У овом случају планирања процеса унапред, ОС додељује ресурсе процесу за унапред одређени временски период. Процес прелази из стања рада у стање спремности или из стања чекања у стање спремно током алокације ресурса. Ово пребацивање се дешава зато што ЦПУ може доделити другим процесима приоритет и заменити тренутно активни процес за процес вишег приоритета.
Приступ који није превентиван
У овом случају планирања процеса без превенције, ресурс се не може повући из процеса пре него што се процес заврши. Када се покренути процес заврши и пређе у стање чекања, ресурси се мењају.
Ефекат конвоја када први дође први служи (ФЦФС)
Ефект конвоја је феномен који се јавља у алгоритму планирања под називом Први дође први послужи (ФЦФС). Алгоритам заказивања „Први дође први послужи“ се јавља на начин који није превентиван.
Начин без превенције значи да ако се процес или посао започне са извршавањем, тада оперативни систем мора да заврши свој процес или посао. Све док процес или посао није нула, нови или следећи процес или посао не започне своје извршавање. Дефиниција планирања без превенције у смислу оперативног система значи да ће централна процесорска јединица (ЦПУ) бити потпуно посвећена до краја процеса или посла који је први започет, а нови процес или посао се извршава тек након завршетка старијег процеса или посао.
Можда постоји неколико случајева који могу довести до тога да централна процесорска јединица (ЦПУ) одвоји превише времена. То је зато што се у алгоритму планирања „први дође први послужи“ без превентивног приступа, процеси или послови се бирају серијским редоследом. Због тога је за краће послове или процесе иза већих процеса или послова потребно превише времена да се заврше. Због тога је време чекања, време заокрета, време завршетка веома високо.
Дакле, пошто је први процес велики или је време завршетка превисоко, онда се јавља овај ефекат конвоја у алгоритму први дође први послужи.
Претпоставимо да је за завршетак дужег посла потребно бесконачно време. Затим, преостали процеси морају да чекају исто бесконачно време. Због овог ефекта конвоја створеног Дужим послом, изгладњивање процеса чекања расте веома брзо. Ово је највећи недостатак ФЦФС планирања процеса ЦПУ.
Карактеристике планирања процеса ФЦФС ЦПУ
Карактеристике ФЦФС планирања ЦПУ процеса су:
- Имплементација је једноставна.
- Не изазива никакве узрочности током употребе
- Усваја непревентивну и превентивну стратегију.
- Покреће сваку процедуру редоследом којим су примљени.
- Време доласка се користи као критеријум избора за процедуре.
Предности планирања процеса ФЦФС ЦПУ
Предности ФЦФС планирања ЦПУ процеса су:
- Да би алоцирао процесе, користи ред „Први ушао, први изашао“.
- Процес планирања ФЦФС ЦПУ-а је једноставан и лак за имплементацију.
- У ФЦФС ситуацији са превентивним заказивањем, нема шансе да процес нестане.
- Пошто се не узима у обзир приоритет процеса, то је правичан алгоритам.
Недостаци планирања процеса ФЦФС ЦПУ
Недостаци ФЦФС планирања ЦПУ процеса су:
- Алгоритам за планирање ФЦФС ЦПУ-а има дуго време чекања
- ФЦФС ЦПУ планирање даје предност ЦПУ-у у односу на улазне или излазне операције
- У ФЦФС постоји шанса за појаву ефекта конвоја
- Пошто је ФЦФС тако директан, често није баш ефикасан. Продужени периоди чекања иду руку под руку са овим. Сви остали налози остају неактивни ако је ЦПУ заузет обрадом једног дуготрајног налога.
Проблеми у алгоритму планирања ЦПУ-а први дође први
Пример
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Приступ који није превентиван
Сада, хајде да решимо овај проблем уз помоћ алгоритма за планирање под називом Први дође први послужи у приступу без превенције.
Гантов дијаграм за горњи пример 1 је:
Време преокрета = Време завршетка - Време доласка
Време чекања = Време заокрета - Време рафала
Решење горњег питања Пример 1
| Да не | ИД процеса | Време доласка | Бурст Тиме | Време завршетка | Смањено | Време чекања | |
|---|---|---|---|---|---|---|---|
| 1 | П 1 | А | 0 | 9 | 9 | 9 | 0 |
| 2 | П 2 | Б | 1 | 3 | 12 | Једанаест | 8 |
| 3 | П 3 | Ц | 1 | 2 | 14 | 13 | Једанаест |
| 4 | П 4 | Д | 1 | 4 | 18 | 17 | 13 |
| 5 | П 5 | И | 2 | 3 | двадесет један | 19 | 16 |
| 6 | П 6 | Ф | 3 | 2 | 23 | двадесет | 18 |
Просечно време завршетка је:
Просечан ЦТ = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Просечан ЦТ = 97 / 6
Просечан ЦТ = 16,16667
конверзија датума у стринг
Просечно време чекања је:
Просечан ВТ = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Просечан ВТ = 66 / 6
Просечан ВТ = 11
Просечно време преокрета је:
Просечан ТАТ = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
Просечан ТАТ = 89 / 6
Просечан ТАТ = 14,83334
Овако је ФЦФС решен у приступу без превенције.
Сада, хајде да разумемо како се они могу решити у превентивном приступу
Превентивни приступ
Сада, хајде да решимо овај проблем уз помоћ алгоритма за планирање под називом Први дође први послужи у превентивном приступу.
У Преемптиве Аппроацх-у тражимо најбољи процес који је доступан
Гантов дијаграм за горњи пример 1 је:
| Да не | ИД процеса | Време доласка | Бурст Тиме | Време завршетка | Смањено | Време чекања | |
|---|---|---|---|---|---|---|---|
| 1 | П 1 | А | 0 | 9 | 23 | 23 | 14 |
| 2 | П 2 | Б | 1 | 3 | 8 | 7 | 4 |
| 3 | П 3 | Ц | 1 | 2 | 3 | 2 | 0 |
| 4 | П 4 | Д | 1 | 4 | петнаест | 14 | 10 |
| 5 | П 5 | И | 2 | 3 | Једанаест | 9 | 7 |
| 6 | П 6 | Ф | 3 | 2 | 5 | 2 | 0 |
| следећи → ← прев Да би се решио проблема трошења сигнала за буђење, Дијкстра је предложио приступ који укључује чување свих позива за буђење. Дијкстра наводи да, уместо да даје позиве за буђење директно потрошачу, произвођач може да сачува позив за буђење у променљивој. Свако од потрошача може да га прочита кад год затреба. Семафор је променљива која чува читаве позиве за буђење који се преносе од произвођача до потрошача. То је променљива на којој се читање, мењање и ажурирање дешава аутоматски у режиму кернела. Семафор се не може имплементирати у корисничком режиму јер услов трке увек може настати када два или више процеса покушавају да приступе променљивој истовремено. Увек је потребна подршка оперативног система да би се имплементирао. Према захтевима ситуације, Семафор се може поделити у две категорије.
О сваком ћемо детаљно разговарати. |