Enkonduko al Operaciumoj
Hej Habr! Mi ŝatus atentigi vin serion da artikoloj-tradukoj de unu interesa literaturo laŭ mi - OSTEP. Ĉi tiu materialo diskutas sufiĉe profunde la laboron de Unikso-similaj operaciumoj, nome, laboro kun procezoj, diversaj planiloj, memoro kaj aliaj similaj komponantoj kiuj konsistigas modernan OS. Vi povas vidi la originalon de ĉiuj materialoj ĉi tie . Bonvolu noti, ke la traduko estis farita senprofesie (sufiĉe libere), sed mi esperas, ke mi konservis la ĝeneralan signifon.
Laboratorio pri ĉi tiu temo troveblas ĉi tie:
Aliaj partoj:
Vi ankaŭ povas kontroli mian kanalon ĉe =)
Planado: Multnivela Retrovico
En ĉi tiu prelego, ni parolos pri la problemoj de disvolvi unu el la plej famaj aliroj al
planado, kiu nomiĝas Multnivela Retrovico (MLFQ). La MLFQ-planilo unue estis priskribita en 1962 fare de Fernando J. Corbató en sistemo nomita
Kongrua Tempo-kundivida Sistemo (CTSS). Tiuj verkoj (inkluzive de pli posta laboro pri
Multics) poste estis nomumitaj por Turing Award. La planisto estis
poste plibonigis kaj akiris la aspekton kiu troviĝas jam en
iuj modernaj sistemoj.
La MLFQ-algoritmo provas solvi 2 fundamentajn interkovrajn problemojn.
Unue, ĝi provas optimumigi la turnan tempon, kiu, kiel ni diskutis en la antaŭa prelego, estas optimumigita per la metodo komenci ĉe la kapo de la atendovico plej
mallongaj taskoj. Tamen, la OS ne scias kiom longe daŭros tiu aŭ alia procezo, kaj ĉi tio
necesaj scioj por la funkciado de SJF, STCF-algoritmoj. Dua, MLFQ provas
igu la sistemon respondema por uzantoj (ekzemple por tiuj, kiuj sidas kaj
rigardante la ekranon atendante ke la tasko finiĝos) kaj tiel minimumigi la tempon
respondo. Bedaŭrinde, algoritmoj kiel RR reduktas respondtempon, sed
havas malbonan efikon sur la turna tempometriko. Tial nia problemo: Kiel desegni
planilo, kiu plenumos niajn postulojn kaj samtempe scias nenion pri
la naturo de la procezo ĝenerale? Kiel la planisto povas lerni la karakterizaĵojn de taskoj,
kiun ĝi lanĉas kaj tiel fari pli bonajn plandecidojn?
La esenco de la problemo: Kiel plani la agordon de taskoj sen perfekta scio?
Kiel desegni planilon, kiu samtempe minimumigas respondtempon
por interagaj taskoj kaj samtempe minimumigas la tempodaŭron sen scii
scio pri tasko ekzekuttempo?
Noto: lernado de antaŭaj eventoj
La MLFQ-vico estas bonega ekzemplo de sistemo, kiu estas trejnita
pasintaj eventoj por antaŭdiri la estontecon. Similaj aliroj ofte estas
trovita en la OS (Kaj multaj aliaj branĉoj en komputiko, inkluzive de branĉoj
aparataj prognozoj kaj kaŝmemoro-algoritmoj). Similaj ekskursoj
ellasilon kiam taskoj havas kondutismajn fazojn kaj estas tiel antaŭvideblaj.
Tamen, vi devus esti singarda kun ĉi tiu tekniko ĉar antaŭdiroj estas tre facilaj
povas montriĝi malĝusta kaj konduki la sistemon fari pli malbonajn decidojn ol
estus tute sen scio.
MLFQ: Bazaj Reguloj
Ni rigardu la bazajn regulojn de la MLFQ-algoritmo. Kaj kvankam efektivigoj de ĉi tiu algoritmo
estas pluraj, la bazaj aliroj estas similaj.
En la efektivigo, kiun ni rigardos, MLFQ havos plurajn
apartaj vostoj, ĉiu el kiuj havos malsaman prioritaton. Iam ajn,
la tasko preta por ekzekuto estas en la sama vico. MLFQ uzas prioritatojn,
decidi kiun taskon kuri por ekzekuto, t.e. tasko kun pli alta
prioritato (tasko el la vico kun la plej alta prioritato) estos lanĉita ĉe la unua
vico.
Kompreneble, povas esti pli ol unu tasko en aparta vico, do
do ili havos la saman prioritaton. En ĉi tiu kazo, la mekanismo estos uzata
RR plani kuron inter ĉi tiuj taskoj.
Tiel ni alvenas al du bazaj reguloj por MLFQ:
- Regulo 1: Se prioritato (A) > Prioritato (B), tasko A ruliĝos (B ne)
- Regulo2: Se prioritato(A) = Prioritato(B), A&B komenciĝas per RR
Surbaze de ĉi-supra, la ŝlosilaj elementoj por plani MLFQ estas
estas prioritatoj. Anstataŭ doni fiksan prioritaton al ĉiu
tasko, MLFQ ŝanĝas sian prioritaton depende de la observita konduto.
Ekzemple, se tasko konstante ĉesas sur la CPU atendante klavarenigon,
MLFQ tenos la procezan prioritaton alta ĉar tiel
interaga procezo devus funkcii. Se, male, la tasko estas konstante kaj
estas CPU-intensa dum longa periodo, MLFQ malaltigos ĝin
prioritato. Tiel, MLFQ studos la konduton de procezoj en la tempo kiam ili funkcias.
kaj uzu kondutojn.
Ni desegnu ekzemplon de kia la vicoj povus aspekti iam
tempo kaj tiam vi ricevas ion tian:
En ĉi tiu skemo, 2 procezoj A kaj B estas en la atendovico kun la plej alta prioritato. Procezo
C estas ie en la mezo, kaj procezo D estas ĉe la fino de la atendovico. Laŭ la supre
priskriboj de la MLFQ-algoritmo, la planilo nur plenumos taskojn kun la plej alta
prioritato laŭ RR, kaj taskoj C, D estos senlabora.
Kompreneble, senmova momentfoto ne donos kompletan bildon pri kiel MLFQ funkcias.
Gravas kompreni ĝuste kiel la bildo ŝanĝiĝas laŭlonge de la tempo.
Provo 1: Kiel ŝanĝi la prioritaton
Je ĉi tiu punkto vi devas decidi kiel MLFQ ŝanĝos la prioritatnivelon
tasko (kaj tiel la pozicio de la tasko en la atendovico) dum ĝia vivociklo. Por
pri tio, vi devas memori la laborfluon: certan kvanton
interagaj taskoj kun mallongaj daŭraj tempoj (kaj tiel ofta liberigo
CPU) kaj pluraj longdaŭraj taskoj, kiuj uzas la CPU sian tutan labortempon, dum
Respondtempo ne gravas por tiaj taskoj. Kaj tiel vi povas fari vian unuan provon
efektivigu la MLFQ-algoritmon kun la sekvaj reguloj:
- Regulo 3: Kiam tasko eniras la sistemon, ĝi estas metita en la voston kun la plej alta
- prioritato.
- Regulo4a: Se tasko uzas sian tutan tempfenestron, tiam ĝi
- la prioritato malaltiĝas.
- Regulo4b: Se Tasko liberigas la CPU antaŭ ol ĝia tempofenestro eksvalidiĝas, tiam ĝi
- restas kun la sama prioritato.
Ekzemplo 1: Ununura longdaŭra tasko
Kiel videblas en ĉi tiu ekzemplo, la akceptotasko estas agordita kun la plej alta
prioritato. Post 10ms tempofenestro, la procezo estas malaltigita en prioritato.
planisto. Post la sekva tempofenestro, la tasko estas finfine malaltigita al
plej malalta prioritato en la sistemo, kie ĝi restas.
Ekzemplo 2: Liveris mallongan taskon
Nun ni vidu ekzemplon pri kiel MLFQ provos alproksimiĝi al SJF. En tio
ekzemple, du taskoj: A, kiu estas longdaŭra tasko konstante
okupante CPU kaj B, kio estas mallonga interaga tasko. Supozu
ke A jam estis kuranta de iom da tempo, kiam tasko B alvenis.
Ĉi tiu grafikaĵo montras la rezultojn de la scenaro. Tasko A, kiel ajna tasko,
uzi la CPU estis ĉe la fundo. Tasko B alvenos je la tempo T=100 kaj volos
metita en la plej alta prioritatovico. Ĉar ĝia funkciada tempo estas mallonga, do
ĝi finiĝos antaŭ ol ĝi atingos la lastan vicon.
El ĉi tiu ekzemplo, la ĉefa celo de la algoritmo devus esti komprenita: ĉar la algoritmo ne faras
scias, ĉu tasko estas longa aŭ mallonga, tiam antaŭ ĉio li supozas, ke la tasko
mallonga kaj donas al ĝi la plej altan prioritaton. Se vere estas mallonga tasko, do
ĝi efektiviĝos rapide, alie se ĝi estas longa tasko ĝi moviĝos malrapide
en prioritato malsupren kaj baldaŭ pruvos ke ŝi ja estas longa tasko kiu ne faras
postulas respondon.
Ekzemplo 3: Kio pri I/O?
Nun ni rigardu ekzemplon de I/O. Kiel dirite en regulo 4b,
se procezo liberigas la procesoron sen plene uzi sian procesoran tempon,
tiam ĝi restas ĉe la sama prioritatnivelo. La intenco de ĉi tiu regulo estas sufiĉe simpla.
- se la interaga laboro faras multajn I/O-operaciojn, ekzemple, atendante
de la uzantklavopremoj aŭ muso, tia tasko liberigos la procesoron
antaŭ la asignita fenestro. Ni ne ŝatus preterlasi tian prioritatan taskon,
kaj tiel ĝi restos sur la sama nivelo.
Ĉi tiu ekzemplo montras kiel la algoritmo funkcios kun tiaj procezoj - interaga laboro B, kiu bezonas CPU nur por 1 ms antaŭ ekzekuto.
I/O-procezo kaj longa laboro A, kiu uzas la CPU la tutan tempon.
MLFQ konservas procezon B ĉe la plej alta prioritato dum ĝi daŭras
liberigu la CPU. Se B estas interaga tasko, tiam la algoritmo en ĉi tiu kazo atingis
ĝia celo estas rapide lanĉi interagajn taskojn.
Problemoj kun la nuna MLFQ-algoritmo
En la antaŭaj ekzemploj, ni konstruis bazan version de MLFQ. Kaj ŝajnas ke li
faras sian laboron bone kaj juste, distribuante CPU-tempon juste inter
longaj taskoj kaj permesante mallongajn taskojn aŭ taskojn kiuj estas peze alireblaj
al I/O por procesi rapide. Bedaŭrinde, ĉi tiu aliro enhavas plurajn
seriozaj problemoj.
Unue, La problemo de malsato: se la sistemo havos multajn interagajn
taskoj, tiam ili konsumos la tutan procesoran tempon kaj tiel ne unu solan dum longa tempo
la tasko ne havos ŝancon esti ekzekutita (ili malsatas).
Dua, inteligentaj uzantoj povus skribi siajn programojn tiel ke
trompi la planiston. La trompo kuŝas en fari ion por devigi
planilo por doni al la procezo pli da CPU-tempo. La algoritmo kiu
priskribita supre estas sufiĉe vundebla al similaj atakoj: antaŭ la tempofenestro estas preskaŭ
super, vi devas fari I/O-operacion (al iuj, negrave kiu dosiero)
kaj tiel liberigi la CPU. Tia konduto permesos al vi resti en la sama
la atendovico mem kaj denove ricevas pli grandan procenton de CPU-tempo. Se farite
ĉi tio estas ĝusta (ekz. rulu 99% de la fenestra tempo antaŭ liberigi la CPU),
tia tasko povas simple monopoligi la procesoron.
Fine, programo povas ŝanĝi sian konduton laŭlonge de la tempo. Tiuj taskoj
kiu uzis la CPU povas fariĝi interagaj. En nia ekzemplo, simila
taskoj ne ricevos la traktadon, kiun ili meritas de la planisto, kiel aliaj ricevus
(originalaj) interagaj taskoj.
Demando por la spektantaro: kiaj atakoj kontraŭ la planisto povus esti faritaj en la moderna mondo?
Provo 2: Pliigu la prioritaton
Ni provu ŝanĝi la regulojn kaj vidu ĉu ni povas eviti problemojn kun
fastado. Kion ni povas fari por certigi tion rilatan
CPU-taskoj ricevos sian tempon (eĉ se ne longaj).
Kiel simpla solvo al la problemo, vi povas sugesti periode
pliigi la prioritaton de ĉiuj tiaj taskoj en la sistemo. Estas multaj manieroj
por atingi tion, ni provu efektivigi ion simplan kiel ekzemplon: traduki
ĉiuj taskoj tuj ricevas la plej altan prioritaton, tial la nova regulo:
- Regulo5: Post iom da periodo S, translokigu ĉiujn taskojn en la sistemo al la plej alta atendovico.
Nia nova regulo solvas du problemojn samtempe. Unue, la procezoj
garantiite ne malsato: taskoj en la plej alta vico dividos
procesorotempo laŭ la RR-algoritmo kaj tiel ĉiuj procezoj ricevos
CPU-tempo. Due, se iu procezo kiu antaŭe uzis
nur la procesoro fariĝas interaga, ĝi restos en la vosto kun la plej alta
prioritato post ricevado de akcelo al la plej alta prioritato unufoje.
Konsideru ekzemplon. En ĉi tiu scenaro, konsideru ununuran procezon uzante
CPU kaj du interagaj, mallongaj procezoj. Maldekstre en la figuro, la figuro montras la konduton sen prioritata akcelo, kaj tiel la longdaŭra tasko komencas malsati post kiam du interagaj taskoj alvenas al la sistemo. En la figuro dekstre, ĉiu 50ms prioritata pliiĝo estas farita kaj tiel ĉiuj procezoj estas garantiitaj ricevi procesoran tempon kaj periode komenciĝos. 50ms en ĉi tiu kazo estas prenita kiel ekzemplo, fakte ĉi tiu nombro estas iom pli alta.
Estas evidente ke la aldono de la perioda pliiĝotempo S kondukas al
logika demando: kian valoron oni agordu? Unu el la merititaj
sisteminĝenieroj John Ousterhout nomis similajn kvantojn en sistemoj voo-doo
konstanta, ĉar ili iel postulis nigran magion por la ĝusta
elmontrante. Kaj, bedaŭrinde, S havas tian guston. Se vi ankaŭ fiksas la valoron
grandaj — longaj taskoj malsatos. Kaj se vi starigas ĝin tro malalte,
interagaj taskoj ne ricevos taŭgan CPU-tempon.
Provo 3: Pli bona Kontado
Nun ni havas ankoraŭ unu problemon por solvi: kiel ne
permesi nian planiston esti trompita? La homoj kulpaj pri ĉi tiu ebleco estas
reguloj 4a, 4b kiuj permesas al laboro konservi sian prioritaton liberigante la procesoron
antaŭ la eksvalidiĝo de la asignita tempo. Kiel trakti ĝin?
La solvo en ĉi tiu kazo povas esti konsiderita pli bona kontado de CPU-tempo sur ĉiu
MLFQ-nivelo. Anstataŭ forgesi la tempon, kiun la programo uzis
procesoro por la asignita periodo, ĝi devus esti konsiderata kaj konservita. Post
la procezo eluzis sian asignitan tempon, ĝi devus esti degradita al la sekva
prioritata nivelo. Nun ne gravas kiel la procezo uzos sian tempon - kiel
konstante komputante sur la procesoro aŭ kiel aro de vokoj. Tiel,
regulo 4 devus esti reverkita jene:
- Regulo4: Post kiam tasko eluzis sian asignitan tempon en la nuna atendovico (sendepende de kiom da fojoj ĝi liberigis la CPU), la prioritato de tia tasko estas reduktita (ĝi moviĝas malsupren en la atendovico).
Ni rigardu ekzemplon:
»
La figuro montras kio okazas se vi provas trompi la planiston, kiel
se ĝi estus kun la antaŭaj reguloj 4a, 4b estus la rezulto maldekstre. Kun nova
la regulo estas la rezulto dekstre. Antaŭ protekto, ajna procezo povus voki I/O antaŭ kompletigo kaj
tiel regas la CPU, post ebligado de protekto, sendepende de konduto
I/O, li ankoraŭ malsupreniros en la vico kaj tiel ne povos malhoneste
transpreni CPU-rimedojn.
Plibonigante MLFQ kaj aliajn problemojn
Kun ĉi-supraj plibonigoj aperas novaj problemoj: unu el la ĉefaj
demandoj - kiel parametrigi tian planilon? Tiuj. Kiom devus esti
vicoj? Kio devus esti la grandeco de la programfenestro ene de la atendovico? Kiel
programo ofte estu prioritatita por eviti malsaton kaj
konsideri la ŝanĝon en la konduto de la programo? Al ĉi tiuj demandoj, ne estas simpla
respondo kaj nur eksperimentoj kun ŝarĝoj kaj posta agordo
planisto povas konduki al iu kontentiga ekvilibro.
Ekzemple, plej multaj MLFQ-efektivigoj permesas vin asigni malsamajn
temponiĉoj por malsamaj atendovicoj. Alta prioritataj atendovicoj estas kutime
mallongaj intervaloj. Tiuj atendovicoj konsistas el interagaj taskoj,
ŝanĝi inter kiuj estas sufiĉe sentema kaj devus preni 10 aŭ malpli
ms. En kontrasto, malalt-prioritataj atendovicoj konsistas el longdaŭraj taskoj kiuj uzas
CPU. Kaj en ĉi tiu kazo, longaj tempintervaloj tre bone taŭgas (100ms).
En ĉi tiu ekzemplo estas 2 taskoj kiuj funkciis en altprioritata atendovico 20
ms, dividita en 10ms fenestrojn. 40ms en la meza vico (20ms fenestro) kaj en la malalta prioritato
atendovictempofenestro iĝis 40ms kie la taskoj kompletigis sian laboron.
La Solaris OS-efektivigo de MLFQ estas klaso de tempodividaj planistoj.
La planilo provizos aron da tabeloj, kiuj difinas ĝuste kiel ĝi devus
ŝanĝi la prioritaton de la procezo dum ĝia vivo, kio devus esti la grandeco
fenestro por esti asignita kaj kiom ofte levi taskoprioritatojn. Administranto
sistemo povas interagi kun ĉi tiu tabelo kaj igi la planilon konduti
malsame. Defaŭlte, ĉi tiu tablo havas 60 atendovicojn kun laŭpaŝa pliiĝo
fenestra grandeco de 20ms (alta prioritato) ĝis kelkcent ms (malalta prioritato), kaj
ankaŭ kun la akcelo de ĉiuj taskoj unufoje sekundo.
Aliaj MLFQ-planistoj ne uzas tabelon aŭ ajnan specifan
reguloj kiuj estas priskribitaj en ĉi tiu prelego, male, ili kalkulas prioritatojn uzante
matematikaj formuloj. Ekzemple, la planilo en FreeBSD uzas formulon por
kalkulante la nunan taskoprioritato surbaze de kiom multe la procezo
uzita CPU. Krome, CPU-uzado malpliiĝas kun la tempo, kaj tiel
Tiel, la prioritata kresko estas iom malsama ol priskribita supre. Ĉi tio estas vera
nomataj disfalo-algoritmoj. Ekde versio 7.1, FreeBSD uzas la ULE-planilon.
Fine, multaj planistoj havas aliajn funkciojn. Ekzemple, iuj
planistoj rezervas la plej altajn nivelojn por la funkciado de la operaciumo kaj tiel
Tiel, neniu uzantprocezo povas akiri la plej altan prioritaton
sistemo. Iuj sistemoj permesas vin doni konsilojn por helpi
la planisto ĝuste prioritati. Ekzemple, uzante la komandon bela
vi povas pliigi aŭ malpliigi la prioritaton de tasko kaj tiel pliigi aŭ
redukti la ŝancojn de la programo por CPU-tempo.
MLFQ: Resumo
Ni priskribis planan aliron nomitan MLFQ. Lia nomo
konkludita en la principo de funkciado - ĝi havas plurajn atendovicojn kaj uzas reagojn
prioritatigi taskon.
La fina formo de la reguloj estos kiel sekvas:
- Regulo1: Se prioritato(A) > Prioritato(B), tasko A ruliĝos (B ne)
- Regulo2: Se prioritato(A) = Prioritato(B), A&B komenciĝas per RR
- Regulo3: Kiam tasko eniras la sistemon, ĝi estas metita en la plej altan prioritatvicon.
- Regulo4: Post kiam tasko eluzis sian asignitan tempon en la nuna atendovico (sendepende de kiom da fojoj ĝi liberigis la CPU), la prioritato de tia tasko estas reduktita (ĝi moviĝas malsupren en la atendovico).
- Regulo5: Post iom da periodo S, translokigu ĉiujn taskojn en la sistemo al la plej alta atendovico.
MLFQ estas interesa pro la jena kialo - anstataŭ postuli scion pri
naturo de la tasko anticipe, la algoritmo lernas la pasintan konduton de la tasko kaj aroj
prioritatoj laŭe. Tiel, li provas sidi sur du seĝoj samtempe - atingi rendimenton por malgrandaj taskoj (SJF, STCF) kaj honeste kuri longajn,
CPU-ŝarĝaj laboroj. Tial, multaj sistemoj, inkluzive de BSD kaj iliaj derivaĵoj,
Solaris, Vindozo, Mac uzas iun formon de algoritmo kiel la planilon
MLFQ kiel bazlinio.
Pliaj materialoj:
- (komputado)
fonto: www.habr.com