Dizajn real-time sistema
Sistemi u realnom vremenu pr.2
Vanr.prof.dr. Lejla Banjanović-Mehmedović
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Dizajn sistema realnog vremena

Hardverski dio dizajna
j uključuje:
j
j



Softverski dio dizajna uključuje:




dizajn, razvoj, testiranje arhitekture fizičkog sistema, štampane
ploče, individualnih komponenti
često se koristi Verilog HDL-Hardware Design Language – za
modeliranje hardvera i kao simulacioni alat
taskove ili algoritme aplikacije, pisane u jezicima visokog nivoa,
asembleru ili kombinaciji
često se koristi Unified Modeling Language (UML) – kao strukturna
metoda za p
prezentaciju
j softverskog
g alata za modeliranje
j
Integracija ova dva segmenta
Testiranje i debagiranje sistema u sprezi sa fizičkim svijetom
analognih i digitalnih siganala
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
1
Proces dizajna

Podjela procesa dizajna s obzirom na
smjer toka odvijanja dizajna:


Odozgo prema dole (eng. Top-Down),
Odozdo prema gore (eng. Bootom-Up).
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Proces dizajna “Odozgo-prema Dole”

Prednosti:

Pogreške i nedostaci u dizajnu se otkrivaju ranije (u ranim
fazama)
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
2
Proces dizajna “Odozdo-prema Gore”

Prednost:


uticaj “neidealne”
implementacije može uzeti u
obzir u ranom stadiju
procesa dizajna.
Nedostatak:

Sistem može biti simuliran
samo kada je u cijelosti
implementiran, tako da
pogreške i nedostaci u
dizajnu sistema nisu
primjetni do kasnijih faza,
što može uzrokovati
značajne troškove i
kašnjenja u razvoju.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Tehnike dizajniranja






Prirodni jezici
Matematička specifikacija
Dijagrami toka
Pseudokod
Dijagrami stanja
Petrijeve
j
mreže
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
3
Prirodni jezici

Automobilski
A
t
bil ki simulator
i l t
sastoji
t ji se od
d sistema
i t
za upravljanje,
lj j
kočenje, ubrzavanje i displeja. Svaki sistem izvodi operacije
sporadično, osim displej sistema koji izvršava operacije svakih 100
milisekundi.
Sistem za upravljanje je pokrenut kada vozač okrene točak za ugao
θ, gdje je θ veće od -30, a manje od 30 stepeni. Pozicija
automobila u odnosu na x,y ravan mijenja se u smjeru x ose za
veličinu koja je proizvod brzine u vremenu t, vrijeme za koje je
točak okrenut i kosinusa ugla za koji je točak zakrenut. Pozicija se
mijenja u smjeru y ose na isti način,
način osim što se koristi sinus ugla
zakretanja točka.
Ubrzanje u bilo kojem trenutku je ubrzanje zbog pritiskanja pedale.
Usporavanja se vrši pritiskanjem kočnice u nepromijenjenom
vremenu. I ubrzavanje i usporavanje su konstantni i pozitivni.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Matematička specifikacija

Sistem za upravljanje je pokrenut kada vozač okrene točak za ugao
θ [-30,30]. Pozicija automobila u odnosu na x,y ravan mijenja se
za:
y  v(t )T sin 
x  v(t )T cos 
gdje je T vrijeme za koje je točak okrenut. v (t ) je dato kao
v (t )   (t )t
a (t )   (t )   (t )
i  (t ) i  (t ) su funkcije ubrzanja i kočenja , date sa
 (t )  BT (t )
 (t )  AT (t )
T
(t
A i B su pozitivne konstante i  ) i T (t ) su funkcije koje opisuju
kada se koristi ubrzavanje i kočenje i koliko dugo.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
4
Dijagrami toka




Dijagrami toka su vjerovatno najstariji alat za
modeliranje softverskih sistema i široko su razumljivi.
Dijagrami toka su korisni za sisteme reda 5.000 do
10.000 instrukcija, ali nisu pogodni za sisteme iznad
te veličine.
U sistemima sa više zadataka, dijagrami toka mogu
biti korišteni da opišu svaki zadatak posebno, ali
međudjelovanje između procesa nije lako
predstavljeno
d t lj
i vremensko
k ponašanje
š j ne može
ž biti
opisano.
Na kraju, dijagrami toka često podržavaju neželjeni
GOTO iskaz.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Dijagrami toka
Dijagram toka u
avioelektroničkom sistemu
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
5
Pseudokod


Pseudokod je jezik za programiranje sa
jednostavnom semantikom za koju obično ni jedan
kompajler nije napravljen.
Koristi se za specifikaciju sistema na način koji je
blizak stvarnom pisanju koda.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Pseudokod i jezici za dizajniranje
programa
begin
Accept the card
Display “Please enter your code”
If code not correct
begin
Display “Sorry”
Exit/Eject card
end
else
begin
Display “Press key”
Accept function key
If key=query account
begin
Display balance
Exit/Eject card
end
Sistemi realnog
vremena 2
else
begin
if key=withdraw
begin
Display “amount?”
Accept amount
if amount > balance
begin
Display “Sorry”
Exit/Eject card
end
end
else
begin
Remit cash
Exit/Eject card
end
end
else
begin
if key=deposit
begin
Display “amount?”
Accept deposit
Exit/Eject card
end
else
begin
Display “Illegal function”
Exit/Eject card
end
end
end
Copyright: Lejla BanjanovicMehmedovic
Opis bankomata
6
Dijagrami stanja




Definisanje stanja sistema u bilo kom
vremenskom trenutku možemo prikazati korištenjem
varijabli stanja.
Kada dođe do bilo kakve promjene varijabli stanja,
mjenja se i stanje sistema.
Sistem može promijeniti stanje u zavisnosti od
 vremena ili
 okolnosti specifičnih događaja.
Za skup varijabli stanja, promjena stanja sa
vremenom se naziva ponašanje sistema.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Dijagrami stanja






Dijagrami stanja ili grafovi opisuju
ponašanje
š
sistema.
Dijagrami stanja su moćan alat za
specifikaciju i modeliranje ponašanja
bilo kojeg tipa hardverskog ili
softverskog sistema.
Stanja digitalne memorijske jedinice
U dijagramima stanja, svako stanje je
predstavljeno krugom, čvorom.
[Ulazi]/[Izlazi]/
Stanje b
Npr. memorija ima 2 stanja, 1 ili 0, što
1
izražava njeno ponašanje - puna ili
prazna.
Tranzicije između 2 stanja
0
označavamo labeliranim usmjerenim
Stanje a
[Ulazi]/[Izlazi]/
linijama ili strelicama ili (ivicama u
grafičkoj teoriji).
Tranzicije između stanja digitalne
Kako su linije usmjerene, dijagrami
stanja nazivaju se usmjereni grafovi. memorijske jedinice
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
7
Dijagrami stanja



Subsistem navigacije korištenjem dijagrama stanja
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Mašina konačnog stanja


Mašina konačnog
g stanja
j oslanja
j se na činjenicu
j
da
mnogi sistemi mogu biti predstavljeni tačno
određenim brojem jedinstvenih stanja.
Postoje tri metode za predstavljanje mašina sa
konačnim brojem stanja (eng. Finite State Machine):



Metoda teorije skupova
Metoda dijagrama
Metoda predstavljanja matricama
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
8
Koncept mašine konačnog stanja
(FSM)


Mašina konačnog stanja (finite state machinemachine
FSM) je prezentacija događajem-vođenog
(reaktivnog) sistema.
U sistemu vođenom događajem, sistemski
prelazi iz jednog stanja (moda) u drugo
propisano stanje,
stanje obezbjeđuju da definisani
uslov promjene bude tačan.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Mašine sa konačnim brojem
stanja

Hardverska implementacija takvih mašina
dostiže se upotrebom:




VLSI
ROM-ova
Diskretne logike
Softverska implementacija se tipično
pojavljuje kao ugrađeni program, koji se
izvršava na različitim vrstama hardvera.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
9
Mašine sa konačnim brojem
stanja






FSM mašina :
M=(I,O,S,λ,δ)
I – konačan neprazan skup ili vektora ulaza
O – konačan neprazan skup ili vektora izlaza
S – konačan neprazan skup ili vektor stanja
δ - mapiranje I x S -> S
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Mašine sa konačnim brojem
stanja






Izlazi mogu
g biti:
vrijednosti varijabli stanja,
kombinacija varijabli stanja ili
kombinacija varijabli stanja i ulaza
Ako je izlazna funkcija funkcija stanja i ulazne abecede
tad ta definicija odgovora Mealyjevom modelu.
Ako izlazna funkcija ovisi samo o stanju, tad ta definicija
odgovora Mooreovom modelu.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
10
Mašina konačnog stanja
Prva brzina
Treca brzina
Peta brzina
Desno,nazad
Lijevo, nazad
Lijevo, naprijed
Nazad
Desno,naprijed
Naprijed
Nazad
Ler
Naprijed
Nazad
Desno,nazad
Lijevo, nazad
Desno,naprijed
Lijevo, naprijed
Naprijed
Lijevo, nazad
Desno,naprijed
Cetvrta
brzina
Druga brzina
Mašina stanja za predstavljanje automatskog prenosa automobila
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Petrijeve mreže



Petrijeve mreže predstavljaju formalni grafički
metod modeliranja predložen od strane Carla
Adama Petrija 1962. godine
Predstavlja matematski alat za opisivanje,
upravljanje i analizu sistema, čije su osobine
asinhronost, distribuiranost, paralelnost,
nederminizam i/ili stohastičnost.
Petrijeve
j
mreže su tip
p matematičkih modela koji
j se
koriste kako bi se identifikovale operacije koje treba
izvesti u sredini višestrukog procesiranja ili
višestrukih zadataka, ali se takođe mogu i grafički
predstaviti.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
11
Petrijeve mreže


Koriste
K
i t se za:
 dizajn komunikacijskih protokola, dizajn računarskih arhitektura
 dizajn sistema baze podataka, dizajn distribuiranih sistema
 dizajn upravljačke logike i planiranja za automatizirane i
proizvodne sisteme, brzi razvoj prototipa, ...
Vrste Petrijevih mreža:




mreže stanja i prijelaza (Petrijeve mreže, predikcijske mreže)
vremenske Petrijeve mreže,
stohastičke Petrijeve mreže - najpopularnije
Najvažnija primjena Petrijevih mreža je u modeliranju složenih
stohastičkih sistema DES (Discrete Event Systems)
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Definicija Petrijeve mreže

Petrijeva mreža je šestorka oblika:
PM  ( P, T , I , O, , m0 )






Početno stanje vektora stanja m: m0 : P  0,1, 2,...
Skup svih mjesta P: P   p1 , p2 ,..., pm 
Skup svih prelaza T: T  t1 , t2 ,..., tn 
Funkciju ulaza I,
I ulazna matrica događaja: I : T  P
Funkciju izlaza O, izlazna matrica događaja: O : T  P
Težinska funkcija (matrica svih težinskih
keoficijenata u PM):  : ( I , O)  1, 2,...
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
12
Petrijeve mreže

Petrijeva mreža je mreža mjesta i prelaza, u kojoj
mjesta imaju ulogu uslova
prelazi ulogu događaja u smislu definicije sistema uslova i događaja.
P1
P1
f1
f1
t1
t1
f1
P2
f1
f2
t2
f2
P2
f2
f2
t2
netačno
P1
netačno
Zadržavanje
u petlji
tačno
Dijagram toka analogan
Petri mrežama
Sistemi realnog
vremena 2
tačno
t1
f1
Copyright: Lejla BanjanovicMehmedovic
f1
While petlja
Struktura Petrijeve mreže

Graf Petrijeve
j
mreže je
j usmjereni
j
biparitetni
p
multigraf:
g

gdje je



G  (V , A)
V - skup čvorova
A - skup usmjerenih veza
Petrijeva mreža - bipartitni graf sastavljen od:
 mjesta (engl. places), koja su grafički predstavljena
ugo
a,
krugovima,
 prelaza (engl. transitions) - predstavljenim
pravougaonicima i
 direktnih grana (engl. directed arcs) koje povezuju
mjesta i prelaze.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
13
Struktura Petrijeve mreže





Usmjerena veza označava se sa a(p
a(p,t)
t) ili a(t,p),
a(t p) gdje
p i t predstavljaju čvorove koji su povezani sa vezom
a.
Svaka veza ima određenu težinu u obliku cijelog
pozitivnog broja pri čemu
K –težinska veza prikazana ili skupom od k paralelnih
lukova ili težinskim faktorom koji je ispisan kod veze
Ako su težine svih grana Petrijeve mreže jednake 1,
tada se takva mreža naziva ordinarna ili obična
Petrijeva mreža.
U suprotnom, mreža je otežana ili neordinarna.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Označavanje Petrijeve mreže




Vektor stanja (eng. marking) m(p) definisan je kao
funkcija označavanja sa skupa mjesta u skup
nenegativnih cjelih brojeva m:P->N0.
Ako je određenom mjestu pi pridruženo stanje m(pi)
kaže se da je ono označeno sa m(pi) oznaka (eng.
token).
Označavanje Petrijeve mreže provodi se pridruživanjem
oznaka () mjestima mreže, sa značenjem ispunjenosti
uslova
l
Prisutnost oznake u mjestu pi se interpretira kao istinitost
uslova vezanog za to mjesto ili kao podatak da je m(pi)
predmeta obrade ili resursa raspoloživo.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
14
Označavanje Petrijeve mreže



Svaka akcija “paljenja”
paljenja mreže uklanja oznake (eng.
(eng
tokens) iz ulaznih mjesta i dodaje ih jednom ili više
izlaznih mjesta.
Broj i raspored oznaka u mjestima može se izmijeniti
tokom izvođenja Petrijeve mreže.
Brojj uklonjenih
B
kl j ih oznaka
k na ulaznim
l
i i broj
b j dodanih
d d ih
oznaka na izlaznim mjestima ovisi od težine (engl.
weight) ulazećih/izlazećih grana, respektivno.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Pravila izvedbe Petrijeve mreže


Izvedba Petrijeve mreže određena je pravilima
izvođenja koji upravljaju kada i kako se oznake
pomiču iz jednog mjesta u drugi uz pomoć aktiviranja
prelaza.
Međutim, prelaz se može aktivirati samo ako je
omogućen, to jest ako svaki od ulaznih mjesta ima
najmanje onoliko oznaka koliko ima grana usmjerenih
prema prelazu:


μi>I(pi,tj)
Mreža se izvodi realizacijom prelaza, pri čemu ulazna
mjesta gube oznake, a izlazna ih dobivaju.
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
15
Vektor oznaka


Na slijedećim slikama prikazano je
nekoliko faza rada označene mreže.
Vektor oznaka za tako označenu mrežu
je slijedećeg formata:
μ =(( μ1,μ2 ,μ3,μ4)
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Primjer 1: Dizajniranje robotske
ćelije Petrijevim mrežama
p3
p1
t1
p2
t2
Pripremljeni Preuzimanje Držanje Odlaganje
elementi
elemenata elemenata elemenata
Sistemi realnog
vremena 2
p4
Odloženi
elementi
Copyright: Lejla BanjanovicMehmedovic
16
Primjer 1: Dizajniranje robotske
ćelije Petrijevim mrežama


P1 - 2 elementa su
pripremljena za
uzimanje od strane
robota;
P3 – robot je na
raspolaganju pa je
raspolaganju,
prelaz t1 omogućen
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Primjer 1: Dizajniranje robotske
ćelije Petrijevim mrežama

Kako je t1 bilo
omogućeno, p2
dobiva element
(držanje elementa)
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
17
Primjer 1: Dizajniranje robotske
ćelije Petrijevim mrežama

Omogućen prelaz t2
pa imamao odložen
element u p4, pa je i
robot spreman (p3)
za novi prenos
p3
p1
t1
p2
t2
p4
m2=(1,0,1,1)
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
Primjer 1: Dizajniranje robotske
ćelije Petrijevim mrežama

Kako je t1 bilo
omogućeno, p2
dobiva element
(držanje elementa)
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
18
Primjer 1: Dizajniranje robotske
ćelije Petrijevim mrežama

Omogućen prelaz t2
pa imamao odložen
drugi element u p4,
pa je robot opet
spreman (p3) za
novi p
prenos,, s tim
da sada više nema
novih elemenata
Sistemi realnog
vremena 2
Copyright: Lejla BanjanovicMehmedovic
19
Download

Dizajn real-time sistema - Vanr.prof.dr. Lejla Banjanović