CPU raspoređivanje Algorithms in Operating sustavi

Što je CPU Scheduling?

CPU raspoređivanje je proces određivanja koji će proces posjedovati CPU za izvršavanje dok je drugi proces na čekanju. Glavni zadatak raspoređivanja CPU-a je osigurati da, kad god CPU ostane neaktivan, OS odabere barem jedan od procesa dostupnih u redu čekanja za izvršenje. Proces odabira provodi raspoređivač CPU-a, koji odabire jedan od procesa u memoriji koji su spremni za izvršenje.

Vrste CPU rasporeda

Evo dvije vrste metoda raspoređivanja:

Preventivno planiranje

U preventivnom raspoređivanju, zadaci su uglavnom dodijeljeni s njihovim prioritetima. Ponekad je važno pokrenuti zadatak s višim prioritetom prije drugog zadatka nižeg prioriteta, čak i ako se zadatak nižeg prioriteta još uvijek izvršava. Zadatak nižeg prioriteta zadržava se neko vrijeme i nastavlja se kada zadatak višeg prioriteta završi s izvršavanjem.

Nepreventivno zakazivanje

U ovoj vrsti metode raspoređivanja, CPU se dodjeljuje određenom procesu. Proces koji drži CPU zauzetim oslobodit će ga promjenom konteksta ili prekidom. To je jedina metoda koja se može koristiti na različitim hardverskim platformama, jer ne treba poseban hardver (na primjer, timer) kao preventivno raspoređivanje.

Kada je zakazivanje preventivno ili nepreventivno?

Kako biste utvrdili je li raspoređivanje preventivno ili nepreemptivno, uzmite u obzir ova četiri parametra:

1. Proces se prebacuje iz stanja rada u stanje čekanja.
2. Određeni proces prelazi iz stanja izvođenja u stanje spremnosti.
3. Određeni proces prelazi iz stanja čekanja u stanje spremnosti.
4. Proces završava svoje izvršavanje i završava.

Ako se primjenjuju samo uvjeti 1 i 4, raspoređivanje se naziva nepreemptivnim. Sve ostale situacije raspoređivanja su preemptivne.

Važne terminologije za raspoređivanje CPU-a

• Vrijeme pucanja/vrijeme izvršenja: Vrijeme potrebno procesu za dovršetak izvršenja. Također se naziva vrijeme izvođenja.
• Vrijeme dolaska: Vrijeme kada proces ulazi u stanje spremnosti.
• Vrijeme završetka: Vrijeme kada se proces završi i sustav izađe iz njega.
• Multiprogramiranje: Više programa koji mogu biti prisutni u memoriji istovremeno.
• Poslovi: Vrsta programa bez ikakve interakcije s korisnikom.
• Korisnik: Vrsta programa koji ima interakciju s korisnikom.
• Proces: Referenca koja se koristi i za posao i za korisnika.
• CPU/IO burst ciklus: Karakterizira izvršavanje procesa, koje se izmjenjuje između aktivnosti procesora i ulazno/izlaznih aktivnosti. Vrijeme CPU-a je obično kraće od vremena ulazno/izlaznih operacija.

CPU kriteriji rasporeda

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

Povećali

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

Propusnost: Broj procesa koji završe svoje izvršavanje po jedinici vremena poznat je kao propusnost. Dakle, kada je CPU zauzet izvršavanjem procesa, obavlja se posao, a posao završen po jedinici vremena naziva se propusnost.

Umanjiti

Vrijeme čekanja: Vrijeme čekanja je vrijeme koje određeni proces mora čekati u redu čekanja.

Vrijeme odziva: To je vrijeme od trenutka kada je zahtjev poslan do trenutka kada je dobiven prvi odgovor.

Vrijeme obrade: Vrijeme izvršenja je vrijeme potrebno za izvršavanje određenog procesa. To je ukupno vrijeme čekanja na ulazak u memoriju, čekanja u redu čekanja i izvršavanja na CPU-u. Razdoblje između vremena slanja procesa i vremena završetka je vrijeme izvršenja.

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šeprogramskih operativnih sustava koristi neku vrstu timera kako bi spriječili da proces trajno blokira sustav.

Što je dispečer?

Dispečer je modul koji procesu omogućuje kontrolu nad CPU-om. Dispečer bi trebao biti brz kako bi se mogao pokrenuti na svakoj promjeni konteksta. Latencija dispečera je vrijeme potrebno raspoređivaču CPU-a da zaustavi jedan proces i pokrene drugi.

Funkcije koje obavlja dispečer:

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

Vrste CPU rasporeda Algorithms

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

Zakazivanje Algorithms

First Come First Serve

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

Kako proces ulazi u red čekanja, njegov PCB (blok upravljanja procesom) povezan je s repom reda. Dakle, kada se CPU oslobodi, treba ga dodijeliti procesu na početku reda.

Karakteristike FCFS metode

• To je nepreemptivni 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 poznat kao SJF preventivno raspoređivanje. U ovoj metodi, proces će biti dodijeljen zadatku koji je najbliži njegovom dovršetku. Ova metoda sprječava da noviji proces u stanju spremnosti zadrži dovršetak starijeg procesa.

Karakteristike metode raspoređivanja SRT-a

• Ova se metoda uglavnom primjenjuje u serijskim okruženjima gdje je potrebno dati prednost kratkim poslovima.
• Ovo nije idealna metoda za implementaciju u dijeljenom sustavu gdje je potrebno CPU vrijeme nepoznato.
• Svaki proces je povezan s duljinom sljedećeg CPU burst-a, pa operativni sustav koristi te duljine za planiranje procesa s najkraćim mogućim vremenom.

Zakazivanje na temelju prioriteta

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

Raspoređivanje prioriteta također pomaže OS-u da uključi dodjelu prioriteta. Procesi s višim prioritetom izvršavaju se prvi, dok se poslovi s jednakim prioritetima izvršavaju kružnim postupkom ili FCFS-om. Prioritet se može odrediti na temelju memorijskih zahtjeva, vremenskih zahtjeva i drugih čimbenika.

Round-robin raspored

Razigravanje je jedan od najstarijih i najjednostavnijih algoritama za raspoređivanje. Naziv ovog algoritma dolazi od principa kružnog raspoređivanja, gdje svaka osoba redom dobiva jednak udio nečega. Uglavnom se koristi za raspoređivanje u multitasking sustavima. Ova metoda pomaže u postizanju izvršavanja procesa bez gladovanja.

Karakteristike Round-Robin rasporeda

• Kružni sistem je hibridni model koji se pokreće taktom.
• Vremenski isječak dodijeljen za obradu određenog zadatka trebao bi biti minimalan. Međutim, može varirati ovisno o procesu.
• Ponaša se poput sustava dijeljenja vremena koji odgovara na svaki proces unutar određenog vremenskog ograničenja.

Prvo najkraći posao

SJF (Shortest Job First - Najkraći posao prvo) je algoritam raspoređivanja u kojem se proces s najkraćim vremenom izvršavanja odabire za sljedeće izvršenje. Ova metoda raspoređivanja može biti preemptivna ili nepreemptivna. Značajno smanjuje prosječno vrijeme čekanja za druge procese koji čekaju na izvršenje.

Karakteristike SJF rasporeda

• Svaki posao povezan je s jedinicom vremena koju treba dovršiti.
• U ovoj metodi, kada je CPU dostupan, prvo se izvršava sljedeći proces ili zadatak s najkraćim vremenom završetka.
• Provodi se nepreventivnom politikom.
• Ovaj algoritam je koristan za obradu u serijama, gdje čekanje na dovršetak poslova nije kritično.
• Poboljšava učinak izvršavanjem kraćih poslova prvo, koji uglavnom imaju kraće vrijeme obrade.

Višerazinsko zakazivanje čekanja

Ovaj algoritam dijeli red čekanja u nekoliko zasebnih redova. U ovoj metodi, procesi se dodjeljuju redu na temelju određenog svojstva procesa, kao što su prioritet procesa, veličina memorije i tako dalje.

Međutim, ovo nije neovisni algoritam raspoređivanja, jer za raspoređivanje poslova treba koristiti druge vrste algoritama.

Karakteristike raspoređivanja redova čekanja na više razina

• Za procese sa zajedničkim karakteristikama treba održavati više redova čekanja.
• Svaki red može imati svoj vlastiti algoritam raspoređivanja.
• Prioriteti se dodjeljuju svakom redu čekanja.

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 u raspodjeli resursa među konkurentskim procesima.
• Maksimalno iskorištenje CPU-a može se postići multiprogramiranjem.
• Procesi koji se trebaju izvršiti čuvaju se u redu čekanja.

Pitanja i odgovori