1 UVOD
Programska oprema za mikrokrmilniške vgrajene sis-
teme je napisana na različne načine. Najpogoštejše pro-
gramske arhitekture so: izvajanje nalog v neskončni
zanki, servisiranje s prekinitvami proženih dogodkov,
razporejanje procesorskega časa med opravili s pomočjo
operacijskega sistema ali kombinacija med njimi. Po-
treba po uporabi operacijskega sistema se pokaže ob
večjem številu nalog, ki jih opravlja mikrokrmilniški
sistem. Programska oprema postane obsežna, zapletena
in posledično neobvladljiva. Operacijski sistem omogoči
navidezno sočasnost izvajanja nalog (ang. time sharing)
za ceno lastne režije. Operacijski sistemi na vgraje-
nih sistemih morajo zaradi svoje interakcije z okoljem
navadno teči v realnem času. Za vgrajene sisteme je
Prejet 17. junij, 2014
Odobren 30. september, 2014
na voljo več operacijskih sistemov v realnem času,
kot npr. FreeRTOS [2], ThreadX [3] ipd., ki navadno
želijo zadostiti vsem željam uporabnikov. Tako tečejo
na množici različnih mikrokrmilnikov, ponujajo različne
politike razvrščanja, sheme dinamičnega dodeljevanja
pomnilnika, sinhronizacije med procesi ipd. Splošnost
je sicer dobrodošla, a lahko postane nepregledna.
V članku predstavljamo nov prioritetni predkupni ope-
racijski sistem v realnem času. Napisali smo minimalen
operacijski sistem, ki omogoča prioritetno predkupnost
poljubnega števila dinamično ustvarjenih končnih ali
neskončnih procesov. Sistem smo implementirali za 32-
bitne mikrokrmilnike družine LPC213x [4] s procesnim
jedrom ARM7TDMI-S [5].
2 DATOTEKE Z IZVORNO KODO
OPERACIJSKEGA SISTEMA
Izvorna koda jedra operacijskega sistema [1] je v da-
totekah s predpono os. Jedro obsega razvrščevalnik
procesov s funkcijami sistemskih klicev. Del jedra je
tudi datoteka exceptions.s, ki prestreže izjeme∗ (ang.
exception) [6]. Procesno jedro ARM7TDMI-S pozna več
vrst izjem s pripadajočimi vektorji in načini delovanja
(ang. mode) [5]. Vsak način delovanja ima svoj kazalec
sklada†. Za inicializacijo kazalcev sklada, kakor tudi za
postavitev incializiranih in neinicializiranih globalnih in
statičnih spremenljivk, poskrbi zagonska koda v datoteki
ctr0.s, ki jo povezovalnik (ang. linker) postavi na naslov
∗Izjema je prekinitev normalnega toka progama, ki je ni mogoče
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.
†Razen načinov usr in sys, ki imata skupen kazalec sklada [5].
210 PUHAN
0x00000000‡. Druge datoteke vsebujejo spremljajočo
kodo, potrebno za inicializacijo mikrokrmilnika (nasta-
vitev fazno sklenjene zanke, smeri pinov ipd.).
3 ZAGON OPERACIJSKEGA SISTEMA IN
PROCESOV
Po izvršitvi zagonske kode v crt0.s se program nadaljuje
v funkciji start up(). Tu se s klicem funkcije os()
inicializira operacijski sistem. V tem trenutku postane
start up() začetni proces. Na operacijskem sistemu tako
po zagonu teče 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-
kličnem povezanem seznamu, prikazanem na sliki 1.
Pomnilnik za sklad (ang. stack) je procesu dodeljen na
kopici (ang. heap), kar ne velja za začetni proces, ki
uporablja sklad načina usr. Za nov proces je privzeta
najnižja prioriteta (spremeniti jo je mogoče s sistemskim
klicem os process priority()) in stanje pripravljenosti
na izvajanje. Začetni proces je zopet izjema. Njegovo
začetno stanje je izvajanje. Poleg stanj izvajanje in
pripravljenost se proces lahko nahaja še v stanjih spanje
(proces določen časovni interval miruje) in čakanje
(proces je blokiran) (slika 2).
nasl.
proces 2proces 1
main()
nasl.
proces n nasl.
Slika 1: Ciklični seznam procesov (nasl. = naslednji proces)
spanje
izvajanje
čakanje
pripravljenost
Slika 2: Prehodi med stanji procesa
Proces se konča, ko se njegova funkcija izvede do konca.
Predčasno ga je mogoče končati s sistemskim klicem
os process kill(). Zaključitev zadnjega procesa povzroči
smrtni objem (ang. deadlock) operacijskega sistema.
Kazalec na funkcijo procesa je hkrati tudi identifikator
procesa. Sočasno lahko teče le en primerek posameznega
procesa. Operacijski sistem ne dovoljuje vzporednega
teka več primerkov istega procesa.
Procesne spremembe vplivajo na razvrščanje proce-
sov. Zato procesni sistemski klici, kakor tudi končanje
procesa, prožijo razvrščevalnik procesov operacijskega
sistema.
‡Ob resetu mikrokrmilnika se prvi ukaz izvede iz naslova 0x0000
0000.
4 STANJI SPANJA IN ČAKANJA
Časovnik operacijskega sistema šteje mikrosekunde od
zagona naprej. Trenutno stanje časovnika vrne sistemski
klic os timer(). Časovnik 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 sproži
razvrščevalnik procesov. Zaradi ciklične narave časovni-
ka je trenutek bujenja dolčen tudi s trenutkom uspavanja,
najdaljši čas 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).
bu
jen
je
spanje
us
pa
va
nje
0x00000000 0xffffffff
bu
jen
je
vrednost časovnika
spanje
us
pa
va
nje
0x00000000 0xffffffff
spanje
Slika 3: Trajanje stanja spanje
Operacijski sistem omogoča zaklepanje virov s pomočjo
binarnih semaforjev [7]. Binarni semafor je realiziran
kot spremenljivka tipa int z vrednostjo nič (deklarirano
z UNLOCKED), ko je vir na voljo, oziroma z vrednostjo
kazalca na funkcijo procesa, ki je vir zasedel. Poskus
zasedbe semaforja/vira (ang. wait semaphore operation)
izvede sistemski klic os mutex lock(). V primeru ne-
uspeha je proces blokiran (stanje čakanje), kar sproži
razvrščevalnik procesov operacijskega sistema, ki cen-
tralno procesno enoto dodeli drugemu procesu.
Sprostitev semaforja (ang. post semaphore operation)
naredi sistemski klic os mutex unlock(). Pri tem se
sproži razvrščevalnik procesov. Blokiran proces iz stanja
čakanje nazaj v stanje izvajanje postavi razvrščevalnik
procesov, ko izbere blokiran proces, katerega semafor je
bil sproščen. Sveže odblokiran proces najprej ponovno
poskusi z zasedbo semaforja.
5 DINAMIČNO DODELJEVANJE
POMNILNIKA
Dinamično dodeljevanje pomnilnika (ang. dynamic me-
mory managment) na kopici izvajata funkciji os allocate
() in os free(). Za preprečitev hkratnega dostopa do
podatkov o dodeljenem pomnilniku funkciji uporabljata
binarni semafor alloc. Dinamično dodeljevaje pomnil-
nika je uporabljeno tudi ob ustvarjanju in končanju
procesa. Poleg prostora s podatki o pocesu se vsakemu
procesu dinamično dodeli še prostor za sklad.
Dodeljen pomnilnik (ang. allocated memory) je orga-
niziran v povezan seznam, prikazan na sliki 4. Seznam
RTOS ZA ARM7 211
je urejen po naslovih dodeljenih kosov (ang. alloca-
tion) pomnilnika. Prvi kos označuje začetek seznama
in ni nikdar sproščen. Pomeni navidezno dodelitev nič
zlogov (ang. byte) pomnilnika. Funkcija os allocate()
implementira strategijo prvega primernega prostora za
dodelitev (ang. first fit algorithm) [8].
začetek
naslednji
k
o
p
ic
a
naslednji
NULL
naslednji
Slika 4: Urejen povezan seznam z dodeljenim pomnilnikom.
Prost pomnilnik je osenčen.
Mikrokrmilniki družine LPC213x nimajo enote za upra-
vljanje delovnega pomnilnika (ang. Memory Manage-
ment Unit). Tako je dinamično dodeljen pomnilnik vi-
den vsem procesom, česar operacijski sistem ne more
omejiti.
6 RAZDELITEV DELOVNEGA POMNILNIKA
Operacijski sistem uporablja prekinitev časovnika timer0
(tj. izjemo/način irq) za časovno rezinjenje in program-
sko prekinitev (tj. izjemo swi v načinu svc) za sistemske
klice. Na vsakem izmed skladov načinov delovanja irq
in svc mora biti na voljo vsaj 68 zlogov namenjenih
trenutnemu stanju jedra (sedemnajst 32-bitnih delovnih
registrov). Razporeditev je prikazana na sliki 5. Sklad
fiq neodvisno od operacijskega sistema uporabljajo pre-
kinitve, deklarirane kot izjeme tipa fiq, sklad usr pa
uporablja začetni proces. 32 zlogov na vrhu delovnega
pomnilnika je na voljo ukazom za zapisovanje v pomnil-
IAP (32B)
neinicializirane spr.
usr
irq (>68B)
fiq
8
-3
2
k
B
S
R
A
M
0x40000000
svc (>68B)
kopica
inicializirane spr.
sk
la
d
i
sk
la
d
i
sk
la
d
i
Slika 5: Razdelitev delovnega pomnilnika SRAM
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 na-
pako avtomatično zaznal. Prav tako ni mogoče zaznati
poplavljanja sklada usr začetnega procesa prek kopice
ali nasprotno. Zasedenost delovnega pomnilnika je treba
oceniti vnaprej, pri čemer je treba upoštevati učinek
razdrobljenosti kopice (ang. heap fragmentation).
7 RAZVRŠČEVALNIK PROCESOV
Razvrščevalnik procesov je srce operacijskega sistema.
Njegova naloga je izbira procesa, ki naj v nadaljeva-
nju začne oziroma nadaljuje izvajanje. Prožen/klican je
ob spremembah, ki vplivajo na razvrščanje procesov.
Prožijo ga sistemski klici ali potek časovnega intervala.
Poznanih je več politik razvrščanja procesov [9], [10].
Predstavljen operacijski sistem spada med predkupne
operacijske sisteme v realnem času (ang. preemptive
real-time operating system) s prioritetnim razvrščanjem.
Algoritem razvrščanja (slika 6) je v osnovi preprost.
preverjanje budnosti
smrtni objem
da proženje
določeno?
prekinjen
izbran
proces
= proces?
preklop
nastavitev časovnika
da
izbira procesa
ne
ne vsi procesi
blokirani?
da ne
določanje trenutka proženja
Slika 6: Algoritem razvrščevalnika procesov
212 PUHAN
Izbran je proces z najvišjo prioriteto. Če je takšnih
procesov več, se čas centralne procesne enote med njimi
enakomerno porazdeli.
Razvrščevalnik na sliki 6 procese, katerih čas spanja
je potekel (slika 3), prestavi v stanje pripravljenost (slika
2). Nato izbere buden, neblokiran proces z najvišjo
prioriteto. Če vsi procesi spijo, se pogoj budnosti uma-
kne. Če je semafor blokiranega procesa sproščen, se
tak proces pri izbiri šteje za neblokiranega. Če obstaja
več enakovrednih procesov, je izmed njih izbran prvi
v cikličnem seznamu (slika 1) od prekinjenega procesa
naprej.
Izbira naslednjega procesa ne uspe, če so vsi procesi
medsebojno blokirani. Razvrščevalnik se ujame v ne-
skončno zanko oziroma v smrtni objem. Sicer je izbran
proces prestavljen v stanje izvajanje, prekinjen pa v sta-
nje pripravljenost. Razvrščevalnik izvede preklop med
procesoma (ang. context switch). Če je izbran prekinjen
proces, preklopa med procesoma ni.
Sledi izračun naslednjega časovno pogojenega prože-
nja razvrščevalnika. Trenutek proženja je enak:
- trenutku prvega bujenja (vsi procesi v stanju spanje),
- trenutku bujenja procesa z višjo prioriteto ali
- poteku ene časovne rezine (več procesov z enako
prioriteto).
Časovnik timer0, ki proži razvrščevalnik, se postavi na
prvega izmed omenjenih časov. Če ni izpolnjen noben
od zgornjih pogojev, se časovnik ne postavi (npr. izbran
proces je buden in ima najvišjo prioriteto).
Iz zgradbe razvrščevalnika procesov sledi, da je ope-
racijski sistem trd realnočasovni sistem (ang. hard real-
time operating system) le za proces z najvišjo prioriteto.
Procesu z nižjo prioriteto pravočasnost ni zagotovljena.
Razvrščevalnik procesov začne delovati ob inicializa-
ciji operacijskega sistema, tj. ob klicu funkcije os().
8 PREKINITVE IN SISTEMSKI KLICI
Izjemo oziroma prekinitev prestreže 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 čaka na dodelitev cen-
tralne procesne enote kot nov proces. V prvem primeru
je operacijski sistem ustavljen za čas izvajanja preki-
nitve. 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.).
Če se izjema/prekinitev izvede pozneje kot proces v
okviru operacijskega sistema, potem se postavi le zah-
teva po njej. Poseben proces periodično preverja zahteve
po prekinitvah (ang. interrupt polling) in na zahtevo
ustvari nov proces, ki prekinitev izvede. Zakasnitev
začetka 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 (način
svc), za proženje razvrščevalnika procesov pa prekinitev
timer0 (izjema/način irq). Stanje prekinjenega procesa
se shrani na sklad pripadajočega načina delovanja. Sledi
sistemski klic. Posebno mesto ima razvrščevalnik proce-
sov, 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.
obnavljanje
stanja
timer0?
ne
postavljanje
zastavice,
ali izvedba
und
abt
fiq
sistemski
klic?
da
ne
shranjevanje
stanja
sistemski klic,
razvrščevalnik
p
r e
k
i n
i t e
v
swi irqizjema
Slika 7: Izvajanje izjem
Ker je gnezdenje prekinitev irq onemogočeno, so sis-
temski klici, kakor tudi razvrščevalnik procesov atomske
operacije.
9 IZMERJENE LASTNOSTI SISTEMA
Izvorna koda operacijskega sistema je napisana v pro-
gramskem jeziku C, razen strojno specifičnih 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ščevalnik 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 Št. ponovitev
relativna hitrost mikrokrmilnika 30818
sodelujoče razvrščanje 566150
predkupno razvrščanje 348228
prekinitve brez preklopa med proc. 1490065
prekinitve s predkupnim preklopom 328587
zaklepanje virov 1669756
dinamično dodeljevanje pomnilnika 662250
RTOS ZA ARM7 213
Meritve so bile opravljene na kodi, prevedeni brez opti-
mizacije na hitrost. Sodelujoče razvrščanje (ang. coope-
rative scheduling) je bilo izvedeno s postavitvijo zahteve
po prekinitvi timer0 (razvrščevalnik) znotraj procesa.
Podobno so prožene prekinitve brez in s predkupnim
preklopom. Metoda Thread-Metric izvaja predkupno
razvrščanje (ang. preemptive scheduling) z ekspicitnim
postavljanjem procesov v stanje čakanja oziroma pri-
pravljenosti, česar predstavljeni operacijski sistem ne
pozna. Enak učinek je bil dosežen s spreminjanjem pri-
oritet. 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 priorite-
tnim razvrščanjem. Je univerzalen, hkrati pa modularen
in preprost za uporabo. Modularna zgradba omogoča
prilagoditev ali zamenjavo dela sistema glede na po-
trebe aplikacije (npr. spreminjanje politike razvrščanja,
zamenjava cikličnega seznama procesov s prioritetnim,
uporaba bitne predstavitve za dinamično dodeljevanje
pomnilnika ipd.). Proženje razvrščevalnika procesov je
dogodkovno. Operacijski sistem je napisan v program-
skem jeziku C, kar omogoča relativno preprost prenos na
mikrokrmilnike z drugačnim jedrom. Dostopna izvorna
koda je implementirana za 32-bitne mikrokrmilnike iz
družine LPC213x.
ZAHVALA
Raziskavo je sofinanciralo Ministrstvo Republike Slo-
venije za izobraževanje, znanost in šport v okviru pro-
grama P2-0246 - Algoritmi in optimizacijski postopki v
telekomunikacijah.