V tomto tutoriálu se naučíme důležitý koncept v algoritmech plánování procesů CPU. Důležitým názvem konceptu je kdo dřív přijde, ten dřív mele. Toto je základní algoritmus, který se musí naučit každý student, aby porozuměl všem základům CPU Process Scheduling Algorithms.

Kdo dřív přijde, je dřív na řadě, dláždí cestu k pochopení dalších algoritmů. Tento algoritmus může mít mnoho nevýhod. Tyto nevýhody však vytvořily velmi nové a efektivní algoritmy. Je tedy naší odpovědností dozvědět se o algoritmech plánování procesů CPU kdo dřív přijde, je dřív na řadě.

Důležité zkratky

1. CPU - - - > Centrální procesorová jednotka
2. FCFS - - - > Kdo dřív přijde, je dřív na řadě
3. AT - - - > Čas příjezdu
4. BT - - - > Burst Time
5. WT - - - > Čekací doba
6. TAT - - - > Turn Around Time
7. CT - - - > Čas dokončení
8. FIFO - - - > První dovnitř, první ven

Kdo dřív příjde ten dřív mele

Algoritmus plánování CPU, kdo dřív přijde, je první, zkráceně známý jako FCFS, je prvním algoritmem algoritmu plánování CPU Process Scheduling Algorithm. V algoritmu kdo dřív přijde, ten dřív serví, to, co děláme, je umožnit, aby proces probíhal lineárně.

js splice

To znamená, že kterýkoli proces vstoupí do procesu, který jako první vstoupí do fronty připravenosti, bude proveden jako první. To ukazuje, že algoritmus kdo dřív přijde, ten dřív serví, se řídí principem FIFO (First In First Out).

Algoritmus „kdo dřív přijde, je dřív na řadě“ může být proveden preemptivním a nepreemptivním způsobem. Než se pustíme do příkladů, pochopme, co je to Pre Emptive a Non Pre Emptive Approach v CPU Process Scheduling.

Preemptivní přístup

V tomto případě Pre Emptive Process Scheduling OS přiděluje zdroje procesu na předem určenou dobu. Proces přechází ze stavu běhu do stavu připravenosti nebo ze stavu čekání do stavu připravenosti během alokace zdrojů. K tomuto přepínání dochází, protože CPU může přiřadit přednost jiným procesům a nahradit proces s vyšší prioritou právě aktivní proces.

Nepreemptivní přístup

V tomto případě plánování non Pre Emptive Process Scheduling nemůže být prostředek odebrán z procesu před dokončením procesu. Když běžící proces skončí a přejde do stavu čekání, prostředky se přepnou.

Efekt konvoje, kdo dřív přijde, je dřív na řadě (FCFS)

Convoy Effect je jev, který se vyskytuje v plánovacím algoritmu s názvem First Come First Serve (FCFS). Algoritmus plánování „kdo dřív přijde, ten dřív slouží“ probíhá způsobem, který není preemptivní.

Nepreemptivní způsob znamená, že pokud je proces nebo úloha zahájena prováděním, musí operační systém dokončit svůj proces nebo úlohu. Dokud není proces nebo úloha nulová, nový nebo další proces nebo úloha nezahájí své provádění. Definice Non Preemptive Scheduling z hlediska operačního systému znamená, že centrální procesorová jednotka (CPU) bude zcela vyhrazena až do konce procesu nebo úlohy spuštěné jako první a nový proces nebo úloha se provede až po dokončení staršího procesu, resp. práce.

Může nastat několik případů, které mohou způsobit, že centrální procesorová jednotka (CPU) přidělí příliš mnoho času. Je to proto, že v nepreemptivním přístupu s plánovacím algoritmem „kdo dřív přijde, ten dřív slouží“ jsou procesy nebo úlohy vybírány v sériovém pořadí. V důsledku toho kratší úlohy nebo procesy za většími procesy nebo úlohami trvá příliš dlouho, než se dokončí jejich provedení. V důsledku toho je doba čekání, doba obratu a doba dokončení velmi vysoká.

pole řetězců v jazyce C

Takže, když je první proces velký nebo čas dokončení příliš dlouhý, dojde k tomuto efektu konvoje v algoritmu kdo dřív přijde, ten dřív slouží.

Předpokládejme, že dokončení Longer Job trvá nekonečně dlouho. Poté musí zbývající procesy čekat stejnou nekonečnou dobu. Díky tomuto Convoy Effectu vytvořenému Longer Job se hladovění čekajících procesů velmi rychle zvyšuje. To je největší nevýhoda FCFS CPU Process Scheduling.

Charakteristika FCFS CPU Process Scheduling

Charakteristiky FCFS CPU Process Scheduling jsou:

1. Implementace je jednoduchá.
2. Při používání nezpůsobuje žádné kauzality
3. Přijímá nepreemptivní a preemptivní strategii.
4. Spustí každou proceduru v pořadí, v jakém jsou přijaty.
5. Čas příjezdu se používá jako výběrové kritérium pro postupy.

Výhody plánování procesů CPU FCFS

Výhody FCFS CPU Process Scheduling jsou:

1. K alokaci procesů používá frontu First In First Out.
2. Proces plánování CPU FCFS je přímočarý a snadno implementovatelný.
3. V situaci preventivního plánování FCFS neexistuje žádná šance, že by proces hladověl.
4. Protože se nebere v úvahu priorita procesu, jedná se o spravedlivý algoritmus.

Nevýhody plánování procesů CPU FCFS

Nevýhody FCFS CPU Process Scheduling jsou:

• Plánovací algoritmus FCFS CPU má dlouhou čekací dobu
• FCFS CPU Scheduling upřednostňuje CPU před vstupními nebo výstupními operacemi
• V FCFS existuje možnost výskytu Convoy Effectu
• Protože FCFS je tak přímočarý, často není příliš efektivní. Ruku v ruce s tím jdou i prodloužené čekací doby. Všechny ostatní objednávky zůstanou nečinné, pokud je CPU zaneprázdněno zpracováním jedné časově náročné objednávky.

Problémy s plánovacím algoritmem CPU, kdo dřív přijde, je dřív na řadě

Příklad

 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 

Nepreemptivní přístup

Nyní vyřešme tento problém pomocí plánovacího algoritmu nazvaného „kdo dřív přijde, ten dřív mele“ v nepreemptivním přístupu.

Ganttův diagram pro výše uvedený příklad 1 je:

charakter.srovnej java

Turn Around Time = Čas dokončení – Čas příjezdu

Čekací doba = Turn Around Time - Burst Time

Řešení výše uvedené otázky Příklad 1

Průměrná doba dokončení je:

Průměrná CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6

Průměrná CT = 97/6

Průměr CT = 16,16667

Průměrná čekací doba je:

Průměrná WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6

Průměrná WT = 66/6

Průměrná WT = 11

Průměrná doba obratu je:

Průměrný TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6

úplná tabulka pravdivosti sčítačky

Průměrný TAT = 89/6

Průměrná TAT = 14,83334

Takto je FCFS řešen v nepřetržitém přístupu.

Nyní pochopíme, jak je lze vyřešit v Pre Emptive Approach

Preemptivní přístup

Nyní vyřešme tento problém pomocí plánovacího algoritmu nazvaného „kdo dřív přijde, ten dřív mele“ v preemptivním přístupu.

V Pre Emptive Approach hledáme nejlepší dostupný proces

Ganttův diagram pro výše uvedený příklad 1 je:

powershell vs bash