Prosessorin ajoitus Algorithms in Operating Systems

Suorittimen ajoituksen tyypit

Tässä on kahdenlaisia ​​ajoitusmenetelmiä:

Ennakoiva ajoitus

Ennakoivassa ajoituksessa tehtävät jaetaan enimmäkseen niiden prioriteettien mukaan. Joskus on tärkeää suorittaa korkeamman prioriteetin tehtävä ennen toista alhaisemman prioriteetin tehtävää, vaikka alhaisemman prioriteetin tehtävä olisi edelleen käynnissä. Alemman prioriteetin tehtävä on voimassa jonkin aikaa ja jatkuu, kun korkeamman prioriteetin tehtävä on suorittanut loppuun.

Ei-ennakoiva ajoitus

Tämän tyyppisessä ajoitusmenetelmässä CPU on varattu tietylle prosessille. Prosessi, joka pitää CPU:n kiireisenä, vapauttaa CPU:n joko vaihtamalla kontekstia tai lopettamalla sen. Se on ainoa menetelmä, jota voidaan käyttää eri laitteistoalustoilla. Tämä johtuu siitä, että se ei vaadi erityistä laitteistoa (esimerkiksi ajastinta), kuten ennaltaehkäisevää ajoitusta.

Milloin ajoitus on ennakoivaa vai ei-ennakollista?

Harkitse näitä neljää parametria määrittääksesi, onko ajoitus ennakoivaa vai ei-ennakoivaa:

1. Prosessi siirtyy käynnissä olevasta odotustilaan.
2. Tietty prosessi vaihtaa käynnissä-tilasta valmiustilaan.
3. Tietty prosessi siirtyy odotustilasta valmiustilaan.
4. Prosessi lopetti suorittamisensa ja lopetettiin.

Vain ehdot 1 ja 4 ovat voimassa, ajoitusta kutsutaan ei-ennaltaehkäiseväksi.

Kaikki muut aikataulut ovat ennakoivia.

Tärkeitä suorittimen ajoituksen termejä

• Purskeaika/suoritusaika: Se on aika, jonka prosessi vaatii suorituksen loppuun saattamiseen. Sitä kutsutaan myös ajoajaksi.
• Saapumisaika: kun prosessi siirtyy valmiustilaan
• Loppuaika: kun prosessi on valmis ja poistu järjestelmästä
• Moniohjelmointi: Useita ohjelmia, jotka voivat olla muistissa samanaikaisesti.
• Työpaikat: Se on eräänlainen ohjelma ilman minkäänlaista käyttäjän vuorovaikutusta.
• Käyttäjä: Se on eräänlainen ohjelma, jossa on käyttäjän vuorovaikutusta.
• Prosessi: Se on viite, jota käytetään sekä työlle että käyttäjälle.
• CPU/IO-purskejakso: Kuvaa prosessin suoritusta, joka vuorottelee CPU- ja I/O-toiminnan välillä. CPU-ajat ovat yleensä lyhyempiä kuin I/O-aika.

CPU:n ajoituskriteerit

Suorittimen ajoitusalgoritmi yrittää maksimoida ja minimoida seuraavat asiat:

Maksimoida

CPU: n käyttö:Suorittimen käyttöaste on päätehtävä, jossa käyttöjärjestelmän on varmistettava, että prosessori on mahdollisimman kiireinen. Se voi vaihdella 0 - 100 prosenttia. RTOS-järjestelmän osalta se voi kuitenkin olla 40 prosentista matalan tason ja 90 prosentista korkean tason järjestelmässä.

suoritusteho: Suorituksensa suorittaneiden prosessien määrä aikayksikköä kohti tunnetaan Suorituskyky. Joten kun prosessori on kiireisenä suorittamassa prosessia, työ tehdään tuolloin, ja aikayksikköä kohti tehtyä työtä kutsutaan läpimenokyvyksi.

Minimoida

Odotusaika: Odotusaika on määrä, joka tietyn prosessin on odotettava valmiusjonossa.

Vasteaika: Se on aika, jonka kuluessa pyyntö lähetettiin, kunnes ensimmäinen vastaus saadaan.

Läpimenoaika: Käsittelyaika on aika, joka kuluu tietyn prosessin suorittamiseen. Se on laskelma kokonaisajasta, joka kuluu odottamiseen muistiin pääsyä, jonossa odottamiseen ja suorittimella suoritukseen. Prosessin toimittamisen ja valmistumisajan välinen aika on läpimenoaika.

Intervalliajastin

Ajastinkeskeytys on menetelmä, joka liittyy läheisesti ennaltaehkäisyyn. Kun tietty prosessi saa CPU-allokoinnin, ajastin voidaan asettaa määrätylle aikavälille. Sekä ajastimen keskeytys että ennaltaehkäisy pakottavat prosessin palauttamaan CPU:n ennen kuin sen prosessoripurske on valmis.

Suurin osa moniohjelmoiduista käyttöjärjestelmistä käyttää jonkinlaista ajastinta estämään prosessia sitomasta järjestelmää ikuisesti.

Mikä on Dispatcher?

Se on moduuli, joka ohjaa CPU:ta prosessiin. Dispatcherin tulee olla nopea, jotta se voi toimia jokaisessa kontekstikytkimessä. Lähetysviive on aika, jonka suorittimen ajoitus tarvitsee pysäyttääkseen yhden prosessin ja käynnistääkseen toisen.

Dispatcherin suorittamat toiminnot:

• Kontekstin vaihtaminen
• Vaihtaa käyttäjätilaan
• Siirtyminen oikeaan paikkaan juuri ladatussa ohjelmassa.

Suorittimen ajoitusalgoritmien tyypit

Niitä on pääasiassa kuusi tyyppiä prosessien ajoitusalgoritmit

1. Ensin tullutta palvella (FCFS)
2. Lyhyin työ ensin (SJF) -aikataulu
3. Lyhin jäljellä oleva aika
4. Ensisijainen ajoitus
5. Kierros Robin -aikataulu
6. Monitasoinen jonon ajoitus

Ensin saapunut ensin -palvelu

First Come First Serve on FCFS:n täysi muoto. Se on helpoin ja yksinkertaisin suorittimen ajoitusalgoritmi. Tämän tyyppisessä algoritmissa prosessi, joka pyytää CPU:ta, saa ensin suorittimen allokoinnin. Tätä ajoitusmenetelmää voidaan hallita FIFO-jonon avulla.

Prosessin saapuessa valmiusjonoon, sen PCB (Process Control Block) linkitetään jonon päähän. Joten kun prosessori vapautuu, se tulee osoittaa prosessille jonon alussa.

FCFS-menetelmän ominaisuudet

• Se tarjoaa ennaltaehkäisevän ja ennaltaehkäisevän aikataulutusalgoritmin.
• Työt tehdään aina saapumisjärjestyksessä
• Se on helppo toteuttaa ja käyttää.
• Tämän menetelmän suorituskyky on kuitenkin heikko, ja yleinen odotusaika on melko pitkä.

Lyhin jäljellä oleva aika

SRT:n täysi muoto on Lyhin jäljellä oleva aika. Se tunnetaan myös nimellä SJF ennaltaehkäisevä ajoitus. Tässä menetelmässä prosessi allokoidaan tehtävälle, joka on lähimpänä sen valmistumista. Tämä menetelmä estää uudempaa valmiustilaprosessia säilyttämästä vanhemman prosessin valmistumista.

SRT-aikataulutusmenetelmän ominaisuudet

• Tätä menetelmää käytetään enimmäkseen eräympäristöissä, joissa lyhyille töille on annettava etusija.
• Tämä ei ole ihanteellinen tapa toteuttaa sitä jaetussa järjestelmässä, jossa vaadittua CPU-aikaa ei tunneta.
• Yhdistä jokaiseen prosessiin sen seuraavan prosessoripurskeen pituudeksi. Joten käyttöjärjestelmä käyttää näitä pituuksia, mikä auttaa ajoittamaan prosessin mahdollisimman lyhyessä ajassa.

Priority Based Scheduling

Ensisijainen ajoitus on menetelmä prosessien ajoittamiseen prioriteetin perusteella. Tässä menetelmässä ajoittaja valitsee tehtävät prioriteetin mukaan.

Prioriteetin ajoitus auttaa myös käyttöjärjestelmää sisällyttämään prioriteettitehtäviin. Korkeamman prioriteetin prosessit tulisi suorittaa ensin, kun taas saman prioriteetin työt suoritetaan round-robin- tai FCFS-pohjalta. Prioriteetti voidaan päättää muistivaatimusten, aikavaatimusten jne. perusteella.

Round-Robin-aikataulu

Round robin on vanhin, yksinkertaisin aikataulutusalgoritmi. Tämän algoritmin nimi tulee round-robin-periaatteesta, jossa jokainen saa vuorotellen yhtä suuren osuuden jostakin. Sitä käytetään enimmäkseen algoritmien ajoittamiseen moniajossa. Tämä algoritmimenetelmä auttaa prosessien suorittamisessa ilman nälkää.

Round-Robin-aikataulutuksen ominaisuudet

• Round robin on kellokäyttöinen hybridimalli
• Aikaosuuden tulee olla pienin, joka on varattu tietylle käsiteltävälle tehtävälle. Se voi kuitenkin vaihdella eri prosesseissa.
• Se on reaaliaikainen järjestelmä, joka reagoi tapahtumaan tietyn aikarajan sisällä.

Lyhyin työ ensin

SJF on täysi muoto (lyhyin työ ensin) on ajoitusalgoritmi, jossa lyhimmän suoritusajan omaava prosessi valitaan seuraavaksi suoritettavaksi. Tämä ajoitusmenetelmä voi olla ennaltaehkäisevä tai ei-ennakoiva. Se lyhentää merkittävästi muiden suoritusta odottavien prosessien keskimääräistä odotusaikaa.

SJF-aikataulutuksen ominaisuudet

• Se liitetään kuhunkin työhön valmistumisaikayksikkönä.
• Tässä menetelmässä, kun CPU on käytettävissä, seuraava prosessi tai työ, jonka valmistumisaika on lyhin, suoritetaan ensin.
• Se toteutetaan ei-ennaltaehkäisevällä politiikalla.
• Tämä algoritmimenetelmä on hyödyllinen erätyyppisessä käsittelyssä, jossa töiden valmistumisen odottaminen ei ole kriittistä.
• Se parantaa työn tuottoa tarjoamalla lyhyempiä töitä, jotka tulisi suorittaa ensin ja joilla on useimmiten lyhyempi läpimenoaika.

Monitasoisten jonojen ajoitus

Tämä algoritmi erottaa valmiin jonon useisiin erillisiin jonoihin. Tässä menetelmässä prosessit osoitetaan jonoon prosessin tietyn ominaisuuden, kuten prosessin prioriteetin, muistin koon jne., perusteella.

Tämä ei kuitenkaan ole itsenäinen ajoituskäyttöjärjestelmäalgoritmi, koska sen on käytettävä muun tyyppisiä algoritmeja töiden ajoittamiseen.

Ominaista monitasoisten jonojen ajoitukselle

• Prosesseille, joilla on joitain ominaisuuksia, tulisi ylläpitää useita jonoja.
• Jokaisella jonolla voi olla omat aikataulutusalgoritminsa.
• Jokaiselle jonolle annetaan prioriteetit.

Ajoitusalgoritmin tarkoitus

Tässä ovat syyt ajoitusalgoritmin käyttöön:

• CPU käyttää ajoitusta tehokkuuden parantamiseksi.
• Se auttaa sinua jakamaan resursseja kilpailevien prosessien kesken.
• Suorittimen maksimaalinen käyttöaste voidaan saavuttaa moniohjelmoinnilla.
• Suoritettavat prosessit ovat valmiusjonossa.

Yhteenveto

• Suorittimen ajoitus on prosessi, jossa määritetään, mikä prosessi omistaa suorittimen suoritettaviksi toisen prosessin ollessa pidossa.
• Ennakoivassa ajoituksessa tehtävät jaetaan enimmäkseen niiden prioriteettien mukaan.
• Non-preemptive Scheduling -menetelmässä CPU on allokoitu tietylle prosessille.
• Purskeaika on aika, joka tarvitaan prosessin suorittamiseen loppuun. Sitä kutsutaan myös juoksuajaksi.
• Suorittimen käyttöaste on päätehtävä, jossa käyttöjärjestelmän on varmistettava, että CPU pysyy mahdollisimman kiireisenä.
• Suorituksensa suorittaneiden prosessien määrä aikayksikköä kohti tunnetaan Suorituskyky.
• Odotusaika on määrä, joka tietyn prosessin on odotettava valmiusjonossa.
• Se on aika, jonka kuluessa pyyntö lähetettiin, kunnes ensimmäinen vastaus on saatu.
• Käsittelyaika on aika, joka kuluu tietyn prosessin suorittamiseen.
• Ajastinkeskeytys on menetelmä, joka liittyy läheisesti ennaltaehkäisyyn.
• Välittäjä on moduuli, joka ohjaa prosessin CPU:ta.
• Kuusi tyyppisiä prosessien ajoitusalgoritmeja ovat: FCFS (First Come First Serve), 2) Lyhin-job-First (SJF) -aikataulutus, 3) Lyhin jäljellä oleva aika, 4) Priority Scheduling, 5) Round Robin Scheduling, 6) Monitasoinen jonoajoitus .
• In Ensin tullut ensin -menetelmä, prosessi, joka pyytää CPU:ta, saa ensin suorittimen allokoinnin.
• Lyhyimmässä jäljellä olevassa ajassa prosessi kohdistetaan tehtävään, joka on lähinnä sen valmistumista.
• Priority Schedulingissa ajoittaja valitsee tehtävät prioriteetin mukaan.
• Round robin -aikataulu toimii periaatteella, että jokainen saa vuorollaan yhtä suuren osuuden jostakin.
• Lyhyin työ ensin -kohdassa lyhin suoritusaika tulee valita seuraavaksi suoritettavaksi.
• Monitasoinen ajoitusmenetelmä erottaa valmiin jonon useisiin erillisiin jonoihin. Tässä menetelmässä prosessit osoitetaan jonoon tietyn ominaisuuden perusteella.
• CPU käyttää ajoitusta tehokkuuden parantamiseksi.