|
ot razor(24-06-2005)
reiting (31)
[ dobre ]
[ zle ]
Variant za otpechatvane Algoritmi za razpredeliane na
protsesornoto
vreme v 4.4BSD, Linux iadra 2.4,2.6.
Mnogo e vazhno da se opredeli iasna granitsa mezhdu mehanizum
i politika na razpredeliane na protsesornoto vreme. Zashto ?
Zashtoto ako imame edin protses s mnogo detsa i niakoi ot detsata
sa po-vazhni ot drugi, mehanizma ne mozhe da razbere koe e
po-vazhno i mozhe da dade po maluk prioritet na po-vazhno dete.
Poradi tazi prichina e dadena vuzmozhnostta na protsesa da si
opredelia koe dete e po vazhno.
Vsiaka moderna operatsionna sistema poddurzha mnogozadachnost,
tui kato povecheto domashni kompyutri sa ednoprotsesorni, vuv
vseki daden moment se izvurshva
tochno edna zadacha (izpulniava se tochno 1 programa). Za da se
postigne mnogozadachnost s 1 protsesor sa
neobhodimi niakakvi algoritmi, po koito da se dava kontrol
na razlichnite protsesi, koito sa startirani - tezi algoritmi
se narichat "Algoritmi za razpredeliane na protsesornoto
vreme".
Tova koeto shte se opitam da obiasnia e kak tochno se izvurshva
tozi protses i kakuv e algorituma, po koito toi se izvurshva v
4.4BSD (Lite-2 ot 1995), Linux iadra 2.4 i 2.6.
Primerite mi shte sa bazirani na x86 arhitektura s edin
protsesor. Taka, ako imate 3 protsesa pusnati, kakto veche
kazah v daden moment se izpulniava samo edin ot tiah, tui kato
pri puskane na niakakuv protses, toi se zarezhda v pametta na
kompyutura(iztsialo ili chastichno) i se izpulniava, no estestveno
kogato ste si pusnali grafichna sreda naprimer, ne izchakvate
tia da spre, za da si pusnete niakakuv tekstov redaktor i
poradi tova, che se izpulniava samo po edin protses vuv vseki
moment se nalaga smiana mezhdu razlichnite protsesi, za da mozhe
da se suzdava ilyuziiata, che vurviat konkurentno mnogo protsesi.
Smianata mezhdu protsesite, koito se izpulniavat e silno
zavisima ot arhitekturata. Tui kato smianata mezhdu razlichnite
protsesi se pravi chesto, to e dobre da e mnogo burza
operatsiia, za da mozhe da se prekara poveche vreme v izpulnenie
na potrebitelski zadachi, ot kolkoto v iadroto.
Sega da vidim kak tazi smiana se izvurshva v BSD & Linux.
4.4BSD-Lite2 pusnat mezhdu 95-96 godina, e iadro
koeto poddurzha mnogozadachnost (tazi ilyuziia, za koiato
govoreh).
To izpolzva algoritum baziran na prioriteti, koito e
"po-dobur" kum interaktivnite programi ot kolkoto
kum programite, koito iziskvat mnogo protsesorno vreme za
izpulnenie. Algorituma dava purvonachalno visok prioritet na
vseki protses i mu dava vuzmozhnost da se izpulniava za
opredelen period ot vreme. Spored tova kolko ot vremeto si e
izrazhodval dadeniia protses - ako se e izpulniaval prez tsialoto
vreme mu se namalia prioriteta, a ako e izvurshval I/O
operatsii ili e osvobodil protsesora dobrovolno, toi si ostava
na sushtiia prioritet. Edna ot tselite na algorituma e da se
osvobodi ot iavlenieto narecheno "thrashing", koeto
oznachava smiana na mnogo protsesi za malko vreme, poradi koeto
ne ostava vreme na tezi protsesi da se izpulniavat.
V 4.4BSD ima niakolko sustoianiia na protsesite
SIDL mezhdinno sustoianie v suzdavaneto na
protsesa
SRUN protses koito mozhe da bude pusnat
SSLEEP chakasht dadeno subitie da se sluchi
SSTOP Protses koito e sprian ili
sleden
SZOMB mezhdinno sustoianie v unishtozhavaneto na
protsesa
Protsesite sa organizirani v dva lista:
1. allproc - kudeto sa vsichki protsesi, koito mogat da
budat puskani
2. zombproc - protsesi, koito sa v sustoianie SZOMB. Tova
razdeliane na protsesite namaliava znachitelno vremeto, za koeto
se preglezhdat vsichki protsesi, koito mozhe da budat
pusnati. Sushto taka ima oshte 2 grupi:
1. protsesi gotovi za izpulnenie (SRUN)
2. protsesi, koito spiat zashtoto chakat niakakvo subitie
(SSLEEP)
Prioritetite za potrebitelski protsesi v 4.4BSD varirat ot
PUSER(50) do 127. Kolkoto po maluk e prioriteta, za tolkova
po visok se smiata. Dobrovolnoto osvobozhdavane na protsesora
stava s izvikvane na sleep(), a nedobrovolnoto se izvurshva s
mi_switch() i setrunnable(). Tui kato protsesite sa s
razlichni prioriteti, to za vseki prioritet v 4.4BSD ima list
s protsesi.
Kogato se nalozhi smiana na protses tozi list se obhozhda ot
nai - visokiia do nai - niskiia prioritet i se puska purviia
nameren protses. Ako v daden list na prioritet ima poveche ot
1 protses, to protsesite v nego se puskat edin sled drug.
Vremeto, koeto e purvonachalno dadeno na vseki protses e 0.1s.
Sistemata smenia prioritetite na protsesite dinamichno, za da
mozhe da se
vuzpolzva nai - dobre ot resursite, s koito razpolaga.
Prioriteta na daden protses se opredelia s 2 promenlivi, koito
se sudurzhat v strukturata mu: p_estcpu i p_nice. p_estcpu e
kolko protsesorno vreme e
polzval skoro dadeniia protses, a p_nice e promenliva, koiato
varira mezhdu -20 i 20 (po podrazbirane e 0) i se zadava ot
potrebitelia. Prioriteta na vseki protses se preizchisliava prez
4 chasovnikovi tick-a (okolo 40 ms) po
spetsialna formula (p_usrpri = PUSER + [ p_estcpu/4 ] + 2 x
p_nice)
Ako prioriteta e po goliam ot 127, to toi se slaga na 127,
ako e po maluk ot minimalniia PUSER(50), to toi se izravniava
na tolkova. Izpolzvaneto na protsesora se izchisliava sushto po
spetsialna formula (p_estcpu = (2 x load)/(2 x load
+1) x p_estcpu + p_nice)
Tova e v nai - obshti linii kak se opredelia koi protses da e
sledvashtiia v 4.4BSD iadroto.
Sega shte obiasnia tozi protses v 2.4 i 2.6 Linux iadra.
V seriia 2.4 na linux, protsesite sa svurzani po dva nachina -
1. Kato krugov dvoino svurzan spisuk s "prev_task"
kato predniia protses i "next_task" kato sledvashtiia i
2. kato hash tablitsa, kato hash klyuch e pid-a na
dadeniia protses. Ima oshte dva spisuka s protsesi, v purviia sa
vsichki protsesi, a vtoriia , koito se kazva
"runqueue" sa protsesite, koito sa gotovi za
izpulnenie (t.e. sa v sustoianie TASK_RUNNING, shte obiasnia
sustoianiiata, po
natatuk). Tuk algorituma za razpredeliane na protsesornoto
vreme sushto izpolzva prioriteti i razdeliane na protsesornoto
vreme. Tezi prioriteti se
smeniat dinamichno spored tova, koeto se izvurshva ot dadeniia
protses. Naprimer ako imame edin
tekstovi redaktor vurviasht i edin film, redaktora shte e s po
visok prioritet, zashtoto e interaktiven protses. Vse oshte v
Linux 2.4 protses ne mozhe da bude prekusvan dokato se
izpulniava v iadroto (kakto v 4.4BSD).
Vseki protses si ima nachalen dial ot vremeto, toi mozhe da se
regulira ot nice i setpriority. "nice" se izpolzva
nai - veche da se namali prioriteta na protsesa (vupreki che se
polzva dosta riadko :), ako ima stoinost po
goliama ot 40, tia stava ravna na 40, a ako e otritsatelna
(t.e. iska da se uvelichi prioriteta na protsesa) se nalaga
protsesa da se pusne kato super potrebitel. Nachalniia dial se
izchisliava po slednata formula "20*HZ/100", kudeto
HZ e intervala na prekusvaniiata na taimer-a, koito za x86
arhitektura obiknoveno e 100 (v 2.6 e 1000).
Diala, koito se dava na protsesa e mnogo vazhen za burzinata
na tsialata
sistema, ako naprimer, za da se smeni protses se iziskvat
10-15
milisekundi i diala na protsesite e maluk, polovinata
protsesorno vreme, koeto inache mozhe da se
izrazhodva za izpulnenie na niakakuv protses, se izrazhodva
za smiana mezhdu razlichnite protsesi, drugiia variant e ako diala
e prekaleno goliam, togava
tazi ilyuziia za paralelna rabota izchezva. Sega da razgledame
sustoianiiata, koito spomenah po rano.
Tuk sustoianiiata na protsesite mogat da budat:
TASK_RUNNING - zadacha, koiato vurvi ili e godna da bude
izbrana.
TASK_INTERRUPTIBLE - zadacha, koiato spi, no mozhe da bude
subudena ot timer ili signal
TASK_UNINTERRUPTIBLE - zadacha, koiato ne mozhe da bude
subudena.
TASL_ZOMBIE - zadacha, koiato e bila spriana, no ne e
zavurshila vse oshte.
TASK_STOPPED - zadacha, koiato e spriana ot ptrace ili ot
signal.
V Linux za razlika ot 4.4BSD ima vuzmozhnost za startirane
na protsesi iziskvashti izpulnenie v realno vreme, tezi protsesi
imat opredelen srok za
tova, koeto vurshat i se razdeliat na dva vida - Hard
real-time i Soft
real-time. Kakto govoriat imenata Hard real-time NE triabva
da se
narushavat tezi srokove, a na soft sa pozvoleni malki
otkloneniia. V Linux
2.4 ima tri politiki za razpredeliane na protsesorno
vreme:
1. SCHED_FIFO
First-in, First-out real-time politika.
2. SCHED_RR
Round-robin real-time politika.
3. SCHED_OTHER
Tova e normalnata politika za vsichki ostanali
protsesi.
Pri real-time protsesite prioriteta varira mezhdu 0 i 99 i
e statichen, za razlika ot normalnite protsesi, na koito se
izchisliava dinamichno. Edna malka podrobnost, chrez
"sched_yield", mozhe da se osvobodi protsesora
dobrovolno, a protsesa, koito go izvikva se slaga
nakraia na "runqueue" (i si ostava v
"TASK_RUNNING" sustoianie). Poradi tova, che Linux
2.4 e veche ostarial kato idei, mislia, che tova e dostatuchno.
Sega shte vi zapoznaia s algoritmite za razpredeliane na
protsesornoto vreme v Linux iadro 2.6, nai - novata stabilna
seriia na Linux. Tuk naistina
iadroto e dokarano do edno dosta dobro sustoianie, zashtoto ima
dosta optimizatsii, koito sega shte razgledame.
V 2.6 otnovo I/O protsesi sa s po goliam prioritet ot tezi
izpolzvashti mnogo protsesora. Otnovo ima prioriteti i
nice stoinost, koiato mozhe da im vuzdeistva. Tuk
ima 2 prioritetni spisuka edin aktiven i edin
neaktiven. Otdelno za vseki prioritet ima spisuk s protsesi,
ako ima poveche ot 1 protses na daden prioritet se izpulniavat
edin sled drug (kakto pri BSD i Linux 2.4). Tuk ima edin
vazhen moment s dvata prioritetni spisuka, za da ne se
povtaria greshkata na Linux 2.4, koiato obhozhda vsichkite
protsesi i im preizchisliava protsesornoto vreme, tuk kogato na
daden protses mu svurshi vremeto (stane 0), to se preizchisliava
i togava protsesa se mesti v spisuka s neaktivnite protsesi,
koeto oznachava, che preizchisliavaneto na protsesite stava s
edno burzo deistvie prosto se smeniat dva ukazatelia
(na aktivniia spisuk i na neaktivniia). Nachina, po koito se
razbira dali daden protses e I/O ili izpolzva protsesora
mnogo, e da se gleda kolko vreme protsesa otdelia za
spane (sleep), ako vremeto e mnogo tova
oznachava, che protsesa e I/O, ako e malko oznachava che e taka
narechena protsesorna hrutka. Nachalnoto protsesorno
vreme e ravno na polovinata na vremeto na protsesa bashta.
Minimuma vreme, koeto mozhe da poluchi daden protses e 10 ms
(do iadro 2.6.9, ot 2.6.9 e 5 ms), normalno e 100 ms,a
maksimuma e 200 ms(otnovo do iadro 2.6.9, ot 2.6.9 e 800 ms),
koeto oznachava, che protsesa e mnogo interaktiven. Edna ot
novite i nai vazhni funktsii, koiato e implementirana v
2.6 e vuzmozhnostta za prekusvane na daden protses dokato se
izpulniava kod na iadroto (t.e. Protsesa naprimer e napravil
niakakvo sistemno izvikvane i taka izpulnenieto navliza v
iadroto). Tova e mnogo vazhno i mnogo malko Unix varianti
mogat da go praviat, obiknoveno protsesite se prekusvat samo
dokato si izpulniavat sobstveniia kod v potrebitelskoto
prostranstvo. Linux 2.6 sushto predlaga real-time algoritmi.
Te sa sushtite kato v Linux 2.4, t.e. edin, koito puska
Real-Time protsesite edin sled drug i drug, koito e First-In
First-out (ili FIFO). Real-time protsesite sa s po visok
prioritet ot normalnite protsesi, tehnite prioriteti varirat
ot 0 do 99. Mislia, che tova pokazva v suvsem malki chasti
kakvo predstavliava politikata za razpredeliane na protsesorno
vreme v tezi iadra. Estestveno po vuprosa ima oshte mnogo
informatsiia, koiato mozhe da bude kazana. Tova e suvsem malka
chast ot temata tui kato tova e osnovna tema v razrabotvaneto
na iadra i mnogo vazhna chast za predstavianeto na iadroto.
BOOKS (only in english):
Operating Systems Design and Implementation
(part 2) - Andrew Tanenbaum & Albert Woodhull (one of
the best books)
Linux Kernel Development - Robert Love (kernel
2.6)
4.4BSD Design & Implementation -
Marshal Kirk McKusick, Keith Bostic, Michael Karels & John
Quarterman
Linux Device Drivers - Alessandro Rubini &
Jonathan Corbet (kernel 2.4)
Understanding the Linux Kernel - Daniel P.
Bovet & Marco Cesatti (kernel 2.4)
NOTES:
1.Suzhaliavam ako ima problemi s prevoda (lat -> cyr),
praven e na ueb prevodach, zashtoto niamah vuzmozhnost da ia
napisha na kirilitsa. Ako ima netochnosti ili iskate poveche
informatsiia mozhete da se svurzhete s men na moiat e-mail
2. Interaktiven protses e tozi, koito si vzaimodeistva s
potrebitelia.
3.I/O Vhodno/izhoden
<< Dinamichna promiana na rabotnata chestota na AMD K7 | Adaptivnostta kato put kum sigurnostta >>
|
|