CPU ajakava Algorithms in Operating Systems

Mis on protsessori ajastamine?

CPU ajakava on protsess, mille käigus määratakse, milline protsess omab protsessorit täitmiseks, samal ajal kui teine ​​protsess on ootel. Protsessori ajastamise peamine ülesanne on tagada, et kui protsessor jääb jõudeolekusse, valiks operatsioonisüsteem täitmiseks vähemalt ühe valmisoleku järjekorras oleva protsessi. Valikuprotsessi viib läbi protsessori ajastaja, mis valib ühe mälus olevatest täitmiseks valmis protsessidest.

Protsessori ajastamise tüübid

Siin on kahte tüüpi ajakava koostamise meetodeid:

Ennetav ajakava

Ennetava ajastamise puhul määratakse ülesanded enamasti vastavalt nende prioriteetidele. Mõnikord on oluline käivitada kõrgema prioriteediga ülesanne enne madalama prioriteediga ülesannet, isegi kui madalama prioriteediga ülesanne veel töötab. Madalama prioriteediga ülesanne jääb mõnda aega ootele ja jätkub, kui kõrgema prioriteediga ülesanne on oma täitmise lõpetanud.

Mitteennetav ajakava

Seda tüüpi ajastamismeetodi puhul eraldatakse protsessor kindlale protsessile. Protsess, mis hoiab protsessori hõivatuna, vabastab selle kas konteksti vahetamise või lõpetamise teel. See on ainus meetod, mida saab kasutada erinevatel riistvaraplatvormidel, kuna see ei vaja spetsiaalset riistvara (näiteks taimerit) nagu ennetav ajastamine.

Millal on ajakava koostamine ennetav või mitteennetav?

Selleks, et teha kindlaks, kas ajastamine on ennetav või mitteennetav, arvestage järgmiste nelja parameetriga:

1. Protsess lülitub töötavast olekust ooteolekusse.
2. Konkreetne protsess lülitub töötavast olekust valmisolekusse.
3. Konkreetne protsess lülitub ooteolekust valmisolekusse.
4. Protsess lõpetab oma täitmise ja peatub.

Kui kehtivad ainult tingimused 1 ja 4, nimetatakse ajastamist mitte-ennetavaks. Kõik muud ajastamisolukorrad on ennetavad.

Olulised protsessori ajastamise terminid

• Sarivõtte aeg/täitmisaeg: Protsessi täitmiseks kuluv aeg. Seda nimetatakse ka jooksuajaks.
• Saabumise aeg: Aeg, mil protsess läheb valmisolekusse.
• Lõpuaeg: Aeg, mil protsess lõpeb ja süsteemist väljub.
• Multiprogrammeerimine: Mälus võib samaaegselt olla mitu programmi.
• Töökohad: Programmitüüp, mis ei vaja mingit kasutaja sekkumist.
• Kasutaja: Programmitüüp, mis nõuab kasutajalt interaktsiooni.
• Protsess: Viide, mida kasutatakse nii töö kui ka kasutaja jaoks.
• CPU/IO sarivõtte tsükkel: Iseloomustab protsessi täitmist, kus vaheldub protsessori ja sisend-/väljundtegevus. Protsessori ajad on tavaliselt lühemad kui sisend-/väljundajad.

CPU ajastamise kriteeriumid

Protsessori ajastamisalgoritm püüab maksimeerida ja minimeerida järgmist:

Maksimeerima

Protsessori kasutus: Protsessori kasutusaste on peamine ülesanne, mille puhul operatsioonisüsteem peab tagama protsessori maksimaalse hõivatuse. See võib olla vahemikus 0 kuni 100 protsenti. RTOS-i puhul võib see aga olla madala taseme süsteemi puhul 40 protsendist kuni kõrge taseme süsteemi puhul 90 protsendini.

Läbilaskevõime: Protsesside arvu, mis ajaühikus oma täitmise lõpetavad, nimetatakse läbilaskevõimeks. Seega, kui protsessor on protsessi täitmisega hõivatud, tehakse tööd ja ajaühikus tehtud tööd nimetatakse läbilaskevõimeks.

Minimeerima

Ooteaeg: Ooteaeg on aeg, mille jooksul konkreetne protsess peab valmisoleku järjekorras ootama.

Reaktsiooniaeg: See on aeg alates taotluse esitamisest kuni esimese vastuse saamiseni.

Tööaeg: Pöördeaeg on aeg, mis kulub konkreetse protsessi käivitamiseks. See on kogu aeg, mis kulub mällu jõudmiseks ootamisele, järjekorras ootamisele ja protsessoris käivitamisele. Protsessi esitamise ja lõpuleviimise vaheline ajavahemik on pöördeaeg.

Intervallitaimer

Taimeri katkestamine on meetod, mis on tihedalt seotud eelmüügiga. Kui teatud protsess saab CPU jaotuse, võidakse taimer seada määratud intervallile. Nii taimeri katkestamine kui ka eelostmine sunnivad protsessi CPU-d tagastama enne, kui selle protsessori sari on lõppenud.

Enamik mitme programmeerimisega operatsioonisüsteeme kasutab mingisugust taimerit, et vältida protsessi süsteemi igaveseks sidumist.

Mis on dispetšer?

Dispetšer on moodul, mis annab protsessile juhtimist protsessori üle. Dispetšer peaks olema kiire, et see saaks töötada igal kontekstilülitil. Dispetši latentsus on aeg, mis kulub protsessori ajasturil ühe protsessi peatamiseks ja teise käivitamiseks.

Dispetšeri täidetavad funktsioonid:

• Konteksti vahetamine.
• Kasutajarežiimi lülitumine.
• Liikumine äsja laaditud programmis õigesse kohta.

Protsessori ajastamise tüübid Algorithms

Peamiselt on kuus tüüpi protsesside ajastamise algoritmid:

1. Serveerimine „kes ees, mees” (FCFS)
2. Lühim töö esimene (SJF) ajakava
3. Lühim järelejäänud aeg
4. Prioriteetne ajakava
5. Round Robini ajakava
6. Mitmetasandiline järjekorra ajastamine

Plaanimine Algorithms

Serveeri „kes ees, see mees“.

FCFS tähistab Serveeri „kes ees, see mees“.See on lihtsaim ja lihtsam protsessori ajastamisalgoritm. Seda tüüpi algoritmis saab protsessorilt päringu esitanud protsessori jaotuse esimesena. Seda ajastamismeetodit saab hallata FIFO järjekorra abil.

Kui protsess siseneb valmisolekujärjekorda, ühendatakse selle trükkplaat (PCB) järjekorra sabaosaga. Seega, kui protsessor vabaneb, tuleks see määrata järjekorra alguses olevale protsessile.

FCFS-meetodi omadused

• See on mitte-preemptiivne ajastamisalgoritm.
• Tööd täidetakse alati "kes ees, see mees" põhimõttel.
• Seda on lihtne rakendada ja kasutada.
• Selle meetodi jõudlus on aga kehv ja üldine ooteaeg on üsna pikk.

Lühim järelejäänud aeg

SRT täielik vorm on lühim järelejäänud aeg (Shortest Remaining Time). Seda tuntakse ka kui SJF-i ennetavat ajastamist. Selle meetodi puhul eraldatakse protsess ülesandele, mis on selle lõpuleviimisele kõige lähemal. See meetod hoiab ära uuema valmisoleku protsessi poolt vanema protsessi lõpuleviimise takistamise.

SRT ajastamismeetodi omadused

• Seda meetodit rakendatakse enamasti partiitöötluskeskkondades, kus tuleb eelistada lühikesi töid.
• See ei ole ideaalne meetod jagatud süsteemis rakendamiseks, kus vajalik protsessori aeg pole teada.
• Iga protsess on seotud selle järgmise protsessori koormuse pikkusega, seega kasutab operatsioonisüsteem neid pikkusi protsessi ajastamiseks võimalikult lühikese ajaga.

Prioriteedipõhine ajakava

Prioriteetne ajakava on prioriteedil põhineva protsesside ajastamise meetod. Selle meetodi puhul valib ajastaja ülesanded, millega töötada, vastavalt nende prioriteedile.

Prioriteetide ajastamine aitab operatsioonisüsteemil kaasata ka prioriteetide määramist. Kõrgema prioriteediga protsessid viiakse läbi esimesena, samas kui sama prioriteediga tööd viiakse läbi ringjada või FCFS-i põhimõttel. Prioriteedi saab määrata mäluvajaduse, ajavajaduse ja muude tegurite põhjal.

Round-Robini ajakava

Round robin on üks vanimaid ja lihtsamaid ajastamisalgoritme. Selle algoritmi nimi tuleneb ringintervalli põhimõttest, kus iga inimene saab kordamööda millestki võrdse osa. Seda kasutatakse enamasti mitme ülesandega süsteemide ajastamiseks. See meetod aitab saavutada protsesside nälgimiseta täitmist.

Round-Robini ajakava omadused

• Round robin on hübriidmudel, mis töötab kella graafikul.
• Konkreetse ülesande töötlemiseks määratud ajaviil peaks olema minimaalne. See võib aga eri protsesside puhul erineda.
• See käitub nagu ajajagamissüsteem, mis reageerib igale protsessile kindla aja jooksul.

Esmalt lühim töö

SJF (Shortest Job First) on ajastamisalgoritm, mille puhul järgmisena täitmiseks valitakse lühima täitmisajaga protsess. See ajastamismeetod võib olla ennetav või mitte-ennetav. See vähendab oluliselt teiste täitmist ootavate protsesside keskmist ooteaega.

SJF ajakava omadused

• Iga töö on seotud ajaühikuga, mis selle täitmiseks kulub.
• Selle meetodi puhul, kui protsessor on saadaval, käivitatakse kõigepealt järgmine lühima valmimisajaga protsess või töö.
• Seda rakendatakse mitte-ennetava poliitikaga.
• See algoritm on kasulik partiitüüpi töötlemiseks, kus tööde lõpuleviimise ootamine pole kriitilise tähtsusega.
• See parandab töötulemusi, teostades esmalt lühemaid töid, millel on enamasti lühem teostusaeg.

Mitmetasandiliste järjekordade ajastamine

See algoritm jagab valmisoleku järjekorra mitmeks eraldi järjekorraks. Selle meetodi puhul määratakse protsessid järjekorda protsessi konkreetse omaduse, näiteks protsessi prioriteedi, mälu suuruse jne alusel.

See ei ole aga iseseisev ajastamisalgoritm, kuna tööde ajastamiseks peab see kasutama teist tüüpi algoritme.

Mitmetasandilise järjekordade ajastamise omadused

• Ühiste omadustega protsesside jaoks tuleks säilitada mitu järjekorda.
• Igal järjekorral võib olla oma eraldi ajastamisalgoritm.
• Igale järjekorrale määratakse prioriteedid.

Ajastusalgoritmi eesmärk

Siin on ajastamisalgoritmi kasutamise põhjused.

• CPU kasutab oma tõhususe parandamiseks ajastamist.
• See aitab teil ressursse konkureerivate protsesside vahel jaotada.
• Protsessori maksimaalset kasutamist saab saavutada multiprogrammeerimisega.
• Käivitatavad protsessid hoitakse valmisoleku järjekorras.

KKK