Uvod u operativne sisteme
Hej Habr! Skrećem vam pažnju na seriju članaka-prevoda jedne po meni zanimljive literature - OSTEP. U ovom materijalu se prilično duboko raspravlja o radu operativnih sistema sličnih unixu, odnosno radu sa procesima, raznim planerima, memorijom i drugim sličnim komponentama koje čine moderni OS. Original svih materijala možete pogledati ovdje . Napominjemo da je prevod urađen neprofesionalno (prilično slobodno), ali se nadam da sam zadržao opšte značenje.
Laboratorijski rad na ovu temu možete pronaći ovdje:
Ostali dijelovi:
Takođe možete pogledati moj kanal na =)
Planiranje: Red za povratne informacije na više nivoa
U ovom predavanju ćemo govoriti o problemima razvoja jednog od najpoznatijih pristupa
planiranje, što se zove Red za povratne informacije na više nivoa (MLFQ). MLFQ planer je prvi opisao Fernando J. Corbató 1962. godine u sistemu pod nazivom
Kompatibilan sistem dijeljenja vremena (CTSS). Ovi radovi (uključujući kasniji rad na
Multics) su kasnije nominovani za Turingovu nagradu. Planer je bio
naknadno poboljšan i stekao izgled kakav se već može naći u
neki savremeni sistemi.
MLFQ algoritam pokušava riješiti 2 fundamentalna problema preklapanja.
Prvo, pokušava optimizirati vrijeme obrta, koje je, kao što smo govorili u prethodnom predavanju, optimizirano metodom počinjanja na početku reda najviše
kratki zadaci. Međutim, OS ne zna koliko dugo će određeni proces trajati, a ovo
neophodna znanja za rad SJF, STCF algoritama. Drugo, MLFQ pokušava
učinite da sistem odgovara korisnicima (na primjer, za one koji sjede i
buljite u ekran čekajući da se zadatak završi) i time minimizirate vrijeme
odgovor. Nažalost, algoritmi poput RR poboljšavaju vrijeme odgovora, ali izuzetno
imaju loš uticaj na metriku vremena obrta. Otuda naš problem: Kako dizajnirati
planer koji će zadovoljiti naše zahtjeve, a da ne zna ništa o tome
priroda procesa uopšte? Kako planer može naučiti karakteristike zadataka,
koje pokreće i na taj način donosi bolje planske odluke?
Suština problema: Kako planirati postavljanje zadataka bez savršenog znanja?
Kako dizajnirati planer koji istovremeno minimizira vrijeme odgovora
za interaktivne zadatke i istovremeno minimizira vrijeme obrade bez znanja
poznavanje vremena izvršenja zadatka?
Napomena: učimo iz prethodnih događaja
MLFQ red je odličan primjer sistema koji uči
prošlih događaja za predviđanje budućnosti. Slični pristupi su često
nalazi se u OS-u (i mnogim drugim granama računarske nauke, uključujući grane
hardverska predviđanja i algoritmi za keširanje). Slična putovanja
se pokreću kada zadaci imaju faze ponašanja i stoga su predvidljivi.
Međutim, s ovom tehnikom treba biti oprezan jer su predviđanja vrlo laka
može se pokazati netačnim i dovesti sistem do donošenja lošijih odluka od
bilo bi bez znanja.
MLFQ: Osnovna pravila
Pogledajmo osnovna pravila MLFQ algoritma. I iako implementacije ovog algoritma
Ima ih nekoliko, osnovni pristupi su slični.
U implementaciji koju ćemo gledati, MLFQ će imati nekoliko
odvojeni redovi, od kojih će svaki imati drugačiji prioritet. bilo kada,
zadatak spreman za izvršenje je u jednom redu. MLFQ koristi prioritete,
odlučiti koji zadatak pokrenuti za izvršenje, tj. zadatak sa višim
prioritet (zadatak iz reda s najvećim prioritetom) će se prvi pokrenuti
queue.
Naravno, može postojati više od jednog zadatka u datom redu, dakle
tako da će imati isti prioritet. U ovom slučaju će se koristiti mehanizam
RR da zakaže trčanje između ovih zadataka.
Tako dolazimo do dva osnovna pravila za MLFQ:
- Pravilo 1: Ako 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 pomoću RR
Na osnovu navedenog, ključni elementi za planiranje MLFQ-a
su prioriteti. Umjesto da svakom date fiksni prioritet
zadatak, MLFQ mijenja svoj prioritet u zavisnosti od uočenog ponašanja.
Na primjer, ako zadatak konstantno baca rad na CPU dok čeka na unos sa tastature,
MLFQ će zadržati visoki prioritet procesa jer je to način
interaktivan proces bi trebao funkcionirati. Ako je, naprotiv, zadatak stalno i
koristi CPU u velikoj meri tokom dužeg perioda, MLFQ će ga smanjiti
prioritet. Stoga će MLFQ proučavati ponašanje procesa dok su pokrenuti
i korištenje ponašanja.
Nacrtajmo primjer kako bi redovi mogli izgledati u nekom trenutku
vrijeme i onda dobijete nešto ovako:
U ovoj šemi, 2 procesa A i B su u redu čekanja najvišeg prioriteta. Proces
C je negdje u sredini, a proces D je na samom kraju reda. Prema gore navedenom
Prema opisima algoritma MLFQ, planer će izvršavati zadatke samo sa najvišim
prioritet prema RR, a zadaci C, D će biti van posla.
Naravno, statički snimak neće dati potpunu sliku o tome kako MLFQ radi.
Važno je razumjeti kako se ta slika mijenja tokom vremena.
Pokušaj 1: Kako promijeniti prioritet
U ovom trenutku morate odlučiti kako će MLFQ promijeniti nivo prioriteta
zadatke (a time i poziciju zadatka u redu) kako napreduje kroz svoj životni ciklus. Za
ovo je neophodno da se ima na umu tok posla: određeni iznos
interaktivni zadaci s kratkim trajanjem (a time i čestim izdavanjem
CPU) i nekoliko dugotrajnih zadataka koji koriste CPU cijelo svoje radno vrijeme, dok
Vrijeme odgovora nije važno za takve zadatke. I na ovaj način možete napraviti svoj prvi pokušaj
implementirajte MLFQ algoritam sa sljedećim pravilima:
- Pravilo 3: Kada zadatak uđe u sistem, on se stavlja u red čekanja sa najvišim
- prioritet.
- Pravilo 4a: Ako zadatak koristi cijeli vremenski okvir koji mu je dodijeljen, onda on
- prioritet je smanjen.
- Pravilo 4b: Ako Zadatak oslobodi CPU prije nego što mu istekne vremenski okvir, onda to
- ostaje sa istim prioritetom.
Primjer 1: Jedan dugotrajni zadatak
Kao što se može vidjeti u ovom primjeru, zadatak prijema je postavljen sa najvišim
prioritet. Nakon vremenskog okvira od 10 ms, proces je degradiran u prioritetu
planer. Nakon sljedećeg vremenskog okvira, zadatak se konačno degradira na
najniži prioritet u sistemu, gdje ostaje.
Primjer 2: Isporučen kratak zadatak
Pogledajmo sada primjer kako će MLFQ pokušati pristupiti SJF-u. U tome
na primjer, dva zadatka: A, koji je dugotrajan zadatak
zauzimaju CPU i B, što je kratak interaktivni zadatak. Pretpostavimo
da je A već radio neko vrijeme kad je stigao zadatak B.
Ovaj grafikon prikazuje rezultate scenarija. Zadatak A, kao i svaki zadatak,
Potrošnja CPU-a je bila na samom dnu. Zadatak B će stići u vrijeme T=100 i hoće
stavljen u red s najvećim prioritetom. Pošto je njegovo vreme rada kratko, onda
završit će se prije nego što stigne do posljednjeg reda.
Iz ovog primjera treba shvatiti glavni cilj algoritma: budući da algoritam to ne čini
zna da li je zadatak dugačak ili kratak, onda pre svega pretpostavlja da je zadatak
kratko i daje mu najviši prioritet. Ako je ovo zaista kratak zadatak, onda
brzo će se završiti, u suprotnom ako je dug zadatak, kretat će se sporo
prioritet dolje i uskoro će dokazati da je ona zaista dugačak zadatak koji nije
zahteva odgovor.
Primjer 3: Šta je sa I/O?
Pogledajmo sada I/O primjer. Kao što je navedeno u pravilu 4b,
ako proces oslobodi procesor bez korištenja cijelog vremena procesora,
onda ostaje na istom nivou prioriteta. Svrha ovog pravila je prilično jednostavna
- ako interaktivni posao izvodi mnogo I/O operacija, na primjer, čeka
pritiskom na korisnički taster ili mišem, takav zadatak će osloboditi procesor
prije dodijeljenog prozora. Ne bismo željeli umanjiti prioritet takvog zadatka,
i time će ostati na istom nivou.
Ovaj primjer pokazuje kako će algoritam raditi s takvim procesima - interaktivni posao B, kojem je CPU potreban samo 1ms 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
oslobodite CPU. Ako je B interaktivni zadatak, onda je algoritam postignut
Vaš cilj je da brzo pokrenete interaktivne zadatke.
Problemi sa trenutnim MLFQ algoritmom
U prethodnim primjerima napravili smo osnovnu verziju MLFQ-a. I čini se da on
radi svoj posao dobro i pošteno, pošteno raspoređujući CPU vreme
duge zadatke i omogućavanje kratkih ili velikih zadataka
raditi na I/O brzo. Nažalost, ovaj pristup sadrži nekoliko
ozbiljni problemi.
Prvo, problem gladi: ako sistem ima mnogo interaktivnih
zadataka, onda će potrošiti svo CPU vrijeme, a time ni jedno dugo vremena
zadatak neće moći da se izvrši (oni umiru od gladi).
Drugo, pametni korisnici bi mogli pisati svoje programe tako da
prevariti planera. Prevara leži u tome da se nešto prisili
Planer daje procesu više CPU vremena. Algoritam koji
gore opisano prilično je ranjivo na slične napade: prije nego što je vremenski okvir praktično
završili, morate izvršiti I/O operaciju (za neke, bez obzira na fajl)
i tako osloboditi CPU. Takvo ponašanje će vam omogućiti da ostanete u istom
sam red i opet dobiti veći procenat CPU vremena. Ako ti uradiš
ovo je tačno (na primjer, izvršite 99% vremena prozora prije otpuštanja CPU-a),
takav zadatak može jednostavno monopolizirati procesor.
Konačno, program može promijeniti svoje ponašanje tokom vremena. Ti zadaci
koja je koristila CPU može postati interaktivna. U našem primjeru slično
zadaci neće dobiti tretman koji zaslužuju od planera kao što bi to činili drugi
(početni) interaktivni zadaci.
Pitanje za publiku: koji se napadi na planer mogu izvesti u modernom svijetu?
Pokušaj 2: Povećanje prioriteta
Pokušajmo promijeniti pravila i vidjeti možemo li izbjeći probleme s njima
posta. Šta možemo učiniti da osiguramo da je to povezano
CPU zadaci će dobiti svoje vrijeme (čak i ako ne dugo).
Kao jednostavno rješenje problema, možete povremeno predložiti
podići prioritet svih takvih zadataka u sistemu. Postoji mnogo načina
Da bismo to postigli, pokušajmo implementirati nešto jednostavno kao primjer: prevesti
svim zadacima se odmah daje najviši prioritet, otuda i novo pravilo:
- Pravilo5: Nakon određenog perioda S, premjestite sve zadatke u sistemu u najviši red čekanja.
Naše novo pravilo rješava dva problema odjednom. Prvo, procesi
garantovano da neće gladovati: zadaci koji imaju najveći prioritet biće podeljeni
CPU vrijeme prema RR algoritmu i time će svi procesi primiti
CPU vrijeme. Drugo, ako je neki proces koji se prethodno koristio
samo procesor postaje interaktivan, on će ostati u redu čekanja sa najvišim
prioritet nakon dobijanja jednokratnog povećanja prioriteta na najviši.
Pogledajmo primjer. U ovom scenariju, razmotrite korištenje jednog procesa
CPU i dva interaktivna, kratka procesa. Na lijevoj strani na slici, slika prikazuje ponašanje bez prioritetnog unapređenja, pa tako dugotrajni zadatak počinje gladovati nakon što dva interaktivna zadatka stignu u sistem. Na slici desno, povećanje prioriteta se vrši svakih 50 ms i tako je zagarantovano da će svi procesi dobiti CPU vreme i periodično će se pokretati. 50ms u ovom slučaju je uzeto kao primjer, u stvarnosti je ovaj broj nešto veći.
Očigledno, dodavanje periodičnog vremena povećanja S dovodi do
logično pitanje: koju vrijednost treba postaviti? Jedan od počašćenih
sistemski inženjeri John Ousterhout nazvao je takve količine u sistemima voo-doo
postojane, jer su im na neki način bila potrebna crna magija za ispravljanje
izlaganje. I, 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 rješavanje: kako ne
dozvoliti da naš planer bude prevaren? Ljudi koji su krivi za ovu mogućnost su
pravila 4a, 4b, koja dozvoljavaju poslu da zadrži prioritet, oslobađajući procesor
prije isteka predviđenog vremena. Kako se nositi s ovim?
Rješenje u ovom slučaju može se smatrati boljim obračunom CPU vremena na svakom
MLFQ nivo. Umjesto da zaboravite vrijeme koje je program koristio
procesora za dodijeljeni period, treba ga uzeti u obzir i sačuvati. Poslije
proces je potrošio svoje dodijeljeno vrijeme, trebalo bi ga degradirati na sljedeći
nivo prioriteta. Sada nije važno kako će proces iskoristiti svoje vrijeme - kako
stalno računajući na procesoru ili kao broj poziva. dakle,
pravilo 4 treba prepisati u sljedeći oblik:
- Pravilo4: Nakon što zadatak potroši svoje dodijeljeno vrijeme u trenutnom redu (bez obzira koliko puta je oslobodio CPU), prioritet tog zadatka se snižava (pomiče se niz red).
Pogledajmo primjer:
»
Slika pokazuje šta se dešava ako pokušate da prevarite planer, na primer
da je s prethodnim pravilima 4a, 4b rezultat bi se dobio lijevo. Sretna nova
pravilo je rezultat na desnoj strani. Prije zaštite, bilo koji proces je mogao pozvati I/O prije završetka i
tako dominiraju CPU-om, nakon omogućavanja zaštite, bez obzira na ponašanje
I/O, on će se i dalje kretati dolje u redu i stoga neće moći nepošteno
preuzimaju CPU resurse.
Poboljšanje MLFQ-a i drugi problemi
Uz gore navedena poboljšanja dolaze novi problemi: jedan od glavnih
Pitanja - kako parametrirati takav planer? One. Koliko bi trebalo da bude
redovi? Koja 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 eksperimente sa opterećenjima i naknadnom konfiguracijom
planer može dovesti do neke zadovoljavajuće ravnoteže.
Na primjer, većina implementacija MLFQ dozvoljava vam da dodijelite različite
vremenski intervali za različite redove. Redovi sa visokim prioritetom obično
propisani su kratki intervali. Ovi redovi se sastoje od interaktivnih zadataka,
prebacivanje između kojih je prilično osjetljivo i trebalo bi trajati 10 ili manje
gospođa. Nasuprot tome, redovi niskog prioriteta sastoje se od dugotrajnih zadataka koji koriste
CPU. I u ovom slučaju, dugi vremenski intervali se vrlo dobro uklapaju (100ms).
U ovom primjeru postoje 2 zadatka koji su radili u redu čekanja 20 visokog prioriteta
ms, podijeljeno u prozore od 10 ms. 40ms u srednjem redu čekanja (20ms prozor) iu niskom prioritetu
Vremenski okvir čekanja je postao 40 ms kada su zadaci završili svoj posao.
Implementacija MLFQ-a za Solaris OS je klasa planera za podjelu vremena.
Planer će obezbediti skup tabela koje definišu tačno onako kako treba
prioritet procesa se menja tokom njegovog života, kolika bi trebala biti veličina
dodijeljeni prozor i koliko često trebate podići prioritete zadataka. Administrator
sistemi mogu komunicirati s ovom tablicom i uzrokovati ponašanje planera
drugačije. Ova tabela podrazumevano ima 60 redova sa postepenim povećanjem
veličina prozora od 20ms (visoki prioritet) do nekoliko stotina ms (niski prioritet), i
također uz pojačanje svih zadataka jednom u sekundi.
Drugi MLFQ planeri ne koriste tabelu ili bilo šta specifično
pravila koja su opisana u ovom predavanju, naprotiv, računaju prioritete koristeći
matematičke formule. Na primjer, FreeBSD planer koristi formulu za
izračunajte trenutni prioritet zadatka na osnovu toga koliko dugo traje proces
korišten CPU. Osim toga, korištenje CPU-a vremenom opada, itd
Dakle, povećanje prioriteta se dešava nešto drugačije nego što je gore opisano. Istina je
nazivaju se algoritmi raspadanja. Od verzije 7.1, FreeBSD koristi ULE planer.
Konačno, mnogi planeri imaju i druge karakteristike. Na primjer, neke
planeri rezervišu najviše nivoe za rad operativnog sistema i na taj način
Dakle, nijedan korisnički proces ne može dobiti najveći prioritet
sistem. Neki sistemi vam omogućavaju da date savjete za pomoć
planer može ispravno postaviti prioritete. Na primjer, korištenjem naredbe lijep
možete povećati ili smanjiti prioritet zadatka i tako povećati ili
smanjiti šanse programa da koristi CPU vrijeme.
MLFQ: Rezime
Opisali smo pristup planiranju nazvan MLFQ. Njegovo ime
zatvoren u principu rada - ima nekoliko redova i koristi povratne informacije
da odredite prioritet zadatka.
Konačni oblik pravila će biti sljedeći:
- Pravilo1: Ako prioritet(A) > Prioritet(B), zadatak A će biti pokrenut (B neće)
- Pravilo2: Ako je prioritet(A) = Prioritet(B), A&B se pokreću pomoću RR
- Pravilo3: Kada zadatak uđe u sistem, stavlja se u red s najvećim prioritetom.
- Pravilo4: Nakon što zadatak potroši svoje dodijeljeno vrijeme u trenutnom redu (bez obzira koliko puta je oslobodio CPU), prioritet tog zadatka se snižava (pomiče se niz red).
- Pravilo5: Nakon određenog perioda S, premjestite sve zadatke u sistemu u najviši red čekanja.
MLFQ je zanimljiv iz sljedećeg razloga - umjesto da zahtijeva znanje o
prirodu zadatka unaprijed, algoritam proučava prošlo ponašanje zadatka i skupova
prioriteti u skladu s tim. Stoga pokušava sjediti na dvije stolice odjednom - da postigne produktivnost za male zadatke (SJF, STCF) i da pošteno dugo trči,
Poslovi učitavanja CPU-a. Stoga mnogi sistemi, uključujući BSD i njihove derivate,
Solaris, Windows, Mac koriste neki oblik algoritma kao planer
MLFQ kao osnova.
Dodatni materijali:
- (računarstvo)
izvor: www.habr.com