ot razor(24-06-2005)

reiting (31)   [ dobre ]  [ zle ]

Printer Friendly 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 >>