36 PREDVIDLJIVO DINAMIČNI PRINCIP RAZVRŠČANJA INFORMATICA 3/92 OPRAVIL V REALNEM ČASU Ključne besede: strogi namenski sistem, jedro OS za delo v realnem času, princip razvrščanja, časovne in logične prioritete opravil, idealna razvrstitev opravil, zaščita skupnih virov Barbara Koroušič, Peter Kolbezen Laboratorij za računalniške arhitekture Inštitut Jožef Štefan, Ljubljana Vloga operacijskih sistemov za delo v realnem času (OS) postaja pri namenskih računalniških sistemih vse pomembnejša. Programer se lahko posveti razvoju programske opreme na abstraktnem nivoju in prepusti odgovornost za upravljanje z opravili aplikacije sistemskim procesom jedra OS. V članku opisujemo takšen proces razvrščanja opravil, ki se istočasno potegujejo za vire računalnika. Podan je opis in analiza dinamičnega principa razvrščanja, ki dodeljuje prednost tistim opravilom, ki so za aplikacijo pomembnejša. Hkrati upošteva tudi časovno omejenost opravil in zagotavlja njihovo pravočasno izvršitev. Princip smo poimenovali predvidljivo dinamični, ker predvideva zavrnitev opravil takoj ob prihodu zahtev za njihovo izvajanje. 0 zavrnitvi govorimo, ko nabor pripravljenih opravil na procesorsko izvajanje ne omogoča pravočasne izvršitve opravila. Zavrnjeno opravilo lahko preusmerimo v drugo procesorsko vozlišče, če je namenski računalnik porazdeljeni ali večprocesorski sistem. Pomembna je čimprejšnja zavrnitev, tako da ima opravilo še dovolj časa za izvršitev vseh potrebnih operacij. PREDICTABLE DYNAMIC TASK SCHEDULING IN HARD REAL-TIME - The essential feature of hard real-time systems is that the embedded computer must deliver its results correctly and on-time - otherwise malfunction may result. To assure software constructions of such systems a support of a real-time operating system is needed. We present a task scheduling and mutual exclusion protocol as one of real-time operating system structuring mechanisms. The protocol is applicable to aperiodic tasks having specific priority and timing characteristics. 1. Uvod Računalniški sistem, ki je prilagojen okolju, v katerem izvaja nadzor, imenujemo namenski ali vloženi (embedded) sistem. Njegova osnovna naloga je spremljanje zunanjih dogodkov in odločanje o nadaljnem dogajanju v okolju. Ker je spreminjanje stanja v okolju dinamično in pogosto tudi nepredvidljivo, mora namenski računalnik delovati ped pogoji realnega časa: 1. Odločitve morajo biti logično in časovno pravilne. 2. Sistem mora delovati varno tudi ob pojavitvi morebitnih napak. Namenske računalnike delimo glede na stopnjo upoštevanja zahtev realnega časa na stroge (liard) in mehke (soft) sisteme [1], Potniško letalo A-320 [2] je primer sistema, ki je pod nadzorom strogega namenskega računalnika. Po obsegu okolja, nad katerim ima računalnik nadzor, so verjetno največji namenski sistemi v elektrarnah, kemijsko predelovalni industriji ali v upravljanju prometa. Manjši namenski sistemi so mobilni roboti, ki jih uporabljajo za opravljanje težaških, monotonih ali nevarnih opravil [3]. Razvoj programske opreme namenskih sistemov je bil do nedavnega prepuščen izkušenim programerjem, ki so imeli bogato znanje o strojni opremi sistema. Dandanes pa poznamo že vrsto • operacijskih sistemov (npr. VRTX32, FlexOS • visokonivojskih programskih jezikov (npr. Ada [5], Modula-2 [6], Real-Time Euclid [7]), • ČASE (Computer Aided Software Engineering) orodij (npr. VRTXdesigner [8]), ki so prilagojeni zahtevani realnega časa. Uporaba tovrstnih orodij poenostavi oblikovanje namenskih sistemov in hkrati zagotavlja večjo učinkovitost razvite kode. Uporaba CASE orodij vodi pblikovanje programske opreme iz definicije problema. Podatkovne in nadzorne strukture visokonivojskih jezikov za programiranje pod pogoji realnega časa omogoča jo razbitje problema na abstraktnem nivoju. Sistemske funkcije jedra OS (real-time kernel) pa prevzamejo odgovornost za upravljanje z opravili, ki predstavljajo osnovne abstraktne enote programske aplikacije. Eden najpomembnejših sistemskih procesov jedra je razvrščanje sočasnih opravil aplikacije računalniškega sistema. Dogodki v okolju namreč lahko zahtevajo sočasen odziv sistema, ne glede na vrstni red prihoda zahtev za izvajanje opravil. Naloga razvrščevalnika je spremljanje dogodkov v okolju in odločanje o vrstnem redu izvajanja prebujenih opravil, saj večina namenskih računalnikov ne omogoča istočasnega izvajanja vseh zahtevanih opravil. Princip razvrščanja (scheduling policy) je pogojen z aplikacijo. V preprostih aplikacijah, kjer je celotno dogajanje v sistemu predvidljivo, so zelo učinkoviti statični principi, ki določajo vrstni red izvajanja opravil z upoštevanjem statičnih (nespremenljivih) lastnosti opravil. Večina namenskih aplikacij pa mora upoštevati dinamično spreminjanje lastnosti opravil. Takoimenovani dinamični principi razvrščanja določajo zaporedje izvajanja prebujenih opravil med samim izvajanjem aplikacije. Razvrščevalnik lahko teži k idealnem (feasible) ali optimalnem razvrščanju opravil. V prvem primeru je razvrstitev pripravljenih opravil čakajočih na procesor določena tako, da nobeno opravilo ne more preseči vnaprej določene časovne omejitve (deadline). Pri optimalni razvrstitvi pa so dovoljene minimalne zakasnitve. V nadaljevanju bomo predstavili predvidljivo dinamični princip razvrščanja, ki določa prioritete prebujenih opravil z upoštevanjem njihove časovne omejenosti ter stopnje pomembnosti za celotno aplikacijo. Časovna omejenost in pomembnost opravil sta namreč kriterija, ki se lahko medsebojno izključujeta. Opravilo, ki je časovno kritično, ima lahko nizko stopnjo pomembnosti za aplikacijo in obratno. Princip teži k idealnem razvrščanju opravil. 2. Opis PD principa razvrščanja opravil PD princip razvrščanja opravil temelji na sledečih predpostavkah: 1. Stanje namenskega sistema se lahko spreminja tudi asinhrono. 2. Odziv na dogodke je časovno omejen. 3. Opravila aplikacije so različno pomembna za delovanje sistema. 4. Dovoljeno je prekinjanje izvajanja opravil. 5. Dostop do skupnih virov je zaščiten. 6. Izvajanje namenske aplikacije mora biti robustno. 1. Dogodki, ki sprožijo izvajanje opravil v računalniškem sistemu, se pojavljajo sinhrono ali asinhrono. Trenutek, v katerem sproži asinhroni dogodek izvajanje opravila, ni znan pred zagonom aplikacije. Asinhroni dogodki lahko sprožijo izvajanje periodičnih ali aperiodičnih opravil. 2. Dogodki v sistemu zahtevajo pravočasen odziv. Vsako opravilo je časovno omejeno. Če računalniški sistem ne more zagotoviti odziva v predvidenem (odzivnem) času, je opravilo zavrnjeno. 3. Prednost pri izvajanju imajo opravila, ki so bolj pomembna za aplikacijo. Če procesor ni zmožen pravočasno izvesti vseh prebujenih opravil, razvrščevalnik zavrne najprej opravila z najmanjšo stopnjo pomembnosti. 4. Ker so dogodki večinoma asinhroni in opravila časovno omejena, mora princip podpirati prekinjanje opravil. Časovne lastnosti opravil se dinamično spreminjajo in tako se tudi prednost opravil pri dostopu do procesorja spreminja s časom izvajanja aplikacije. Prekinjanje izvajanja opravil je dovoljeno, če je prioriteta prebujenega opravila višja od prioritete opravila, ki se trenutno izvaja. 5. Opravila lahko zahtevajo dostop do skupnih virov. Metoda medsebojnega izključevanja (mutual exclusion) z uporabo monitorja, zagotavlja zaščito skupnih virov [9]. Ker pa smo želeli zadostiti tudi zahtevi po možnosti prekinjanja opravil, smo princip monitorja razširili in ga priredili za uporabo v 38 strogih namenskih sistemih. Podrobnejši opis sledi v poglavju 2.1. 6. Robustnost izvajanja namenskih aplikacij smo želeli zagotoviti posredno s principom razvrščanja. Opravilo, ki poruši idealno razvrstitev prebujenih opravil, je zavrnjeno že ob prihodu' dogodka, ki je sprožil izvajanje opravila. Če je namenski sistem večprocesorski, se lahko opravilo preusmeri v drugo procesorsko vozlišče. Zato je zelo pomembno, da je zavrnitev objavljena, ko ima opravilo še dovolj časa, da opravi vse operacije. Upoštevali smo tudi morebitne napake pri izračunu operacij opravil. Če ima opravilo še dovolj časa, lahko ob pojavitvi napake ponovi niz operacij z alternativnimi procedurami (razširjeni mehanizem okrevanja po napaki (recovery block programming) [1]). Rezultati matematične in simulacijske analize, ki sta jih objavila Craig in Woodside [10], kažejo na učinkovitost dinamičnega principa prednosti časovno kritičnih opravil (Earliest Deadline /ls Soon As Possible) [1]. Princip dodeljuje prednost opravilom, ki so časovno bolj kritična. Ker princip ne upošteva pomembnosti opravil za aplikacijo, smo vgradili dodaten mehanizem „izločanja" manj pomembnih opravil v primeru nasičenja v vrsti pripravljenih opravil (ready queue). To je programska struktura, ki hrani zahteve za izvajanje prebujenih opravil v vrstnem redu, kot ga določa razvrščevalnik. Ob prihodu nove zahteve za izvajanje opravila rn razvrščevalnik preveri pogoj: k (TDk n n, saj je pri nižjih vrednostih indeksa zanesljivo izpolnjen. Če je pogoj izpolnjen, poteka razvrščanje opravil po principu prednosti časovno kritičnih opravil. t- Ti 1 h 1 Tn ti ■ Ti t i r« j Tm t T°- Slika. 1: Časovne lastnosti in urejenost opravil Prednost pri dostopu do procesorja ima opravilo, ki je časovno najbolj omejeno. V nasprotnem primeru pa se vključi mehanizem za "izločanje,, manj pomembnih opravil. Recimo, da pogoj ni izpolnjen pri vrednosti indeksa k = j, n < j < m. Potem razvrščevalnik izloči iz vrste opravilo, katerega stopnja pomembnosti je najmanjša v podmnožici prebujenih opravil {Ti,T2, ...Tj} ter ponovno preveri pogoj pri vrednosti indeksa k > j. Biyabani in Stankovic [11] sta dokazala, da je princip izločanja najmanj pomembnih opravil najbolj učinkovit. Druga možnost je izločanje opravil, katerih časovna prioriteta je najmanjša in hkrati stopnja pomembnosti ne preseže stopnje pomembnosti opravila rn. V primerjavi s prvo možnostjo, ki smo jo označili kot najbolj učinkovito, je slednja časovno manj potratna. Postopek izločanja opravil se ponavlja, dokler pogoju (1) ni zadoščeno. Ker so predvideni časi izvajanja opravil določeni za „najslabši" (najdaljši) primer, razvrščevalnik dejansko ne izloči opravil iz vrste prebujenih opravil, temveč jih prestavi na konec vrste in obvesti sistem o predvideni zakasnitvi odziva na dogodke, ki so sprožili zahteve za izvajanje teh opravil. Sistem lahko zahteva dejansko izločitev teh opravil iz vrste pripravljenih opravil. Če je dejanski čas izvajanja opravila krajši od predvidenega, razvrščevalnik ponovno preveri pogoj (1) po zaključenem izvajanju opravila. Če je pogoju (1) zadoščeno, je zagotovljeno idealno razvrščanje opravil, četudi je procesor 100 % 39 zaseden: Em rrt i u= TDm Tn (2) saj je časovna meja Tom zmeraj manjša ocl časa t in velja: lim 1 - — m—► oo Tn L/n i. (3) 2.1 Mehanizem za zaščito skupnih virov Pri opisu zahtev smo omenili, da monitor, kot mehanizem za zaščito skupnih virov, ne zagotavlja pravočasnega izvajanja namenskih aplikacij v realnem času, ker ne dopušča prekinjanja izvajanja opravil v kritičnih področjih [12]. Izogniti se moramo tudi težavam, ki nastopijo ob blokiranju (časovno in logično) pomembnih opravil, zaradi zasedenosti kritičnih področij z manj pomembnimi opravili: • verižno blokiranje (chained blocking) izvajanja opravil, • problem mrtve zanke (deadlock). Opravilo je blokirano, kadar čaka na nadaljevanje izvajanja operacij zaradi zasedenosti zahtevanega vira z manj pomembnim opravilom. Težave nastopijo, ko opravilo zahteva vstop v več kritičnih področij, ki so zasedene z manj pomembnimi opravili (verižno blokiranje). Kot primer podajmo situacijo, ko opravilo tq vstopi v kritično področje. Opravilo tb, ki je bolj pomembno, prekine izvajanje opravila tq ter vstopi v drugo kritično področje. Opravilo Tji, ki je še bolj pomembno, prekine izvajanje opravila tb• Ce zahteva opravilo r^ vstop v obe kritični področji, se njegovo izvajanje blokira, ker sta področji zasedeni z opravili tq in rg. Problemu mrtve zanke pri potegovanju za skupni vir se lahko izognemo z uporabo semaforjev [9]. Mrtva zanka pa se lahko pojavi tudi po vstopu opravil v kritična področja, ko opravila navzkrižno zahtevajo dostop do skupnih virov, ki so že zasedeni. Princip monitorja temelji na uporabi semaforjev za zaščito kritičnih področij in signalov za sporazumevanje z opravili, ki zahtevajo uporabo skupnih virov [9]. Princip razširimo z dodatnim mehanizmom, ki omogoča varno prekinjanje izvajanja opravil v kritičnih področjih [12]. Poleg osnovnih lastnosti opravil, ki jih mora določiti programer pred zagonom aplikacije, zahteva mehanizem seznam semaforjev, katere mora opravilo upoštevati pred vstopom v kritična področja. Vsakemu kritičnemu področju določimo prioriteto, ki se med izvajanjem aplikacije dinamično spreminja. Prioriteta kritičnega področja je enaka najvišji prioriteti prebujenega opravila, ki lahko zahteva vstop v to kritično področje. Mehanizem za varno prekinjanje izvajanja opravil v kritičnih področjih razdelimo v dva dela. Prvi del omogoča, dinamično določanje prioritet opravil v kritičnih področjih. Opravilo, ki ima trenutno dostop do skupnega vira, lahko blokira izvajanje višje prioritetnih opravil. V takšnem primeru prevzame opravilo v kritičnem področju najvišjo prioriteto blokiranih opravil. Ko izstopi iz kritičnega področja, dobi ponovno "originalno,, prioriteto. Drugi del upravlja s kritičnimi področji. Opravilo, ki zahteva ključ za vstop v kritično področje, mora ustrezati pogoju, da je njegova prioriteta višja od vseh prioritet trenutno zasedenih kritičnih področij. Sicer razvrščevalnik blokira izvajanje opravila in čaka na vstop v zasedeno področje. Opišimo dva možna načina blokiranja opravil, ki zahtevajo dostop do skupnih virov: 1. Opravilo t zahteva, ključ za vstop v kritično področje S, vendar ga ne dobi; ker je njegova prioriteta nižja, ali enaka najvišji prioriteti zasedenih področij, Sh- Opravilo r je blokirano, dokler se področje Sh ne sprosti, opravilo v Sh pa prevzame prioriteto opravila r, če je njegova prioriteta nižja. 2. Opravilo r je blokirano, ker zahteva vstop v področje S in ima prioriteto nižjo ali enako najvišji prioriteti zasedenih področij, Sh- Če je opravilo v področju Sh že prevzelo višjo prioriteto od predhodnje blokiranega opravila, potem ostane njegova prioriteta nespremenjena. Dokaz, da mehanizem onemogoča verižno blokiranje izvajanja opravil, temelji na sledečih lemah [12]- 40 LEMA 1: Če opravilo t blokira izvajanje višje prioritetnega opravila Th, potem t zaseda vsaj eno kritično področje S s prioriteto višjo ali enako prioriteti t^ v času prihoda opravila r^ (t). Dokaz: Predpostavimo, da je najvišja prioriteta kritičnih področij, ki jih zaseda r v času i, prioriteta področja S h■ Če je ta prioriteta nižja od prioritete opravila r^, potem lahko opravilo r prevzame le prioriteto, nižjo od prioritete opravila r^. Drugače rečeno, dokler je opravilo r^ aktivno (prebujeno), opravilo t ne bo razvrščeno tako, da bi blokiralo r^. Torej obstaja vsaj eno področje, ki ga zaseda r, s prioriteto večjo ali enako prioriteti r^, v času t ALEMA 2: V vsakem trenutku t obstaja največ eno kritično področje s prioriteto višjo ali enako P, ki ga zaseda opravilo z „originalno" prioriteto nižjo od P. Dokaz: Predpostavimo, da lema ne velja. V času t sta področji 5,- in S j zasedeni in imata obe prioriteto višjo ali enako P. Dodatno predpostavimo, da je najprej opravilo rp zasedlo področje S, v času tp in nato opravilo rq področje S j v času tq. Prioriteti opravil tp in rq sta nižji od P. Upoštevajoč princip našega mehanizma mora biti prioriteta opravila rq višja od prioritete kateregakoli zasedenega področja v času tq. Ker pa zahtevamo, da je prioriteta opravila rq zmeraj nižja od P in prioriteta področja S{ višja ali enaka P, pridemo v nasprotje 4k- S pomočjo lem smo dokazali, da lahko opravilo r blokirajo le opravila z nižjimi prioritetami, ki zasedajo področja, katerih prioritete so višje ali enake prioriteti opravila r (LEMA 1). V času prihoda opravila r je zasedeno največ eno kritično področje s prioriteto višjo od prioritete r, ki ga zaseda opravilo z nižjo prioriteto (LEMA 2). Tako smo dokazali, da lahko opravilo r blokira največ eno opravilo z nižjo prioriteto in pogoj za verižno blokiranje nikoli ni izpolnjen. Pri izboru mehanizma za varno prekinjanje izvajanja opravil v kritičnih področjih, smo se želeli izogniti tudi mrtvim zankam. Pogoj za mrtvo zanko je navzkrižno čakanje opravil, ki zasedajo kritična področja, medtem ko čakajo na semaforje področij, ki jih zasedajo ostala opravila, sodelujoča v zanki. Predpostavimo, da obstaja mrtva zanka in ima opravilo r najvišjo prioriteto med opravili v zanki. t zaseda področje medtem, ko čaka na semafor področja, ki je zasedeno z drugim (nižje prioritetnim) opravilom iz zanke. Dokažemo pa lahko, da opravilo, ki zaseda področje, ne more biti blokirano z nobenim nižje prioritetnim opravilom [12] (LEMA 3). Tako pogoj za pojavitev mrtve zanke ne more biti izpolnjen. LEMA 3: Opravilo je lahko blokirano le pred vstopom v prvo kritično področje. Dokaz: Ko opravilo r vstopi v prvo kritično področje v času t, ima najvišjo prioriteto med prebujenimi opravili. Ostala zasedena področja, ki jih zasedajo nižje prioritetna opravila v času t, označimo z množico 5'. Prioriteta opravila t je zagotovo višja od prioritet področij iz S. Predpostavimo, da. bo izvajanje opravila r blokirano v času 11, t\ > t, ko se bo začelo izvajati opravilo z nižjo prioriteto r/. Opravilo r/ bo začasno prevzelo prioriteto od opravila r. Upoštevajoč princip mehanizma lahko opravilo r/ zaklene področje S k, če je prioriteta opravila r nižja ali enaka prioriteti 5fc. Ker nobeno opravilo ni bilo razvrščeno v času med t in t\,je množica zasedenih področij v času ii enaka S in Sk € S. Tako pridemo v nasprotje, saj nobeno področje iz S nima prioritete višje ali enake od prioritete opravila r Razvrščevalnik mora preveriti pred vstopom opravila v kritično področje, ali je njegova prioriteta višja od najvišje prioritete zasedenih področij. Ker pa smo v zgornji lemi dokazali, da je opravilo lahko blokirano le pred vstopom v prvo kritično področje, moramo preveriti pogoj le pred vstopom v prvo področje. Nadaljne zahteve za dostop do skupnih virov izvaja razvrščevalnik brez preverjanja pogoja, ali je prioriteta opravila višja od najvišje prioritete zasedenih področij. Predstavljeni mehanizem za zaščito skupnih virov opravil vpliva na potek izvajanja opravil. Blokiranje izvajanja opravil zaradi zasedenosti kritičnih področij vpliva na odzivni čas, kar moramo upoštevati pri preverjanju pogoja o idealni razvrstitvi prebujenih opravil. V pogoj (1) vpeljemo dodatni parameter Bk- k (rD*-($]TCi + £fe))><, 1<* 1, pri čemer sta Td1 in Tcl časovna parametra opravila r2. Najdaljši možni čas blokiranja opravila r2 B\ = 0.5. To je čas zasedenosti področja S3, do katerega ima dostop tudi nižje prioritetno opravilo r3. Ker je pogoju zadoščeno, preverimo pogoj pri vrednosti indeksa k = 2: 2 Td2 ~ (]TTc, + B2) = 8 - (2.5 + 2 + 0) > 1. ¿=1 Vrednost indeksa 2 označuje lastnosti opravila 73 in 1 lastnosti r2. Opravilo 73 ima nižjo prioriteto, zato njegovega izvajanja ne more blokirati r2 (Bi = 0). V času t = 3 se pojavi nova zahteva za izvajanje opravila tx. RQ = ,-r2,t3], p(n) = 1, v{T2) = 2 in p(r3) = 3, c{S\) = c(S2) = Mri) = 1 in c(^3) = p(r2) = 2. Pogoju (4) ni zadoščeno pri vrednosti indeksa k = 3: TDl ~ {Tci + -Bi) = 6 - (2 + 0.5) > 3, 2 TD2 - (J2TC\ + B2) = 7- (2.+ 1 + 0.5) > 3, ¿=1 3 TD3 - (£ Tc, + B3) = 8 - (2 + 1 + 2.5 + 0) < 3, 1=1 zato je potrebno izločanje manj kritičnih opravil iz nabora prebujenih opravil {ri,r2,r3}. Vrednost indeksa i = 1 označuje parametre opravila T\, i = 2 opravila r2 in i — 3 opravila r3. B1 = 0.5, ker lahko izvajanje opravila T\ blokira r2 v 5i za 0.5 časovne enote. B2 = 0.5, ker lahko izvajanje opravila r2 blokira r3 v 53 za 0.5 časovne enote. Slika 2 natančno prikazuje potek izvajanja opravil. V času t = 1 prekine r2 izvajanje opravila r3. Ker se nahaja r3 v kritičnem področju 52 in r2 ne zahteva dostop do skupnega področja, se izvajanje r3 v S2 nadaljuje. Ko zahteva opravilo r2 v času t = 1.5 ključ za vstop v S3, ga dobi, ker ni zasedeno nobeno področje. Opravilo r2 se ob prihodu zahteve za izvajanje T\ nahaja v področju S\. Ker je c(£i) = p(ti) in p(rx) > p(r2), blokira opravilo r2 izvajanje T\ in prevzame do izstopa iz ,S'i prioriteto 1. 42 ces). Prav tako so določeni tudi strežni in čakalni časi opravil z eksponentno porazdelitvijo. Hitrost prihoda zahtev je podana s parametrom A, srednja vrednost dolžine strežnih časov z p. ter čakalnih časov z 7. Opravilo zapusti sistem, ko opravi vse zahtevane operacije. Verjetnost, da je opravilo prekinjeno in se mora vrniti v čakalno vrsto pripravljenih opravil je določena s parametrom (1-a). Slika 2: Primer PD razvrščanja 3. Primerjava PD principa z dinamičnimi principi razvrščanja Osnovo PD principa razvrščanja predstavljata princip prednosti časovno kritičnih opravil (ED) in princip kritičnih opravil (Priority Scheduling -PS). Slednji dodeli prednost pri dostopu do procesorja opravilu, ki ima tisti trenutek najvišjo stopnjo pomembnosti v vrsti pripravljenih opravil. Stopnjo pomembnosti določi programer subjektivno in se le ta med izvajanjem aplikacije ne spreminja [1]. Pri snovanju PD principa razvrščanja smo težili k odpravi pomankljivosti ED in PS pristopov. Seveda pa smo želeli ohraniti tudi vse dobre lastnosti. V nadaljevanju bomo podali primerjalno analizo, ki je sestavljena iz dveh delov, matematičnega in simulacijskega. Matematični model je zahtevnejši za izpeljavo, vendar podaja zanesljive rezultate, ki temeljijo na primerjavi lastnosti posameznih principov pod enakimi pogoji. S pomočjo simulacije pa lahko preverimo rezultate matematične analize brez upoštevanja predpostavk, katere običajno uvedemo zaradi lažje izpeljave zahtevnega matematičnega modela. <1 -o) Slika 3: Sistem z vrsto Izhodni parametri našega matematičnega modela so naslednji: 1. Izkoriščenost procesorja. 2. Verjetnost zavrnitve opravil. 3. Lastnosti zavrnjenih opravil: • Preostali strežni čas. • Preostali čakalni čas. 1. Izkoriščenost procesorja (U = p) izračunamo s pomočjo dveh podatkov, povprečnega strežnega časa E(Tc) ter povprečnega časa W, ki ga opravilo preživi v sistemu [1]: E(TC) W ' (5) Če upoštevamo, da so strežni in čakalni časi porazdeljeni eksponencialno: 3.1 Matematični model PD principa Namenski računalniški sistem lahko predstavimo kot matematični model iz teorije vrst (slika 3). Okolje pošilja asinhrone zahteve za izvajanje opravil, ki se kopičijo v vrsti pripravljenih opravil. Zahteve so časovno neodvisne in časi med prihodi opravil so eksponentno porazdeljeni (Markov pro- g(x) = l(x) = potem sledi izpeljava: fie fe~ (6) C(t) = [ xg{x) f l(y)dydx, Jo Jo H (t) = f g{x) f X l{y)dydx, (7) Jo Jo 43 W'{t) = Porazdelitev preostalega čakalnega Čaaa 2(1 - XC(t))2 ( / x2g(x) / l(y)dydx + J o ./o f x2g{x)[l-H{x)]dx), (8) Jo ^ = r^r^ 11 = (9) W(t) = W'(t) + W"{t). (10) W(t) je povprečni odzivni čas opravila, katerega predvideni odzivni čas je enak t. Povprečni čas opravila s poljubnim predvidenim odzivnim časom izračunamo s približkom vrednosti t s srednjo vrednostjo E{t): m= f Jo t h{t)dt. (11) 2. - 3. Podrobnejši opis analize verjetnosti zavrnitve opravil ter njihovih lastnosti smo podali v prispevku [13] ter v nalogi [1]. Zato podajmo na tem mestu le grafično primerjavo rezultatov analize dinamičnih principov razvrščanja (graf 1, 2, 3). 16 14 12 10 8 e 4 2 0 Verjetnost zavrnitve (%) — * EDtlm O PDalm -ED -PD I-- j 1 ^^ □ i a ° ■.....—* □ o * * * ^^ a . 5 10 15 Procesorska izkoriščenost (%) 20 Graf 2: Porazdelitev preostalih čakalnih časov zavrnjenih opravil o.a Porazdelitev preostalega strežnega Esbs 0.4 0.2 - ED - PD 1 2 3 y Graf 3: Porazdelitev preostalih strežnih časov zavrnjenih opravil trenutku potegujeta za procesor največ dve opravili. Ker pa je procesorska izkoriščenost v strogih namenskih računalnikih nizka (največ 10 % [14]) in upoštevamo Markov proces prihoda zahtev za izvajanje opravil, rezultati analize ne odstopajo močno od dejanskih. To smo tudi potrdili s simulacijo, ki temelji na bolj realnih pogojih. Graf 1: Verjetnost zavrnitve opravil 3.2 Simulacijslci model PD principa Pri analizi matematičnega modela smo privzeli zelo močno predpostavko, da se lahko v določenem Program, ki omogoča simulacijo principov razvrščanja opravil, smo razvili v programskem jezi- 44 ku SimScript II.5 za PC kompatibilni računalnik. Uporabnik lahko spreminja sledeče parametre simulacij: • razvrščevalni princip, • dolžino simulacij in • časovne parametre opravil (slika 4). M i"f° Input J fln inatIon M R»n fc Results J Quit | Simulation Parameters □ Scheduling Policy ttcan of lnterarriual lines .1881 Response Tines 0 tlean of Conputation Tines .18B| Sinple Round Robin Predictable Dynanlc o tlean of Laxities ftean of Context Sultching Tines 1 •BSB1 1 -«I Predictable Dynanic Length or Tine Slice Hunter of Rejected Tasks hunbcr of Simulations )1B8B{ □3 pJeTauU^l I^Sav^^ fČ^ri Slika 4: Vhodni simulacijski parametri ter spremlja rezultate: • verjetnost zavrnitve opravil pri določeni procesorski izkoriščenosti (graf 1), • lastnosti zavrnjenih opravil (graf 4), • uteženo verjetnost pravočasne izvršitve opravil (graf 5). Mero utežene verjetnosti izvršitve opravil smo izračunali s pomočjo funkcije: WGR c, = 100 I {tL,} I) £,•(«• I D ' = e'"1. (12) Množica {TgXe} vsebuje opravila s stopnjo pomembnosti i, ki so se pravočasno izvršila in {t^} vsa prebujena opravila z ¿-to stopnjo pomembnosti za aplikacijo. Nižja vrednost indeksa i pomeni višjo stopnjo pomembnosti opravila. BTTnTcT ^ Input B flnination B Pun J Results B Quit | Rejected Tasks 1 - nost critiCAl tasks IB - less critical tasks (e.g.. 5C3B*) neans that 38* or .tasks uith criticalness 5 uere rejected) Graf 4: Lastnosti zavrnjenih opravil 100 99.5 98.5 98 97.5 97 Verjetnost Izvršitve (*) — ! \ i \ s^......—-V---- k -ED« Im -POalm 1 5 10____15 Procesorska izkoriščenost (%) 20 Graf 5: Utežena verjetnost izvršitve opravil 0.T a °-< b i 1 0.3 i t y • 1 II FCFJ^^ -.-- .... , , - - V / • / Jy /\ / too 1 1 > 1 0.20.40.60.81 :.2 :.( !.S ! ratio 7/p Graf 6: Verjetnost zavrnitve opravil 45 4. Zaključek Predvidljivo dinamični princip razvrščanja opravil, na katerem temelji jedro OS za delo v strogem realnem času, upošteva zahteve realnega časa. To pomeni, da obravnava zahteve za izvajanje aperio-dičnih opravil, ki so časovno in logično različno zahtevna za programsko aplikacijo. V primerjavi z ostalimi dinamičnimi principi razvrščanja opravil (graf 6 [10]) lahko povzamemo sledeče zaključke: 1. Princip PD zagotavlja pri določeni procesorski izkoriščenosti večjo verjetnost zavrnitve manj pomembnih opravil. 2. Verjetnost zavrnitve opravil z visoko stopnjo pomembnosti za aplikacijo je manjša. 3. Ker princip temelji na predvidljivosti, so lastnosti zavrnjenih opravil ugodnejše. Razvrščevalnik lahko preusmeri opravilo v drugo procesorsko vozlišče porazdeljenega ali večprocesorskega namenskega sistema, če je preostali čakalni čas še dovolj velik. Področje večprocesorskih in porazdeljenih namenskih sistemov odpira nove težave, s katerimi se je potrebno soočiti. Naše nadaljne delo bo usmerjeno v raziskavo topologij namenskih sistemov s porazdeljenimi vhodno-izhodnimi napravami, ki omogočajo hitro in zanesljivo zaznavanje zunanjih dogodkov ter komunikacijo med opravili. Literatura [1] B. Koroušic. Jedro operacijskega sistema za delo v strogem realnem času (magistrska naloga). Univerza v Ljubljani, Fakulteta za elektrotehniko in računalništvo, april 1992. [2] M. Thaler. Nova tehnologija v pilotski kabini. KRILA, page 28, maj 1989. [3] L.S. McTamaney. Real-time intelligent control. IEEE Expert, 2(4):55-68, 1987. ■ [4] Operating systems in real time. .EXE Magazine, 4(7):72-77, 1989. [5] W.A. Halang. Evaluation of ada from the viewpoint of control engineering. IEEE, pages 8-13, 1986. [6] A. Brodnik in M. Spegel in T. Lasbaher. Programiranje z modulo-2. Informatica, Ljubljana, (2):78-82, 1987. [7] E. Kligerman in À.D. Stoyenko. Real-time euclid: A language for reliable real-time systems. IEEE Transactions on Softtvare Engineering, 12(9):941-949, September 1986. [8] Real-time software. Micro Technology, december 1991. [9] J.E. Cooling. Software Design for Real-Time Systems. Chapman and Hall, 1990. ISBN 0-412-341- • 808. [10] D.W. Craig in C.M. Woodside. The rejection rate for tasks with random arrivais, deadlines, and preemptive scheduling. IEEE Transactions on Software Engineering, 16( 10), oktober 1990. . [11] J. A. Stankovic. Misconceptions about real-time computing. COMPUTER, .21 ( 10): 10—19, oktober 1988.' [12] M.I. Chen in K.J. Lin. Dynamic priority ceilings: A concurrency control protocol for real-time systems. Real-Time Systems - The international journal of time-critical computing systems, 2(4):325-345, november 1990. [13] B. Korousic in J.E. Cooling in P. Kolbezen. Predictable hard real-time scheduling. In Proceedings of the 4th EUROMICRO Workshop on Real-Time, junij 1992. [14] C.J. Paul in A. Acharya in B. Black in J.K. Stros-nider. Reducing problem-solving variance to improve predictability. COMMUNICATIONS OF THE ACM, pages 81-93, avgust 1991.