CARACTERIZAREA SISTEMELOR TIMP-REAL

CARACTERIZAREA SISTEMELOR TIMP-REAL

1.Definirea sistemelor timp-real

        Sistemele TR sunt definite ca fiind acele sisteme in care corectitudinea depinde nu numai de rezultatul logic al prelucrarii, ci si de momentul la care este disponibil [Stankovic92]. Principala dimensiune a sistemelor TR o constituie deci timpul. Anumite prelucrari trebuie realizate in limite de timpi predeterminati, procesarile fiind deci supuse constrangerilor temporale.

Functie de strictetea constrangerilor, sistemele TR pot fi impartite in doua subclase:

• sisteme TR critice - hard real-time systems - sistemele pentru care neindeplinirea unei constrangeri se considera a fi o eroare grava ( failure ) a sistemului, putand avea urmari catastrofale
• sisteme TR necritice - soft real-time systems - sistemele pentru care neindeplinirea oricarei constrangeri poate fi tolerata.

Sistemele TR pot fi ilustrate la diferite nivele de abstractizare.La un nivel inalt de abstractizare, un sistem TR apare ca format din trei subsisteme componente.

• Subsistemul controlat reprezinta aplicatia sau mediul care dicteaza cerintele TR.
• Subsistemul de control este intregul echipament de calcul, care este conectat cu mediul controlat printr-un numar de intrari si iesiri, formand interfata aplicatiei. Subsistemul de control poate cuprinde unul sau mai multe procesoare si resurse. Procesoarele si resursele sunt gestionate de un sistem software denumit sistem de operare TR - SOTR. In mod normal, un sistem TR are o interfata cu un operator uman,
• subsistemul operator, care initializeaza si monitorizeaza intregul sistem, dand anumite comenzi, mai ales in situatii exceptionale. Sistemele TR ale viitorului se doresc a fi suficient de inteligente, sigure, autonome, pentru o executie independenta de operatorul uman [Stankovic92].

Un sistem TR raspunde unor stimuli externi receptionati prin intrarile sale. Acesti stimuli pot fi:

• time-triggered - daca sistemul testeaza periodic intrarile sale
• event triggered - daca aparitia datelor la intrare este semnalata prin intreruperi.

Fiecare stimul determina anumite prelucrari in sistemul TR, rezultatele putand duce la actualizarea unor date interne, referitoare la sistemul condus sau la trimiterea unui semnal de raspuns spre exterior. Setul de pasi care se executa intre receptionarea unui stimul si raspunsul sistemului la acesta, se numeste tranzactie TR. Conducerea unui proces impune anumite constrangeri temporale tranzactiilor TR, acestea fiind esentiale in specificarea sistemului TR.

In specificarea sistemelor TR trebuie sa se tina cont de doua ipoteze, estimari:

• ipoteza de incarcare - load hypothesis - se refera la rata maxima cu care poate apare fiecare stimuli extern si care reprezinta o estimare a incarcarii sistemului
• ipoteza de eroare - fault hypothesis - este un set de estimari referitoare la tipul de erori si la rata maxima de erori ce ar putea apare in timpul executiei, sistemul trebuind sa functioneze corect chiar in cazul aparitiei setului respectiv de erori.

2.Caracteristicile sistemelor TR

SOTR trebuie sa ia in considerare notiunea timp la toate nivelele.
In proiectarea unui SOTR trebuie sa fie adresate urmatoarele aspecte [Stankovic92]:

• Dimensiunea timp trebuie sa fie principiul central de proiectare. Constrangerile temporale trebuie sa fie surprinse de tehnicile de specificare si verificare folosite si deci sa nu fie tratate numai la implementare;
• Sa se realizeze echilibrul ( fragil ) dintre flexibilitate si predictibilitate: sistemul trebuie sa ramana suficient de flexibil pentru a se putea adapta unui mediu dinamic, dar in acelasi timp sa permita satisfacerea constrangerilor temporale;
• O gestionare a resurselor integrata care sa trateze aspectele legate de constrangeri temporale, predictibilitate, adaptabilitate, corectitudine, siguranta, toleranta.

Un SOTR trebuie sa ofere [Stankovic92]:

• un model care sa permita specificarea constrangerilor temporare pentru toate tipurile de procese
• un limbaj care sa permita specificarea clara a sistemului si care sa permita luarea in considerare a comunicatiilor asincrone cu exteriorul
• politici de planificare si gestionare a resurselor care sa confere sistemului proprietatile de garantie si predictibilitate
• protocoale de comunicatie care sa ia in considerare aspectele temporare
• protocoale speciale pentru gestiunea memoriei
• mecanisme de sincronizare inter-taskuri si de sincronizare de ceas.

Aplicatiile TR din prima generatie rulau pe sisteme monoprocesor, problemele ce la rezolvau fiind relativ simple si nepresupunand algorimi sofisticati sau prelucrari foarte complexe. In ultimii 10-15 ani, sistemele TR au evoluat ca urmare a cercetarilor si rezultatelor deosebite din acest domeniu, care au fost imperativ cerute de necesitatea proiectarii unor aplicatii concrete, foarte complexe, critice, ce implica siguranta si predictibilitate deosebite: sisteme de control al traficului aerian, sisteme informationale distribuite, centrale nucleare, sisteme de aparare spatiale, largi sisteme de comanda si control in productie, etc.

Pentru a putea executa aplicatiile TR actuale, foarte complexe, atributele sistemelor TR trebuie sa fie:

• Predictibilitatea - se refera la garantarea indeplinirii constrangerilor de timp ale aplicatiilor, in contextul dinamicii mediului;
• Granularitati multiple ale taskurilor si de comunicatie - aplicatiile TR complexe constau din taskuri de dimensiuni diferite, de la taskuri ce cuprind cateva instructiuni si care se executa cu o periodicitate ridicata, pana la taskuri de dimensiuni foarte mari, care se executa rar. Taskurile comunica intre ele prin mesaje de granularitati diferite;
• Semantici diferite de timp - Taskurile unui sistem pot avea grade diferite de criticalitate, urgenta, se pot modifica dinamic, pot exista grupuri de taskuri cu acelasi deadline, deci planificatorul trebuie trata toate aceste situatii;
• Modele multiple de taskuri si comunicatii - Constrangerile temporale ale taskurilor implica constrangerea temporala a comunicatiilor; functie de modelul comunicatiilor utilizate, se poate presupune ca mesajele nu pot fi pierdute niciodata sau nesosirea unui mesaj la timp poate fi tolerata pentru a se putea trata un eveniment asincron.
• Configurabilitate - Din cauza arhitecturilor gazda care pot varia foarte mult de la sisteme cu un numar mic de procesoare la retele distribuite pe arii intinse - WAN, SOTR trebuie sa fie configurabile ca dimensiune si functionalitate;
• Adaptabilitate - SOTR trebuie sa se adapteze in performanta si functionalitate posibilelor schimbari externe. Cercetarile curente diferentiaza doua tipuri de adaptari: cele preventive, care anticipeaza schimbarile din mediu ai cele reactive, care trateaza schimbarile neasteptate.
• Toleranta la defecte - Sistemele trebuie sa incorporeze mecanisme performante software si hardware pentru detectarea si tratarea erorilor.

Performantele deosebite cerute de complexele sisteme TR actuale, precum si caracteristicile sistemelor distribuite, fac din sistemele distribuite o solutie viabila pentru sistemele TR.

3.Definirea si caracteristicile sistemelor distribuite

Un sistem distribuit este definit ca fiind un sistem constituit din mai multe elemente de prelucrare - noduri - legate in retea, care coopereaza pentru realizarea unei prelucrari integrate. Caracteristicile sistemelor distribuite sunt [CDK95]:

• partajarea resurselor
• deschidere - sistemul poate fi extins prin noi servicii fara o intrerupere ( disruption ) sau duplicare a serviciilor existente )
• concurenta
• scalabilitate
• toleranta la defecte
• transparenta - transparenta distribuirii cuprinde entitatile: accesul la informatii, localizarea, concurenta, replicarea, defectele, migrarea, performanta si scalarea.

Sistemele distribuite pot fi:

• puternic conectate - tightly coupled - daca nodurile componente au acces la o memorie comuna
• slab conectate - loosely coupled - daca nodurile componente nu au acces la o memorie comuna.

De asemenea, functie de tipurile nodurilor, sistemele distribuite pot fi:

• omogene - daca toate procesoarele componente sunt de acelasi tip
• neomogene - daca procesoarele componente nu sunt de acelasi tip.

Avantajele distribuirii pentru domeniul TR sunt:

• performanta imbunatatita prin exploatarea paralelismului
• cresterea disponibilitatii ( availability ) si sigurantei ( reliability ) datorita redundantei
• dispersia prelucrarii in punctele de comanda si control
• facilitatea de crestere incrementala prin adaugarea de procesoare si linii de comunicatie.

De cele mai multe ori, aplicatiile TR au ca suport sisteme distribuite slab cuplate, omogene.

Distribuirea aplicatiilor TR, aduce insa o serie de probleme noi proiectarii sistemelor TR, fiecare concretizandu-se in cate un domeniu actual de cercetare:

• tehnici de specificare si verificare a constrangerilor temporale si de distribuire
• planificarea distribuita a aplicatiei
• sincronizare globale de ceas, noi mecanisme de sincronizare si comunicare intre taskuri
• limbaje de programare distribuita in TR
• toleranta la defecte in mediu TR si distribuit.

4.Evolutia sistemelor TR

Prima propunere de utilizare a unui calculator pentru a opera in timp-real ca parte a unui sistem de control, a fost facuta de Brown si Campbell in 1950 [BC50] de folosire de elemente analogice de calcul, neexcluzandu-se si cele digitale.

Primele calculatoare digitale construite pentru control TR au fost cele pentru operarea avioanelor, iar in 1954, un calculator Digitrac a fost cu succes folosit pentru zborul automat [Be94].

Aplicarea calculatoarea in controlul proceselor industriale s-a realizat la sfarsitul anilor '50: intr-o electrocentrala din Louisiana si o rafinarie din Texas, prin closed-loop control.

Primul sistem de control digital direct a fost instalat in 1962 la o intreprindere chimica din Anglia; era un sistem cu 120 bucle de control si 256 puncte de masurare. In aceeasi perioada se inregistraza primul control ierarhic la o intreprindere din Texas.

Primele programe TR au fost scrise in cod masina, programele fiind relativ reduse. Cresterea in complexitate a aplicatiilor, a impus dezvoltarea unor sisteme de operare TR si a unor limbaje de programare TR. La sfarsitul anilor '60, au aparut primele compilatoare de PROCESS FORTRAN.

Minicalculatoarele aparute la inceputul anilor '70 au fost folosite in sistemele TR, inregistrandu-se si sisteme tolerante bazate pe solutia stand-by. Anul 1974, de aparitie a microprocesoarelor a marcat o evolutie spectaculoasa in domeniul TR. S-a trecut de la sistemele TR monoprocesor, la cele multiprocesor si apoi la cele distribuite.
 

5.Caracteristicile taskurilor TR

5.1.Definirea taskurilor TR

Termenul cheie in implementarea unui sistem TR il constituie taskul TR. Taskurile TR corespund tranzactiilor TR pe care sistemul le executa si reprezinta calea naturala de trecere de la specificare spre implementarea aplicatiei TR. In continuare se prezinta un model de taskuri TR ce generalizeaza varietatea de modele intalnite in bibliografie [GMS94, Me92, Pa94, PD93], multe aplicatii TR folosind doar un subset al caracteristicilor.

In cazul cel mai simplu, un task TR poate fi modelat ca o actiune atomica, in sensul de a prelua date de intrare, a le prelucra si a furniza un rezultat, fara a schimba date in starile intermediare ale prelucrarii. Taskurile atomice constituie obiectul multor teme de cercetare [GMS94, Me92, Pa94, PD93], deoarece pot fi tratate mai simplu decat taskurile generalizate si prin utilizarea lor, multe probleme pot fi implementate.

Taskurile TR generalizate sunt mult mai complexe, schimburile de date intre taskuri putandu-se realiza in orice punct al executiei lor. Aceste taskuri constau din mai multe secvente de prelucrare si sincronizare. In timpul unei secvente de procesare, un task TR generalizat realizeaza prelucrarea unor date locale, iar pe parcursul unei secvente de sincronizare, realizeaza accesarea unei resurse partajabile sau comunicarea cu un alt task.

5.2.Caracteristicile temporale ale taskurilor TR

Din punctul de vedere al implementarii, taskurile TR reprezinta cele mai mici unitati de prelucrare ce pot fi planificate. Intregul sistem consta dintr-un set de n taskuri i=1,n, care coopereaza pentru indeplinirea cerintelor de implementare. Fiecare task ti are asociat un set de proprietati:

ti(ai, ri, ti,max, di, pi, li, vi(t), Ri)

unde

• ai - momentul aparitiei taskului Ti pe un anumit procesor - este fie momentul crearii, fie cel al transferarii de pe un alt procesor. Dupa acest moment, taskul va fi luat in considerare de catre planificator
• ri - momentul la care taskul poate sa-si inceapa executia, este pregatit ( ready ); unele taskuri sunt dependente de altele, neputand fi lansate in executie pana la terminarea primelor; aceste taskuri sunt legate prin relatii de precedenta ( isi comunica un rezultat la sfarsitul prelucrarii ) sau de cauzalitate; uneori momentul ri coincide cu ai
• ti,max - timpul de executie pentru cazul cel mai defavorabil ( worst case execution time - WCET )
• di - momentul, termenul limita la care taskul isi poate termina executia - deadline
• pi - perioada de activare, in cazul in care ti este un task periodic
• li - prioritatea ( urgenta, criticalitatea ) taskului ti
• vi(t) - o functie valoare, optionala, care descrie importanta pentru sistem ca taskul ti sa-si termine executia inainte de deadline
• Ri - setul de resurse necesar executiei taskului.

Cunoasterea apriorica a parametrilor taskurilor nu este doar dificil de realizat, dar implica si o limita superioara in cerinta de resurse, parametrii corespunzand cazului celui mai defavorabil. Planificarea realizata pe baza acestor valori, asigura insa fiabilitatea sistemului. In timpul executiei, parametrii oscileaza intre o valoare minima si cea maxima calculata, un mare numar de resurse ramanand nefolosite pentru un procent destul de mare de timp.

Pe baza parametrilor ri, ti,max, di, planificatorul determina urmatorii parametri:

• si - momentul la care taskului ti i se aloca ( scheduled ) resursele Ri necesare executiei , deci momentul activarii
• ci - momentul terminarii executiei ( completed ); acest moment nu corespunde neaparat momentului si+ti,max, pentru ca taskul poate fi suspendat temporar din executie de catre un task mai prioritar
• tri - timpul de raspuns al taskului, perioada dintre momentul cand taskul poate fi activat - ri si cel cand isi termina executia - ci, deci tri=ci-ri
• tli - timpul de latenta al unui task, adica timpul cu care un task poate fi intarziat, fara a depasi deadline, deci tli=di-ri-ti,max
• li - laxitatea taskului - pentru indeplinirea constrangerii de timp di, deadline, taskul trebuie sa-si inceapa executia cel mai tarziu la momentul li=di-ti,max
• ui - rata de utilizare a procesorului, ui=ti,max/pi.

Ansamblul acestor parametri trebuie sa verifice relatiile:

ai<ri<si<ci-ti,max<di-ti,max.

In unele sisteme TR, termenul limita, deadline, este modelat printr-o functie de timp, numita functie valoare - time value function [Me92]. Functia valoare vi(t) descrie utilitatea pentru sistem a terminarii taskului la momentul t. Functia vi(t) are valoarea maxima daca ti isi termina executia inainte de deadline di. Daca dupa expirarea termenului limita, di functia valoare:
 

• scade brusc la -x, respectiv la 0 - termenul limita este strict - hard deadline, neindeplinirea caruia putand duce la efecte catastrofale, in primul caz
• scade treptat la 0 - termenul limita este esential - soft deadline
• se mentine la aceeasi valoare constanta - termenul nu este esential - non-real-time value function, deci taskul nu are nu are constrangeri temporale explicite.

5.2.Notiunea de prioritate

Nu toate taskurile au aceeasi importanta pentru un sistem. Importanta fiecarui task se ilustreaza print-un parametru al taskului, cel de prioritate. Prioritatile se definesc de catre utilizator sau sistem, functie de evolutia sistemului ele se pot modifica, fiind dinamice sau pot ramane constante, caz in care se numesc statice. Taskurile pot fi clasificate in trei categorii, functie de prioritate, clasificare propusa pentru sistemul Spring [SR91], dar care a fost adoptata pentru majoritatea sistemelor TR:
 

• taskuri TR critice - hard real-time tasks - indeplinirea constrangerilor lor temporale este esentiala pentru sistem, depasirea deadlines neputand fi tolerata si ducand la efecte catastrofale; au prioritatea cea mai mare; acestor taskuri in multe sisteme, li se rezerva static resursele, aceasta fiind o garantie necesara, dar nu susficienta pentru a trata toate situatiile dinamice ce ar putea aparea; in general, numarul taskurilor critice este foarte redus comparativ cu numarul total de taskuri ale sistemului
• taskuri TR esentiale - soft real-time tasks - indeplinirea constrangerilor lor temporale este importanta pentru sistem, dar depasirea deadlines poate fi tolerata
• taskuri neesentiale - non-real-time tasks - nu sunt direct asociate activittailor TR ale aplicatiei; au prioritatea cea mai scazuta, planificarea lor pentru executie se realizeaza dupa executia celor din primele doua categorii.

5.3.Notiunea de periodicitate

Dupa modul de succedare al momentelor de lansare in executie si, taskurile se clasifica in:
 

• taskuri periodice - un task ti este periodic, cu perioada pi daca este reexecutat dupa fiecare durata de timp egala cu pi
• taskuri aperiodice - timpii de activare nu sunt periodici, depinzand de un set de conditii de activare; de obicei, aceste taskuri sunt necritice
• taskuri sporadice - au o natura aperiodica, avand de obicei constrangeri stricte ( hard deadlines ).

Majoritatea taskurilor unui sistem sunt periodice.

5.4.Notiunea de planificare

Sistemele TR interactioneaza cu exteriorul, garantand respectarea constrangerilor temporale. Nerespectarea acestor constrangeri este o eroare grava a sistemului, rezultand cel mai des din conflictele survenite intre taskurile in executie. Aceste conflicte sunt de doua tipuri, referindu-se la procesoare si resurse:
 

• conflictele datorate disputarii procesoarelor - mai multe taskuri trebuie executate simultan pe acelasi procesor, pentru a-si putea indeplini constrangerile. Acest conflict poate fi rezolvat prin mecanisme de planificare care asigura accesul la procesor; in planificare se tine cont de parametrii anterior definiti pentru taskuri ca timp de executie, deadline. Planificarea taskurilor pe un procesor consta in a determina secventa de executie a taskurilor pe acel procesor, astfel incat indeplinirea constrangerilor sa fie garantata;
• conflictele datorate disputarii resurselor - in rezolvarea acestor conflicte se apeleaza la mecanisme de planificare a resurselor, in care aspectele temporale trebuie luate in considerare, pentru a se putea indeplini constrangerile impuse taskurilor.

Un mecanism de planificare trebuie sa coordoneze executia unui set de taskuri, avand anumite constrangeri temporale si de resurse, pe un anumit sistem. Daca sistemul este multiprocesor, planificarea are un aspect local si unul global. Primul se refera la o gestionare temporala, iar al doilea se refera la plasarea pe procesoarele disponibile a taskurilor ( dinamice ), fiind deci vorba de o gestionare distribuita.

O alta caracteristica a taskurilor este preemptibilitatea, posibilitatea de a fi intrerupte, suspendate temporar, de executia altor taskuri. Taskurile pot fi deci:
 

• complet preemptive - cand pot fi intrerupte in orice punct al executiei
•  nepreemptive - cand nu pot fi intrerupte in nici un punct al executiei
• partial preemptive - cand nu pot fi intrerupte in timpul executiei unor regiuni critice.

Activarea taskurilor poate fi facuta de un stimul extern sau de rezultatul unor conditii interne sistemului. O tranzactie TR poate fi implementata nu doar printr-un task, ci si ca un grup de taskuri. Un grup de taskuri poate consta fie din:
 

•  taskuri atomice care au o secventa statica de executie ( constrangeri de precedenta ), fie din
•  taskuri generalizate cu un anumit tipar ( pattern ) de comunicarii in interiorul grupului.

Un grup de taskuri are asociat un deadline unic, termenul limita pentru prelucrarea stimulului ce activeaza grupul, care implica tehnici speciale de planificare pentru taskurile ce-l compun.

Exista doua tehnici de implementare a taskurilor:

• raspunsul garantat - guaranteed response - tehnica ce asigura aprioric indeplinirea constrangerilor temporale, pe baza informatiilor referitoare la incarcare si defecte posibile, cu o rezervare statica de resurse; duce la o risipa de resurse, mai ales pentru taskurile neperiodice, motiv pentru care metoda este folosita mai ales pentru implementarea taskurilor critice;
• efortul cel mai bun - best effort - tehnica nu garanteaza indeplinirea constrangerilor, dar se incearca satisfacerea in primul rand a constrangerilor hard, apoi a celor soft; metoda este mai economica in ce priveste resursele necesare.