V tomto návode sa naučíme dôležitý koncept v algoritmoch plánovania procesov CPU. Dôležitý názov konceptu je „kto prv príde, ten prv melie“. Toto je základný algoritmus, ktorý sa musí naučiť každý študent, aby pochopil všetky základy plánovacích algoritmov CPU Process Scheduling.

Kto prv príde, ten prv melie dláždi cestu pre pochopenie iných algoritmov. Tento algoritmus môže mať veľa nevýhod. Tieto nevýhody však vytvorili veľmi nové a efektívne algoritmy. Takže je našou zodpovednosťou dozvedieť sa o algoritmoch plánovania procesov CPU, kto príde prvý.

Dôležité skratky

1. CPU - - - > Centrálna procesorová jednotka
2. FCFS - - - > Kto príde, ten prv melie
3. AT - - - > Čas príchodu
4. BT - - - > Burst Time
5. WT - - - > Čakacia doba
6. TAT - - - > Turn Around Time
7. CT - - - > Čas dokončenia
8. FIFO - - - > Prvý dnu, prvý von

Kto prv príde, ten prv melie

Algoritmus plánovania CPU, ktorý je skôr známy ako FCFS, je prvým algoritmom algoritmu plánovania CPU Process Scheduling Algorithm. V algoritme „kto prv príde, ten prv berie“ to, čo robíme, je umožniť, aby sa proces vykonával lineárne.

To znamená, že ktorýkoľvek proces vstúpi do procesu, ktorý ako prvý vstúpi do frontu pripravenosti, sa vykoná ako prvý. To ukazuje, že algoritmus „kto prv príde, prv berie“ sa riadi princípom „prvý dnu, prvý von“ (FIFO).

Algoritmus „kto prv príde, ten prv melie“ môže byť vykonaný preemptívnym a nepreemptívnym spôsobom. Predtým, ako prejdeme na príklady, dovoľte nám pochopiť, čo je preemptívny a nepreemptívny prístup v plánovaní procesov CPU.

Preemptívny prístup

V tomto prípade Pre Emptive Process Scheduling OS prideľuje zdroje procesu na vopred určené časové obdobie. Proces prechádza zo stavu spustenia do stavu pripravenosti alebo zo stavu čakania do stavu pripravenosti počas prideľovania zdrojov. K tomuto prepínaniu dochádza, pretože CPU môže priradiť prednosť iným procesom a nahradiť proces s vyššou prioritou práve aktívnym procesom.

Nepreemptívny prístup

V tomto prípade plánovania procesu bez predbežného vyprázdnenia nie je možné zdroj z procesu stiahnuť skôr, ako sa proces dokončí. Keď spustený proces skončí a prejde do čakacieho stavu, prostriedky sa prepnú.

Efekt konvoja, kto prvý príde, ten prv melie (FCFS)

Convoy Effect je jav, ktorý sa vyskytuje v plánovacom algoritme s názvom First Come First Serve (FCFS). Algoritmus plánovania „kto prv príde, ten prv berie“ prebieha spôsobom, ktorý nie je preventívny.

Nepreemptívny spôsob znamená, že ak sa proces alebo úloha začne vykonávať, operačný systém musí dokončiť svoj proces alebo úlohu. Kým nie je proces alebo úloha nulová, nový alebo ďalší proces alebo úloha nezačne vykonávať svoju činnosť. Definícia Nepreemptívneho plánovania z hľadiska operačného systému znamená, že centrálna procesorová jednotka (CPU) bude úplne vyhradená až do konca procesu alebo úlohy, ktorá bola spustená ako prvá a nový proces alebo úloha sa vykoná až po dokončení staršieho procesu, resp. prácu.

Môže nastať niekoľko prípadov, ktoré môžu spôsobiť, že centrálna procesorová jednotka (CPU) pridelí príliš veľa času. Je to preto, že v bezpreventívnom prístupe plánovacieho algoritmu „kto prv príde, ten prv berie“ sa procesy alebo úlohy vyberajú v sériovom poradí. V dôsledku toho kratšie úlohy alebo procesy za väčšími procesmi alebo úlohami trvá príliš veľa času na dokončenie ich vykonania. Z tohto dôvodu je čas čakania, čas obrátky a čas dokončenia veľmi vysoký.

Takže, keď je prvý proces veľký alebo čas dokončenia je príliš dlhý, nastáva tento efekt konvoja v algoritme „kto prv príde, ten prv melie“.

Predpokladajme, že dokončenie dlhšej úlohy trvá nekonečne dlho. Potom zostávajúce procesy musia čakať rovnaký nekonečný čas. Kvôli tomuto Convoy Effectu vytvorenému Longer Job sa hladovanie čakacích procesov veľmi rýchlo zvyšuje. Toto je najväčšia nevýhoda plánovania procesov CPU FCFS.

Charakteristika plánovania procesov CPU FCFS

Charakteristiky plánovania procesov CPU FCFS sú:

1. Implementácia je jednoduchá.
2. Počas používania nespôsobuje žiadne kauzality
3. Prijíma nepreventívnu a preventívnu stratégiu.
4. Spustí každú procedúru v poradí, v akom sú prijaté.
5. Čas príchodu sa používa ako výberové kritérium pre postupy.

Výhody plánovania procesov CPU FCFS

Výhody plánovania procesov CPU FCFS sú:

1. Na prideľovanie procesov používa front First In First Out.
2. Proces plánovania CPU FCFS je priamočiary a ľahko implementovateľný.
3. V prípade preventívneho plánovania FCFS neexistuje šanca, že proces bude hladný.
4. Keďže sa nezohľadňuje priorita procesu, ide o spravodlivý algoritmus.

Nevýhody plánovania procesov CPU FCFS

Nevýhody plánovania procesov CPU FCFS sú:

• Plánovací algoritmus FCFS CPU má dlhú čakaciu dobu
• FCFS CPU Scheduling uprednostňuje CPU pred vstupnými alebo výstupnými operáciami
• V FCFS existuje možnosť výskytu Convoy Effect
• Pretože FCFS je taký priamy, často nie je veľmi efektívny. Ruka v ruke s tým idú aj predĺžené čakacie doby. Všetky ostatné objednávky zostanú nečinné, ak je CPU zaneprázdnené spracovaním jednej časovo náročnej objednávky.

Problémy v algoritme plánovania CPU, kto príde prvý

Prí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 

Nepreemptívny prístup

Teraz poďme vyriešiť tento problém pomocou plánovacieho algoritmu s názvom Kto príde, ten prv berie v nepreventívnom prístupe.

Ganttov diagram pre vyššie uvedený príklad 1 je:

od abecedy k číslu

Čas obratu = čas dokončenia - čas príchodu

Čakacia doba = Doba obrátenia - Čas zhluku

Riešenie vyššie uvedenej otázky Príklad 1

Priemerný čas dokončenia je:

Priemerná CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6

Priemerná CT = 97/6

Priemer CT = 16,16667

Priemerná doba čakania je:

Priemerná WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6

Priemerná WT = 66/6

Priemerná WT = 11

Priemerný čas obratu je:

Priemerná TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6

Priemer TAT = 89/6

Priemer TAT = 14,83334

Takto je FCFS vyriešený v prístupe bez predbežného opatrenia.

Teraz pochopme, ako ich možno vyriešiť pomocou predbežného prístupu

algoritmus pre rsa

Preemptívny prístup

Teraz poďme vyriešiť tento problém pomocou plánovacieho algoritmu s názvom „kto prv príde, ten prv melie“ v predbežnom prístupe.

V Pre Emptive Approach hľadáme najlepší dostupný proces

Ganttov diagram pre vyššie uvedený príklad 1 je: