CPU raspoređivanje Algorithms in Operating sustavi

Vrste CPU rasporeda

Ovdje su dvije vrste metoda zakazivanja:

Preventivno planiranje

U Preemptive Scheduling, zadaci su uglavnom dodijeljeni sa 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 tijeku. Zadatak nižeg prioriteta zadržava se neko vrijeme i nastavlja kada zadatak višeg prioriteta završi s izvršenjem.

Nepreventivno zakazivanje

U ovoj vrsti metode raspoređivanja, CPU je dodijeljen određenom procesu. Proces koji drži CPU zauzet će osloboditi CPU ili promjenom konteksta ili prekidom. 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) kao što je preventivno raspoređivanje.

Kada je zakazivanje preventivno ili nepreventivno?

Da biste odredili je li raspoređivanje preventivno ili ne, razmotrite ova četiri parametra:

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

Primjenjuju se samo uvjeti 1 i 4, raspored se naziva nepreventivnim.

Svi drugi rasporedi su preventivni.

Važna terminologija CPU rasporeda

• Vrijeme pucanja/vrijeme izvršenja: To je vrijeme potrebno procesu za dovršetak izvršenja. Naziva se i vrijeme trajanja.
• Vrijeme dolaska: kada proces uđe u stanje spremnosti
• Vrijeme završetka: kada proces završi i izađe iz sustava
• Multiprogramiranje: Nekoliko programa koji mogu biti prisutni u memoriji u isto vrijeme.
• Poslovi: To je vrsta programa bez ikakve interakcije s korisnikom.
• Korisnik: To je vrsta programa koji ima interakciju s korisnikom.
• Proces: To je referenca koja se koristi i za posao i za korisnika.
• CPU/IO burst ciklus: Karakterizira izvršenje procesa, koje se izmjenjuje između CPU i I/O aktivnosti. CPU vremena su obično kraća od vremena I/O.

CPU kriteriji rasporeda

CPU algoritam za raspoređivanje pokušava maksimizirati i minimizirati sljedeće:

Povećali

Iskorištenje CPU-a:Iskorištenje CPU-a je glavni zadatak u kojem operativni sustav treba osigurati da CPU ostane što je moguće više zauzet. Može se kretati od 0 do 100 posto. Međutim, za RTOS, može biti u rasponu od 40 posto za sustav niske razine i 90 posto za sustav visoke razine.

Propusnost: Broj procesa koji završe svoje izvršenje po jedinici vremena je poznata propusnost. Dakle, kada je CPU zauzet izvršavanjem procesa, u to vrijeme se obavlja posao, a posao dovršen po jedinici vremena naziva se propusnost.

Umanjiti

Vrijeme čekanja: Vrijeme čekanja je količina koju određeni proces treba čekati u redu čekanja.

Vrijeme odziva: To je vrijeme u kojem je zahtjev podnesen do prvog odgovora.

Vrijeme obrade: Vrijeme obrade je količina vremena za izvršenje određenog procesa. To je izračun ukupnog vremena provedenog čekanja da se uđe u memoriju, čekanja u redu i izvršavanja na CPU-u. Razdoblje između vremena podnošenja procesa i vremena završetka je vrijeme obrade.

Intervalni mjerač vremena

Prekidanje mjerača vremena je metoda koja je usko povezana s preemptionom. Kada određeni proces dobije CPU alokaciju, mjerač vremena može se postaviti na određeni interval. I prekid mjerača vremena i preemption prisiljavaju proces da vrati CPU prije nego što završi njegov CPU burst.

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

Što je dispečer?

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

Funkcije koje obavlja dispečer:

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

Vrste CPU algoritama za raspoređivanje

Postoji uglavnom šest vrsta algoritmi za raspoređivanje procesa

1. Prvi dođe prvi posluži (FCFS)
2. Najkraći posao prvi (SJF) Planiranje
3. Najkraće preostalo vrijeme
4. Prioritetno raspoređivanje
5. Round Robin raspored
6. Višerazinsko zakazivanje čekanja

First Come First Serve

First Come First Serve puni je oblik FCFS-a. To je najlakši i najjednostavniji CPU algoritam za raspoređivanje. U ovoj vrsti algoritma, proces koji zahtijeva CPU prvi dobiva CPU alokaciju. Ovom metodom raspoređivanja može se upravljati pomoću FIFO reda čekanja.

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

Karakteristike FCFS metode

• Nudi ne-preemptivni i preventivni algoritam raspoređivanja.
• Poslovi se uvijek izvršavaju po načelu tko prvi dođe, prvi poslužen
• Jednostavan je za implementaciju i korištenje.
• Međutim, ova metoda ima lošu izvedbu, a općenito vrijeme čekanja je prilično dugo.

Najkraće preostalo vrijeme

Puni oblik SRT-a je najkraće preostalo vrijeme. Također je poznato kao SJF preventivno raspoređivanje. U ovoj metodi, proces će biti dodijeljen zadatku koji je najbliži njegovom završetku. Ova metoda sprječava da novi proces stanja spremnosti zadrži završetak starijeg procesa.

Karakteristike SRT metode raspoređivanja

• Ova se metoda uglavnom primjenjuje u serijskim okruženjima gdje se mora dati prednost kratkim poslovima.
• Ovo nije idealna metoda za implementaciju u zajedničkom sustavu gdje je potrebno CPU vrijeme nepoznato.
• Povežite sa svakim procesom kao duljinu njegovog sljedećeg CPU praska. Tako da operativni sustav koristi ove duljine, što pomaže u planiranju procesa u najkraćem mogućem vremenu.

Zakazivanje na temelju prioriteta

Prioritetno raspoređivanje je metoda raspoređivanja procesa na temelju prioriteta. U ovoj metodi, planer odabire zadatke koji će raditi prema prioritetu.

Prioritetno raspoređivanje također pomaže OS-u da uključi dodjele prioriteta. Procesi s višim prioritetom trebaju se provesti prvi, dok se poslovi s jednakim prioritetima provode na kružnoj ili FCFS osnovi. Prioritet se može odrediti na temelju memorijskih zahtjeva, vremenskih zahtjeva itd.

Round-robin raspored

Round robin je najstariji, najjednostavniji algoritam za raspoređivanje. Naziv ovog algoritma dolazi od kružnog principa, gdje svaka osoba dobiva jednaki dio nečega zauzvrat. Uglavnom se koristi za raspoređivanje algoritama u multitaskingu. Ova metoda algoritma pomaže u izvršavanju procesa bez izgladnjivanja.

Karakteristike Round-Robin rasporeda

• Round robin je hibridni model koji pokreće sat
• Vremenski odsječak treba biti minimalan, koji je dodijeljen određenom zadatku koji treba obraditi. Međutim, može varirati za različite procese.
• To je sustav u stvarnom vremenu koji reagira na događaj unutar određenog vremenskog ograničenja.

Prvo najkraći posao

SJF je puni oblik (Prvo najkraći posao) algoritma za raspoređivanje u kojem proces s najkraćim vremenom izvršenja treba biti odabran za sljedeće izvršenje. Ova metoda raspoređivanja može biti preventivna ili nepreventivna. Značajno smanjuje prosječno vrijeme čekanja za druge procese koji čekaju na izvršenje.

Karakteristike SJF rasporeda

• Povezan je sa svakim poslom kao jedinica vremena koje treba izvršiti.
• U ovoj metodi, kada je CPU dostupan, prvi će se izvršiti sljedeći proces ili posao s najkraćim vremenom završetka.
• Provodi se s politikom bez prevencije.
• Ova metoda algoritma korisna je za serijsku obradu, gdje čekanje da se poslovi završe nije kritično.
• Poboljšava učinak posla nudeći kraće poslove, koji bi se trebali izvršiti prvi, a koji uglavnom imaju kraće vrijeme obrade.

Višerazinsko zakazivanje čekanja

Ovaj algoritam razdvaja spremni red u različite zasebne redove. U ovoj metodi, procesi se dodjeljuju redu čekanja na temelju specifičnog svojstva procesa, kao što je prioritet procesa, veličina memorije itd.

Međutim, ovo nije neovisni algoritam operativnog sustava za raspoređivanje jer treba koristiti druge vrste algoritama kako bi rasporedio poslove.

Karakteristike rasporeda čekanja na više razina

• Trebalo bi održavati višestruke redove čekanja za procese s nekim karakteristikama.
• Svaki red čekanja može imati svoje zasebne algoritme za raspoređivanje.
• Prioriteti su dani za svaki red.

Svrha algoritma za raspoređivanje

Evo razloga za korištenje algoritma za zakazivanje:

• CPU koristi raspoređivanje kako bi poboljšao svoju učinkovitost.
• Pomaže vam raspodijeliti resurse između konkurentskih procesa.
• Maksimalno iskorištenje CPU-a može se postići višestrukim programiranjem.
• Procesi koji se trebaju izvršiti nalaze se u redu čekanja.

rezime

• CPU raspoređivanje je proces određivanja koji će proces posjedovati CPU za izvršavanje dok je drugi proces na čekanju.
• U Preemptive Scheduling, zadaci su uglavnom dodijeljeni sa svojim prioritetima.
• U metodi rasporeda bez prednosti, CPU je dodijeljen određenom procesu.
• Vrijeme praska je vrijeme potrebno da proces završi izvršenje. Naziva se i vrijeme trajanja.
• Iskorištenje CPU-a glavni je zadatak u kojem operativni sustav treba osigurati da CPU ostane što je moguće više zauzet.
• Broj procesa koji završe svoje izvršenje po jedinici vremena je poznata propusnost.
• Vrijeme čekanja je količina koju određeni proces treba čekati u redu čekanja.
• To je vrijeme u kojem je zahtjev podnesen do prvog odgovora.
• Vrijeme obrade je količina vremena za izvršenje određenog procesa.
• Prekidanje mjerača vremena je metoda koja je usko povezana s preemptionom.
• Dispečer je modul koji procesu omogućuje kontrolu CPU-a.
• Šest vrsta algoritama za raspoređivanje procesa su: First Come First Serve (FCFS), 2) Shortest-Job-First (SJF) Scheduling, 3) Shortest Remaining Time, 4) Priority Scheduling, 5) Round Robin Scheduling, 6) Multilevel Queue Scheduling .
• u First Come First Serve metoda, proces koji zahtijeva CPU prvi dobiva CPU alokaciju.
• U najkraćem preostalom vremenu, proces će biti dodijeljen zadatku koji je najbliži njegovom završetku.
• U Priority Scheduling, planer odabire zadatke koji će raditi prema prioritetu.
• Round robin raspored funkcionira na principu gdje svaka osoba dobiva jednaki dio nečega zauzvrat.
• U Shortest job first, najkraće vrijeme izvršenja treba biti odabrano za sljedeće izvršenje.
• Metoda raspoređivanja na više razina odvaja spremni red čekanja u različite zasebne redove. U ovoj metodi procesi se dodjeljuju redu čekanja na temelju određenog svojstva.
• CPU koristi raspoređivanje kako bi poboljšao svoju učinkovitost.