Algoritmy plánovania CPU v operačných systémoch

Obsah:

Anonim

Čo je plánovanie CPU?

Plánovanie procesora je proces určovania, ktorý proces bude vlastniť procesor na vykonanie, zatiaľ čo iný proces bude pozastavený. Hlavnou úlohou plánovania CPU je zabezpečiť, aby vždy, keď CPU zostane nečinné, operačný systém aspoň vybral jeden z procesov dostupných vo fronte pripravených na vykonanie. Proces výberu uskutoční plánovač CPU. Vyberie jeden z procesov v pamäti, ktoré sú pripravené na vykonanie.

V tomto výučbe plánovania CPU sa dozviete:

  • Čo je plánovanie CPU?
  • Typy plánovania CPU
  • Dôležité terminológie plánovania CPU
  • Kritériá plánovania CPU
  • Intervalový časovač
  • Čo je dispečer?
  • Algoritmus plánovania CPU
  • Prvý, prvý, prvý podávajte
  • Najkratší zostávajúci čas
  • Prioritné plánovanie
  • Round-Robin Scheduling
  • Najkratšia práca
  • Plánovanie front na viacerých úrovniach
  • Účel algoritmu plánovania

Typy plánovania CPU

Tu sú dva druhy metód plánovania:

Preventívne plánovanie

V preventívnom plánovaní sú úlohy väčšinou priradené k svojim prioritám. Niekedy je dôležité spustiť úlohu s vyššou prioritou pred ďalšou úlohou s nižšou prioritou, aj keď je úloha s nižšou prioritou stále spustená. Úloha s nižšou prioritou nejaký čas trvá a obnoví sa, keď úloha s vyššou prioritou dokončí svoje vykonávanie.

Nepreventívne plánovanie

V tomto type plánovacej metódy bola CPU pridelená konkrétnemu procesu. Proces, ktorý udržuje CPU v činnosti, uvoľní CPU buď prepnutím kontextu, alebo ukončením. Je to jediná metóda, ktorú je možné použiť pre rôzne hardvérové ​​platformy. Je to preto, lebo nepotrebuje špeciálny hardvér (napríklad časovač), ako je napríklad preventívne plánovanie.

Kedy je plánovanie preventívne alebo nepre preventívne?

Ak chcete zistiť, či je plánovanie preventívne alebo nie preventívne, zvážte tieto štyri parametre:

  1. Proces sa prepne z bežiaceho do čakajúceho stavu.
  2. Konkrétny proces sa prepne z prevádzkového stavu do pripraveného stavu.
  3. Konkrétny proces sa prepne z čakajúceho stavu do pripraveného stavu.
  4. Proces dokončil svoje vykonávanie a ukončil sa.

Platia iba podmienky 1 a 4, plánovanie sa nazýva nepreventívne.

Všetky ostatné plánovania sú preventívne.

Dôležité terminológie plánovania CPU

  • Burst Time / Execution Time: Je to čas potrebný na dokončenie procesu. Hovorí sa mu aj doba behu.
  • Čas príchodu: keď proces vstúpi do pripraveného stavu
  • Čas ukončenia: po dokončení procesu a ukončení systému
  • Multiprogramovanie: Viacero programov, ktoré môžu byť súčasne v pamäti.
  • Pracovné miesta: Je to typ programu bez akejkoľvek interakcie používateľa.
  • Užívateľ: Je to druh programu, ktorý má interakciu s používateľom.
  • Proces: Je to referencia, ktorá sa používa pre prácu aj pre používateľa.
  • Cyklus série CPU / IO: Charakterizuje vykonávanie procesu, pri ktorom sa striedajú aktivity CPU a I / O. Časy CPU sú zvyčajne kratšie ako čas I / O.

Kritériá plánovania CPU

Algoritmus plánovania CPU sa snaží maximalizovať a minimalizovať nasledovné:

Maximalizovať:

Využitie CPU: Využitie CPU je hlavnou úlohou, pri ktorej sa operačný systém musí ubezpečiť, že CPU zostáva čo najviac vyťažené. Môže sa pohybovať od 0 do 100 percent. Pre RTOS to však môže byť interval od 40 percent pre nízku úroveň a 90 percent pre systém vysokej úrovne.

Priepustnosť: Počet procesov, ktoré dokončia svoje vykonávanie za jednotku času, je známy priepustnosť. Takže keď je CPU zaneprázdnený vykonávaním procesu, v tom čase sa pracuje, a práca dokončená za jednotku času sa nazýva priepustnosť.

Minimalizovať:

Čas čakania: Čas čakania je suma, na ktorú musí konkrétny proces čakať v rade pripravených.

Čas odpovede: Je to čas, v ktorom bola žiadosť odoslaná, kým sa nevytvorí prvá odpoveď.

Čas obratu: Čas obratu je čas potrebný na vykonanie konkrétneho procesu. Je to výpočet celkového času stráveného čakaním na vstup do pamäte, čakaním vo fronte a vykonaním na CPU. Obdobie medzi časom predloženia procesu a časom dokončenia predstavuje čas obratu.

Intervalový časovač

Prerušenie časovačom je metóda, ktorá úzko súvisí s predvídaním. Keď určitý proces získa pridelenie CPU, môže byť časovač nastavený na určený interval. Prerušenie aj predvoľba časovača vynútia, aby proces vrátil procesor skôr, ako je zhluk procesora dokončený.

Väčšina multi-programovaných operačných systémov používa určitú formu časovača, aby zabránila tomu, aby proces navždy viazal systém.

Čo je dispečer?

Jedná sa o modul, ktorý poskytuje riadenie CPU procesu. Dispečer by mal byť rýchly, aby sa dal spustiť pri každom prepnutí kontextu. Latencia odoslania je množstvo času, ktoré potrebuje plánovač CPU na zastavenie jedného procesu a na spustenie iného.

Funkcie vykonávané dispečerom:

  • Prepínanie kontextu
  • Prepína sa do používateľského režimu
  • Presun na správne miesto v novo načítanom programe.

Algoritmus plánovania CPU

Existuje hlavne šesť typov algoritmov plánovania procesov

  1. Prvé, prvé, prvé podávanie (FCFS)
  2. Plánovanie najkratšej práce (SJF)
  3. Najkratší zostávajúci čas
  4. Prioritné plánovanie
  5. Round Robin Scheduling
  6. Viacúrovňové plánovanie front
Algoritmy plánovania

Prvý, prvý, prvý podávajte

First Come First Serve je plná forma FCFS. Je to najjednoduchší a najjednoduchší algoritmus plánovania procesora. V tomto type algoritmu získa proces, ktorý požaduje CPU, najskôr pridelenie CPU. Túto metódu plánovania je možné spravovať pomocou frontu FIFO.

Keď proces vstupuje do frontu pripravených, jeho PCB (Process Control Block) je spojená s chvostom frontu. Keď sa teda CPU uvoľní, malo by sa to procesu priradiť na začiatku frontu.

Charakteristika metódy FCFS:

  • Ponúka nepreventívny a preventívny plánovací algoritmus.
  • Úlohy sa vždy vykonávajú podľa princípu „kto skôr príde“
  • Ľahko sa implementuje a používa.
  • Táto metóda má však slabý výkon a všeobecná čakacia doba je dosť vysoká.

Najkratší zostávajúci čas

Plná forma SRT je najkratší zostávajúci čas. Je tiež známy ako preventívne plánovanie SJF. V tejto metóde bude proces pridelený úlohe, ktorá je najbližšie k jej dokončeniu. Táto metóda zabraňuje tomu, aby novší pripravený stav procesu podržal dokončenie staršieho procesu.

Charakteristika metódy plánovania SRT:

  • Táto metóda sa väčšinou používa v dávkových prostrediach, kde sa vyžaduje uprednostnenie krátkych úloh.
  • Toto nie je ideálna metóda na implementáciu do zdieľaného systému, kde požadovaný čas CPU nie je známy.
  • Priraďte sa ku každému procesu ako dĺžka jeho ďalšieho prasknutia procesora. Tento operačný systém teda používa tieto dĺžky, čo pomáha naplánovať proces na čo najkratší čas.

Prioritné plánovanie

Prioritné plánovanie je metóda plánovania procesov na základe priority. V tejto metóde plánovač vyberá úlohy, ktoré majú pracovať podľa priority.

Prioritné plánovanie tiež pomáha OS zahrnúť prioritné priradenia. Najskôr by sa mali vykonať procesy s vyššou prioritou, zatiaľ čo úlohy s rovnakými prioritami sa vykonávajú zásadne alebo podľa princípov FCFS. O priorite je možné rozhodnúť na základe požiadaviek na pamäť, čas, atď.

Round-Robin Scheduling

Round robin je najstarší a najjednoduchší plánovací algoritmus. Názov tohto algoritmu pochádza z princípu kruhových obchádzok, keď každý človek dostane rovnaký podiel na niečom. Väčšinou sa používa na plánovanie algoritmov v multitaskingu. Táto metóda algoritmu pomáha pri hladkom vykonávaní procesov.

Charakteristiky plánovania podľa princípu Round Robin

  • Round robin je hybridný model poháňaný hodinami
  • Časový úsek by mal byť minimálny, ktorý je priradený konkrétnej úlohe, ktorá sa má spracovať. Môže sa však líšiť pre rôzne procesy.
  • Je to systém v reálnom čase, ktorý reaguje na udalosť v stanovenom časovom limite.

Najkratšia práca

SJF je úplná forma (Najkratšia úloha ako prvá) je plánovací algoritmus, v ktorom by sa mal zvoliť proces s najkratšou dobou vykonania pre ďalšie vykonanie. Táto metóda plánovania môže byť preventívna aj nepreventívna. Výrazne znižuje priemernú dobu čakania na ďalšie procesy čakajúce na vykonanie.

Charakteristika plánovania SJF

  • Je spojená s každou úlohou ako jednotka času na dokončenie.
  • Ak je v tomto spôsobe k dispozícii procesor, najskôr sa vykoná ďalší proces alebo úloha s najkratším časom dokončenia.
  • Implementuje sa pomocou nepreventívnej politiky.
  • Táto metóda algoritmu je užitočná pre dávkové spracovanie, kde čakanie na dokončenie úloh nie je kritické.
  • Zlepšuje produkciu úloh tým, že ponúka kratšie úlohy, ktoré by sa mali vykonať najskôr, ktoré majú väčšinou kratšiu dobu spracovania.

Plánovanie front na viacerých úrovniach

Tento algoritmus rozdeľuje front pripravených na rôzne samostatné fronty. V tejto metóde sú procesy priradené do frontu na základe konkrétnej vlastnosti procesu, ako je priorita procesu, veľkosť pamäte atď.

Nejde však o nezávislý algoritmus plánovania operačného systému, pretože na plánovanie úloh je potrebné použiť iné typy algoritmov.

Charakteristika plánovania front na viacerých úrovniach:

  • Pre procesy s niektorými charakteristikami by sa malo zachovať viac radov.
  • Každá fronta môže mať svoje samostatné plánovacie algoritmy.
  • Pre každý front sú dané priority.

Účel algoritmu plánovania

Tu sú dôvody použitia plánovacieho algoritmu:

  • CPU využíva plánovanie na zvýšenie svojej efektívnosti.
  • Pomáha vám alokovať zdroje medzi konkurenčné procesy.
  • Maximálne využitie CPU je možné dosiahnuť multi-programovaním.
  • Procesy, ktoré sa majú vykonať, sú v pohotovosti.

Zhrnutie:

  • Plánovanie CPU je proces určovania, ktorý proces bude vlastniť CPU na vykonávanie, zatiaľ čo iný proces je pozastavený.
  • V preventívnom plánovaní sú úlohy väčšinou priradené k svojim prioritám.
  • V metóde nepreventívneho plánovania bola CPU pridelená konkrétnemu procesu.
  • Čas prasknutia je čas potrebný na dokončenie procesu. Hovorí sa mu aj doba behu.
  • Využitie CPU je hlavnou úlohou, pri ktorej sa operačný systém musí ubezpečiť, že CPU zostáva čo najviac vyťažené
  • Počet procesov, ktoré dokončia svoje vykonávanie za jednotku času, je známy priepustnosť.
  • Čakacia doba je množstvo, na ktoré musí konkrétny proces čakať v rade pripravených.
  • Je to čas, v ktorom bola žiadosť predložená, kým nebude predložená prvá odpoveď.
  • Čas obratu predstavuje množstvo času na vykonanie konkrétneho procesu.
  • Prerušenie časovačom je metóda, ktorá úzko súvisí s predkupným právom,
  • Dispečer je modul, ktorý poskytuje riadenie CPU procesu.
  • Šesť typov algoritmov plánovania procesov je:
  • Prvé prídu prvé, obsluhujú (FCFS), 2) Plánovanie s najkratšou prácou najskôr (SJF) 3) Najkratší zostávajúci čas 4) Plánovanie priorít 5) Plánovanie opakovaných úloh 6) Viacúrovňové plánovanie front
  • V metóde First Come First Serve je proces, ktorý požaduje CPU, najskôr pridelený CPU.
  • V najkratšom zostávajúcom čase bude proces pridelený úlohe, ktorá je najbližšie k jej dokončeniu.
  • V časti Prioritné plánovanie vyberie plánovač úlohy, ktoré majú pracovať podľa priority.
  • V tomto rozvrhu funguje každý deň plánovanie, podľa ktorého každá osoba získa zase rovnaký podiel na niečom
  • V Najkratšej úlohe by sa mal zvoliť ďalší najkratší čas vykonania
  • Pri viacúrovňovom plánovaní metóda oddelí frontu pripravených položiek do rôznych samostatných frontov. V tejto metóde sú procesy priradené do frontu na základe konkrétnej vlastnosti
  • CPU využíva plánovanie na zvýšenie svojej efektívnosti.