Ievads operētājsistēmās

Čau Habr! Es vēlos vērst jūsu uzmanību uz vienas, manuprāt, interesantas literatūras - OSTEP - rakstu sēriju-tulkojumiem. Šajā materiālā diezgan dziļi aplūkots unix līdzīgu operētājsistēmu darbs, proti, darbs ar procesiem, dažādiem plānotājiem, atmiņu un citiem līdzīgiem komponentiem, kas veido modernu OS. Visu materiālu oriģinālus varat apskatīt šeit šeit. Lūdzu, ņemiet vērā, ka tulkojums tika veikts neprofesionāli (diezgan brīvi), bet es ceru, ka es saglabāju vispārējo nozīmi.

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

Citas daļas:

Varat arī apskatīt manu kanālu vietnē telegramma =)

Plānošana: vairāku līmeņu atsauksmju rinda

Šajā lekcijā mēs runāsim par problēmām, kas saistītas ar vienas no slavenākajām pieejām
plānošana, ko sauc Daudzlīmeņu atsauksmju rinda (MLFQ). MLFQ plānotāju 1962. gadā pirmo reizi aprakstīja Fernando J. Korbato sistēmā ar nosaukumu
Saderīga laika dalīšanas sistēma (CTSS). Šie darbi (ieskaitot vēlākos darbus
Multics) pēc tam tika nominēti Tjūringa balvai. Plānotājs bija
pēc tam uzlaboja un ieguva izskatu, kāds jau ir atrodams
dažas modernas sistēmas.

MLFQ algoritms mēģina atrisināt 2 pamata problēmas, kas pārklājas.
Pirmkārt, tā mēģina optimizēt aprites laiku, kas, kā mēs runājām iepriekšējā lekcijā, tiek optimizēts ar metodi, kas sākas rindas sākumā.
īsi uzdevumi. Tomēr OS nezina, cik ilgi tas vai cits process darbosies, un tas
nepieciešamās zināšanas SJF, STCF algoritmu darbībai. Otrkārt, MLFQ mēģina
padarīt sistēmu atsaucīgu lietotājiem (piemēram, tiem, kas sēž un
skatoties uz ekrānu, gaidot, kamēr uzdevums tiks pabeigts), un tādējādi samazināt laiku
atbildi. Diemžēl tādi algoritmi kā RR samazina reakcijas laiku, bet
negatīvi ietekmē apstrādes laika metriku. Tāpēc mūsu problēma: kā noformēt
plānotājs, kas atbildīs mūsu prasībām un tajā pašā laikā neko nezina
procesa būtība kopumā? Kā plānotājs var apgūt uzdevumu īpašības,
ko tā uzsāk un tādējādi pieņemt labākus plānošanas lēmumus?

Problēmas būtība: Kā plānot uzdevumu uzstādīšanu bez perfektām zināšanām?
Kā izveidot plānotāju, kas vienlaikus samazina reakcijas laiku
interaktīviem uzdevumiem un tajā pašā laikā samazina apstrādes laiku, nezinot
zināšanas par uzdevuma izpildes laiku?

Piezīme: mēs mācāmies no iepriekšējiem notikumiem

MLFQ rinda ir lielisks piemērs sistēmai, kas mācās
pagātnes notikumi, lai paredzētu nākotni. Šādas pieejas bieži ir
atrodams operētājsistēmā (Un daudzās citās datorzinātņu nozarēs, ieskaitot filiāles
aparatūras prognozes un kešatmiņas algoritmi). Līdzīgi braucieni
tiek aktivizēti, ja uzdevumiem ir uzvedības fāzes un tādējādi tie ir paredzami.
Tomēr ar šo paņēmienu jābūt uzmanīgiem, jo prognozēšana ir ļoti vienkārša.
var izrādīties nepareizi un likt sistēmai pieņemt sliktākus lēmumus nekā
būtu vispār bez zināšanām.

MLFQ: pamatnoteikumi

Apsveriet MLFQ algoritma pamatnoteikumus. Un, lai gan šī algoritma realizācijas
ir vairākas, pamata pieejas ir līdzīgas.
Ieviešanā, ko mēs apsvērsim, MLFQ būs vairākas
atsevišķas rindas, no kurām katrai būs atšķirīga prioritāte. Jebkurā laikā,
izpildei gatavs uzdevums atrodas tajā pašā rindā. MLFQ izmanto prioritātes,
izlemt, kuru uzdevumu palaist izpildei, t.i. uzdevums ar augstāku
prioritāte (uzdevums no rindas ar augstāko prioritāti) tiks palaists pirmajā
rindā.
Protams, noteiktā rindā var būt vairāk nekā viens uzdevums, tāpēc
tāpēc viņiem būs tāda pati prioritāte. Šajā gadījumā tiks izmantots mehānisms
RR palaišanas plānošanai starp šiem uzdevumiem.
Tādējādi mēs nonākam pie diviem MLFQ pamatnoteikumiem:

1. noteikums: ja prioritāte(A) > Prioritāte(B), uzdevums A tiks izpildīts (B nedarbosies).
2. noteikums: ja prioritāte (A) = prioritāte (B), A&B tiek sākta, izmantojot RR

Pamatojoties uz iepriekš minēto, galvenie elementi MLFQ plānošanā ir
ir prioritātes. Tā vietā, lai katram piešķirtu noteiktu prioritāti
uzdevums, MLFQ maina savu prioritāti atkarībā no novērotās uzvedības.
Piemēram, ja uzdevums pastāvīgi tiek aizvērts CPU, gaidot tastatūras ievadi,
MLFQ saglabās procesa prioritāti augstu, jo tieši tā
interaktīvajam procesam vajadzētu darboties. Ja, gluži pretēji, uzdevums ir pastāvīgi un
ir CPU intensīvs ilgu laiku, MLFQ pazeminās to
prioritāte. Tādējādi MLFQ pētīs procesu uzvedību to darbības laikā.
un izmantot uzvedību.
Uzzīmēsim piemēru, kā varētu izskatīties rindas kādā brīdī
laiks, un tad jūs saņemat kaut ko līdzīgu šim:

Šajā shēmā 2 procesi A un B atrodas rindā ar augstāko prioritāti. Process
C atrodas kaut kur vidū, un process D atrodas rindas pašā beigās. Saskaņā ar iepriekš minēto
MLFQ algoritma aprakstus, plānotājs izpildīs tikai uzdevumus ar augstāko
prioritāte saskaņā ar RR, un uzdevumi C, D būs bez darba.
Protams, statisks momentuzņēmums nesniegs pilnīgu priekšstatu par MLFQ darbību.
Ir svarīgi precīzi saprast, kā attēls laika gaitā mainās.

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

Šajā brīdī jums ir jāizlemj, kā MLFQ mainīs prioritātes līmeni
uzdevumu (un līdz ar to uzdevuma pozīciju rindā) tā dzīves cikla laikā. Priekš
tas ir nepieciešams, lai paturētu prātā darbplūsmu: noteiktu summu
interaktīvi uzdevumi ar īsu darbības laiku (un tādējādi bieža izlaišana
CPU) un vairākus garus uzdevumus, kas izmanto CPU visu savu darba laiku, kamēr
reakcijas laiks šādiem uzdevumiem nav svarīgs. Un tāpēc jūs varat veikt pirmo mēģinājumu
ieviest MLFQ algoritmu ar šādiem noteikumiem:

3. noteikums: kad uzdevums nonāk sistēmā, tas tiek ievietots rindā ar augstāko
prioritāte.
4.a noteikums: ja uzdevumam tiek izmantots viss laika logs, tad tas
prioritāte ir pazemināta.
4.b noteikums: ja uzdevums atbrīvo centrālo procesoru pirms tā laika loga beigām, tad tas
paliek ar tādu pašu prioritāti.

1. piemērs. Viens ilgstošs uzdevums

Kā redzat šajā piemērā, uzņemšanas uzdevums ir iestatīts ar visaugstāko
prioritāte. Pēc 10 ms laika loga procesa prioritāte tiek pazemināta.
plānotājs. Pēc nākamā laika loga uzdevums beidzot tiek pazemināts uz
zemākā prioritāte sistēmā, kur tā paliek.

2. piemērs: izvēlējies īsu uzdevumu

Tagad apskatīsim piemēru, kā MLFQ mēģinās tuvoties SJF. Tajā
Piemēram, divi uzdevumi: A, kas ir ilgstošs uzdevums, kas pastāvīgi tiek veikts
aizņem CPU un B, kas ir īss interaktīvs uzdevums. Pieņemsim
ka A jau kādu laiku bija skrējis brīdī, kad ieradās uzdevums B.

Šajā grafikā parādīti scenārija rezultāti. A uzdevums, tāpat kā jebkurš uzdevums,
CPU izmantošana bija pašā apakšā. Uzdevums B ieradīsies laikā T=100 un tiks
ievietots augstākās prioritātes rindā. Tā kā darbības laiks ir īss,
tas tiks pabeigts, pirms tas sasniegs pēdējo rindu.

No šī piemēra jums vajadzētu saprast algoritma galveno mērķi: jo algoritms to nedara
zina garu vai īsu uzdevumu, tad vispirms pieņem, ka uzdevums
īss un piešķir tai augstāko prioritāti. Ja tas tiešām ir īss uzdevums, tad
tas tiks izpildīts ātri, pretējā gadījumā, ja tas ir ilgs uzdevums, tas virzīsies lēni
prioritāti uz leju, un drīzumā pierādīs, ka viņa patiešām ir garš uzdevums, kas nav
prasa atbildi.

3. piemērs. Kā ar I/O?

Tagad apskatīsim I/O piemēru. Kā norādīts 4.b noteikumā,
ja process atbrīvo procesoru, pilnībā neizmantojot savu procesora laiku,
tad tas paliek tajā pašā prioritātes līmenī. Šī noteikuma mērķis ir diezgan vienkāršs.
- ja interaktīvais darbs veic daudz I/O, piemēram, gaida
no lietotāja taustiņsitieniem vai peles, šāds uzdevums atbrīvos procesoru
pirms atvēlētā loga. Mēs negribētu izlaist šādu prioritāru uzdevumu,
un tādējādi tas paliks tajā pašā līmenī.

Šajā piemērā parādīts, kā algoritms darbotos ar šādiem procesiem - interaktīvais uzdevums B, kuram CPU nepieciešams tikai 1 ms pirms izpildes
I/O process un ilgs darbs A, kas visu laiku izmanto centrālo procesoru.
MLFQ saglabā procesam B visaugstāko prioritāti, kā tas turpinās
atlaidiet centrālo procesoru. Ja B ir interaktīvs uzdevums, tad algoritms šajā gadījumā ir sasniedzis
tā mērķis ir ātri uzsākt interaktīvus uzdevumus.

Problēmas ar pašreizējo MLFQ algoritmu

Iepriekšējos piemēros mēs esam izveidojuši MLFQ pamata versiju. Un šķiet, ka viņš
labi un godīgi veic savu darbu, godīgi sadalot CPU laiku starp
gari uzdevumi un atļaut īsus uzdevumus vai uzdevumus, kuriem ir liela piekļuve
ātri strādāt pie I/O. Diemžēl šī pieeja ietver vairākus
nopietnas problēmas.
Pirmkārt, bada problēma: ja sistēmai būs daudz interaktīvu
uzdevumiem, tie patērēs visu CPU laiku un tādējādi ne vienu ilgi
uzdevums nesaņems iespēju tikt izpildīts (viņi ir badā).

Otrkārt, viedie lietotāji varētu rakstīt savas programmas tā, lai
apmānīt plānotāju. Maldināšana slēpjas tajā, ka kaut ko dara, lai piespiestu
plānotāju, lai procesam piešķirtu vairāk CPU laika. Algoritms, kas
iepriekš aprakstītais ir diezgan neaizsargāts pret šādiem uzbrukumiem: pirms laika loga praktiski nav
beigās, jums ir jāveic I/O darbība (dažiem neatkarīgi no faila)
un tādējādi atbrīvojiet centrālo procesoru. Šāda uzvedība ļaus jums palikt tajā pašā stāvoklī
pati rinda un atkal iegūt lielāku CPU laika procentu. Ja jūs to darāt
tas ir pareizi (piemēram, palaidiet 99% loga laika pirms CPU atlaišanas),
šāds uzdevums var vienkārši monopolizēt procesoru.

Visbeidzot, programma laika gaitā var mainīt savu uzvedību. Tie uzdevumi
kas izmantoja centrālo procesoru, var kļūt interaktīvs. Mūsu piemērā līdzīgi
uzdevumi netiks pienācīgi apstrādāti no plānotāja, kā to darītu citi
(sākotnējie) interaktīvie uzdevumi.

Jautājums auditorijai: kādus uzbrukumus plānotājam varētu veikt mūsdienu pasaulē?

2. mēģinājums: palieliniet prioritāti

Mēģināsim mainīt noteikumus un redzēt, vai mēs varam izvairīties no problēmām ar
bads. Ko mēs varam darīt, lai nodrošinātu, ka tas ir saistīts
CPU uzdevumi saņems savu laiku (pat ja ne ilgi).
Kā vienkāršu problēmas risinājumu varat periodiski ieteikt
palielināt visu šādu uzdevumu prioritāti sistēmā. Ir daudz veidu
lai to panāktu, mēģināsim īstenot kaut ko vienkāršu kā piemēru: tulkot
visiem uzdevumiem vienlaikus ir augstākā prioritāte, tāpēc jaunais noteikums:

5. noteikums: Pēc kāda perioda S pārsūtiet visus uzdevumus sistēmā uz augstāko rindu.

Mūsu jaunais noteikums vienlaikus atrisina divas problēmas. Pirmkārt, procesi
garantēts, ka nenomirs badā: uzdevumi augstākajā rindā dalīsies
procesora laiks saskaņā ar RR algoritmu un tādējādi visi procesi saņems
procesora laiks. Otrkārt, ja kāds process, kas iepriekš izmantots
tikai procesors kļūst interaktīvs, tas paliks rindā ar augstāko
prioritāte pēc tam, kad vienreiz ir saņemts paaugstinājums uz augstāko prioritāti.
Apsveriet piemēru. Šajā scenārijā apsveriet iespēju izmantot vienu procesu

CPU un divi interaktīvi, īsi procesi. Attēla kreisajā pusē parādīta darbība bez prioritātes palielināšanas, un tādējādi ilgstoši darbojas uzdevums sāk izzust pēc tam, kad sistēmā nonāk divi interaktīvi uzdevumi. Labajā attēlā ik pēc 50 ms tiek veikts prioritātes palielinājums, un tādējādi visi procesi tiek garantēti procesora laika saņemšanai un tiks periodiski palaisti. 50 ms šajā gadījumā tiek ņemts par piemēru, patiesībā šis skaitlis ir nedaudz lielāks.
Ir acīmredzams, ka periodiskā pieauguma laika S pievienošana noved pie
loģisks jautājums: kāda vērtība ir jāiestata? Viens no pelnītajiem
sistēmu inženieri Džons Ousterhouts atsaucās uz līdzīgiem daudzumiem sistēmās kā voo-doo
nemainīgs, jo tie kaut kādā veidā prasīja melno maģiju pareizai darbībai
iedarbība. Un diemžēl S ir tāda garša. Ja iestatāt arī vērtību
lieli - gari uzdevumi nomirs. Un, ja jūs to iestatāt pārāk zemu,
interaktīvie uzdevumi nesaņems pienācīgu CPU laiku.

3. mēģinājums: labāka grāmatvedība

Tagad mums ir jāatrisina vēl viena problēma: kā to nedarīt
ļaut apkrāpt mūsu plānotāju? Šīs iespējas vainīgie ir
4.a un 4.b noteikumi, kas ļauj darbam saglabāt savu prioritāti, atbrīvojot procesoru
pirms noteiktā laika beigām. Kā ar to tikt galā?
Par risinājumu šajā gadījumā var uzskatīt labāku CPU laika uzskaiti katrā
MLFQ līmenis. Tā vietā, lai aizmirstu programmas izmantoto laiku
procesoru piešķirtajam intervālam, jums tas jāņem vērā un jāsaglabā. Pēc
process ir iztērējis atvēlēto laiku, tas ir jāpazemina uz nākamo
prioritātes līmenis. Tagad nav svarīgi, kā process izmantos savu laiku – kā
pastāvīgi skaitļo procesorā vai kā zvanu kopums. Tādējādi
4. noteikums ir jāpārraksta šādi:

4. noteikums: pēc tam, kad uzdevums ir iztērējis atvēlēto laiku pašreizējā rindā (neatkarīgi no tā, cik reižu tas atbrīvoja centrālo procesoru), šāda uzdevuma prioritāte tiek samazināta (tas pārvietojas rindā uz leju).

Apskatīsim piemēru:
»

Attēlā parādīts, kas notiek, ja mēģināt piemānīt plānotāju
ja tas būtu ar iepriekšējiem noteikumiem 4a, 4b būtu rezultāts kreisajā pusē. Ar jaunu
noteikums ir tāds, ka rezultāts ir labajā pusē. Pirms aizsardzības jebkurš process varēja izsaukt I/O pirms pabeigšanas un
tādējādi dominē CPU pēc aizsardzības iespējošanas neatkarīgi no uzvedības
I/O, viņš joprojām iestāsies rindā un tādējādi nevarēs negodīgi
pārņemt CPU resursus.

MLFQ un citu problēmu uzlabošana

Ar iepriekšminētajiem uzlabojumiem rodas jaunas problēmas: viena no galvenajām
Jautājumi - kā parametrizēt šādu plānotāju? Tie. Cik vajadzētu būt
rindas? Kādam jābūt programmas loga izmēram rindā? Kā
programmai bieži vien būtu jānosaka prioritāte, lai izvairītos no bada un
lai ņemtu vērā izmaiņas programmas darbībā? Uz šiem jautājumiem nav vienkārša
reakcija un tikai eksperimenti ar slodzēm un turpmāko konfigurāciju
plānotājs var radīt apmierinošu līdzsvaru.

Piemēram, lielākā daļa MLFQ implementāciju ļauj piešķirt dažādus
laika nišas dažādām rindām. Parasti ir augstas prioritātes rindas
īsi intervāli. Šīs rindas sastāv no interaktīviem uzdevumiem,
pārslēgšanās starp kurām ir diezgan jutīga, un tai vajadzētu ilgt 10 vai mazāk
jaunkundze. Turpretim zemas prioritātes rindas sastāv no ilgstošiem uzdevumiem, kas tiek izmantoti
PROCESORS. Un šajā gadījumā ļoti labi iederas garie laika intervāli (100ms).

Šajā piemērā ir 2 uzdevumi, kas ir darbojušies augstas prioritātes rindā 20
ms, sadalīts 10 ms logos. 40 ms vidējā rindā (20 ms logā) un zemajā prioritātē
rindas laika logs kļuva par 40 ms, kurā uzdevumi pabeidza savu darbu.

MLFQ ieviešana operētājsistēmā Solaris ir laika koplietošanas plānotāju klase.
Plānotājs nodrošinās tabulu kopu, kas precīzi nosaka, kā tam vajadzētu būt
mainīt procesa prioritāti visā tā dzīves laikā, kādam jābūt izmēram
logs, kas jāpiešķir un cik bieži jāpaaugstina uzdevumu prioritātes. Administrators
sistēma var mijiedarboties ar šo tabulu un likt plānotājam darboties
savādāk. Pēc noklusējuma šajā tabulā ir 60 rindas ar pakāpenisku pieaugumu
loga izmērs no 20 ms (augsta prioritāte) līdz vairākiem simtiem ms (zemākā prioritāte) un
arī ar visu uzdevumu palielināšanu reizi sekundē.

Citi MLFQ plānotāji neizmanto tabulu vai kādu konkrētu
noteikumi, kas ir aprakstīti šajā lekcijā, gluži pretēji, viņi aprēķina prioritātes, izmantojot
matemātiskās formulas. Piemēram, FreeBSD plānotājs izmanto formulu
pašreizējās uzdevuma prioritātes aprēķināšana, pamatojoties uz procesa apjomu
izmantoja centrālo procesoru. Turklāt CPU lietojums laika gaitā sabojājas, un līdz ar to
Tādējādi prioritātes palielinājums nedaudz atšķiras no iepriekš aprakstītā. Tā ir patiesība
sauc par samazinājuma algoritmiem. Sākot ar versiju 7.1, FreeBSD izmanto ULE plānotāju.

Visbeidzot, daudziem plānotājiem ir arī citas funkcijas. Piemēram, daži
plānotāji rezervē augstākus līmeņus operētājsistēmas darbībai un tādējādi
Tādējādi neviens lietotāja process nevar iegūt augstāko prioritāti
sistēma. Dažas sistēmas ļauj jums sniegt padomus, lai palīdzētu
plānotājs, lai pareizi noteiktu prioritātes. Piemēram, izmantojot komandu jauki
varat palielināt vai samazināt uzdevuma prioritāti un tādējādi palielināt vai
samazinātu programmas izredzes uz CPU laiku.

MLFQ: kopsavilkums

Mēs esam aprakstījuši plānošanas pieeju, ko sauc par MLFQ. Viņa vārds
ietverts darbības principā - tajā ir vairākas rindas un tiek izmantota atgriezeniskā saite
lai noteiktu uzdevumu prioritāti.
Noteikumu galīgā forma būs šāda:

1. noteikums: ja prioritāte (A) > Prioritāte (B), uzdevums A tiks izpildīts (B nedarbosies)
2. noteikums: Ja prioritāte(A) = Prioritāte(B), A&B tiek palaists, izmantojot RR
3. noteikums: Kad uzdevums nonāk sistēmā, tas tiek ievietots augstākās prioritātes rindā.
4. noteikums: pēc tam, kad uzdevums ir iztērējis atvēlēto laiku pašreizējā rindā (neatkarīgi no tā, cik reižu tas atbrīvoja centrālo procesoru), šāda uzdevuma prioritāte tiek samazināta (tas pārvietojas rindā uz leju).
5. noteikums: Pēc kāda perioda S pārsūtiet visus uzdevumus sistēmā uz augstāko rindu.

MLFQ ir interesants šāda iemesla dēļ - tā vietā, lai pieprasītu zināšanas par
uzdevuma raksturs iepriekš, algoritms apgūst uzdevuma un kopu pagātnes uzvedību
prioritātes. Tādējādi viņš mēģina sēdēt uz diviem krēsliem vienlaikus - lai sasniegtu veiktspēju maziem uzdevumiem (SJF, STCF) un godīgi skrietu garus,
CPU ielādes darbi. Tāpēc daudzas sistēmas, tostarp BSD un to atvasinājumi,
Solaris, Windows, Mac izmanto kādu algoritmu kā plānotāju
MLFQ kā bāzes līnija.