RTOS za ARM7 Janez Puhan Univerza v Ljubljani, Fakulteta za elektrotehniko, Tržaška 25, 1000 Ljubljana, Slovenija E-pošta: janez.puhan@fe.uni-lj.si Povzetek. Predstavljen je predkupni operacijski sistem, ki tece v realnem casu. Prirejen je za mikrokrmilnike s procesnim jedrom ARM7. Izvorna koda za druZino mikrokrmilnikov LPC123x je dostopna na svetovnem spletu [1]. Posamezne sklope operacijskega sistema, kot so npr. razvrščanje procesov, dinamično dodeljevanje pomnilnika in binarni semaforji, smo implementirali na preprost in modularen nacin. Odlocili smo se za prioriteten algoritem razvrsšcšanja procesov, kar procesu z najvisšjo prioriteto zagotavlja trdo realno cšasovno razvršcanje. Poudarjeni so primeri, ki povzrocijo smrtni objem. Za dinamicno dodeljevanje pomnilnika smo uporabili algoritem prvega primernega prostora, dodeljen pomnilnik pa se nahaja v urejenem povezanem seznamu. Razvršcevalnik procesov je prozen s prekinitvijo casovnika timerO, medtem ko so sistemski klici izvedeni s programsko prekinitvijo. Nesistemske prekinitve programska oprema prestreze. Obdelane so lahko v okviru operacijskega sistema ali mimo njega. Izmerjene lastnosti sistema podajamo za mikrokrmilnik LPC2138. Ključne besede: operacijski sistemi v realnem casu, razvršcanje procesov, vgrajeni sistemi RTOS for ARM7 The paper presents a new preemptive real-time operating system for the ARM7 core. The source code for the LPC213x processors with the ARM7TDMI-S core is available [1]. The required mechanisms, such as process handling, dynamic-memory management and binary semaphores, are implemented both in a simple and modular manner. The developed scheduling algorithm is priority-based to ensure hard real-time scheduling of the highest-priority process. Deadlock situations are pointed out. The first-fit dynamic-memory management algorithm is used. The memory allocations are organized in an ordered linked list. To invoke the scheduler timerO, an interrupt request is used, while the system calls are performed by the software interrupt exceptions. The non-system exceptions are caught and can be handled by or without the system. The system properties are measured on the Lpc2138 processor. 1 Uvod Programska oprema za mikrokrmilniške vgrajene sisteme je napisana na različne nacine. Najpogostejše programske arhitekture so: izvajanje nalog v neskoncni zanki, servisiranje s prekinitvami prozenih dogodkov, razporejanje procesorskega casa med opravili s pomocjo operacijskega sistema ali kombinacija med njimi. Potreba po uporabi operacijskega sistema se pokaže ob vecjem številu nalog, ki jih opravlja mikrokrmilniški sistem. Programska oprema postane obsezna, zapletena in posledicno neobvladljiva. Operacijski sistem omogoci navidezno socasnost izvajanja nalog (ang. time sharing) za ceno lastne rezije. Operacijski sistemi na vgrajenih sistemih morajo zaradi svoje interakcije z okoljem navadno teci v realnem casu. Za vgrajene sisteme je Prejet 17. junij, 2014 Odobren 30. september, 2014 na voljo vec operacijskih sistemov v realnem casu, kot npr. FreeRTOS [2], ThreadX [3] ipd., ki navadno želijo zadostiti vsem željam uporabnikov. Tako tecejo na množici različnih mikrokrmilnikov, ponujajo različne politike razvršcanja, sheme dinamicnega dodeljevanja pomnilnika, sinhronizacije med procesi ipd. Splošnost je sicer dobrodošla, a lahko postane nepregledna. V clanku predstavljamo nov prioritetni predkupni operacijski sistem v realnem casu. Napisali smo minimalen operacijski sistem, ki omogoca prioritetno predkupnost poljubnega števila dinamicno ustvarjenih koncnih ali neskoncnih procesov. Sistem smo implementirali za 32-bitne mikrokrmilnike druzine LPC213x [4] s procesnim jedrom ARM7TDMI-S [5]. 2 Datoteke z izvorno kodo operacijskega sistema Izvorna koda jedra operacijskega sistema [1] je v datotekah s predpono os. Jedro obsega razvršcevalnik procesov s funkcijami sistemskih klicev. Del jedra je tudi datoteka exceptions.s, ki prestreze izjeme* (ang. exception) [6]. Procesno jedro ARM7TDMI-S pozna vec vrst izjem s pripadajocimi vektorji in nacini delovanja (ang. mode) [5]. Vsak nacin delovanja ima svoj kazalec sklada1". Za inicializacijo kazalcev sklada, kakor tudi za postavitev incializiranih in neinicializiranih globalnih in staticšnih spremenljivk, poskrbi zagonska koda v datoteki ctrO.s, ki jo povezovalnik (ang. linker) postavi na naslov * Izjema je prekinitev normalnega toka progama, ki je ni mogoce maskirati. Vse prekinitve zaradi zahtev perifernih enot (npr. timer, uart itd.) so izjeme tipa irq ali fiq, ki jih vektorski nadzornik prekinitev (ang. Vector Interrupt Controller) ne maskira. tRazen nacinov usr in sys, ki imata skupen kazalec sklada [5]. 0x00000000^. Druge datoteke vsebujejo spremljajočo kodo, potrebno za inicializacijo mikrokrmilnika (nastavitev fazno sklenjene zanke, smeri pinov ipd.). 3 Zagon operacijskega sistema in procesov Po izvršitvi zagonske kode v crtO.s se program nadaljuje v funkciji start_up(). Tu se s klicem funkcije os() inicializira operacijski sistem. V tem trenutku postane start_up() zacetni proces. Na operacijskem sistemu tako po zagonu tece en proces (tj. funkcija main(), klicana iz start_up()). Proces je funkcija tipa void brez argumentov. Nov proces se ustvari ob sistemskem klicu os_process_create (). Operacijski sistem podatke o procesih hrani v ci-klicnem povezanem seznamu, prikazanem na sliki 1. Pomnilnik za sklad (ang. stack) je procesu dodeljen na kopici (ang. heap), kar ne velja za zacetni proces, ki uporablja sklad nacina usr. Za nov proces je privzeta najnizšja prioriteta (spremeniti jo je mogocše s sistemskim klicem os_process_priority()) in stanje pripravljenosti na izvajanje. Zacetni proces je zopet izjema. Njegovo zacetno stanje je izvajanje. Poleg stanj izvajanje in pripravljenost se proces lahko nahaja še v stanjih spanje (proces dolocen casovni interval miruje) in čakanje (proces je blokiran) (slika 2). proces 1 main() nasl. proces 2 nasl. proces n nasl. Slika 1: Ciklični seznam procesov (nasl. = naslednji proces) i^pripravljenost^) 4 Stanji spanja in čakanja Casovnik operacijskega sistema šteje mikrosekunde od zagona naprej. Trenutno stanje casovnika vrne sistemski klic os_timer(). (Casovnik je 32-bitni števnik. Njegovo stanje se ponovi na vsakih 232^s « 1h 11min 35s. Proces gre iz stanja izvajanje v spanje (slika 2) s sistemskim klicem os_timer_sleep(). Sprememba sprozi razvršcevalnik procesov. Zaradi ciklicne narave casovni-ka je trenutek bujenja dolcšen tudi s trenutkom uspavanja, najdaljši cas spanja pa je (232 - 1)^s (slika 3). Iz stanja spanje se proces prebudi v izvajanje (proces ima najvišjo prioriteto) ali pripravljenost (proces nima najvišje prioritete). vrednost časovnika 0X00000000 ^ 68B) fiq irq (>68B) kopica JL neinicializirane spr. inicializirane spr. 3 nik FLASH (ang. In Application Programming). Na drugi strani delovnega pomnilnika se nahajajo inicializirane in neinicializirane globalne in statične spremenljvke, ki jim sledi kopica. Naslovi skladov s slike 5 so postavljeni v datoteki crt0.s. ,equ svc_stack, 0x40007fe0 /* 128B */ ,equ fiq_stack, 0x40007f60 /* 64B */ ,equ irq_stack, 0x40007f20 /* 128B */ .equ usr_stack, 0x40007ea0 Skladi procesov, razen sklada začetnega procesa, se nahajajo na kopici. Pri poplavljanju katerega izmed skladov (ang. stack overflow) ni mehanizma, ki bi napako avtomaticno zaznal. Prav tako ni mogoce zaznati poplavljanja sklada usr zacetnega procesa prek kopice ali nasprotno. Zasedenost delovnega pomnilnika je treba oceniti vnaprej, pri cemer je treba upoštevati ucinek razdrobljenosti kopice (ang. heap fragmentation). 7 RazvrSCevalnik procesov Razvršcevalnik procesov je srce operacijskega sistema. Njegova naloga je izbira procesa, ki naj v nadaljevanju zacne oziroma nadaljuje izvajanje. Prozen/klican je ob spremembah, ki vplivajo na razvršcanje procesov. Prozijo ga sistemski klici ali potek casovnega intervala. Poznanih je vec politik razvršcanja procesov [9], [10]. Predstavljen operacijski sistem spada med predkupne operacijske sisteme v realnem casu (ang. preemptive real-time operating system) s prioritetnim razvršcanjem. Algoritem razvršcanja (slika 6) je v osnovi preprost. preverjanje budnosti izbira procesa vsi procesi blokirani? da smrtni objem da /prekinjen proces\ ne izbran proces?, preklop določanje tren utka proženja da proženje določeno? nastavitev časovnika Slika 5: Razdelitev delovnega pomnilnika SRAM Slika 6: Algoritem razvrščevalnika pročesov ne ne usr Izbran je proces z najvišjo prioriteto. Ce je taksnih procesov vec, se cas centralne procesne enote med njimi enakomerno porazdeli. Razvršcevalnik na sliki 6 procese, katerih cas spanja je potekel (slika 3), prestavi v stanje pripravljenost (slika 2). Nato izbere buden, neblokiran proces z najvišjo prioriteto. Ce vsi procesi spijo, se pogoj budnosti umakne. Ce je semafor blokiranega procesa sproščen, se tak proces pri izbiri šteje za neblokiranega. Ce obstaja vec enakovrednih procesov, je izmed njih izbran prvi v ciklicnem seznamu (slika 1) od prekinjenega procesa naprej. Izbira naslednjega procesa ne uspe, ce so vsi procesi medsebojno blokirani. Razvršcevalnik se ujame v ne-skoncno zanko oziroma v smrtni objem. Sicer je izbran proces prestavljen v stanje izvajanje, prekinjen pa v stanje pripravljenost. Razvršcevalnik izvede preklop med procesoma (ang. context switch). Ce je izbran prekinjen proces, preklopa med procesoma ni. Sledi izracšun naslednjega cšasovno pogojenega prozše-nja razvršcevalnika. Trenutek prozenja je enak: - trenutku prvega bujenja (vsi procesi v stanju spanje), - trenutku bujenja procesa z višjo prioriteto ali - poteku ene casovne rezine (vec procesov z enako prioriteto). Casovnik timer0, ki prozi razvršcevalnik, se postavi na prvega izmed omenjenih casov. Ce ni izpolnjen noben od zgornjih pogojev, se cšasovnik ne postavi (npr. izbran proces je buden in ima najvišjo prioriteto). Iz zgradbe razvrsšcševalnika procesov sledi, da je operacijski sistem trd realnocasovni sistem (ang. hard realtime operating system) le za proces z najvišjo prioriteto. Procesu z nizjo prioriteto pravocasnost ni zagotovljena. Razvrsšcševalnik procesov zacšne delovati ob inicializa-ciji operacijskega sistema, tj. ob klicu funkcije os(). 8 Prekinitve in sistemski klici Izjemo oziroma prekinitev prestreze koda v datoteki exceptions.s, ki je del jedra operacijskega sistema. Od tod naprej je izjema/prekinitev lahko izvedena neodvisno od operacijskega sistema ali pa caka na dodelitev centralne procesne enote kot nov proces. V prvem primeru je operacijski sistem ustavljen za cas izvajanja prekinitve. Takšna prekinitev je podobna procesu z najvišjo prioriteto. V njej ni dovoljeno uporabljati sistemskih klicev operacijskega sistema (npr. ustvarjanje novega procesa, dodeljevanje pomnilnika ipd.). Cš e se izjema/prekinitev izvede pozneje kot proces v okviru operacijskega sistema, potem se postavi le zahteva po njej. Poseben proces periodicno preverja zahteve po prekinitvah (ang. interrupt polling) in na zahtevo ustvari nov proces, ki prekinitev izvede. Zakasnitev zacetka izvajanja prekinitve (ang. latency) je odvisna od frekvence preverjanja prekinitvenih zahtev. Takšna prekinitev lahko uporablja sistemske klice operacijskega sistema. Za sistemske klice je uporabljena izjema swi (nacin svc), za proženje razvršcevalnika procesov pa prekinitev timer0 (izjema/nacin irq). Stanje prekinjenega procesa se shrani na sklad pripadajočega nacina delovanja. Sledi sistemski klic. Posebno mesto ima razvršcevalnik procesov, ki izvede preklop med procesoma. To naredi tako, da zamenja vsebino na skladu s podatki prekinjenega procesa. Princip delovanja izjem je prikazan na sliki 7. izjema irq sistemskiN klic? rt k shranj sta evanje nja sistemski klic, razvršcevalnik obnav sta 'ljanje nja und abt fiq postavljanje zastavice, ali izvedba Slika 7: Izvajanje izjem Ker je gnezdenje prekinitev irq onemogoceno, so sistemski klici, kakor tudi razvrsšcševalnik procesov atomske operacije. 9 Izmerjene lastnosti sistema Izvorna koda operacijskega sistema je napisana v programskem jeziku C, razen strojno specificnih odsekov, ki so napisani v zbirniku. Pri prevajanju s prevajalniško zbirko GCC brez optimizacije velikosti kode zavzame 5108 zlogov, od tega inicializacija sistema 588 zlogov, sistemski klici 2324 in razvršcevalnik 2196 zlogov. Lastnosti sistema so bile izmerjene po metodi Thread-Metric [11] na mikrokrmilniku LPC2138 s taktom 60MHz. Rezultati v tabeli 1 podajajo število ponovitev testirane lastnosti v 30 sekundah. Tabela 1: Lastnosti sistema po metodi Thread-Metric Meritev St. ponovitev relativna hitrost mikrokrmilnika 30818 sodelujoce razvršcanje 566150 predkupno razvršcanje 348228 prekinitve brez preklopa med proc. 1490065 prekinitve s predkupnim preklopom 328587 zaklepanje virov 1669756 dinamicšno dodeljevanje pomnilnika 662250 swi ne ne Meritve so bile opravljene na kodi, prevedeni brez optimizacije na hitrost. Sodelujoče razvrščanje (ang. cooperative scheduling) je bilo izvedeno s postavitvijo zahteve po prekinitvi timer0 (razvrščevalnik) znotraj procesa. Podobno so prozene prekinitve brez in s predkupnim preklopom. Metoda Thread-Metric izvaja predkupno razvrščanje (ang. preemptive scheduling) z ekspicitnim postavljanjem procesov v stanje čakanja oziroma pripravljenosti, česar predstavljeni operacijski sistem ne pozna. Enak učinek je bil dosezen s spreminjanjem prioritet. Test dinamičnega dodeljevanja pomnilnika je bil izveden konservativno z dodeljevanjem in sproščanjem pomnilnika na koncu povezanega seznama (slika 4). 10 Sklep Predstavljen operacijski sistem za vgrajene sisteme s procesnim jedrom ARM7 teče v realnem času s prioritetnim razvrščanjem. Je univerzalen, hkrati pa modularen in preprost za uporabo. Modularna zgradba omogoča prilagoditev ali zamenjavo dela sistema glede na potrebe aplikacije (npr. spreminjanje politike razvrščanja, zamenjava cikličnega seznama procesov s prioritetnim, uporaba bitne predstavitve za dinamično dodeljevanje pomnilnika ipd.). Prozenje razvrščevalnika procesov je dogodkovno. Operacijski sistem je napisan v programskem jeziku C, kar omogoča relativno preprost prenos na mikrokrmilnike z drugačnim jedrom. Dostopna izvorna koda je implementirana za 32-bitne mikrokrmilnike iz druzine LPC213x. Zahvala Raziskavo je sofinanciralo Ministrstvo Republike Slovenije za izobrazševanje, znanost in sšport v okviru programa P2-0246 - Algoritmi in optimizacijski postopki v telekomunikacijah. Literatura [1] SEOS: Simple Educational Operating System, del knjiznice http://fides.fe.uni-lj.si/~janezp/libraries.zip, Jul. 2014. [2] FreeRTOS, http://www.freertos.org, Jul. 2014. [3] ThreadX Real Time Operating System, http://rtos.com/products/ threadx, Jul. 2014. [4] LPC2131/2/4/6/8 User manual, Rev. 4, Doc. ID UM10120, 23 Apr. 2012, NXP. [5] ARM7TDMI-S Technical Reference Manual, Rev. r4p3, DDI 0234B, 2001, ARM Ltd. [6] A.N. Sloss, D. Symes, C. Wright, J. Rayfield, ARM System Developer's Guide: Designing and Optimizing System Software, Elsevier, 2004. [7] E.W. Dijkstra, Cooperating Sequential Processes, Technological University, Eindhoven, The Netherlands, Sep. 1965, ponatisnjeno v Programming Languages, ured. F. Genuys, str. 43-112, Academic Press, NY, 1968. [8] D.E. Knuth, The Art of Computer Programming Vol. 1, Fundamental Algorithms, 3rd ed., Adison-Wesley, 2008. [9] J.W.S. Liu, Real-Time Systems, Prentice-Hall, NJ, 2000 [10] A. Silberschatz, P.B. Galvin, G. Gagne, Operating System Concepts, 8th ed. update, Wiley, NJ, 2012. [11] Thread-Metric Benchmark Suite, http://rtos.com/PDFs/Measu ringRTOSPerformance.pdf, Jul. 2014. Janez Puhan je leta 2000 doktoriral s področja elektrotehnike na Univerzi v Ljubljani. Je asistent na Fakulteti za elektrotehniko. Njegovo področje raziskovanja obsega modeliranje, simulacijo in optimizacijske postopke pri računalniškem načrtovanju vezij, kakor tudi programsko in strojno opremo vgrajenih sistemov.