Įvadas į operacines sistemas
Sveiki, Habr! Norėčiau atkreipti jūsų dėmesį į vienos, mano nuomone, įdomios literatūros - OSTEP - straipsnių-vertimų ciklą. Šioje medžiagoje gana nuodugniai aptariamas į unix panašių operacinių sistemų darbas, būtent darbas su procesais, įvairiais planuokliais, atmintimi ir kitais panašiais komponentais, kurie sudaro šiuolaikinę OS. Visų medžiagų originalus galite pamatyti čia . Atkreipkite dėmesį, kad vertimas atliktas neprofesionaliai (gana laisvai), bet tikiuosi, kad išlaikiau bendrą prasmę.
Laboratorinius darbus šia tema galite rasti čia:
Kitos dalys:
Taip pat galite peržiūrėti mano kanalą adresu =)
Įvadas į planuoklį
Problemos esmė: Kaip sukurti planavimo politiką
Kaip turėtų būti kuriamos pagrindinės planavimo politikos sistemos? Kokios turėtų būti pagrindinės prielaidos? Kokie rodikliai yra svarbūs? Kokie pagrindiniai metodai buvo naudojami ankstyvosiose skaičiavimo sistemose?
Darbo krūvio prielaidos
Prieš aptardami galimą politiką, pirmiausia padarykime keletą supaprastinančių nukrypimų apie sistemoje veikiančius procesus, kurie bendrai vadinami darbo krūvis. Darbo krūvio apibrėžimas yra svarbi kūrimo politikos dalis, ir kuo daugiau žinote apie darbo krūvį, tuo geresnę politiką galėsite parašyti.
Padarykime tokias prielaidas apie sistemoje veikiančius procesus, kartais dar vadinamus darbo vietų (užduotys). Beveik visos šios prielaidos nėra tikroviškos, tačiau būtinos mąstymo vystymuisi.
- Kiekviena užduotis atliekama tiek pat laiko,
- Visos užduotys nustatomos vienu metu,
- Paskirta užduotis veikia iki jos atlikimo,
- Visos užduotys naudoja tik CPU,
- Kiekvienos užduoties vykdymo laikas yra žinomas.
Planuoklio metrika
Be kai kurių prielaidų apie apkrovą, reikalingas kitas įrankis, leidžiantis palyginti skirtingas planavimo strategijas: planavimo metrika. Metrika yra tik kažkoks matas. Yra keletas metrikų, kurias galima naudoti planuotojams palyginti.
Pavyzdžiui, naudosime metriką, vadinamą apsisukimo laikas (apsisukimo laikas). Užduoties vykdymo laikas apibrėžiamas kaip skirtumas tarp užduoties atlikimo laiko ir užduoties atvykimo į sistemą laiko.
Tturnaround=Tužbaigimas-Tarrival
Kadangi darėme prielaidą, kad visos užduotys atkeliavo tuo pačiu metu, tada Ta=0, taigi Tt=Tc. Ši vertė natūraliai pasikeis, kai pakeisime aukščiau pateiktas prielaidas.
Kitas rodiklis - teisingumas (sąžiningumas, sąžiningumas). Produktyvumas ir sąžiningumas dažnai yra priešingos planavimo savybės. Pavyzdžiui, planuoklis gali optimizuoti našumą, bet už tai, kad reikia laukti, kol bus paleistos kitos užduotys, taip sumažinant sąžiningumą.
FIRST IN FIRST OUT (FIFO)
Pats paprasčiausias algoritmas, kurį galime įgyvendinti, vadinamas FIFO arba pirmas atvykęs, pirmas aptarnaujantis (išėjus). Šis algoritmas turi keletą privalumų: jį labai lengva įgyvendinti, jis atitinka visas mūsų prielaidas ir puikiai atlieka savo darbą.
Pažiūrėkime į paprastą pavyzdį. Tarkime, vienu metu buvo nustatytos 3 užduotys. Tačiau tarkime, kad A užduotis atėjo šiek tiek anksčiau nei visos kitos, todėl ji pasirodys vykdymo sąraše anksčiau nei kitos, kaip ir B, palyginti su C. Tarkime, kad kiekviena iš jų bus vykdoma 10 sekundžių. Kiek šiuo atveju vidutiniškai reikės atlikti šias užduotis?
Suskaičiavę reikšmes - 10+20+30 ir padalijus iš 3, gauname vidutinį programos vykdymo laiką, lygų 20 sekundžių.
Dabar pabandykime pakeisti savo prielaidas. Visų pirma, 1 prielaida, todėl mes nebemanome, kad kiekvienai užduočiai atlikti reikia tiek pat laiko. Kaip FIFO seksis šį kartą?
Pasirodo, skirtingi užduočių vykdymo laikai turi itin neigiamą įtaką FIFO algoritmo produktyvumui. Tarkime, kad A užduočiai atlikti prireiks 100 sekundžių, o B ir C – po 10 sekundžių.
Kaip matyti iš paveikslo, vidutinis sistemos laikas bus (100+110+120)/3=110. Šis efektas vadinamas konvojaus efektas, kai kai kurie trumpalaikiai resurso vartotojai stos į eilę po didelio vartotojo. Tai tarsi eilė bakalėjos parduotuvėje, kai priešais jus yra klientas su pilnu krepšeliu. Geriausias problemos sprendimas – pabandyti pakeisti kasos aparatą arba atsipalaiduoti ir giliai įkvėpti.
Pirmiausia trumpiausias darbas
Ar įmanoma kaip nors išspręsti panašią situaciją su sunkiasvoriais procesais? Žinoma. Kitas planavimo tipas vadinamasPirmiausia trumpiausias darbas (SJF). Jo algoritmas taip pat gana primityvus – kaip rodo pavadinimas, trumpiausios užduotys bus paleidžiamos pirmiausia viena po kitos.
Šiame pavyzdyje tų pačių procesų vykdymo rezultatas pailgės vidutinis programos vykdymo laikas ir bus lygus 50 vietoj 110, kuris yra beveik 2 kartus geresnis.
Taigi, esant prielaidai, kad visos užduotys ateina tuo pačiu metu, SJF algoritmas atrodo optimaliausias algoritmas. Tačiau mūsų prielaidos vis dar neatrodo tikroviškos. Šį kartą keičiame 2 prielaidą ir šį kartą įsivaizduojame, kad užduotys gali būti bet kuriuo metu, o ne visos vienu metu. Kokias problemas tai gali sukelti?
Įsivaizduokime, kad užduotis A (100c) ateina pirmoji ir pradedama vykdyti. Esant t=10, ateina užduotys B ir C, kurių kiekviena užtruks po 10 sekundžių. Taigi vidutinis vykdymo laikas yra (100+(110-10)+(120-10))3 = 103. Ką planuotojas galėtų padaryti, kad tai pagerintų?
Pirmiausia trumpiausias laikas iki užbaigimo (STCF)
Siekdami pagerinti situaciją, neįtraukiame 3 prielaidos, kad programa paleidžiama ir veikia iki pabaigos. Be to, mums reikės techninės įrangos palaikymo ir, kaip galite spėti, mes naudosime laikmatis nutraukti vykdomą užduotį ir konteksto perjungimas. Taigi, planuoklis gali ką nors padaryti tuo metu, kai ateina užduotys B, C – sustabdyti A užduoties vykdymą, o užduotis B ir C įdėti į apdorojimą, o joms pasibaigus tęsti proceso A vykdymą. Toks planuoklis vadinamas STCFarba Pirmiausia prevencinis darbas.
Šio planuotojo rezultatas bus toks: ((120-0)+(20-10)+(30-10))/3=50. Taigi toks planuotojas tampa dar optimalesnis mūsų užduotims.
Metrinis atsako laikas
Taigi, jei žinome užduočių vykdymo laiką ir kad šios užduotys naudoja tik centrinį procesorių, STCF bus geriausias sprendimas. Ir kadaise šie algoritmai veikė gana gerai. Tačiau dabar vartotojas didžiąją laiko dalį praleidžia prie terminalo ir tikisi produktyvios interaktyvios patirties. Taip gimė nauja metrika – atsakymo laikas (atsakymas).
Reakcijos laikas apskaičiuojamas taip:
Tresponse=Tfirstrun−Tarrival
Taigi, ankstesniame pavyzdyje atsako laikas bus: A=0, B=0, C=10 (abg=3,33).
Ir pasirodo, kad STCF algoritmas nėra toks geras situacijoje, kai vienu metu atkeliauja 3 užduotys – teks palaukti, kol smulkios užduotys bus visiškai atliktos. Taigi algoritmas yra geras apyvartos laiko metrikai, bet blogas interaktyvumo metrikai. Įsivaizduokite, jei sėdėtumėte prie terminalo ir bandytumėte įvesti simbolius į redaktorių ir turėtumėte laukti daugiau nei 10 sekundžių, nes procesorių užimtų kokia nors kita užduotis. Tai nėra labai malonu.
Taigi susiduriame su kita problema – kaip sukurti planavimo priemonę, kuri būtų jautri reakcijos laikui?
Varžybos ratų sistema
Šiai problemai išspręsti buvo sukurtas algoritmas Varžybos ratų sistema (RR). Pagrindinė idėja yra gana paprasta: užuot vykdydami užduotis, kol jos bus baigtos, mes vykdysime užduotį tam tikrą laiką (vadinamą laiko pjūviu), o tada pereisime prie kitos užduotys iš eilės. Algoritmas kartoja savo darbą, kol bus baigtos visos užduotys. Tokiu atveju programos veikimo laikas turi būti kartotinis laiko, po kurio laikmatis nutrauks procesą. Pavyzdžiui, jei laikmatis pertraukia procesą kas x = 10 ms, tada proceso vykdymo lango dydis turi būti 10 kartotinis ir būti 10,20, 10 arba x * XNUMX.
Pažiūrėkime į pavyzdį: ABC užduotys į sistemą patenka vienu metu ir kiekviena iš jų nori paleisti 5 sekundes. SJF algoritmas atliks kiekvieną užduotį prieš pradėdamas kitą. Priešingai, RR algoritmas su paleidimo langu = 1s atliks užduotis taip (4.3 pav.):
(Vėl SJF (blogas atsako laikas)
(Round Robin (geras atsako laikas)
Vidutinis RR algoritmo atsako laikas yra (0+1+2)/3=1, o SJF (0+5+10)/3=5.
Logiška manyti, kad laiko langas yra labai svarbus RR parametras; kuo jis mažesnis, tuo ilgesnis atsako laikas. Tačiau neturėtumėte jo padaryti per mažo, nes konteksto perjungimo laikas taip pat turės įtakos bendram našumui. Taigi, vykdymo lango laiko pasirinkimą nustato OS architektas ir jis priklauso nuo užduočių, kurias jame planuojama vykdyti. Konteksto perjungimas nėra vienintelė paslaugos operacija, kuri gaišina laiką – veikianti programa veikia su daugybe kitų dalykų, pavyzdžiui, įvairios talpyklos, o su kiekvienu perjungimu reikia išsaugoti ir atkurti šią aplinką, kuri taip pat gali užtrukti daug. laikas.
RR yra puikus planuotojas, jei kalbėtume tik apie atsako laiko metriką. Bet kaip užduoties atlikimo laiko metrika elgsis naudojant šį algoritmą? Apsvarstykite aukščiau pateiktą pavyzdį, kai A, B, C veikimo laikas = 5s ir atvyksta tuo pačiu metu. Užduotis A baigsis 13 val., B – 14 val., C – 15 sek., o vidutinis atlikimo laikas bus 14 sek. Taigi, RR yra blogiausias apyvartos metrikos algoritmas.
Apskritai, bet koks RR tipo algoritmas yra teisingas; jis vienodai padalija procesoriaus laiką visiems procesams. Taigi šie rodikliai nuolat prieštarauja vienas kitam.
Taigi, turime kelis kontrastingus algoritmus ir tuo pačiu dar liko kelios prielaidos – kad užduoties laikas yra žinomas ir užduotis naudoja tik procesorių.
Maišymas su I/O
Visų pirma, pašalinkime 4 prielaidą, kad procesas naudoja tik centrinį procesorių; žinoma, taip nėra ir procesai gali pasiekti kitą įrangą.
Kai kuris nors procesas reikalauja įvesties / išvesties operacijos, procesas pereina į užblokuotą būseną ir laukia, kol įvestis / išvestis bus baigta. Jei įvestis / išvestis siunčiama į standųjį diską, tokia operacija gali užtrukti iki kelių ms ar ilgiau, o procesorius šiuo metu bus neaktyvus. Per šį laiką planuotojas gali užimti procesorių bet kokiu kitu procesu. Kitas sprendimas, kurį turės priimti planuotojas, yra tada, kai procesas baigs įvesties / išvesties procesą. Kai taip atsitiks, įvyks pertraukimas ir OS įves į parengties būseną procesą, kuris iškvietė I/O.
Pažvelkime į kelių problemų pavyzdį. Kiekvienam iš jų reikia 50 ms procesoriaus laiko. Tačiau pirmasis prisijungs prie įvesties / išvesties kas 10 ms (tai taip pat bus vykdoma kas 10 ms). O procesas B tiesiog naudoja 50 ms procesorių be I/O.
Šiame pavyzdyje naudosime STCF planuoklį. Kaip elgsis planuotojas, jei jame bus paleistas toks procesas kaip A? Jis atliks šiuos veiksmus: iš pradžių jis visiškai atliks A procesą, o tada B procesą.
Tradicinis šios problemos sprendimo būdas yra kiekvieną 10 ms proceso A dalį laikyti atskira užduotimi. Taigi, pradedant nuo STJF algoritmo, pasirinkimas tarp 50 ms užduoties ir 10 ms užduoties yra akivaizdus. Tada, kai bus atlikta A dalis, bus paleistas procesas B ir įvestis / išvestis. Pasibaigus įvesties / išvesties operacijai, vietoj proceso B bus įprasta vėl pradėti 10 ms procesą A. Tokiu būdu galima įgyvendinti persidengimą, kai CPU naudoja kitas procesas, o pirmasis laukia I/O. Ir dėl to sistema geriau išnaudojama – tuo momentu, kai interaktyvūs procesai laukia I/O, procesoriuje gali būti vykdomi kiti procesai.
Orakulo nebėra
Dabar pabandykime atsikratyti prielaidos, kad užduoties vykdymo laikas yra žinomas. Paprastai tai yra pati blogiausia ir nerealiausia prielaida visame sąraše. Tiesą sakant, vidutinėje įprastoje OS pati OS paprastai labai mažai žino apie užduočių vykdymo laiką, taigi kaip tada galite sukurti planuoklį, nežinant, kiek laiko užtruks užduotis? Galbūt galėtume pasinaudoti kai kuriais RR principais, kad išspręstume šią problemą?
Visas
Apžvelgėme pagrindines užduočių planavimo idėjas ir pažvelgėme į 2 planuotojų šeimas. Pirmoji pirmiausia pradeda trumpiausią užduotį ir taip padidina atlikimo laiką, o antroji vienodai blaškosi tarp visų užduočių, padidindama atsako laiką. Abu algoritmai yra blogi ten, kur kitos šeimos algoritmai yra geri. Taip pat pažiūrėjome, kaip lygiagretus procesoriaus ir įvesties/išvesties naudojimas gali pagerinti našumą, bet neišsprendėme OS aiškiaregystės problemos. Kitoje pamokoje pažvelgsime į planuotoją, kuris žvelgia į artimiausią praeitį ir bando nuspėti ateitį. Ir tai vadinama kelių lygių atsiliepimų eile.
Šaltinis: www.habr.com