Algoritmi planiranja CPU -a u operacijskim sustavima

Što je CPU raspoređivanje?

Raspored procesora je proces određivanja koji će proces posjedovati CPU za izvršavanje dok je drugi proces na čekanju. Glavni zadatak planiranja CPU -a je pobrinuti se da, kad god CPU ostane u stanju mirovanja, OS barem odabere jedan od procesa koji su dostupni u redu za izvršavanje. Proces odabira provest će CPU raspoređivač. Odabire jedan od procesa u memoriji koji su spremni za izvođenje.

U ovom vodiču za planiranje CPU -a naučit ćete:

Vrste raspoređivanja CPU -a

Evo dvije vrste rasporeda:

Preventivno zakazivanje

U preventivnom rasporedu zadaci se uglavnom dodjeljuju svojim prioritetima. Ponekad je važno pokrenuti zadatak s višim prioritetom prije drugog zadatka nižeg prioriteta, čak i ako je zadatak nižeg prioriteta još uvijek u izvođenju. Zadatak nižeg prioriteta zadržava se neko vrijeme i nastavlja se kad zadatak višeg prioriteta završi s izvršavanjem.

Nepreventivno zakazivanje

U ovoj vrsti metode planiranja, CPU je dodijeljen određenom procesu. Proces koji zadržava CPU zauzet će osloboditi CPU bilo prebacivanjem konteksta ili završetkom. To je jedina metoda koja se može koristiti za različite hardverske platforme. To je zato što ne treba poseban hardver (na primjer, mjerač vremena) poput preventivnog zakazivanja.

Kada je zakazivanje preventivno ili nepreventivno?

Da biste utvrdili je li zakazivanje preventivno ili nepreventivno, uzmite u obzir ova četiri parametra:

  1. Proces se prebacuje iz stanja rada u stanje čekanja.
  2. Određeni proces prelazi iz stanja rada u stanje pripravnosti.
  3. Određeni proces prelazi iz stanja čekanja u stanje pripravnosti.
  4. Proces je završio izvršenje i završio.

Primjenjuju se samo uvjeti 1 i 4, zakazivanje se naziva nepreventivno.

Sva ostala zakazivanja su preventivna.

Važne terminologije raspoređivanja CPU -a

  • Vrijeme bursta/vrijeme izvođenja: Proces je vrijeme potrebno za dovršetak izvođenja. Također se naziva vrijeme rada.
  • Vrijeme dolaska: kada proces uđe u stanje pripravnosti
  • Vrijeme završetka: kada se proces dovrši i izađe iz sustava
  • Višeprogramiranje: Brojni programi koji mogu biti prisutni u memoriji u isto vrijeme.
  • Poslovi: To je vrsta programa bez ikakve interakcije korisnika.
  • Korisnik: To je vrsta programa s interakcijom korisnika.
  • Postupak: To je referenca koja se koristi i za posao i za korisnika.
  • CPU/IO burst ciklus: Karakterizira izvršavanje procesa koji se izmjenjuje između CPU -a i I/O aktivnosti. CPU vrijeme je obično kraće od vremena I/O.

Kriteriji raspoređivanja CPU -a

Algoritam planiranja CPU -a pokušava povećati i smanjiti sljedeće:

Povećanje:

Korištenje procesora: Korištenje CPU -a glavni je zadatak u kojem operacijski sustav mora osigurati da CPU ostane što je moguće zauzetiji. Može se kretati od 0 do 100 posto. Međutim, za RTOS to može biti raspon od 40 posto za nisku razinu i 90 posto za sustav visoke razine.

Propusnost: Broj procesa koji završe svoje izvršavanje po jedinici vremena poznat je Propusnost. Dakle, kada je CPU zauzet izvršavanjem procesa, u to vrijeme se radi, a rad završen po jedinici vremena naziva se Propusnost.

Smanji:

Vrijeme čekanja: Vrijeme čekanja je iznos koji određeni proces treba čekati u redu čekanja.

Vrijeme odziva: To je vremenski period u kojem je zahtjev podnesen do dobivanja prvog odgovora.

Vrijeme obrade: Vrijeme obrade je vrijeme potrebno za izvršavanje određenog procesa. To je izračun ukupnog vremena provedenog čekajući da se uđe u memoriju, čeka u redu i izvrši na CPU -u. Razdoblje od trenutka podnošenja procesa do vremena završetka je vrijeme obrtanja.

Intervalni mjerač vremena

Prekidač timera je metoda koja je usko povezana s predubojem. Kad određeni proces dobije dodjelu CPU -a, mjerač vremena može se postaviti na određeni interval. Prekid i mjerač timera prisiljavaju proces na vraćanje CPU -a prije nego što se završi njegov rafal CPU -a.

Većina višeprogramiranih operacijskih sustava koristi neki oblik mjerača vremena kako bi spriječila proces da zauvijek poveže sustav.

Što je Dispečer?

To je modul koji omogućuje kontrolu CPU -a procesu. Dispečer bi trebao biti brz kako bi mogao raditi na svakom kontekstnom prekidaču. Latencija otpreme je vrijeme potrebno planiranju CPU -a da zaustavi jedan proces i pokrene drugi.

Funkcije koje vrši dispečer:

  • Promjena konteksta
  • Prebacivanje u korisnički način rada
  • Premještanje na ispravno mjesto u novo učitanom programu.

Vrste algoritama raspoređivanja CPU -a

Postoji uglavnom šest vrsta algoritama za planiranje procesa

  1. Prvi dođe prvi posluži (FCFS)
  2. Zakazivanje najkraćeg radnog mjesta (SJF)
  3. Najkraće preostalo vrijeme
  4. Prioritetno zakazivanje
  5. Robin Robin raspored
  6. Zakazivanje redova na više razina

Algoritmi planiranja



Prvi dođi prvi posluži

First Come First Serve je puni oblik FCFS -a. To je najjednostavniji i najjednostavniji algoritam za planiranje procesora. U ovoj vrsti algoritma, proces koji traži CPU prvo dobiva dodjelu CPU -a. Ovom metodom raspoređivanja može se upravljati s FIFO redom.

Kako proces ulazi u red čekanja, njegova PCB (Process Control Block) povezana je s repom reda. Dakle, kada CPU postane slobodan, treba ga dodijeliti procesu na početku reda.

Karakteristike FCFS metode:

  • Nudi preventivni i preventivni algoritam planiranja.
  • Poslovi se uvijek izvode po principu prvi stigao, prvi opslužio
  • Lako se implementira i koristi.
  • Međutim, ova metoda ima loše performanse, a opće je vrijeme čekanja prilično veliko.

Najkraće preostalo vrijeme

Puni oblik SRT -a je najkraće preostalo vrijeme. Poznat je i kao SJF preventivno zakazivanje. U ovoj metodi proces će biti dodijeljen zadatku koji je najbliži završetku. Ova metoda sprječava novije stanje spremnog stanja da zadrži završetak starijeg procesa.

Karakteristike metode raspoređivanja SRT -a:

  • Ova se metoda uglavnom primjenjuje u paketnim okruženjima gdje je potrebno dati prednost kratkim poslovima.
  • Ovo nije idealna metoda za implementaciju u dijeljenom sustavu gdje je potrebno vrijeme CPU -a nepoznato.
  • Pridružite se svakom procesu kao duljinu njegova sljedećeg niza CPU -a. Tako da operacijski sustav koristi te duljine, što pomaže u planiranju procesa u najkraćem mogućem vremenu.

Raspored temeljen na prioritetima

Prioritetno raspoređivanje je metoda planiranja procesa na temelju prioriteta. U ovoj metodi raspoređivač odabire zadatke za rad prema prioritetu.

Zakazivanje prioriteta također pomaže OS -u da uključi prioritetne dodjele. Prvo se trebaju provesti procesi s većim prioritetom, dok se poslovi s jednakim prioritetima provode na principu ponavljanja ili FCFS-a. Prioritet se može odlučiti na temelju memorijskih zahtjeva, vremenskih zahtjeva itd.

Round-Robin raspored

Round robin je najstariji, najjednostavniji algoritam planiranja. Naziv ovog algoritma potječe od načela ponavljanja, gdje svaka osoba zauzvrat dobiva jednak udio u nečemu. Najviše se koristi za algoritme raspoređivanja u više zadataka. Ova metoda algoritma pomaže u izvođenju procesa bez gladovanja.

Karakteristike okruglog rasporeda

  • Round robin je hibridni model koji radi na sat
  • Vremenski odsječak trebao bi biti minimalan, koji je dodijeljen za određeni zadatak koji se obrađuje. Međutim, može se razlikovati za različite procese.
  • To je sustav u stvarnom vremenu koji reagira na događaj u određenom vremenskom roku.

Prvo najkraći posao

SJF je potpuni oblik (Najkraći posao najprije) je algoritam za raspoređivanje u kojemu bi proces s najkraćim vremenom izvođenja trebao biti izabran za sljedeće izvršavanje. Ova metoda raspoređivanja može biti preventivna ili nepreventivna. Znatno smanjuje prosječno vrijeme čekanja za druge procese koji čekaju izvršenje.

Karakteristike SJF raspoređivanja

  • Povezan je sa svakim poslom kao jedinicom vremena za dovršetak.
  • U ovoj metodi, kada je CPU dostupan, prvi će se izvesti sljedeći proces ili posao s najkraćim vremenom dovršetka.
  • Provodi se s nepreventivnom politikom.
  • Ova metoda algoritma korisna je za paketnu obradu, gdje čekanje na dovršetak poslova nije kritično.
  • Poboljšava učinak poslova nudeći kraće poslove, koje bi trebalo prvo izvršiti, koji uglavnom imaju kraće vrijeme izvršavanja.

Zakazivanje redova na više razina

Ovaj algoritam odvaja spreman red u različite zasebne redove. U ovoj metodi procesi se dodjeljuju redu na temelju određenog svojstva procesa, poput prioriteta procesa, veličine memorije itd.

Međutim, ovo nije neovisni algoritam OS -a za raspoređivanje jer mora koristiti druge vrste algoritama za planiranje poslova.

Karakteristike raspoređivanja redova na više razina:

  • Za procese s nekim karakteristikama trebalo bi održavati više redova čekanja.
  • Svaki red može imati svoje zasebne algoritme raspoređivanja.
  • Prioriteti se daju svakom redu čekanja.

Svrha algoritma raspoređivanja

Evo razloga za korištenje algoritma zakazivanja:

  • CPU koristi raspoređivanje kako bi poboljšao svoju učinkovitost.
  • Pomaže vam u raspodjeli resursa među konkurentnim procesima.
  • Maksimalna iskoristivost CPU-a može se postići multiprogramiranjem.
  • Procesi koje treba izvršiti su u redu za čekanje.

Sažetak:

  • Raspoređivanje CPU -a je proces određivanja koji će procesor posjedovati CPU za izvršavanje dok je drugi proces na čekanju.
  • U preventivnom rasporedu zadaci se uglavnom dodjeljuju svojim prioritetima.
  • U metodi nepreventivnog planiranja, CPU je dodijeljen određenom procesu.
  • Burst vrijeme je vrijeme potrebno za dovršetak procesa. Također se naziva vrijeme rada.
  • Korištenje CPU -a glavni je zadatak u kojem operacijski sustav mora osigurati da CPU ostane što je moguće zauzetiji
  • Broj procesa koji završe svoje izvršavanje po jedinici vremena poznat je Propusnost.
  • Vrijeme čekanja je iznos koji određeni proces treba čekati u redu čekanja.
  • To je vremenski period u kojem je zahtjev podnesen do dobivanja prvog odgovora.
  • Vrijeme obrade je vrijeme potrebno za izvršavanje određenog procesa.
  • Prekid brojača je metoda koja je usko povezana s prevencijom,
  • Dispečer je modul koji omogućuje kontrolu CPU -a procesu.
  • Šest vrsta algoritama planiranja procesa su:
  • Prvo dođi prvi posluži (FCFS), 2) Raspored najkraćih zadataka (SJF) 3) Najkraće preostalo vrijeme 4) Prioritetno raspoređivanje 5) Round Robin raspoređivanje 6) Višestepeno raspoređivanje redova
  • U metodi First Come First Serve, proces koji traži CPU prvo dobiva dodjelu CPU -a.
  • U najkraćem preostalom vremenu proces će biti dodijeljen zadatku koji je najbliži završetku.
  • U, Raspoređivanje prioriteta, raspoređivač odabire zadatke za rad prema prioritetu.
  • U ovom zaokruženom rasporedu funkcionira u načelu, gdje svaka osoba zauzvrat dobiva jednak udio u nečemu
  • U najkraćem poslu najprije treba izabrati najkraće vrijeme izvođenja
  • U višerazinskom raspoređivanju metoda razdvaja spreman red u različite zasebne redove. U ovoj metodi procesi se dodjeljuju redu na temelju određenog svojstva
  • CPU koristi raspoređivanje kako bi poboljšao svoju učinkovitost.