Шта је планирање најкраћег посла?
Најкраћи посао прво (СЈФ) је алгоритам у коме се за следеће извршавање бира процес који има најмање време извршења. Ова метода заказивања може бити превентивна или непредвиђена. Значајно смањује просечно време чекања за остале процесе који чекају извршење. Пуни облик СЈФ-а је Најкраћи посао прво.
У основи постоје две врсте СЈФ метода:
- Непревентивни СЈФ
- Превентивни СЈФ
У овом упутству за оперативни систем научићете:
- Шта је планирање најкраћег посла?
- Карактеристике СЈФ заказивања
- Непревентивни СЈФ
- Превентивни СЈФ
- Предности СЈФ-а
- Мане / недостаци СЈФ-а
Карактеристике СЈФ заказивања
- Уз сваки посао повезан је као јединица времена коју треба обавити.
- Ова метода алгоритма је корисна за серијску обраду, где чекање на завршетак послова није критично.
- Може побољшати проток процеса осигуравајући да се прво извршавају краћи послови, па према томе могу имати кратко време обраде.
- Побољшава излазну понуду нудећи краће послове, које би прво требало извршити, а који углавном имају краће време израде.
Непревентивни СЈФ
У не-превентивном планирању, када се процесорски циклус додели процесу, процес га задржава док не достигне стање чекања или се не прекине.
Размотрите следећих пет процеса који имају своје јединствено време избијања и време доласка.
| Ред чекања | Пуцање времена | Време доласка |
| П1 | 6 | 2 |
| П2 | 2 | 5 |
| П3 | 8 | 1 |
| П4 | 3 | 0 |
| П5 | 4 | 4 |
Корак 0) У време = 0, П4 стиже и започиње извршење.
Корак 1) У време = 1, долази процес П3. Али, П4 и даље требају 2 извршне јединице да би их довршио. Наставиће извршење.
Корак 2) У време = 2, процес П1 стиже и додаје се у ред чекања. П4 ће наставити извршење.
Корак 3) У време = 3, процес П4 ће завршити своје извршавање. Упоређује се време пуцања П3 и П1. Процес П1 се извршава јер је његово пуцање мање у односу на П3.
Корак 4) У време = 4, процес П5 стиже и додаје се у ред чекања. П1 ће наставити извршење.
Корак 5) У време = 5, процес П2 стиже и додаје се у ред чекања. П1 ће наставити извршење.
Корак 6) У време = 9, процес П1 ће завршити своје извршавање. Упоређује се време пуцања П3, П5 и П2. Процес П2 се извршава јер је његово пуцање најниже.
Корак 7) У тренутку = 10, П2 се извршава, а П3 и П5 су у реду чекања.
Корак 8) У време = 11, процес П2 ће завршити своје извршавање. Упоређује се време пуцања П3 и П5. Процес П5 се извршава јер је његово пуцање краће.
Корак 9) У време = 15, процес П5 ће завршити своје извршавање.
Корак 10) У време = 23, процес П3 ће завршити своје извршавање.
Корак 11) Израчунајмо просечно време чекања за горњи пример.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Превентивни СЈФ
У превентивном СЈФ заказивању, послови се стављају у ред спремности чим дођу. Процес са најкраћим временом бурст-а започиње извршење. Ако стигне процес са чак краћим временом бурст-а, тренутни процес се уклања или онемогућава извршењу, а краћи посао додељује се циклусу процесора.
Размотрите следећих пет процеса:
| Ред чекања | Пуцање времена | Време доласка |
| П1 | 6 | 2 |
| П2 | 2 | 5 |
| П3 | 8 | 1 |
| П4 | 3 | 0 |
| П5 | 4 | 4 |
Корак 0) У време = 0, П4 стиже и започиње извршење.
| Ред чекања | Пуцање времена | Време доласка |
| П1 | 6 | 2 |
| П2 | 2 | 5 |
| П3 | 8 | 1 |
| П4 | 3 | 0 |
| П5 | 4 | 4 |
Корак 1) У време = 1, долази процес П3. Али, П4 има краће време пуцања. Наставиће извршење.
Корак 2) У време = 2, процес П1 стиже са временом пуцања = 6. Време пуцања је дуже од времена П4. Стога ће П4 наставити извршење.
Корак 3) У време = 3, процес П4 ће завршити своје извршавање. Упоређује се време пуцања П3 и П1. Процес П1 се извршава јер је његово пуцање краће.
Корак 4) У време = 4, стићи ће процес П5. Упоређује се време пуцања П3, П5 и П1. Процес П5 се извршава јер је његово пуцање најниже. Процес П1 је предузет.
| Ред чекања | Пуцање времена | Време доласка |
| П1 | Преостало је 5 од 6 | 2 |
| П2 | 2 | 5 |
| П3 | 8 | 1 |
| П4 | 3 | 0 |
| П5 | 4 | 4 |
Корак 5) У време = 5, стићи ће процес П2. Упоређује се време пуцања П1, П2, П3 и П5. Процес П2 се извршава јер је његово пуцање најмање. Процес П5 је предузет.
| Ред чекања | Пуцање времена | Време доласка |
| П1 | Преостало је 5 од 6 | 2 |
| П2 | 2 | 5 |
| П3 | 8 | 1 |
| П4 | 3 | 0 |
| П5 | Преостало је 3 од 4 | 4 |
Корак 6) У тренутку = 6, извршава се П2.
Корак 7) У тренутку = 7, П2 завршава своје извршавање. Упоређује се време пуцања П1, П3 и П5. Процес П5 се извршава јер је његово пуцање краће.
| Ред чекања | Пуцање времена | Време доласка |
| П1 | Преостало је 5 од 6 | 2 |
| П2 | 2 | 5 |
| П3 | 8 | 1 |
| П4 | 3 | 0 |
| П5 | Преостало је 3 од 4 | 4 |
Корак 8) У време = 10, П5 ће завршити своје извршавање. Упоређује се време пуцања П1 и П3. Процес П1 се извршава јер је његово пуцање краће.
Корак 9) У време = 15, П1 завршава своје извршавање. П3 је једини преостали процес. Започеће извршење.
Корак 10) У време = 23, П3 завршава своје извршавање.
Корак 11) Израчунајмо просечно време чекања за горњи пример.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Предности СЈФ-а
Ево предности / предности употребе СЈФ методе:
- СЈФ се често користи за дугорочно заказивање.
- Смањује просечно време чекања преко ФИФО (Фирст ин Фирст Оут) алгоритма.
- СЈФ метода даје најниже просечно време чекања за одређени скуп процеса.
- Прикладно је за послове који се изводе у серији, где су времена извођења унапред позната.
- За пакетни систем дугорочног заказивања, из описа посла може се добити процена времена пуцања.
- За краткорочно заказивање, морамо предвидети вредност следећег времена рафалног снимања.
- Вероватно оптимално с обзиром на просечно време обраде.
Мане / недостаци СЈФ-а
Ево неколико недостатака / недостатака СЈФ алгоритма:
- Време завршетка посла мора бити познато раније, али је тешко предвидети.
- Често се користи у пакетном систему за дугорочно заказивање.
- СЈФ се не може применити за планирање ЦПУ-а на кратак рок. То је зато што не постоји одређена метода за предвиђање дужине надолазећег ЦПУ-а.
- Овај алгоритам може проузроковати веома дуго време обрта или изгладњивање.
- Захтева знање о томе колико дуго ће трајати процес или посао.
- Доводи до гладовања које не смањује просечно време обраде.
- Тешко је знати дужину предстојећег захтева за процесор.
- Протекло време треба евидентирати, што резултира већим трошковима на процесору.
Резиме
- СЈФ је алгоритам у коме се за следеће извршавање бира процес који има најмање време извршења.
- СЈФ заказивање повезано је са сваким послом као временска јединица.
- Ова метода алгоритма је корисна за серијску обраду, где чекање на завршетак послова није критично.
- У основи постоје две врсте СЈФ метода 1) Непревентивни СЈФ и 2) Преемптиве СЈФ.
- У не-превентивном планирању, када се процесорски циклус додели процесу, процес га задржава док не достигне стање чекања или се не прекине.
- У превентивном СЈФ заказивању, послови се стављају у ред спремности чим дођу.
- Иако започиње процес са кратким временом бурст-а, тренутни процес се уклања или спречава да се изврши, а посао који је краћи извршава се 1..
- СЈФ се често користи за дугорочно заказивање.
- Смањује просечно време чекања преко ФИФО (Фирст ин Фирст Оут) алгоритма.
- У СЈФ заказивању, време завршетка посла мора се знати раније, али је тешко предвидети.
- СЈФ се не може применити за планирање ЦПУ-а на кратак рок. То је зато што не постоји одређена метода за предвиђање дужине надолазећег ЦПУ-а.