Destpêka Pergalên Xebatê
Hey Habr! Ez dixwazim rêzek gotar-wergerên yek wêjeya balkêş bi nerîna min - OSTEP-ê bînim ber çavên we. Ev materyal bi kûrahî li ser xebata pergalên xebitandinê yên mîna unix-ê nîqaş dike, ango, xebata bi pêvajoyên, plansazkerên cihêreng, bîranîn û hêmanên din ên mîna ku OS-ya nûjen pêk tînin. Hûn dikarin orîjînala hemî materyalan li vir bibînin . Ji kerema xwe bala xwe bidin ku werger bi rengek neprofesyonel (gelek serbest) hatîye kirin, lê ez hêvî dikim ku min wateya giştî parastiye.
Xebatên laboratîfê yên li ser vê mijarê li vir têne dîtin:
Parçeyên din:
Hûn dikarin li kanala min jî temaşe bikin =)
Plankirin: Rêza Bersiva Pir-Asta
Di vê dersê de, em ê li ser pirsgirêkên pêşxistina yek ji nêzîkatiyên herî navdar biaxivin
plankirin, ku tê gotin Dora Bersiva Pir-Asta (MLFQ). Plansaziya MLFQ yekem car di sala 1962 de ji hêla Fernando J. Corbató ve di pergalek bi navê
Pergala Parvekirina Demjimêra Hevaheng (CTSS). Van xebatan (tevlî karên paşîn ên li ser
Multics) paşê ji bo Xelata Turing hatin berbijêrkirin. Rêvebir bû
dûv re çêtir bû û xuyangê ku jixwe tê de tê dîtin bi dest xist
hin sîstemên modern.
Algorîtmaya MLFQ hewl dide ku 2 pirsgirêkên bingehîn ên hevgirtî çareser bike.
Yekem, ew hewl dide ku dema zivirînê xweşbîn bike, ya ku, wekî me di dersên berê de behs kir, bi rêbaza ku herî zêde di serê rêzê de dest pê dike tê xweşbîn kirin.
karên kurt. Lêbelê, OS-ê nizane ev an ew pêvajo dê kengî bimeşîne, û ev
zanîna pêwîst ji bo xebata SJF, algorîtmayên STCF. Duyemîn, MLFQ hewl dide
pergalê ji bo bikarhêneran bersivdar bikin (mînak, ji bo yên ku rûniştin û
dema ku li benda qedandina peywirê ye) li ekranê mêze dike û bi vî rengî demê kêm dike
bersiv. Mixabin, algorîtmayên mîna RR dema bersivê kêm dikin, lê
bandorek xirab li ser metrika dema zivirandinê heye. Ji ber vê yekê pirsgirêka me: Meriv çawa sêwiran dike
plansazker ku dê daxwazên me bicîh bîne û di heman demê de tiştek jê nizane
xwezaya pêvajoyê, bi giştî? Çawa plansaz dikare taybetmendiyên karan fêr bibe,
ya ku ew dest pê dike û bi vî rengî biryarên plansazkirinê çêtir digire?
Esasê pirsgirêkê: Meriv çawa bêyî zanîna bêkêmasî sazkirina peywiran plan dike?
Meriv çawa plansaziyek ku di heman demê de dema bersivê kêm dike sêwirîne
ji bo karên înteraktîf û di heman demê de bêyî ku bizanibe dema zivirîn kêm dike
zanîna dema pêkanîna peywirê?
Nîşe: fêrbûna ji bûyerên berê
Rêza MLFQ mînakek hêja ya pergalek ku li ser tê perwerde kirin e
bûyerên berê ji bo pêşbînîkirina pêşerojê. Nêzîkatiyên wiha gelek caran hene
di OS-ê de tê dîtin (Û gelek şaxên din ên di zanistiya komputerê de, tevî şax
pêşbîniyên hardware û algorîtmayên cachkirinê). rêwîtiyên manend
dema ku peywir xwedî qonaxên behrê ne û bi vî rengî pêşbîn in, diqewime.
Lêbelê, divê meriv bi vê teknîkê baldar be, ji ber ku pêşbînkirin pir hêsan in.
dibe ku xelet derkeve û pergalê rê bide ku biryarên xirabtir bide
dê qet bê zanîn be.
MLFQ: Rêbazên bingehîn
Qaîdeyên bingehîn ên algorîtmaya MLFQ bifikirin. Û her çend pêkanînên vê algorîtmê
çend hene, nêzîkatiyên bingehîn dişibin hev.
Di pêkanîna ku em ê bifikirin, MLFQ dê gelek hebin
rêzikên cuda, ku her yek ji wan dê pêşanîyek cûda hebe. Herdem,
karê ji bo îdamê amade ye di heman dorê de ye. MLFQ pêşînan bikar tîne,
ku biryarê bide ka kîjan peywirê ji bo darvekirinê bimeşîne, yanî. peywira bi bilindtir
pêşîn (xebatek ji rêzê ya bi pêşengiya herî bilind) dê di yekem de were destpêkirin
mar.
Bê guman, dibe ku di rêzek taybetî de ji yekê zêdetir peywir hebe, lewra
ji ber vê yekê ew ê xwedî heman pêşîn bin. Di vê rewşê de, mekanîzma dê bikar bînin
RR ji bo plansazkirina destpêkirinê di nav van karan de.
Bi vî rengî em digihîjin du qaîdeyên bingehîn ji bo MLFQ:
- Qanûn 1: Ger pêşanî (A) > Pêşanî (B), karê A dê bimeşe (B nabe)
- Rêbaz2: Ger pêşanî (A) = Pêşanî (B), A&B bi karanîna RR-ê dest pê dike
Li ser bingeha jorîn, hêmanên sereke yên plansazkirina MLFQ ne
pêşanî ne. Li şûna ku ji her yekê re pêşîniyek diyarkirî bidin
peywirê, MLFQ pêşaniya xwe li gorî tevgera çavdêriyê diguhezîne.
Mînakî, heke dema ku li benda têketina klavyeyê ye, peywirek bi berdewamî ji CPU-yê derkeve,
MLFQ dê pêşaniya pêvajoyê bilind bihêle ji ber ku bi vî rengî ye
pêvajoya înteraktîf divê bixebite. Ger, berevajî, peywira berdewam û
ji bo demek dirêj CPU zexm e, MLFQ dê wê dakêşîne
pêşînek. Bi vî rengî, MLFQ dê tevgera pêvajoyên di dema ku ew dimeşînin de lêkolîn bike.
û tevgeran bikar bînin.
Werin em mînakek xêz bikin ka rêzan di hin xalan de çawa dibe
dem û paşê hûn tiştek wekî vê yekê bistînin:
Di vê nexşeyê de, 2 pêvajoyên A û B di rêza bi pêşîniya herî bilind de ne. Doz
C li deverek navîn e, û pêvajoya D di dawiya rêzê de ye. Li gora jorîn
danasînên algorîtmaya MLFQ, plansazker dê tenê karan bi ya herî bilind pêk bîne
pêşanî li gorî RR, û peywirên C, D dê ji kar derkevin.
Bi xwezayî, wêneyek statîk dê wêneyek bêkêmasî ya çawa MLFQ dixebite nede.
Girîng e ku meriv tam fêm bike ka wêne bi demê re çawa diguhere.
Hewldan 1: Meriv çawa pêşîniyê biguhezîne
Di vê nuqteyê de, hûn hewce ne ku biryar bidin ka MLFQ dê asta pêşîn çawa biguhezîne
peywir (û bi vî rengî pozîsyona peywirê di dorê de) di dema çerxa jiyana xwe de. Bo
ji vê yekê, hûn hewce ne ku hûn rêça xebatê li ber çavan bigirin: mîqdarek diyar
karên înteraktîf ên bi demên xebitandinê yên kurt (û bi vî rengî berdana pir caran
CPU) û çend karên dirêj ên ku CPU-yê hemî dema xebata xwe bikar tînin, dema
dema bersivdayînê ji bo karên weha ne girîng e. Û vî awayî hûn dikarin hewldana yekem bikin
algorîtmaya MLFQ bi qaîdeyên jêrîn bicîh bikin:
- Qanûn3: Dema ku peywirek dikeve pergalê, ew di rêza herî bilind de tê danîn
- pêşeyî.
- Rule4a: Ger peywirek tevahiya paceya dema xwe bikar bîne, wê hingê ew
- pêşanî kêm dibe.
- Rule4b: Ger Peywirek CPU-yê berî ku pencereya dema wê biqede berde, wê hingê ew
- bi heman pêşanî dimîne.
Nimûne 1: Karê dirêj-rêvebera yekane
Wekî ku hûn di vê nimûneyê de dibînin, peywira di pejirandinê de bi ya herî bilind tête danîn
pêşeyî. Piştî pencereyek demkî 10ms, pêvajo di pêşanî de tê daxistin.
scheduler. Piştî pencereya dema din, peywir di dawiyê de tê daxistin
herî kêm pêşanî di sîstemê de, ku ew dimîne.
Mînak 2: Karekî kurt hilgirt
Naha em mînakek bibînin ka MLFQ dê çawa hewl bide ku nêzîkê SJF bibe. Di wê de
Nimûne, du peywir: A, ku karekî demdirêj berdewam e
dagirkirina CPU û B, ku karekî înteraktîf kurt e. Bawerkirin
ku A jixwe dema ku peywira B hat demek dirêj bû.
Ev graf encamên senaryoyê nîşan dide. Karê A, mîna her karekî,
karanîna CPU-ê di binê jêrîn de bû. Karê B dê di dema T=100 de bigihîje û dê bibe
di rêza pêşîn a herî bilind de tê danîn. Ji ber ku dema xebatê kurt e,
ew ê berî ku ew bigihîje rêza paşîn temam bibe.
Ji vê nimûneyê, divê hûn armanca sereke ya algorîtmayê fêm bikin: ji ber ku algorithm nake
karekî dirêj yan jî kin dizane, paşê berî her tiştî ew wezîfe dihesibîne
kurt e û ew dide pêşaniya herî bilind. Ger ew bi rastî karekî kurt e, hingê
ew ê zû cîbicî bike, wekî din heke ew karek dirêj be ew ê hêdî bimeşe
di pêşiyê de ye û dê di demek nêzîk de îspat bike ku ew bi rastî karekî dirêj e ku nake
bersivek hewce dike.
Mînak 3: Di derbarê I/O de çi?
Niha em li mînakek I/O binêrin. Wekî ku di qaîdeya 4b de tê gotin,
heke pêvajoyek bêyî ku dema xwe ya pêvajoyê bi tevahî bikar bîne, pêvajoyê berdide,
hingê ew di heman asta pêşîn de dimîne. Armanca vê qaîdeyê pir hêsan e.
- heke karê înteraktîf gelek I/O pêk tîne, mînakî, li benda
ji lêdana bişkojka bikarhêner an mişkê, karek wusa dê pêvajoyê azad bike
berî pencereya diyarkirî. Em naxwazin karekî weha pêşîn ji dest berdin,
û bi vî awayî wê di heman astê de bimîne.
Ev mînak nîşan dide ka dê çawa algorîtma bi pêvajoyên weha re bixebite - peywira înteraktîf B, ya ku berî darvekirinê tenê ji bo 1ms CPU hewce dike
Pêvajoya I/O û karekî dirêj A, ku her dem CPU bikar tîne.
MLFQ ji ber ku ew berdewam dike pêvajoya B di pêşîniya herî bilind de digire
CPU serbest berdin. Ger B karekî înteraktîf e, wê hingê algorîtma di vê rewşê de gihîştiye
armanca wê ew e ku zû karên înteraktîf bide destpêkirin.
Pirsgirêkên bi algorîtmaya MLFQ ya heyî
Di mînakên berê de, me guhertoyek bingehîn a MLFQ ava kiriye. Û ew xuya dike ku ew
karê xwe baş û bi dadperwerî dike, dema CPU-ê bi dadwerî di navberê de belav dike
karên dirêj û destûrê dide karên kurt an karên ku bi giranî têne gihîştin
ji bo I/O ji bo pêvajoyê bi lez. Mixabin, ev nêzîkatî gelek hene
pirsgirêkên cidî.
Yekem, Pirsgirêka birçîbûnê: heke pergalê dê gelek înteraktîf hebe
peywiran, ew ê hemî wextê CPU-yê bixwin û bi vî rengî ne yek dirêj
wezîfe dê firsenda îdamkirinê nebîne (birçîne).
Duyemîn, bikarhênerên jîr dikaribûn bernameyên xwe wisa binivîsin
plansazker bixapînin. Xapandin di kirina tiştekî de ji bo zorê ye
plansazker ku pêvajoyê bêtir wextê CPU bide. Algorîtmaya ku
li jor hatî behs kirin ji êrîşên weha re pir xeternak e: berî ku pencereya demê bi pratîkî ye
li ser, hûn hewce ne ku operasyonek I / O bikin (ji hinan re, ne girîng e kîjan pelê)
û bi vî awayî CPU azad bikin. Tevgerek wusa dê dihêle hûn di heman demê de bimînin
dorê bixwe û dîsa rêjeyek mezin a dema CPU-yê bistînin. Ger kirin
ev rast e (mînak. 99% ji dema pencereyê berî ku CPU-yê azad bike)
karekî weha bi hêsanî dikare pêvajoyên yekdestdar bike.
Di dawiyê de, bernameyek dikare bi demê re tevgera xwe biguherîne. Wan karan
ku CPU bikar tîne dikare bibe înteraktîf. Di nimûneya me de, wekhev
peywir dê ji plansazker dermankirina rast wernegirin, wekî yên din dê
(esîl) karên înteraktîf.
Pirs ji temaşevanan re: Di cîhana nûjen de çi êrîşên li ser plansazker dikarin bêne kirin?
Hewldan 2: Pêşîniyê zêde bikin
Werin em hewl bidin ku qaîdeyan biguhezînin û bibînin ka em dikarin ji pirsgirêkan dûr bisekinin
ji naza mirin. Em dikarin çi bikin da ku ew têkildar piştrast bikin
Karên CPU dê wextê xwe bistînin (tevî ku ne dirêj be).
Wekî çareseriyek hêsan a pirsgirêkê, hûn dikarin demkî pêşniyar bikin
pêşîniya hemî karên weha di pergalê de zêde bikin. Gelek rê hene
ji bo bidestxistina vê, em hewl bidin ku wekî mînakek tiştek hêsan bicîh bikin: werger
Hemî peywir bi yekcarî berbi pêşîniya herî bilind ve diçin, ji ber vê yekê qaîdeya nû:
- Qanûn 5: Piştî demek S, hemî peywirên pergalê veguhezînin rêza herî bilind.
Rêbaza me ya nû di carekê de du pirsgirêkan çareser dike. Pêşîn, pêvajoyên
garantî kirin ku birçî nemînin: karên di rêza herî bilind de dê parve bikin
dema pêvajoyê li gorî algorîtmaya RR-ê û bi vî rengî dê hemî pêvajo bistînin
dema processor. Ya duyemîn, heke hin pêvajoyek ku berê hatî bikar anîn
tenê pêvajo înteraktîf dibe, ew ê di rêza herî bilind de bimîne
pêşanî piştî ku carek pêvekek ji bo pêşîniya herî bilind werdigire.
Nimûneyek bifikirin. Di vê senaryoyê de, pêvajoyek yekane bikar bînin
CPU û du pêvajoyên înteraktîf, kurt. Li milê çepê di jimarê de, jimar behreyê bêyî zêdekirina pêşîn nîşan dide, û bi vî rengî peywira dirêj-dirêj piştî ku du karên înteraktîf digihîjin pergalê dest bi birçîbûnê dike. Di jimareya rastê de, her 50 ms zêdebûnek pêşîn tê kirin û bi vî rengî hemî pêvajo garantî ye ku dema pêvajoyê werbigire û dê bi awayekî periyodîk dest pê bike. Di vê rewşê de 50 ms wek mînak tê girtin, di rastiyê de ev hejmar hinekî zêdetir e.
Eşkere ye ku zêdekirina dema rabûna perîyodîk S dibe sedema
pirsa mentiqî: çi nirx divê were danîn? Yek ji wan ên hêja
endezyarên pergalê John Ousterhout di pergalan de mîqdarên wekhev wekî voo-doo binav kirin
domdar, ji ber ku ew bi rengekî ji bo rast sêhra reş hewce ne
tûşbûn. Û, mixabin, S xwedan çêjek wusa ye. Ger hûn nirxê jî destnîşan bikin
karên mezin - dirêj dê birçî bimînin. Û heke hûn wê pir nizm bikin,
karên înteraktîf dê dema CPU-ya rast nestînin.
Hewldan 3: Hesabkirina çêtir
Naha pirsgirêkek me ya din heye ku em çareser bikin: çawa neyê
destûrê dide ku plansazkarê me bixapîne? Sûcdarên vê îhtîmalê ne
qaîdeyên 4a, 4b ku destûrê didin karek ku bi azadkirina pêvajoyê pêşîya xwe bigire
berî bidawîbûna dema diyarkirî. Meriv çawa pê re mijûl dibe?
Di vê rewşê de çareserî dikare li ser her yekê hesabek çêtir a dema CPU were hesibandin
asta MLFQ. Li şûna ku dema bernameyê bikar anîn ji bîr bikin
processor ji bo navberê veqetandî, divê hûn wê hesab bikin û hilînin. Piştî
pêvajoyê dema xwe ya diyarkirî bi kar aniye, divê ji bo ya din were daxistin
asta pêşîn. Niha ne girîng e ku pêvajo dê çawa wextê xwe bikar bîne - çawa
bi berdewamî li ser pêvajoyê an wekî komek bangan hesab dike. Ji ber vê yekê,
Qanûna 4 divê bi vî awayî ji nû ve were nivîsandin:
- Qanûn 4: Piştî ku peywirek dema xwe ya veqetandî di rêza heyî de bi kar anî (bêyî ku ew çend caran CPU azad kir), pêşaniya karekî weha kêm dibe (ew di rêzê de diçe xwarê).
Ka em li mînakekê binêrin:
»
Hêjmar nîşan dide ka çi diqewime heke hûn hewl bidin ku plansazker mîna bixapînin
eger ew bi qaîdeyên berê 4a bûya, 4b dê encam li çepê be. Bi nû
hukm e ku encam li ser rast e. Berî parastinê, her pêvajo dikare berî qedandinê bangî I/O bike û
Bi vî rengî CPU-yê serdest bikin, piştî ku parastinê çalak bike, bêyî ku behreyê bigire
Ez/O, ew ê dîsa jî bikeve rêzê û bi vî rengî dê nikaribe bêrûmet bike
çavkaniyên CPU bigirin.
Başkirina MLFQ û pirsgirêkên din
Bi pêşveçûnên jorîn, pirsgirêkên nû derdikevin: yek ji sereke
pirs - meriv çawa bernameyek weha parameterîze dike? Ewan. Divê çiqas be
dorên? Divê mezinahiya pencereya bernameyê di nav rêzê de çi be? Çawa
divê pir caran bername were pêşanî kirin da ku ji birçîna û birçîbûnê dûr nekevin
ji bo guhertina tevgera bernameyê bihesibînin? Ji bo van pirsan, ne hêsan e
bersiv û tenê ceribandinên bi bargiran û veavakirina paşîn
scheduler dikare bibe sedema hin hevsengiya têrker.
Mînakî, piraniya pêkanînên MLFQ dihêlin ku hûn cihêreng bidin
slots dem ji bo dorên cuda. Rêzên pêşîn ên bilind bi gelemperî ne
navberên kurt. Van rêzan ji karên înteraktîf pêk tên,
veguhertina di navbera ku pir hesas e û divê 10 an kêmtir bigire
ms. Berevajî vê, rêzikên kêm-pêşeng ji karên dirêj-dirêj ên ku bikar tînin pêk tê
CPU. Û di vê rewşê de, navberên demdirêj pir baş çêdibin (100ms).
Di vê nimûneyê de, 2 peywir hene ku di rêza pêşîn 20 de xebitîne
ms di pencereyên 10ms de têne dabeş kirin. 40 ms di rêza navîn (paceya 20 ms) û di rêza pêşîniya nizm de
pencereya dema rêzê bû 40ms ku peywiran karê xwe qedand.
Pêkanîna MLFQ-ê di Solaris OS-ê de çînek plansazkerên parvekirina demê ye.
Plansaz dê komek tabloyan peyda bike ku tam çawa divê diyar bike
pêşîniya pêvajoyê di heyama jiyana wê de biguhezîne, mezinahî çi be
pencereya ku were veqetandin û çend caran meriv pêşengên peywirê bilind bike. Birêvebir
pergal dikare bi vê tabloyê re têkilî daynin û plansazker tevbigerin
cuda. Ji hêla xwerû ve, vê tabloyê 60 rêz bi zêdebûna gav bi gav heye
Mezinahiya pencereyê ji 20ms (pêşengiya bilind) heya çend sed ms (pêşiya herî kêm), û
di heman demê de bi zêdekirina hemî karan di saniyeyekê de.
Plansazên MLFQ yên din tabloyek an tiştek taybetî bikar nakin
qaîdeyên ku di vê beşê de têne vegotin, berevajî vê yekê, ew bi karanîna pêşînan hesab dikin
formulên matematîkî. Mînakî, plansazker di FreeBSD de formulek bikar tîne
hesabkirina pêşîniya peywira heyî li gorî pêvajoyê çiqasî ye
CPU bikar anîn. Digel vê yekê, karanîna CPU bi demê re xirab dibe, û bi vî rengî
Ji ber vê yekê, zêdebûna pêşîn ji ya ku li jor hatî destnîşan kirin hinekî cûda ye. Ev rast e
algorîtmayên rizîbûnê tê gotin. Li gorî guhertoya 7.1, FreeBSD nexşerêya ULE bikar tîne.
Di dawiyê de, gelek planker taybetmendiyên din hene. Ji bo nimûne, hinek
plansazker astên bilindtir ji bo xebata pergala xebitandinê vedigirin û bi vî rengî
Ji ber vê yekê, ti pêvajoyek bikarhêner nikare pêşîya herî bilind bigire
sîstem. Hin pergal dihêlin ku hûn ji bo alîkariyê şîretan bidin
plansazker bi rêkûpêk pêşengiyê bike. Mînakî, fermanê bikar tîne xweşik
hûn dikarin pêşîniya karekî zêde bikin an kêm bikin û bi vî rengî zêde bikin an kêm bikin
şansê bernameyê ji bo dema CPU kêm bike.
MLFQ: Kurte
Me nêzîkatiyek plansaziyê ya bi navê MLFQ şirove kiriye. Navê wî
di prensîba operasyonê de hate encamdan - ew çend rêz hene û bertek bikar tîne
pêşî li karekî girtin.
Forma dawî ya qaîdeyan dê wiha be:
- Qanûn 1: Ger pêşanî (A) > Pêşanî (B), karê A dê bimeşe (B nabe)
- Qanûn 2: Heke pêşanî (A) = Pêşanî (B), A&B bi karanîna RR dest pê kirin
- Qanûn 3: Dema ku karek dikeve pergalê, ew di rêza pêşîn a herî bilind de tê danîn.
- Qanûn 4: Piştî ku peywirek dema xwe ya veqetandî di rêza heyî de bi kar anî (bêyî ku ew çend caran CPU azad kir), pêşaniya karekî weha kêm dibe (ew di rêzê de diçe xwarê).
- Qanûn 5: Piştî demek S, hemî peywirên pergalê veguhezînin rêza herî bilind.
MLFQ ji ber sedema jêrîn balkêş e - li şûna ku hewcedariya zanînê li ser bike
cewherê peywirê di pêş de, algorîtm tevgera paşîn a peywirê fêr dibe û saz dike
pêşanî li gorî. Bi vî rengî, ew hewl dide ku yekcar li ser du kursî rûne - ji bo karên piçûk (SJF, STCF) performansê bi dest bixe û yên dirêj bi dilpakî dimeşîne,
Karên barkirina CPU. Ji ber vê yekê, gelek pergalên, di nav de BSD û derhênerên wan,
Solaris, Windows, Mac hin formên algorîtmayê wekî plansaz bikar tînin
MLFQ wekî bingehek bingehîn.
Дополльные материалы:
- (kompîtur)
Source: www.habr.com