Sissejuhatus operatsioonisüsteemidesse
Tere Habr! Juhin teie tähelepanu artiklite sarjale-tõlketele ühest minu arvates huvitavast kirjandusest - OSTEP. Selles materjalis käsitletakse üsna põhjalikult unixi-laadsete operatsioonisüsteemide tööd, nimelt tööd protsesside, erinevate ajakavade, mälu ja muude sarnaste komponentidega, mis moodustavad kaasaegse OS-i. Kõikide materjalide originaale näed siit . Pange tähele, et tõlge on tehtud ebaprofessionaalselt (üsna vabalt), kuid loodan, et säilitasin üldise tähenduse.
Selle teema laboritööd leiate siit:
Muud osad:
Võite vaadata ka minu kanalit aadressil =)
Planeerimine: mitmetasandiline tagasiside järjekord
Selles loengus räägime ühe tuntuima lähenemisviisi väljatöötamise probleemidest
planeerimine, mida nimetatakse Mitmetasandiline tagasiside järjekord (MLFQ). MLFQ planeerijat kirjeldas esmakordselt 1962. aastal Fernando J. Corbató süsteemis nn.
Ühilduv ajajagamissüsteem (CTSS). Need tööd (kaasa arvatud hilisemad tööd
Multics) nimetati seejärel Turingi auhinna kandidaadiks. Planeerija oli
hiljem täiustatud ja omandanud välimuse, mida võib juba leida
mõned kaasaegsed süsteemid.
MLFQ algoritm püüab lahendada 2 põhilist kattuvat probleemi.
Esiteks, püüab see optimeerida pöördeaega, mida, nagu eelmises loengus arutasime, optimeeritakse kõige rohkem järjekorra algusest alustamise meetodiga.
lühikesed ülesanded. OS aga ei tea, kui kaua see või teine protsess kestab ja see
vajalikud teadmised SJF, STCF algoritmide tööks. Teiseks, MLFQ proovib
muuta süsteem kasutajate jaoks tundlikuks (näiteks nende jaoks, kes istuvad ja
vaadake ekraani, oodates ülesande täitmist) ja minimeerige seega aega
vastuseks. Kahjuks vähendavad sellised algoritmid nagu RR reageerimisaega, kuid
avaldavad töötlemisaja mõõdikule halba mõju. Siit ka meie probleem: kuidas kujundada
planeerija, mis vastab meie nõuetele ja samal ajal ei tea sellest midagi
protsessi olemus üldiselt? Kuidas saab planeerija õppida ülesannete omadusi,
mille see käivitab ja teeb seega paremaid sõiduplaani otsuseid?
Probleemi olemus: Kuidas planeerida ülesannete püstitamist ilma täiuslike teadmisteta?
Kuidas koostada ajakava, mis samaaegselt minimeerib reageerimisaega
interaktiivsete ülesannete jaoks ja minimeerib samal ajal teadmata tööaega
teadmised ülesande täitmise ajast?
Märkus: õppimine eelmistest sündmustest
MLFQ järjekord on suurepärane näide süsteemist, mida õpetatakse
minevikusündmused, et ennustada tulevikku. Sellised lähenemisviisid on sageli
leitud OS-is (ja paljudes teistes arvutiteaduse harudes, sealhulgas filiaalides
riistvaraennustused ja vahemällu salvestamise algoritmid). Sarnased matkad
käivitada, kui ülesannetel on käitumisfaasid ja need on seega etteaimatavad.
Selle tehnikaga tuleks aga ettevaatlik olla, sest ennustamine on väga lihtne.
võib osutuda valeks ja viia süsteemi halvemate otsusteni kui
oleks üldse teadmisteta.
MLFQ: põhireeglid
Mõelge MLFQ-algoritmi põhireeglitele. Ja kuigi selle algoritmi teostused
neid on mitu, põhilised lähenemisviisid on sarnased.
Kaalutletavas teostuses on MLFQ-l mitu
eraldi järjekorrad, millest igaühel on erinev prioriteet. igal ajal,
täitmiseks valmis ülesanne on samas järjekorras. MLFQ kasutab prioriteete,
otsustada, millise ülesande täitmiseks kandideerida, s.t. ülesanne kõrgemaga
prioriteet (kõrgeima prioriteediga ülesanne järjekorrast) käivitatakse esimesena
järjekorda.
Muidugi võib antud järjekorras olla rohkem kui üks ülesanne, seega
seega on neil sama prioriteet. Sel juhul kasutatakse mehhanismi
RR nende ülesannete hulgas käivitamise planeerimise eest.
Seega jõuame MLFQ kahe põhireeglini:
- Reegel 1: kui prioriteet (A) > prioriteet (B), käivitub ülesanne A (B mitte)
- Reegel 2: kui prioriteet (A) = prioriteet (B), käivitatakse A&B RR abil
Ülaltoodu põhjal on MLFQ planeerimise põhielemendid
on prioriteedid. Selle asemel, et anda igaühele kindel prioriteet
ülesande puhul muudab MLFQ oma prioriteeti sõltuvalt vaadeldavast käitumisest.
Näiteks kui toiming sulgub pidevalt CPU-st, oodates klaviatuuri sisendit,
MLFQ hoiab protsessi prioriteedina kõrge, sest nii
interaktiivne protsess peaks toimima. Kui vastupidi, ülesanne on pidevalt ja
on pikka aega protsessorimahukas, siis MLFQ alandab selle versiooni
prioriteet. Seega uurib MLFQ protsesside käitumist nende töötamise ajal
ja kasutada käitumist.
Toome näite, millised võivad järjekorrad ühel hetkel välja näha
aega ja siis saad midagi sellist:
Selles skeemis on 2 protsessi A ja B kõrgeima prioriteediga järjekorras. Protsess
C on kuskil keskel ja protsess D on järjekorra lõpus. Eeltoodu kohaselt
MLFQ-algoritmi kirjeldusi, täidab planeerija ainult kõrgeima väärtusega ülesandeid
prioriteet vastavalt RR-ile ning ülesanded C, D jäävad tööta.
Loomulikult ei anna staatiline hetktõmmis täielikku pilti MLFQ toimimisest.
Oluline on täpselt mõista, kuidas pilt aja jooksul muutub.
1. katse: kuidas prioriteeti muuta
Siinkohal peate otsustama, kuidas MLFQ prioriteeditaset muudab
ülesanne (ja seega ka ülesande asukoht järjekorras) selle elutsükli jooksul. Sest
sellest peate meeles pidama töövoogu: teatud summa
interaktiivsed ülesanded lühikese tööajaga (ja seega sagedase vabastamisega
CPU) ja mitu pikka ülesannet, mis kasutavad protsessorit kogu tööaja
selliste ülesannete reageerimisaeg ei ole oluline. Ja nii saate teha esimese katse
Rakendage MLFQ-algoritmi järgmiste reeglitega:
- Reegel 3: kui ülesanne siseneb süsteemi, asetatakse see kõige kõrgema ülesandega järjekorda
- prioriteet.
- Reegel 4a: kui ülesanne kasutab kogu oma ajaakent, siis see
- prioriteet on langetatud.
- Reegel 4b: kui ülesanne vabastab protsessori enne ajaakna aegumist, siis see
- jääb sama prioriteediga.
Näide 1: Üks pikaajaline ülesanne
Nagu sellest näitest näha, on vastuvõtuülesanne seatud kõrgeima väärtusega
prioriteet. Pärast 10 ms pikkust ajavahemikku vähendatakse protsessi prioriteetsust
planeerija. Pärast järgmist ajaakent viiakse ülesanne lõpuks alla versioonile
süsteemi madalaim prioriteet, kuhu see jääb.
Näide 2: valisin lühikese ülesande
Vaatame nüüd näidet, kuidas MLFQ proovib SJF-ile läheneda. Selles
Näiteks kaks ülesannet: A, mis on pidevalt pikaajaline ülesanne
hõivavad CPU ja B, mis on lühike interaktiivne ülesanne. Oletame
et A oli ülesande B saabumise ajaks juba mõnda aega jooksnud.
See graafik näitab stsenaariumi tulemusi. Ülesanne A, nagu iga ülesanne,
CPU kasutamine oli kõige põhjas. Ülesanne B saabub ajal T=100 ja saabub
asetatakse kõrgeima prioriteediga järjekorda. Kuna tööaeg on lühike,
see lõpeb enne viimase järjekorda jõudmist.
Sellest näitest peaksite mõistma algoritmi peamist eesmärki: kuna algoritm seda ei tee
teab pikka või lühikest ülesannet, siis ennekõike eeldab, et ülesanne
lühike ja annab sellele kõrgeima prioriteedi. Kui see on tõesti lühike ülesanne, siis
see täidetakse kiiresti, vastasel juhul, kui see on pikk ülesanne, liigub see aeglaselt
eelisjärjekorras ja varsti tõestab, et ta on tõepoolest pikk ülesanne, mis seda ei tee
nõuab vastust.
Näide 3: Aga I/O?
Vaatame nüüd I/O näidet. Nagu on öeldud reeglis 4b,
kui protsess vabastab protsessori, ilma et oleks oma protsessori aega täielikult ära kasutanud,
siis jääb see samale prioriteetsuse tasemele. Selle reegli eesmärk on üsna lihtne.
- kui interaktiivne töö sooritab palju I/O-d, näiteks ootab
kasutaja klahvivajutustest või hiirest vabastab selline ülesanne protsessori
enne määratud akent. Me ei tahaks sellist prioriteetset ülesannet tegemata jätta,
ja seega jääb see samale tasemele.
See näide näitab, kuidas algoritm selliste protsessidega töötab - interaktiivne ülesanne B, mis vajab CPU-d ainult 1 ms enne käivitamist
I/O protsess ja pikaajaline töö A, mis kulutab kogu oma aja protsessorit kasutades.
MLFQ hoiab protsessi B kõrgeima prioriteedina, kuna see jätkub
vabastage CPU. Kui B on interaktiivne ülesanne, siis on antud juhul algoritm jõudnud
selle eesmärk on interaktiivsete ülesannete kiire käivitamine.
Probleemid praeguse MLFQ algoritmiga
Eelmistes näidetes oleme loonud MLFQ põhiversiooni. Ja tundub, et ta
teeb oma tööd hästi ja õiglaselt, jaotades protsessori aja õiglaselt
pikad ülesanded ja lühikeste või raskesti ligipääsetavate ülesannete lubamine
I/O-sse, et kiiresti töödelda. Kahjuks sisaldab see lähenemisviis mitmeid
tõsiseid probleeme.
Esiteks, näljaprobleem: kui süsteemis on palju interaktiivseid
ülesandeid, kulutavad nad kogu protsessori aja ja seega mitte ühtegi pikka aega
ülesannet ei täideta (nad nälgivad).
Teiseks, nutikad kasutajad võiksid oma programme kirjutada nii, et
ajakava koostaja lolliks. Pettus seisneb selles, et tehakse midagi selleks, et sundida
planeerija, et anda protsessile rohkem protsessori aega. Algoritm, mis
ülalkirjeldatud on selliste rünnakute suhtes üsna haavatav: enne ajaaken on praktiliselt
pärast, peate sooritama I / O toimingu (mõnedele, olenemata sellest, mis failist)
ja vabastab seega CPU. Selline käitumine võimaldab teil jääda samaks
järjekord ise ja jällegi saada suurem protsent CPU ajast. Kui tehtud
see on õige (nt käivitage 99% akna ajast enne CPU vabastamist),
selline ülesanne võib protsessori lihtsalt monopoliseerida.
Lõpuks võib programm oma käitumist aja jooksul muuta. Need ülesanded
mis kasutasid CPU-d, võivad muutuda interaktiivseks. Meie näites sarnane
ülesandeid ei käsitle ajakava koostaja korralikult, nagu teised seda teeksid
(originaal) interaktiivsed ülesanded.
Küsimus publikule: milliseid rünnakuid planeerija vastu võiks tänapäeva maailmas teha?
2. katse: suurendage prioriteeti
Proovime reegleid muuta ja vaatame, kas suudame probleeme vältida
nälgimine. Mida saame teha, et tagada seos
CPU ülesanded saavad oma aja (isegi kui mitte kaua).
Probleemi lihtsa lahendusena võite perioodiliselt soovitada
tõsta kõigi selliste ülesannete prioriteetsust süsteemis. Võimalusi on palju
selle saavutamiseks proovime rakendada näitena midagi lihtsat: tõlkida
kõik ülesanded korraga kõrgeima prioriteediga, seega uus reegel:
- Reegel5: Pärast teatud perioodi S teisaldage kõik süsteemis olevad ülesanded kõrgeimasse järjekorda.
Meie uus reegel lahendab kaks probleemi korraga. Esiteks protsessid
garanteeritud, et ei jää nälga: kõrgeimas järjekorras olevad ülesanded jagatakse
protsessori aeg vastavalt RR algoritmile ja seega saavad kõik protsessid
protsessori aeg. Teiseks, kui mõni protsess, mida varem kasutati
ainult protsessor muutub interaktiivseks, jääb see kõrgeima järjekorda
prioriteet pärast ühekordse tõuke saamist kõrgeimale prioriteedile.
Kaaluge näidet. Selle stsenaariumi korral kaaluge ühe protsessi kasutamist
CPU ja kaks interaktiivset lühikest protsessi. Joonisel vasakul on kujutatud käitumist ilma prioriteetse edutamiseta ja seega hakkab kaua kestnud ülesanne pärast kahe interaktiivse ülesande süsteemi saabumist nälgima. Parempoolsel joonisel toimub prioriteedi tõstmine iga 50 ms järel ja seega on garanteeritud, et kõik protsessid saavad CPU aega ja neid käivitatakse perioodiliselt. Antud juhul on näiteks võetud 50 ms, tegelikkuses on see arv veidi suurem.
On ilmne, et perioodilise tõusuaja S liitmine toob kaasa
loogiline küsimus: milline väärtus tuleks määrata? Üks väljateenitud
süsteemiinsenerid John Outterhout viitasid sarnastele kogustele süsteemides kui voo-doo
konstantne, kuna nad mingil moel nõudsid õigeks musta maagiat
kokkupuude. Ja kahjuks on S-l selline maitse. Kui määrate ka väärtuse
suured - pikad ülesanded jäävad nälga. Ja kui määrate selle liiga madalaks,
Interaktiivsed ülesanded ei saa õiget protsessori aega.
Katse 3: parem raamatupidamine
Nüüd on meil lahendada veel üks probleem: kuidas mitte
Kas lubada meie planeerijat petta? Selle võimaluse süüdlased on
reeglid 4a, 4b, mis lubavad protsessori vabastamisega töö prioriteedi säilitada
enne määratud aja möödumist. Kuidas sellega toime tulla?
Lahenduseks võib sel juhul pidada paremat CPU aja arvestamist igaühe jaoks
MLFQ tase. Selle asemel, et unustada programmi kasutatud aeg
protsessor määratud intervalli jaoks, peaksite seda arvesse võtma ja salvestama. Pärast
protsess on oma määratud aja ära kasutanud, tuleks see järgmisele alandada
prioriteetsuse tase. Nüüd pole vahet, kuidas protsess oma aega kasutab – kuidas
pidevalt protsessoris või kõnede komplektina. Seega
reegel 4 tuleks ümber kirjutada järgmiselt:
- Reegel4: pärast seda, kui ülesanne on praeguses järjekorras oma eraldatud aja ära kasutanud (olenemata sellest, mitu korda see on CPU-d vabastanud), vähendatakse sellise ülesande prioriteetsust (see liigub järjekorras allapoole).
Vaatame näidet:
»
Joonisel on näha, mis juhtub, kui proovite ajakava koostajat petta
kui see oleks koos eelmiste reeglitega 4a, oleks 4b tulemus vasakul. Uuega
reegel on, et tulemus on paremal. Enne kaitsmist võib mis tahes protsess kutsuda sisend-/väljundi enne lõpetamist ja
seega domineerivad protsessoris pärast kaitse lubamist, olenemata käitumisest
I/O, ta läheb ikka järjekorda ega saa seega ebaausalt teha
võtta üle protsessori ressursse.
MLFQ ja muude probleemide parandamine
Ülaltoodud täiustustega tekivad uued probleemid: üks peamisi
Küsimused – kuidas sellist planeerijat parameetritesse seada? Need. Kui palju peaks olema
järjekorrad? Kui suur peaks olema järjekorras olev programmiaken? Kuidas
programm tuleks sageli prioriteediks seada, et vältida nälgimist ja
et võtta arvesse programmi käitumise muutust? Nendele küsimustele pole lihtsat
vastus ja ainult katsed koormustega ja sellele järgneva konfiguratsiooniga
planeerija võib viia mõne rahuldava tasakaaluni.
Näiteks võimaldab enamik MLFQ-rakendusi määrata erinevaid
ajapilud erinevate järjekordade jaoks. Tavaliselt on kõrge prioriteediga järjekorrad
lühikesed intervallid. Need järjekorrad koosnevad interaktiivsetest ülesannetest,
mille vahel ümberlülitamine on üsna tundlik ja peaks kestma 10 või vähem
Prl. Seevastu madala prioriteediga järjekorrad koosnevad kauakestvatest ülesannetest, mis kasutavad
PROTSESSOR. Ja sellisel juhul sobivad pikad ajaintervallid väga hästi (100ms).
Selles näites on kõrge prioriteediga järjekorras 2 töötanud 20 ülesannet
ms jagatud 10 ms akendeks. 40 ms keskmises järjekorras (20 ms aken) ja madala prioriteediga järjekorras
järjekorra ajaakna pikkus oli 40 ms, kus ülesanded lõpetasid oma töö.
MLFQ juurutamine Solarise OS-is on ajajagatud planeerijate klass.
Planeerija pakub tabelite komplekti, mis määratlevad täpselt, kuidas see peaks olema
muuta protsessi prioriteeti selle eluea jooksul, milline peaks olema suurus
eraldatav aken ja ülesannete prioriteetide tõstmise sagedus. Administraator
süsteem saab selle tabeliga suhelda ja ajakava käituma panna
erinevalt. Vaikimisi on selles tabelis 60 järkjärgulise suurenemisega järjekorda
akna suurus 20 ms (kõrge prioriteet) kuni mitmesaja ms (madala prioriteediga) ja
ka kõigi ülesannete kiirendusega üks kord sekundis.
Teised MLFQ-planeerijad ei kasuta tabelit ega ühtegi konkreetset
selles peatükis kirjeldatud reeglid, vastupidi, nad arvutavad prioriteete kasutades
matemaatilised valemid. Näiteks FreeBSD planeerija kasutab valemit
praeguse ülesande prioriteedi arvutamine selle põhjal, kui palju protsess on
kasutas protsessorit. Lisaks mädaneb protsessori kasutus aja jooksul ja seega
Seega on prioriteedi tõstmine mõnevõrra erinev ülalkirjeldatust. See on tõsi
mida nimetatakse lagunemisalgoritmideks. Alates versioonist 7.1 kasutab FreeBSD ULE planeerijat.
Lõpuks on paljudel planeerijatel muid funktsioone. Näiteks mõned
planeerijad reserveerivad operatsioonisüsteemi tööks kõrgemad tasemed ja seega
Seega ei saa ükski kasutajaprotsess omada kõrgeimat prioriteeti
süsteem. Mõned süsteemid võimaldavad teil abi anda
planeerija oskab prioriteete õigesti seada. Näiteks käsu abil kena
saate ülesande prioriteetsust suurendada või vähendada ja seeläbi suurendada või vähendada
vähendage programmi võimalusi protsessori aja jaoks.
MLFQ: kokkuvõte
Oleme kirjeldanud planeerimismeetodit nimega MLFQ. Tema nimi
sõlmitud tööpõhimõttes - sellel on mitu järjekorda ja kasutatakse tagasisidet
ülesande prioritiseerimiseks.
Reeglite lõplik vorm on järgmine:
- Reegel1: Kui prioriteet(A) > Prioriteet(B), käivitub ülesanne A (B mitte)
- Reegel2: Kui prioriteet (A) = prioriteet (B), käivitatakse A&B RR abil
- Reegel3: kui ülesanne siseneb süsteemi, asetatakse see kõrgeima prioriteediga järjekorda.
- Reegel4: pärast seda, kui ülesanne on praeguses järjekorras oma eraldatud aja ära kasutanud (olenemata sellest, mitu korda see on CPU-d vabastanud), vähendatakse sellise ülesande prioriteetsust (see liigub järjekorras allapoole).
- Reegel5: Pärast teatud perioodi S teisaldage kõik süsteemis olevad ülesanded kõrgeimasse järjekorda.
MLFQ on huvitav järgmisel põhjusel - selle asemel, et nõuda teadmisi
ülesande olemust eelnevalt õpib algoritm ülesande varasema käitumise ja komplektide kohta
prioriteedid vastavalt. Seega püüab ta istuda kahel toolil korraga – saavutada jõudlust väikeste ülesannete puhul (SJF, STCF) ja ausalt joosta pikki,
Protsessori laadimise tööd. Seetõttu on paljud süsteemid, sealhulgas BSD ja nende derivaadid,
Solaris, Windows ja Mac kasutavad planeerijana mingit algoritmi
MLFQ kui lähtejoon.
Lisateave:
- (arvutamine)
Allikas: www.habr.com