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
- CPU - - - > Centrálna procesorová jednotka
- FCFS - - - > Kto príde, ten prv melie
- AT - - - > Čas príchodu
- BT - - - > Burst Time
- WT - - - > Čakacia doba
- TAT - - - > Turn Around Time
- CT - - - > Čas dokončenia
- 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ú:
- Implementácia je jednoduchá.
- Počas používania nespôsobuje žiadne kauzality
- Prijíma nepreventívnu a preventívnu stratégiu.
- Spustí každú procedúru v poradí, v akom sú prijaté.
- Č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ú:
- Na prideľovanie procesov používa front First In First Out.
- Proces plánovania CPU FCFS je priamočiary a ľahko implementovateľný.
- V prípade preventívneho plánovania FCFS neexistuje šanca, že proces bude hladný.
- 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
| Áno nie | ID procesu | Čas príchodu | Burst Time | Čas dokončenia | Turn Around Time | Čas čakania | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | jedenásť | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | jedenásť |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | A | 2 | 3 | dvadsaťjeden | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | dvadsať | 18 |
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:
| Áno nie | ID procesu | Čas príchodu | Burst Time | Čas dokončenia | Turn Around Time | Čas čakania | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 23 | 23 | 14 |
| 2 | P 2 | B | 1 | 3 | 8 | 7 | 4 |
| 3 | P 3 | C | 1 | 2 | 3 | 2 | 0 |
| 4 | P 4 | D | 1 | 4 | pätnásť | 14 | 10 |
| 5 | P 5 | A | 2 | 3 | jedenásť | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| ďalej → ← predch Aby sa zbavil problému plytvania signálmi budenia, Dijkstra navrhol prístup, ktorý zahŕňa ukladanie všetkých budíkov. Dijkstra uvádza, že namiesto toho, aby výrobca dával budenie hovorom priamo spotrebiteľovi, môže ho uložiť do premennej. Ktorýkoľvek zo spotrebiteľov si ho môže prečítať, kedykoľvek to potrebuje. Semafor sú premenné, v ktorých sú uložené všetky budenia, ktoré sa prenášajú od výrobcu k spotrebiteľovi. Je to premenná, ktorej čítanie, úprava a aktualizácia prebieha automaticky v režime jadra. Semafor nie je možné implementovať v užívateľskom režime, pretože súperenie môže nastať vždy, keď sa dva alebo viac procesov pokúša o prístup k premennej súčasne. Na implementáciu vždy potrebuje podporu operačného systému. Podľa požiadaviek situácie možno Semafor rozdeliť do dvoch kategórií.
O každom sa budeme podrobne rozprávať. |