Aféierung fir Betribssystemer
Hey Habr! Ech géif gären op Är Opmierksamkeet eng Serie vun Artikelen-Iwwersetzunge vun enger interessant Literatur an menger Meenung ze bréngen - OSTEP. Dëst Material diskutéiert ganz déif d'Aarbecht vun Unix-ähnlechen Betribssystemer, nämlech d'Aarbecht mat Prozesser, verschidde Scheduler, Erënnerung an aner ähnlech Komponenten, déi e modernen OS ausmaachen. Dir kënnt d'Original vun all Material hei gesinn . Maacht weg datt d'Iwwersetzung onprofessionell (zimlech fräi) gemaach gouf, awer ech hoffen, datt ech déi allgemeng Bedeitung behalen hunn.
Labo Aarbecht zu dësem Thema kann hei fonnt ginn:
Aner Deeler:
Dir kënnt och mäi Kanal kucken op =)
Aféierung fir Scheduler
D'Essenz vum Problem: Wéi eng Stonneplang Politik ze entwéckelen
Wéi sollen déi ënnerierdesch Scheduler Politikkader entworf ginn? Wat sollen d'Haaptviraussetzungen sinn? Wéi eng Metriken si wichteg? Wéi eng Basis Technike goufen a fréie Rechensystemer benotzt?
Aarbechtslaascht Viraussetzungen
Ier mer iwwer méiglech Politiken diskutéieren, loosst eis fir d'éischt e puer vereinfacht Digressiounen iwwer d'Prozesser déi am System lafen, déi kollektiv genannt ginn. Aarbechtslaascht. D'Definitioun vun der Aarbechtsbelaaschtung ass e kriteschen Deel vun der Baupolitik, a wat Dir méi iwwer d'Aarbechtslaascht wësst, wat besser d'Politik Dir kënnt schreiwen.
Loosst eis déi folgend Viraussetzunge maachen iwwer d'Prozesser déi am System lafen, heiansdo och genannt Aarbechtsplaze (Aufgaben). Bal all dës Viraussetzungen sinn net realistesch, mä si néideg fir d'Entwécklung vum Gedanken.
- All Aufgab leeft fir déi selwecht Zäit,
- All Aufgabe ginn gläichzäiteg gesat,
- Déi zougewisen Aufgab funktionnéiert bis se fäerdeg ass,
- All Aufgaben benotzen nëmmen CPU,
- D'Laafzäit vun all Aufgab ass bekannt.
Scheduler Metriken
Zousätzlech zu e puer Viraussetzungen iwwer d'Laascht, ass en anert Tool fir verschidde Fuerplangpolitik ze vergläichen: Scheduler Metriken. Eng Metrik ass just eng Moossnam vun eppes. Et ginn eng Zuel vu Metriken déi kënne benotzt ginn fir Scheduler ze vergläichen.
Zum Beispill benotze mir eng Metrik genannt Ëmlafzäit (Ëmlafzäit). D'Task Ëmlafzäit ass definéiert als den Ënnerscheed tëscht der Aufgab fäerdeg Zäit an der Task Arrivée Zäit am System.
Tturnround=Tcompletion-Tarrival
Well mir ugeholl hunn datt all Aufgaben zur selwechter Zäit ukomm sinn, dann Ta=0 an domat Tt=Tc. Dëse Wäert wäert natierlech änneren wa mir déi uewe genannte Viraussetzungen änneren.
Eng aner Metrik - Fairness (Gerechtegkeet, Éierlechkeet). Produktivitéit a Gerechtegkeet sinn dacks opposéierend Charakteristiken an der Planung. Zum Beispill kann de Scheduler d'Performance optimiséieren, awer op d'Käschte fir op aner Aufgaben ze waarden, sou datt d'Gerechtegkeet reduzéiert gëtt.
FIRST IN FIRST OUT (FIFO)
Dee meescht Basis Algorithmus dee mir kënne implementéieren ass FIFO oder first come (in), first serve (out). Dësen Algorithmus huet verschidde Virdeeler: et ass ganz einfach ze implementéieren an et passt all eis Viraussetzungen an mécht d'Aarbecht ganz gutt.
Loosst eis en einfacht Beispill kucken. Loosst eis soen datt 3 Aufgaben gläichzäiteg agestallt goufen. Awer loosst eis unhuelen datt d'Aufgab A e bësse méi fréi ukomm ass wéi all déi aner, sou datt se an der Ausféierungslëscht méi fréi erscheint wéi déi aner, grad wéi B par rapport zu C. Loosst eis unhuelen datt jidderee vun hinnen fir 10 Sekonnen ausgefouert gëtt. Wat wäert d'Duerchschnëttszäit sinn fir dës Aufgaben an dësem Fall ze kompletéieren?
Andeems Dir d'Wäerter zielt - 10+20+30 an duerch 3 deelen, kréie mir déi duerchschnëttlech Programmausféierungszäit gläich wéi 20 Sekonnen.
Loosst eis elo probéieren eis Viraussetzungen z'änneren. Besonnesch Viraussetzung 1 an domat wäerte mir net méi dovun ausgoen datt all Aufgab déiselwecht Zäit brauch fir auszeféieren. Wéi wäert FIFO dës Kéier Leeschtung?
Wéi et sech erausstellt, hunn verschidden Task Ausféierungszäiten en extrem negativen Impakt op d'Produktivitéit vum FIFO Algorithmus. Loosst eis unhuelen datt d'Aufgab A 100 Sekonnen dauert fir ze kompletéieren, während B an C nach ëmmer 10 Sekonnen daueren.
Wéi aus der Figur gesi kann, wäert d'Moyenne Zäit fir de System ginn (100 + 110 + 120) / 3 = 110. Dësen Effekt gëtt genannt Konvoi Effekt, Wann e puer kuerzfristeg Konsumenten vun enger Ressource an der Schlaang no engem schwéiere Konsument. Et ass wéi d'Linn an der Epicerie wann et e Client virun Iech ass mat engem vollen Weenchen. Déi bescht Léisung fir de Problem ass ze probéieren de Keesseberäich z'änneren oder ze relaxen an déif ze otmen.
Kuerzst Job Éischt
Ass et méiglech iergendwéi eng ähnlech Situatioun mat schwéiere Prozesser ze léisen? Bestëmmt. Eng aner Aart vu Planung gëtt genanntKuerzst Job Éischt (SJF). Säin Algorithmus ass och zimmlech primitiv - wéi den Numm et scho seet, ginn déi kuerzst Aufgaben als éischt gestart, een nom aneren.
An dësem Beispill ass d'Resultat vum Laafen vun de selwechte Prozesser eng Verbesserung vun der duerchschnëttlecher Ëmlafzäit vum Programm an et wäert gläich sinn 50 statt 110, wat bal 2 mol besser ass.
Also, fir déi gegebene Viraussetzung datt all Aufgaben zur selwechter Zäit ukommen, schéngt de SJF Algorithmus den optimalsten Algorithmus ze sinn. Eis Viraussetzunge schéngen awer nach ëmmer net realistesch. Dës Kéier änneren mir d'Annam 2 an dës Kéier stellen mir Iech vir datt Aufgaben zu all Moment präsent sinn, an net all zur selwechter Zäit. Zu wat fir Problemer kann dëst féieren?
Loosst eis virstellen datt d'Aufgab A (100c) als éischt kënnt a fänkt un auszeféieren. Bei t=10 kommen d'Aufgaben B an C un, déi all 10 Sekonnen daueren. Also déi duerchschnëttlech Ausféierungszäit ass (100+(110-10)+(120-10))3 = 103. Wat kéint de Scheduler maachen fir dëst ze verbesseren?
Shortest Time-to-Completion First (STCF)
Fir d'Situatioun ze verbesseren, verloosse mir d'Annam 3 datt de Programm lancéiert ass a leeft bis fäerdeg. Zousätzlech brauche mir Hardware Ënnerstëtzung an, wéi Dir vläicht roden, wäerte mir benotzen Timer fir eng lafend Aufgab ze ënnerbriechen an Kontext wiesselen. Also kann de Scheduler eppes maachen am Moment wou d'Aufgaben B, C ukommen - stoppen d'Aufgab A auszeféieren an d'Aufgaben B an C an d'Veraarbechtung ze setzen an no hirer Fäerdegstellung weider de Prozess A auszeféieren. Sou e Scheduler gëtt genannt STCFoder Preemptive Job Éischt.
D'Resultat vun dësem Planer wäert de folgende Resultat sinn: ((120-0)+(20-10)+(30-10))/3=50. Sou gëtt esou e Scheduler nach méi optimal fir eis Aufgaben.
Metresch Äntwert Zäit
Also, wa mir d'Laafzäit vun den Aufgaben wëssen an datt dës Aufgaben nëmmen CPU benotzen, wäert STCF déi bescht Léisung sinn. An eemol an de fréien Zäiten hunn dës Algorithmen zimlech gutt geschafft. Wéi och ëmmer, de Benotzer verbréngt elo déi meescht vun hirer Zäit um Terminal an erwaart eng produktiv interaktiv Erfahrung. Sou gouf eng nei Metrik gebuer - Äntwert Zäit (Äntwert).
D'Äntwertzäit gëtt wéi follegt berechent:
Tresponse=Tfirstrun-Tarrival
Also, fir dat viregt Beispill, ass d'Äntwertzäit: A = 0, B = 0, C = 10 (abg = 3,33).
An et stellt sech eraus datt de STCF Algorithmus net sou gutt ass an enger Situatioun wou 3 Aufgaben zur selwechter Zäit ukommen - et muss waarden bis déi kleng Aufgaben komplett ofgeschloss sinn. Also den Algorithmus ass gutt fir d'Wendungszäit Metrik, awer schlecht fir d'Interaktivitéitsmetrik. Stellt Iech vir, wann Dir op engem Terminal sëtzt a probéiert Zeechen an en Editeur ze tippen a musst méi wéi 10 Sekonnen waarden, well eng aner Aufgab d'CPU ophëlt. Et ass net ganz agreabel.
Also si mir mat engem anere Problem konfrontéiert - wéi kënne mir e Scheduler bauen dee sensibel ass op d'Äntwertzäit?
Ronn Robin
En Algorithmus gouf entwéckelt fir dëse Problem ze léisen Ronn Robin (RR). D'Basis Iddi ass ganz einfach: Amplaz Aufgaben ze lafen bis se ofgeschloss sinn, lafe mir d'Aufgab fir eng gewëssen Zäit (eng Zäitschnëtt genannt) a wiesselen dann op eng aner Aufgab aus der Schlaang. Den Algorithmus widderhëlt seng Aarbecht bis all Aufgaben ofgeschloss sinn. An dësem Fall muss d'Laafzäit vum Programm e Multiple vun der Zäit sinn, no där den Timer de Prozess ënnerbrach. Zum Beispill, wann en Timer e Prozess all x = 10ms ënnerbrach, da soll d'Gréisst vun der Prozessausféierungsfenster e Multiple vun 10 sinn an 10,20 oder x*10 sinn.
Loosst eis e Beispill kucken: ABC Aufgaben kommen gläichzäiteg an de System a jidderee vun hinnen wëll 5 Sekonnen lafen. De SJF Algorithmus wäert all Aufgab fäerdeg maachen ier Dir eng aner ufänkt. Am Géigesaz, wäert de RR Algorithmus mat enger Startfenster = 1s duerch d'Aufgaben goen wéi follegt (Fig. 4.3):
(SJF Again (Schlecht fir Äntwertzäit)
(Round Robin (gutt fir Äntwertzäit)
Déi duerchschnëttlech Äntwertzäit fir den RR Algorithmus ass (0+1+2)/3=1, während fir den SJF (0+5+10)/3=5.
Et ass logesch unzehuelen datt d'Zäitfenster e ganz wichtege Parameter fir RR ass; wat méi kleng et ass, wat méi héich d'Äntwertzäit ass. Allerdéngs sollt Dir et net ze kleng maachen, well Kontextschaltzäit spillt och eng Roll an der Gesamtleeschtung. Also ass d'Wiel vun der Ausféierungsfensterzäit vum OS Architekt festgeluegt an hänkt vun den Aufgaben of, déi geplangt sinn an der auszeféieren. Wiesselkontext ass net déi eenzeg Serviceoperatioun déi Zäit verschwendt - de lafende Programm funktionnéiert op vill aner Saachen, zum Beispill verschidde Cache, a mat all Schalter ass et néideg dëst Ëmfeld ze späicheren an ze restauréieren, wat och vill vun Zäit.
RR ass e super Scheduler wa mir nëmmen iwwer d'Äntwertzäit Metrik schwätzen. Awer wéi wäert d'Task Wendungszäit Metrik mat dësem Algorithmus behuelen? Bedenkt d'Beispill hei uewen, wann d'Betribszäit vun A, B, C = 5s a gläichzäiteg ukommen. Aufgab A wäert um 13 ophalen, B um 14, C um 15s an déi duerchschnëttlech Wendungszäit wäert 14s sinn. Also ass RR de schlëmmsten Algorithmus fir den Ëmsaz Metrik.
A méi allgemeng Begrëffer ass all RR-Typ Algorithmus fair; et trennt d'CPU Zäit gläich tëscht all Prozesser. An dofir sinn dës Metriken dauernd matenee konflikt.
Also hu mir e puer kontrastéierend Algorithmen a gläichzäiteg sinn et nach ëmmer verschidde Viraussetzungen - datt d'Taskzäit bekannt ass an datt d'Aufgab nëmmen d'CPU benotzt.
Vermëschung mat I/O
Als éischt, loosst eis d'Annam 4 ewechhuelen datt de Prozess nëmmen d'CPU benotzt; natierlech ass dëst net de Fall a Prozesser kënnen Zougang zu aner Ausrüstung kréien.
De Moment wou e Prozess eng I/O-Operatioun freet, geet de Prozess an de blockéierte Staat a waart bis den I/O fäerdeg ass. Wann I/O op d'Festplack geschéckt gëtt, da kann esou eng Operatioun bis zu e puer MS oder méi laang daueren, an de Prozessor wäert zu dësem Moment Idle sinn. Wärend dëser Zäit kann de Scheduler de Prozessor mat all anere Prozess besetzen. Déi nächst Entscheedung déi de Scheduler muss huelen ass wann de Prozess säin I/O fäerdeg mécht. Wann dat passéiert, geschitt en Ënnerbriechung an d'OS wäert de Prozess deen den I / O genannt huet an de prett Zoustand setzen.
Loosst eis e Beispill vu verschiddene Probleemer kucken. Jiddereng vun hinnen erfuerdert 50ms CPU Zäit. Wéi och ëmmer, deen éischten Zougang zu I/O all 10ms (wat och all 10ms ausgefouert gëtt). A Prozess B benotzt einfach en 50ms Prozessor ouni I / O.
An dësem Beispill wäerte mir de STCF Scheduler benotzen. Wéi wäert de Scheduler behuelen wann e Prozess wéi A drop lancéiert gëtt? Hie wäert déi folgend maachen: éischt wäert hien de Prozess A komplett ausschaffen, an dann Prozess B.
Déi traditionell Approche fir dëse Problem ze léisen ass all 10 ms Ënnertask vum Prozess A als eng separat Aufgab ze behandelen. Also, wann Dir mam STJF Algorithmus ufänkt, ass d'Wiel tëscht enger 50 ms Aufgab an enger 10 ms Aufgab offensichtlech. Dann, wann d'Subtask A fäerdeg ass, gëtt de Prozess B an I/O gestart. Nodeems den I/O fäerdeg ass, ass et üblech fir den 10ms Prozess A erëm ze starten anstatt Prozess B. Op dës Manéier ass et méiglech Iwwerlappung ëmzesetzen, wou d'CPU vun engem anere Prozess benotzt gëtt, während deen éischten op d'Waart op de I/O. An als Resultat gëtt de System besser genotzt - am Moment wou interaktiv Prozesser op I/O waarden, kënnen aner Prozesser um Prozessor ausgefouert ginn.
Den Oracle ass net méi
Loosst eis elo probéieren d'Annahme lass ze ginn datt d'Laafzäit vun der Aufgab bekannt ass. Dëst ass allgemeng déi schlëmmst an onrealistesch Viraussetzung op der ganzer Lëscht. Tatsächlech, am duerchschnëttleche normale OS, weess d'OS selwer normalerweis ganz wéineg iwwer d'Ausféierungszäit vun Aufgaben, also wéi kënnt Dir e Scheduler bauen ouni ze wëssen wéi laang d'Aufgab dauert fir auszeféieren? Vläicht kënne mir e puer RR Prinzipien benotze fir dëse Problem ze léisen?
D 'Resultat
Mir hunn d'Basis Iddie vum Aufgabeplang gekuckt a gekuckt 2 Famille vu Scheduler. Déi éischt fänkt déi kürzest Aufgab als éischt un an erhéicht domat d'Dauerzäit, während deen zweeten tëscht all Aufgaben gläich zerrass gëtt, wat d'Äntwertzäit erhéicht. Béid Algorithmen si schlecht wou Algorithmen vun der anerer Famill gutt sinn. Mir hunn och gekuckt wéi d'parallel Notzung vun der CPU an ech / O kann d'Performance verbesseren, awer huet de Problem mat OS Clairvoyance net léisen. An an der nächster Lektioun wäerte mir e Planer kucken, deen an déi direkt Vergaangenheet kuckt a probéiert d'Zukunft virauszesoen. An et gëtt Multi-Level Feedback Queue genannt.
Source: will.com