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 =)
Planung: Multi-Level Feedback Queue
An dësem Virtrag wäerte mir iwwer d'Problemer vun der Entwécklung vun enger vun de bekanntste Approche schwätzen
Planung, déi genannt gëtt Multi-Level Feedback Queue (MLFQ). De MLFQ Scheduler gouf fir d'éischt am Joer 1962 vum Fernando J. Corbató an engem System genannt
Kompatibel Time-Sharing System (CTSS). Dës Wierker (inklusiv spéider Aarbecht op
Multics) goufen duerno fir den Turing Award nominéiert. De Planer war
duerno verbessert an d'Erscheinung kritt, déi scho ka fonnt ginn
puer modern Systemer.
De MLFQ Algorithmus probéiert 2 fundamental iwwerlappende Probleemer ze léisen.
Éischtens, et probéiert d'Dauerzäit ze optimiséieren, déi, wéi mir an der viregter Virliesung diskutéiert hunn, duerch d'Method optimiséiert gëtt fir am Ufank vun der Schlaang am meeschten unzefänken
kuerz Aufgaben. Wéi och ëmmer, d'OS weess net wéi laang e bestëmmte Prozess leeft, an dëst
néideg Wëssen fir d'Operatioun vun der SJF, STCF Algorithmen. Zweet, MLFQ probéiert
maachen de System reaktiounsfäeger fir Benotzer (zum Beispill, fir déi, déi sëtzen an
stare op den Ecran op d'Aufgab ze waarden bis fäerdeg) an domat Zäit minimiséieren
Äntwert. Leider verbesseren Algorithmen wéi RR d'Äntwertzäit, awer extrem
hunn e schlechten Impakt op d'Dauerzäit Metrik. Dofir eise Problem: Wéi designen
e Scheduler deen eis Ufuerderungen entsprécht ouni eppes iwwer ze wëssen
d'Natur vum Prozess am Allgemengen? Wéi kann de Scheduler d'Charakteristike vun Aufgaben léieren,
déi et lancéiert an domat besser plangen Décisiounen huelen?
D'Essenz vum Problem: Wéi de Kader vun Aufgaben ouni perfekt Wëssen ze plangen?
Wéi designt een e Scheduler deen gläichzäiteg d'Äntwertzäit miniméiert
fir interaktiv Aufgaben a gläichzäiteg miniméiert Wendungszäit ouni ze wëssen
Wëssen vun Aufgab Ausféierung Zäit?
Bemierkung: mir léiere vu fréieren Eventer
D'MLFQ Schlaang ass en exzellent Beispill vun engem System dee léiert
Vergaangenheet Evenementer fir d'Zukunft virauszesoen. Ähnlech Approche sinn dacks
am OS fonnt (A vill aner Filialen vun der Informatik, dorënner Filialen
Hardware Prognosen an Caching Algorithmen). Ähnlech Reesen
ginn ausgeléist wann Aufgaben Verhalensphasen hunn an domat prévisibel sinn.
Wéi och ëmmer, Dir sollt virsiichteg sinn mat dëser Technik well Prognosen ganz einfach sinn
kann sech als falsch erausstellen a féieren de System méi schlecht Entscheedungen ze treffen wéi
wier iwwerhaapt ouni Wëssen.
MLFQ: Grondregelen
Loosst eis d'Basisregele vum MLFQ Algorithmus kucken. An obwuel Implementatioune vun dësem Algorithmus
Et gi verschidde, d'Basis Approche sinn ähnlech.
An der Ëmsetzung, déi mir kucken, wäert MLFQ e puer hunn
getrennt Schlaangen, all vun deenen wäert eng aner Prioritéit hunn. egal wéini,
eng Aufgab prett fir Ausféierung ass an enger Schlaang. MLFQ benotzt Prioritéite,
fir ze entscheeden wéi eng Aufgab fir d'Ausféierung ze lafen, d.h. Aufgab mat héijer
Prioritéit (Aufgab aus der Schlaang mat der héchster Prioritéit) gëtt als éischt lancéiert
Schlaang.
Natierlech kann et méi wéi eng Aufgab an enger bestëmmter Schlaang sinn, also
sou wäerten se déi selwecht Prioritéit hunn. An dësem Fall gëtt de Mechanismus benotzt
RR fir eng Course ënnert dësen Aufgaben ze Zäitplang.
Also komme mir zu zwee Grondregele fir MLFQ:
- Regel 1: Wann Prioritéit (A) > Prioritéit (B), Aufgab A gëtt gestart (B net)
- Regel 2: Wann Prioritéit (A) = Prioritéit (B), ginn A&B mat RR gestart
Baséiert op der uewen, de Schlëssel Elementer MLFQ Planung
Prioritéite sinn. Amplaz jidderengem eng fix Prioritéit ze ginn
Aufgab, MLFQ ännert seng Prioritéit jee no der observéierter Verhalen.
Zum Beispill, wann eng Aufgab dauernd Aarbecht op d'CPU werft wärend op Tastaturinput waart,
MLFQ wäert Prozess Prioritéit héich halen well dat ass wéi
en interaktive Prozess soll funktionnéieren. Wann, am Géigendeel, d'Aufgab ass permanent an
benotzt CPU schwéier iwwer eng laang Period, MLFQ wäert et senken
eng Prioritéit. Also wäert MLFQ d'Behuele vu Prozesser studéieren wärend se lafen
a benotzen Verhalen.
Loosst eis e Beispill zéien wéi d'Schlaangen iergendwann ausgesinn
Zäit an da kritt Dir eppes wéi dat:
An dësem Schema sinn 2 Prozesser A a B an der héchster Prioritéit Schlaang. Prozess
C ass iergendwou an der Mëtt, a Prozess D ass ganz um Enn vun der Schlaang. Laut der uewen
Geméiss den Beschreiwunge vum MLFQ Algorithmus wäert de Scheduler Aufgaben nëmme mat dem héchsten ausféieren.
Prioritéit no RR, an Aufgaben C, D wäert ouni Aarbecht.
Natierlech gëtt e statesche Snapshot net e komplett Bild vu wéi MLFQ funktionnéiert.
Et ass wichteg genee ze verstoen wéi d'Bild mat der Zäit ännert.
Versuch 1: Wéi Prioritéit änneren
Zu dësem Zäitpunkt musst Dir entscheeden wéi MLFQ de Prioritéitsniveau änneren
Aufgaben (an domat d'Positioun vun der Aufgab an der Schlaang) wéi se duerch säi Liewenszyklus viru geet. Fir
dëst ass néideg fir de Workflow am Kapp ze halen: e gewësse Betrag
interaktiv Aufgaben mat kuerzen Runtimes (an domat dacks Verëffentlechung
CPU) a verschidde laangfristeg Aufgaben, déi d'CPU all hir Aarbechtszäit benotzen, während
D'Äntwertzäit ass net wichteg fir sou Aufgaben. An esou kënnt Dir Ären éischte Versuch maachen
implementéiert den MLFQ Algorithmus mat de folgende Reegele:
- Regel 3: Wann eng Aufgab an de System erakënnt, gëtt se an der Schlaang mat der héchster gesat
- Prioritéit.
- Rule4a: Wann eng Aufgab déi ganz Zäitfenster benotzt, déi derzou zougewisen ass, dann ass et
- Prioritéit reduzéiert.
- Regel 4b: Wann eng Task d'CPU verëffentlecht ier seng Zäitfenster ofleeft, dann ass et
- bleift mat der selwechter Prioritéit.
Beispill 1: Single laang Lafen Aufgab
Wéi an dësem Beispill gesi ka ginn, ass d'Entrée Aufgab mat der héchster gesat
Prioritéit. No enger Zäitfenster vun 10ms gëtt de Prozess an der Prioritéit ofgeschnidden
Planer. No der nächster Zäitfenster gëtt d'Aufgab endlech ofgeschnidden
niddregsten Prioritéit am System, wou et bleift.
Beispill 2: Eng kuerz Aufgab geliwwert
Loosst eis elo e Beispill kucken wéi MLFQ probéiert SJF ze Approche. An deem
Beispill, zwou Aufgaben: A, déi eng laang Lafen Aufgab permanent ass
besat CPU an B, déi eng kuerz interaktiv Aufgab ass. Ugeholl
datt den A schonn eng Zäit laang geschafft huet wéi d'Aufgab B ukomm ass.
Dës Grafik weist d'Resultater vum Szenario. Aufgab A, wéi all Aufgab,
CPU Notzung war ganz ënnen. Aufgab B wäert zu Zäit T = 100 ukommen a wäert
an der héchster Prioritéit Schlaang gesat. Well seng Operatiounszäit kuerz ass, dann
et wäert fäerdeg sinn ier Dir déi lescht Schlaang erreecht.
Aus dësem Beispill soll d'Haaptziel vum Algorithmus verstane ginn: well den Algorithmus net
weess, ob eng Aufgab laang oder kuerz ass, da geet e fir d'éischt dovun aus, datt d'Aufgab
kuerz a gëtt et déi héchste Prioritéit. Wann dëst eng wierklech kuerz Aufgab ass, dann
et wäert séier ofgeschloss ginn, soss wann et eng laang Aufgab ass, wäert et lues bewegen
Prioritéit erof a wäert geschwënn beweisen, datt si wierklech eng laang Aufgab ass, datt net
verlaangt eng Äntwert.
Beispill 3: Wat iwwer I/O?
Loosst eis elo en I/O Beispill kucken. Wéi an der Regel 4b,
wann e Prozess de Prozessor fräigelooss ouni all seng Prozessorzäit ze benotzen,
da bleift et um selwechte Prioritéitsniveau. D'Intent vun dëser Regel ass ganz einfach
- wann der interaktiv Aarbecht mécht vill ech / O Operatiounen, Zum Beispill, waarden
vum Benotzerschlëssel oder Mauspressen, esou eng Aufgab wäert de Prozessor befreien
virun der zougewisen Fënster. Mir wëllen d'Prioritéit vun esou enger Aufgab net erofsetzen,
an domat bleift et um selwechten Niveau.
Dëst Beispill weist wéi den Algorithmus mat sou Prozesser funktionnéiert - interaktiv Job B, déi nëmmen CPU fir 1ms brauch virun der Ausféierung
ech / O Prozess a laang Lafen Job A, déi verbréngt all seng Zäit mat der CPU.
MLFQ hält Prozess B op héchster Prioritéit well et weider
Fräisetzung der CPU. Wann B eng interaktiv Aufgab ass, dann huet den Algorithmus erreecht
Äert Zil ass interaktiv Aufgaben séier ze lafen.
Problemer mat der aktueller MLFQ Algorithmus
An de fréiere Beispiller hu mir eng Basisversioun vum MLFQ gebaut. An et schéngt, datt hien
mécht seng Aarbecht gutt an éierlech, Verdeelt CPU Zäit zimlech tëscht
laang Aufgaben an erlaabt kuerz oder héich-Volumen Aufgaben
Aarbecht op I / O séier. Leider enthält dës Approche e puer
sérieux Problemer.
Éischtens, de Problem vun Honger: wann de System huet vill interaktiv
Aufgaben, da verbrauchen se all Prozessor Zäit an domat net eng eenzeg fir eng laang Zäit
d'Aufgab kann net ausgefouert ginn (si hongereg).
Zweet, Smart Benotzer kéinten hir Programmer schreiwen sou datt
Narr de Scheduler. Täuschung läit an eppes ze zwéngen
De Scheduler gëtt de Prozess méi CPU Zäit. Algorithmus datt
uewen beschriwwen ass zimlech vulnérabel fir ähnlech Attacken: virun der Zäitfenster ass praktesch
ofgeschloss, musst Dir eng I/O Operatioun maachen (fir e puer, egal wéi eng Datei)
an domat der CPU fräi. Esou Verhalen wäert erlaben Iech am selwechten ze bleiwen
der Schlaang selwer an erëm eng gréissere Prozentsaz vun CPU Zäit kréien. Wann Dir maacht
dëst ass richteg (zum Beispill, 99% vun der Fënsterzäit ausféieren ier Dir d'CPU verëffentlecht),
esou eng Aufgab kann de Prozessor einfach monopoliséieren.
Schlussendlech kann e Programm säi Verhalen iwwer Zäit änneren. Déi Aufgaben
déi benotzt der CPU kann interaktiv ginn. An eisem Beispill, ähnlech
Aufgaben kréien net d'Behandlung déi se vum Scheduler verdéngen wéi anerer
(initial) interaktiv Aufgaben.
Fro fir d'Publikum: wéi eng Attacken op de Scheduler kënnen an der moderner Welt duerchgefouert ginn?
Versuch 2: Erhéijung Prioritéit
Loosst eis probéieren d'Regelen z'änneren a kucken ob mir Problemer kënne vermeiden mat
fasten. Wat kënne mir maachen, datt am Zesummenhang
CPU Aufgaben kréien hir Zäit (och wann net laang).
Als einfach Léisung fir de Problem kënnt Dir periodesch proposéieren
d'Prioritéit vun all esou Aufgaben am System erhéijen. Et gi vill Weeër
Fir dëst z'erreechen, loosst eis probéieren eppes einfach als Beispill ëmzesetzen: iwwersetzen
all Aufgaben kréien direkt déi héchst Prioritéit, dofir déi nei Regel:
- Regel5: No enger bestëmmter Period S, plënneren all Aufgaben am System op déi héchste Schlaang.
Eis nei Regel léist zwee Problemer gläichzäiteg. Éischtens, d'Prozesser
sinn garantéiert net hongereg: Aufgaben, déi an der héchster Prioritéit sinn, ginn opgedeelt
CPU Zäit no dem RR Algorithmus an domat all Prozesser kréien
CPU Zäit. Zweetens, wann e puer Prozess, datt virdrun benotzt
nëmmen de Prozessor gëtt interaktiv, et bleift an der Schlaang mat der héchster
Prioritéit nodeems se eng eemoleg Erhéijung vun der Prioritéit op den héchste krut.
Loosst eis e Beispill kucken. An dësem Szenario betruecht ee Prozess benotzt
CPU an zwee interaktiv, kuerz Prozesser. Op der lénker Säit an der Figur weist d'Figur d'Verhalen ouni Prioritéit Promotioun, an domat fänkt d'laang lafend Aufgab ze hongereg no zwou interaktiv Aufgaben am System ukommen. An der Figur op der rietser Säit gëtt eng Prioritéit Erhéijung all 50ms duerchgefouert an domat all Prozesser sinn garantéiert CPU Zäit ze kréien a wäert periodesch lancéiert ginn. 50ms an dësem Fall gëtt als Beispill geholl; a Wierklechkeet ass dës Zuel liicht méi héich.
Selbstverständlech, addéiere vun der periodesch Erhéijung Zäit S féiert zu
eng logesch Fro: wat Wäert soll gesat ginn? Ee vun de geéiert
Systemingenieuren John Ousterhout genannt esou Quantitéiten a Systemer wéi Voo-doo
konstante, well se op eng Manéier schwaarz Magie fir korrekt verlaangt
ausstellen. An, leider, S huet esou en Doft. Wann Dir och de Wäert setzt
grouss - laang Aufgaben fänken un hongereg. A wann Dir de Wäert ze niddreg setzt,
Interaktiv Aufgaben kréien net déi richteg CPU Zäit.
Versuch 3: Besser Comptabilitéit
Elo hu mir en anere Problem ze léisen: wéi net
erlaben eise Scheduler ze narren? D'Leit fir dës Méiglechkeet ze schëlleg sinn
Regelen 4a, 4b, déi erlaben eng Aarbecht Prioritéit ze halen, befreit de Prozessor
ier déi zougewisen Zäit ofleeft. Wéi mat dësem ëmzegoen?
D'Léisung an dësem Fall kann als besser Comptabilitéit vun CPU Zäit op all considéréiert ginn
MLFQ Niveau. Amplaz vun der Zäit ze vergiessen de Programm benotzt
Prozessor fir déi zougewisen Period, sollt et berücksichtegt a gespäichert ginn. Nach
de Prozess huet seng zougewisen Zäit verbraucht, et soll op déi nächst degradéiert ginn
Prioritéit Niveau. Elo ass et egal wéi de Prozess seng Zäit benotzt - wéi
stänneg Rechenzäit um Prozessor oder als Zuel vun Appellen. Also,
Regel 4 soll op déi folgend Form ëmgeschriwwe ginn:
- Regel4: Nodeems eng Aufgab seng zougewisen Zäit an der aktueller Schlaang benotzt huet (egal wéi oft se d'CPU befreit huet), gëtt d'Prioritéit vun där Aufgab erofgesat (et beweegt sech an d'Schlaang erof).
Loosst eis e Beispill kucken:
»
D'Figur weist wat geschitt wann Dir probéiert de Scheduler ze narren, wéi
wann et mat de fréiere Regelen 4a wier, 4b d'Resultat op der lénker Säit kritt. Glécklech nei
d'Regel ass d'Resultat op der rietser. Virum Schutz, all Prozess kéint I / O virum Réalisatioun ruffen an
dominéiert also d'CPU, nodeems de Schutz aktivéiert ass, onofhängeg vum Verhalen
I / O, hien wäert nach erof an der Schlaang plënneren an domat wäert net fäheg sinn onéierlech
iwwerhuelen CPU Ressourcen.
Verbesserung vun MLFQ an aner Problemer
Mat den uewe Verbesserunge kommen nei Problemer: ee vun den Haapt
Froen - wéi Parameteren esou Scheduler? Déi. Wéi vill soll et sinn
Schlaangen? Wat soll d'Gréisst vun der Programmfenster an der Schlaang sinn? Wéi
Programm Prioritéit soll dacks erhéicht ginn Honger ze vermeiden an
d'Verännerung vum Programmverhalen berücksichtegen? Et gëtt keng einfach Äntwert op dës Froen
Äntwert an nëmmen Experimenter mat Luede a spéider Konfiguratioun
Planner kann zu puer zefriddestellend Gläichgewiicht Féierung.
Zum Beispill, déi meescht MLFQ Implementatiounen erlaben Iech verschidden ze zouzeschreiwen
Zäitintervaller fir verschidde Schlaangen. Héich Prioritéit Schlaangen normalerweis
kuerz Intervalle sinn verschriwwen. Dës Schlaangen besteet aus interaktiven Aufgaben,
Wiessel tëscht deem ass ganz sensibel a soll huelen 10 oder manner
ms. Am Géigesaz, sinn niddereg-Prioritéit Schlaangen aus laang-Lafen Aufgaben déi benotzen
CPU. An an dësem Fall passt laang Zäitintervaller ganz gutt (100ms).
An dësem Beispill ginn et 2 Aufgaben déi an der Prioritéit Schlaang 20 geschafft hunn
ms, opgedeelt an 10ms Fënsteren. 40ms an der Mëtt Schlaang (20ms Fënster) an an der niddereg Prioritéit
D'Schlaangzäitfenster gouf 40ms wou Aufgaben hir Aarbecht ofgeschloss hunn.
D'Solaris OS Implementatioun vun MLFQ ass eng Klass vun Zäit-Sharing Scheduler.
De Planer gëtt eng Rei vun Dëscher déi genau definéieren wéi et soll
d'Prioritéit vum Prozess ännert sech am Laf vu sengem Liewen, wat soll d'Gréisst sinn
zougewisen Fënster a wéi dacks musst Dir Aufgab Prioritéite erhéijen. Administrateur
Systemer kënne mat dësem Dësch interagéieren an de Scheduler behuelen
anescht. Par défaut huet dësen Dësch 60 Schlaangen mat enger gradueller Erhéijung
Fënster Gréisst vun 20ms (héich Prioritéit) zu puer honnert MS (niddereg Prioritéit), an
och mat engem Schwong vun all Aufgaben eemol pro Sekonn.
Aner MLFQ Planer benotzen keen Dësch oder spezifesch
Regelen, déi an dësem Virtrag beschriwwe sinn, am Géigendeel, si Berechent Prioritéite benotzt
mathematesch Formelen. Zum Beispill benotzt de FreeBSD Scheduler eng Formel fir
Berechent déi aktuell Prioritéit vun enger Aufgab baséiert op wéi laang de Prozess ass
benotzt CPU. Zousätzlech zerfällt d'CPU Notzung mat der Zäit, a sou
Also, d'Erhéijung vun der Prioritéit geschitt e bëssen anescht wéi uewen beschriwwen. Dat ass richteg
Zerfall Algorithmen genannt. Zënter Versioun 7.1 huet FreeBSD den ULE Scheduler benotzt.
Endlech, vill Scheduler hunn aner Funktiounen. Zum Beispill, e puer
Scheduler reservéieren den héchsten Niveau fir d'Operatioun vum Betribssystem an domat
Also kann kee Benotzerprozess déi héchst Prioritéit kréien
System. E puer Systemer erlaben Iech Rotschléi ze hëllefen
de Planer kann Prioritéite richteg setzen. Zum Beispill benotzt de Kommando léif
Dir kënnt d'Prioritéit vun enger Aufgab erhéijen oder erofsetzen an domat erhéijen oder
reduzéieren de Programm d'Chancen CPU Zäit ze benotzen.
MLFQ: Resumé
Mir hunn eng Planungs Approche genannt MLFQ beschriwwen. Säin Numm
am Prinzip vun der Operatioun zougemaach - et huet verschidde Schlaangen a benotzt Feedback
Aufgab Prioritéit ze bestëmmen.
Déi definitiv Form vun de Regele wäert wéi follegt sinn:
- Regel1: Wann Prioritéit (A) > Prioritéit (B), Aufgab A gëtt gestart (B net)
- Regel2: Wann Prioritéit (A) = Prioritéit (B), ginn A&B mat RR gestart
- Regel3: Wann eng Aufgab an de System erakënnt, gëtt se an der héchster Prioritéitschlaang gesat.
- Regel4: Nodeems eng Aufgab seng zougewisen Zäit an der aktueller Schlaang benotzt huet (egal wéi oft se d'CPU befreit huet), gëtt d'Prioritéit vun där Aufgab erofgesat (et beweegt sech an d'Schlaang erof).
- Regel5: No enger bestëmmter Period S, plënneren all Aufgaben am System op déi héchste Schlaang.
MLFQ ass interessant fir de folgende Grond - amplaz Wëssen iwwer ze erfuerderen
Natur vun der Aufgab am Viraus, den Algorithmus studéiert de vergaangene Verhalen vun der Aufgab a Sets
Prioritéiten deementspriechend. Also probéiert hien op zwee Still gläichzäiteg ze sëtzen - fir Produktivitéit fir kleng Aufgaben (SJF, STCF) z'erreechen an éierlech laang ze lafen,
CPU-Luede Aarbechten. Dofir, vill Systemer, dorënner BSD an hir Derivate,
Solaris, Windows, Mac benotzen eng Form vun Algorithmus als Scheduler
MLFQ als Basis.
Zousätzlech Material:
- (Informatik)
Source: will.com