LUCRARE DE LICENŢĂ - ACSE...
78
Universitatea Politehnica Bucureşti Facultatea de Automatică şi Calculatoare Departamentul de Automatică şi Ingineria Sistemelor LUCRARE DE LICENŢĂ Algoritmi de planificare a resurselor in sisteme de operare de timp real Coordonator: Absolvent: Prof. dr. Ing. Daniela Saru Levent Menadil Bucureşti, 2013
Transcript of LUCRARE DE LICENŢĂ - ACSE...
Universitatea Politehnica Bucureşti
Facultatea de Automatică şi Calculatoare
Departamentul de Automatică şi Ingineria Sistemelor
LUCRARE DE LICENŢĂ
Algoritmi de planificare a resurselor in sisteme de
operare de timp real
Coordonator: Absolvent:
Prof. dr. Ing. Daniela Saru Levent Menadil
Bucureşti, 2013
2
CUPRINS
1 Introducere ........................................................................................................................ 4
2 Aspecte teoretice ................................................................................................................ 7
2.1. Algoritmi de planificare ............................................................................................... 8
2.1.1. Criterii de performanţă........................................................................................ 10
2.1.2. Algoritmul FCFS ................................................................................................ 12
2.1.3. Algoritmul SJF ................................................................................................... 14
2.1.4. Algoritmi bazaţi pe priorităţi ............................................................................... 16
2.1.5. Algoritmi de tip Round-robin .............................................................................. 17
2.1.6. Algoritmi de tip coada multinivel ........................................................................ 19
2.2. Compararea algoritmilor ............................................................................................ 21
2.3. Condiţiile de timp real ............................................................................................... 26
3 Implementarea Microkernelului .................................................................................... 28
3.1. De ce un microkernel? ............................................................................................... 28
3.2. Componenta Hardware .............................................................................................. 30
3.2.1. Arhitectura Cortex-M3 ........................................................................................ 33
3.3. Componenta Software ............................................................................................... 36
3.3.1. Schimbarea contextului ....................................................................................... 36
3.3.2. Iniţializarea task-urilor ........................................................................................ 39
3.3.3. Mecanisme de sincronizare ................................................................................. 41
3.4. Modul de utilizare ..................................................................................................... 43
4 Comparaţie cu alte soluţii existente ................................................................................ 45
5 Studiu de caz: algoritm PID ........................................................................................... 49
5.1. Obţinerea ecuaţiei cu diferenţe .................................................................................. 49
5.2. Structura task-ului ..................................................................................................... 52
5.3. Interpretarea rezultatelor ............................................................................................ 54
6 Concluzii si dezvoltări ulterioare .................................................................................... 57
7 Anexe ............................................................................................................................... 58
8 Bibliografie: ..................................................................................................................... 77
3
Listă de figuri si tabele:
Figură 2.1. Regimul de funcţionare al procesorului ............................................................................................ 9 Figură 2.2. Diagrama de stări a task-urilor .......................................................................................................10 Figură 2.3.Diagrama simplificată de stări .........................................................................................................12 Figură 2.4. Ordinea de execuţie cu algoritmul FCFS ...........................................................................................13 Figură 2.5. Simularea algoritmului FCFS ...........................................................................................................14 Figură 2.6. Ordinea de execuţie cu algoritmul SJF .............................................................................................15 Figură 2.7. Simularea algoritmului SJF ..............................................................................................................15 Figură 2.8. Ordinea de execuţie cu algoritmul bazat pe priorităţi ......................................................................16 Figură 2.9. Simularea algoritmului bazat pe priorităţi .......................................................................................17 Figură 2.10. Simularea algoritmului Round-robin .............................................................................................18 Figură 2.11. Simularea algoritmului Lottery Round-robin ..................................................................................19 Figură 2.12. Algoritmul de tip coadă multinivel ................................................................................................20 Figură 2.13. Algoritmul de tip coadă multinivel cu feedback .............................................................................20 Figură 2.14. Funcţia de probabilitate a 𝑡𝑡 pentru cei trei algoritmi ....................................................................23 Figură 2.15. Funcţia de probabilitate a 𝑡𝑟 pentru cei trei algoritmi....................................................................24 Figură 2.16. Funcţia de probabilitate a 𝑡𝑡 pentru RR, respectiv Lottery RR .........................................................25 Figură 2.17. Funcţia de probabilitate a 𝑡𝑟 pentru RR si pentru Lottery RR ..........................................................25 Figură 2.18. Constrângerile de timp real...........................................................................................................26 Figură 3.1. Sistem de operare monolitic ...........................................................................................................29 Figură 3.2. Sistem de operare de tip microkernel ..............................................................................................29 Figură 3.3. Sistem de operare de tip hibrid .......................................................................................................30 Figură 3.4. Plăcuţa de dezvoltare STM32-H107.................................................................................................31 Figură 3.5. Programatorul/Depanatorul ST/Link v2. ..........................................................................................32 Figură 3.6. Stagiile pipeline pentru instrucţiunile ARMv7. .................................................................................34 Figură 3.7. Regiştrii procesorului Cortex-M3 .....................................................................................................35 Figură 3.8. Schimbarea contextului in procesorul Cortex-M3 .............................................................................37 Figură 5.1. Schema de reglare automată pentru un regulator discret ................................................................52 Figură 5.2. Execuţia task-urilor in sistemul proiectat .........................................................................................54
Tabel 2.1. Timpurile medii de terminare pentru algoritmii de planificare ...........................................................21 Tabel 2.2. Timpurile medii de răspuns pentru algoritmii de planificare ..............................................................21 Tabel 2.3. Media si abaterea medie pătratică a măsurătorilor ..........................................................................22 Tabel 2.4. Măsurătorile algoritmilor FCFS, SJF si RR ..........................................................................................22 Tabel 3.1. Modurile de pornire pentru microcontrolerul STM32-F107 ................................................................32 Tabel 4.1. Evaluarea criteriilor de performanţă a soluţiei propuse .....................................................................47 Tabel 4.2. Evaluarea criteriilor de performanţă pentru microkernelul ThreadX ..................................................47 Tabel 4.3. Evaluarea criteriilor de performanţă pentru microkernelul FreeRTOS ................................................48 Tabel 4.4. Evaluarea criteriilor de performanţă pentru microkernelul Neutrino .................................................48
4
1 Introducere
În ultimele decade am fost martori ai unei explozii a sistemelor informatice. Progresul
lor s-a datorat în mare măsură utilităţii în viaţa de zi cu zi, începând de la ajutorul cotidian de
la locul de muncă, ajungând la sistemul medical şi terminând cu vastele sisteme informatice
care sunt folosite pentru asigurarea securităţii. Un al exemplu îl reprezintă sistemele integrate
ce sunt prezente acum în aproape toate aparatele electronice.
Modelul clasic al unui sistem informatic este clădit pe interacţiunea dintre componenta
hardware; partea fizică (procesor, memorie şi restul circuitelor auxiliare) şi componenta
software; definită ca partea logică.
Pentru a permite utilizatorului să interacţioneze eficient cu resursele hardware,
sistemele de calcul implementează un nivel separat de software, numit nivelul sistemului de
operare. Acesta este, din punct de vedere structural, un program care gestionează resursele
hardware, iar din punct de vedere funcţional, duce la o abstractizare a resurselor hardware
pentru utilizatori. Sistemele de operare prezintă utilizatorului o interfaţă mai plăcută
comparativ cu interfaţa directă cu hardware-ul, ducând la performanţe sporite. Realizând
această cerinţă, dificultatea utilizării elementelor de bază ale sistemului de calcul (sau simpla
cunoaştere a acestora) se transferă proiectantului sistemului de operare.
Printre cerinţele sistemelor de operare putem aminti: asigurarea accesului mai multor
utilizatori la un sistem de calcul, rularea mai multor programe în paralel, asigurarea protecţiei
programelor din memorie, precum şi nemodificarea majoră a performanţelor sistemului de
calcul prin implementarea sistemului de operare, iar sistemele specializate pot avea cerinţe
mai variate. Spre exemplu, în aplicaţii ce implică stocarea de date pe un sistem distribuit, un
accent mai mare este pus pe asigurarea siguranţei sistemului iar în aplicaţii industriale sau
ştiinţifice apar constrângeri de timp real. De aici apare nevoia dezvoltării unor sisteme de
operare ce pot satisface aceste cerinţe.
Una din cele mai frecvente cerinţe este execuţia în paralel a mai multor aplicaţii. Fie
că este vorba de execuţia a 20-30 de aplicaţii pe un PC sau de achiziţia, prelucrarea şi
5
trimiterea prin o reţea a unor măsurători într-o aplicaţie industrială, multitasking-ul este
esenţial. Întrucât sistemele de calcul au un număr redus de nuclee de execuţie (cel mai adesea
unul singur), şi prin urmare, un număr redus de fire de execuţie fizice, apar probleme în
realizarea, sau mai degrabă, simularea paralelismului.
Obţinerea paralelismului prin maparea fiecărui proces logic pe un proces fizic este
realizat de sistemul de operare, mai precis de o componentă a sa, numită planificator de
thread-uri sau, mai simplu, planificator (engl: scheduler). Aceasta componentă trebuie să ţină
cont de numeroşi parametrii şi constrângeri ducând la dificultăţi majore în proiectarea sa. Din
cauza dificultăţii proiectării unui algoritm de planificare care să satisfacă toate cerinţele date
şi să minimizeze toate criteriile de performanţă se recomandă utilizarea algoritmilor în funcţie
de cerinţele sistemului.
În sisteme interactive, o importanţă sporită o are timpul de răspuns, adică timpul de la
crearea task-ului până la lansarea sa în execuţie iar în sistemele de timp real, timpul de
terminare, definit ca timpul de la crearea task-ului până la execuţia sa în întregime, este vital.
Lucrarea de faţă îşi propune studierea algoritmilor de planificare şi a criteriilor
acestora de performanţă în Capitolul 2, ţinându-se cont de constrângerile de timp real. În
Capitolul 3 am proiectat şi am implementat nucleul unui Sistem de Operare în Timp Real
(SOTR) cu scopul de a testa şi a evalua aceşti algoritmi. Nucleul, de tip microkernel, este
implementat pe un microcontroler STM32-F107, dar va putea fi portat cu uşurinţă către alte
microcontrolere cu acelaşi procesor, Cortex-M3, sau cu versiuni mai noi de procesoare
Cortex-M. Acesta va avea un grad ridicat de scalabilitate, având implementate semafoare
binare şi mutexi că mecanisme de sincronizare şi putând să i se adauge la revizii ulterioare un
sistem de fişiere, drivere pentru periferice, şi un sistem de protecţie a memoriei, toate utile în
aplicaţiile uzuale. În Capitolul 4, am relizat o comparaţie a microkernelului cu alte soluţii
existente de pe piaţă, iar în Capitolul 5, am implementat pe acesta un algoritm de reglare, de
tip PID, sub forma unui task pentru a putea studia criteriile de performanţă definite în
Capitolul 2 şi a evidenţia funcţionalitatea acestui task în timp real.
Scopul urmărit a fost aprofundarea domeniului sistemelor de operare şi a proiectării
lor precum şi a domeniului programării microcontrolerelor. Conexiunea dintre aceste
domenii, aparent neintuitivă, este vitală în sectoarele bazate pe sisteme integrate. Însăşi
proiectarea sistemelor de operare este deseori considerată de mulţi ca fiind un domeniu
6
periculos, destinat unui număr restrâns de oameni, preferându-se utilizarea acestora din
perspectiva de utilizatori, iar lucrarea de faţă încearcă, oferind un exemplu relativ simplu şi
intuitiv, să arate contrariul.
7
2 Aspecte teoretice
Pentru a înţelege conceptul de execuţie în paralel a firelor de execuţie trebuie să fie
definim clar termenul de fir de execuţie (engl. thread). Acesta este cea mai mică unitate de
procesare ce poate fi programată spre execuţie de către sistemul de operare. Nu trebuie făcută
confuzia între program şi fir de execuţie, cel din urmă fiind o instanţiere a unui program în
execuţie şi prezentând parametrii de stare.
În cadrul sistemelor de operare, mai există conceptul de proces pentru a defini o zonă
clară de memorie care poate conţine unul sau mai multe fire de execuţie. Acest concept ne
permite evitarea efectelor nefaste ale utilizării aceluiaşi spaţiu de către mai multe fire de
execuţie şi a alterării codului sau a datelor unui fir de execuţie de către alt fir de execuţie.
Diferenţa dintre proces şi fir de execuţie constă, aşadar în utilizarea unei zone comune de
memorie de către mai multe thread-uri şi utilizarea unor zone separate în cazul proceselor.
Din perspectiva sistemului de operare, schimbarea de la un proces la altul implică saltul la o
zonă de memorie îndepărtată, trecerea la altă stivă, la alt "heap", precum şi schimbarea
completă a parametrilor de stare. Însă trecerea de la un fir de execuţie la altul implica cel mai
adesea încărcarea altui set de regiştrii ai procesorului şi trecerea la altă stivă. Din această
cauză, schimbarea de la un proces la altul se realizează mai lent, iar schimbarea între fire de
execuţie mai rapid, ducând la denumirea de "light-weight process" pentru fire de execuţie.
În mod ideal, firele de execuţie sunt folosite pentru programe ce au nevoie de un
paralelism perfect controlabil. De exemplu, dacă o problemă poate fi împărţită în mai multe
probleme, cu sarcini aproape identice, firele de execuţie ar putea fi o alegere bună, iar dacă nu
este nevoie de un paralelism atât de controlabil, ar trebui utilizate procese [1]. Pentru a obţine
performanţe maxime în sisteme în care se doreşte o paralelizare semnificativă (ex. Serverele
WEB sau sistemele de tip PC) se folosesc procesele iar în cadrul acestora, firele de execuţie.
Pentru a realiza o abstractizare a ambilor termeni când ne referim la îndeplinirea unui
scop, se foloseşte termenul de task. Acest termen, împreună cu cel de fir de execuţie şi de
proces va fi utilizat în continuare în această lucrare, deşi există o distincţie clară între ultimele
două.
8
Sistemele de operare cu suport pentru multitasking au de îndeplinit mai multe cerinţe.
Cele mai elementare sunt alocarea unui spaţiu în memorie pentru variabilele de stare şi pentru
codul programului precum şi asigurarea schimbării între task-uri fără pierderi de informaţii
(doar în cod reentrant) şi relativ rapid [1] iar printre cerinţele opţionale putem enumera
comunicarea şi sincronizarea între task-uri.
Tot sistemului de operare îi revine sarcina asigurării că programele nu se suprascriu şi
că nu se ajunge la pierderi de date. Ideal, într-un astfel de sistem, fiecare task creat de
utilizator ar trebui privit ca având monopol asupra procesorului, a regiştrilor săi de uz general
şi a contorului de program, precum şi a unei zone de memorie.
Alegerea programului ce se va executa în continuare este realizată de o componentă a
sistemului de operare, din cadrul kernelului, numit planificator de task-uri (engl: task
scheduler) iar schimbarea efectivă a regiştrilor procesorului şi sărirea la altă linie de program
este datoria dispacherului, tot din cadrul kernelului [2]. Acesta poate rula ca task separat
pentru a decide task-ul care va urma, sau poate fi apelat de către o întrerupere pentru a aplica
pe moment algoritmul de planificare. Ultima variantă, prezintă avantaje clare de flexibilitate,
kernelul fiind apelat mai des şi ducând la o eficienţă mai bună a algoritmului folosit, însă are
ca dezavantaj schimbarea mai greoaie între task-uri în cazul algoritmilor complecşi şi cu o
durată nedeterministă.
2.1. Algoritmi de planificare
Descrierea algoritmilor de planificare se va face, în continuare cu următoarele
premize: procesorul are un singur nucleu de execuţie, aşadar în orice moment de timp se poate
executa fizic un singur task, şi nu se face distincţia între fire de execuţie şi procese, sistemul
considerându-se că are un singur tip de task implementat.
Pentru a înţelege condiţiile în care se poate schimba contextul şi, implicit task-urile,
trebuie să fie făcute clare condiţiile în care funcţionează majoritatea sistemelor de calcul. În
prezent, date fiind creşterea frecvenţei procesorului şi îmbunătăţirea microarhitecturii
acestora, puterea de calcul este rareori o problemă. În schimb, acestea sunt cel mai adesea
9
limitate de puterea utilizatorului (prin care o să ne referim la orice instanţă situată în afara
calculatorului) de a introduce date. Spre exemplu, motoraşul dintr-un hard disk rulează de
câteva ordine de mărime mai încet decât viteza procesorului. În cazuri concrete, şi luând în
considerare un singur task, acesta din urmă va alterna deseori între perioade lungi în care va
rula pe procesor şi perioade lungi în care va aştepta să primească date din exterior.
Acest lucru reprezintă un avantaj pentru proiectantul sistemului de operare
permiţându-i acestuia să folosească timpul în care task-ul aşteaptă să primească date, pentru a
rula alt task. În figura de mai jos, este reprezentată grafic alternanţa perioadelor în care
procesorul rulează cu programul task-ului (numite aici CPU burst-uri) şi a perioadelor în care
acesta aşteaptă date din exterior (numite I/O burst-uri).
Figură 2.1. Regimul de funcţionare al procesorului
Sursa imaginii este [15]
De aici rezultă o primă categorie de algoritmi de planificare care duc la schimbarea
task-ului curent, şi anume algoritmii non-preemptivi sau cooperativi, (Silberschantz, et al.,
2005) aceştia invocând kernelul doar în situaţia în care task-ul curent trece în starea de
aşteptare pentru a întâmpina un semnal din exterior şi, evident, în situaţia în care task-ul
10
curent se termină de executat. Termenul de cooperativi mai este folosit deoarece, în lipsa unei
întreruperi din exterior pentru a schimba task-ului curent, ei îşi pot ceda între ei, voluntar,
accesul la procesor.
A doua categorie a algoritmilor de planificare o reprezintă algoritmii preemptivi care
pot fi schimbaţi din execuţie de către o întrerupere sau la terminarea unui I/O burst.
Deşi algoritmii non-preemptivi pot fi folosiţi şi pe sisteme ce nu au anumite
componente hardware (de exemplu, un timer) se pot vedea clar beneficiile algoritmilor de tip
preemptiv, aceştia permiţând o flexibilitate sporită, nebazându-se pe evenimente semi-
stocastice cum ar fi cererea unor date de I/O. În sistemele de operare actuale, sunt în folosinţă
algoritmi preemptivi încăpând cu Windows 95 şi cu Mac OS X.
În figura 2.2 este prezentată diagrama corespunzătoare task-urilor organizate de un
algoritm de planificare. În cazul algoritmilor non-preemptivi, dispatcherul nu poate trimite
spre rulare un alt task decât după blocarea task-ului actual.
Figură 2.2. Diagrama de stări a task-urilor
2.1.1. Criterii de performanţă
Alegerea unui algoritm de planificare în defavoarea altuia se face raportat la nişte
criterii de performanţă. Aceştia, la rândul lor, pot fi sau nu semnificativi, în funcţie de context
şi sunt [2]:
11
1. Utilizarea CPU-ului. Reprezintă procentual raportul dintre timpul folosit pentru a
executa cod util şi timpul total care trece. Ideal se doreşte utilizarea procesorului într-o
proporţie de 100%, dar în sistemele reale, utilizarea variază între 40% şi 90%.
2. Rata de terminare a task-urilor. Pentru a măsura eficienţa algoritmului raportat la
cantitatea de muncă efectuată se mai poate lua drept criteriu de performanţa rata în care se
termină task-urile. Pentru task-uri lungi, poate fi de un task / oră iar în cazul task-urilor scurte,
poate fi de 10 task-uri / secundă.
3. Timpul de terminare. Din punctul de vedere al unui task, acesta este caracterizat
prin timpul total scurs de la creare până la terminare. Acest timp este alcătuit din suma
timpilor în care task-ul aşteaptă în lista de aşteptare, execută pe CPU şi realizează transferuri
I/O.
4. Timpul de aşteptare. Acesta reprezintă timpul total pe care task-ul îl petrece în
lista de aşteptare şi este direct afectat de acţiunile luate de planificator
5. Timpul de răspuns. În sistemele interactive se pune accent pe timpul mediu de la
crearea task-ului până când acesta începe să ofere rezultate. Acest timp este în general limitat
de viteza echipamentului periferic de I/O, dar pentru simplificare putem considera acest timp
ca fiind timpul de aşteptare de la crearea task-ului până la lansarea sa în execuţie pentru prima
dată.
Pentru optimizarea algoritmilor de planificare ar trebui să se urmărească mărirea
utilizării CPU-ului şi a ratei de terminare a task-urilor şi să se micşoreze timpul de terminare,
timpul de aşteptare şi timpul de răspuns. Cel mai adesea se doreşte optimizarea valorii medii,
dar în multe situaţii se doreşte obţinerea unui minim sau unui maxim garantat pentru cel puţin
un criteriu de performanţă. În unele situaţii se poate dori obţinerea unei variante mici între
valoarea medie şi valorile de minim sau de maxim.
În continuare vor fi prezentaţi şi exemplificaţi mai mulţi algoritmi de planificare.
Aceştia au fost simulaţi în C++ sub mediul de dezvoltare Devcpp 5.3 cu compilatorul TDM-
GCC pe 64 de biţi. Pentru realizarea diagramelor am folosit programul Gnuplot 4.6. şi un
program realizat în Python 3.3, pentru a translata datele dintr-un format .txt într-un format
.gpl, util programului de plotare.
12
Ca ipoteza se consideră 5 task-uri cu momentul de pornire un timp aleator cuprins
între 0 şi 399 unităţi de timp, cu o durată (care se consideră cunoscută) cuprinsă între 150 şi
500 u.t. şi cu prioritatea între 0 şi 16, din 4 în 4, 16 considerându-se prioritatea minimă, iar 0
prioritatea maximă. De asemenea, cuanta de timp se consideră de 50 u.t. şi se neglijează,
pentru moment, timpul utilizat de planificator şi de dispatcher pentru a schimba între task-uri.
În alegerea acestor mărimi s-a ţinut cont, în defavoarea unor studii şi referinţe pentru
sisteme de operare de pe piaţă (acestea fiind deseori valabile doar în situaţii specifice), doar
de respectarea condiţiilor tipice ce apar în execuţia task-urilor. Ca exemple în acest sens sunt
numărul relativ mic de priorităţi diferite, durata task-urilor comparabilă cu momentul creării
acestora şi mărimea cuantei de timp considerabil mai mică decât durata task-ului.
O altă notă importantă este faptul că nu se în calcul mărimea CPU burst-ului, ci mai
degrabă mărimea task-ului. Aşadar, sistemului simplificat îi lipseşte starea de „blocat pentru
I/O” rezultând diagrama de stări prezentată în figura 2.3.
Figură 2.3.Diagrama simplificată de stări
Criteriile de performanţă luate în considerare au fost timpul mediu de terminare şi
timpul mediu de răspuns. Procesorul se consideră ocupat în proporţie de 100%, neputându-se
lua nivelul de ocupare a CPU-ului drept criteriu iar, deoarece unitatea de timp aleasa este pur
conceptuală, nu se poate lua în calcul nici criteriul ratei de terminare a task-urilor.
2.1.2. Algoritmul FCFS
Unul dintre cei mai simplii algoritmi de planificare este algoritmul Primul Venit –
Primul Servit, (engl: First Come, First Served - FCFS). Acesta este de tip non-preemptiv şi
implică executarea task-urilor în ordinea în care acestea sunt create. Kernelul ţine o coadă de
13
tip FIFO în care sunt trecute task-urile pe măsură ce sunt create, pe o parte, şi din care sunt
şterse task-uri, pe măsură ce intră în execuţie, pe cealaltă parte.
Luăm exemplul a patru task-uri: A, B, C, D, de lungime 5, 1, 3, 2 ms care sunt create
în această ordine la momentul 0. În acest caz, procesele se vor executa precum se vede în
figura 2.4:
Figură 2.4. Ordinea de execuţie cu algoritmul FCFS
În acest caz, timpul de terminare pentru procesul A este de 5 ms, pentru procesul B, 6
ms, pentru procesul C, 9 ms iar pentru procesul D, 11 ms. Aşadar, timpul mediu de terminare
este (5 + 6 + 9 + 11) / 4 = 7.75 ms, iar timpul mediu de răspuns este (0 + 5 + 6 + 9) / 4 = 5 ms.
Simularea acestui algoritm a rezultat, conform aşteptărilor, într-un timp mediu de
terminare şi un timp mediu de răspuns relativ mari, 1047 u.t. respectiv, 650 u.t. Rezultatele
acestui algoritm depind foarte mult de ordinea în care sunt create task-urile şi durata lor, iar
optimizarea lui este practic imposibilă, considerându-i caracterul non-preemptiv. Simularea
acestui algoritm apare în figura 2.5.
14
Figură 2.5. Simularea algoritmului FCFS
2.1.3. Algoritmul SJF
Pentru a încerca scăderea timpului mediu de terminare şi a timpului mediu de răspuns,
s-a încercat prioritizarea task-urilor scurte, punându-le pe acestea înaintea task-urilor create
anterior, dar mai lungi. Acesta este principiul din spatele algoritmului Shortest Job First (SJF)
de tip preemptiv. Algoritmul verifică la fiecare creare de task, dacă acesta are cea mai scurtă
durată, comparându-i durata cu cea a task-ului curent, iar dacă are durata mai mică, se trece la
task-ului nou creat (de unde rezultă caracterul lui preemptiv). Deoarece, deseori, nu
cunoaştem durata task-ului, problema la acest algoritm e dată de estimarea acestui timp.
Aşadar se poate ajunge la pierderea unei părţi semnificative din puterea de procesare al
algoritmului de planificare, care este în sine greu de proiectat. De asemenea, acest algoritm nu
se recomandă aplicaţiilor de timp real, care impun constrângeri dure din cauza neglijării task-
urilor cu durată mare.
Pentru a funcţiona corespunzător, algoritmul mai necesită din partea kernelului un
vector în care sunt ţinute task-urile cu un câmp adiţional în care sunt trecute durata lor
estimată (sau dată).
15
Considerând acelaşi exemplu teoretic de mai devreme cu 4 task-uri, luate în ordinea
sosirii, A, B, C, D de durata 5, 1, 3, 2 şi utilizând algoritmul SJF, ele se vor executa în ordinea
B, D, C, A, cum se vede şi în figura 2.6.
Figură 2.6. Ordinea de execuţie cu algoritmul SJF
Timpul de terminare devine de 1 ms pentru procesul B, de 3 ms pentru D, respectiv 6
şi 11 ms pentru procesele C şi A. Prin urmare, timpul mediu de terminare devine (1 + 3 + 6 +
11) / 4 = 5.25 ms iar timpul mediu de aşteptare este (0 + 1 + 3 + 6) / 4 = 2.5 ms.
Implementarea acestui algoritm a rezultat într-un timp mediu de terminare de 940 u.t.
şi într-un timp mediu de aşteptare de 515 u.t., ambele fiind mai mici decât echivalentele lor în
algoritmul FCFS. Optimizarea acestui algoritm se realizează aproape exclusiv părţii
responsabile de predicţia duratei task-ului sau a duratei CPU burst-ului în cazul proceselor
dependente de I/O. Ordinea de execuţie se poate vedea în simularea din figura 2.7.
Figură 2.7. Simularea algoritmului SJF
16
Cum se vede şi din diagramă, sunt executate prioritar task-urile cu o durată mică. Ce
nu se poate observa, însă, este apelarea planificatorului la fiecare iniţializare de task, acesta
fiind chemat şi la momentul 334 odată cu iniţializarea task-ului 4 precum şi la momentul 369,
cu crearea task-ului 5. Asta duce la un număr dublu de apeluri ale planificatorului faţă de
algoritmul FCFS.
2.1.4. Algoritmi bazaţi pe priorităţi
Problema planificării se poate complica dacă este să luăm în calcul prioritatea
explicită a task-urilor. Algoritmii trataţi anterior aveau prioritatea egală, în cazul algoritmului
FCFS şi o prioritate implicită, dată de durată task-ului, în cazul algoritmului SJF.
Planificarea bazată pe priorităţi poate fi atât de tip non-preemptivă cât şi de tip
preemptivă, în prima situaţie, schimbarea cu task-ul cel mai prioritar din coadă de aşteptare
având loc doar la încheierea task-ului curent. În cazul preemptiv, schimbarea poate avea loc la
o întrerupere dată de expirarea unui timer sau, mai simplu, la crearea noului task (dacă acesta
este mai prioritar decât task-ul curent). La algoritmii bazaţi pe priorităţi poate apărea
problema "înfometării" task-urilor cu o prioritate scăzută, aceştia ajungând să nu se execute
decât după toate task-urile cu o prioritate crescută. Această problemă poate fi rezolvată
modificând dinamic prioritatea taskului, crescându-i prioritatea pe parcurs, când acesta nu se
execută (procedeu cunoscut drept „îmbătrânire”) sau modificând algoritmul prin introducerea
conceptul de cuanta de timp.
Considerând aceleaşi task-uri, cu durata de 5, 1, 3 şi 2 ms, le vom asigna priorităţile 2,
3, 1, 4 şi vom verifica priorităţiile doar la momentul creării task-urilor. Aşadar, ele se vor
executa în ordinea C, A, B, D potrivit priorităţii, cum reiese şi din figura 2.8.
Figură 2.8. Ordinea de execuţie cu algoritmul bazat pe priorităţi
17
Simulând algoritmul cu priorităţi, obţinem timpul mediu de aşteptare de 1167 u.t. şi
timpul mediu de răspuns de 770 u.t., lucru ilustrat şi în figura 2.9.
Figură 2.9. Simularea algoritmului bazat pe priorităţi
În acest exemplu priorităţile task-urilor de la 1 la 5 au fost 12, 8, 4, 4, 12.
Deşi se remarcă un timp mediu de aşteptare şi un timp mediu de răspuns mai mare
decât în ultimii algoritmi studiaţi, acest algoritm are printre cele mai bune performanţe în
sistemele de timp real, garantând un timp minim de răspuns pentru anumite task-uri critice.
2.1.5. Algoritmi de tip Round-robin
O clasă de algoritmi foarte des utilizaţi în prezent este cea de tip Round-robin. Aceştia
sunt algoritmi preemptivi ce implică schimbul între task-uri la un interval de timp stabilit.
Astfel, procesorul executa cuante din fiecare task din coadă, aflat în starea ready, pe rând.
Fiind folosiţi preferenţiabil în sisteme interactive, aceşti algoritmi au mai multe variaţiuni care
ţin sau nu cont de prioritatea task-urilor.
18
În figura 2.10 se poate observa succesiunea task-urilor executate pentru o cuantă de
timp de 50 u.t.
Figură 2.10. Simularea algoritmului Round-robin
Timpul de aşteptare în acest caz este mult mai mare, fiind proporţional cu numărul de
task-uri înmulţit cu durata medie a unui task, însă timpul de răspuns este mult mai mic, fiind
limitat la numarul de task-uri înmulţit cu mărimea unei cuante de timp. Algoritmii de tip
Round-robin pot fi optimizaţi pentru a corespunde cerinţelor sistemului variând mărimea
cuantei de timp pentru a obţine rezultate mai bune.
Aceşti algoritmi pot avea caracteristici de timp real, introducând conceptul de
prioritate. Aşadar se poate ajunge la creşterea dimensiunii cuantei de timp sau a numărului
acestora pentru task-uri cu o prioritate ridicată.
Un astfel de algoritm bazat pe priorităţi şi pe cuante de timp este cel de Lottery
scheduling, care oferă un număr mai mare de cuante de timp task-urilor prioritare. Acest
algoritm nu duce decât la performanţe sporite în medie pentru task-urile cu prioritate mare,
nefiind recomandat sistemelor de timp real. Totuşi, avem garanţia executării cel puţin timp de
o cuantă a tuturor proceselor într-un ciclu complet, rezolvând problema "înfometării".
19
În simularea acestui algoritm am ales acordarea unei cuante de timp task-urilor cu
prioritate 12, a doua cuante pentru prioritatea 8, şi a 4 şi 8 cuante pentru task-uri cu priorităţile
4 şi 0. Ordinea de execuţie este vizibilă în figura 2.11.
Figură 2.11. Simularea algoritmului Lottery Round-robin
2.1.6. Algoritmi de tip coada multinivel
Algoritmii studiaţi până acum au constant în menţinerea de către sistemul de operare a
unei singure cozi sau a unui vector care să conţină informaţii despre toate procesele din
memorie.
O altă abordare implica împărţirea task-urilor în mai multe cozi şi executarea lor într-o
manieră ierarhică. Acest lucru este facilitat de separarea relativ facilă a task-urilor în mai
multe categorii. Cea mai simplă categorisire ar fi împărţirea în task-uri interactive ce rulează
în „foreground” şi în task-uri ne-interactive ce rulează în „background”.
Modalitatea de execuţie este simplă, existând un algoritm de planificare între cozi. Cel
mai adesea acesta este bazat pe priorităţi fixe, aşadar se execută procese din coadă cea mai
prioritară, abia la finalizarea tuturor acestora putând rula procese din coadă imediat
20
următoare, s.a.m.d. O altă variantă este executarea după o manieră de tip Round-Robin cu
priorităţi între cozi, spre exemplu acordarea primei cozi a 80% din timpul pe procesor, iar
celei de-a două cozi, a restului de 20% într-o structură cu două cozi. În cadrul fiecărei cozi se
poate implementa câte un alt algoritm de planificare, rezultate bune fiind obţinute cu algoritmi
de tip Round-Robin pentru primele cozi şi cu algoritmul FCFS pentru ultimele cozi. În figura
2.12 apar reprezentate grafic cele 3 cozi ale kernelului în care se vor păstra date despre
procese.
Figură 2.12. Algoritmul de tip coadă multinivel
Pentru a acorda o flexibilitate mai mare algoritmului coada multinivel, se permite
schimbarea dinamică a task-urilor între cozi. Acest lucru poate avea loc după o perioadă de
timp, când unui task îi creşte prioritatea datorită „îmbătrânirii” sau explicit, printr-un apel de
sistem din interiorul task-ului. Algoritmul rezultat poartă denumirea de algoritm coada
multinivel cu reacţie (engl: multilevel feedback-queue scheduling algoritm).
Figură 2.13. Algoritmul de tip coadă multinivel cu feedback
21
2.2. Compararea algoritmilor
Deoarece avem un singur set de valori simulat pe algoritmi cu intrări aleatoare, alegem
să formulăm o concluzie pe o analiză statistică. Aşadar, pentru a obţine un set de măsurători
cu nivel ridicat de încredere, formulam problema cu 10 task-uri şi efectuăm măsurătorile de
10 de ori pentru fiecare din cei 5 algoritmi.
Măsurând timpul mediu de terminare, 𝑡𝑡, obţinem setul de date din tabelul 2.1
Algoritm 𝑡𝑡
Test 1 Test 2 Test 3 Test 4 Test 5 Test 6 Test 7 Test 8 Test 9 Test 10
FCFS 1803 1787 1741 1497 1395 1697 2031 1485 1412 1720
SJF 1348 1543 1261 1346 1455 1351 1105 1420 1144 1255
Priority Based 1813 1911 1723 1251 1572 1392 2054 1492 1566 1639
Round-Robin 2445 2460 2315 2577 2699 2265 2735 1992 2188 3506
Lottery RR 1760 2131 2071 2428 2601 2231 2860 2157 2129 2561
Tabel 2.1. Timpurile medii de terminare pentru algoritmii de planificare
Iar pentru timpul mediu de răspuns, 𝑡𝑟, avem valorile:
Algoritm 𝑡𝑟
Test 1 Test 2 Test 3 Test 4 Test 5 Test 6 Test 7 Test 8 Test 9 Test 10
FCFS 1465 1445 1404 1217 1127 1338 1636 1154 1117 1403
SJF 974 1204 969 973 1135 1038 814 1078 727 936
Priority Based 1297 1421 1245 953 1227 1044 1464 1085 908 1296
Round-Robin 108 145 113 128 115 87 53 155 97 77
Lottery RR 316 182 351 263 341 314 157 527 277 366
Tabel 2.2. Timpurile medii de răspuns pentru algoritmii de planificare
22
Efectuând media tuturor testelor şi calculând abaterea medie pătratica pentru fiecare
set de 10 teste cu ecuaţia 2.1 obţinem datele din tabelul 2.3. Abaterea medie pătratică, în acest
context, are rolul de a stabili nivelul de dispersie a valorilor, permiţându-ne să facem afirmaţii
clare pe baza unor seturi de valori.
𝜎(𝑋) = √1
𝑛(∑ (𝑋 − �̅�)2𝑛
𝑖=1 (2.1)
În ecuaţia 2.1, σ(X) este abaterea medie pătratică a variabilei X, acesta fiind, pe rând,
𝑡𝑡 si 𝑡𝑟, iar �̅� reprezintă media celor n măsurători.
Algoritm 𝑡�̅� 𝜎(𝑡𝑡) 𝑡�̅� 𝜎(𝑡𝑟)
FCFS 1656,8 193.5 1330,6 163.2
SJF 1322,8 128.5 984,8 134,4
Priority Based 1641,3 229.4 1194 179,8
Round-Robin 2518,2 394.8 107,8 29.3
Lottery RR 2292,9 302.5 309,4 98
Tabel 2.3. Media si abaterea medie pătratică a măsurătorilor
Pentru a formula concluzii din acest tabel alegem sa luăm in calcul doar algoritmii
care nu ţin cont de prioritatea explicită a task-urilor. Deoarece aceasta nu apare în formulele
pentru a calcula cei doi indici de performanţă, raportat la timpul mediu de terminare şi la
timpul mediu de răspuns, vom avea rezultate mai slabe.
Algoritm 𝑡�̅� 𝜎(𝑡𝑡) 𝑡�̅� 𝜎(𝑡𝑟)
FCFS 1656,8 193.5 1330,6 163.2
SJF 1322,8 128.5 984,8 134,4
Round-robin 2518,2 394.8 107,8 29.3
Tabel 2.4. Măsurătorile algoritmilor FCFS, SJF si RR
Din acest ultim tabel, se poate observa că algoritmul FCFS are atât timpul mediu de
terminare cât şi timpul mediu de răspuns mai mari decât în cazul algoritmul SJF. De
asemenea, algoritmul Round-robin duce la un timp mediu de aşteptare mai mare decât ceilalţi
23
doi algoritmi, dar la un timp mediu de răspuns mult mai mic. Aceste concluzii ţin cont de
media ± abaterea medie pătratică pentru cele trei seturi de valori.
Pentru a ilustra ordonarea timpului mediu de aşteptare pentru cei trei algoritmi am
plasat pe acelaşi grafic funcţia densitate de probabilitate pentru cele trei seturi de valori.
Figură 2.14. Funcţia de probabilitate a 𝑡�̅� pentru cei trei algoritmi
24
Figură 2.15. Funcţia de probabilitate a 𝑡�̅� pentru cei trei algoritmi
Graficele au fost realizate folosind metoda neparametrică kernel density estimation
(KDE) pentru a obţine densitatea de probabilitate pentru o serie de variabile aleatoare.
O altă observaţie este că algoritmul bazat pe cuante de timp fără priorităţi (Round-
robin) are timpul mediu de răspuns mult mai mic decât primii doi algoritmi. Acest lucru este
datorat limitării timpului de răspuns la numărul de taskuri înmulţit cu mărimea cuantei de
timp, cel din urmă fiind mic relativ la durata unui task. Tot despre algoritmul Round-robin se
poate spune că are cel mai mare timp de terminare dintre cei cinci algoritmi studiaţi.
Realizând o comparative între cei doi algoritmi bazaţi pe cuante de timp, anume
Round-robin şi Lottery Round-robin, observăm că media timpilor de terminare este puţin mai
mare în cazul algoritmului Round-robin, cea ce era de aşteptat, având în vedere preferinţa
algoritmului Lotterry RR pentru anumite task-uri.
25
Figură 2.16. Funcţia de probabilitate a 𝑡�̅� pentru RR, respectiv Lottery RR
În cazul timpului mediu de răspuns, pentru algoritmii Lottery RR respectiv RR, se
obţin rezultate mai bune pentru cel din urmă.
Figură 2.17. Funcţia de probabilitate a 𝑡�̅� pentru RR si pentru Lottery RR
26
2.3. Condiţiile de timp real
Sistemele de timp real se caracterizează prin necesitatea obţinerii unui rezultat într-un
interval stabilit. Pentru ele, respectarea acestui timp minim impus este la fel de importantă ca
şi corectitudinea rezultatelor [3]. Ele se împart în sisteme cu constrângeri dure si sisteme cu
constrângeri lejere.
În sistemele cu constrângeri dure (engl: Hard Real-time) ratarea termenului de predare
a rezultatelor poate duce la situaţii catastrofale iar prin proiectarea lor trebuie să se prevină
astfel de situaţii. Exemple în acest sens sunt sistemul de control al unei centrale nucleare sau
sistemul de deschidere a airbag-urilor într-o maşină. În sistemele cu constrângeri lejere (engl:
Soft Real-time) pe de altă parte, se permite depăşirea termenului, ocazional. Acest lucru
ducând doar la scăderea calităţii serviciului oferit. Printre exemplele de sisteme de timp real
cu restricţii lejere putem enumera monitoarele de supraveghere video sau telecomunicaţiile.
În figura 2.18 apare executarea unui task periodic având constrângeri de timp real. S-a
notat cu 𝑡𝑎timpul de aşteptare pentru apariţia evenimentului, cu C timpul de execuţie sau
timpul de calcul iar cu D timpul limită maxim (engl: deadline). Condiţia pentru respectarea
cerinţei de timp real este ca 𝑡𝑎 + C < D.
În figura 2.18 apare executarea unui task periodic având constrângeri de timp real. S-a
notat cu 𝑡𝑎timpul de aşteptare pentru apariţia evenimentului, cu C timpul de execuţie sau
timpul de calcul iar cu D timpul limită maxim (engl: deadline). Condiţia pentru respectarea
cerinţei de timp real este ca 𝑡𝑎 + C < D.
Figură 2.18. Constrângerile de timp real
27
În sisteme cu astfel de constrângeri, sistemul de operare, numit şi RTOS (Real Time
Operating System) trebuie să ne asigure facilităţi pentru garantarea nevoilor de timp real. Mai
precis ele trebuie să aibă un sistem de priorităţi care să asigure un timp minim de execuţie
task-urilor prioritare.
În majoritatea microcontrolerelor este prevăzut un astfel de sistem, numit sistem de
întreruperi, care permite întreruperea asincronă a programului principal şi schimbarea fluxului
de control către un alt program. Aceste întreruperi funcţionează după o regulă absolută de
priorităţi: orice întrerupere cu o prioritate mai mare se poate executa peste o întrerupere cu o
prioritate mai mică.
Luând în calcul proiectarea pe un microcontroler cu un sistem de întreruperi,
proiectantul sistemului de operare trebuie să implementeze un sistem echitabil de planificare
pentru task-uri cu aceeaşi gamă de priorităţi (de regulă scăzută).
Dintre algoritmii studiaţi, FCFS şi SJF pot duce la executarea întârziată a unor task-
uri prioritare, iar Lottery Round-robin este nedetermist. Totuşi se poate implementa cu succes
algoritmul bazat pe priorităţi pentru task-uri cu priorităţi diferite şi algoritmul Round-robin
pentru task-uri cu aceeaşi prioritate.
28
3 Implementarea Microkernelului
În ciclul de viaţă al unui proiect trebuie urmărite o serie de etape bine stabilite pentru a
asigura îndeplinirea obiectivelor cu succes. Aceste etape sunt de regulă de analiză, proiectare,
implementare şi de testare. Însă ciclu de viaţă nu se termină odată cu implementarea efectivă a
soluţiei, ci se continua cu etapa de mentenanţă post-implementare. Aceasta constă în
îmbunătăţirea facilitaţilor deja existente, corectarea unor erori imposibil de prevăzut în
momentul proiectării sau dezvoltarea ulterioară a proiectului.
În cadrul implementării microkernelului am folosit tehnica proiectării în spirală.
Aceasta a constat în realizarea mai multor prototipuri unul după altul, fiecare fiind realizat
prin cei patru paşi definiţi anterior.
3.1. De ce un microkernel?
Actualmente, datorită abundenţei sistemelor de operare şi a utilizării lor într-un mod
generalizat pe sisteme cu microprocesoare, producătorii de chipuri au implementat suport
direct pe procesor pentru funcţiile acestora. Un exemplu concret este capacitatea de a scrie
cod protejat sau neprotejat prin modificarea unui bit dintr-un registru intern.
Pentru a coordona resursele unui calculator, sistemele de operare trebuie să aibă acces
de scriere/citire asupra programelor utilizator, dar pentru a fi protejate de erori umane, trebuie
să nu poată fi modificate de acestea. Acest lucru duce la o primă clasificare a sistemelor de
operare între sisteme de operare scrise în întregime în cod privilegiat, aşa numitele kernele
monolitice (dintr-o singură bucată) şi sisteme de operare scrise parţial în cod protejat. Pentru
ultima categorie, se face distincţia clară între kernel (numit microkernel datorită dimensiunii
reduse) şi restul sistemului de operare, scris în cod neprotejat.
A treia categorie reprezintă o combinaţie a celor două abordări, având componentele
esenţiale, dar şi o parte a elementelor neesenţiale ale sistemului scrise în cod protejat.
29
În figurile 3.1, 3.2 şi 3.3 sunt reprezentate grafic cele trei mari categorii de sisteme de
operare, sursa bibliografică utilizată fiind [19]. În zona colorată cu roşu apar componentele
sistemului de operare scrise în cod protejat iar în zona colorată cu galben sunt trecute
elementele scrise în cod utilizator sau neprotejat.
Figură 3.1. Sistem de operare monolitic
Figură 3.2. Sistem de operare de tip microkernel
30
Figură 3.3. Sistem de operare de tip hibrid
Datorită dimensiunilor reduse şi a modularităţii microkernelelor, acest tip de sistem de
operare este cel mai adesea folosit în sistemele integrate. Printre versiunile cunoscute de
microkernele putem enumera QNX, MINIX, Symbian, ThreadX şi FreeRTOS. Pentru o
arhitectură dată, acestea pot varia ca mărime între câteva zeci de KB până la câteva sute KB.
Din cauza cerinţelor diferite ce pot să apară în proiectarea sistemele integrate, o
practică des întâlnită este conceperea separată a sistemului de operare, în defavoarea utilizării
unei versiuni existente de pe piaţă. Proiectantul sistemului de operare, poate alege, aşadar,
metoda de implementare a task-urilor, de alocare a memoriei, algoritmul de planificare a task-
urilor precum şi eventuale componente din afara microkernelului (spre exemplu un sistem de
fişiere).
3.2. Componenta Hardware
Microcontrolerul ales pentru a implementa sistemul de operare este STM32-F107 şi
este integrat pe o plăcuţă de dezvoltare STM32-H107, amândouă produse de Olimex.
Acest microcontroler utilizează un procesor de tip Cortex-M3 interfaţat cu o memorie
de program de 256 KB de tip Flash şi cu 64 KB de memorie de date de tip SRAM. Sursele
primare de ceas constau dintr-un oscilator de cuarţ extern cu frecvenţa de 25MHz si din un
31
oscilator intern RC cu frecvenţa de 8 Mhz. Printre alte periferice putem enumera 10 timere
din care 4 sunt de uz general, 2 CAN-uri pe 12 biţi ce pot analiza până la 16 canale externe, 2
DAC-uri pe 12 biţi şi un senzor de temperatură. Comunicarea cu exteriorul se poate realiza
prin trei porturi SPI, două porturi I²C, şi printr-un port MII ce ne permite accesul pe Ethernet.
Pinii de I/O sunt configuraţi pe 5 porturi numerotate de la A la E cu 8 biţi fiecare. Pentru a
vedea uşor parametrii de stare ai microcontrolerului, plăcuţa mai are 2 LED-uri de culori
diferite.
Tensiunea de utilizare este de 2-3.6V (3.3V in mod nominal) pentru alimentare şi
nivelul logic "1". Aceasta tensiune este asigurată printr-un transformator alimentat prin USB.
În starea nealimentata, microcontrolerul poate asigura tensiune unui număr de 41 de regiştrii
pe 16 biţi şi unui oscilator 32.768 Khz utilizând o baterie internă.
Frecvenţa utilizată în cadrul proiectului a fost de 37.5 Mhz, obţinută folosind un
multiplicator de frecvenţă, de la oscilatorul extern de 25 Mhz.
Figură 3.4. Plăcuţa de dezvoltare STM32-H107.
Sursa pozei este [20]
32
O altă componentă hardware folosită a fost debugger-ul pe JTAG ST-Link/v2 produs
tot de Olimex. Acesta se conectează la portul JTAG al microcontrolerului pentru a avea
control şi acces nemijlocit asupra resurselor microcontrolerului utilizând magistrala internă a
procesorului. Prezentată în figura 3.5, aceasta componentă e folosită pentru programarea
microcontrolerului şi mai asigură depanarea programului prin funcţiile de executare pas cu
pas şi prin introducerea breakpoint-urilor.
Figură 3.5. Programatorul/Depanatorul ST/Link v2.
Sursa imaginii este [21]
Pentru a facilita programarea sa, microcontrolerul mai este prevăzut cu un bootloader
în ultimii 2 KB (numită şi zona de memorie de sistem) ai memoriei Flash. Acesta iniţializează
regiştrii interni ai procesorului precum şi regiştrii interfeţei seriale de comunicaţie USART
pentru a permite comunicare cu PC-ul.
Tabelul 3.1, luat din [12] ne prezintă zone de memorie la care putem sării la
alimentarea microcontrolerului, setând pinii B0 şi B1 prin intermediul unor jumperi.
Boot mode selection pins Boot mode
BOOT1 (B1) BOOT0 (B0)
X 0 User Flash memory
0 1 System memory
1 1 Embedded SRAM
Tabel 3.1. Modurile de pornire pentru microcontrolerul STM32-F107
33
Deoarece nu vom folosi interfaţa serială USART pentru programare şi dorim
executarea programului din memoria Flash pinul B0 va fi setat pe 0.
3.2.1. Arhitectura Cortex-M3
Cel mai important element al microcontrolerului este procesorul Cortex-M3. Acesta
implementează arhitectura ARMv7 de tip RISC pe 32 de biţi. Spaţiul de adrese este tot pe 32
de biţi, ducând la o zonă adresabilă de 4GB de la 0x00000000 la 0xFFFFFFFF pentru cele
două memorii. Acestea sunt adresate prin magistrale diferite datorită arhitecturii ARMv7 de
tip Harvard. În cazul microcontrolerului STM32-F107, memoria Flash ocupă zona de la
0x08000000 până la 0x0803FFFF iar memoria SRAM de la 0x20000000 până la
0x2000FFFF.
Printre elementele strâns legate de procesor, putem enumera NVIC-ul (Nested
Vectored Interrupt Controller) tabela ROM precum şi mai multe componente cu scopul de a
ajuta in depanarea programului. Dintre acestea, NVIC-ul reprezintă elementul însărcinat cu
prioritizarea şi trimiterea întreruperilor către procesor, acesta putând configura intre 1 si 240
de întreruperi externe.
Trecând scurt în revistă setul de instrucţiuni ARMv7-M, acesta suporta atât
instrucţiuni pe 16 biţi (Thumb şi Thumb2) utile pentru a mării densitatea codului cât şi pe 32
de biţi. Cât despre microarhitectură, elementele semnificative ale acesteia sunt: specularea
branch-urilor şi pipeline-ul cu 3 stagii: Instruction Fetch, Instruction Decode şi Instruction
Execute. Cunoaşterea acesteia din urmă este importantă pentru măsurarea corectă a duratei
unor instrucţiuni cu restricţii legate de pipeline. Etapele pipeline sunt reprezentate în figura
3.6.
34
Figură 3.6. Stagiile pipeline pentru instrucţiunile ARMv7.
Sursa pentru imagine este [11]
Microcontrolerele cu procesoare ce implementează setul de instrucţiuni ARMv7-M
prezintă o serie de avantaje faţă de alte microcontrolere de pe piaţă, cum ar fi un raport putere
de calcul/energie consumată foarte bun precum şi documentaţie şi suport amplu în
compilatoare. În cazul de faţă, a fost ales un microcontroler cu un procesor Cortex-M3 din
cauza suportului nativ al acestuia pentru sistemele de operare.
În mod concret acesta prezintă, asemenea arhitecturilor ARM anterioare, două niveluri
de protecţie a codului. Nivelul protejat aparţine exclusiv funcţiilor de întrerupere şi a altor
tipuri de excepţii, el fiind propice scrierii codului sistemului de operare, iar nivelul neprotejat
aparţine restului aplicaţiilor, el putând fi executat şi de funcţiile de întrerupere.
Alt aspect important sunt întreruperile SysTick şi PendsSV implementate. Ele fac
parte din grupul predefinit de întreruperi, care ocupa primele 15 priorităţi din totalul celor 255
de întreruperi posibile. Întreruperea Systick este generată când timer-ul pe 24 de biţi numit tot
SysTick ajunge la 0. Acestui timer îi se poate configura durata precum şi sursa de ceas. Pentru
35
a ţine microcontrolerul funcţional într-o stare latentă în lipsa alimentării sau pentru a avea o
cuantă de timp bazată pe multiplii/submultiplii de o secundă, putem utiliza RTC-ul (Real
Time Clock-ul) integrat pe cip ca sursă de ceas pentru SysTick. Cealaltă întrerupere, numită
PendSV poate fi utilizată de programator pentru a apela "manual" scheduler-ul. Aceste două
întreruperi au priorităţile -1 respectiv -2, fiind executate înaintea tuturor întreruperilor
configurabile de utilizator.
Procesorul Cortex-M3 mai prezintă suport pentru sistemele de operare sub forma a doi
pointeri pentru stivă: Main Stack Pointer (MSP) şi Process Stack Pointer (PSP). Aceştia sunt
amândoi adresabili în zona registrului Stack Pointer (SP), cum se vede şi în figura 3.7, luată
din documentul [14]
Figură 3.7. Regiştrii procesorului Cortex-M3
După un restart, procesorul trece automat la utilizarea MSP-ului, acesta putând fi
folosit atât din cod privilegiat, cât şi din cod neprotejat. PSP-ul, în schimb, poate fi utilizat
doar din cod neprotejat, acesta fiind recomandat în executarea proceselor. Deoarece nu am
utilizat în mod separat un thread pentru sistemul de operare, acesta fiind scris în zona
funcţiilor de excepţie, se va folosi în toate cazurile, stiva principală (MSP).
36
3.3. Componenta Software
În proiectarea microkernelului, se va folosi întreruperea SysTick pentru implementarea
unui algoritm de tip Round-robin, urmând ca la reviziile ulterioare să se poată implementa alţi
algoritmi preemptivi, utilizând întreruperea PendSV. Algoritmul Round-robin a fost ales
datorită caracterului său determinist, al timpului mic de schimbare între task-uri precum şi
datorită caracteristicilor sale de timp-real.
Proiectul a fost scris în C++ şi în limbaj de asamblare şi compilat în mediul de
dezvoltare CooCox. Acesta a mai ajutat şi la programarea respectiv depanarea pas cu pas a
programului, împreună cu programatorul ST-Link/v2. Limbajul predominant folosit a fost
C++, iar pentru salvarea şi încărcarea regiştrilor s-a folosit limbajul de asamblare specific
arhitecturii ARMv7. O notă importantă aici este necesitatea dezactivării opţiunii de
optimizare a codului produs de compilator pentru a evita situaţii neprevăzute.
3.3.1. Schimbarea contextului
Într-un microkernel, planificatorul de thread-uri este componenta ce aloca pe procesor
task-urile după un algoritm dat. Pentru realizarea acestui ţel, el se foloseşte de o altă
componentă, numită dispatcher pentru a salva starea task-ului curent şi a încărca starea task-
ului următor.
Contextul, sau starea procesului, e păstrat în cei 16 + 1 regiştrii ai procesorului.
Dispatcherul trebuie să asigure, aşadar, salvarea conţinutului regiştrilor R1-R13 precum şi a
regiştrilor LR (Link Register), PC (Program Counter), LR (Link Register) PSR (Program
Status Register), şi să încarce aceiaşi regiştri ai următorului thread în procesor. Pe de altă
parte, planificatorul, trebuie să asigure alegerea corectă a următorului task pentru execuţie
precum şi actualizarea tabelei de procese cu noua stare a task-urilor.
Aceste operaţii trebuie realizate utilizând cât mai puţine instrucţiuni pentru a asigura
fluenţa rulării programelor şi dimensiunea redusă a microkernelului.
Sistemul de operare va implementa un tabel central pentru a ajuta cunoaşterea
numărului şi stărilor task-urilor. Acesta este definit ca o structură având câmpurile
37
stack_pointer şi flag. Rolul câmpului stack_pointer este intuitiv, acesta păstrând un pointer
către stiva unui task, iar câmpul de flag-uri ne spune dacă task-ul respectiv este gata sau nu de
execuţie, în funcţie de ultimul bit.
Trecerea la următorul thread se concretizează prin următorii paşi:
a. Salvarea regiştrilor pe stivă principală
b. Trecerea în tabela de procese a nivelului stivei procesului curent
c. Căutarea următorului proces liber de execuţie în tabela de procese
d. Trecerea în registrul de stivă al procesorului a nivelului noii stive
e. Încărcarea restului regiştrilor în procesor
În prima etapă, precum şi în ultima, trebuie să fie încărcaţi explicit doar regiştrii de la
R5 la R11 inclusiv. De restul regiştrilor se ocupă automat procesorul la executarea întreruperii
SysTick. Acest lucru este reprezentat în figura 3.8, luată şi modificată din [22].
Figură 3.8. Schimbarea contextului in procesorul Cortex-M3
38
În figura de mai sus, in dunga neagră îngroşată, dintre R11 si R0, se află variabilele
locale utilizate in funcţia de întrerupere
Codul utilizat pentru salvarea regiştrilor apare mai jos în două segmente de limbaj de
asamblare:
asm volatile
(
"MRS %0, msp\n\t"
"STMDB %0!, {r5-r11}\n\t"
"MSR msp, %0\n\t" : "=r" (rest)
);
asm volatile
(
"MRS %0, msp\n\t"
"LDMFD %0!, {r5-r11}\n\t"
"MSR msp, %0\n\t" : "=r" (rest)
);
Prima instrucţiune, în ambele cazuri mută conţinutul registrului special MSP în
registrul general R4 (notat aici cu %0), acesta din urmă va trebui definit ca o variabilă în
codul C++. A doua instrucţiune în cele două segmente de cod abreviază STore Multiple
Decrement Before, respectiv LoaD Multiple Full Descending stack. Aceste instrucţiuni duc la
adăugarea în stivă, respectiv retragerea din stiva a regiştrilor R5-R11 şi la actualizarea adresei
finale a stivei în registrul %0. Ultima instrucţiune, în ambele segmentele de limbaj de
asamblare, duce la reactualizarea pointerului spre stiva principală (MSP).
Paşii 2, 3 şi 4 constau în salvarea pointerului stivei procesului curent, în deciderea
procesului următor (îl vom luăm pe următorul liber, datorită algoritmului Round-robin) iar la
sfârşit în scrierea în registrul de stivă, MSP, a nivelul stivei noului task ales.
Citirea şi scrierea pointerului stivei de proces se realizează trivial, utilizând un bloc în
limbaj de asamblare asemănător celui anterior rezultatul salvându-se sau încărcându-se in
task_table[task_curent].stack_pointer.
Aceşti trei paşi sunt reprezentaţi în codul următor:
39
void *ptr1, *ptr2;
asm volatile ("MRS %0, msp\n\t" : "=r" (ptr1) );
task_table[task_curent].stack_pointer = ptr1;
do
{
task_curent++;
if (task_curent == NO_TASKS )
task_curent = 1;
if (task_table[task_curent].flag & READY)
break;
}
while(1);
ptr2 = task_table[task_curent].stack_pointer;
asm volatile ("MSR msp, %0\n\t" : : "r" (ptr2) );
Logica programului constă din căutarea următorului proces gata de execuţie într-o
buclă infinită. Această buclă se reia automat când se ajunge la ultimul task al tabelei. Dacă
dorim implementarea unui task auxiliar pentru funcţiile kernelului, acest lucru poate avea loc
în acest pas.
Deoarece, în C++, variabilele locale precum şi parametrii funcţiilor se păstrează în
stivă, am evitat apelul funcţiilor şi am folosit un număr minim necesar de variabile în cadrul
funcţiei de întrerupere. Aşadar, se evita încărcarea inutilă a stivelor proceselor.
3.3.2. Iniţializarea task-urilor
Iniţializarea task-urilor are loc după iniţializarea sistemului şi înainte de lansarea in
execuţie a task-ului idle şi a planificatorului.
Prototipul funcţiei de iniţializare are forma:
void Init_Task(int nr, uint32_t stack_adr, void (*cod_functie)(int))
unde nr este numărul sau id-ul task-ului, stack_adr reprezintă adresa stivei task-ului,
iar (*cod_functie)(int) este un pointer către codul task-ului respectiv.
Complementar cu funcţia de iniţializare, avem funcţia de ştergere a task-ului,
40
void Delete_Task(int nr)
unde nr reprezintă din nou, id-ul task-ului.
Iniţializarea task-ului implică în primul rând iniţializarea tabelei kernelului, anume a
câmpurilor stack_pointer şi flag pentru task-ul cu id-ul nr. Pentru a asigura funcţionarea
planificatorului şi a dispatcherului, tot în acest pas trebuie să se iniţializeze stiva. Acest lucru
se realizează scriind la adresa respectivă folosind pointeri în C++.
Datele care trebuie iniţializate se împart în trei grupe. În ordine, avem regiştrii R5-R11
pe care îi vom încărca în interiorul funcţiei întreruperii. În al doilea rând trebuie rezervate
cinci adrese de memorie pentru variabilele din cadrul handlerului de întrerupere precum şi o
adresă pentru a trece adresa stivei de la întoarcere din întrerupere (în cazul de faţă stack_adr +
84). La sfârşit trebuie puşi, R0, R1, R2, R3, LR, PC, xPSR, în ordinea aceasta precum şi
adresa stivei înainte de întrerupere. Aceşti regiştrii, precum şi primul argument al task-ului,
care va fi id-ul lui, ne obligă să rezervăm o mărime minimă pentru stivă de 24*4 octeţi, la care
se mai adăugă câte 4 octeţi pentru fiecare variabilă de tip uint32_t din cadrul task-ului.
Scrierea la o adresă de memorie se realizează utilizând codul:
adr1 = stack_adr;
p_adr1 = (uint32_t*)adr1;
*p_adr1 = 0;
unde adr1 reprezintă adresa la care se face scrierea iar *p_adr1 este pointerul care
reprezintă datele scrise de la adresa respectivă.
Majoritate adreselor de memorie salvate pentru regiştrii pot fi iniţializaţi cu 0, cu
excepţia zonei pentru registrul PC (căruia îi se atribuie pointerul către codul task-ului), pentru
registrul xPSR care conţine flag-urile programului, precum şi zona în care se va trimite primul
parametru al funcţiei şi două zone care sunt rezervate adresei de întoarcere în stivă după
întrerupere.
41
Funcţia de ştergere a task-ului se scrie de utilizator la sfârşitul thread-ului respectiv şi
duce la punerea pe „0” a flag-ului din tabela de procese şi intrarea într-o buclă infinit până la
următoarea întrerupere Systick.
3.3.3. Mecanisme de sincronizare
Pentru sincronizarea task-urilor, în sistemele de operare există conceptul de
semafoare. Acestea au două primitive, P şi V, numite şi wait şi signal.
Primitiva P impune un punct de aşteptare în cadrul unui thread. Acest thread nu se va
mai executa până nu se activează semnalul P al aceluiaşi semafor (dintr-un alt thread) pentru
a-l debloca.
Implementarea acestor funcţii se realizează incrementând o variabilă, numită semafor,
în cazul primitivei V. În cazul funcţiei P, se verifică dacă valoarea semaforului este pozitivă,
iar dacă condiţia se respectă, semaforul se va decrementa.
O variantă simplificată este cea a semafoarelor binare, ce le atribuie acestora valorile
de „0” şi „1”. Un semafor cu valoarea de „0” se va considera blocat, ducând la oprirea thread-
ului ce conţine primitivă de wait (P), iar un semafor cu valoarea de „1” se va considera
deblocat, permiţând trecerea de funcţia P, funcţie care va bloca, după ea, semaforul. Identic ca
în cazul anterior, primitivă V, va incrementa semaforul.
Pentru a nu afecta executarea funcţiilor semafoarelor, operaţiile din funcţiile P şi V
trebuie să aibă loc fără să poată fi întrerupte de către planificator. Acest lucru a fost realizat în
implementarea microkernelului, oprind întreruperea SysTick, prin intermediul registrul
SYST_CSR (SysTick Control and Status Register) cu codul:
void Disable_intr(void)
{
uint32_t *p_SYST_CSR, SYST_CSR;
SYST_CSR = 0xE000E010;
p_SYST_CSR = (uint32_t*)SYST_CSR;
*p_SYST_CSR = *p_SYST_CSR & 0xFFFFFFFE;
}
42
pentru oprirea întreruperii, respectiv codul:
void Enable_intr(void)
{
uint32_t *p_SYST_CSR, SYST_CSR;
SYST_CSR = 0xE000E010;
p_SYST_CSR = (uint32_t*)SYST_CSR;
*p_SYST_CSR = *p_SYST_CSR | 1;
}
pentru reactivarea întreruperii SysTick.
În cadrul microkernelului, am ales implementarea cu semafoare binare. Acestea au
avantajul utilizării unui singur bit pentru starea semaforului şi am folosit acest lucru pentru a
implementa 32 de semafoare într-o singură locaţie de memorie, numită ADR_SEM. Codul
pentru funcţiile de Wait şi Signal este reprezentat mai jos:
void Sem_signal(int nr) // V
{
uint32_t com, nr_sem, *p_com;
nr_sem = 1<<nr;
Disable_intr();
com = ADR_SEM;
p_com = (uint32_t*)com;
*p_com = *p_com | nr_sem;
Enable_intr();
}
void Sem_wait(int nr) // P
{
uint32_t com, nr_sem, *p_com;
nr_sem = 1<<nr;
Disable_intr();
com = ADR_SEM;
p_com = (uint32_t*)com;
Enable_intr();
while ((*p_com & nr_sem) == 0) ;
*p_com = *p_com & (~nr_sem);
}
43
Metoda de implementare aleasă foloseşte numere pentru identificarea semafoarelor, în
defavoarea string-urilor. Aceste numere pot fi cuprinse între 0 şi 31 şi corespund unui singur
bit dintr-o adresă de memorie, pentru a economisi spaţiu.
Un alt mecanism de sincronizare implementat este mutex-ul. Denumirea lor reprezintă
prescurtarea de la MUTual Exclusion, şi precum le sugerează şi numele, sunt folosite pentru a
asigura accesul exclusiv la o zonă de date folosită în comun de mai multe thread-uri, [4]
Altfel spus, mutex-urile pot fi considerate asemănătoare semafoarelor binare, având în
anumite sisteme de operare aceeaşi implementare. O diferenţă importantă, este însă, conceptul
lor de „proprietate”. Altfel spus, un mutex este „deţinut” de un thread, pe când în cazul unui
semafor, cele două primitive apar deseori în thread-uri diferite.
Primitivele elementare ale mutex-urilor sunt:
Mutex_lock – asigură acces unic thread-ului din care se apelează asupra unei resurse
partajate. Trebuie să fie urmat de Mutex_unlock
Mutex_unlock – marchează sfârşitul zonei de excludere mutuală. Trebuie să fie
precedat de Mutex_lock
Pentru a evita complicarea inutilă a microkernelului, am implementat aceste două
funcţii oprind semnalul de întrerupere în cazul Mutex_lock, şi repornind acelaşi semnal în
cazul Mutex_unlock. Aceasta implementare este diferită de implementarea „standard” a
mutex-urilor, însă prezintă avantaje de simplitate şi rapiditate în apelul celor două funcţii.
Însă, implementând astfel mutex-urile, obligăm utilizatorul să le utilizeze doar pentru
segmente mici de cod (condiţie adevărată şi în general pentru mutex-uri) şi să nu uite funcţia
de Mutex_unlock după terminarea operaţiilor pe resursa partajată (pentru a nu altera
funcţionalitatea microkernelului).
3.4. Modul de utilizare
Ca un rezumat la subcapitolele 3.3.2 şi 3.3.3, se reiau în acest capitol elementele
microkernelului de interes pentru utilizator. Interfaţa cu acesta se realizează cu următoarele
şase funcţii:
44
void Init_Task(int nr, uint32_t stack_adr, void (*cod_functie)(int))
void Delete_Task(int nr)
void Sem_wait(int nr)
void Sem_signal(int nr)
void Mutex_lock(void)
void Mutex_unlock(void)
Dintre acestea, prima funcţie se apelează în funcţia main înainte de pornirea
planificatorului şi duce la iniţializarea tabelei de procese precum şi la iniţializarea stivei
utilizată de task-ul respectiv. Cei trei parametrii ai funcţiei reprezintă id-ul, adresa stivei,
respectiv un pointer către corpul task-ului.
Pentru a iniţializa corect un task, este obligatoriu păstrarea distanţei minime de 96 de
octeţi (+ nr de octeţi folosit de variabilele locale) între adresele stivelor task-urilor. Deoarece
avem la început o zonă de memorie destinată variabilelor kernelului, se permite alocarea
memoriei pentru task-uri începând cu adresa 0x20000408.
Pentru a uşura munca utilizatorului, sunt definite la începutul programului, trei adrese
de memorie, la o diferenţă de 256 (0x100) de octeţi între ele ce pot fi utilizate pentru a
permite iniţializarea mai uşoară a primelor task-uri.
Celelalte cinci primitive se apelează din interiorul task-urilor. Detele_Task are rolul
ştergerii task-ului cu id-ul dat în parametrul funcţiei, iar perechile de primitive ale
semafoarelor permit sincronizarea a doua thread-uri, pe când mutex-urile garantează accesul
asupra unei zone de memorie unui singur thread. Ambele mecanisme de sincronizare au fost
explicate mai detaliat în capitolul 3.3.3.
45
4 Comparaţie cu alte soluţii existente
Pentru a compara acest microkernel cu alte soluţii existente pe piaţă, trebuie să ne
raportăm la alte criterii de performanţă decât cele definite în Capitolul 2 şi anume la criterii
care nu ţin cont de task-urile implementate. Acestea sunt:
- CP1: Numărul de cicli pentru efectuarea schimbării între task-uri
- CP2*: Numărul de cicli pentru iniţializarea semafoarelor
- CP2: Numărul de cicli pentru funcţiile semafoarelor
- CP3: Memoria minimă de cod necesară
- CP4: Memoria minimă de date necesară
- CP5: Memoria minimă alocată iniţial stivelor task-urilor
Dintre acestea, vom explicita modul de calcul al timpului de schimbare între task-uri
(luat în ciclii de ceas). Acesta poate fi calculat ca sumă între timpul folosit de dispatcher
pentru a schimba context-ul celor două task-uri şi timpul folosit de algoritmul de planificare.
Ecuaţia pentru această sumă este:
𝑡𝑡𝑜𝑡𝑎𝑙 = 𝑡ℎ𝑤 + 𝑡𝑠𝑤1 + 𝑡𝑝𝑙 + 𝑡𝑠𝑤2 + 𝑡ℎ𝑤 (4.1)
În formula precedentă termenul notat cu 𝑡ℎ𝑤 reprezintă timpul necesar intrării,
respectiv ieşirii din întrerupere, dat in manualul de referinţă, la 16 ciclii. Timpii notaţi cu 𝑡𝑠𝑤1
şi 𝑡𝑠𝑤2 reprezintă durata necesară salvării sau încărcarea celor 6 regiştrii din stivă, la care se
mai adaugă, în cazul a 𝑡𝑠𝑤1 timpul încărcării în stivă a variabilelor din funcţia de întrerupere,
şi în cazul 𝑡𝑠𝑤2, timpul ieşirii din funcţie. Luând în calcul instrucţiunile folosite precum şi
numărul de ciclii ai acestor am ajuns la un număr de maxim 24 de ciclii pentru 𝑡𝑠𝑤1 respectiv
de maxim 23 de ciclii pentru 𝑡𝑠𝑤2.
Timpul de rulare al planificatorului, 𝑡𝑝𝑙 , are valoarea maximă:
𝑡𝑝𝑙 = 28 + 35 ∙ 𝑥 (4.2)
unde x este numărul de poziţii pe care planificatorul îl parcurge pentru a ajunge la
următorul task pregătit de rulare. În cazul în care se trece la următorul task din vector, x este
46
egal cu 1.
Atât in calcularea a 𝑡𝑝𝑙 cât şi în calculul a 𝑡𝑠𝑤1si 𝑡𝑠𝑤2 am luat cea mai rea situaţie,
pentru instrucţiuniile cu un număr variabil de ciclii de ceas, numărul real de ciclii putând fi cu
2-4 mai mic pentru fiecare din cei trei timpi.
Înlocuind în ecuaţia 4.1, obţinem:
𝑡𝑡𝑜𝑡𝑎𝑙 = 16 + 24 + 28 + 35 ∙ 𝑥 + 23 + 16 = 107 + 35 ∙ 𝑥 (4.3)
Este de notat că acest număr de ciclii, luând x = 1, ne dă un timp de 3.8 µs, la
frecvenţa de 37.5 Mhz, considerabil mai mic decât cuanta de timp luată de regulă în
planificarea de tip Round-robin de câteva zeci de ms.
Celelalte criterii de performanţă pot fi evaluate în acelaşi fel, evaluând instrucţiunile
executate (numărul de ciclii pentru funcţiile semafoarelor) sau prin vizualizarea raportului dat
de mediul de dezvoltare după compilare (memoria minimă de cod, memoria minimă de date).
În tabelele 4.1, 4.2, 4.3 şi 4.4 sunt trecute comparativ criteriile de performanţă ale
acestui microkernel, respectiv ale altor soluţii existente pe piaţă, mai exact ThreadX,
FreeRTOS şi Neutrino (QNX 6.5).
47
Criteriu Descriere
Valoare Unitate de
măsură
Observaţii
CP1 Timp de schimbare
între task-uri
<142 ciclii de ceas 130-142
CP2 Timp apel funcţiile
semafoarelor
<66 ciclii de ceas 56-66
S-a luat in vedere
funcţia Sem_signal();
CP2* Timp de iniţializare
semafoare
<24 ciclii de ceas 22-24
CP3 Memoria de cod
necesară (min.)
2400 octeţi
CP4 Memoria de date
necesară (min.)
1056 octeţi Dintre care 1036 se
află in segmentul BSS
CP5 Memoria minimă
alocată stivelor
96 octeţi Se poate reduce până
la 84 de octeţi
Tabel 4.1. Evaluarea criteriilor de performanţă a soluţiei propuse
(folosind procesorul Cortex-M3)
Criteriu Descriere
Valoare Unitate de
măsură
Observaţii
CP1 Timp de schimbare
între task-uri
<100 ciclii de ceas
CP2 Timp apel funcţiile
semafoarelor
30 ciclii de ceas Pentru funcţia
sem_getvalue();
CP3 Memoria de cod
necesară (min.)
2000 octeţi
CP4 Memoria de date
necesară (min.)
500 octeţi
Tabel 4.2. Evaluarea criteriilor de performanţă pentru microkernelul ThreadX
Nu se specifică procesorul utilizat iar datele sunt luate din [23].
48
Criteriu Descriere
Valoare Unitate de
măsură
Observaţii
CP2* Timp de iniţializare
semafoare
~500 ciclii de ceas Pentru Cortex-M3
CP3 Memoria de cod
necesară (min.)
5000-10000 octeţi In funcţie de
arhitectura folosită
CP4 Memoria de date
necesară (min.) 312 octeţi Pentru planificator si
o coada de task-uri
CP5 Memoria minima
alocată stivelor
64 octeţi
Tabel 4.3. Evaluarea criteriilor de performanţă pentru microkernelul FreeRTOS
(nu se specifică procesorul utilizat, cu excepţia timpului de iniţializare a semafoarelor).
Sursa pentru aceste date este [24].
Criteriu Descriere
Valoare Unitate de
măsură
Observaţii
CP1 Timp de schimbare
între task-uri
1809 ciclii de ceas Prin task se înţelege
fir de execuţie
CP1* Timp de schimbare
între task-uri
3009 ciclii de ceas Prin task se înţelege
proces
CP2 Timp apel funcţiile
semafoarelor
5705 ciclii de ceas S-a luat in vedere
functia Sem_signal();
Tabel 4.4. Evaluarea criteriilor de performanţă pentru microkernelul Neutrino
(Procesorul de referinţă este ARM926EJ-S cu o arhitectură ARM9).
Sursa pentru aceste date este [25].
O comparaţie cu FreeRTOS poate să nu ofere rezultate concludente, acesta fiind
considerabil mai complex şi având mai multe componente decât microkernelul implementat
(suport pentru protecţia memoriei, alocarea dinamică a memoriei..etc.). O situaţie similară
avem şi în cazul comparaţiei cu microkernelul Neutrino folosit de QNX 6.5. Însă comparând
soluţia noastră cu ThreadX putem să observăm că multe valori sunt asemănătoare şi că
aducând optimizări sau proiectând componente noi, se poate aduce pe piaţa un produs relativ
util.
49
5 Studiu de caz: algoritm PID
În timpul testării microkernelului, am implementat nişte task-uri de testare, care,
împreună cu o cuantă mare de timp aleasa (100 ms), permit vizualizarea pe placă a execuţiei
lor în paralel. Acest lucru, împreună cu depanarea programului pentru a verifica integritatea
regiştrilor şi a stivei ne-a ajutat să tragem concluzia că microkernelul funcţionează corect.
Respectivele task-uri, care testează şi funcţionarea semafoarelor, pot fi găsite în anexă.
Însă, pentru a putea evalua mai bine criteriile de performanţă definite în Capitolul 2, se
propune implementarea unui task care poate să apară în realitate şi anume un task de reglare
folosind un algoritm de tip PID. Pentru implementarea acestui algoritm cu un singur grad de
libertate, se vor alege corespunzător frecvenţa de eşantionare a PID-ului precum şi cuanta de
timp a microkernelului iar pentru simularea condiţiilor reale vom implementa un alt task ce va
rula în paralel. Acesta va fi interacţiona periodic cu reţeaua primind referinţă pentru PID,
trimiţând un raport către server, etc.
5.1. Obţinerea ecuaţiei cu diferenţe
Pentru a putea implementa algoritmului de tip PID pe microcontroler, trebuie să-l
reprezentăm într-o formă discretizată, ca o ecuaţie cu diferenţe [5]. Vom alege modelul părţii
fixate ca punct de start pentru a calcula forma discretizată a PID-ului.
Aşadar, alegem un sistem de ordin II, cu funcţia de transfer:
𝐻𝑃(𝑠) =𝐾𝜔2
𝑠2+2𝜉𝜔𝑠+𝜔2 (5.1)
Pentru a avea necesar un timp de eşantionare foarte mic, propunem un proces mecanic
(Dumitrache, 2010) cu timp tranzitoriu foarte mic si o pulsaţie 𝜔 mare. Acesta are
amplificarea, K, unitară, pulsaţia 40, si factorul de amortizare 𝜉 = 1.25, aşadar funcţia de
transfer devine:
50
𝐻𝑃(𝑠) =700
𝑠2+55𝑠+700=
700
(𝑠+20)(𝑠+35) (5.2)
Cerinţele pentru proiectarea regulatorului sunt ca eroarea staţionară să rămână 0,
suprareglajul, 𝜎[%], sa fie mai mic decât 20% iar timpul tranzitoriu, 𝑡𝑡 sa fie maxim 0.15
secunde.
Ca o metodă relativ simplă de proiectare a regulatoarelor discrete, dorim să ajungem la
forma continuă a acestuia, după care să-l discretizăm. Acest lucru se va realiza cu următorii
paşi:
1. Determinarea structurii SRA-ului în buclă închisă folosind metoda alocării polilor
2. Determinarea funcţiei de transfer în bucla deschisă, din pasul anterior
3. Determinarea funcţiei de transfer a regulatorului PID continuu
4. Discretizarea regulatorului PID cu o perioadă de eşantionare potrivită
Pasul 1 consta în calculul funcţiei de transfer în buclă închisă care respectă cerinţele
impuse. Aceasta va fi tot de ordin II, având aceeaşi formă ca în ecuaţia 5.1. Folosim formula
5.3 pentru a alege factorul de amortizare 𝜉 potrivit, şi calculând pulsaţia 𝜔0 cu aproximarea
5.4 obţinem funcţia de transfer a sistemului în buclă închisa:
𝜎[%] = 100 ∙ 𝑒(−𝜉
𝜋
(1−𝜉2)) (5.3)
𝑡𝑡 ≈ 3.9
𝜉∙𝜔0 (5.4)
𝐻0(𝑠) =1225
𝑠2+2∙0.5∙35∙𝑠+1225 (5.5)
Pasul 2 constă in determinarea funcţiei de transfer a SRA-ului în buclă deschisă din
ecuaţia 5.5:
51
𝐻𝑑(𝑠) =𝐻0(𝑠)
1− 𝐻0(𝑠)=
𝜔02
𝑠(𝑠+2𝜔𝑜𝜉)=
1225
𝑠(𝑠+35) (5.6)
Aceasta mai este egală cu produsul dintre funcţia de transfer a părţii fixe şi regulator
de unde rezultă, ca pasul 3, funcţia de transfer pentru regulator:
𝐻𝑅(𝑠) = 𝐻𝑑(𝑠) ∙1
𝐻𝑃(𝑠)=
1225(𝑠+20)
𝑠∙700=
7𝑠+140
4 (5.7)
Acest regulator este de tip PI, iar pentru a-l putea implementa pe microcontroler,
trebuie discretizat. În pasul 4 se realizează acest lucru cu o discretizare de ordin zero (metoda
Euler) folosind comanda c2d in Matlab, obţinându-se, aşadar, modelul 5.8 pentru regulatorul
discret. Pentru a realiza discretizarea, alegem perioada de eşantionare Te = 0.01 sec, ce
verifică condiţia luata de regulă pentru timpul de eşantionare, anume 𝑇𝑒 ≤1
6𝑡𝑡.
𝐻𝑅(𝑧) =1.75 𝑧−1.4
𝑧−1 (5.8)
Atât cu acest regulator, cât si cu cel de la pasul 3 unde aveam forma sa continuă, am
testat schema de reglare automată in Simulink pentru a ne asigura de respectarea cerinţelor
impuse.
Din ecuaţia 5.8, împărţind prin z pentru a ne raporta la pasul anterior obţinem forma
ecuaţiei cu diferenţe 5.9, unde s-a notat cu 𝜀𝑘 eroarea la momentul curent şi cu 𝜀𝑘−1 eroarea
de la pasul precedent. De asemenea 𝑢𝑘 este comanda dată de regulator la pasul curent iar 𝑢𝑘−1
este comanda de la pasul precedent.
𝑢𝑘 = 1.75 ∙ 𝜀𝑘 − 1.4 ∙ 𝜀𝑘−1 + 𝑢𝑘−1 (5.9)
52
5.2. Structura task-ului
Pentru a putea implementa această ecuaţie cu diferenţe pe microcontroler, mai trebuie
să alegem mărimea cuantei de timp din cadrul sistemului, care să asigure timp suficient pentru
executarea algoritmului de reglare şi să definim structura algoritmului PID.
Pentru a rezolva ultima problemă trebuie să explicităm forma fizică a schemei de
reglare automată. Aşadar, se consideră atât semnalul de comandă cât şi semnalul de intrare ca
având valorile între 0 şi 3.3V. Task-ul PID-ului va converti semnalul analogic într-un semnal
discret, folosind CAN-ul microcontrolerului, va reactualiza datele şi va calcula valoarea
comenzii iar la sfârşit va converti comanda într-o mărime analogică folosind un CNA.
În alegerea mărimii cuantei de timp, se va ţine cont de cele două task-uri ce vor fi
implementate împărţind timpul de eşantionare la 2 şi obţinând 5 ms.
Figură 5.1. Schema de reglare automată pentru un regulator discret
Precum se vede şi în figura 5.1, task-ul va trebui să asigure conversia semnalului de
intrare folosind un Convertor Analog-Numeric (CAN) şi să trimită comanda de ieşire către un
Convertor Numeric-Analogic (CNA) pentru a putea fi utilizat de elementul de execuţie.
Pentru a realiza prima cerinţă, se foloseşte unul din cele două CAN-uri cu rezoluţie pe 12 biţi
ale plăcuţei de dezvoltare printr-o funcţie numită readADC1. Aceasta se ocupa atât de
selectarea canalului, de aşteptarea timpului de conversie, precum şi de convertirea variabilei
rezultate într-un întreg pe 16 biţi (uint16_t). DAC-ul, pe de altă parte foloseşte funcţia
writeDAC1 pentru a trimite variabila de comanda 16 biţi, convertorului cu număr de ordin 1
care are o rezoluţie tot pe 12 biţi.
53
În momentul setării referinţei, este obligatoriu să cunoaştem faptul că atât ADC-ul cât
şi DAC-ul folosesc variabile cuprinse între 0 şi 4095. Astfel, pentru a calcula valoarea
tensiunii pe care dorim s-o setăm că referinţă se va utiliza formula 5.10
𝑢𝑟 = (2𝑛𝑟.𝑏−1)∙𝑈𝑟
𝑈𝑚𝑎𝑥 (5.10)
unde 𝑢𝑟 reprezintă valoarea în biţi a tensiunii pe care dorim s-o setăm, 𝑈𝑚𝑎𝑥 este tensiunea
maximă a domeniului admisibil şi anume 3.3V, 𝑈𝑟 este tensiunea de referinţă pe care dorim să
o punem iar nr.b este numărul de biţi pe care este făcută conversia, în cazul nostru 12.
Ţinând cont de necesităţile explicate mai sus, ne rezultă codul task-ului:
void task_code1(int task_id)
{
uint32_t i;
uint16_t ep_k = 0, ep_k1, u_k = 0, u_k1;
while(1)
{
Disable_intr();
ep_k1 = ep_k;
u_k1 = u_k;
ep_k = readADC1(1) - ref;
u_k = (uint16_t)(1.75 * ep_k – 1.4 * ep_k1 + u_k1);
writeDAC1(u_k, 1);
Enable_intr();
for (i=0;i<23943;i++); //4.991 ms la frecventa 37.5 Mhz
}
}
Pentru a ne asigura de implementarea corectă a task-ului de reglare trebuie să ajungem
la o singură declanşare a algoritmului PID în cuanta de timp destinată ei. Acest lucru se
realizează punând task-ul într-o buclă infinită şi adăugând o întârziere mare după, sub forma
unui bucle for. Folosind depanatorul, vedem până unde a ajuns indicele i din cadrul for-ului şi
folosim o întârziere cu acest indice.
Aceasta acordare, a dat valoarea 23943 în cazul de faţă pentru o cuantă de timp de 5
ms. Deoarece, operaţiile din cadrul algoritmului PID plus întârzierea dată de noi durează 5 ms
54
(±1 ciclu de ceas), avem asigurată declanşarea de fiecare dată a task-ului de reglare la
începutului cuantei de timp destinată ei.
Respectarea afirmaţiei anterioare este prezentată în schema execuţiei task-urilor din
figura 5.2
Figură 5.2. Execuţia task-urilor în sistemul proiectat
O notă importantă, referitoare la figura anterioara este ca poziţia algoritmului PID
poate fi alterată in cadrul cuantei de timp destinat task-ului prin introducerea mecanismelor de
sincronizare in cel de-al doilea task. Pentru a ne feri de această problemă se recomandă
evitarea semafoarelor sau a mutexilor in cel de-al doilea task.
Modul in care este implementat task-ul PID-ului ne permite mărirea numărului de
thread-uri pe care le putem rula in paralel. Însă mai multe task-uri vor duce la modificarea
perioadei de eşantionare pentru algoritmul de reglare, lucru care trebuie compensat prin
modificarea mărimii cuantei de timp pentru toate task-urile. În concluzie, proiectantul PID-
ului îi este indicat sa cunoască modul de funcţionare al sistemului de operare din cazul de faţă.
5.3. Interpretarea rezultatelor
Task-ul dat se va executa de fiecare dată în acelaşi loc în cadrul cuantei de timp,
păstrând o distanţă constantă de timp până la pornirea următorului thread din memorie.
Aşadar, se poate concluziona că acesta respectă condiţiile de timp real.
55
Criteriile de performanţă, definite în subcapitolul 2.1 sunt uşor de calculat pentru acest
task. Reamintim că acestea sunt:
- Utilizarea CPU-ului
- Rata de terminare a task-urilor
- Timpul de terminare
- Timpul de aşteptare
- Timpul de răspuns
Pentru calcului lor, vom defini timpul de rulare a planificatorului şi de de
salvarea/încărcarea contextului, 𝑡𝑠 , calculat în capitolul 3 la 3.8 μs, durata unei cuante de
timp, 𝑡𝑐, egal cu 5 ms şi timpul efectiv de rulare al algoritmului de reglare, 𝑡𝑃𝐼𝐷, egal cu 1.5
μs.
Dacă ţinem cont că nu există nici un thread idle, care să ruleze în paralel cu cele două
task-uri definite de noi, obţinem o utilizare a procesorului de 99.92%. Dacă este, însă, să luăm
în calcul timpul în care chiar se execută algoritmul de reglare precum şi timpul de execuţie al
celui de-al doilea task, obţinem utilizarea procesorului de 49.97%. Pentru prima valoare s-a
folosit formula 5.11 iar pentru a doua, 5.12
𝑐𝑝𝑢[%] = 100𝑡𝑐
𝑡𝑐+𝑡𝑠 (5.11)
𝑐𝑝𝑢∗[%] = 100𝑡𝑐+𝑡𝑃𝐼𝐷
2∙𝑡𝑐+2∙𝑡𝑠 (5.12)
Deoarece, task-ul rulează la nesfârşit, nu putem să-i calculăm timpul de terminare, iar
rata de terminare a task-urilor devine iar nesemnificativă.
Timpul de aşteptare, definit ca perioada de timp în care task-ul stă în coada de
aşteptare este infinit, dar se poate calcula procentul de timp cât task-ul sta în coada de
aşteptare la 50.04% folosind formula 5.13.
𝑡𝑎[%] = 100𝑡𝑐+2∙𝑡𝑠
2∙𝑡𝑐+2∙𝑡𝑠 (5.13)
56
Timpul de răspuns este teoretic 0, dacă este să luăm în calcul momentul în care se
pune în execuţie codul util. Însă dacă dorim să ţinem cont de timpul până când oferim date de
I/O, timpul de răspuns este de fapt 𝑡𝑃𝐼𝐷 = 1.5 μs.
Acest timp de răspuns, este singurul criteriu de performanţă util în cazul task-ului de
faţă, el garantându-ne un răspuns rapid chiar şi la o frecvenţă a procesorului nu foarte ridicată.
Împreună cu respectarea condiţiilor de timp real, timpul mic de răspuns ne asigură
funcţionarea corespunzătoare a sistemului.
57
6 Concluzii si dezvoltări ulterioare
Microkernelul cu algoritmul de planificare implementat respectă condiţiile de timp
real, lucru evidenţiat în capitolul 5 pentru un task de forma unui algoritm de reglare. De
asemena, el prezintă toate funcţionalităţile unui sistem de operare în timp real ce utilizează
fire de execuţie.
Proiectul se poate dezvolta în continuare în sensul adăugării unui sistem de protecţie a
memoriei precum şi al unui sistem de fişiere într-o primă fază, urmând ca într-o fază
ulterioară să se poată modifica modul de implementare a task-urilor utilizând procese în
defavoarea firelor de execuţie. De asemenea, pentru a facilita programarea de către utilizator,
în revizii ulterioare se pot adăuga driverele pentru perifericele cel mai des folosite ale
microcontrolerului. În scopul simulării şi a comparaţiei algoritmilor de planificare de timp
real, se mai poate implementa pe microcontroler algoritmul preemptiv bazat pe priorităţi fixe,
utilizând întreruperea PendSV, şi păstrând acelaşi cod al dispatcherului.
Datorită duratei mici de schimbare între task-uri şi de apelare a funcţiilor
mecanismelor de sincronizare, microkernelul implementat este comparabil cu alte soluţii de
pe piaţă (spre exemplu ThreadX). Întrucât în domeniul sistemelor integrate, este importantă
dimensiunea redusă a programului, s-a încercat micşorarea dimensiunii microkernelului prin
simplificarea componentelor sale. De asemenea, componenta de sincronizare este opţionala,
lipsa ei putând reduce dimensiunea programul până la aproximativ 2 KB. Acest lucru permite
utilizarea sa şi pe controlerele STM32 F103xx (cu o memorie de 16 + 6 KB), ce sunt
compatibile binar cu controlerul utilizat în cazul de faţă.
Implementarea microkernelului a fost o experienţă nouă şi captivantă care mi-a permis
dobândirea cunoştinţelor atât în domeniului programării la nivel de bază şi mediu cât şi în
domeniul sistemelor de operare.
58
7 Anexe
Codul microkernelului, luat din fisierul main.cpp:
#include "stm32f10x.h"
#include "stm32f10x_gpio.h"
#include "stm32f10x_rcc.h"
#include "stm32f10x_tim.h"
#include "misc.h"
#define READY 1 //1 daca este gata de executie, 0 daca nu
este gata de executie
#define NO_TASKS 3 //include task-ul initial (idle
task)
#define ADR_SEM 0x20000400 //adresa de memorie pentru semafor - se
modifica daca se suprascriu date
#define TASK_STACK1 0x20000800
#define TASK_STACK2 0x20000900
#define TASK_STACK3 0x20000A00 //se pot adauga mai multe, dupa
nevoie
typedef struct
{
void * stack_pointer; //pointer catre stiva task-ului
int flag; //flagurile task-ului
} struct_task_table;
int task_curent = 0;
uint16_t ref = 2000;
struct_task_table task_table[NO_TASKS];
void Init_Task(int nr, uint32_t stack_adr, void
(*cod_functie)(int));
void NVIC_Configuration(void) //configurarea NVIC
{
NVIC_InitTypeDef NVIC_InitStructure;
NVIC_InitStructure.NVIC_IRQChannel = SysTick_IRQn;
NVIC_InitStructure.NVIC_IRQChannelPreemptionPriority = 0;
NVIC_InitStructure.NVIC_IRQChannelSubPriority = 0;
NVIC_InitStructure.NVIC_IRQChannelCmd = ENABLE;
NVIC_Init(&NVIC_InitStructure);
}
void GPIO_Configuration(void) //configurarea GPIO
{
GPIO_InitTypeDef GPIO_InitStructure;
59
RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOC, ENABLE);
GPIO_InitStructure.GPIO_Pin = GPIO_Pin_All;
GPIO_InitStructure.GPIO_Mode = GPIO_Mode_Out_PP;
GPIO_InitStructure.GPIO_Speed = GPIO_Speed_50MHz;
GPIO_Init(GPIOC, &GPIO_InitStructure);
}
void Start_scheduler(void)
{
NVIC_Configuration();
SysTick_Config(SystemCoreClock / 10); //intervalul de intreruperi
(setat la 100ms)
}
static inline void Set_MSP_Privileged(void)
{
int rest;
asm volatile
(
"MOV r8, #0\n\t"
"MSR control, r8\n\t": "=r" (rest)
);
}
void Disable_intr(void)
{
uint32_t *p_SYST_CSR, SYST_CSR;
SYST_CSR = 0xE000E010;
p_SYST_CSR = (uint32_t*)SYST_CSR;
*p_SYST_CSR = *p_SYST_CSR & 0xFFFFFFFE; //ultimul bit pe 0 duce
la dezactivarea systick-
ului
}
void Enable_intr(void)
{
uint32_t *p_SYST_CSR, SYST_CSR;
SYST_CSR = 0xE000E010;
p_SYST_CSR = (uint32_t*)SYST_CSR;
*p_SYST_CSR = *p_SYST_CSR | 1; //ultimul bit pe 1 duce la
activarea systick-ului
}
void Init_Sem(void) {
uint32_t com, *p_com;
com = ADR_SEM;
60
p_com = (uint32_t*)com;
*p_com = 0;
}
void Sem_signal(int nr) // V
{
uint32_t com, nr_sem, *p_com;
nr_sem = 1<<nr;
Disable_intr();
com = ADR_SEM;
p_com = (uint32_t*)com;
*p_com = *p_com | nr_sem;
Enable_intr();
}
void Sem_wait(int nr) // P
{
uint32_t com, nr_sem, *p_com;
nr_sem = 1<<nr;
Disable_intr();
com = ADR_SEM;
p_com = (uint32_t*)com;
Enable_intr();
while ((*p_com & nr_sem) == 0) ;
*p_com = *p_com & (~nr_sem);
}
void SysTick_Handler(void)
{
int rest;
asm volatile
(
"MRS %0, msp\n\t"
"STMDB %0!, {r5-r11}\n\t"
"MSR msp, %0\n\t" : "=r" (rest)
);
if (SysTick->CTRL & (1<16))
{
void *ptr1, *ptr2;
asm volatile ("MRS %0, msp\n\t" : "=r" (ptr1) );
task_table[task_curent].stack_pointer = ptr1;
do
{
task_curent++;
if (task_curent == NO_TASKS )
task_curent = 1;
if (task_table[task_curent].flag & READY)
61
break;
}
while(1);
ptr2 = task_table[task_curent].stack_pointer;
asm volatile ("MSR msp, %0\n\t" : : "r" (ptr2) );
}
asm volatile
(
"MRS %0, msp\n\t"
"LDMFD %0!, {r5-r11}\n\t"
"MSR msp, %0\n\t" : "=r" (rest)
);
}
void Delete_Task(int nr)
{
task_table[nr].flag = 0;
while(1);
}
void Init_Task(int nr, uint32_t stack_adr, void (*cod_functie)(int))
{
uint32_t adr1, *p_adr1, adr2, *p_adr2, adr3, *p_adr3, adr4,
*p_adr4, adr5, *p_adr5, adr6, *p_adr6, adr7, *p_adr7, adr8, *p_adr8,
adr9, *p_adr9, adr10, *p_adr10;
uint32_t adr11, *p_adr11, adr12, *p_adr12, adr13, *p_adr13,
adr14, *p_adr14, adr15, *p_adr15, adr16, *p_adr16, adr17, *p_adr17,
adr18, *p_adr18, adr19, *p_adr19, adr20, *p_adr20;
uint32_t adr21, *p_adr21, adr22, *p_adr22, adr23, *p_adr23;
task_table[nr].flag = READY;
task_table[nr].stack_pointer = stack_adr;
adr1 = stack_adr;
p_adr1 = (uint32_t*)adr1; //r5
*p_adr1 = 0;
adr2 = stack_adr + 4;
p_adr2 = (uint32_t*)adr2; //r6
*p_adr2 = 0;
adr3 = stack_adr + 8;
p_adr3 = (uint32_t*)adr3; //r7
*p_adr3 = stack_adr + 28;
adr4 = stack_adr + 12;
p_adr4 = (uint32_t*)adr4; //r8
*p_adr4 = 0;
adr5 = stack_adr + 16;
p_adr5 = (uint32_t*)adr5; //r9
*p_adr5 = 0;
62
adr6 = stack_adr + 20;
p_adr6 = (uint32_t*)adr6; //r10
*p_adr6 = 0;
adr7 = stack_adr + 24;
p_adr7 = (uint32_t*)adr7; //r11
*p_adr7 = 0;
//----------------------------------
adr8 = stack_adr + 28;
p_adr8 = (uint32_t*)adr8;
*p_adr8 = 0;
adr9 = stack_adr + 32;
p_adr9 = (uint32_t*)adr9;
*p_adr9 = 0;
adr10 = stack_adr + 36;
p_adr10 = (uint32_t*)adr10;
*p_adr10 = 0;
adr11 = stack_adr + 40;
p_adr11 = (uint32_t*)adr11;
*p_adr11 = 0;
adr12 = stack_adr + 44;
p_adr12 = (uint32_t*)adr12;
*p_adr12 = 0;
adr13 = stack_adr + 48;
p_adr13 = (uint32_t*)adr13;
*p_adr13 = stack_adr + 84;
//----------------------------------
adr14 = stack_adr + 52;
p_adr14 = (uint32_t*)adr14; //R0
*p_adr14 = 0;
adr15 = stack_adr + 56;
p_adr15 = (uint32_t*)adr15; //R1
*p_adr15 = 0;
adr16 = stack_adr + 60;
p_adr16 = (uint32_t*)adr16; //R2
*p_adr16 = 0;
adr17 = stack_adr + 64;
p_adr17 = (uint32_t*)adr17; //R3
*p_adr17 = 0;
adr18 = stack_adr + 68;
p_adr18 = (uint32_t*)adr18; //R12
*p_adr18 = 0;
adr19 = stack_adr + 72;
63
p_adr19 = (uint32_t*)adr19; //LR
*p_adr19 = 0;
adr20 = stack_adr + 76;
p_adr20 = (uint32_t*)adr20; //PC
*p_adr20 = cod_functie + 7;
adr21 = stack_adr + 80;
p_adr21 = (uint32_t*)adr21; //xPSR
*p_adr21 = 0x81000000;
adr22 = stack_adr + 84;
p_adr22 = (uint32_t*)adr22; //SP
*p_adr22 = stack_adr + 88;
adr23 = stack_adr + 88;
p_adr23 = (uint32_t*)adr23; //primul argument al
functiei in care se
intra
*p_adr23 = nr;
}
void task_code1(int task_id)
{
uint32_t i;
for (i=0; i<5000000; i++)
GPIOC->ODR = GPIO_Pin_6;
Sem_signal(13);
for (i=0; i<2500000; i++)
GPIOC->ODR = GPIO_Pin_6;
GPIOC->ODR = 0;
Delete_Task(task_id);
}
void task_code2(int task_id)
{
uint32_t i;
for (i=0; i<2500000; i++)
GPIOC->ODR = GPIO_Pin_7;
Sem_wait(13);
for (i=0; i<2500000; i++)
GPIOC->ODR = GPIO_Pin_7;
GPIOC->ODR = 0;
Delete_Task(task_id);
}
void Idle_task(void)
{
while(1);
}
64
int main()
{
Set_MSP_Privileged();
GPIO_Configuration();
Init_Sem();
Init_Task(1, TASK_STACK1, task_code1); //stack1: 2000 0800
Init_Task(2, TASK_STACK2, task_code2); //stack2: 2000 0900
Start_scheduler();
Idle_task();
}
Codul task-ului PID-ului si a functiilor de initializare pentru CAN/CNA:
void task_code1(int task_id)
{
uint32_t i;
uint16_t ep_k = 0, ep_k1, u_k = 0, u_k1;
while(1)
{
Disable_intr();
ep_k1 = ep_k;
u_k1 = u_k;
ep_k = readADC1(1) - ref;
u_k = 2 * ep_k - 2 * ep_k1 + u_k1;
DAC_WriteData(u_k);
Enable_intr();
for (i=0;i<23943;i++); //4.991 ms la frecventa 37.5 Mhz
}
}
void ADC_Configuration(void)
{
ADC_InitTypeDef ADC_InitStructure;
RCC_ADCCLKConfig(RCC_PCLK2);
RCC_APB2PeriphClockCmd(RCC_APB2Periph_ADC1, ENABLE);
ADC_DeInit(ADC1);
ADC_InitStructure.ADC_Mode = ADC_Mode_Independent;
ADC_InitStructure.ADC_ScanConvMode = DISABLE;
ADC_InitStructure.ADC_ContinuousConvMode = DISABLE;
ADC_InitStructure.ADC_ExternalTrigConv =
ADC_ExternalTrigConv_None;
ADC_InitStructure.ADC_DataAlign = ADC_DataAlign_Right;
ADC_InitStructure.ADC_NbrOfChannel = 1;
ADC_Init(ADC1, &ADC_InitStructure);
ADC_Cmd(ADC1, ENABLE);
65
ADC_ResetCalibration(ADC1);
while(ADC_GetResetCalibrationStatus(ADC1));
ADC_StartCalibration(ADC1);
while(ADC_GetCalibrationStatus(ADC1));
}
void DAC_Configuration(void)
{
GPIO_InitTypeDef GPIO_InitStructure;
GPIO_InitStructure.GPIO_Pin = GPIO_Pin_4;
GPIO_InitStructure.GPIO_Mode = GPIO_Mode_AIN;
GPIO_Init(GPIOA, &GPIO_InitStructure);
RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA, ENABLE);
RCC_APB1PeriphClockCmd(RCC_APB1Periph_DAC, ENABLE);
DAC_InitStructure.DAC_Trigger = DAC_Trigger_Software;
DAC_InitStructure.DAC_WaveGeneration = DAC_WaveGeneration_None;
DAC_InitStructure.DAC_OutputBuffer = DAC_OutputBuffer_Disable;
DAC_Init(DAC_Channel_1, &DAC_InitStructure);
DAC_Cmd(DAC_Channel_1, ENABLE);
DAC_SetChannel1Data(DAC_Align_12b_R, 0); //initial
DAC_SoftwareTriggerCmd(DAC_Channel_1, ENABLE);
}
uint16_t readADC1(uint16_t channel)
{
ADC_RegularChannelConfig(ADC1, channel, 1,
ADC_SampleTime_1Cycles5);
ADC_SoftwareStartConvCmd(ADC1, ENABLE);
while(ADC_GetFlagStatus(ADC1, ADC_FLAG_EOC) == 0);
return ADC_GetConversionValue(ADC1);
}
void DAC_WriteData(u_k);
{
DAC_SetChannel1Data(DAC_Align_12b_R, u_k);
}
Codul folosit pentru a desena functia densitate de probabilitate, in matlab:
x = [1803;1787;1741;1497;1395;1697;2031;1485;1412;1720]; %Timp de
terminare
y = [1348;1543;1261;1346;1455;1351;1105;1420;1144;1255];
z = [2445;2460;2315;2577;2699;2265;2735;1992;2188;3506];
%x = [1465;1445;1404;1217;1127;1338;1636;1154;1117;1403]; %Timp de
raspuns
%y = [974;1204;969;973;1135;1038;814;1078;727;936];
%z = [108;145;113;128;115;87;53;155;97;77];
66
%x = [2445;2460;2315;2577;2699;2265;2735;1992;2188;3506];
%y = [1760;2131;2071;2428;2601;2231;2860;2157;2129;2561];
%x = [108;145;113;128;115;87;53;155;97;77];
%y = [316;182;351;263;341;314;157;527;277;366];
pts1 = (min(x):1:max(x));
pts2 = (min(y):1:max(y));
pts3 = (min(z):1:max(z));
[f,xi] = ksdensity(x);
[g,yi] = ksdensity(y);
[h,zi] = ksdensity(z);
ylabel('Probabilitatea')
xlabel('Tr')
hold all
title(' Functia densitatii de probabilitate pentru timpul mediu de
terminare');
plot(xi,f);
plot(yi,g);
plot(zi,h);
Codul utilizat pentru simularea diversi algoritmi de planificare pe PC :
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NO_TASKS 5
#define TM_SLICE 50
struct task
{
int id;
unsigned int start_t;
unsigned int duration;
int prio;
int inf;
} prog[NO_TASKS], aux;
int timp_ast;
void fi_fo()
//Algoritmul de Scheduling FiFO
{
int i, j = 0, perf[NO_TASKS+1][3], Turn_t = 0, Resp_t = 0;
for(i = 0; i < NO_TASKS; i++)
perf[i][0] = prog[i].start_t;
perf[0][1] = prog[0].start_t;
printf("Procesul 0 porneste la momentul %d \n",prog[0].start_t);
67
for(i = prog[0].start_t; i < 5000; i++)
{
prog[j].duration--;
if (prog[j].duration == 0)
{
perf[j][2] = i;
j++;
perf[j][1] = i;
if (j!= NO_TASKS) printf("Procesul %d porneste la
momentul %d \n",j, i+1);
if (j == NO_TASKS) break;
}
}
for (j = 0; j < NO_TASKS; j++)
{
Turn_t = Turn_t + perf[j][2] - perf[j][0];
Resp_t = Resp_t + perf[j][1] - perf[j][0];
}
Turn_t = Turn_t / NO_TASKS;
Resp_t = Resp_t / NO_TASKS;
printf("\nTimpul mediu de terminare este %d\n", Turn_t);
printf("\nTimpul mediu de raspuns este %d\n", Resp_t);
}
void shortes_job() //Algoritmul de Scheduling cu timp
minim pana la terminare
{
int i, j, proc_curent, durata_min, cnt = 0, nr_proc = 0,
perf[NO_TASKS][4], Turn_t = 0, Resp_t = 0;
for(i = 0; i < NO_TASKS; i++)
{
perf[i][0] = prog[i].start_t;
perf[i][3] = 0;
//0 daca apare pentru prima data, 1 daca e la a 2-a
aparitie
}
durata_min = prog[0].duration;
proc_curent = prog[0].id;
perf[0][1] = prog[0].start_t;
std::cout<<"La momentul "<<prog[0].start_t<<" s-a lansat
procesul "<<proc_curent<<std::endl;
for(i = prog[0].start_t; i < 5000; i++)
{
prog[proc_curent].duration --;
for (j = 0; j < NO_TASKS; j++)
if (i == prog[j].start_t)
{
nr_proc ++;
68
if(prog[j].duration<prog[proc_curent].duration)
{
proc_curent = j;
if (perf[proc_curent][3] == 0)
perf[proc_curent][1] = i;
//se noteaza momentul lansarii
in executie a procesului
perf[proc_curent][3] = 1;
std::cout<<"La momentul "<<i<<" s-a
lansat procesul
"<<proc_curent<<std::endl;
}
}
if (prog[proc_curent].duration == 0)
{
cnt++;
perf[proc_curent][2] = i;
//se noteaza momentul terminarii procesului
if (cnt == NO_TASKS)
break;
else
{
for (j = 0; j < nr_proc; j++)
if (durata_min > prog[j].duration &&
prog[j].duration!= 0)
{
durata_min = prog[j].duration;
proc_curent = j;
}
if (perf[proc_curent][3] == 0)
perf[proc_curent][1] = i;
perf[proc_curent][3] = 1;
std::cout<<"La momentul "<<i<<" s-a lansat
procesul "<<proc_curent<<std::endl;
}
}
durata_min = 1000;
}
for (j = 0; j < NO_TASKS; j++)
{
Turn_t = Turn_t + perf[j][2] - perf[j][0];
Resp_t = Resp_t + perf[j][1] - perf[j][0];
}
Turn_t = Turn_t / NO_TASKS;
Resp_t = Resp_t / NO_TASKS;
printf("\nTimpul mediu de terminare este %d\n", Turn_t);
printf("\nTimpul mediu de raspuns este %d\n", Resp_t);
}
void priority() //Algoritmul de Scheduling FiFO cu prioritati
69
{
int i, j, proc_curent, prio_curent, cnt_no_tasks = 0,
coada[NO_TASKS], perf[NO_TASKS][4], cnt = 0, Turn_t = 0, Resp_t = 0;
for(i = 0; i < NO_TASKS; i++)
{
coada[i] = -1;
//coada[i] contine prioritatea procesului i
perf[i][0] = prog[i].start_t;
perf[i][3] = 0;
//0 daca apare pentru prima data, 1 daca e la a 2-a
aparitie
}
proc_curent = prog[0].id;
prio_curent = prog[0].prio;
perf[0][1] = prog[0].start_t;
std::cout<<"La timpul "<<prog[0].start_t<<" s-a lansat in
executie procesul "<<proc_curent<<std::endl;
for(i = prog[0].start_t; i < 5000; i++)
{
prog[proc_curent].duration--;
for (j = 0; j < NO_TASKS; j++)
//daca apare un nou proces
if (prog[j].start_t == i)
{
coada[cnt++] = prog[j].prio;//il punem in coada
if (prog[j].prio < prog[proc_curent].prio)
//daca are prioritatea mai mare, trecem la
executia lui
{
proc_curent = prog[j].id;
prio_curent = prog[j].prio;
std::cout<<"La timpul "<<i<<" s-a
lansat in executie procesul "<<proc_curent<<std::endl;
}
if (perf[proc_curent][3] == 0)
{
perf[proc_curent][1] = i;
}
perf[proc_curent][3] = 1;
}
if (prog[proc_curent].duration == 0) //daca s-a terminat
procesul
{
cnt_no_tasks ++;
perf[proc_curent][2] = i; //se noteaza momentul terminarii
procesului
if (cnt_no_tasks == NO_TASKS)
break;
70
else
{
prio_curent = 21;
coada[proc_curent] = 21;
//dam procesului curent prioritatea minima
for (j = 0; j < cnt; j++)
if (coada[j] < prio_curent)
{
proc_curent = j;
prio_curent = coada[j];
}
std::cout<<"La timpul "<<i<<" s-a lansat in
executie procesul "<<proc_curent<<std::endl;
if (perf[proc_curent][3] == 0)
perf[proc_curent][1] = i;
perf[proc_curent][3] = 1;
}
}
}
for (j = 0; j < NO_TASKS; j++)
{
Turn_t = Turn_t + perf[j][2] - perf[j][0];
Resp_t = Resp_t + perf[j][1] - perf[j][0];
}
Turn_t = Turn_t / NO_TASKS;
Resp_t = Resp_t / NO_TASKS;
printf("\nTimpul mediu de terminare este %d\n", Turn_t);
printf("\nTimpul mediu de raspuns este %d\n", Resp_t);
}
void tm_slice() //Algoritmul de Scheduling cu cuante de timp
{
int i, j, k = 0, nr_proc = 0, cnt = 0, cnt_no_tasks = 0,
slice[NO_TASKS], perf[NO_TASKS][4], proc_curent = 0, Turn_t = 0,
Resp_t = 0;
for(i = 0; i < NO_TASKS; i++)
{
perf[i][0] = prog[i].start_t;
perf[i][3] = 0;
//0 daca apare pentru prima data, 1 daca e la a 2-a
aparitie
slice[i] = 1;
//1 - nu s-a creat procesul respectiv, 2 - e in coada, 3 - procesul
respectiv s-a terminat
}
perf[0][1] = prog[0].start_t;
71
std::cout<<"La timpul "<<prog[0].start_t<<" s-a lansat in
executie procesul "<<0<<std::endl;
for (i = prog[0].start_t; i < 5000; i++)
{
prog[proc_curent].duration--;
cnt++;
for (j = 0; j < NO_TASKS; j++)
if (i == prog[j].start_t)
slice[nr_proc++] = 2;
if (prog[proc_curent].duration == 0)
{
cnt_no_tasks ++;
perf[proc_curent][2] = i;
if (cnt_no_tasks == NO_TASKS)
break;
else
{
slice[proc_curent] = 3;
cnt = 0;
k++;
if (k == nr_proc)
k = 0;
while (slice[k] != 2)
//cautam in coada urmatorul proces disponibil
cu slice[k] == 2
{
k++;
if (k == nr_proc)
k = 0;
}
proc_curent = k;
if (perf[proc_curent][3] == 0)
perf[proc_curent][1] = i;
perf[proc_curent][3] = 1;
std::cout<<"La timpul "<<i<<" s-a lansat in
executie procesul "<<proc_curent<<std::endl;
}
}
if (cnt >= TM_SLICE)
{
cnt = 0;
k++;
if (k == nr_proc)
k = 0;
while (slice[k] != 2)
//cautam in coada urmatorul proces disponibil
cu slice[k] == 2
72
{
k++;
if (k == nr_proc)
k = 0;
}
proc_curent = k;
if (perf[proc_curent][3] == 0 &&proc_curent!=0)
perf[proc_curent][1] = i;
perf[proc_curent][3] = 1;
std::cout<<"La timpul "<<i<<" s-a lansat in
executie procesul "<<proc_curent<<std::endl;
}
}
for (j = 0; j < NO_TASKS; j++)
{
Turn_t = Turn_t + perf[j][2] - perf[j][0];
Resp_t = Resp_t + perf[j][1] - perf[j][0];
}
Turn_t = Turn_t / NO_TASKS;
Resp_t = Resp_t / NO_TASKS;
printf("\nTimpul mediu de terminare este %d\n", Turn_t);
printf("\nTimpul mediu de raspuns este %d\n", Resp_t);
}
void lottery_tm_slice()
//Algoritmul de Scheduling cu cuante de timp bazat pe prioritate
{
int i, j, p, q, test, nr_proc = 0, cnt_no_tasks = 0, cnt = 0,
slice[NO_TASKS][9], perf[NO_TASKS][4], limit = 1, Turn_t = 0, Resp_t
= 0;
int proc_curent = prog[0].id;
for (i = 0; i < NO_TASKS; i++)
{
perf[i][0] = prog[i].start_t;
perf[i][3] = 0;
//0 daca apare pentru prima data, 1 daca e la a 2-a
aparitie
slice[i][0] = 1;
//1 - nu s-a creat procesul respectiv, 2 - e in coada, 3 -
procesul respectiv s-a terminat
for (j = 1; j < 9; j++)
slice[i][j] = -1;
}
perf[0][1] = prog[0].start_t;
std::cout<<"La timpul "<<prog[0].start_t<<" s-a lansat in
executie procesul "<<0<<std::endl;
for (i = prog[0].start_t; i < 5000; i++)
{
prog[proc_curent].duration--;
73
cnt++;
for (j = 0; j < NO_TASKS; j++)
if (i == prog[j].start_t)
{
slice[nr_proc++][0] = 2;
switch (prog[j].prio)
{
case 0:
limit = 9;
break;
case 4:
limit = 5;
break;
case 8:
limit = 3;
break;
case 12:
limit = 2;
break;
}
for (p = 1; p < limit; p++)
slice[j][p] = rand() % 100;
}
if (prog[proc_curent].duration == 0)
{
cnt_no_tasks ++;
perf[proc_curent][2] = i;
if (cnt_no_tasks == NO_TASKS)
break;
else
{
slice[proc_curent][0] = 3;
cnt = 0;
for (j = 99; j >= 0; j--)
for (p = 0; p < nr_proc; p++)
for (q = 1; q < 9; q++)
if (slice[p][q] == j && slice[p][0]
== 2) //cautam un proces in starea
ready cu lozul ales j
{
slice[p][q] = slice[p][q] +100;
proc_curent = p;
if (perf[proc_curent][3] == 0)
perf[proc_curent][1] = i;
perf[proc_curent][3] = 1;
goto proc_finished;
}
proc_finished:
74
test = 0;
for (p = 0; p < nr_proc; p++)
for (q = 1; q < 9; q++)
if (slice[p][q] >= 0 && slice[p][q]
< 100 && slice[p][0] == 2)
test = 1;
if (test == 0)
for (p = 0; p < nr_proc; p++)
for (q = 1; q < 9; q++)
if (slice[p][q] >= 100)
slice[p][q] = slice[p][q]
- 100;
std::cout<<"La timpul "<<i<<" s-a lansat in
executie procesul "<<proc_curent<<std::endl;
}
}
if (cnt >= TM_SLICE)
{
cnt = 0;
for (j = 99; j >= 0; j--)
for (p = 0; p < nr_proc; p++)
for (q = 1; q < 9; q++)
if (slice[p][q] == j &&
slice[p][0] == 2) //cautam un
proces in starea ready cu lozul
ales j
{
slice[p][q] = slice[p][q] +100;
proc_curent = p;
if (perf[proc_curent][3] == 0)
perf[proc_curent][1] = i;
perf[proc_curent][3] = 1;
goto new_ts;
}
new_ts:
test = 0;
for (p = 0; p < nr_proc; p++)
for (q = 1; q < 9; q++)
if (slice[p][q] >= 0 && slice[p][q]
< 100 && slice[p][0] == 2)
test = 1;
if (test == 0)
for (p = 0; p < nr_proc; p++)
for (q = 1; q < 9; q++)
if (slice[p][q] >= 100)
{
slice[p][q] = slice[p][q]
- 100;
}
75
std::cout<<"La timpul "<<i<<" s-a lansat in
executie procesul "<<proc_curent<<std::endl;
}
}
for (j = 0; j < NO_TASKS; j++)
{
Turn_t = Turn_t + perf[j][2] - perf[j][0];
Resp_t = Resp_t + perf[j][1] - perf[j][0];
}
Turn_t = Turn_t / NO_TASKS;
Resp_t = Resp_t / NO_TASKS;
printf("\nTimpul mediu de terminare este %d\n", Turn_t);
printf("\nTimpul mediu de raspuns este %d\n", Resp_t);
}
int main(int argc, char *argv[])
{
int i, j;
srand (time(NULL)); //comenteaza pentru a nu tine cont de timp
for (i=0; i <NO_TASKS; i++)
prog[i].start_t = rand() % 400;
//se genereaza aleator momentele de inceput a task-urilor
for (i=0; i <NO_TASKS; i++)
prog[i].duration = rand() % 350 + 150;
//se genereaza aleator durata task-urilor
for (i=0; i <NO_TASKS; i++)
prog[i].prio = (rand() % 5) * 4; //se genereaza aleator
prioritatile
for(i=0; i <NO_TASKS; i++) //se sorteaza dupa ordinea aparitiei
task-urilor
for(j=i+1; j <NO_TASKS; j++)
if(prog[i].start_t > prog[j].start_t)
{
aux = prog[i];
prog[i] = prog[j];
prog[j] = aux;
}
for (i=0; i <NO_TASKS; i++) //initializam id-urile task-urilor
prog[i].id = i;
for (i=0; i <NO_TASKS; i++)
printf("Procesul %d a fost creat la timpul %d, are durata
%d si prioritatea %d \n", prog[i].id, prog[i].start_t,
prog[i].duration, prog[i].prio);
printf("\n\n");
76
//fi_fo();
//shortes_job();
//priority();
//tm_slice();
lottery_tm_slice();
system("pause");
}
77
8 Bibliografie:
[1] Tanenbaum, Andrew S. 2007. Modern Operating Systiems, 3rd Ed.– capitolele 2.1, 2.4
[2] A. Silberschatz, G. Gagne, P. Galvin. 2005. Operating System Concepts 7th ED. s.l. :
Wiley. – capitolele 2.3, 2.4, 2.5
[3] Laplante, Philip A. 2004. Real-Time Systems design and analysis 3rd Edition. s.l. : Wiley
Interscience, IEEE Press.
[4] Dragoicea, Monica. 2009. Programarea Aplicaţiilor în Timp Real. Teorie şi Practică. –
capitolele 3.3, 3.8
[5] Dumitrache, Ioan. 2010. Automatica vol. I. s.l. : Editura Academiei Romane, 2010.
[6] Saru, Daniela and Mocanu, Stefan. 2010. Comunicare si sincronizare intre procese
utilizator in sistemul de operare QNX. Bucuresti : Printech.
[7] Tanenbaum, S. Andrew. 2006. Operating Systems Design and Implementation, 3rd
Edition. s.l. : Prentce Hall.
[8] Hoglund, Greg and Butler, James. 2005. Rootkits: Subverting the Windows Kernel. s.l. :
Addison Wesley Professional.
[9] Antunes de Almeida, Rodrigo Maximiano. 2011. Microkernel development: From
project to implementation, Techinal Notes. Universidade Federal de Itajubá : s.n. .
[10] Baumann, Christian. 2009. Real Time Operating Systems (RTOS).
[11] ARM. Cortex-M3 Technical Reference Manual Revision: r1p1 2006. s.l. .
[12] STMicroelectronics AN2606, Application note STM32™ microcontroller system
memory boot mode.
[13] STMicroelectronics. 2011. STM32F105xx, STM32F107xx, Doc ID 15274, Rev 6. 2011.
[14] ARM. Overview of the Cortex-M3, Chappter 2.
[15] Gupta, Preeti. 2012. http://guptapreeti.blogspot.ro/2012/03/alternating-sequence-of-cpu-
and-io.html. 9.3.2012. [Accesat la data de 4.6.2013.]
[16] ARM Infocenter. http://infocenter.arm.com/help/index.jsp. [Accesat la data de
12.5.2013.]
[17] Kesden, Gregory. 2001. http://www.cs.cmu.edu/~gkesden/412-
18/fall01/ln/lecture5.html. 7.9.2001. [Accesat la data de 16.6.2013.]
[18] Hafsal. Real-Time Operating Systems. http://vetechlib.blogspot.ro/2009/10/real-time-
operating-systems.html. [Accesat la data de 19.6.2013.]
[19] Wikipedia. 2006. Wikipedia Hibrid kernel. http://en.wikipedia.org/wiki/Hybrid_kernel.
78
19 4 2006. [Accesat la data de 24.6.2013.]
[20] ThaiEasyElec. STM32F107-Stamp-Module. http://www.thaieasyelec.com/Development-
Tools/ARM/STM32F107-Stamp-Module.html. [Accesat la data de 14.06.2013.]
[21] STMicroelectronics. ST Catalog - ST Link v2.
http://www.st.com/web/catalog/tools/FM146/CL1984/SC724/SS1677/PF251168.
[Accesat la data de 16.6.2013.]
[22] CoActionOS. http://www.coactionos.com/embedded-design/36-context-switching-on-
the-cortex-m3.html. [Accesat la data de 6.12.2013.]
[23] ThreadX. RTOS. http://rtos.com/products/threadx/. [Accesat la data de 30.6.2013.]
[24] FreeRTOS. http://www.freertos.org/tutorial/. Real Time Engineers ltd. [Accesat la data
de 30.06.2013.]
[25] QNX. http://www.qnx.com/products/neutrino-rtos/rtos_evaluation.html. [Accesat la data
de 30.6.2013.]
