Entwodiksyon nan sistèm operasyon yo
Bonjou, Habr! Mwen ta renmen prezante nan atansyon w yon seri atik-tradiksyon yon sèl literati ki enteresan nan opinyon mwen - OSTEP. Materyèl sa a egzamine byen pwofondman travay sistèm operasyon UNIX, sètadi travay ak pwosesis, pwogramasyon divès kalite, memwa ak lòt konpozan ki sanble ak yon sistèm eksplwatasyon modèn. Ou ka wè orijinal la nan tout materyèl isit la . Tanpri sonje ke tradiksyon an te fèt san pwofesyonèl (byen lib), men mwen espere ke mwen te kenbe siyifikasyon jeneral la.
Ou ka jwenn travay laboratwa sou sijè sa a isit la:
Lòt pati:
Ou ka tcheke tou chèn mwen an nan =)
Planifikasyon: Keu Feedback milti-nivo
Nan konferans sa a nou pral pale sou pwoblèm yo nan devlope youn nan apwòch ki pi popilè yo
planifikasyon, ki rele Keu Feedback milti-nivo (MLFQ). Planifikatè MLFQ te premye dekri an 1962 pa Fernando J. Corbató nan yon sistèm ki rele
Konpatib Tan-Sharing System (CTSS). Travay sa yo (ki gen ladan travay pita sou
Multics) te imedyatman nominasyon pou prim Turing. Planifikatè a te
imedyatman amelyore ak akeri aparans la ki ka jwenn deja nan
kèk sistèm modèn.
Algorithm MLFQ la eseye rezoud 2 pwoblèm fondamantal sipèpoze.
Premyerman, li eseye optimize tan an rotation, ki, jan nou te diskite nan konferans anvan an, se optimize pa metòd la nan kòmanse nan kòmansman an nan keu la pi plis.
travay kout. Sepandan, eksplwatasyon an pa konnen konbyen tan yon pwosesis patikilye pral kouri, ak sa a
konesans ki nesesè pou operasyon algoritm SJF, STCF. Dezyèmman, MLFQ ap eseye
fè sistèm nan reponn pou itilizatè yo (pa egzanp, pou moun ki chita ak
fikse sou ekran an ap tann pou travay la fini) epi konsa minimize tan
repons. Malerezman, algoritm tankou RR amelyore tan repons, men ekstrèmman
gen yon move enpak sou mezi a tan rotation. Pakonsekan pwoblèm nou an: Ki jan yo konsepsyon
yon pwogramè ki pral satisfè kondisyon nou yo san yo pa konnen anyen sou
nati pwosesis la an jeneral? Ki jan pwogramè a ka aprann karakteristik travay yo,
ki li lanse e konsa pran pi bon desizyon planifikasyon?
Sans nan pwoblèm nan: Ki jan yo planifye anviwònman an nan travay san konesans pafè?
Ki jan yo desine yon pwogramè ki an menm tan minimize tan repons
pou travay entèaktif ak an menm tan an minimize tan deplasman san yo pa konnen
konesans sou tan ekzekisyon travay?
Remak: nou aprann nan evènman anvan yo
Keu MLFQ a se yon egzanp ekselan nan yon sistèm ki aprann nan
evènman sot pase yo pou predi tan kap vini an. Apwòch ki sanble yo souvan
yo te jwenn nan OS (Ak anpil lòt branch nan syans òdinatè, ki gen ladan branch
prediksyon pyès ki nan konpitè ak algoritm kachèt). Vwayaj menm jan an
yo deklanche lè travay yo gen faz konpòtman epi yo konsa previzib.
Sepandan, ou ta dwe fè atansyon ak teknik sa a paske prediksyon yo trè fasil
ka tounen kòrèk epi mennen sistèm nan pran desizyon pi mal pase
ta dwe san konesans ditou.
MLFQ: Règ debaz yo
Ann gade règ debaz algorithm MLFQ la. Ak byenke aplikasyon sa a algorithm
Gen plizyè, apwòch debaz yo sanble.
Nan aplikasyon nou pral gade, MLFQ ap gen plizyè
ke moun kap kriye separe, chak nan yo pral gen yon priyorite diferan. Nenpòt lè,
yon travay ki pare pou egzekisyon se nan yon sèl keu. MLFQ itilize priyorite,
pou deside ki travay pou kouri pou ekzekisyon, i.e. travay ak pi wo
priyorite (travay ki soti nan keu ki gen pi gwo priyorite a) pral lanse an premye
keu.
Natirèlman, ka gen plis pase yon travay nan yon keu bay, kidonk
konsa yo pral gen menm priyorite. Nan ka sa a, yo pral itilize mekanis lan
RR pou planifye yon kouri nan mitan travay sa yo.
Se konsa, nou rive nan de règ debaz pou MLFQ:
- Règ 1: Si priyorite (A) > Priyorite (B), travay A pral lanse (B pa pral)
- Règ 2: Si priyorite (A) = Priyorite (B), A&B yo kòmanse itilize RR
Dapre pi wo a, eleman kle yo nan planifikasyon MLFQ
se priyorite. Olye pou yo bay chak priyorite fiks
travay, MLFQ chanje priyorite li depann sou konpòtman an obsève.
Pou egzanp, si yon travay toujou ap voye travay nan CPU a pandan y ap tann opinyon klavye a,
MLFQ ap kenbe priyorite pwosesis segondè paske se konsa
yon pwosesis entèaktif ta dwe travay. Si, okontrè, travay la se toujou ap ak
itilize CPU lou sou yon peryòd tan, MLFQ pral bese li
yon priyorite. Kidonk, MLFQ pral etidye konpòtman pwosesis yo pandan y ap kouri
epi sèvi ak konpòtman yo.
Ann trase yon egzanp sou kisa ke moun kap kriye yo ta ka sanble nan kèk pwen
tan ak Lè sa a, ou jwenn yon bagay tankou sa a:
Nan konplo sa a, 2 pwosesis A ak B yo nan keu priyorite ki pi wo a. Pwosesis
C se yon kote nan mitan an, ak pwosesis D se nan fen anpil keu la. Dapre pi wo a
Dapre deskripsyon algorithm MLFQ la, pwogramè a pral egzekite travay sèlman ak pi wo a.
priyorite dapre RR, ak travay C, D yo pral pa travay.
Natirèlman, yon snapshot estatik pa pral bay yon foto konplè sou ki jan MLFQ ap travay.
Li enpòtan pou w konprann egzakteman ki jan foto a chanje sou tan.
Eseye 1: Ki jan yo chanje priyorite
Nan pwen sa a ou bezwen deside kijan MLFQ pral chanje nivo priyorite a
travay (e konsa pozisyon travay la nan keu a) kòm li pwogrese nan sik lavi li yo. Pou
sa a nesesè kenbe nan tèt ou workflow la: yon sèten kantite
travay entèaktif ak tan kout (e konsa lage souvan
CPU) ak plizyè travay ki dire lontan ki sèvi ak CPU a tout tan travay yo, pandan y ap
Tan repons pa enpòtan pou travay sa yo. Ak fason sa a ou ka fè premye eseye ou
aplike algorithm MLFQ ak règ sa yo:
- Règ 3: Lè yon travay antre nan sistèm nan, li mete nan keu ki pi wo a
- priyorite.
- Règ 4a: Si yon travay sèvi ak tout fennèt tan ki bay li, Lè sa a, li
- priyorite redwi.
- Règ 4b: Si yon Travay lage CPU a anvan fennèt tan li a ekspire, Lè sa a, li
- rete ak menm priyorite.
Egzanp 1: Yon sèl travay ki dire lontan
Kòm yo ka wè nan egzanp sa a, travay la admisyon mete ak pi wo a
priyorite. Apre yon fenèt tan nan 10ms, pwosesis la se degrade nan priyorite
planifikatè. Apre fennèt tan kap vini an, travay la finalman degrade a
pi ba priyorite nan sistèm nan, kote li rete.
Egzanp 2: Livre yon travay kout
Koulye a, ann wè yon egzanp sou fason MLFQ pral eseye apwoche SJF. Nan sa
egzanp, de travay: A, ki se yon travay ki dire lontan toujou ap
okipe CPU ak B, ki se yon travay kout entèaktif. Sipoze
ke A te deja travay depi kèk tan lè travay B te rive.
Grafik sa a montre rezilta senaryo a. Travay A, tankou nenpòt travay,
Itilizasyon CPU te nan pati anba a anpil. Travay B ap rive nan tan T=100 epi li pral
plase nan keu priyorite ki pi wo a. Depi lè fonksyònman li kout, lè sa a
li pral fini anvan yo rive nan dènye keu la.
Soti nan egzanp sa a, objektif prensipal algorithm la ta dwe konprann: depi algorithm la pa fè sa
konnen si yon travay se long oswa kout, Lè sa a, premye nan tout li sipoze ke travay la
kout epi li ba li pi gwo priyorite. Si sa a se yon travay vrèman kout, lè sa a
li pral ranpli byen vit, otreman si li se yon travay long, li pral deplase dousman
priyorite desann epi yo pral byento pwouve ke li se tout bon yon travay long ki pa fè sa
mande yon repons.
Egzanp 3: E I/O?
Koulye a, ann gade nan yon egzanp I/O. Jan sa di nan règ 4b,
si yon pwosesis lage processeur a san yo pa itilize tout tan processeur li a,
Lè sa a, li rete nan menm nivo priyorite. Entansyon règ sa a se byen senp
- si travay entèaktif la fè yon anpil nan operasyon I/O, pou egzanp, ap tann
soti nan kle itilizatè a oswa peze sourit, tankou yon travay pral libere processeur a
anvan fennèt la. Nou pa ta renmen bese priyorite yon travay konsa,
e konsa li pral rete nan menm nivo.
Egzanp sa a montre ki jan algorithm la pral travay ak pwosesis sa yo - travay entèaktif B, ki sèlman bezwen CPU pou 1ms anvan ekzekisyon.
I/O pwosesis ak travay ki dire lontan A, ki pase tout tan li lè l sèvi avèk CPU a.
MLFQ kenbe pwosesis B nan pi gwo priyorite paske li kontinye
lage CPU a. Si B se yon travay entèaktif, Lè sa a, algorithm la te reyalize
Objektif ou se kouri travay entèaktif byen vit.
Pwoblèm ak algorithm MLFQ aktyèl la
Nan egzanp anvan yo nou bati yon vèsyon debaz nan MLFQ. Epi li sanble ke li
fè travay li byen ak onètman, distribye tan CPU san patipri ant
travay long ak pèmèt travay kout oswa gwo volim
travay sou I/O byen vit. Malerezman, apwòch sa a gen plizyè
pwoblèm grav.
Premyerman, pwoblèm nan grangou: si sistèm nan gen anpil entèaktif
travay, Lè sa a, yo pral konsome tout tan an processeur e konsa pa yon sèl pou yon tan long
travay la p ap ka egzekite (yo ap mouri grangou).
Dezyèmman, itilizatè entelijan te kapab ekri pwogram yo pou sa
twonpe pwogramè a. Desepsyon se nan fè yon bagay pou fòse
Planifikatè a bay pwosesis la plis tan CPU. Algorithm sa
ki dekri pi wo a se byen vilnerab a atak sa yo: anvan fenèt la tan se pratikman
fini, ou bezwen fè yon operasyon I/O (pou kèk, kèlkeswa dosye)
epi konsa libere CPU a. Konpòtman sa a pral pèmèt ou rete nan menm bagay la
keu la tèt li epi ankò jwenn yon pi gwo pousantaj tan CPU. Si ou fè
sa a kòrèk (pa egzanp, egzekite 99% nan tan fenèt la anvan yo lage CPU a),
tankou yon travay ka tou senpleman monopolize processeur la.
Finalman, yon pwogram ka chanje konpòtman li sou tan. Travay sa yo
ki itilize CPU a ka vin entèaktif. Nan egzanp nou an, menm jan an
travay yo p ap resevwa tretman yo merite nan men pwogramè a tankou lòt moun ta
(inisyal) travay entèaktif.
Kesyon pou odyans lan: ki atak sou pwogramè a ta ka fèt nan mond modèn lan?
Eseye 2: Ogmante priyorite
Ann eseye chanje règ yo epi wè si nou ka evite pwoblèm ak
jèn. Ki sa nou ka fè pou asire sa ki gen rapò
Travay CPU yo pral jwenn tan yo (menm si pa lontan).
Kòm yon solisyon senp nan pwoblèm nan, ou ka sijere detanzantan
ogmante priyorite tout travay sa yo nan sistèm nan. Gen plizyè fason
Pou reyalize sa a, ann eseye aplike yon bagay senp kòm yon egzanp: tradui
tout travay yo imedyatman bay pi gwo priyorite, kidonk nouvo règ la:
- Règleman5: Apre yon sèten peryòd S, deplase tout travay nan sistèm nan nan keu ki pi wo a.
Nouvo règ nou an rezoud de pwoblèm alafwa. Premyèman, pwosesis yo
yo garanti yo pa mouri grangou: travay ki nan pi gwo priyorite yo pral divize
CPU tan dapre algorithm RR a e konsa tout pwosesis yo pral resevwa
tan CPU. Dezyèmman, si gen kèk pwosesis ki te deja itilize
sèlman processeur a vin entèaktif, li pral rete nan keu la ak pi wo a
priyorite apre yo fin resevwa yon ogmantasyon yon sèl fwa nan priyorite a pi wo a.
Ann gade yon egzanp. Nan senaryo sa a, konsidere yon pwosesis lè l sèvi avèk
CPU ak de entèaktif, pwosesis kout. Sou bò gòch la nan figi a, figi a montre konpòtman an san pwomosyon priyorite, e konsa travay la long kouri kòmanse mouri grangou apre de travay entèaktif rive nan sistèm nan. Nan figi ki sou bò dwat la, yon ogmantasyon priyorite fèt chak 50ms e konsa tout pwosesis yo garanti yo resevwa tan CPU epi yo pral lanse detanzantan. 50ms nan ka sa a pran kòm yon egzanp; an reyalite nimewo sa a se yon ti kras pi wo.
Li evidan, ajoute tan an ogmantasyon peryodik S mennen nan
yon kesyon ki lojik: ki valè yo ta dwe mete? Youn nan onore yo
enjenyè sistèm John Ousterhout te rele kantite sa yo nan sistèm kòm voo-doo
konstan, depi yo nan kèk fason mande maji nwa pou kòrèk
ekspoze. Epi, malerezman, S gen yon sant konsa. Si ou mete valè a tou
gwo - travay long ap kòmanse mouri grangou. Men, si ou mete valè a twò ba,
Travay entèaktif pa pral resevwa bon tan CPU.
Eseye 3: Pi bon Kontablite
Koulye a, nou gen yon lòt pwoblèm yo rezoud: ki jan pa
pèmèt pwogramè nou an twonpe? Moun ki blame pou posibilite sa a se
règ 4a, 4b, ki pèmèt yon travay kenbe priyorite, libere processeur a
anvan tan yo bay la ekspire. Ki jan fè fas ak sa a?
Solisyon an nan ka sa a ka konsidere kòm yon pi bon kontablite nan tan CPU sou chak
Nivo MLFQ. Olye ke yo bliye lè pwogram lan te itilize
processeur pou peryòd la, li ta dwe pran an kont ak sove. Apre
pwosesis la te itilize tan li yo, li ta dwe degrade nan pwochen an
nivo priyorite. Koulye a, li pa enpòtan ki jan pwosesis la pral sèvi ak tan li - ki jan
toujou ap kalkile sou processeur a oswa kòm yon kantite apèl. Kidonk,
règ 4 ta dwe reekri nan fòm sa a:
- Règleman4: Apre yon travay te itilize tan li te resevwa nan keu aktyèl la (pa gen pwoblèm konbyen fwa li te libere CPU a), priyorite travay sa a bese (li deplase desann keu a).
Ann gade yon egzanp:
»
Figi a montre sa k ap pase si ou eseye twonpe pwogramè a, tankou
si se te ak règ anvan yo 4a, 4b rezilta ki sou bò gòch la ta jwenn. Kè kontan nouvo
règ la se rezilta a sou bò dwat la. Anvan pwoteksyon, nenpòt pwosesis te kapab rele I/O anvan fini ak
konsa domine CPU a, apre yo fin pèmèt pwoteksyon, kèlkeswa konpòtman
I/O, li pral toujou deplase desann nan keu la epi konsa pa yo pral kapab malonètman
pran sou resous CPU yo.
Amelyore MLFQ ak lòt pwoblèm
Avèk amelyorasyon ki anwo yo vini nouvo pwoblèm: youn nan prensipal la
Kesyon - ki jan yo paramèt tankou yon orè? Moun sa yo. Konbyen li ta dwe
keu? Ki gwosè fenèt pwogram lan ta dwe nan keu a? Ki jan
Priyorite pwogram yo ta dwe souvan ogmante pou evite grangou ak
pran an kont chanjman nan konpòtman pwogram nan? Pa gen yon repons senp pou kesyon sa yo
reponn ak sèlman eksperyans ak chaj ak konfigirasyon ki vin apre
planifikatè ka mennen nan kèk balans satisfezan.
Pou egzanp, pifò aplikasyon MLFQ pèmèt ou bay diferan
entèval tan pou ke moun kap kriye diferan. Gwo priyorite ke moun kap kriye anjeneral
entèval kout yo preskri. File sa yo konpoze de travay entèaktif,
chanje ant ki se byen sansib epi yo ta dwe pran 10 oswa mwens
ms. Nan contrast, ke moun kap kriye priyorite ki ba yo konpoze de travay ki dire lontan ki itilize
CPU. Ak nan ka sa a, entèval tan long anfòm trè byen (100ms).
Nan egzanp sa a gen 2 travay ki te travay nan gwo priyorite keu 20
ms, divize an 10ms fenèt. 40ms nan mitan keu (20ms fenèt) ak nan priyorite ki ba
Fenèt tan keu la te vin 40ms kote travay yo te fini travay yo.
Enplemantasyon MLFQ Solaris OS se yon klas pwogramasyon tan pataje.
Planifikatè a pral bay yon seri tab ki defini egzakteman jan li ta dwe
priyorite nan pwosesis la chanje sou kou a nan lavi li, ki sa ki ta dwe gwosè a
fenèt atribye ba yo ak konbyen fwa ou bezwen ogmante priyorite travay yo. Administratè
sistèm yo ka kominike avèk tablo sa a epi lakòz pwogramasyon an konpòte yo
yon fason diferan. Pa default, tab sa a gen 60 moun kap kriye ak yon ogmantasyon gradyèl
gwosè fenèt soti nan 20ms (priyorite segondè) a plizyè santèn ms (priyorite ki ba), ak
tou ak yon ogmantasyon nan tout travay yon fwa pa segonn.
Lòt planifikatè MLFQ pa sèvi ak yon tab oswa okenn espesifik
règ ki dekri nan konferans sa a, okontrè, yo kalkile priyorite lè l sèvi avèk
fòmil matematik. Pou egzanp, pwogramasyon FreeBSD la itilize yon fòmil pou
kalkile priyorite aktyèl la nan yon travay ki baze sou konbyen tan pwosesis la se
itilize CPU. Anplis de sa, itilizasyon CPU dekonpoze sou tan, ak konsa
Kidonk, ogmante priyorite rive yon ti jan diferan pase sa ki dekri pi wo a. Sa a se vre
yo rele algorithm dekonpozisyon. Depi vèsyon 7.1, FreeBSD te itilize pwogramasyon ULE la.
Finalman, anpil pwogramè gen lòt karakteristik. Pou egzanp, kèk
pwogramè yo rezève nivo ki pi wo yo pou operasyon sistèm operasyon an e konsa
Kidonk, pa gen okenn pwosesis itilizatè ka resevwa pi gwo priyorite nan
sistèm. Kèk sistèm pèmèt ou bay konsèy pou ede
planifikatè a ka fikse priyorite kòrèkteman. Pou egzanp, lè l sèvi avèk lòd la nice
ou ka ogmante oswa diminye priyorite nan yon travay epi konsa ogmante oswa
redwi chans pou pwogram nan itilize tan CPU.
MLFQ: Rezime
Nou te dekri yon apwòch planifikasyon ki rele MLFQ. Non li
fèmen nan prensip la nan operasyon - li gen plizyè ke moun kap kriye epi sèvi ak fidbak
pou detèmine priyorite travay.
Fòm final la nan règ yo pral jan sa a:
- Règleman1: Si priyorite (A) > Priyorite (B), travay A pral lanse (B pa pral)
- Règleman2: Si priyorite (A) = Priyorite (B), A&B yo kòmanse itilize RR
- Règleman3: Lè yon travay antre nan sistèm nan, li mete l nan pi gwo priyorite keu.
- Règleman4: Apre yon travay te itilize tan li te resevwa nan keu aktyèl la (pa gen pwoblèm konbyen fwa li te libere CPU a), priyorite travay sa a bese (li deplase desann keu a).
- Règleman5: Apre yon sèten peryòd S, deplase tout travay nan sistèm nan nan keu ki pi wo a.
MLFQ enteresan pou rezon sa a - olye pou yo mande konesans sou
nati travay la an avans, algorithm la etidye konpòtman sot pase travay la ak ansanm
priyorite kòmsadwa. Kidonk, li eseye chita sou de chèz nan yon fwa - reyalize pwodiktivite pou ti travay (SJF, STCF) ak onètman kouri lontan,
CPU-chaje travay. Se poutèt sa, anpil sistèm, ki gen ladan BSD ak dérivés yo,
Solaris, Windows, Mac sèvi ak kèk fòm algorithm kòm orè
MLFQ kòm yon baz.
Lòt materyèl:
- (informatique)
Sous: www.habr.com