В този урок ще научим важна концепция в алгоритмите за планиране на процеси на процесора. Важното наименование на концепцията е First Come First Serve. Това е основният алгоритъм, който всеки студент трябва да научи, за да разбере всички основи на алгоритмите за планиране на процеси на процесора.
First Come First Serve проправя пътя за разбиране на други алгоритми. Този алгоритъм може да има много недостатъци. Но тези недостатъци създадоха много нови и ефективни алгоритми. Така че наша отговорност е да научим за алгоритмите за планиране на процеси на процесора „първи дошъл първи обслужен“.
Важни съкращения
- CPU - - - > Централен процесор
- FCFS - - - > Първи дошъл първи сервиран
- AT - - - > Час на пристигане
- BT - - - > Време на спукване
- WT - - - > Време на изчакване
- TAT - - - > Време за обръщане
- CT - - - > Време за завършване
- FIFO - - - > Първи влязъл, първи излязъл
First Come First Serve
Алгоритъмът за планиране на CPU First Come First Serve, известен накратко като FCFS, е първият алгоритъм на алгоритъма за планиране на CPU процеси. В алгоритъма First Come First Serve това, което правим, е да позволим на процеса да се изпълнява по линеен начин.
Това означава, че всеки процес, който влиза в процеса, влиза първи в опашката за готовност, се изпълнява първи. Това показва, че алгоритъмът „първи дошъл, първи обслужен“ следва принципа „първи влязъл, първи излязъл“ (FIFO).
азбука в цифри
Алгоритъмът First Come First Serve може да бъде изпълнен по Pre Emptive и Non Pre Emptive начин. Преди да преминем към примери, нека разберем какво е предварителен и непредварителен подход в планирането на процеси на процесора.
Предварителен подход
В този случай на предварително изчистващо планиране на процес, ОС разпределя ресурсите на процес за предварително определен период от време. Процесът преминава от състояние на работа в състояние на готовност или от състояние на изчакване в състояние на готовност по време на разпределението на ресурсите. Това превключване се случва, защото процесорът може да присвои предимство на други процеси и да замени текущо активния процес с процеса с по-висок приоритет.
Непредварителен подход
В този случай на непредварително планиране на процеса, ресурсът не може да бъде изтеглен от процес, преди процесът да е приключил. Когато работещ процес завърши и премине в състояние на изчакване, ресурсите се превключват.
Ефект на конвоя при First Come First Serve (FCFS)
Ефектът на конвоя е феномен, който възниква в алгоритъма за планиране, наречен First Come First Serve (FCFS). Алгоритъмът за планиране на първия дошъл, първи сервиран се осъществява по начин, който не е изпреварващ.
Непревантивният начин означава, че ако даден процес или задание е започнало изпълнение, тогава операционната система трябва да завърши своя процес или задание. Докато процесът или заданието не е нула, новият или следващият процес или задание не започва своето изпълнение. Дефиницията на Non Preemptive Scheduling по отношение на операционната система означава, че централният процесор (CPU) ще бъде напълно посветен до края на процеса или задачата, която е стартирана първа, а новият процес или задача се изпълнява само след приключване на по-стария процес или работа.
Може да има няколко случая, които може да накарат централния процесор (CPU) да отдели твърде много време. Това е така, защото в алгоритъма за планиране „първи дошъл първи обслужен“ непредварителен подход процесите или заданията се избират в последователен ред. Поради това по-кратките задачи или процеси зад по-големите процеси или задачи отнемат твърде много време за завършване на изпълнението им. Поради това времето за изчакване, времето за обръщане и времето за завършване е много високо.
И така, тук, тъй като първият процес е голям или времето за завършване е твърде голямо, тогава се получава този ефект на конвой в алгоритъма „Първи дошъл, първи обслужен“.
Да приемем, че изпълнението на Longer Job отнема безкрайно време. След това останалите процеси трябва да изчакат същото безкрайно време. Благодарение на този ефект на конвой, създаден от по-дългата работа, гладуването на процесите на чакане нараства много бързо. Това е най-големият недостатък на FCFS CPU Process Scheduling.
Характеристики на FCFS CPU Process Scheduling
Характеристиките на FCFS CPU Process Scheduling са:
- Изпълнението е просто.
- Не причинява никакви причинно-следствени връзки по време на употреба
- Той приема непревантивна и превантивна стратегия.
- Той изпълнява всяка процедура в реда, в който са получени.
- Времето на пристигане се използва като критерий за избор на процедури.
Предимства на FCFS CPU Process Scheduling
Предимствата на FCFS CPU Process Scheduling са:
- За да разпредели процесите, той използва опашката First In First Out.
- Процесът на планиране на процесора FCFS е ясен и лесен за изпълнение.
- В ситуацията на FCFS изпреварващо планиране няма шанс за спиране на процеса.
- Тъй като не се взема предвид приоритетът на процеса, това е справедлив алгоритъм.
Недостатъци на FCFS CPU Process Scheduling
Недостатъците на FCFS CPU Process Scheduling са:
- Алгоритъмът за планиране на процесора FCFS има дълго време на изчакване
- Графикът на процесора на FCFS предпочита процесора пред входните или изходните операции
- В FCFS има шанс за поява на Convoy Effect
- Тъй като FCFS е толкова ясен, често не е много ефективен. Удължените периоди на изчакване вървят ръка за ръка с това. Всички останали поръчки остават неактивни, ако процесорът е зает с обработката на една отнемаща време поръчка.
Проблеми в алгоритъма за планиране на процесора „първи дошъл първи обслужен“.
Пример
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
Непредварителен подход
Сега, нека разрешим този проблем с помощта на алгоритъма за планиране, наречен First Come First Serve в непревантивния подход.
Диаграмата на Гант за горния пример 1 е:
Време за обръщане = време за завършване - време на пристигане
Време на изчакване = време на обръщане - време на спукване
низ от масив в c
Решение на горния въпрос Пример 1
| Да не | ID на процеса | Час на пристигане | Време за спукване | Време за завършване | Време за изпълнение | Време за чакане | |
|---|---|---|---|---|---|---|---|
| 1 | П 1 | А | 0 | 9 | 9 | 9 | 0 |
| 2 | П 2 | Б | 1 | 3 | 12 | единадесет | 8 |
| 3 | П 3 | ° С | 1 | 2 | 14 | 13 | единадесет |
| 4 | P 4 | д | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | И | 2 | 3 | двадесет и едно | 19 | 16 |
| 6 | стр. 6 | Е | 3 | 2 | 23 | двадесет | 18 |
Средното време за завършване е:
Средно CT = (9 + 12 + 14 + 18 + 21 + 23) / 6
Среден CT = 97 / 6
Среден CT = 16.16667
Средното време на изчакване е:
Средна WT = (0 + 8 + 11 + 13 + 16 + 18) /6
Средна WT = 66 / 6
Средна WT = 11
Средното време за изпълнение е:
Среден TAT = (9 + 11 + 13 + 17 + 19 +20) / 6
Среден TAT = 89 / 6
Среден TAT = 14.83334
Ето как FCFS се решава в Non Pre Emptive Approach.
Сега нека разберем как те могат да бъдат решени в Pre Emptive Approach
Предварителен подход
Сега нека разрешим този проблем с помощта на алгоритъма за планиране, наречен First Come First Serve в Pre Emptive Approach.
В Pre Emptive Approach ние търсим най-добрия наличен процес
протоколи на слоя за връзка за данни
Диаграмата на Гант за горния пример 1 е:
| Да не | ID на процеса | Час на пристигане | Време за спукване | Време за завършване | Време за изпълнение | Време за чакане | |
|---|---|---|---|---|---|---|---|
| 1 | П 1 | А | 0 | 9 | 23 | 23 | 14 |
| 2 | П 2 | Б | 1 | 3 | 8 | 7 | 4 |
| 3 | П 3 | ° С | 1 | 2 | 3 | 2 | 0 |
| 4 | P 4 | д | 1 | 4 | петнадесет | 14 | 10 |
| 5 | P 5 | И | 2 | 3 | единадесет | 9 | 7 |
| 6 | стр. 6 | Е | 3 | 2 | 5 | 2 | 0 |
| следващ → ← предишна За да се отърве от проблема с загубата на сигнали за събуждане, Дайкстра предложи подход, който включва съхраняване на всички повиквания за събуждане. Dijkstra заявява, че вместо да дава обажданията за събуждане директно на потребителя, производителят може да съхрани обаждането за събуждане в променлива. Всеки от потребителите може да го прочете, когато има нужда. Семафорът е променливите, които съхраняват всички повиквания за събуждане, които се прехвърлят от производителя към потребителя. Това е променлива, на която четенето, модифицирането и актуализирането се извършват автоматично в режим на ядрото. Семафорът не може да бъде внедрен в потребителски режим, тъй като винаги може да възникне състояние на състезание, когато два или повече процеса се опитват да получат достъп до променливата едновременно. Винаги се нуждае от поддръжка от операционната система, за да бъде внедрена. Според търсенето на ситуацията, Semaphore може да бъде разделен на две категории.
Ще обсъдим всеки един подробно. |