Operating Systems: Three Easy Pieces. Dio 5: Planiranje: Multi-Level Feedback Queue (prijevod)

Uvod u operacijske sustave

Pozdrav, Habr! Želim predstaviti seriju članaka-prijevoda jedne zanimljive literature po mom mišljenju — OSTEP. U ovom materijalu duboko se razmatra rad unix-sličnih operacijskih sustava, a posebno — rad s procesima, raznim planerima, memorijom i drugim sličnim komponentama koji čine moderni OS. Original svih materijala možete pogledati ovdje ovdje. Molim vas, imajte na umu da je prijevod izveden neprofesionalno (dovoljno slobodno), ali se nadam da sam zadržao opći smisao.

Laboratorijske vježbe vezane uz ovu temu možete pronaći ovdje:

Ostali dijelovi:

A također možete zaviriti na moj kanal u telegramu =)

Planiranje: Multi-Level Feedback Queue

U ovoj lekciji ćemo razgovarati o problemima razvoja jednog od najpoznatijih pristupa
planiranju, koji se naziva Multi-Level Feedback Queue (MLFQ). Prvi put je MLFQ planer opisao 1962. godine Fernando J. Corbató u sustavu koji se zove
Compatible Time-Sharing System (CTSS). Ovi radovi (uključujući i kasnije radove na
Multics) kasnije su bili nominirani za Turingovu nagradu. Planer je
kasnije unaprijeđen i dobio oblik koji se može naći u
nekim modernim sustavima.

Algoritam MLFQ pokušava riješiti 2 temeljna preklapajuća problema.
Prvo, pokušava optimizirati vrijeme prometa, koje se, kao što smo razmatrali u prethodnoj lekciji, optimizira metodom pokretanja na početku reda naj
kraćih zadataka. Međutim, OS ne zna koliko će dugo raditi određeni proces, a to je
neophodno znanje za rad algoritama SJF, STCF. Drugo, MLFQ pokušava
učiniti sustav odgovoriti korisnicima (npr. onima koji sjede i
bulje u ekran u čekanju da se zadatak završi) i tako minimizirati vrijeme
odgovora. Nažalost, algoritmi poput RR smanjuju vrijeme odgovora, ali imaju izuzetno
loš utjecaj na metriku vremena prometa. Odatle naš problem: Kako dizajnirati
planer koji će zadovoljiti naše zahtjeve, a da pri tome ne zna ništa o
prirodi procesa, uopće? Kako će planer moći proučiti karakteristike zadataka,
koje pokreće i tako donositi bolje odluke o planiranju?

Suština problema: Kako planirati postavljanje zadataka bez idealnog znanja?
Kako razviti planer koji istovremeno minimizira vrijeme odgovora
za interaktivne zadatke i pritom minimizira vrijeme prometa bez unaprijed
znanja vremena izvršavanja zadatka?

Napomena: učenje iz prethodnih događaja

Red MLFQ je izvrstan primjer sustava koji se uči iz
prošlih događaja kako bi predvidio budućnost. Slični pristupi se često
susreću u OS-u (i mnogim drugim područjima informatike, uključujući grane
predikcija u hardveru i algoritme keširanja). Slični pristupi
funkcioniraju kada zadaci imaju ponašajne faze i tako su predvidljivi.
Međutim, s ovom tehnikom treba biti oprezan jer predikcije vrlo lako
mogu biti pogrešne i dovesti sustav do donošenja lošijih odluka nego što bi
bilo bez znanja uopće.

MLFQ: Osnovna pravila

Pogledajmo osnovna pravila MLFQ algoritma. Iako postoji nekoliko
implementacija ovog algoritma, osnovni pristupi su slični.
U implementaciji koju ćemo razmatrati, MLFQ će imati nekoliko
odvojenih redova, od kojih će svaki imati drugačiji prioritet. U bilo kojem trenutku,
zadatak spreman za izvršenje nalazi se u jednom redu. MLFQ koristi prioritete
da odluči koji zadatak pokrenuti, tj. zadatak s višim
prioritetom (zadatak iz reda s najvišim prioritetom) bit će pokrenut prvi.
Nesumnjivo, u određenom redu može biti više od jednog zadatka, tako
da će imati isti prioritet. U tom slučaju koristit će se mehanizam
RR za planiranje pokretanja među tim zadacima.
Na taj način dolazimo do dva osnovna pravila za MLFQ:
Pravilo 1: Ako prioritet(A) > Prioritet(B), pokrenut će se zadatak A (B se neće)

  • Pravilo 2: Ako prioritet(A) = Prioritet(B), A i B pokreću se koristeći RR
  • Na temelju navedenog, ključni elementi za planiranje MLFQ

su prioriteti. Umjesto da dodijeli fiksni prioritet svakom
zadacima, MLFQ mijenja njegov prioritet ovisno o promatranoj
ponašanju.
Na primjer, ako zadatak konstantno baca rad na CPU-u u očekivanju unosa s tipkovnice,
MLFQ će održavati prioritet procesa na visokom nivou jer bi tako
trebao raditi interaktivni proces. Nasuprot tome, ako zadatak konstantno i
intenzivno koristi CPU tijekom dužeg razdoblja, MLFQ će smanjiti njegov
prioritet. Tako će MLFQ učiti ponašanje procesa tijekom njihovog rada
i koristiti to ponašanje.
Nacrtajmo primjer kako bi redovi mogli izgledati u nekom trenutku
vremena i to će izgledati otprilike ovako:
Operating Systems: Three Easy Pieces. Dio 5: Planiranje: Multi-Level Feedback Queue (prijevod)

U ovom dijagramu 2 procesa A i B nalaze se u redu s najvišim prioritetom. Proces
C negdje je posred, a proces D na samom kraju reda. Prema gore navedenim
opisima algoritma MLFQ planirač će izvoditi zadatke samo s najvišim
prioritet prema RR, a zadaci C, D neće biti na redu.
Naravno, statički snimak neće dati potpunu sliku o tome kako radi MLFQ.
Važno je razumjeti kako se slika mijenja s vremenom.

Pokušaj 1: Kako mijenjati prioritet

U ovom trenutku potrebno je odlučiti kako će MLFQ mijenjati razinu prioriteta
zadaća (i tako poziciju zadatka u redu) tijekom njegovog životnog ciklusa. Za
to je potrebno imati na umu radni proces: određeni broj
interaktivnih zadataka s kratkim vremenom trajanja (i tako čestim oslobađanjem
CPU-a) i nekoliko dugih zadataka koji koriste CPU cijelo svoje radno vrijeme, pri čemu
vrijeme odziva za takve zadatke nije važno. Tako se može napraviti prvi pokušaj
implementacije algoritma MLFQ s sljedećim pravilima:

  • Rule3: Kada zadatak uđe u sustav, smješta se u red s najvišim
  • prioritetom.
  • Rule4a: Ako zadatak iskoristi cijeli dodijeljeni vremenski prozor, tada njegov
  • prioritet pada.
  • Rule4b: Ako zadatak oslobađa CPU prije isteka svog vremenskog prozora, tada
  • ostaje s prethodnim prioritetom.

Primjer 1: Jedan dugotrajni zadatak

Kao što se može vidjeti u ovom primjeru, zadatak se prilikom ulaska postavlja s najvišim
prioritetom. Nakon vremenskog prozora od 10ms, proces pada u prioritetu
u planeru. Nakon sljedećeg vremenskog prozora, zadatak konačno pada na
najniži prioritet u sustavu, gdje i ostaje.
Operating Systems: Three Easy Pieces. Dio 5: Planiranje: Multi-Level Feedback Queue (prijevod)

Primjer 2: Doveden je kratak zadatak

Sada ćemo pogledati primjer kako će se MLFQ pokušati približiti SJF-u. U ovom
primjeru postoje dva zadatka: A, koji je dugotrajni zadatak koji stalno
koristi CPU, i B, koji je kratki interaktivni zadatak. Pretpostavimo
da je A već radio neko vrijeme kada je zadatak B došao.
Operating Systems: Three Easy Pieces. Dio 5: Planiranje: Multi-Level Feedback Queue (prijevod)

Na ovom grafikonu vidljivi su rezultati scenarija. Zadatak A, kao i svaki zadatak,
koji koristi CPU, našao se na dnu. Zadatak B će stići u trenutku T=100 i bit će
smješten u red s najvišim prioritetom. Budući da je vrijeme njegovog rada kratko,
završit će prije nego što dođe do posljednjeg reda.

Iz ovog primjera treba razumjeti glavnu svrhu algoritma: budući da algoritam ne
zna je li zadatak dug ili kratak, u prvom redu pretpostavlja da je zadatak
kratka i dodaje joj najviši prioritet. Ako je to doista kratka zadaća,
izvršit će se brzo, inače, ako je to duga zadaća, bit će spora
s prioritetom dolje i ubrzo će pokazati da je to doista duga zadaća koja ne
zahtijeva odgovor.

Primjer 3: Što je s unosom i izlazom?

Sada ćemo pogledati primjer s unosom i izlazom. Kao što je navedeno u pravilu 4b,
ako proces oslobodi procesor ne koristeći u potpunosti njegovo procesorsko vrijeme,
ostaje na istoj razini prioriteta. Namjera ovog pravila je prilično jednostavna
— ako interaktivna zadaća izvodi mnogo operacija unosa i izlaza, na primjer, čekajući
na pritiske tipke ili miša korisnika, takva zadaća će osloboditi procesor
ranije od predviđenog vremena. Ne bismo željeli smanjiti prioritet takve zadaće,
pa će tako ostati na istoj razini.
Operating Systems: Three Easy Pieces. Dio 5: Planiranje: Multi-Level Feedback Queue (prijevod)

Ovaj primjer pokazuje kako će algoritam raditi s takvim procesima — interaktivna zadaća B, koja treba CPU samo 1ms prije izvršenja
procesa unosa i izlaza i duga zadaća A, koja cijelo svoje vrijeme koristi CPU.
MLFQ drži proces B na najvišoj razini prioriteta, jer stalno
oslobađa CPU. Ako je B — interaktivna zadaća, tada algoritam u tom slučaju postiže
svoj cilj izvođenja interaktivnih zadaća brzo.

Problemi s trenutnim algoritmom MLFQ

U prethodnim primjerima izgradili smo osnovnu verziju MLFQ. Čini se da
dobro obavlja svoj posao i pravedno dijeli procesorsko vrijeme između
dugih zadaća, dopuštajući kratkim zadaćama ili zadaćama koje intenzivno koriste
ulaz i izlaz da se brzo izvrše. Nažalost, ovakvo rješenje sadrži nekoliko
ozbiljnih problema.
Prvo, problem gladi: ako u sustavu postoji mnogo interaktivnih
zadaća, one će trošiti cijelo procesorsko vrijeme i tako nijedna duga
zadaća neće imati priliku za izvršenje (gladni su).

Drugo, pametni korisnici mogli bi pisati svoje programe na način koji
bi prevario planifier. Prevara se sastoji u tome da se učini nešto
što bi natjeralo planifiera da dodijeli procesu više procesorskog vremena. Algoritam koji
opisano gore, vrlo je ranjivo na slične napade: prije nego što vrijeme gotovo istekne,
potrebno je izvršiti operaciju ulaza-izlaza (na neki, nevažno koji, datoteku)
i na taj način osloboditi CPU. Takvo ponašanje omogućit će ostanak u istoj
redoslijedu i ponovno dobivanje većeg postotka procesorskog vremena. Ako se to
ispravno učini (na primjer, izvršava se 99% vremena unutar prozora prije oslobađanja CPU-a),
taka zadaća može jednostavno monopolizirati procesor.

Na kraju, program može promijeniti svoje ponašanje s vremenom. One zadaće,
koje su koristile CPU, mogu postati interaktivne. U našem primjeru, takve
zadaće neće dobiti odgovarajuće tretiranje od planera, jer bi dobile druge
(izvorne) interaktivne zadaće.

Pitanje za publiku: koje napade na planer bismo mogli izvesti u suvremenom svijetu?

Pokušaj 2: Povećanje prioriteta

Pokušajmo promijeniti pravila i vidjeti možemo li izbjeći probleme s
gladovanjem. Što bismo mogli učiniti kako bismo osigurali da zadaće povezane s
CPU-om dobiju svoje vrijeme (čak i ako ne dugo).
Kao jednostavno rješenje problema, može se predložiti da se povremeno
povećava prioritet svih takvih zadaća u sustavu. Postoji mnogo načina
za postizanje ovog cilja, pokušajmo provesti kao primjer nešto jednostavno: prebaciti
sve zadaće odmah na najviši prioritet, odakle novo pravilo:

  • Rule5: Nakon određenog razdoblja S, prebaciti sve zadaće u sustavu u najviši red.

Naše novo pravilo rješava dva problema odjednom. Prvo, procesi
jamče da ne gladuju: zadaće u višem redu dijelit će
procesorsko vrijeme prema RR algoritmu, i time će svi procesi dobiti
procesorsko vrijeme. Drugo, ako neki proces, koji je ranije koristio
samo procesor, postane interaktivan, tada će ostati u redu s višim
prioritetom nakon što dobije povećanje prioriteta na najviši.
Razmotrite primjer. U ovom scenariju razmotrite jedan proces koji koristi
Operating Systems: Three Easy Pieces. Dio 5: Planiranje: Multi-Level Feedback Queue (prijevod)

CPU i dva interaktivna, kratka procesa. Na lijevoj strani slike prikazano je ponašanje bez povećanja prioriteta, zbog čega dugačka zadaća počinje gladovati nakon dolaska dva interaktivna zadatka u sustav. Na slici desno, svake 50 ms dolazi do povećanja prioriteta, čime svi procesi jamče dobivanje procesorskog vremena i bit će povremeno pokretani. 50 ms u ovom slučaju uzeto je kao primjer, u stvarnosti je to broj nešto veći.
Očigledno je da dodavanje vremena periodičnog povećanja S dovodi do
zakonskog pitanja: koju vrijednost trebamo postaviti? Jedan od cijenjenih
sistemskih inženjera John Ousterhout nazivao je takve veličine u sustavima voodoo
konstantama, jer su na neki način zahtijevale crnu magiju za ispravno
postavljanje. I, nažalost, S ima takav miris. Ako se postavi prevelika
vrijednost — dugačke zadaće će početi gladovati. A ako se postavi previše niska vrijednost,
interaktivni zadaci neće dobiti dovoljno procesorskog vremena.

Pokušaj 3: Bolje praćenje

Sada imamo još jedan problem koji treba riješiti: kako ne
dopustiti našem planer uređaja da vara? Krivce za ovu mogućnost
čine pravila 4a, 4b, koja omogućavaju zadatku da zadrži prioritet oslobađajući procesor
prije isteka dodijeljenog vremena. Kako se nositi s tim?
Rješenje u ovom slučaju može biti najbolje praćenje vremena CPU na svakom
nivou MLFQ. Umjesto da zaboravi vrijeme koje je program koristio
procesor u dodijeljenom intervalu, treba ga pratiti i pohranjivati. Nakon što
proces potroši svoje dodijeljeno vrijeme, treba ga smanjiti na sljedeći
prioritetni nivo. Sada nije važno kako proces koristi svoje vrijeme — kao
neprekidno računanje na procesoru ili kao niz poziva. Tako,
pravilo 4 treba prepisati na sljedeći način:

  • Rule4: Nakon što je zadatak potrošio dodijeljeno vrijeme u trenutnoj redu (bez obzira na to koliko je puta oslobodio CPU), prioritet takvog zadatka se smanjuje (pomiče se prema dolje u redu).

Pogledajmo primjer:
Operating Systems: Three Easy Pieces. Dio 5: Planiranje: Multi-Level Feedback Queue (prijevod)»

Na slici je prikazano što se događa ako pokušate prevariti planer, kako
Ako bi se primijenila prethodna pravila 4a, 4b, rezultat bi bio lijevo. S novim
pravilo — rezultat je desno. Prije zaštite, bilo koji proces mogao bi izazvati I/O do završetka i
tako dominirati CPU-om; nakon uključivanja zaštite, bez obzira na ponašanje
I/O, i dalje će se spuštati niz red i stoga neće moći nepošteno
zauzeti resurse CPU-a.

Poboljšanje MLFQ i drugih problema

S gore navedenim poboljšanjima javljaju se novi problemi: jedno od glavnih
pitanja je kako parametrijizirati takav planirač? Odnosno, koliko bi trebalo biti
redova? Koja bi trebala biti veličina radnog prozora unutar redova? Kako
često treba podizatiprioritet programa kako bi se izbjeglo izgladnjivanje i
uzeti u obzir promjenu ponašanja programa? Na ta pitanja nema jednostavnog
odgovora, a samo eksperimenti s opterećenjima i naknadno konfiguriranje
planirača mogu dovesti do nekog zadovoljavajućeg balansa.

Na primjer, većina implementacija MLFQ omogućuje dodjeljivanje različitih
vremenskih intervala različitim redovima. Visokopriritetnim redovima obično
se dodjeljuju kratki intervali. Ovi redovi se sastoje od interaktivnih zadataka,
prebacivanje između kojih je prilično osjetljivo i trebalo bi trajati 10 ili manje
ms. Nasuprot tome, niskoprioretetni redovi sastoje se od dugih zadataka koji koriste
CPU. I u ovom su slučaju dugi vremenski intervali vrlo dobri (100ms).
Operating Systems: Three Easy Pieces. Dio 5: Planiranje: Multi-Level Feedback Queue (prijevod)

U ovom primjeru postoje 2 zadatka koja su provela 20
ms u visokopriritetnom redu, podijeljena u prozore od 10ms. 40ms u srednjem redu (prozor od 20ms) i u niskopriritetnom
redu vremensko okno postalo je 40ms, gdje su zadaci završili svoj rad.

Implementacija MLFQ u OS Solaris — klasa planirača koji dijeli vrijeme.
Planirač pruža skup tablica koje precizno definiraju kako bi se trebao
mijenjati prioritet procesa tijekom njegovog života, koja bi trebala biti veličina
dodijeljenog prozora i koliko često treba podizati prioritete zadatka. Administrator
sustava može komunicirati s ovom tablicom i prisiliti planirač da se ponaša
drugačije. Po zadanim postavkama u ovoj tablici ima 60 redova s postupnim povećanjem
veličine prozora s 20ms (visoki prioritet) do nekoliko stotina ms (nizak prioritet), a
također s pojačanim izvršavanjem svih zadataka svaki put u sekundi.

Drugi MLFQ planeri ne koriste tablice ili neka konkretna
pravila koja su opisana u ovoj lekciji, naprotiv, oni izračunavaju prioritete koristeći
matematičke formule. Tako, na primjer, planer u FreeBSD-u koristi formulu za
izračunavanje trenutnog prioriteta zadatka, temeljeći se na tome koliko je proces
koristio CPU. Osim toga, korištenje CPU s vremenom opada, i na taj
način, povećanje prioriteta događa se malo drugačije nego što je opisano iznad. To su
takozvani decay algoritmi. Od verzije 7.1 u FreeBSD-u koristi se planer ULE.

Na kraju, mnogi planeri imaju druge karakteristike. Na primjer, neki
planeri rezerviraju više razine za rad operativnog sustava i na taj
način, nijedan korisnički proces ne može dobiti najviši prioritet u
sistemu. Neki sustavi omogućuju davanje savjeta kako bi pomogli
planeru da ispravno postavlja prioritete. Tako, na primjer, pomoću naredbe nice
može se povećati ili smanjiti prioritet zadatka i na taj način povećati ili
smanjiti šanse programa za procesorsko vrijeme.

MLFQ: Zaključci

Opisali smo pristup planiranju koji se naziva MLFQ. Njegovo ime
proizlazi iz načela rada — ima više redova i koristi povratne informacije
za određivanje prioriteta zadatka.
Konačni izgled pravila bit će sljedeći:

  • Rule1: Ako prioritet(A) > Prioritet(B), pokrenut će se zadatak A (B neće biti)
  • Rule2: Ako prioritet(A) = Prioritet(B), A i B se pokreću koristeći RR
  • Rule3: Kada zadatak dođe u sustav, stavljaju ga u red s najvišim prioritetom.
  • Rule4: Nakon što je zadatak potrošio dodijeljeno vrijeme u trenutnoj redu (bez obzira na to koliko je puta oslobodio CPU), prioritet takvog zadatka se smanjuje (pomiče se prema dolje u redu).
  • Rule5: Nakon određenog razdoblja S, prebaciti sve zadaće u sustavu u najviši red.

MLFQ je zanimljiv iz sljedećeg razloga — umjesto da zahtijeva prethodno znanje o
prirodi zadatka, algoritam proučava prethodno ponašanje zadatka i postavlja
prioritete sukladno tome. Na taj način pokušava sjesti na dvije stolice - postići
performanse za male zadatke (SJF, STCF) i pravedno pokretati dugotrajne,
CPU-intenzivne zadatke. Stoga mnogi sustavi, uključujući BSD i njihove
derivate, Solaris, Windows, Mac koriste neku formu algoritma

Dodatni materijali:

  1. MLFQ kao osnovni planer.
  2. manpages.debian.org/stretch/manpages/sched.7.en.htmlen.wikipedia.org/wiki/Scheduling_
  3. pages.lip6.fr/Julia.Lawall/atc18-bouron.pdf
  4. www.usenix.org/legacy/event/bsdcon03/tech/full_papers/roberson/roberson.pdf
  5. chebykin.org/freebsd-process-scheduling

Izvor: habr.com

Kupite pouzdan hosting za web stranice s DDoS zaštitom, VPS VDS servere 🔥 Kupite pouzdan hosting za web stranice s DDoS zaštitom, VPS VDS servere | ProHoster