Inleiding tot bedryfstelsels
Haai Habr! Ek wil graag 'n reeks artikels-vertalings van een interessante literatuur na my mening onder u aandag bring - OSTEP. Hierdie materiaal bespreek redelik diep die werk van unix-agtige bedryfstelsels, naamlik werk met prosesse, verskeie skeduleers, geheue en ander soortgelyke komponente waaruit 'n moderne bedryfstelsel bestaan. Jy kan die oorspronklike van alle materiaal hier sien . Neem asseblief kennis dat die vertaling onprofessioneel (heel vrylik) gemaak is, maar ek hoop ek het die algemene betekenis behou.
Laboratoriumwerk oor hierdie onderwerp kan hier gevind word:
Ander dele:
Jy kan ook na my kanaal kyk by =)
Inleiding tot skeduleerder
Die kern van die probleem: Hoe om 'n skeduleerderbeleid te ontwikkel
Hoe moet die onderliggende skeduleerderbeleidsraamwerke ontwerp word? Wat moet die sleutelaannames wees? Watter maatstawwe is belangrik? Watter basiese tegnieke is in vroeë rekenaarstelsels gebruik?
Werkslading Aannames
Voordat ons moontlike beleide bespreek, kom ons maak eers 'n paar vereenvoudigende afwykings oor die prosesse wat in die stelsel loop, wat gesamentlik genoem word werklading. Om die werklading te definieer is 'n kritieke deel van die bou van beleide, en hoe meer jy van die werklading weet, hoe beter is die beleid wat jy kan skryf.
Kom ons maak die volgende aannames oor die prosesse wat in die stelsel loop, soms ook genoem werksgeleenthede (take). Byna al hierdie aannames is nie realisties nie, maar is nodig vir die ontwikkeling van denke.
- Elke taak loop vir dieselfde hoeveelheid tyd,
- Alle take word gelyktydig opgestel,
- Die opgedra taak werk totdat dit voltooi is,
- Alle take gebruik slegs SVE,
- Die looptyd van elke taak is bekend.
Skeduleerder statistieke
Benewens 'n paar aannames oor die las, is 'n ander hulpmiddel nodig om verskillende skeduleringsbeleide te vergelyk: skeduleerder-metrieke. 'n Metriek is net 'n mate van iets. Daar is 'n aantal maatstawwe wat gebruik kan word om skeduleers te vergelyk.
Byvoorbeeld, ons sal 'n metriek gebruik genaamd omkeertyd (omkeertyd). Die taakomkeertyd word gedefinieer as die verskil tussen die taakvoltooiingstyd en die taakaankomstyd in die stelsel.
Tturnaround=Tvoltooiing-Aankoms
Aangesien ons aangeneem het dat alle take op dieselfde tyd aangekom het, dan is Ta=0 en dus Tt=Tc. Hierdie waarde sal natuurlik verander wanneer ons die bogenoemde aannames verander.
Nog 'n maatstaf - regverdigheid (regverdigheid, eerlikheid). Produktiwiteit en regverdigheid is dikwels opponerende kenmerke in beplanning. Die skeduleerder kan byvoorbeeld prestasie optimeer, maar ten koste van wag vir ander take om uit te voer, en sodoende regverdigheid verminder.
EERSTE IN EERSTE UIT (EIEU)
Die mees basiese algoritme wat ons kan implementeer, word EIEU of genoem eerste kom (in), eerste bedien (uit). Hierdie algoritme het verskeie voordele: dit is baie maklik om te implementeer en dit pas by al ons aannames en doen die werk redelik goed.
Kom ons kyk na 'n eenvoudige voorbeeld. Kom ons sê 3 take is gelyktydig opgestel. Maar kom ons neem aan dat taak A 'n bietjie vroeër as al die ander aangekom het, so dit sal vroeër in die uitvoeringslys verskyn as die ander, net soos B relatief tot C. Kom ons neem aan dat elkeen van hulle vir 10 sekondes uitgevoer sal word. Wat sal die gemiddelde tyd wees om hierdie take in hierdie geval te voltooi?
Deur die waardes te tel - 10+20+30 en deur 3 te deel, kry ons die gemiddelde programuitvoertyd gelyk aan 20 sekondes.
Kom ons probeer nou ons aannames verander. In die besonder, aanname 1 en dus sal ons nie meer aanvaar dat elke taak dieselfde tyd neem om uit te voer nie. Hoe gaan EIEU hierdie keer presteer?
Soos dit blyk, het verskillende taakuitvoertye 'n uiters negatiewe impak op die produktiwiteit van die EIEU-algoritme. Kom ons neem aan dat taak A 100 sekondes sal neem om te voltooi, terwyl B en C steeds 10 sekondes elk sal neem.
Soos uit die figuur gesien kan word, sal die gemiddelde tyd vir die stelsel (100+110+120)/3=110 wees. Hierdie effek word genoem konvooi effek, wanneer sommige korttermynverbruikers van 'n hulpbron sal toustaan na 'n swaar verbruiker. Dit is soos die ry by die kruidenierswinkel wanneer daar 'n klant voor jou is met 'n vol wa. Die beste oplossing vir die probleem is om die kasregister te probeer verander of te ontspan en diep asem te haal.
Kortste Job Eerste
Is dit moontlik om 'n soortgelyke situasie met swaargewigprosesse op te los? Sekerlik. 'n Ander tipe beplanning word genoemKortste Job Eerste (SJF). Die algoritme daarvan is ook redelik primitief - soos die naam aandui, sal die kortste take eers, een na die ander, van stapel gestuur word.
In hierdie voorbeeld sal die resultaat van die uitvoer van dieselfde prosesse 'n verbetering in die gemiddelde programomkeertyd wees en dit sal gelyk wees aan 50 in plaas van 110, wat amper 2 keer beter is.
Dus, vir die gegewe aanname dat alle take op dieselfde tyd aankom, blyk die SJF-algoritme die mees optimale algoritme te wees. Ons aannames lyk egter steeds nie realisties nie. Hierdie keer verander ons aanname 2 en stel ons hierdie keer voor dat take enige tyd teenwoordig kan wees, en nie almal op dieselfde tyd nie. Tot watter probleme kan dit lei?
Kom ons stel ons voor dat taak A (100c) eerste aankom en begin uitgevoer word. By t=10 kom take B en C aan, wat elk 10 sekondes sal neem. Die gemiddelde uitvoeringstyd is dus (100+(110-10)+(120-10))3 = 103. Wat kan die skeduleerder doen om dit te verbeter?
Kortste tyd-tot-voltooiing eerste (STCF)
Om die situasie te verbeter, laat ons aanname 3 weg dat die program geloods is en loop totdat dit voltooi is. Daarbenewens sal ons hardeware-ondersteuning nodig hê en, soos jy dalk raai, sal ons gebruik timer om 'n lopende taak te onderbreek en kontekswisseling. Die skeduleerder kan dus iets doen op die oomblik dat take B, C aankom - ophou om taak A uit te voer en take B en C in verwerking plaas en, na voltooiing daarvan, voortgaan om proses A uit te voer. So 'n skeduleerder word genoem STCFof Voorkomende werk eerste.
Die resultaat van hierdie beplanner sal die volgende resultaat wees: ((120-0)+(20-10)+(30-10))/3=50. So 'n skeduleerder word dus selfs meer optimaal vir ons take.
Metrieke reaksietyd
Dus, as ons weet wat die looptyd van die take is en dat hierdie take slegs SVE gebruik, sal STCF die beste oplossing wees. En een keer in die vroeë tye het hierdie algoritmes redelik goed gewerk. Die gebruiker spandeer egter nou die meeste van haar tyd by die terminale en verwag 'n produktiewe interaktiewe ervaring. So is 'n nuwe maatstaf gebore - reaksie tyd (reaksie).
Die reaksietyd word soos volg bereken:
Tresponse=Tfirstrun−Aankoms
Dus, vir die vorige voorbeeld, sal die reaksietyd wees: A=0, B=0, C=10 (abg=3,33).
En dit blyk dat die STCF-algoritme nie so goed is in 'n situasie waar 3 take op dieselfde tyd aankom nie - dit sal moet wag totdat die klein take heeltemal afgehandel is. Die algoritme is dus goed vir die omkeertyd-metriek, maar sleg vir die interaktiwiteit-metriek. Stel jou voor dat jy by 'n terminale sit en probeer om karakters in 'n redigeerder te tik en meer as 10 sekondes moet wag omdat 'n ander taak die SVE opneem. Dis nie baie lekker nie.
Ons word dus met 'n ander probleem gekonfronteer - hoe kan ons 'n skeduleerder bou wat sensitief is vir reaksietyd?
Rondomtalie
'n Algoritme is ontwikkel om hierdie probleem op te los Rondomtalie (RR). Die basiese idee is redelik eenvoudig: in plaas daarvan om take uit te voer totdat hulle voltooi is, sal ons die taak vir 'n sekere tydperk uitvoer (genoem 'n tydsny) en dan oorskakel na 'n ander taak uit die tou. Die algoritme herhaal sy werk totdat alle take voltooi is. In hierdie geval moet die looptyd van die program 'n veelvoud wees van die tyd waarna die timer die proses sal onderbreek. Byvoorbeeld, as 'n timer 'n proses elke x=10ms onderbreek, moet die grootte van die prosesuitvoeringsvenster 'n veelvoud van 10 wees en 10,20 of x*10 wees.
Kom ons kyk na 'n voorbeeld: ABC-take kom gelyktydig in die stelsel aan en elkeen van hulle wil vir 5 sekondes loop. Die SJF-algoritme sal elke taak voltooi voordat 'n ander begin. In teenstelling hiermee sal die RR-algoritme met 'n bekendstellingsvenster = 1s deur die take soos volg gaan (Fig. 4.3):
(SJF Weereens (sleg vir reaksietyd)
(Round Robin (Goed vir reaksietyd)
Die gemiddelde reaksietyd vir die RR-algoritme is (0+1+2)/3=1, terwyl vir die SJF (0+5+10)/3=5.
Dit is logies om te aanvaar dat die tydvenster 'n baie belangrike parameter vir RR is; hoe kleiner dit is, hoe hoër is die reaksietyd. Jy moet dit egter nie te klein maak nie, aangesien kontekswisseltyd ook 'n rol sal speel in algehele prestasie. Die keuse van uitvoeringsvenstertyd word dus deur die OS-argitek gestel en hang af van die take wat beplan word om daarin uitgevoer te word. Skakelkonteks is nie die enigste diensoperasie wat tyd mors nie - die lopende program werk op baie ander dinge, byvoorbeeld verskeie kas, en met elke skakelaar is dit nodig om hierdie omgewing te stoor en te herstel, wat ook baie van tyd.
RR is 'n goeie skeduleerder as ons net oor die reaksietyd-metriek praat. Maar hoe sal die taakomdraaityd-metriek met hierdie algoritme optree? Beskou die voorbeeld hierbo, wanneer die bedryfstyd van A, B, C = 5s en op dieselfde tyd aankom. Taak A sal eindig op 13, B op 14, C op 15s en die gemiddelde omkeertyd sal 14s wees. Dus, RR is die swakste algoritme vir die omsetmetriek.
In meer algemene terme is enige RR-tipe algoritme billik; dit verdeel die SVE tyd gelykop tussen alle prosesse. En dus bots hierdie maatstawwe voortdurend met mekaar.
Ons het dus verskeie kontrasterende algoritmes en terselfdertyd is daar nog verskeie aannames oor – dat die taaktyd bekend is en dat die taak slegs die SVE gebruik.
Meng met I/O
Eerstens, laat ons aanname 4 verwyder dat die proses slegs die SVE gebruik; dit is natuurlik nie die geval nie en prosesse kan toegang tot ander toerusting kry.
Die oomblik wanneer enige proses 'n I/O-operasie versoek, gaan die proses in die geblokkeerde toestand in en wag vir die I/O om te voltooi. As I/O na die hardeskyf gestuur word, kan so 'n bewerking tot 'n paar ms of langer neem, en die verwerker sal op hierdie oomblik ledig wees. Gedurende hierdie tyd kan die skeduleerder die verwerker met enige ander proses beset. Die volgende besluit wat die skeduleerder sal moet neem, is wanneer die proses sy I/O sal voltooi. Wanneer dit gebeur, sal 'n onderbreking plaasvind en die bedryfstelsel sal die proses wat die I/O geroep het in die gereed toestand plaas.
Kom ons kyk na 'n voorbeeld van verskeie probleme. Elkeen van hulle benodig 50ms se SVE-tyd. Die eerste een sal egter elke 10 ms toegang tot I/O kry (wat ook elke 10 ms uitgevoer sal word). En proses B gebruik eenvoudig 'n 50ms verwerker sonder I/O.
In hierdie voorbeeld sal ons die STCF skeduleerder gebruik. Hoe sal die skeduleerder optree as 'n proses soos A daarop geloods word? Hy sal die volgende doen: eers sal hy proses A heeltemal uitwerk, en dan proses B.
Die tradisionele benadering om hierdie probleem op te los is om elke 10 ms-subtaak van proses A as 'n aparte taak te hanteer. Wanneer dus met die STJF-algoritme begin word, is die keuse tussen 'n 50 ms-taak en 'n 10 ms-taak voor die hand liggend. Dan, wanneer subtaak A voltooi is, sal proses B en I/O van stapel gestuur word. Nadat die I/O voltooi is, sal dit gebruiklik wees om die 10ms proses A weer te begin in plaas van proses B. Op hierdie manier is dit moontlik om oorvleueling te implementeer, waar die SVE deur 'n ander proses gebruik word terwyl die eerste een wag vir die I/O. En gevolglik word die stelsel beter benut – op die oomblik wanneer interaktiewe prosesse op I/O wag, kan ander prosesse op die verwerker uitgevoer word.
Die Oracle is nie meer nie
Kom ons probeer nou ontslae raak van die aanname dat die looptyd van die taak bekend is. Dit is oor die algemeen die ergste en mees onrealistiese aanname op die hele lys. Trouens, in die gemiddelde gewone bedryfstelsel weet die bedryfstelsel self gewoonlik baie min van die uitvoeringstyd van take, so hoe kan jy dan 'n skeduleerder bou sonder om te weet hoe lank die taak sal neem om uit te voer? Miskien kan ons 'n paar RR-beginsels gebruik om hierdie probleem op te los?
Totale
Ons het na die basiese idees van taakskedulering gekyk en na 2 families van skeduleerders gekyk. Die eerste een begin die kortste taak eerste en verhoog dus die omkeertyd, terwyl die tweede een eweredig tussen alle take geskeur word, wat die reaksietyd verhoog. Albei algoritmes is sleg waar algoritmes van die ander familie goed is. Ons het ook gekyk na hoe parallelle gebruik van SVE en I/O werkverrigting kan verbeter, maar het nie die probleem met OS heldersiendheid opgelos nie. En in die volgende les sal ons kyk na 'n beplanner wat na die onmiddellike verlede kyk en probeer om die toekoms te voorspel. En dit word multi-vlak terugvoer tou genoem.
Bron: will.com