Introducere în sistemele de operare

Bună, Habr! Aș dori să vă prezint atenției o serie de articole-traduceri ale unei literaturi care este interesantă în opinia mea - OSTEP. Acest material examinează destul de profund munca sistemelor de operare asemănătoare Unix, și anume lucrul cu procese, diverse programatoare, memorie și alte componente similare care alcătuiesc un sistem de operare modern. Puteți vedea originalul tuturor materialelor aici aici. Vă rugăm să rețineți că traducerea a fost făcută neprofesionist (destul de liber), dar sper că am păstrat sensul general.

Lucrările de laborator pe acest subiect pot fi găsite aici:

Alte părți:

Puteți verifica și canalul meu la telegramă =)

Planificare: coadă de feedback pe mai multe niveluri

În această prelegere vom vorbi despre problemele dezvoltării uneia dintre cele mai cunoscute abordări
planificare, care se numește Coadă de feedback pe mai multe niveluri (MLFQ). Programatorul MLFQ a fost descris pentru prima dată în 1962 de Fernando J. Corbató într-un sistem numit
Sistem compatibil de partajare a timpului (CTSS). Aceste lucrări (inclusiv lucrările ulterioare despre
Multics) au fost nominalizați ulterior pentru Premiul Turing. Planificatorul a fost
ulterior îmbunătățit și dobândit aspectul care se regăsește deja în
unele sisteme moderne.

Algoritmul MLFQ încearcă să rezolve 2 probleme fundamentale care se suprapun.
În primul rând, încearcă să optimizeze timpul de răspuns, care, așa cum am discutat în prelegerea anterioară, este optimizat prin metoda de a începe cel mai mult la începutul cozii.
sarcini scurte. Cu toate acestea, sistemul de operare nu știe cât timp va rula un anumit proces și asta
cunoștințe necesare pentru funcționarea algoritmilor SJF, STCF. În al doilea rând, MLFQ încearcă
faceți sistemul receptiv pentru utilizatori (de exemplu, pentru cei care stau și
uitați-vă la ecran așteptând finalizarea sarcinii) și astfel minimizați timpul
raspuns. Din păcate, algoritmi precum RR îmbunătățesc timpul de răspuns, dar extrem de mult
au un impact negativ asupra valorii timpului de executie. De aici problema noastră: Cum să proiectăm
un planificator care va satisface cerințele noastre fără a ști nimic despre
natura procesului în general? Cum poate planificatorul să învețe caracteristicile sarcinilor,
pe care o lansează și astfel să ia decizii de planificare mai bune?

Esența problemei: Cum să planificați stabilirea sarcinilor fără cunoștințe perfecte?
Cum să proiectați un planificator care minimizează simultan timpul de răspuns
pentru sarcini interactive și, în același timp, minimizează timpul de realizare fără a ști
cunoștințe despre timpul de execuție a sarcinii?

Notă: învățăm din evenimentele anterioare

Coada MLFQ este un exemplu excelent de sistem care învață din
evenimentele trecute pentru a prezice viitorul. Abordări similare sunt adesea
găsit în OS (și multe alte ramuri ale informaticii, inclusiv ramuri
predicții hardware și algoritmi de stocare în cache). Excursii similare
sunt declanșate atunci când sarcinile au faze comportamentale și sunt astfel previzibile.
Cu toate acestea, ar trebui să fii atent cu această tehnică, deoarece predicțiile sunt foarte ușoare
se poate dovedi a fi incorectă și poate conduce sistemul să ia decizii mai proaste decât
ar fi deloc fără cunoștințe.

MLFQ: Reguli de bază

Să ne uităm la regulile de bază ale algoritmului MLFQ. Și deși implementările acestui algoritm
Există mai multe, abordările de bază sunt similare.
În implementarea pe care o vom analiza, MLFQ va avea mai multe
cozi separate, fiecare dintre ele va avea o prioritate diferită. oricând,
o sarcină gata de execuție se află într-o singură coadă. MLFQ folosește priorități,
pentru a decide ce sarcină să ruleze pentru execuție, de ex. sarcină cu mai mare
prioritate (sarcina din coada cu cea mai mare prioritate) va fi lansată mai întâi
coadă.
Desigur, pot exista mai multe sarcini într-o anumită coadă, deci
deci vor avea aceeasi prioritate. În acest caz, se va folosi mecanismul
RR pentru a programa o rulare printre aceste sarcini.
Astfel ajungem la două reguli de bază pentru MLFQ:

Regula 1: Dacă prioritatea (A) > Prioritatea (B), sarcina A va fi lansată (B nu)
Regula 2: Dacă prioritatea(A) = Prioritatea(B), A&B sunt pornite folosind RR

Pe baza celor de mai sus, elementele cheie pentru planificarea MLFQ
sunt prioritati. În loc să acorde o prioritate fixă fiecăruia
sarcină, MLFQ își schimbă prioritatea în funcție de comportamentul observat.
De exemplu, dacă o sarcină aruncă în mod constant lucru către CPU în timp ce așteaptă intrarea de la tastatură,
MLFQ va menține prioritate ridicată a procesului pentru că așa se face
un proces interactiv ar trebui să funcționeze. Dacă, dimpotrivă, sarcina este în mod constant și
folosește procesorul foarte mult pe o perioadă lungă de timp, MLFQ îl va reduce
o prioritate. Astfel, MLFQ va studia comportamentul proceselor în timp ce acestea rulează
și folosiți comportamente.
Să desenăm un exemplu despre cum ar putea arăta cozile la un moment dat
timp și apoi obțineți ceva de genul acesta:

În această schemă, 2 procese A și B sunt în coada cu cea mai mare prioritate. Proces
C este undeva la mijloc, iar procesul D se află la sfârșitul cozii. Conform celor de mai sus
Conform descrierilor algoritmului MLFQ, planificatorul va executa sarcini numai cu cea mai mare
prioritate conform RR, iar sarcinile C, D vor fi fără muncă.
Desigur, un instantaneu static nu va oferi o imagine completă a modului în care funcționează MLFQ.
Este important să înțelegeți exact cum se schimbă imaginea în timp.

Încercarea 1: Cum să schimbați prioritatea

În acest moment, trebuie să decideți cum MLFQ va schimba nivelul de prioritate
sarcinile (și, prin urmare, poziția sarcinii în coadă) pe măsură ce progresează prin ciclul său de viață. Pentru
acest lucru este necesar pentru a avea în vedere fluxul de lucru: o anumită cantitate
sarcini interactive cu durate scurte de execuție (și, prin urmare, lansări frecvente
CPU) și mai multe sarcini de lungă durată care folosesc CPU tot timpul lor de lucru, în timp ce
Timpul de răspuns nu este important pentru astfel de sarcini. Și astfel puteți face prima încercare
implementați algoritmul MLFQ cu următoarele reguli:

Regula 3: Când o sarcină intră în sistem, aceasta este plasată în coada cu cea mai mare
prioritate.
Regula 4a: Dacă o sarcină folosește întreaga fereastră de timp alocată, atunci aceasta
prioritatea este redusă.
Regula 4b: Dacă o sarcină eliberează CPU înainte ca fereastra de timp să expire, atunci aceasta
rămâne cu aceeași prioritate.

Exemplul 1: o singură sarcină de lungă durată

După cum se poate vedea în acest exemplu, sarcina de admitere este setată cu cea mai mare
prioritate. După o fereastră de timp de 10 ms, procesul este retrogradat în prioritate
planificator. După următoarea fereastră de timp, sarcina este în sfârșit retrogradată la
cea mai mică prioritate din sistem, unde rămâne.

Exemplul 2: S-a livrat o sarcină scurtă

Acum să vedem un exemplu despre modul în care MLFQ va încerca să abordeze SJF. In aceea
de exemplu, două sarcini: A, care este o sarcină de lungă durată în mod constant
ocupând CPU și B, care este o sarcină interactivă scurtă. Presupune
că A lucra deja de ceva timp până la sosirea sarcinii B.

Acest grafic prezintă rezultatele scenariului. Sarcina A, ca orice sarcină,
Utilizarea procesorului a fost în partea de jos. Sarcina B va ajunge la ora T=100 și va ajunge
plasat în coada cu cea mai mare prioritate. Din moment ce timpul său de funcționare este scurt, atunci
se va finaliza înainte de a ajunge la ultima coadă.

Din acest exemplu, scopul principal al algoritmului trebuie înțeles: deoarece algoritmul nu
știe dacă o sarcină este lungă sau scurtă, apoi în primul rând presupune că sarcina
scurt și îi acordă cea mai mare prioritate. Dacă aceasta este o sarcină foarte scurtă, atunci
va fi finalizat rapid, altfel, dacă este o sarcină lungă, se va mișca încet
prioritatea în jos și va dovedi în curând că ea este într-adevăr o sarcină lungă care nu
necesită un răspuns.

Exemplul 3: Dar I/O?

Acum să ne uităm la un exemplu I/O. După cum se precizează în regula 4b,
dacă un proces eliberează procesorul fără a utiliza tot timpul său de procesor,
atunci rămâne la același nivel de prioritate. Intenția acestei reguli este destul de simplă
- dacă jobul interactiv efectuează o mulțime de operațiuni I/O, de exemplu, așteptare
de la apăsarea tastei utilizatorului sau a mouse-ului, o astfel de sarcină va elibera procesorul
înainte de fereastra alocată. Nu am dori să reducem prioritatea unei astfel de sarcini,
si astfel va ramane la acelasi nivel.

Acest exemplu arată cum va funcționa algoritmul cu astfel de procese - jobul interactiv B, care are nevoie doar de CPU timp de 1 ms înainte de execuție
Procesul I/O și Job A de lungă durată, care își petrece tot timpul utilizând CPU.
MLFQ păstrează procesul B la cea mai mare prioritate pentru că continuă
eliberați CPU. Dacă B este o sarcină interactivă, atunci algoritmul a fost realizat
Scopul tău este să rulezi rapid sarcini interactive.

Probleme cu algoritmul actual MLFQ

În exemplele anterioare am construit o versiune de bază a MLFQ. Și se pare că el
își face treaba bine și cinstit, distribuind timpul CPU în mod corect
sarcini lungi și permițând sarcini scurte sau cu volum mare
lucrează rapid la I/O. Din păcate, această abordare conține mai multe
probleme serioase.
În primul rând, problema foamei: dacă sistemul are multe interactive
sarcini, atunci vor consuma tot timpul procesorului și astfel nu unul singur pentru o lungă perioadă de timp
sarcina nu va putea fi executată (ei mor de foame).

În al doilea rând, utilizatorii inteligenți și-ar putea scrie programele astfel încât
pacaleste programatorul. Înșelăciunea constă în a face ceva pentru a forța
Planificatorul oferă procesului mai mult timp CPU. Algoritmul care
descris mai sus este destul de vulnerabil la atacuri similare: înainte de fereastra de timp este practic
terminat, trebuie să efectuați o operație I/O (pentru unii, indiferent de fișier)
și astfel eliberați procesorul. Un astfel de comportament vă va permite să rămâneți în același
coada în sine și din nou obține un procent mai mare de timp CPU. Dacă faci
acest lucru este corect (de exemplu, executați 99% din timpul ferestrei înainte de a elibera procesorul),
o astfel de sarcină poate monopoliza pur și simplu procesorul.

În cele din urmă, un program își poate schimba comportamentul în timp. Acele sarcini
care a folosit CPU poate deveni interactiv. În exemplul nostru, similar
sarcinile nu vor primi tratamentul pe care îl merită de la planificator, așa cum ar primi alții
sarcini interactive (inițiale).

Întrebare pentru public: ce atacuri asupra programatorului ar putea fi efectuate în lumea modernă?

Încercarea 2: Creșterea priorității

Să încercăm să schimbăm regulile și să vedem dacă putem evita problemele cu
post. Ce putem face pentru a ne asigura că este legat
Sarcinile CPU își vor primi timpul lor (chiar dacă nu sunt lungi).
Ca o soluție simplă la problemă, puteți sugera periodic
ridicați prioritatea tuturor acestor sarcini din sistem. Sunt multe cai
Pentru a realiza acest lucru, să încercăm să implementăm ceva simplu ca exemplu: traduceți
toate sarcinile primesc imediat cea mai mare prioritate, de unde noua regulă:

Rule5: După o anumită perioadă S, mutați toate sarcinile din sistem la cea mai mare coadă.

Noua noastră regulă rezolvă două probleme simultan. În primul rând, procesele
au garantat că nu vor muri de foame: sarcinile care au cea mai mare prioritate vor fi împărțite
Timpul CPU conform algoritmului RR și astfel vor primi toate procesele
Timp CPU. În al doilea rând, dacă un proces care a folosit anterior
doar procesorul devine interactiv, acesta va rămâne în coada cu cea mai mare
prioritate după ce a primit o creștere unică a priorității la cea mai mare.
Să ne uităm la un exemplu. În acest scenariu, luați în considerare un proces care utilizează

CPU și două procese interactive, scurte. În stânga în figură, figura arată comportamentul fără promovare prioritară și astfel sarcina de lungă durată începe să se înfometeze după ce două sarcini interactive ajung în sistem. În figura din dreapta, se realizează o creștere a priorității la fiecare 50ms și astfel toate procesele sunt garantate să primească timp CPU și vor fi lansate periodic. 50 ms în acest caz este luat ca exemplu; în realitate, acest număr este puțin mai mare.
Evident, adăugarea timpului de creștere periodică la care duce S
o întrebare logică: ce valoare ar trebui setată? Unul dintre onorați
inginerii de sisteme John Ousterhout au numit astfel de cantități în sisteme ca voo-doo
constantă, deoarece au nevoie într-un fel de magie neagră pentru a fi corecte
exponând. Și, din păcate, S are un astfel de parfum. Dacă setați și valoarea
mari - sarcinile lungi vor începe să moară de foame. Și dacă setați valoarea prea mică,
Sarcinile interactive nu vor primi timp CPU adecvat.

Încercarea 3: o contabilitate mai bună

Acum avem o altă problemă de rezolvat: cum să nu
permiteți planificatorului nostru să fie păcălit? Oamenii vinovați pentru această posibilitate sunt
regulile 4a, 4b, care permit unei sarcini să păstreze prioritatea, eliberând procesorul
înainte de expirarea timpului alocat. Cum să te descurci cu asta?
Soluția în acest caz poate fi considerată o contabilizare mai bună a timpului CPU pe fiecare
Nivelul MLFQ. În loc să uităm timpul folosit de program
procesor pentru perioada alocată, trebuie luat în considerare și salvat. După
procesul și-a epuizat timpul alocat, ar trebui retrogradat la următorul
nivel de prioritate. Acum nu contează modul în care procesul își va folosi timpul - cum
calculând constant pe procesor sau ca număr de apeluri. Prin urmare,
regula 4 ar trebui rescrisă în următoarea formă:

Rule4: După ce o sarcină și-a epuizat timpul alocat în coada curentă (indiferent de câte ori a eliberat CPU), prioritatea sarcinii respective este redusă (se deplasează în jos în coadă).

Să ne uităm la un exemplu:
»

Figura arată ce se întâmplă dacă încercați să păcăliți planificatorul, de exemplu
daca ar fi cu regulile anterioare 4a, 4b s-ar obtine rezultatul din stanga. Fericit nou
regula este rezultatul din dreapta. Înainte de protecție, orice proces poate apela I/O înainte de finalizare și
domina astfel CPU-ul, dupa activarea protectiei, indiferent de comportament
I/O, el se va deplasa în continuare în coadă și astfel nu va putea să facă necinstit
prelua resursele CPU.

Îmbunătățirea MLFQ și alte probleme

Odată cu îmbunătățirile de mai sus apar noi probleme: una dintre principalele
Întrebări - cum se parametriză un astfel de planificator? Acestea. Cât ar trebui să fie
cozi? Care ar trebui să fie dimensiunea ferestrei programului din coadă? Cum
Prioritatea programului ar trebui deseori mărită pentru a evita foamea și
luați în considerare schimbarea comportamentului programului? Nu există un răspuns simplu la aceste întrebări
răspunde și experimentează doar cu încărcări și configurație ulterioară
planificatorul poate duce la un echilibru satisfăcător.

De exemplu, majoritatea implementărilor MLFQ vă permit să atribuiți diferite
intervale de timp pentru diferite cozi. Cozile cu prioritate mare de obicei
se prescriu intervale scurte. Aceste cozi constau din sarcini interactive,
comutarea între care este destul de sensibilă și ar trebui să dureze 10 sau mai puțin
Domnișoară. În schimb, cozile cu prioritate scăzută constau în sarcini de lungă durată care utilizează
CPU. Și în acest caz, intervalele lungi de timp se potrivesc foarte bine (100ms).

În acest exemplu, există 2 sarcini care au funcționat în coada 20 de prioritate ridicată
ms, împărțit în ferestre de 10 ms. 40 ms în coada de mijloc (fereastră de 20 ms) și cu prioritate scăzută
Fereastra de timp la coadă a devenit 40 ms în care sarcinile și-au încheiat munca.

Implementarea MLFQ a sistemului de operare Solaris este o clasă de programatori de timp partajat.
Planificatorul va furniza un set de tabele care definesc exact așa cum ar trebui
prioritatea procesului se schimbă pe parcursul vieții sale, care ar trebui să fie dimensiunea
fereastra alocată și cât de des trebuie să ridicați prioritățile sarcinilor. Administrator
sistemele pot interacționa cu acest tabel și pot determina comportamentul planificatorului
diferit. În mod implicit, acest tabel are 60 de cozi cu o creștere treptată
dimensiunea ferestrei de la 20 ms (prioritate mare) la câteva sute de ms (prioritate scăzută) și
de asemenea, cu un impuls al tuturor sarcinilor o dată pe secundă.

Alți planificatori MLFQ nu folosesc un tabel sau orice anume
regulile care sunt descrise în această prelegere, dimpotrivă, ele calculează prioritățile folosind
formule matematice. De exemplu, programatorul FreeBSD folosește o formulă pentru
calculați prioritatea curentă a unei sarcini în funcție de durata procesului
CPU folosit. În plus, utilizarea procesorului scade în timp și așa
Astfel, creșterea priorității are loc oarecum diferit față de cel descris mai sus. Asta este adevărat
numiti algoritmi de dezintegrare. Începând cu versiunea 7.1, FreeBSD a folosit programatorul ULE.

În cele din urmă, mulți programatori au alte caracteristici. De exemplu, unii
programatorii rezervă cele mai înalte niveluri pentru funcționarea sistemului de operare și astfel
Astfel, niciun proces utilizator nu poate primi cea mai mare prioritate în
sistem. Unele sisteme vă permit să oferiți sfaturi pentru a ajuta
planificatorul poate stabili prioritățile corect. De exemplu, folosind comanda frumos
poți crește sau micșora prioritatea unei sarcini și astfel crește sau
reduce șansele programului de a utiliza timpul CPU.

MLFQ: Rezumat

Am descris o abordare de planificare numită MLFQ. Numele lui
inclusă în principiul de funcționare - are mai multe cozi și folosește feedback
pentru a determina prioritatea sarcinii.
Forma finală a regulilor va fi următoarea:

Rule1: Dacă prioritatea (A) > Prioritatea (B), sarcina A va fi lansată (B nu)
Rule2: Dacă priority(A) = Priority(B), A&B sunt pornite folosind RR
Rule3: Când o sarcină intră în sistem, aceasta este plasată în coada cu cea mai mare prioritate.
Rule4: După ce o sarcină și-a epuizat timpul alocat în coada curentă (indiferent de câte ori a eliberat CPU), prioritatea sarcinii respective este redusă (se deplasează în jos în coadă).
Rule5: După o anumită perioadă S, mutați toate sarcinile din sistem la cea mai mare coadă.

MLFQ este interesant din următorul motiv - în loc să necesite cunoștințe despre
natura sarcinii în avans, algoritmul studiază comportamentul trecut al sarcinii și setează
priorități în consecință. Astfel, încearcă să stea pe două scaune deodată - să obțină productivitate pentru sarcini mici (SJF, STCF) și să alerge sincer mult timp,
Lucrări de încărcare CPU. Prin urmare, multe sisteme, inclusiv BSD și derivatele lor,
Solaris, Windows, Mac folosesc o anumită formă de algoritm ca programator
MLFQ ca punct de referință.

Materiale suplimentare:

Sursa: www.habr.com

Sisteme de operare: trei piese ușoare. Partea 5: Planificare: coadă de feedback pe mai multe niveluri (traducere)