Ievads operētājsistēmās

Sveiki, Habr! Vēlos iepazīstināt jūs ar rakstu sēriju - tulkojumiem par vienu interesantu literatūru - OSTEP. Šajā materiālā tiek apskatīta diezgan dziļa unix līdzīgu operētājsistēmu darbība, proti, darbs ar procesiem, dažādiem plānotājiem, atmiņu un citiem līdzīgiem komponentiem, kas veido mūsdienu OS. Oriģinālu materiālu varat skatīt šeit šeit. Lūdzu, ņemiet vērā, ka tulkojums veikts neprofesionāli (īpaši brīvi), taču ceru, ka esmu saglabājis kopējo nozīmi.

Laboratorijas darbus par šo tēmu var atrast šeit:

Citas daļas:

Un jūs varat apmeklēt manu kanālu Telegram =)

Plānošana: Multi-Level Feedback Queue

Šajā lekcijā mēs runāsim par vienu no vispazīstamākajiem pieejām plānošanai, kas tiek saukta par
Multi-Level Feedback Queue (MLFQ). Pirmo reizi MLFQ plānotājs tika aprakstīts 1962. gadā Fernando J. Corbató sistēmā, kas tika saukta par Compatible Time-Sharing System (CTSS). Šie darbi (ieskaitot vēlākos darbus pie
Multics) tika vēlāk izvirzīti Turing balvai. Plānotājs tika
vēlāk uzlabots un ieguva formu, ko var sastapt jau mūsdienu sistēmās.
MLFQ algoritms cenšas atrisināt divas pamatšūnas, kas krustojas.
Tas mēģina optimizēt apgrozījuma laiku, kā mēs apskatījām iepriekšējā lekcijā, optimizējot ar metodi, kas sākumā ievieto visīsākās

uzdevumus rindā. Tomēr, OS nezina, cik ilgi darbosies konkrēts process, un tas ir
Pirmkārtnepieciešams zināšanas SJF, STCF algoritmu darbībai.
MLFQ mēģina
padarīt sistēmu atsaucīgu lietotājiem (piemēram, tiem, kuri skatās ekrānā, gaidot uzdevuma pabeigšanu) un tādējādi samazināt Otrkārtatbildes laiku. Diemžēl tādi algoritmi kā RR samazina atbildes laiku, bet ievērojami
ietekmē apgrozījuma laika metriku. Tādējādi mūsu problēma ir: kā izstrādāt
plānotāju, kas apmierinās mūsu prasības, un tajā pašā laikā neko nezinās par
procesa dabu ģenerāli? Kā plānotājs varēs iegūt informāciju par uzdevumu raksturojumu,
kurus tas palaidīs, un tādējādi pieņemt labākus lēmumus par plānošanu?
Problēmas būtība: kā plānot uzdevumu izpildi bez ideālas zināšanas?
Kā izstrādāt plānotāju, kas vienlaikus samazina atbildes laiku
interaktīviem uzdevumiem un tajā pašā laikā samazina apgrozījuma laiku bez iepriekšējām

zināšanām par uzdevuma izpildes laiku?
Pieņemiet: mācāmies, balstoties uz iepriekšējiem notikumiem.
MLFQ rinda ir lielisks piemērs sistēmai, kas mācās no
notikušajiem notikumiem, lai prognozētu nākotni. Līdzīgi pieejas bieži

sastopamas OS (un daudzās citās informātikas nozarēs, tostarp prognozēšanas jomās

iekārtās un kešatmiņas algoritmos). Tādi pieejas
strādā, kad uzdevumiem ir uzvedības fāzes, tādējādi tās kļūst prognozējamas.
darbojas, kad uzdevumiem ir uzvedības fāzes un līdz ar to tās ir prognozējamas.
strādā, kad uzdevumiem ir uzvedības fāzes un tādējādi tie ir prognozējami.
tiek aktivizēti, kad uzdevumiem ir uzvedības fāzes, un tādējādi tie ir prognozējami.
Tomēr ar šādām tehnoloģijām jābūt uzmanīgiem, jo prognozes var ļoti viegli
izrādīties nepareizas un novest pie sliktāku lēmumu pieņemšanas nekā
tām būtu bijis vispār bez zināšanām.

MLFQ: Pamata noteikumi

Apskatīsim MLFQ algoritma pamata noteikumus. Un, lai gan šī algoritma
īstenojumu ir vairākas, pamata pieejas ir līdzīgas.
Ievērojot to realizāciju, ko mēs apskatīsim, MLFQ būs vairākas
atsevišķas rindas, katrai no kurām būs atšķirīgs prioritātes līmenis. Jebkurā brīdi,
uzdevums, kas gatavs izpildei, atrodas vienā rindā. MLFQ izmanto prioritātes,
lai noteiktu, kuru uzdevumu palaist izpildei, t.i., uzdevums ar augstāku
prioritāti (uzdevums augstākas prioritātes rindā) tiks palaists pirmais.
Neapšaubāmi, konkrētā rindā var būt vairāk nekā viens uzdevums, tādējādi
viņiem būs vienāda prioritāte. Šajā gadījumā tiks izmantots RR mehānisms
uzdevumu izpildes plānošanai starp šiem uzdevumiem.
Tādējādi mēs nonākam pie diviem pamata noteikumiem MLFQ:
Noteikums 1: Ja prioritāte(A) > Prioritāte(B), tiks palaists uzdevums A (B netiks)

Noteikums 2: Ja prioritāte(A) = Prioritāte(B), A un B tiek palaisti ar RR
Ņemot vērā iepriekš minēto, galvenie elementi MLFQ plānošanā

ir prioritātes. Tā vietā, lai noteiktu fiksētu prioritāti katram
uzdevumam, MLFQ maina tā prioritāti atkarībā no novērotās uzvedības.
Piemēram, ja uzdevums pastāvīgi pārtrauc darbu uz CPU, gaidot ievadi no klaviatūras,
MLFQ uzturēs procesa prioritāti augstā līmenī, jo tieši tā
jādarbojas interaktīvam procesam. Ja, savukārt, uzdevums pastāvīgi un
intensīvi izmanto CPU ilgstoši, MLFQ samazinās tā
prioritāti. Tādējādi MLFQ apgūs procesu uzvedību to darbības laikā
un izmantos šo uzvedību.
Zīmēsim piemēru par to, kā varētu izskatīties rindas noteiktā brīdī
un tas izskatīsies aptuveni šādi:
Šajā shēmā ir 2 procesi A un B augstākās prioritātes rindā. Process

C atrodas kaut kur vidū, bet process D rindas pašā galā. Saskaņā ar iepriekš minētajām
MLFQ algoritma aprakstiem plānotājs izpildīs tikai uzdevumus ar augstāko
prioritāti.
prioritāte saskaņā ar RR, bet uzdevumi C un D paliks bez uzmanības.
Dabiski, ka statisks snappshots nesniegs pilnu priekšstatu par to, kā darbojas MLFQ.
Ir svarīgi saprast, kā tieši attēls mainās laika gaitā.

Pirmais mēģinājums: kā mainīt prioritāti

Šajā brīdī jāizlemj, kā MLFQ mainīs prioritātes līmeni
uzdevumiem (un līdz ar to uzdevumu stāvokli rindā) to dzīves cikla laikā. Lai
to izdarītu, jātur prātā darba process: noteikts skaits
interaktīvu uzdevumu ar īsu izpildes laiku (un līdz ar to bieža CPU atbrīvošana)
un vairāki ilgi uzdevumi, kas izmanto CPU visu savu darba laiku, kamēr
aizture šādiem uzdevumiem nav svarīga. Tādējādi var veikt pirmo mēģinājumu
īstenot MLFQ algoritmu ar sekojošiem noteikumiem:

Noteikums 3: Kad uzdevums ienāk sistēmā, tas tiek novietots rindā ar augstāko
prioritāti.
Noteikums 4a: Ja uzdevums pilnībā izmanto tam atvēlēto laika logu, tad tā
prioritāte tiek pazemināta.
Noteikums 4b: Ja uzdevums atbrīvo CPU pirms tam atvēlētā laika loga beigām, tad tas
paliek ar iepriekšējo prioritāti.

Piemērs 1: Atsevišķs ilgi strādājošs uzdevums

Kā redzams šajā piemērā, uzdevums ierodoties tiek novietots ar augstāko
prioritāti. Pēc 10 ms laika loga procesors tiek pazemināts prioritātē
plānotājam. Pēc nākamā laika loga uzdevums galu galā tiek pazemināts līdz
zemākajai prioritātei sistēmā, kur tas arī paliek.

Piemērs 2: Pienāca īss uzdevums

Tagad aplūkosim piemēru, kā MLFQ centīsies tuvināties SJF. Šajā
piemērā ir divi uzdevumi: A, kas ir ilgi strādājošs uzdevums, kas pastāvīgi
izmanto CPU, un B, kas ir īss interaktīvs uzdevums. Pieņemsim,
ka A jau kādu laiku ir strādājusi, kad ieveda uzdevumu B.

Šajā grafikā ir redzami scenārija rezultāti. Uzdevums A, kā jebkurš uzdevums,
kas izmanto CPU, izrādījās pašā apakšā. Uzdevums B ieradīsies laikā T=100 un tiks
novietots rindā ar augstāko prioritāti. Tā kā tās izpildes laiks ir īss, tad
tas pabeigs darbu pirms nokļūšanas pēdējā rindā.

No šī piemēra ir jāsaprot galvenais algoritma mērķis: tā kā algoritms ne
zina, vai uzdevums ir garš vai īss, vispirms tam jāpieņem, ka uzdevums
īsa un piešķir tam augstāko prioritāti. Ja tā patiešām ir īsa uzdevums, tad
tas tiks izpildīts ātri, pretējā gadījumā, ja tas ir garš uzdevums, tad tas lēnām virzīsies
uz zemāku prioritāti un drīz pierādīs, ka tas patiešām ir garš uzdevums, kas ne
prasa atbildi.

Piemērs 3: Kas par ievadi un izvadi?

Tagad paskatīsimies uz piemēru ar ievadi un izvadi. Kā tika apgalvots noteikumā 4b,
ja process atbrīvo procesoru, neizmantot pilnībā savu procesora laiku,
tad tas paliek iepriekšējā prioritātes līmenī. Šī noteikuma nodoms ir diezgan vienkāršs
- ja interaktīvs uzdevums veic daudz ievadi un izvadīšanas operāciju, piemēram, gaidot
lietotāja taustiņu vai pele spiedienus, šāds uzdevums atbrīvos procesoru
agrāk noteiktā logā. Mums nepatiktu pazemināt tāda uzdevuma prioritāti,
un tādējādi tas paliks iepriekšējā līmenī.

Šis piemērs parāda, kā algoritms darbosies ar šādiem procesiem – interaktīvs uzdevums B, kas nepieciešams CPU tikai 1 ms pirms izpildes
ievadi un ilgstošs uzdevums A, kas visu savu laiku izmanto CPU.
MLFQ uztur procesu B ar augstāko prioritāti, jo tas visu laiku turpina
atbrīvot CPU. Ja B ir interaktīvs uzdevums, tad algoritms šajā gadījumā sasniedz
savu mērķi ātri palaist interaktīvos uzdevumus.

Problēmas ar pašreizējo algoritmu MLFQ

Iepriekšējās piemēros mēs uzbūvējām pamata variantu MLFQ. Un šķiet, ka tas
izpilda savu uzdevumu labi un godīgi, godīgi sadalot procesora laiku starp
ilgstošiem uzdevumiem un ļaujot īsiem uzdevumiem vai uzdevumiem, kas intensīvi veic
ieguldīšanu, darboties ātri. Diemžēl šāds piegājiens satur vairākas
nopietnas problēmas.
Pirmkārt, izsalkuma problēma: ja sistēmā būs daudz interaktīvu
uzdevumu, tie patērēs visu procesora laiku un tādējādi nevienam ilgstošam
uzdevumam nebūs iespējas izpildīties (tie izsalkst).

Otrkārt, viedie lietotāji varētu rakstīt savas programmas tā, lai
apmānītu plānotāju. Māns ir tajā, lai izdarītu kaut ko tādu, kas liktu
plānotājam piešķirt procesam vairāk procesora laika. Algoritms, kas
iepriekš minētā ir pilnīgi uzņēmīga pret līdzīgām uzbrukumu metodēm: pirms laika loga praktiski
beigušanās ir jāveic ievades-izvades operācija (uz kādu, nav svarīgi, uz kādu failu)
un tādējādi atbrīvot CPU. Šāda uzvedība ļaus palikt tajā pašā
rindā un atkal iegūt lielāku procentuālo daļu no procesora laika. Ja to izdarīs
pareizi (piemēram, darbojoties 99% laika loga pirms CPU atbrīvošanas),
tāda uzdevums var vienkārši monopolizēt procesoru.

Beigās programma var mainīt savu uzvedību laika gaitā. Tās uzdevumi,
kas izmantoja CPU, var kļūt interaktīvi. Mūsu piemērā līdzīgi
uzdevumi nesaņems pienācīgu attieksmi no plānotāja, kādā potenciāli saņemtu citi
(sākotnējie) interaktīvie uzdevumi.

Jautājums zālei: kādas uzbrukumu metodes pret plānotāju varēja tikt īstenotas mūsdienu pasaulē?

Mēģinājums 2: Prioritātes paaugstināšana

Mēģināsim mainīt noteikumus un redzēsim, vai varam izvairīties no problēmām ar
izsalkumu. Ko mēs varētu darīt, lai garantētu, ka ar
CPU saistītie uzdevumi saņems savu laiku (pat ja ne ilgi).
Kā vienkāršu problēmas risinājumu varētu ieteikt periodiski
paaugstināt visiem šādiem uzdevumiem prioritāti sistēmā. Ir daudz veidu
kā to panākt, mēģināsim īstenot kādu vienkāršu piemēru: pārvērst
uzreiz visus uzdevumus augstākajā prioritātē, no tā izriet jauns noteikums:

Rule5: Pēc noteikta laika perioda S pārvērst visus uzdevumus sistēmā augstākajā rindā.

Mūsu jaunais noteikums risina divas problēmas tūlīt. Pirmkārt, procesi
garantēti necieš izsalkumu: uzdevumi, kas atrodas augstākajā rindā, dalīs
procesora laiku saskaņā ar RR algoritmu un tādējādi visi procesi saņems
procesora laiku. Otrkārt, ja kāds process, kurš iepriekš izmantoja
tikai procesoru, kļūst interaktīvs, tad tas paliks rindā ar augstāko
prioritāti pēc tam, kad to vienreiz paaugstinās līdz augstākajam.
Apskatīsim piemēru. Šajā scenārijā apskatīsim vienu procesu, kas izmanto

CPU un divi interaktīvi, īsie procesi. Attēlā pa kreisi ir parādīts uzvedības modelis bez prioritātes paaugstināšanas, un tādējādi garie uzdevumi sāk gaidīt pēc divu interaktīvu uzdevumu ierašanās sistēmā. Attēlā pa labi katras 50 ms tiek veikta prioritātes paaugstināšana un tādējādi visi procesi garantēti saņem procesora laiku un tiks periodiski izpildīti. 50 ms šajā gadījumā tiek ņemti piemēram, faktiski šis skaitlis ir nedaudz lielāks.
Acīmredzami, ka periodiskā paaugstināšanas S laika pievienošana noved pie
loģiska jautājuma: kāda vērtība tam ir jābūt? Viens no cienījamajiem
sistēmu inženieriem John Ousterhout šādus lielumus sistēmās dēvēja par voo-doo
konstanti, jo tie kaut kādā veidā prasīja melno maģiju pareizai
iestatīšanai. Un, diemžēl, S ir ar tādu piegaršu. Ja iestata vērtību pārāk
lielu — gari uzdevumi sāk gaidīt. Bet ja iestata pārāk zemu vērtību,
interaktīvie uzdevumi nesaņems pienācīgu procesora laiku.

Mēģinājums 3: Labākā uzskaite

Tagad mums ir vēl viena problēma, ko jāatrisina: kā ne
ļaut mūsu plānotājam maldināt? Atbildīgie par šo iespēju ir
noteikumi 4a, 4b, kas ļauj uzdevumam saglabāt prioritāti, atbrīvojot procesoru
līdz tai ir beidzies piešķirts laiks. Kā ar to tikt galā?
Risinājums šajā gadījumā var būt labāka procesora laika uzskaite katrā
MLFQ līmenī. Tā vietā, lai aizmirstu laiku, kuru programma izmantoja
procesoram piešķirtajā periodā, vajadzētu to uzskaitīt un saglabāt. Pēc tam, kad
process ir iztērējis tam piešķirto laiku, tam jāmaina prioritāte uz nākamo
zemāko prioritāti. Tagad nav svarīgi, kā procesu izmantos — vai
pastāvīgi rēķinājot uz procesora vai kā vairākus izsaukumus. Tādējādi,
būtu jāpārraksta noteikums 4 šādā veidā:

Rule4: Pēc tam, kad uzdevums ir iztērējis tai piešķirto laiku pašreizējā rindā (neatkarīgi no tā, cik reizes tā ir atbrīvojusi CPU), tā prioritāte tiek samazināta (tā pārvietojas uz leju rindā).

Apskatīsim piemēru:
»

Attēlā parādīts, kas notiek, ja mēģināt maldināt plānotāju, kā
ja, ja iepriekšējie noteikumi 4a, 4b sniegtu rezultātu pa kreisi. Ar jauno
noteikumu - rezultāts pa labi. Pirms aizsardzības jebkurš process varēja izsaukt I/O līdz pabeigšanai un
tādējādi dominēt CPU, pēc aizsardzības ieslēgšanas, neatkarīgi no uzvedības
I/O, tas tomēr tiks nolaists rindās un tādējādi nevarēs negodīgi
iegūt CPU resursus.

Uzlabojam MLFQ un citas problēmas

Ar iepriekš minētajiem uzlabojumiem rodas jaunas problēmas: viens no galvenajiem
jautājumiem ir, kā parametrizēt tādu plānotāju? Cik daudz jābūt
rindām? Kāds ir programmas darba loga izmērs rindā? Cik
bieži jāpaaugstina programmas prioritāte, lai izvairītos no izsalkuma un
ņemtu vērā programmas uzvedības izmaiņas? Uz šiem jautājumiem nav vienkāršas
atbildes, un tikai eksperimenti ar slodzēm un turpmākā konfigurācija
plānotājam var novest pie kāda apmierinoša līdzsvara.

Piemēram, lielākā daļa MLFQ realizāciju ļauj piešķirt dažādus
laika intervālus dažādām rindām. Augstas prioritātes rindām parasti
piešķir īsus intervālus. Šīs rindas sastāv no interaktīvām uzdevumiem,
starptautiskas kuriem pārslēgšanās ir diezgan jūtīga un tai jāaizņem 10 vai mazāk
ms. Pretēji tam, zemas prioritātes rindas sastāv no ilgstošām uzdevumiem, kas izmantos
CPU. Un šajā gadījumā garie laika intervāli der ļoti labi (100ms).

Šajā piemērā ir 2 uzdevumi, kas strādājuši augstas prioritātes rindā 20
ms, sadalīti logiem pa 10ms. 40ms vidējā rindā (logs 20ms) un zemās prioritātes
rindā laika logs bija 40ms, kur uzdevumi pabeidza savu darbu.

MLFQ realizācija Solaris OS - plānotāju klase, kas dalās pa laikam.
Plānotājs nodrošina virkni tabulu, kas precīzi nosaka, kādā veidā
jāmaina procesa prioritāte tā dzīves laikā, kādam jābūt izmēram
piešķirtā loga un cik bieži jāpaaugstina uzdevuma prioritātes. Sistēmas
administrators var mijiedarboties ar šo tabulu un likt plānotājam uzvesties
atšķirīgi. Noklusējuma šajā tabulā ir 60 rindas ar pakāpenisku palielināšanu
logu izmērs no 20ms (augsta prioritāte) līdz dažiem simtiem ms (zemāka prioritāte), un
arī ar uzlabojumu visām uzdevumu izpildēm reizi sekundē.

Citi MLFQ plānotāji neizmanto tabulas vai kādus konkrētus
noteikumus, kas aprakstīti šajā lekcijā, tie tieši aprēķina prioritātes, izmantojot
matemātiskās formulas. Piemēram, plānotājs FreeBSD izmanto formulu, lai
aprēķinātu pašreizējo uzdevuma prioritāti, balstoties uz to, cik daudz procesors
izmantojis CPU. Turklāt CPU izmantošana laika gaitā samazinās, un līdz ar to
prioritātes paaugstināšana notiek nedaudz savādāk nekā iepriekš aprakstīts. Tas ir
tā saucamais decay algoritms. Kopš versijas 7.1 FreeBSD izmanto plānotāju ULE.

Visbeidzot, daudzi plānotāji ir ar citām īpašībām. Piemēram, daži
plānotāji rezervē augstākos līmeņus operētājsistēmas darbībai, un tādējādi
nekāds lietotāju process nevar iegūt visaugstāko prioritāti
sistemā. Dažas sistēmas ļauj sniegt norādījumus, lai palīdzētu
plānotājam pareizi noteikt prioritātes. Piemēram, izmantojot komandu nice
ir iespējams palielināt vai samazināt uzdevuma prioritāti un tādējādi paaugstināt vai
samazināt programmas izredzes uz procesora laiku.

MLFQ: Secinājumi

Mēs esam aprakstījuši plānošanas pieeju, ko sauc par MLFQ. Tā nosaukums
balstās uz darbības principu — tai ir vairāki izsūtīšanas līmeņi un tā izmanto atgriezenisko saiti
uzdevuma prioritātes noteikšanai.
Galīgā noteikumu forma būs šāda:

Noteikums 1: Ja prioritāte(A) > Prioritāte(B), tad tiks palaists uzdevums A (B netiks palaists)
Noteikums 2: Ja prioritāte(A) = Prioritāte(B), A un B tiks palaistas, izmantojot RR
Noteikums 3: Kad uzdevums tiek pieņemts sistēmā, tas tiek ievietots visaugstākās prioritātes rindā.
Rule4: Pēc tam, kad uzdevums ir iztērējis tai piešķirto laiku pašreizējā rindā (neatkarīgi no tā, cik reizes tā ir atbrīvojusi CPU), tā prioritāte tiek samazināta (tā pārvietojas uz leju rindā).
Rule5: Pēc noteikta laika perioda S pārvērst visus uzdevumus sistēmā augstākajā rindā.

MLFQ ir interesants šādu iemeslu dēļ — vietā, lai pieprasītu iepriekšēju izpratni par
uzdevuma dabu, algoritms pēta uzdevuma pagātnes uzvedību un nosaka
prioritātes atbilstoši. Tādējādi tas cenšas uzreiz sēdēt uz divām krēslām — sasniegt veiktspēju mazajiem uzdevumiem (SJF, STCF) un godīgi izpildīt garos,
CPU intensīvos uzdevumus. Tāpēc daudzas sistēmas, tostarp BSD un to atvasinājumus,
Solaris, Windows, Mac izmanto dažādu MLFQ algoritma formu
kā pamata plānotāju.