curs patr 10-14
Post on 23-Nov-2015
81 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
PROGRAMAREA APLICAIILOR N N
TIMP-REAL
Semestrul 2, 2013-2014
Monica DrgoiceaDepartament Automatica si Ingineria Sistemelor
Curs 10-14
-
Comunicatia intre procese: studiu de caz - QNX
QNX Neutrino suporta mai multe mecanisme de comunicare intre procese (IPC):
mesaje Neutrino native pulsuri semnale memorie partajata pipe-uri (buffere dinamice) cozi de mesaje POSIX
4/27/2014 Programarea Aplicatiilor in Timp Real 2
-
Continutul cursului:
Semnale
Planificarea taskurilor pe conditie de timp
Programarea Aplicatiilor in Timp Real4/27/2014 3
-
Semnale - definitii:
semnale
un mecanism asincron de tratare a evenimentelor
spre deosebire de mesaje, semnalele sunt indicatoare complet asincrone ale evenimentelor care apar in sistem
semnalele mai sunt denumite si intreruperi software, deoarece pot schimba fluxulnormal de executie al programului la orice moment de timp si in orice loc al executiei
semnalele pot fi generate intr-un proces ca urmare a unei erori (de exemplu, semnalele pot fi generate intr-un proces ca urmare a unei erori (de exemplu, impartire la zero), a unui eveniment (de exemplu, se tasteaza CTRL-C), sauatunci semnalul este generat de catre un proces (de exemplu, cu functia kill())
4/27/2014 4Programarea Aplicatiilor in Timp Real
-
4/27/2014 5Programarea Aplicatiilor in Timp Real
-
Semnale:
semnalele trebuie "tratate" in mod special de procese
rutine de tratare a semnalelor (engl. signal handlers) cei trei pasi de procesare asociati semnalelor sunt
generarea semnalelor transmiterea semnalelor tratarea semnalelor
Exemplusemnale - QNXsemnale - QNX
4/27/2014 6Programarea Aplicatiilor in Timp Real
-
4/27/2014 7Programarea Aplicatiilor in Timp Real
-
Semnale:
Exista trei modalitati in care un proces poate lua in considerare un semnal:
procesul poate trata semnalul prin definirea unei functii speciale (engl. signal-handler) care sa fie apelata si sa prinda (catch a signal) semnalulde fiecare data cand acesta este primit;
procesul poate ignora in mod explicit semnalul (caz in care semnalul estepierdut), nefiind executata nici o actiune;
procesul accepta semnalul in mod implicit, si in acest caz se aplicaactiunea default, care in mod normal presupune terminarea procesului
4/27/2014 8Programarea Aplicatiilor in Timp Real
-
Semnale:
exista un numar predefinit de semnale, fiecaruia fiindu-i alocat un numar intreg
exista, de asemenea, un numar de semnale definite de utilizator ce pot fi folosite in aplicatii
semnalele sunt identificate prin nume si numar semnalele sunt identificate prin nume si numar
unele semnale sunt asociate evenimentelor care le-au generat (de exemplu, SIGINT, generat de o intrerupere de la tastura)
altele nu au asociate evenimente predefinite (de exemplu, SIGUSR1).
detalii despre semnale sunt disponibile in biblioteca QNX signal.h
exemplu QNX: exemplu QNX:
s-a definit SIGRTMIN pentru primul semnal de timp real si SIGRTMAX pentru ultimulsemnal de timp real
doar semnalele ale caror numere se afla intre SIGRTMIN si SIGRTMAX suntconsiderate semnale POSIX de timp real
4/27/2014 9Programarea Aplicatiilor in Timp Real
-
Semnale (exemplu QNX):
4/27/2014 10Programarea Aplicatiilor in Timp Real
-
Semnale:
un semnal poate
fi livrat (delivery) imediat procesului caruia ii este destinat
poate fi blocat (mai tarziu, despre masti de semnal) si livrat mai tarziu
un semnal blocat intra in starea de asteptare a livrarii(este pending)
standardul POSIX include conceptul de asezare in coada a semnalelor de timp-real
4/27/2014 11Programarea Aplicatiilor in Timp Real
-
Semnale generarea semnalelor sub QNX:
anumite semnale sunt generate in mod automat la aparitia anumitor evenimente (de exemplu, se genereaza un semnal la arithmetic, invalid instruction and memory protection faults)
alte semnale pot fi generate pentru a raporta evenimente de un anumit tip (de exemplu, CTRL-C de la tastatura, finalizarea unei operatii asincrone de I/O, expirarea unui timer)
anumite semnale pot fi generate de catre un proces prin intermediul functiilor kill() siraise()
un proces isi poate trimite un semnal, de exemplu atunci cand expira o alarma(SIGALARM) sau la terminarea unei operatii de intrare / iesire asincrona
aparitia unui semnal poate fi asteptata cu ajutorul functiei pause() acest apel blocheaza programul panaa la aparitia semnalului si procesarea
acestuia in rutina specifica
4/27/2014 12Programarea Aplicatiilor in Timp Real
-
Semnale generarea semnalelor sub QNX:
Modalitatile prin care un proces poategenera un semnal care va fi trimis unui alt proces suntproces sunturmatoarele:
prin intermediulfunctiei kill();
cu ajutorul functieisigqueue(). Aceasta functiepoate trimitenumai semnale de numai semnale de timp real;
cu ajutorul functieiraise().
4/27/2014 13Programarea Aplicatiilor in Timp Real
-
4/27/2014 14Programarea Aplicatiilor in Timp Real
-
4/27/2014 15Programarea Aplicatiilor in Timp Real
-
Semnale tratarea semnalelor sub QNX:
actiunea default a celor mai multe semnale este aceea de a termina (engl. kill ) procesulcare le primeste, dar este posibil ca aceast comportament implicit sa fie evitat princare le primeste, dar este posibil ca aceast comportament implicit sa fie evitat prinfolosirea unor handlere se semnal dedicate, definite de programatorul aplicatiei
multe semnale sunt generate de erori serioase, cum ar fi cele de memorie sau de cadereatensiunii de alimentare
aceste erori nu pot fi remediate si nu se poate face mare lucru pentru a le evita
pe de alta parte, anumite semnale (de exemplu, SIGCONT) sunt benigne si sunt utilizate pe de alta parte, anumite semnale (de exemplu, SIGCONT) sunt benigne si sunt utilizatedoar pentru a atentiona utilizatorul in privinta unui anumit eveniment
4/27/2014 16Programarea Aplicatiilor in Timp Real
-
Semnale tratarea semnalelor sub QNX:
4/27/2014 17Programarea Aplicatiilor in Timp Real
-
Semnale tratarea semnalelor sub QNX:
in general, procesarea semnalelor prin intermediul rutinelor de tratare a semnalelor (handlere de semnal) presupune trei pasi:semnalelor (handlere de semnal) presupune trei pasi:
definirea semnalului care va fi procesat in rutina;
declararea rutinei de tratare a semnalului;
instalarea rutinei de tratare a semnalului (cu functia sigaction()).
4/27/2014 18Programarea Aplicatiilor in Timp Real
-
Semnale tratarea semnalelor sub QNX:
#define MySig
// declara handler semnal
void handler(int signo, ){void handler(int signo, ){switch(signo){
case ... : ....case MySig:executa_ceva();
// continua executia taskului din punctul in care // a fost intreruptbreak;
default: break;}
}
main(){instaleaza_handler_semnal(handler);......
executa_operatii();...
}
4/27/2014 19Programarea Aplicatiilor in Timp Real
-
Semnale tratarea semnalelor sub QNX (exemplu):#include #include #include #include #include
static volatile sig_atomic_t sig_count = 0;
void sig_handler(int sig_no){if( sig_no == SIGALRM)
printf("A expirat alarma! \n");elseif(sig_no == SIGSEGV){printf("Segment violation! \n");signal(SIGSEGV, SIG_DFL);
}elseif(sig_no == SIGCHLD)
printf("S-a terminat procesul fiu! \n");elseelse
if(sig_no == SIGINT)printf("Break ! \n");
elseif(sig_no == SIGUSR1)printf("Semnal de la user ! \n");
++sig_count;}
4/27/2014 20Programarea Aplicatiilor in Timp Real
-
Semnale tratarea semnalelor sub QNX (exemplu):main(void){
int n;void sig_handler(int);
signal(SIGALRM, sig_handler);signal(SIGALRM, sig_handler);
/*signal(SIGSEGV, sig_handler);*/
signal(SIGCHLD, sig_handler);signal(SIGINT, sig_handler);signal(SIGUSR1, sig_handler);
alarm(10);
if(spawnl(P_NOWAIT, "./ex_schild.out", "./ex_schild.out", NULL) != 1)for(n=20; n; )n = sleep(n);
printf("%d semnale \n", sig_count);
*((char*)1) = 0; /* genereaza o ultima eroare */
}
4/27/2014 21Programarea Aplicatiilor in Timp Real
-
Semnale tratarea semnalelor sub QNX (exemplu):
/* ex_schild.c */
#include #include #include
main(void){printf("Proces fiu ... \n");sleep(5);exit(123);
}
4/27/2014 22Programarea Aplicatiilor in Timp Real
-
4/27/2014 23Programarea Aplicatiilor in Timp Real
-
Semnale tratarea semnalelor sub QNX (exemplu):
semnalul cu numarul 16, SIGUSR1, poate fi transmis din alt terminal, cu comanda:
# slay -sUSR1 signal.out
OBSERVATIE:
deoarece linia de cod care trateaza semnalul SIGSEGV este comentata, procesul, nu vaputea trata acest semnal in rutina si se va termina fortat
eroarea primita este:
# Memory fault (core dumped)
4/27/2014 24Programarea Aplicatiilor in Timp Real
-
Semnale transmiterea semnalelor:
masti de semnal
tratarea semnalelor:
sigaction() signal()
4/27/2014 25Programarea Aplicatiilor in Timp Real
-
Planificarea pe conditie de timp
notiuni referitoare la "timp" acces la un "ceas"
planificarea taskurilor pe conditie de timp
utilizarea semnalelor pentru instalarea unei baze de timp in aplicatiile software in timp-real
alarme
pulsuri
4/27/2014 Programarea Aplicatiilor in Timp Real 26
pulsuri
-
Notiuni referitoare la "timp":
din punct de vedere al limbajului de programare utilizat, pentru implementarea unei aplicatiisoftware (de conducere de procese) in timp-real sunt necesare:
un model de concurenta reprezentarea notiunii de timp
sa existe o interfata cu "timpul", adica sa avem un "ceas" cu care sa masuramscurgerea timpului
cum specificam cerintele de timp (deadline-uri) ? cum verificam daca cerintele de timp sunt indeplinite?
un sistem (embedded) in timp-real trebuie sa-si poata coordona executia cu "timpul" mediului in care opereaza
4/27/2014 Programarea Aplicatiilor in Timp Real 27
"Real" = facem distinctia intre"timpul" vazut ca dimensiune a mediului de operare si "ceasul"
calculatorului
Timpul este "real" pentruca este extern
sistemului de calcul
-
Notiuni referitoare la "timp":
avand acces la o baza de timp, pot fi definite trei tipuri de operatii realizate n functie de timp:timp:
(a) asteptare un interval de timp T (de exemplu, cu sleep(), pause(), etc);
(b) executie a unei operatii unice la un moment specificat de timp absolut (de exemplu, la HH:MM:SS) sau relativ (de exemplu, peste T)
(c) operatii ciclice cu perioada de timp specificata, T;
planificarea taskurilor pe conditie de timp se poate realiza in doua moduri:
4/27/2014 Programarea Aplicatiilor in Timp Real 28
ca planificare ciclica
ca planificare prin intermediul unui task planificator
-
Planificare ciclica:
taskul se reprogrameaza singur prin intermediul unei directive de tip asteapta(T) si vafunctiona in bucla infinita
intervalul de reprogramare al taskului este ( + T)
T este este timpul de asteptare, este timpul de executie al taskului
din punct de vedere al programului, este necesara urmatoarea secventa de instructiuni:Task planificat
...
+ T + T
4/27/2014 Programarea Aplicatiilor in Timp Real 29
...
while(true){
actiune_task();
asteapta(T);
}
-
Planificare ciclica:
primitiva asteapta(T) are efect numai asupra taskului care a lansat-o
nucleul va realiza urmatoarele actiuni neintreruptibile:
trece valoarea T intr-un contor aferent taskului trece valoarea T intr-un contor aferent taskului blocheaza taskul pana la expirarea intervalului de timp T
decrementeaza contorul cu o cuanta de timp la fiecare intrerupere data de ceasul de timpreal
trece taskul in starea gata de executie la anularea contorului si declara evenimentsemnificativ
intervalul de reprogramare al taskului este ( + T), cu variabil deoarece momentul intrarii in executie al taskului si durata executiei sale nu sunt
cunoscute (la expirarea intervalului de timp T taskul este trecut in stare gata de
4/27/2014 Programarea Aplicatiilor in Timp Real 30
cunoscute (la expirarea intervalului de timp T taskul este trecut in stare gata de executie, urmand a fi adus in executie de catre planificatorul de taskuri in functie de politica planificare nucleului)
acest mod de planificare a executiei unui task poate fi satisfacator daca
-
Planificare prin intermediul unui task planificator:
acest tip de planificare pe conditie de timp permite ca intervalul de reprogramare al taskului, T, sa fie cunoscut si sa fie respectat
TT
intervalul va fi masurat exact si urmatoarea actiune va incepe fix dupa intervalul T (intervalul de reprogramare al taskului este T)
Interval de executie altaskului reprogramat
Timp de asteptare al taskului reprogramat
4/27/2014 Programarea Aplicatiilor in Timp Real 31
(intervalul de reprogramare al taskului este T)
-
Planificare prin intermediul unui task planificator:
4/27/2014 Programarea Aplicatiilor in Timp Real 32
-
Servicii de ceas sub QNX:
Standardul ANSI C:
toate operatiile pentru accesul la o baza de timp utilizeaza structuri de date sifunctii definite de standardul ANSI C
standardul ANSI C furnizeaza o biblioteca standard pentru interfatarea cu timpulcalendaristic, care defineste timpul sub forma time_t si contine mai multerutine pentru manipularea obiectelor de tip timp
4/27/2014 Programarea Aplicatiilor in Timp Real 33
-
Servicii de ceas sub QNX - standardul ANSI C:
4/27/2014 Programarea Aplicatiilor in Timp Real 34
-
Servicii de ceas sub QNX - standardul POSIX:
4/27/2014 Programarea Aplicatiilor in Timp Real 35
-
Servicii de ceas sub QNX - standardul POSIX:
4/27/2014 Programarea Aplicatiilor in Timp Real 36
-
Operatii uzuale cu baza de timp citirea timpului calendaristic:
4/27/2014 Programarea Aplicatiilor in Timp Real 37
-
Servicii de ceas sub QNX - standardul POSIX:
4/27/2014 Programarea Aplicatiilor in Timp Real 38
-
Operatii uzuale cu baza de timp citirea timpului calendaristic:
/* citeste timpul curent in secunde masurate de la 1 Ianuarie 1970 (in UTC) */
#include #include
time_t acum;time_t acum;char *ptr;
struct tm *tod;
main(void){time(&acum);tod = localtime(&acum);ptr = asctime(tod);printf("Momentul curent de timp este %s\n", ptr);
}
4/27/2014 Programarea Aplicatiilor in Timp Real 39
Output:
$ Momentul curent de timp este Wed May 5 04:30:49 2010
-
Operatii uzuale cu baza de timp calculul duratei unui eveniment:
deoarece functia time() calculeaza timpul in secunde, poate fi folosita pentru calcululintervalelor de timp pentru diferite sectiuni ale unui program, presupunand ca o rezolutie de 1 secunda este suficienta
time_t start, interval;start = time(NULL);...
// executie sectiune de cod...
interval = time(NULL) - start;
4/27/2014 Programarea Aplicatiilor in Timp Real 40
in plus, se poate folosi functia difftime(), care returneaza o valoare de tip double:
diff = difftime(time(NULL), start);
-
Exemplu:
#include #include #include
time_t start, interval;
int main(int argc, char *argv[]) {int main(int argc, char *argv[]) {
double diff;start = time(NULL);sleep(5);interval = time(NULL) - start;printf("Diferenta de timp este = %d secunde.\n", interval);sleep(5);diff = difftime(time(NULL), start);printf("Diferenta de timp este = %2.2f secunde.\n", diff);
}
4/27/2014 Programarea Aplicatiilor in Timp Real 41
Output program:
$ Diferenta de timp este = 5 secunde.$ Diferenta de timp este = 10.00 secunde.
-
Operatii uzuale cu baza de timp operatii cu delay:
in plus fata de accesul la un ceas, procesele trebuie sa aiba posibilitatea de a-si intarzia(engl. to delay) executia fie pe o perioada relativa de timp, fie pana la un anumit moment in viitor
sub standardul POSIX, un delay poate fi obtinut prin intermediul apelurilor de sistem sleep() (pentru rezolutii mari, de exemplu un delay de ordinul secundelor) sau nanosleep() (pentru rezolutii mai mici) - apel masurat in functie de ceasul de timp-
real CLOCK_REALTIME
un proces se poate auto-suspenda pe un interval de maxim 65535 secunde apeland functiasleep():
4/27/2014 Programarea Aplicatiilor in Timp Real 42
#include
... ...
sleep(10); // sleep de 10 secunde
-
Operatii uzuale cu baza de timp operatii cu delay:
sistemul de operare in timp-real QNX asigura si delay-uri de ordinul milisecundelor:#include
... ...
delay(250); // suspenda procesul pentru 250 ms
pentru intervale foarte mici de timp se poate folosi functia nanosleep():
#include
struct timespec interval, remaining;
interval.tv_sec = 0; // 0 secunde
4/27/2014 Programarea Aplicatiilor in Timp Real 43
interval.tv_sec = 0; // 0 secunde
interval.tv_nsec = 100; // 100 ms
nanosleep(&interval, &remaining);
-
Servicii de ceas sub QNX - standardul POSIX:
4/27/2014 Programarea Aplicatiilor in Timp Real 44
-
Servicii de ceas sub QNX - standardul POSIX:
QNX Neutrino 2 furnizeaza un set complet de functionalitati POSIX pentru accesul la o baza de timp (acces la un ceas)baza de timp (acces la un ceas)
timpul poate fi masurat cu diverse baze de timp, de la secunde pana la nanosecunde
sub QNX data poate fi setata ntre Ianuarie 1970 si Ianuarie 2554, nsa standardulPOSIX poate introduce o limitare la anul 2038
4/27/2014 Programarea Aplicatiilor in Timp Real 45
-
Servicii de ceas sub QNX - standardul POSIX:
4/27/2014 Programarea Aplicatiilor in Timp Real 46
-
Servicii de ceas sub QNX - standardul POSIX:
4/27/2014 Programarea Aplicatiilor in Timp Real 47
-
Bibliografie:
Programarea aplicatiilor in timp real, capitolul 6, pag. 169, sectiunile 6.1 si 6.2
4/27/2014 Programarea Aplicatiilor in Timp Real 48
-
Continutul cursului:
Planificarea taskurilor pe conditie de timp
Contoare de timp (timere)
Programarea Aplicatiilor in Timp Real4/27/2014 49
-
Cuprins curs:
planificarea taskurilor pe conditie de timp contoare de timp (timere)
notificare prin intermediul pulsurilor notificare prin intermediul alarmelor
4/27/2014 Programarea Aplicatiilor in Timp Real 50
-
Timere:
timerele POSIX furnizeaza un mecanism prin care un fir de executie poate fianuntat ca a expirat un anumit interval de timp (timeout) masurat cu un anumitceas
necesita utilizarea mecanismului de transmitere de semnale al sistemului de operare
conform modelului de timere POSIX un timer poate expira:
la o data exprimata in valoare absoluta
4/27/2014 Programarea Aplicatiilor in Timp Real 51
la o data exprimata in valoare relativa (e.g. n nanosecunde din acestmoment)
ciclic (i.e. la fiecare n nanosecunde)
-
Timere:
4/27/2014 Programarea Aplicatiilor in Timp Real 52
-
Timere:
timerele sunt considerate a fi o sursa de generare de evenimente in sistem, din care cauza apeleaza la sistemul de livrare a evenimentelor asociat nucleului
o aplicatie poate cere ca orice eveniment suportat de microkernelul Neutrino o aplicatie poate cere ca orice eveniment suportat de microkernelul Neutrino sa-i fie livrat la expirarea unui timeout
din aceasta cauza, expirarea unui timer poate fi semnalizata cu un semnalSIGALRM (asociat functiei alarm()) sau cu orice alt semnal POSIX de timp-real
4/27/2014 Programarea Aplicatiilor in Timp Real 53
-
Timere:
pentru aplicatiile de timp real sunt utile doua tipuri de timere:
one-shot. Este un timer armat initial cu o valoare de expirare, relativ la momentul curent sau absolut (in functie de o baza de timp). Expira o singuramomentul curent sau absolut (in functie de o baza de timp). Expira o singuradata si apoi este dezarmat;
periodic. Este un timer armat initial cu o valoare de expirare, relativ la momentul curent sau absolut, si cu un interval de repetitie. La expirareaintervalului initial, timer-ul este reincarcat cu intervalul de repetitie si continua sa numere
un timer QNX este de fapt o structura de date care trebuie sa fie creata, utilizata
4/27/2014 Programarea Aplicatiilor in Timp Real 54
un timer QNX este de fapt o structura de date care trebuie sa fie creata, utilizatao data sau de mai multe ori, si apoi distrusa
-
Crearea timerelor:
principalele structuri de date pentru manipularea timerelor:
4/27/2014 Programarea Aplicatiilor in Timp Real 55
Programarea aplicatiilor in timp real, capitolul 6, pag. 178
-
Crearea timerelor:
principalele functii pentru manipularea timerelor:
4/27/2014 Programarea Aplicatiilor in Timp Real 56
-
Crearea timerelor:
4/27/2014 Programarea Aplicatiilor in Timp Real 57
-
Crearea timerelor:
4/27/2014 Programarea Aplicatiilor in Timp Real 58
-
Setarea timerelor:
timer-ul se armeaza prin asocierea unui timp de alarmare si (optional) a uneiperioade de repetitie
timpul de alarmare poate fi setat relativ (la momentul apelului) sau absolut de exemplu, un timer care va suna prima data dupa o secunda si apoi repetat, la de exemplu, un timer care va suna prima data dupa o secunda si apoi repetat, la
fiecare 50 ms, se instaleaza astfel:
// seteaza parametrul timer-ului la 1 secunda, 0 nanosecunde
timer.it_value.tv_sec = 1;
timer.it_value.tv_nsec = 0;
// seteaza parametrii pentru repetarea automata a timer-ului la 50ms
4/27/2014 Programarea Aplicatiilor in Timp Real 59
// seteaza parametrii pentru repetarea automata a timer-ului la 50ms
timer.it_interval.tv_sec = 0;
timer.it_interval.tv_nsec = 50000000;
timer_settime(tid, 0, &timer, NULL);
-
Setarea timerelor:
timerul poate fi setat sa sune o singura data alegand it_interval = 0:
timer_t tid;
...
timer.it_value.tv_sec = 1;
timer.it_value.tv_nsec = 0;
timer.it_interval.tv_sec = 0;
timer.it_interval.tv_nsec = 0;
...
4/27/2014 Programarea Aplicatiilor in Timp Real 60
...
timer_settime(tid, 0, &timer, NULL);
-
Setarea timerelor:
timerul poate fi dezactivat alegand it_value = 0:
timer_t tid;
...
timer.it_value.tv_sec = 0;
timer.it_value.tv_nsec = 0;
timer.it_interval.tv_sec = 0;
timer.it_interval.tv_nsec = 50000000;
4/27/2014 Programarea Aplicatiilor in Timp Real 61
timer.it_interval.tv_nsec = 50000000;
...
timer_settime(tid, 0, &timer, NULL);
-
Planificarea ciclica a taskurilor prin intermediul timerelor:
posibilitatea de a planifica un timer pentru activare ciclica este utila pentruplanificarea periodica a firelor de executie
un timer este o sursa periodica de evenimente care poate fi utilizata pentru a un timer este o sursa periodica de evenimente care poate fi utilizata pentru a forta un fir de executie sa se activeze la anumite momente de timp, dupa care saintre in sleep pana la urmatorul eveniment
firul de executie va programa timer-ul o singura data si apoi va raspunde la aparitia periodica a evenimentelor
un timer este asemanator unui ceas cu alarma care face o numaratoare inversape un anumit interval, semnalizand expirarea acestuia
4/27/2014 Programarea Aplicatiilor in Timp Real 62
spre deosebire de sleep(), un timer nu suspenda procesul (firul) apelant
-
Planificarea ciclica a taskurilor prin intermediul timerelor:
un fir de executie isi poate seta ciclic un timer, asteptand un semnal pentru care nu are un handler
pentru setarea timer-ului se poate folosi semnalul SIGALRM pentru setarea timer-ului se poate folosi semnalul SIGALRM
OBSERVATIE:
deoarece semnalele sunt tratate global in cadrul unui proces POSIX, ele nu suntlegate de un anumit fir de executie din cadrul procesului. De aceea, pentru ca acest exemplu sa functioneze, nici un alt fir de executie nu trebuie sa foloseascasemnalul SIGALRM pentru (orice) alt scop
4/27/2014 Programarea Aplicatiilor in Timp Real 63
semnalul SIGALRM pentru (orice) alt scop
sunt necesare doua structuri de lucru, sigevent si itimerspec
-
Ceasuri si timere: cum primeste kernelul intreruperi periodice de la hardware si ce face cu aceste intreruperi?
OBSERVATIE:
kernelul poate replanifica procese si /sau fire de executie in trei situatii:
la aparitia unei intreruperi hardware la aparitia unei intreruperi hardware cand se face un apel de sistem (system call) la declararea unei exceptii (fault)
exemplu:
daca un fir de executie face sleep(), biblioteca C contine cod care in final face apella o functie (apel) de sistem
acest apel scoate firul de executie din coada RUNNING si porneste un timer
4/27/2014 Programarea Aplicatiilor in Timp Real
acest apel scoate firul de executie din coada RUNNING si porneste un timer (countdown)
in acelasi timp kernelul primeste intreruperi hardware la intervale egale de la ceasulhardware (de exemplu, la 10 ms)
aceste intreruperi sunt tratate de catre rutina de tratare a intreruperilor de ceas a kernelului (ISR)
64
-
Ceasuri sursa intreruperilor de ceas Help QNX Momentics IDE QNX Neutrino Realtime Operating System > Getting Started with QNX Neutrino: A Guide for Realtime Programmers
sursa circuite hardware (capitolul Clocks, Timers, and Getting a Kick Every So Often) in bibligrafia de pe site !!!!
4/27/2014 Programarea Aplicatiilor in Timp Real 65
-
Timere: tipuri de timere
relative = perioada de expirare (timeout) este specificata relativ la momentul curent(peste ...)
absolute = momentul de expirare (timeout) este specificat exact la momentul dorit (la data de ...)
one-shot = suna o singura data periodic = suna periodic, la intervalul specificat
cum verificam ca a expirat timpul?
scheme de notificareOBSERVATIE:
daca se face un simplu delay, la expirarea timpului de asteptare procesul sau firul de executie este trecut inapoi in starea READY (gata de executie)
4/27/2014 Programarea Aplicatiilor in Timp Real
executie este trecut inapoi in starea READY (gata de executie) in cazul timerelor periodice sau one-shot, se poate:
trimite un puls exemplul prezentat la curs ! trimite un semnal exemplul prezentat la curs, cu alarma ! crea un thread
66
-
Scheme de notificare:
in orice schema de notificare se foloseste o structura sigevent
detalii ale definitiilor se gasesc in
struct sigevent {int sigev_notify; // tipul de notificareunion {
int sigev_signo;int sigev_coid;int sigev_id;void (*sigev_notify_function) (union sigval);
};union sigval sigev_value;union {
struct {
4/27/2014 Programarea Aplicatiilor in Timp Real
struct {short sigev_code;short sigev_priority;
};pthread_attr_t *sigev_notify_attributes;
};};
67
-
Scheme de notificare tipul de notificare:
sigev_notify: determina tipul de notificare selectat, adica:
SIGEV_PULSE se va transmite un puls se va transmite un puls
SIGEV_SIGNAL, SIGEV_SIGNAL_CODE, sau SIGEV_SIGNAL_THREAD se va transmite un semnal
SIGEV_UNBLOCK not used in this case; used with kernel timeouts
SIGEV_INTR not used in this case; used with interrupts
SIGEV_THREAD
4/27/2014 Programarea Aplicatiilor in Timp Real
SIGEV_THREAD creaza un thread
deoarece folosim aceasta structura pentru timere, ne intereseaza doar SIGEV_PULSE, SIGEV_SIGNAL si SIGEV_THREAD
68
-
Scheme de notificare notificare prin semnale:
4/27/2014 Programarea Aplicatiilor in Timp Real 69
-
Scheme de notificare notificare prin pulsuri:
se trimite un puls la expirarea timer-ului se seteaza campul sigev_notify la SIGEV_PULSE
se transmite informatie suplimentara, astfel: se transmite informatie suplimentara, astfel:
4/27/2014 Programarea Aplicatiilor in Timp Real 70
-
Utilizarea timerelor:
operatii necesare pentru utilizarea timerelor:
crearea unui obiect de tip timer se decide schema de notificare (semnal, puls sau creare thread) si se creaza
structura de notificare (struct sigevent) se alege tipul de timer (relativ / absolut sau one-shot / periodic) se porneste timer-ul
4/27/2014 Programarea Aplicatiilor in Timp Real 71
-
Crearea timerelor:
timerul se creaza cu functia timer_create()
#include #include int timer_create (clockid_t clock_id, struct sigevent *event,int timer_create (clockid_t clock_id, struct sigevent *event,
timer_t *timerid); argumentul clock_id specifica baza de timp cu care va fi creat acest timer
OBSERVATIE:
standardul POSIX spune ca se pot folosi mai multe baze de timp, pe diferiteplatforme, dar orice platforma trebuie sa suporte cel putin baza de timp data de CLOCK_REALTIME
sub Neutrino pot fi alese 3 baze de timp:
4/27/2014 Programarea Aplicatiilor in Timp Real
sub Neutrino pot fi alese 3 baze de timp: CLOCK_REALTIME
CLOCK_SOFTTIME
CLOCK_MONOTONIC
72
-
Ce fel de timer:
se specifica cu o combinatie de argumente in functia timer_settime(), utilizatapentru pornirea timer-ului:
#include #include int timer_settime (timer_t timerid,int flags, struct itimerspec *value,
struct itimerspec *oldvalue);
argumentul timerid este valoarea returnata de functia timer_create() intr-o aplicatie pot fi create mai multe timere si apoi se apeleaza
timer_settime() individual pentru fiecare, pentru setare si pornire
argumentul flags specifica tipul de timer
4/27/2014 Programarea Aplicatiilor in Timp Real
daca este setat la valoarea constanta TIMER_ABSTIME, timerul va fi de tip absolut
daca este setat la zero, timer-ul va fi considerat relativ la momentul curent
73
-
Cum se specifica timpul:
cu ajutorul celor doua structuri definite in
struct timespec {long tv_sec,long tv_sec,
tv_nsec;};
struct itimerspec {struct timespec it_value,
it_interval;};
struct itimerspec are doi membri:
it_value
4/27/2014 Programarea Aplicatiilor in Timp Real
valoare one-shot it_interval
valoare de reincarcare
74
-
Setarea timerelor:
timer-ul se armeaza prin asocierea unui timp de alarmare si (optional) a unei perioade de repetitie (se reincarca)
timpul de alarmare poate fi setat relativ (la momentul apelului) sau absolut de exemplu, un timer care va suna prima data dupa o secunda si apoi repetat, la fiecare 50 de exemplu, un timer care va suna prima data dupa o secunda si apoi repetat, la fiecare 50
ms, se instaleaza astfel:
timer_t tid;// seteaza parametrul timer-ului la 1 secunda, 0 nanosecundetimer.it_value.tv_sec = 1;timer.it_value.tv_nsec = 0;
// seteaza parametrii pentru repetarea automata a timer-ului la 50mstimer.it_interval.tv_sec = 0;timer.it_interval.tv_nsec = 50000000;
4/27/2014 Programarea Aplicatiilor in Timp Real
timer_settime(tid, 0, &timer, NULL);
75
-
Setarea timerelor:
timerul poate fi setat sa sune o singura data alegand it_interval = 0:
timer_t tid;...
timer.it_value.tv_sec = 1;timer.it_value.tv_nsec = 0;timer.it_interval.tv_sec = 0;timer.it_interval.tv_nsec = 0;...
timer_settime(tid, 0, &timer, NULL);
4/27/2014 Programarea Aplicatiilor in Timp Real 76
-
Utilizarea timerelor:
4/27/2014 Programarea Aplicatiilor in Timp Real 77
-
Anularea timerelor:
4/27/2014 Programarea Aplicatiilor in Timp Real 78
-
Exemplu notificare prin semnale: utilizarea alarmelor (exempluprezentat la curs)#include sem_t semaf;void handler(signo){
printf("\nExecuta rutina pentru semnalul (SIGALRM) cu codul %d .\n", signo);}void* fir(void* arg){
while(1){sem_wait(&semaf);sem_wait(&semaf);printf("\nSe executa firul reprogramat la 3 secunde ... \n");}
}int main() {
pthread_t fir_ciclic;struct sigaction act;sigset_t set;int valoare;sem_init(&semaf, 1, 0);pthread_create(&fir_ciclic, NULL, (void*)fir, NULL);sigemptyset(&set );sigaddset(&set, SIGALRM );sigaddset(&set, SIGINT);act.sa_flags = 0;act.sa_mask = set;
4/27/2014 Programarea Aplicatiilor in Timp Real
act.sa_mask = set;act.sa_handler = &handler;sigaction(SIGALRM, &act, NULL );while(1){alarm(3); // executie ciclica a unui set de operatiisem_post(&semaf);pause(); // asteapta expirarea alarmei}return EXIT_SUCCESS;
}
79
-
Exemplu: reprogramare prin instalarea unei alarme output [program)
Se executa firul reprogramat la 3 secunde ...
Executa rutina pentru semnalul (SIGALRM) cu codul 14 .
Se executa firul reprogramat la 3 secunde ...
Executa rutina pentru semnalul (SIGALRM) cu codul 14 .
Se executa firul reprogramat la 3 secunde ...
Executa rutina pentru semnalul (SIGALRM) cu codul 14 .
Se executa firul reprogramat la 3 secunde ...
4/27/2014 Programarea Aplicatiilor in Timp Real 80
-
Pulsuri:
spre deosebire de serviciile sincrone Send/Receive/Reply, nucleul Neutrino suporta si mesaje fara blocare de dimensiune fixa = pulsuri
pulsurile
sunt mesaje scurte formate din 8 biti de cod si 32 biti de date sunt folosite adesea drept mecanism de notificare n cadrul rutinelor de
tratare a intreruperilor de asemenea, permit serverelor sa notifice clientii, fara a-i bloca
se foloseste acelasi mecanism de transmitere de mesaje prin intermediul
4/27/2014 Programarea Aplicatiilor in Timp Real
se foloseste acelasi mecanism de transmitere de mesaje prin intermediulcanalelor de comunicatie sub QNX
81
-
Pulsuri:
4/27/2014 Programarea Aplicatiilor in Timp Real 82
-
Notificare prin intermediul pulsurilor:
setarea unui timer si receptionarea pulsurilor prin intermediul timerelor
4/27/2014 Programarea Aplicatiilor in Timp Real 83
-
Notificare prin intermediul pulsurilor (cont):
4/27/2014 Programarea Aplicatiilor in Timp Real 84
-
Notificare prin intermediul pulsurilor (cont):
4/27/2014 Programarea Aplicatiilor in Timp Real 85
-
Exemplu - executia ciclica a firelor de executie prin intermediultimerelor notificare prin pulsuri (exemplu prezentat la curs):#include #include #include #include
#define MY_PULSE_CODE _PULSE_CODE_MINAVAIL
typedef union { struct _pulse pulse;
} tip_mesaj;main(){
timer_t tid; // identicatorul timer-uluistruct itimerspec timer; // o specificatie de timerstruct sigevent event; // o specificatie de eveniment
int chid, rcvid;tip_mesaj msg;chid = ChannelCreate(0);
4/27/2014 Programarea Aplicatiilor in Timp Real
chid = ChannelCreate(0);
// pentru notificare se trimite un puls pe un canal de comunicatie
event.sigev_notify = SIGEV_PULSE;event.sigev_coid = ConnectAttach(0, 0, chid, _NTO_SIDE_CHANNEL, 0);event.sigev_priority = getprio(0);event.sigev_code = MY_PULSE_CODE;
...
86
-
Exemplu - executia ciclica a firelor de executie prin intermediultimerelor notificare prin pulsuri (cont):
timer_create(CLOCK_REALTIME, &event, &tid);
// timerul este setat la 1.5 secunde// timerul este setat la 1.5 secunde
timer.it_value.tv_sec = 1;timer.it_value.tv_nsec = 500000000; /* 0.5 secunde */
// intervalul de reprogramare este de 1.5 secunde
timer.it_interval.tv_sec = 1;timer.it_interval.tv_nsec = 500000000; /* 0.5 secunde */
timer_settime(tid, 0, &timer, NULL);
while(1) {rcvid = MsgReceive(chid, &msg, sizeof(msg), NULL);
4/27/2014 Programarea Aplicatiilor in Timp Real
rcvid = MsgReceive(chid, &msg, sizeof(msg), NULL);
if (rcvid == 0) /* s-a primit un puls */if (msg.pulse.code == MY_PULSE_CODE)
printf("S-a primit un puls de la timer ... \n");}
}
87
-
Exemplu - executia ciclica a firelor de executie prin intermediultimerelor notificare prin pulsuri (cont):
rezultatul executiei programului:
S-a primit un puls de la timer ...
S-a primit un puls de la timer ...
S-a primit un puls de la timer ...
S-a primit un puls de la timer ...
S-a primit un puls de la timer ...
4/27/2014 Programarea Aplicatiilor in Timp Real
S-a primit un puls de la timer ...
88
-
Atentie:
intarzierea unui proces pe un anumit interval de timp:
GRESIT: constructie software de tip busy-wait GRESIT: constructie software de tip busy-wait
un task asteapta trecerea unui interval de 10 secunde intr-o organizare de tip busy-wait
start := clock; // citeste ceasul
loop
exit when (clock start) > 10.0;
end loop;
4/27/2014 Programarea Aplicatiilor in Timp Real
corect:
se folosesc functiile specificate pentru asteptare, care elibereaza CPU cind taskul se blocheaza asteptand trecerea intervalului de asteptare (sleep, delay, etc)
89
-
Studiu individual:http://qnx.com/developers/docs/6.3.2/parse_software/
Getting Started with QNX Neutrino 2: A Guide for RealtimeProgrammers, by Rob Krten
This book describes the fundamental concepts of QNX Neutrino, including:
message passing
processes and threads
timers
4/27/2014 Programarea Aplicatiilor in Timp Real
timers
resource managers
interrupts
90
-
Studiu individual:
4/27/2014 Programarea Aplicatiilor in Timp Real 91
-
Studiu individual:
Capitolul 3 - Clocks, Timers and Getting a Kick Every So Often
37 pages detailing the implementation of QNX Neutrino's timing system, and how to use it. The kernel and POSIX calls are explained, along with interesting notes to use it. The kernel and POSIX calls are explained, along with interesting notes about timing jitter, accuracy, and the interaction of timers with message passing and scheduling. Also, contains a generalized discussion of the extended structsigevent structure which is fundamental to "notification" events. Kernel timeouts are also discussed
Capitolul 2 - Processes & Threads
4/27/2014 Programarea Aplicatiilor in Timp Real
91 pages of information about how threads and processes are viewed and managed under QNX Neutrino, includes information on scheduling, prioritization, thread functions (e.g., pthread_create()), thread synchronization (e.g., mutexes, barriers, sleepons), process creation (e.g., system(), exec(), spawn(), fork()), and the interaction of scheduling and hardware interrupts.
92
-
Sumar curs PATR:
Notiuni introductive: sistem in timp real si sisteme embedded in timp-real, sisteme de operare in timp real, limbaje de programare pentru aplicatii in timp-real, programareconcurenta, definitii (proces, fir de executie, task, preemptiune);
Aspecte concurentiale ale aplicatiilor in timp-real - mecanisme pentru sincronizarea si Aspecte concurentiale ale aplicatiilor in timp-real - mecanisme pentru sincronizarea sicomunicarea intre taskuri (sincronizare, excludere mutuala, mesaje, etc);
Aspecte temporale ale aplicatiilor in timp-real caracteristici de limbaj pentru specificarea, implementarea si analiza deadline-urilor;
Mecanisme de planificare pentru aplicatii in timp-real algoritmi de planificare, evitareainversiunii de prioritate.
Tehnici de specificare si proiectare a aplicatiilor software in timp-real. Metode de proiectare. Standarde pentru dezvoltarea aplicatiilor in timp-real;
4/27/2014 Programarea Aplicatiilor in Timp Real 93
proiectare. Standarde pentru dezvoltarea aplicatiilor in timp-real;
Organizarea aplicatiilor in timp-real. Proiectare de sistem UML si OMG SysML. Metodologii de proiectare si implementare a aplicatiilor in timp-real MDD (Model driven Development).
-
Continutul cursului:
sisteme de operare in timp real
algoritmi (politici) de planificare a proceselor pentru sisteme in timp real
Programarea Aplicatiilor in Timp Real4/27/2014 94
-
Sisteme de operare in timp-real - Nuclee proprietary:
comerciale
QNX, pSOS, VxWorks, Nucleus, ERCOS, EMERALDS, Windows CE,...
caracteristici:
dimensiune redusa (~ zeci K) rapide comutare de context rapida si raspuns rapid la intreruperi multitasking si IPC prin intermediul cutiilor postale, evenimentelor, semnalelor,
semafoarelor, etc management special al memoriei
cum suporta constrangerile de timp
4/27/2014 Programarea Aplicatiilor in Timp Real 95
ceas de timp-real (e.g. QNX - CLOCK_REALTIME) planificare pe baza de prioritati (in continuare ...) alarme speciale si timeouts (e.g. QNX - cu timere)
standardizare prin extensii POSIX Real-Time
-
Extensii RT ale UNIX:
e.g. RT-UNIX,RT-LINUX, RT-MACH, RT-POSIX
caracteristici:
mai lente, mai putin predictibile in functionare au medii de dezvoltare mai bune
adopta din RT-POSIX
timere, planificare pe baza de prioritati, semafoare, IPC, notificare prin evenimenteasincrone, procese
4/27/2014 Programarea Aplicatiilor in Timp Real 96
mem locking, threads, operatii sincrone si asincrone de I/O
probleme: coarse timers, raspuns lent la intreruperi (engl. latency), cozi FIFO, no locking pages in memory, no predictable IPC
-
OBSERVATIE:
Evenimente (events) = aparitii externe care vin din lumea reala ("things that happen")
evenimentele pot fi:
sincrone: sunt tratate in ordinea in care apar (cronologic) - de exemplu, mesajele asincrone: de obicei sunt evenimente critice care trebuie procesate imediat, si este
necesar sa intrerupa activitatea care se executa in mod curent (se trateaza cu ajutorulsemnalelor)
evenimentele reprezinta tranzitii care provoaca (engl. trigger) o modificare in starea
4/27/2014 Programarea Aplicatiilor in Timp Real 97
evenimentele reprezinta tranzitii care provoaca (engl. trigger) o modificare in stareasistemului
-
Diagrama generala a tranzitiilor de stare ale unui proces / thread:
NEW(creat)
READY (gatade executie)
TERMINAT
fork, exec
spawn
dispatch
RUNNING (inde executie)
BLOCKED(blocat,
suspendatpe conditie)
intrerupere (I/O)
sau asteptare pe
eveniment / timp
tratare intrerupere (I/O)
sau aparitie eveniment/
indeplinire conditie timp
Coada procese READY
4/27/2014 Programarea Aplicatiilor in Timp Real 98
PROCESOR
Coada procese READY
Coada procese BLOCKED
-
Tranzitii de stare ale proceselor / firelor de executie (1):
instalat (creat NEW) exista din punct de vedere al nucleului (are create structurile de date: bloc de control
task, descriptor de task, etc.task, descriptor de task, etc. gata de executie (READY)
are ndeplinite toate conditiile si poate prelua unitatea centrala;
planificatorul de task-uri ia n considerare doar task-urile aflate n aceasta stare;
un task intra in starea gata de executie daca se afla in executie (la expirarea time slice-ului) sau daca a fost scos din executie de catre alt task mai prioritar (preempted). daca era in starea BLOCKED / SUSPENDED, taskul poate intra in starea READY
daca apare evenimentul care a determinat trecerea taskului in starea
4/27/2014 Programarea Aplicatiilor in Timp Real 99
daca apare evenimentul care a determinat trecerea taskului in stareaSUSPENDED;
-
Tranzitii de stare ale proceselor / firelor de executie (2):
in executie (RUNNING) task-ul care este executat efectiv de catre procesor;
un task poate intra in executie atunci cind este creat (daca nici un alt task nu estegata de executie), sau prin tranzitie din starea gata de executie (daca este eligibilpentru a fi executat pe baza prioritatii sale sau in functie de pozitia sa in coadaround-robin);
blocat (BLOCKED / SUSPENDED) blocat pe o operatie de I/O;
blocat pe o conditie de timp (sleep t);blocat nedefinit (sleep(0), suspend, etc.);
4/27/2014 Programarea Aplicatiilor in Timp Real 100
blocat nedefinit (sleep(0), suspend, etc.); taskurile care asteapta pe o anumita resursa, deci nu sunt gata de executie, se afla
in starea suspendat sau blocat (pe conditie de timp sau pe eveniment).
-
Tranzitii de stare ale proceselor / firelor de executie (3):
pentru starile READY si BLOCKED, nucleul organizeaza cozi de asteptare (coada de procese READY si coada de procese BLOCKED).(coada de procese READY si coada de procese BLOCKED).
un task blocat este scos din oricare dintre aceste doua stari atunci cnd este ndeplinita conditia pentru care asteapta si este trecut n coada READY
4/27/2014 Programarea Aplicatiilor in Timp Real 101
-
Nuclee de RT pentru cercetare:
suport pentru algoritmi de planificare in RT (in continuare ...) suport pentru timing analysis RT sync primitives, e.g., priority ceiling (in continuare ...) RT sync primitives, e.g., priority ceiling (in continuare ...)
algoritmi de evitare a inversunii de prioritate predictability over avg perf support for fault-tolerance and I/O
exemple: Spring, Mars, HARTOS, MARUTI, ARTS, CHAOS, EMERALDSOBSERVATIE: Timing:
operatii necesare (e.g.): wait pentru anumite intervale (mici) de timp
4/27/2014 Programarea Aplicatiilor in Timp Real 102
wait pentru anumite intervale (mici) de timp sleep, delay, nanosleep, etc
notify (schedule) procesul la intervale specificate de timp timere, etc
-
Sisteme de operare:
sistem de operare general de tip monolit
sistem de operare minimal cu un nucleu minimal (kernel)
Bibliografie studiu individual:Documentatie QNX Momentics QNX Neutrino System Architecture: arhitectura microkernel,
4/27/2014 Programarea Aplicatiilor in Timp Real 103
QNX Neutrino System Architecture: arhitectura microkernel, planificare (scheduling), etc ...
QNX Neutrino Programmer's Guide, etc ...Real Time and Embedded Guide(Herman Bruyninckx, K.U.Leuven, Belgium)http://people.mech.kuleuven.be/~brunyninc/rthowto/
-
Planificarea taskurilor (procese/fire de executie) in sisteme in timp-real:
planificarea (engl. scheduling) reprezinta un concept asociat sistemelor de operare, princare se asigura mecanismele necesare pentru a face posibila concurenta
un context de planificare un context de planificare
include un motor de executie denumit planificator (engl. scheduler) care executa o anumita politica (strategie) de planificare (engl. scheduling algorithm)
dispune de un numar de resurse care sunt planificate in functie de politica de planificare resursele includ (au) actiuni care se executa cu o anumita prioritate in raport cu
alte actiuni
sistemul de operare furnizeaza motorul de executie (planificatorul) si politicile de planificare
4/27/2014 Programarea Aplicatiilor in Timp Real 104
sistemul de operare furnizeaza motorul de executie (planificatorul) si politicile de planificare
utilizatorul furnizeaza resursele planificabile (taskuri sau resurse care trebuie sa fie (saunu) protejate de accesul simultan prin mecanisme de tipul semafoarelor (de exemplu)
-
Planificarea taskurilor in sisteme in timp-real (1):
in general, intr-un sistem in timp real, unele taskuri sunt de timp real, adica au un anumit grad de urgenta in executarea actiunilor specifice le asociem deadline-uri
de exemplu, taskurile pot fi clasificate ca fiind taskuri hard sau taskuri soft de exemplu, taskurile pot fi clasificate ca fiind taskuri hard sau taskuri soft
un task TR de tip hard trebuie sa-si respecte deadline-ul in orice conditii. In caz contrar, in sistem poate apare o eroare fatala
un task TR de tip soft are asociat un deadline care este de dorit a fi indeplinit, dar acestlucru nu este obligatoriu pentru corectitudinea functionarii sistemului global. Taskul isi poatecontinua executia chiar daca nu indeplineste deadline-ul
4/27/2014 Programarea Aplicatiilor in Timp Real 105
-
Planificarea taskurilor in sisteme in timp-real (2):
Alte doua concepte asociate planificarii in sistemele in timp-real sunt: importanta. Se refera la valoarea pe care o are pentru performanta corecta a sistemului
finalizarea unei actiuni specifice (de exemplu, ajustarea corecta a altitudinii de zbor a unui avion in timpul specificat are o
importanta mai mare decat transmiterea unui film in cabina pasagerilor); urgenta. Urgenta unei actiuni se refera la cat de aproape este deadline-ul asociat unei anumite
actiuni, fara a lua in considerare importanta sa.
cele mai multe planificatoare furnizeaza o singura posibilitate de planificare a actiunilor, sianume prin intermediul prioritatii (cu ea se controleaza atat importanta, cat si urgenta)
4/27/2014 Programarea Aplicatiilor in Timp Real 106
-
Planificarea taskurilor in sisteme in timp-real (3):
OBSERVATIE:
multe dintre sistemele in timp real actuale nu pot face fata direct deadline-urilor. De aceea, ele sunt proiectate sa raspunda cat mai bine cerintelor taskurilor de timp real, astfel incat, atunci cand se apropie un deadline, sa poata fi planificat rapid un task atunci cand se apropie un deadline, sa poata fi planificat rapid un task
relativ la momentele semnificative la care se pune problema alegerii unui task pentru a filansat in executie, apar deosebiri in functie de implementarea nucleului
momentele semnificative sunt momentele la care se apeleaza planificatorul de task-uri. In general, aceste momente sunt de tipul:
terminarea unei operatii de I/O expirarea unei perioade fixe de timp (ceas de timp real) - se fixeaza o baza de timp,
4/27/2014 Programarea Aplicatiilor in Timp Real 107
expirarea unei perioade fixe de timp (ceas de timp real) - se fixeaza o baza de timp, iar la fiecare astfel de interval de timp se apeleaza planificatorul de task-uri
executia (apelul) unor functii de sistem specifice
-
Planificarea taskurilor in sisteme in timp-real (4):
principalele notiuni asociate in cazul planificarii taskurilor sunt:
mecanismul de tip round-robin
preemptiunea / nonpreemptiunea taskurilor
in functie de combinatiile acestor notiuni in cadrul unei metode de planificare putem clasifica algoritmii de planificare ai taskurilor
4/27/2014 Programarea Aplicatiilor in Timp Real 108
-
Planificarea taskurilor in sisteme in timp-real (5):
planificarea de tip round-robin se refera la o metoda de planificare a taskurilor care presupune organizarea unor taskuri intr-o coada circulara, taskul care se executa in mod curent fiind primul task din coada. Dupa ce isi termina executia (sau si-o intrerupe in mod temporar) el va fi pus la sfirsitul cozii, deci in mod (sau si-o intrerupe in mod temporar) el va fi pus la sfirsitul cozii, deci in mod relativ va deveni cel mai putin prioritar.
taskurile se executa secvential, pina la final, intr-o ordine de tip FIFO de multe ori aceasta maniera de planificare se utilizeaza in conjunctie cu un
executiv de tip ciclic.
4/27/2014 Programarea Aplicatiilor in Timp Real 109
Mecanismul de planificare de tip round robin
-
Planificarea taskurilor in sisteme in timp-real (6):
preemptiunea taskurilor este o procedura prin care este posibila intrerupereaexecutiei unui task mai putin prioritar de catre un task cu prioritate mai mare executiei unui task mai putin prioritar de catre un task cu prioritate mai mare
prioritatile atasate fiecarei intreruperi se bazeaza pe urgenta taskului asociatintreruperii respective
4/27/2014 Programarea Aplicatiilor in Timp Real 110
-
Metode de planificare a taskurilor:
planificator preemptiv cu planificare simpla de tip round-robin
planificator non-preemptiv cu prioritati
combinarea prioritatilor cu intreruperile de ceas
situatii intermediare de alocare a task-urilor (mixte)
4/27/2014 Programarea Aplicatiilor in Timp Real 111
-
Planificator preemptiv cu planificare simpla de tip round-robin:
planificarea de tip round-robin este o planificare de tip FIFO (primul task sosit este servit primul) la planificatoarele de tip round-robin cu time-slicing, fiecarui task executabil ii este atasat un cuanta fixa de
timp, denumita time slice, in care taskul se poate executa. Taskul se executa pina cind isi termina completexecutia sau ii expira timpul de executie, timp specificat de intreruperea de ceas
daca taskul nu reuseste sa-si termine executia intr-un time slice, contextul sau trebuie salvat, dupa care va daca taskul nu reuseste sa-si termine executia intr-un time slice, contextul sau trebuie salvat, dupa care vafi plasat la coada listei de taskuri executabile. Va fi refacut apoi contextul urmatorului task din lista siexecutia sa va fi reluata
taskul care si-a intrerupt temporar executia devine in mod relativ cel mai putin prioritar
taskul TR va fi adaugat la coada de procese gata de executie (engl. READY) si va astepta urmatoarea feliede timp (engl. time slice)
in general, nu este o solutie acceptabila pentru aplicatii in timp-real Se activeaza procesul de
4/27/2014 Programarea Aplicatiilor in Timp Real 112
Proces nProces 1 Proces 2 Proces de Timp-Real
Puncte de preemptiune(tact ceas)
procesul de timp-real
Interval de planificare al taskuluide timp-real
-
Planificator non-preemptiv cu prioritati:
in cazul unui planificator non-preemptiv, taskul care se executa in mod curent nu poate fi intrerupt pina cind nu isi intrerupe el singur executia
se poate utiliza totusi un mecanism de planificare bazat pe prioritati, dndu-i-se task-ului de timp real prioritatea cea mai mare, astfel incat un task TR aflat in stare gata de executie (engl. READY) poate fi planificat imediat ce procesul curent se blocheaza sau isi termina normal executia
taskul TR este adaugat la inceputul cozii de procese gata de executie.
acest mod de planificare poate conduce la delay-uri de ordinul a cateva secunde daca procesul care se executa in mod curent este lent si de prioritate scazuta
nici aceasta solutie nu este acceptabila din punct de vedere al considerentelor de procesare in timp real.
Se activeaza procesul de timp-real
4/27/2014 Programarea Aplicatiilor in Timp Real 113
Proces 1 (se executa)
Proces de Timp-Real
Interval de planificare al taskuluide timp-real
Aici se blocheaza procesul care se executa la momentul curent sau isi termina executia
-
Combinarea prioritatilor cu intreruperile de ceas (planificatorpreemptiv cu prioritati si puncte de preemptiune):
punctele de preemptiune apar la intervale de timp egale. Cand apare un punct de preemptiune, taskul care se executa in mod curent va fi scos din executie (engl. preempted) daca in coada asteapta un task cu prioritate mai mare
in acest caz delay-ul poate fi de ordinul a cateva ms in acest caz delay-ul poate fi de ordinul a cateva ms
totusi, nu este o solutie optima pentru aplicatiile de timp real critice.
Proces 1 (se executa)
Proces de Timp-Real
Se activeaza procesul de timp-real
4/27/2014 Programarea Aplicatiilor in Timp Real 114
Interval de planificare al taskuluide timp-real
Aici taskul de timp-real scoate din executie procesul care se executa la momentul curent si se executa imediat
Puncte de preemptiune(tact ceas)
-
Combinarea prioritatilor cu intreruperile de ceas (planificatorpreemptiv cu prioritati si puncte de preemptiune) - exemplu:
PrioritateOrdinea de sosire a taskurilor: 1, 2, 3Ordinea de executie a taskurilor: 1, 2, 3, 2, 1
Mica
Medie
Mare
Task 1
Task 2
Task 3
Task 2
Task 1
4/27/2014 Programarea Aplicatiilor in Timp Real 115
MicaTimp
Task 1 Task 1
Taskul 1 este intreruptde sosirea taskului 2 Taskul 2 este intrerupt
de sosirea taskului 3
-
Politici de planificare de tip fair:
Politicile de planificare tip fair:
planifica in asa fel incat toate taskurile progreseaza mai mult sau planifica in asa fel incat toate taskurile progreseaza mai mult sau mai putin uniform (in acelasi fel evenly).
EXEMPLE:
executivul de tip ciclic
executiv ciclic de tip time-triggered
4/27/2014 Programarea Aplicatiilor in Timp Real 116
round-robin
round-robin preemptiv cu diviziunea timpului
-
Politici de planificare de tip fair executiv de tip ciclic:
se foloseste atunci cand exista un numar fix de procese periodice si putem dezvolta o schema completa de planificare, a carei executie repetata va forta procesele sa se execute la momentul dorit
un executiv de tip ciclic este de fapt o tabela de apeluri de proceduri, fiecare procedura un executiv de tip ciclic este de fapt o tabela de apeluri de proceduri, fiecare procedura reprezentand o parte a codului corespunzator unui proces (task)
executivul ruleaza setul de proceduri (taskuri), complet fiecare dintre ele, intr-un ciclu infinit lista de taskuri este stabilita la inceput, inainte de rularea aplicatiei.
avantajul: foarte simplu, are o predictibilitate mare
4/27/2014 Programarea Aplicatiilor in Timp Real 117
dezavantaj: bun pentru taskuri scurte (fiecare task trebuie sa se execute intr-un interval de timp scurt, pentru ca politica sa fie de tip fair).
daca un task e mai lung, programatorul trebuie sa-l sparga in taskuri mai mici (scurte).
-
Politici de planificare de tip fair executiv de tip ciclic (cont):
tabela de taskuri, care se repeta periodic, este denumita frame major. Fiecare frame major (principal) este format dintr-un anumit numar de felii mai mici de timp, denumite frame-uri minore, care au durate fixe, in care sunt planificate taskurile pentru executie, cu ajutorul unui timer
operatiile sunt implementate sub forma unor proceduri, organizate intr-o lista predefinita pentru operatiile sunt implementate sub forma unor proceduri, organizate intr-o lista predefinita pentru fiecare frame major. La inceputul fiecarui ciclu (frame) minor, taskul timer va apela fiecare procedura din lista
de exemplu, pentru 5 procese / taskuri):
while(1){asteapta_intrerupere();procedura_pentru_a();procedura_pentru_b();procedura_pentru_c();
4/27/2014 Programarea Aplicatiilor in Timp Real 118
asteapta_intrerupere();procedura_pentru_a();procedura_pentru_b();procedura_pentru_d();procedura_pentru_e();// etc ...}
-
Politici de planificare de tip fair executiv de tip ciclic (cont): spre exemplificare se considera 4 proceduri care se repeta intr-un frame major presupunem ca durata unui frame minor este 10 ms.
se considera ca cele 4 proceduri trebuie sa se execute cu o frecventa de 50 Hz, 25 Hz, 12.5 Hz si 6.25 Hz, respectiv cu perioada de 20 ms, 40 ms, 80 ms si 160 ms
Frame major Frame major
Procedura 1 (executie la fiecare 2 frame-uri minore)
Procedura 3 (executie la fiecare 8 frame-uri minore)
4/27/2014 Programarea Aplicatiilor in Timp Real 119
fiecare 2 frame-uri minore)
Procedura 2 (executie la fiecare 4 frame-uri minore)
fiecare 8 frame-uri minore)
Procedura 4 (executie la fiecare 16 frame-uri minore)
-
Politici de planificare de tip fair - executiv ciclic de tip time-triggered:
este la fel ca si executivul de tip ciclic, cu diferenta ca inceputul unui ciclu este dat ca raspuns la un event time, astfel incat sistemul face o pauza intre cicli
avantaj: foarte simplu, predictibilitate mare, resincronizeaza ciclul cu ceasul referinta
dezavantaj: util pentru taskuri scurte
4/27/2014 Programarea Aplicatiilor in Timp Real 120
-
Politici de planificare de tip fair planificare de tip round-robin:
dupa ce a fost pornit, un task va rula pana cand va elibera el insusi procesorul. Takurile pot fi distruse (killed) in timp de ruleazafi distruse (killed) in timp de ruleaza
Avantaj: mai flexibil decat executivul de tip ciclic, simplu.
Dezavantaj: pentru taskuri scurte.
4/27/2014 Programarea Aplicatiilor in Timp Real 121
-
Politici de planificare de tip fair - round-robin cu diviziuneatimpului (preemptiv):
este o planificare de tip round-robin pentru care, daca un task nu elibereaza procesorul de buna voie, va fi intrerupt de planificator dupa un interval de timp specificat denumit time buna voie, va fi intrerupt de planificator dupa un interval de timp specificat denumit time slice
Avantaj: mai flexibil decat executivul de tip ciclic si round-robin simplu, este simplu, robust.
4/27/2014 Programarea Aplicatiilor in Timp Real 122
-
Politici de planificare bazate pe prioritati (unfair):
Politici de planificarede tip priority-driven (unfair policies). anumite taskuri (cele cu prioritate mai mare) sunt planificate preferential fata
de celelalte. cand mai multe taskuri sunt gata de executie, selectia se va face in functie de cand mai multe taskuri sunt gata de executie, selectia se va face in functie de
prioritati in cazul unui planificator preeemptiv cu prioritati, taskul care se executa va fi
scos din executie de un task cu prioritate mai mare care este gata de executie planificatoarele bazate pe prioritati sunt responsive atita timp cat prioritatea
taskului activat de evenimentul exterior (incoming event) este mai mare decat cea a taskului care se executa in momentul aparitiei evenimentului. Din aceasta cauza, in astfel de sisteme intreruperile au cea mai mare prioritate.
EXEMPLE: Rate Monotonic Scheduling (RMS)
4/27/2014 Programarea Aplicatiilor in Timp Real 123
Rate Monotonic Scheduling (RMS) Deadline Monotonic Scheduling (DMS) Earliest Deadline First (EDF) Least Laxity (LL) Maximum Urgency First (MUF)
-
Rate Monotonic Scheduling (RMS):
toate taskurile se presupun a fi periodice, cu deadline-ul la sfarsitul perioadei
prioritatile se ataseaza in momentul proiectarii, astfel incat taskurile cu perioadele cele mai scurte au prioritatea cea mai mare.
dezavantaj: poate sa nu corespunda sistemelor mai complexe. dezavantaj: poate sa nu corespunda sistemelor mai complexe.
C C
T T
D = T D = T
Timp
4/27/2014 Programarea Aplicatiilor in Timp Real 124
RUNNING
D = deadline
C = timpul de executie al taskuluiT= perioada de executie a taskului
-
Rate Monotonic Scheduling (RMS) - cont.:OBSERVATIE:
daca un task periodic este executat intotdeauna pina la finalizare (adica nu exista situatii in care o instanta a taskului nu se poate executa din lipsa de resurse), atunci utilizarea procesorului de catre acest task este specificata de o relatie de tipul
CUM SETAM PRIORITATEA TASKURILOR:
toate schemele de planificare pe baza de prioritati se bazeaza pe urgenta
este posibil sa se pondereze pe baza importantei prin multiplicarea cu un factor de importanta, wj, setandu-se apoi prioritatea taskului ca fiind egala cu produsul dintre unweighted priority si factorul de importanta
e.g. prioritatea taskului la planificarea RMS va fi setata la:
U = CT
4/27/2014 Programarea Aplicatiilor in Timp Real 125
unde pj este prioritatea taskului, wj este o masura a importantei finalizarii taskului (completion), iar Tjeste perioada de executie a taskului
p j=w jT j
-
Rate Monotonic Scheduling (RMS) - cont.:
in cazul planificarii de tip RMS, taskul cu prioritatea cea mai mare este taskul cu cea mai mica perioada T, al doilea in ordinea prioritatii este cel cu a doua cea mai mica perioada, etc ...
daca mai multe taskuri sunt gata de executie, va fi servit primul cel cu cea mai mica perioada, adica:
P1 > P2 = T1 < T2
(prioritate) (perioada)
daca afisam grafic prioritatea unui task functie de frecventa sa de executie (rate)
4/27/2014 Programarea Aplicatiilor in Timp Real 126
daca afisam grafic prioritatea unui task functie de frecventa sa de executie (rate) rezulta o functie monoton crescatoare (de aici numele rate monotonic scheduling)
-
Rate Monotonic Scheduling (RMS) - cont.:
Prioritate
Mare
Cea mare frecventa, cel mai prioritar task
4/27/2014 Programarea Aplicatiilor in Timp Real 127
MicaCea mai mica frecventa, cel mai putin prioritar task
Frecventa (HZ)
-
Observatie:
ca masura a eficientei (effectiveness) a unui algoritm cu planificare periodica trebuie specificat daca acesta garanteaza sau nu indeplinirea deadline-urilor hard.
presupunem ca avem n taskuri, fiecare avand o perioada de executie fixa si un presupunem ca avem n taskuri, fiecare avand o perioada de executie fixa si un anumit timp de executie, pentru a fi posibil ca toate deadline-urile sa fie indeplinite, trebuie sa fie indeplinita urmatoarea inegalitate:
adica suma indicilor de utilizare a procesorului pentru toate taskurile nu poate depasi valoarea 1 (utilizare totala a procesorului).
C1 T 1
C2 T 2 ...
C nT n 1
4/27/2014 Programarea Aplicatiilor in Timp Real 128
depasi valoarea 1 (utilizare totala a procesorului). aceasta ecuatie estimeaza o limita superioara a numarului de taskuri pe care
algoritmul le poate planifica cu succes.
-
Deadline Monotonic Scheduling (DMS):
la fel ca si planificatorul RMS, cu exceptia faptului ca nu se presupune ca deadline-ul este la sfirsitul perioadei
prioritatile sunt asociate in momentul proiectarii aplicatiei, pe baza lungimii (shortness) deadline-ului taskului(shortness) deadline-ului taskului
C C
T T
D < T D < T
Timp
4/27/2014 Programarea Aplicatiilor in Timp Real 129
RUNNING
D = deadline
C = timpul de executie al taskuluiT= perioada de executie a taskului
-
Earliest Deadline First (EDF):
prioritatile sunt asociate la run-time atunci cand taskurile sunt gata de executie, pe baza aproprierii (nearness) deadline-ului taskului (cu cat deadline-ul este mai pe baza aproprierii (nearness) deadline-ului taskului (cu cat deadline-ul este mai aproape, cu atat prioritatea este mai mare).
dezavantaj: lipsa suport din partea sistemului de operare in timp-real.
4/27/2014 Programarea Aplicatiilor in Timp Real 130
-
Inversiunea de prioritate:
sistemele de timp-real executa taskuri multiple
trebuie sa coordoneze aceste taskuri si sa partajeze resurse, de aceea maniera in care aceste resurse sunt gestionate este foarte importanta, atat pentru
functionarea corecta a aplicatiei, cat si pentru planificare problema principala o reprezinta protejarea resurselor fata de accesul concurent
solutia uzuala - serializarea accesului la resurse si prevenirea accesului simultan
de exemplu, accesul la resurse prin intermediul sectiunilor critice Aceasta solutie este utila atunci cand timpul de acces la resursa este foarte scurt relativ la deadline-uri si timpii necesari pentru finalizarea actiunii (action completion)
in acest caz resursa este protejata cu un semafor (sau orice alt mecanism pentru excludere mutuala, de exemplu, mutex-uri)
4/27/2014 Programarea Aplicatiilor in Timp Real 131
poate apare o situatie speciala, denumita unbounded priority inversion, adica
deoarece detinea resursa, un task cu prioritate mai mica se executa, in timp ce un task cu prioritate mai mare, care a facut o cerere de alocare resursa mai tarziu, va fi blocat, asteptand eliberarea resursei de catre taskul cu prioritate mai mica
-
Exemplu - scenariu aparitie inversiune de prioritate:
consideram 4 taskuri care au urmatoarele prioritati:
PHPT > PTask1 > PTask2 > PLPT
Folosim urmatoarele notatii:
a taskul este activ
4/27/2014 Programarea Aplicatiilor in Timp Real 132
i taskul este inactiv
b taskul este blocat
-
Resursa disponibila
Resursa ocupataResursa partajata
Prioritate
Activ
BlocatInactiv
Activ
Blocat
Inactiv
Activ
Task 2
Task 1
Task HPT
B
C
D E
G
F
4/27/2014 Programarea Aplicatiilor in Timp Real 133
Blocat
Inactiv
Activ
BlocatInactiv
Blocat
Inactiv
ActivTask LPT
Task 2
Timp
A H
-
Exemplu - scenariu aparitie inversiune de prioritate:
A- Taskul LPT este READY, intra in RUN, si in timpul executiei sale acapareaza resursapartajata SR (shared resource).
B - Taskul HPT este READY, dar are nevoie de resursa, si se blocheaza pentru a-i permitetaskului 1 sa se termine (sau sa elibereze resursa).
C - Taskul 2, care are prioritate mai mare decat LPT, este READY. Deoarece nu are nevoiede resursa, preempts taskul LPT. In acest moment, HPT e blocat de doua taskuri, taskul 2 siLPT).
D - Taskul 1, care are prioritatea mai mare decat Task 2, este READY. Deoarece nu utilizeaza resursa, preempts Task 2. Taskul HPT e blocat acum de 3 taskuri.
E - Taskul 1 se termina, si se reia taskul 2.
F - Deadline-ul taskului HPT este pierdut, chiar daca a fost suficient de lung pentru a permite
4/27/2014 Programarea Aplicatiilor in Timp Real 134
F - Deadline-ul taskului HPT este pierdut, chiar daca a fost suficient de lung pentru a permiteatat executia taskului HPT, cat si a taskului LPT (dar nu a fost suficient de lung pentru a permite ca toate taskurile sa se execute). Aici apare inversiunea de prioritate.
G - Taskul 2 se termina, deci se va relua taskul LPT.
H - Taskul LPT se termina si elibereaza resursa. Taskul HPT va avea acum acces la resursa.
-
Exemplu:
se considera 3 taskuri si o resursa, X.
Prioritate
Task A
Task B
Task C
Low
High
Aici apare inversiunea de prioritate
Taskul C isi continua executia
se considera 3 taskuri si o resursa, X.
Task Prioritate
A mica - 10
B medie - 15
C mare - 20
taskul A foloseste resursa X, blocand-o (lock).
Low
lock(X) unlock(X)
4/27/2014 Programarea Aplicatiilor in Timp Real 135
taskul A foloseste resursa X, blocand-o (lock). taskul B scoate A din executie in mod preemptiv si incepe sa se execute un timp mai lung. taskul C scoate taskul B din executie in mod preemptiv si incearca sa acapareze resursa X (sa faca lock),
dar nu poate, deoarece taskul A a preluat deja lock-ul resursei X. astfel, taskul C, cu prioritatea cea mai mare, nu poate progresa atata timp cat taskul A nu elibereaza
resursa X, iar taskul A nu poate face acest lucru pana cand taskul B nu-si termina executia. Acest scenariu ii da efectiv taskului C aceeasi prioritate ca si taskului A
-
Inversiune de prioritate - OBSERVATII: inversiunea de prioritate apare in cazul planificatoarelor cu prioritati fixe (din ce in ce mai rare),
care planifica taskurile in functie de prioritatile specificate de programator, si care nu pot fimodificate
inversiunea de prioritate este o situatie in care un task cu prioritate mai mare este planificat ca inversiunea de prioritate este o situatie in care un task cu prioritate mai mare este planificat ca si cand ar avea o prioritate mai mica decat un task cu prioritate mai mica decat a lui.
alternativa o constituie un planificator cu prioritati care pot fi modificate dinamic (dynamic-priority scheduler), in timpul executiei aplicatiei
inversiunea de prioritate poate fi controlata de un programator experimentat, insa doar daca poate fi anticipata, fiind greu de detectat
4/27/2014 Programarea Aplicatiilor in Timp Real 136
inversiunea de prioritate apare doar atunci cand o secventa particulara de evenimente face ca un task de prioritate redusa sa detina o resursa atunci cand un task de prioritate mai mare are nevoie de aceasta
acest tip de situatie poate necesita pentru aparitie o combinatie improbabila de evenimente, nedetectate in perioada de testare a software-ului si care se poate manifesta intermitent in sistemul aflat in functiune
-
Tehnici de rezolvare a inversiunii de prioritate:
poarta denumirea de priority inversion avoidance protocols
sunt protocoale standard in doua variante
(a) priority inheritance protocol(b) priority ceiling emulation protocol
4/27/2014 Programarea Aplicatiilor in Timp Real 137
-
Protocolul cu mostenire de prioritate (priority inheritance protocol- PIP):
daca un task care asteapta pe o anumita resursa are o prioritate mai mare decat cea a taskului care detine resursa, acest protocol va da taskului cu prioritatea mai mica prioritatea taskului cu prioritate mare care asteapta eliberarea resursei, pana cand taskul mai putin prioritar va elibera resursa.
in exemplu, protocolul cu mostenire a prioritatii va da taskului A prioritatea taskului C, astfel in exemplu, protocolul cu mostenire a prioritatii va da taskului A prioritatea taskului C, astfelincat taskul A va executa blocul de cod intre operatia de lock si cea de unlock, fara a maitrebui sa astepte taskul B sa se termine
Prioritate
Task B
Task C
HighTaskul C isi continua executiaPIP
4/27/2014 Programarea Aplicatiilor in Timp Real 138
Task A
Low
lock(X) unlock(X)
-
Protocolul cu mostenire de prioritate (priority inheritance protocol- PIP):
probleme:
implementarea este destul de complexa. Folosind PIP, un task altereaza temporar prioritatea unui alt task, atunci cand incearca sa acapareze o resursa
acest lucru se poate intampla de mai multe ori, cand taskurile cu prioritate mare intra in coada de wait
sistemul trebuie sa refaca prioritatile originale ale taskurilor cand acestea elibereza o resursa (fac unlock())
4/27/2014 Programarea Aplicatiilor in Timp Real 139
-
Priority Ceiling Emulation Protocol (PCEP): mareste temporar prioritatea unui task care detine o resursa peste prioritatea celui mai
prioritar task care ar putea incerca sa acapareze resursa.
un task isi seteaza propria prioritate atunci cand recupereaza o resursa (un lock) si se reintoarce la prioritatea originala atunci cand elibereaza resursa
sectiunea de cod in care este preluat lockul se executa indivizibil in raport cu alte taskuri care ar vrea sa acapareze resursa
Priority returned
Prioritate
Task B
Task C
HighTaskul C isi continua executia
lock(X) unlock(X)
Priority raised to ceiling
4/27/2014 Programarea Aplicatiilor in Timp Real 140
Priority returned to normal
Task A
Low
lock(X) unlock(X)
ceiling
-
Alte probleme asociate concurentei deadlock si starvation:
resursele pe care procesele le pot utiliza in mod concurent, situatii in care acestea pot ajunge la blocaje de tip deadlock sau starvation, pot fi reutilizabile sau consumabile:ajunge la blocaje de tip deadlock sau starvation, pot fi reutilizabile sau consumabile:
resurse reutilizabile. O resursa reutilizabila este acea resursa care poate fi utilizata la un moment dat de catre un proces si nu este distrusa de acesta (de exemplu, procesorul, canalele de I/O, memorie, structuri de date - fisiere, baze de date, semafoare)
resurse consumabile. O resursa consumabila este o resursa care poate fi creata(produsa) si distrusa (consumata). Atunci cand o astfel de resursa a fost acaparata de un proces, ea inceteaza sa mai existe (de exemplu, intreruperi, semnale, mesaje, datele din bufferele de I/O)
4/27/2014 Programarea Aplicatiilor in Timp Real 141
-
Deadlock:
deadlock-ul poate fi definit ca fiind o blocare permanenta a unei multimi de procese care fie sunt in competitie pentru resurse, fie comunica intre ele
spre deosebire de alte probleme referitoare la managementul proceselor concurente, nu spre deosebire de alte probleme referitoare la managementul proceselor concurente, nu exista o solutie eficienta generala de rezolvare a unei situatii de deadlock
exemplu aparitie deadlock daca primitiva receive() este cu blocare (de obicei aceastaeste o eroare de programare, greu de detectat):
Task 1 Task 2
4/27/2014 Programarea Aplicatiilor in Timp Real 142
receive(Task2); receive(Task1);.
send(Task2, mesaj1); send(task1, mesaj2);
-
Deadlock:
In general, cauzele aparitiei deadlock-ului pot fi multiple:
o excludere mutuala realizata incorect- doar un singur proces poate utiliza o anumitaresursa la un moment dat;
o operatie de tip hold and wait - un proces detine resursele alocate in timp ce asteaptaprimirea altor resurse;primirea altor resurse;
nu este posibila preemptiunea - resursele nu pot fi dealocate fortat de la procesul care le detine;
asteptare circulara (engl. circular wait) - presupune existenta unui lant inchis de procese, astfel incat fiecare proces tine ocupata cel putin o resursa asteptata de urmatorul procesdin lant.
Resursa Acere
detinuta de
4/27/2014 Programarea Aplicatiilor in Timp Real 143
Resursa B
Proces 1 Proces 2
ceredetinuta de
-
Deadlock:
primele trei conditii sunt necesare, dar nu si suficiente pentru aparitia deadlock-ului.
ce-a patra este o consecinta potentiala a primelor trei conditii (adica, daca una dintre ce-a patra este o consecinta potentiala a primelor trei conditii (adica, daca una dintreprimele trei conditii sunt indeplinite, poate apare o secventa de evenimente care pot conduce la o coada circulara fara rezolvare)
astfel, cele patru conditii, considerate impreuna sunt conditiile necesare si suficiente pentruaparitia deadlock-ului.
o coada circulara nerezolvata poarta denumirea de deadlock
4/27/2014 Programarea Aplicatiilor in Timp Real 144
-
Sumar curs PATR:
Notiuni introductive: sistem in timp real si sisteme embedded in timp-real, sisteme de operare in timp real, limbaje de programare pentru aplicatii in timp-real, programareconcurenta, definitii (proces, fir de executie, task, preemptiune);
Aspecte concurentiale ale aplicatiilor in timp-real - mecanisme pentru sincronizarea si Aspecte concurentiale ale aplicatiilor in timp-real - mecanisme pentru sincronizarea sicomunicarea intre taskuri (sincronizare, excludere mutuala, mesaje, etc);
Aspecte temporale ale aplicatiilor in timp-real caracteristici de limbaj pentru specificarea, implementarea si analiza deadline-urilor;
Mecanisme de planificare pentru aplicatii in timp-real algoritmi de planificare, evitareainversiunii de prioritate.
Continuarea cursului de PATR:
4/27/2014 Programarea Aplicatiilor in Timp Real 145
Sisteme n Timp Real sem I, anul IV Tehnici de specificare i proiectare a aplicaiilor software n timp real Organizarea aplicaiilor n timp-real. Proiectare de sistem UML i SysML (OMG) Dezvoltarea pe baz de model a aplicaiilor n timp real MDD (Model driven Development)
top related