Uvod u operacijske sustave
Hej Habr! Predstavljam vam seriju članaka-prijevoda jedne po meni zanimljive literature - OSTEP. Ovaj materijal prilično duboko raspravlja o radu operativnih sustava nalik unixu, naime o radu s procesima, raznim planerima, memorijom i drugim sličnim komponentama koje čine moderan OS. Izvornike svih materijala možete vidjeti ovdje . Napominjem da je prijevod urađen neprofesionalno (sasvim slobodno), ali se nadam da sam zadržao opći smisao.
Laboratorijske radove iz ove teme možete pronaći ovdje:
Ostali dijelovi:
Također možete pogledati moj kanal na =)
Planiranje: višerazinski red povratnih informacija
U ovom predavanju govorit ćemo o problemima razvoja jednog od najpoznatijih pristupa
planiranje, koje je tzv Višerazinski red povratnih informacija (MLFQ). MLFQ planer prvi je opisao 1962. Fernando J. Corbató u sustavu tzv.
Kompatibilni sustav dijeljenja vremena (CTSS). Ovi radovi (uključujući kasniji rad na
Multics) su naknadno nominirani za Turingovu nagradu. Planer je bio
naknadno poboljšan i stekao izgled koji se može naći već u
neki moderni sustavi.
MLFQ algoritam pokušava riješiti 2 temeljna preklapajuća problema.
Prvo, pokušava optimizirati vrijeme obrade koje se, kao što smo govorili u prethodnom predavanju, optimizira metodom pokretanja na početku reda najviše
kratke zadatke. Međutim, OS ne zna koliko dugo će određeni proces trajati, a ovo
potrebna znanja za rad SJF, STCF algoritama. drugo, MLFQ pokušava
učiniti sustav osjetljivim na korisnike (na primjer, za one koji sjede i
buljiti u ekran čekajući da se zadatak završi) i tako minimizirati vrijeme
odgovor. Nažalost, algoritmi poput RR poboljšavaju vrijeme odziva, ali iznimno
imaju loš utjecaj na metriku vremena obrade. Otud naš problem: Kako dizajnirati
planer koji će ispuniti naše zahtjeve, a da ne zna ništa o tome
prirodu procesa općenito? Kako planer može naučiti karakteristike zadataka,
koje pokreće i tako donosi bolje odluke o planiranju?
Suština problema: Kako planirati postavljanje zadataka bez savršenog znanja?
Kako dizajnirati planer koji istovremeno smanjuje vrijeme odgovora
za interaktivne zadatke i u isto vrijeme minimizira vrijeme obrade bez znanja
poznavanje vremena izvršenja zadatka?
Napomena: učimo iz prethodnih događaja
MLFQ red je odličan primjer sustava koji uči iz
prošlih događaja za predviđanje budućnosti. Slični pristupi su česti
naći u OS-u (I mnogim drugim granama računalne znanosti, uključujući grane
hardverska predviđanja i algoritmi za predmemoriju). Slična putovanja
pokreću se kada zadaci imaju faze ponašanja i stoga su predvidljivi.
Međutim, treba biti oprezan s ovom tehnikom jer su predviđanja vrlo jednostavna
može se pokazati netočnom i dovesti sustav do donošenja gorih odluka od
bio bi uopće bez znanja.
MLFQ: Osnovna pravila
Pogledajmo osnovna pravila MLFQ algoritma. I premda implementacije ovog algoritma
Ima ih nekoliko, osnovni pristupi su slični.
U implementaciji koju ćemo promatrati, MLFQ će imati nekoliko
odvojeni redovi, od kojih će svaki imati drugačiji prioritet. Bilo kada,
zadatak spreman za izvršenje nalazi se u jednom redu. MLFQ koristi prioritete,
odlučiti koji zadatak pokrenuti za izvršenje, tj. zadatak s višim
prioritet (zadatak iz reda s najvišim prioritetom) će se prvi pokrenuti
red.
Naravno, u određenom redu čekanja može biti više od jednog zadatka, pa
pa će imati isti prioritet. U ovom slučaju će se koristiti mehanizam
RR za raspored izvođenja među ovim zadacima.
Tako dolazimo do dva osnovna pravila za MLFQ:
- Pravilo 1: Ako je prioritet (A) > prioritet (B), zadatak A će biti pokrenut (B neće)
- Pravilo 2: Ako je prioritet(A) = prioritet(B), A&B se pokreću koristeći RR
Na temelju gore navedenog, ključni elementi za planiranje MLFQ
su prioriteti. Umjesto da svakome date fiksni prioritet
zadatak, MLFQ mijenja svoj prioritet ovisno o promatranom ponašanju.
Na primjer, ako zadatak neprestano baca posao na CPU dok čeka na unos s tipkovnice,
MLFQ će održati prioritet procesa visokim jer je to kako
trebao bi funkcionirati interaktivni proces. Ako je, naprotiv, zadatak stalno i
intenzivno koristi CPU tijekom dugog razdoblja, MLFQ će ga smanjiti
prioritet. Stoga će MLFQ proučavati ponašanje procesa dok se izvode
i ponašanja korištenja.
Nacrtajmo primjer kako bi redovi mogli izgledati u nekom trenutku
vremena i onda dobijete nešto poput ovoga:
U ovoj shemi, 2 procesa A i B su u redu čekanja najvišeg prioriteta. Postupak
C je negdje u sredini, a proces D na samom kraju reda čekanja. Prema navedenom
Prema opisima algoritma MLFQ, planer će izvršiti zadatke samo s najvišim
prioritet prema RR, a zadaci C, D bit će bez posla.
Naravno, statična snimka neće dati potpunu sliku o tome kako MLFQ funkcionira.
Važno je točno razumjeti kako se slika mijenja tijekom vremena.
Pokušaj 1: Kako promijeniti prioritet
U ovom trenutku morate odlučiti kako će MLFQ promijeniti razinu prioriteta
zadatke (a time i položaj zadatka u redu čekanja) kako napreduje kroz svoj životni ciklus. Za
ovo je potrebno imati na umu tijek rada: određeni iznos
interaktivni zadaci s kratkim vremenom izvođenja (a time i čestim izdavanjem
CPU) i nekoliko dugotrajnih zadataka koji koriste CPU cijelo svoje radno vrijeme, dok
Za takve zadatke vrijeme odziva nije važno. I na ovaj način možete napraviti svoj prvi pokušaj
implementirati MLFQ algoritam sa sljedećim pravilima:
- Pravilo 3: Kada zadatak uđe u sustav, postavlja se u red čekanja s najvišim
- prioritet.
- Pravilo 4a: Ako zadatak koristi cijeli vremenski prozor koji mu je dodijeljen, tada ga
- prioritet je smanjen.
- Pravilo 4b: Ako zadatak oslobodi CPU prije isteka vremenskog okvira, tada ga
- ostaje s istim prioritetom.
Primjer 1: Jedan dugotrajni zadatak
Kao što se može vidjeti u ovom primjeru, prijemni zadatak postavljen je s najvišim
prioritet. Nakon vremenskog okvira od 10 ms, proces se degradira u prioritetu
planer. Nakon sljedećeg vremenskog prozora, zadatak se konačno degradira na
najniži prioritet u sustavu, gdje i ostaje.
Primjer 2: Isporučen kratki zadatak
Sada da vidimo primjer kako će MLFQ pokušati pristupiti SJF-u. U tome
na primjer, dva zadatka: A, koji je zadatak koji se stalno izvodi dugo
zauzima CPU i B, što je kratki interaktivni zadatak. Pretpostavimo
da je A već neko vrijeme radio do trenutka kada je stigao zadatak B.
Ovaj grafikon prikazuje rezultate scenarija. Zadatak A, kao i svaki zadatak,
Zauzetost CPU-a bila je na samom dnu. Zadatak B će stići u trenutku T=100 i hoće
postavljeni u red čekanja s najvišim prioritetom. Budući da je njegovo vrijeme rada kratko, dakle
završit će prije nego što stigne do posljednjeg reda čekanja.
Iz ovog primjera treba razumjeti glavni cilj algoritma: budući da algoritam ne
zna je li zadatak dugačak ili kratak, tada prije svega pretpostavlja da je zadatak
kratko i daje mu najveći prioritet. Ako je ovo stvarno kratak zadatak, onda
bit će dovršen brzo, inače ako je dug zadatak, ići će sporo
prioritet dolje i uskoro će dokazati da je ona doista dugačak zadatak koji ne
zahtijeva odgovor.
Primjer 3: Što je s I/O?
Sada pogledajmo I/O primjer. Kao što je navedeno u pravilu 4b,
ako proces oslobodi procesor bez korištenja svog procesorskog vremena,
tada ostaje na istoj razini prioriteta. Smisao ovog pravila je vrlo jednostavan
- ako interaktivni posao izvodi mnogo I/O operacija, na primjer, čekanje
od pritisaka korisničke tipke ili miša, takav će zadatak osloboditi procesor
prije dodijeljenog prozora. Ne bismo htjeli smanjiti prioritet takvog zadatka,
i tako će ostati na istoj razini.
Ovaj primjer pokazuje kako će algoritam raditi s takvim procesima - interaktivni posao B, koji treba samo CPU 1 ms prije izvršenja
I/O proces i dugotrajni posao A, koji sve svoje vrijeme provodi koristeći CPU.
MLFQ drži proces B na najvišem prioritetu jer se nastavlja
otpustite CPU. Ako je B interaktivni zadatak, tada je algoritam postigao
Vaš cilj je brzo izvršavanje interaktivnih zadataka.
Problemi s trenutnim MLFQ algoritmom
U prethodnim primjerima izgradili smo osnovnu verziju MLFQ-a. A čini se da on
radi svoj posao dobro i pošteno, pravedno raspoređujući CPU vrijeme
duge zadatke i dopuštanje kratkih ili opsežnih zadataka
brzo raditi na I/O. Nažalost, ovaj pristup sadrži nekoliko
ozbiljnih problema.
Prvo, problem gladi: ako sustav ima mnogo interaktivnih
zadataka, onda će oni potrošiti sve procesorsko vrijeme i tako niti jedan dugo vremena
zadatak se neće moći izvršiti (umiru od gladi).
drugo, pametni korisnici mogu napisati svoje programe tako da
prevariti rokovnika. Prijevara leži u tome da se nešto prisili
Planer daje procesu više CPU vremena. Algoritam koji
gore opisano prilično je osjetljivo na slične napade: prije vremenskog prozora praktički
završio, morate izvršiti I/O operaciju (za neke, bez obzira na datoteku)
i time osloboditi CPU. Takvo ponašanje će vam omogućiti da ostanete u istom
samom redu čekanja i opet dobiti veći postotak CPU vremena. Ako to uradiš
to je točno (na primjer, izvrši 99% vremena prozora prije otpuštanja CPU-a),
takav zadatak može jednostavno monopolizirati procesor.
Konačno, program može promijeniti svoje ponašanje tijekom vremena. Ti zadaci
koji su koristili CPU mogu postati interaktivni. U našem primjeru, slično
zadaci neće dobiti tretman koji zaslužuju od planera kao što bi to učinili drugi
(početni) interaktivni zadaci.
Pitanje za publiku: kakvi napadi na raspored mogu biti izvedeni u modernom svijetu?
Pokušaj 2: Povećanje prioriteta
Pokušajmo promijeniti pravila i vidjeti možemo li izbjeći probleme s
post. Što možemo učiniti da to bude povezano
CPU zadaci će dobiti svoje vrijeme (čak i ako ne dugo).
Kao jednostavno rješenje problema, možete predložiti povremeno
podići prioritet svih takvih zadataka u sustavu. Postoji mnogo načina
Da bismo to postigli, pokušajmo implementirati nešto jednostavno kao primjer: prevedi
svi zadaci odmah dobivaju najviši prioritet, stoga novo pravilo:
- Rule5: Nakon određenog perioda S, sve zadatke u sustavu premjestiti u najviši red.
Naše novo pravilo rješava dva problema odjednom. Prvo, procesi
zajamčeno neće gladovati: zadaci koji imaju najveći prioritet bit će podijeljeni
CPU vrijeme prema RR algoritmu i time će svi procesi dobiti
CPU vrijeme. Drugo, ako je neki proces koji je prethodno korišten
samo procesor postaje interaktivan, on će ostati u redu s najvišim
prioritet nakon primanja jednokratnog povećanja prioriteta na najviši.
Pogledajmo primjer. U ovom scenariju, razmotrite korištenje jednog procesa
CPU i dva interaktivna, kratka procesa. Lijevo na slici, slika prikazuje ponašanje bez prioritetne promocije, pa tako dugotrajni zadatak počinje gladovati nakon što dva interaktivna zadatka stignu u sustav. Na slici desno, povećanje prioriteta provodi se svakih 50 ms i stoga je zajamčeno da će svi procesi dobiti CPU vrijeme i povremeno će se pokretati. 50ms u ovom slučaju uzeto je kao primjer; u stvarnosti je taj broj malo veći.
Očito, dodavanje vremena periodičkog povećanja S dovodi do
logično pitanje: koju vrijednost postaviti? Jedan od počašćenih
sistemski inženjeri John Ousterhout takve su količine u sustavima nazivali voo-doo
konstanta, budući da im je na neki način bila potrebna crna magija za ispravljanje
izlažući. A, nažalost, S ima takav miris. Ako postavite i vrijednost
veliki - dugi zadaci će početi gladovati. A ako postavite prenisku vrijednost,
Interaktivni zadaci neće dobiti odgovarajuće CPU vrijeme.
Pokušaj 3: Bolje računovodstvo
Sada imamo još jedan problem za riješiti: kako ne
dopustiti da naš planer bude prevaren? Ljudi koji su krivi za ovu mogućnost su
pravila 4a, 4b, koja dopuštaju da posao zadrži prioritet, oslobađajući procesor
prije nego što istekne zadano vrijeme. Kako se nositi s ovim?
Rješenje u ovom slučaju može se smatrati boljim obračunom CPU vremena na svakom
MLFQ razina. Umjesto da zaboravite vrijeme koje je program koristio
procesora za dodijeljeno razdoblje, treba ga uzeti u obzir i spremiti. Nakon
proces je potrošio svoje dodijeljeno vrijeme, treba ga degradirati na sljedeći
razina prioriteta. Sada nije važno kako će proces iskoristiti svoje vrijeme - kako
stalno računanje na procesoru ili kao broj poziva. Tako,
pravilo 4 treba prepisati u sljedeći oblik:
- Rule4: Nakon što zadatak iskoristi svoje dodijeljeno vrijeme u trenutnom redu čekanja (bez obzira koliko je puta oslobodio CPU), prioritet tog zadatka se snižava (pomiče se niz red čekanja).
Pogledajmo primjer:
»
Slika pokazuje što se događa ako pokušate prevariti planer, npr
da je bilo s prethodnim pravilima 4a, 4b rezultat na lijevoj strani bi se dobio. Sretna Nova
pravilo je rezultat s desne strane. Prije zaštite, svaki proces je mogao pozvati I/O prije završetka i
tako dominiraju CPU-om, nakon što omoguće zaštitu, bez obzira na ponašanje
I/O, on će se i dalje pomicati dolje u redu čekanja i stoga neće moći nepošteno
preuzeti CPU resurse.
Poboljšanje MLFQ i drugi problemi
S navedenim poboljšanjima dolaze novi problemi: jedan od glavnih
Pitanja - kako parametrizirati takav planer? Oni. Koliko bi trebalo biti
redovi? Kolika bi trebala biti veličina prozora programa unutar reda? Kako
Prioritet programa često treba povećati kako bi se izbjeglo gladovanje i
uzeti u obzir promjenu ponašanja programa? Ne postoji jednostavan odgovor na ova pitanja
odgovor i samo eksperimenti s opterećenjima i naknadnom konfiguracijom
planer može dovesti do neke zadovoljavajuće ravnoteže.
Na primjer, većina MLFQ implementacija omogućuje vam dodjeljivanje različitih
vremenski intervali za različite redove. Redovi čekanja visokog prioriteta obično
propisani su kratki razmaci. Ti se redovi sastoje od interaktivnih zadataka,
prebacivanje između kojih je prilično osjetljivo i trebalo bi trajati 10 ili manje
ms. Nasuprot tome, redovi čekanja niskog prioriteta sastoje se od dugotrajnih zadataka koji koriste
CPU. I u ovom slučaju, dugi vremenski intervali vrlo dobro odgovaraju (100ms).
U ovom primjeru postoje 2 zadatka koja su radila u redu čekanja visokog prioriteta 20
ms, podijeljen u prozore od 10 ms. 40 ms u srednjem redu (prozor od 20 ms) i u niskom prioritetu
Vremenski prozor čekanja postao je 40 ms gdje su zadaci dovršili svoj posao.
Implementacija MLFQ-a u OS Solaris je klasa planera za dijeljenje vremena.
Planer će osigurati set tablica koje definiraju točno onako kako treba
prioritet procesa se mijenja tijekom njegovog života, koja bi trebala biti veličina
dodijeljeni prozor i koliko često trebate povisiti prioritete zadataka. Administrator
sustavi mogu komunicirati s ovom tablicom i uzrokovati ponašanje planera
različito. Prema zadanim postavkama, ova tablica ima 60 redova s postupnim povećanjem
veličina prozora od 20 ms (visoki prioritet) do nekoliko stotina ms (niski prioritet) i
također s pojačavanjem svih zadataka jednom u sekundi.
Drugi MLFQ planeri ne koriste tablicu ili bilo koji specifičan
pravila koja su opisana u ovom predavanju, naprotiv, izračunavaju prioritete pomoću
matematičke formule. Na primjer, FreeBSD planer koristi formulu za
izračunati trenutni prioritet zadatka na temelju toga koliko dugo proces traje
korišten CPU. Osim toga, korištenje CPU-a s vremenom opada, i tako
Stoga se povećanje prioriteta događa nešto drugačije nego što je gore opisano. To je istina
koji se nazivaju algoritmi raspada. Od verzije 7.1, FreeBSD koristi ULE planer.
Na kraju, mnogi planeri imaju i druge značajke. Na primjer, neki
planeri rezerviraju najviše razine za rad operacijskog sustava i na taj način
Stoga niti jedan korisnički proces ne može dobiti najviši prioritet
sustav. Neki sustavi vam omogućuju davanje savjeta kao pomoć
planer može pravilno postaviti prioritete. Na primjer, pomoću naredbe lijepo
možete povećati ili smanjiti prioritet zadatka i time povećati ili
smanjiti šanse programa da koristi CPU vrijeme.
MLFQ: Sažetak
Opisali smo pristup planiranju nazvan MLFQ. Njegovo ime
zatvoren u principu rada - ima nekoliko redova i koristi povratnu vezu
za određivanje prioriteta zadatka.
Konačni oblik pravila bit će sljedeći:
- Rule1: Ako je prioritet(A) > prioritet(B), zadatak A će biti pokrenut (B neće)
- Rule2: Ako je prioritet(A) = prioritet(B), A&B se pokreću koristeći RR
- Rule3: Kada zadatak uđe u sustav, postavlja se u red čekanja s najvišim prioritetom.
- Rule4: Nakon što zadatak iskoristi svoje dodijeljeno vrijeme u trenutnom redu čekanja (bez obzira koliko je puta oslobodio CPU), prioritet tog zadatka se snižava (pomiče se niz red čekanja).
- Rule5: Nakon određenog perioda S, sve zadatke u sustavu premjestiti u najviši red.
MLFQ je zanimljiv iz sljedećeg razloga - umjesto da zahtijeva znanje o
prirodu zadatka unaprijed, algoritam proučava prošlo ponašanje zadatka i postavlja
prioritete u skladu s tim. Tako pokušava sjediti na dvije stolice odjednom - postići produktivnost za male zadatke (SJF, STCF) i pošteno trčati dugo,
Poslovi koji opterećuju CPU. Stoga mnogi sustavi, uključujući BSD i njihove derivate,
Solaris, Windows, Mac koriste neki oblik algoritma kao planer
MLFQ kao osnova.
Dodatni materijali:
- (Computing)
Izvor: www.habr.com