Wprowadzenie do

sieci Petriego

Wprowadzenie do

sieci Petriego

Paweł Witas

Paweł Witas

Co to są sieci Petriego ?

Co to są sieci Petriego ?

Sieci warunków i zdarzeń

Sieci warunków i zdarzeń

Każdy warunek jest reprezentowany przez okrąg.

Każdy warunek jest reprezentowany przez okrąg.

Każde zdarzenie jest reprezentowane przez kwadrat.

Każde zdarzenie jest reprezentowane przez kwadrat.

Spełnienie jakiegoś warunku oznacza się umieszczając

Spełnienie jakiegoś warunku oznacza się umieszczając

kropkę (znacznik) w odpowiadającym mu okręgu.

kropkę (znacznik) w odpowiadającym mu okręgu.

Zbiór warunków spełnionych w pewnej konfiguracji

Zbiór warunków spełnionych w pewnej konfiguracji

systemu nazywamy

systemu nazywamy

przypadkiem

przypadkiem

.

.

e

e

Spełnione są warunki wejściowe

Spełnione są warunki wejściowe

warunki

warunki

wejściowe

wejściowe

warunki

warunki

wyjściowe

wyjściowe

Co to są sieci Petriego ?

Co to są sieci Petriego ?

Sieci warunków i zdarzeń

Sieci warunków i zdarzeń

Każdy warunek jest reprezentowany przez okrąg.

Każdy warunek jest reprezentowany przez okrąg.

Każde zdarzenie jest reprezentowane przez kwadrat.

Każde zdarzenie jest reprezentowane przez kwadrat.

Spełnienie jakiegoś warunku oznacza się umieszczając

Spełnienie jakiegoś warunku oznacza się umieszczając

kropkę (znacznik) w odpowiadającym mu okręgu.

kropkę (znacznik) w odpowiadającym mu okręgu.

Zbiór warunków spełnionych w pewnej konfiguracji

Zbiór warunków spełnionych w pewnej konfiguracji

systemu nazywamy

systemu nazywamy

przypadkiem

przypadkiem

.

.

e

e

Spełnione są warunki wejściowe

Spełnione są warunki wejściowe

warunki

warunki

wejściowe

wejściowe

warunki

warunki

wyjściowe

wyjściowe

i wystąpiło zdarzenie „e”

i wystąpiło zdarzenie „e”

Co to są sieci Petriego ?

Co to są sieci Petriego ?

Sieci warunków i zdarzeń

Sieci warunków i zdarzeń

Każdy warunek jest reprezentowany przez okrąg.

Każdy warunek jest reprezentowany przez okrąg.

Każde zdarzenie jest reprezentowane przez kwadrat.

Każde zdarzenie jest reprezentowane przez kwadrat.

Spełnienie jakiegoś warunku oznacza się umieszczając

Spełnienie jakiegoś warunku oznacza się umieszczając

kropkę (znacznik) w odpowiadającym mu okręgu.

kropkę (znacznik) w odpowiadającym mu okręgu.

Zbiór warunków spełnionych w pewnej konfiguracji

Zbiór warunków spełnionych w pewnej konfiguracji

systemu nazywamy

systemu nazywamy

przypadkiem

przypadkiem

.

.

e

e

Spełnione są warunki wyjściowe

Spełnione są warunki wyjściowe

warunki

warunki

wejściowe

wejściowe

warunki

warunki

wyjściowe

wyjściowe

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Przykładowa sieć warunków i zdarzeń

Przykładowa sieć warunków i zdarzeń

Wiosna

Wiosna

Początek lata

Początek lata

Lato

Lato

Początek

Początek

jesieni

jesieni

Jesień

Jesień

Początek zimy

Początek zimy

Zima lub

Zima lub

wiosna

wiosna

Nie

Nie

jesień

jesień

Początek

Początek

wiosny

wiosny

Zima

Zima

Sieci miejsc i przejść (tranzycji)

Sieci miejsc i przejść (tranzycji)

Każde

Każde

miejsce

miejsce

jest reprezentowane przez okrąg

jest reprezentowane przez okrąg

i posiada określoną pojemność znaczników (ozn. przez K)

i posiada określoną pojemność znaczników (ozn. przez K)

Każde

Każde

przejście

przejście

jest reprezentowane przez kwadrat i jest

jest reprezentowane przez kwadrat i jest

aktywną składową systemu mogącą produkować, przesyłać

aktywną składową systemu mogącą produkować, przesyłać

i zmieniać obiekty (reprezentowane przez znaczniki).

i zmieniać obiekty (reprezentowane przez znaczniki).

Łuki wskazują, które składowe systemu są ze sobą bezpo-

Łuki wskazują, które składowe systemu są ze sobą bezpo-

średnio połączone i w których kierunkach obiekty mogą

średnio połączone i w których kierunkach obiekty mogą

przepływać przez sieć.

przepływać przez sieć.

Każdy łuk sieci posiada wagę (liczbę naturalną różną od 0)

Każdy łuk sieci posiada wagę (liczbę naturalną różną od 0)

Sieci składające się z miejsc i przejść modelują właściwo-

Sieci składające się z miejsc i przejść modelują właściwo-

ści systemu związane z liczbą, rozkładem i przepływem

ści systemu związane z liczbą, rozkładem i przepływem

obiektów, których poszczególnych egzemplarzy

obiektów, których poszczególnych egzemplarzy

się nie rozróżnia

się nie rozróżnia

Sieci miejsc i przejść

Sieci miejsc i przejść

Przejście się

Przejście się

odpala

odpala

, usuwając z każdego miejsca

, usuwając z każdego miejsca

wejściowego ilość znaczników równą wadze odp. łuku

wejściowego ilość znaczników równą wadze odp. łuku

i dodając do każdego miejsca wyjściowego ilość

i dodając do każdego miejsca wyjściowego ilość

znaczników równą wadze odp. łuku.

znaczników równą wadze odp. łuku.

4

4

2

2

miejsca

miejsca

wejściowe

wejściowe

miejsca

miejsca

wyjściowe

wyjściowe

2

2

1

1

Sieci miejsc i przejść

Sieci miejsc i przejść

Przejście się

Przejście się

odpala

odpala

, usuwając z każdego miejsca

, usuwając z każdego miejsca

wejściowego ilość znaczników równą wadze odp. łuku

wejściowego ilość znaczników równą wadze odp. łuku

i dodając do każdego miejsca wyjściowego ilość

i dodając do każdego miejsca wyjściowego ilość

znaczników równą wadze odp. łuku.

znaczników równą wadze odp. łuku.

4

4

2

2

miejsca

miejsca

wejściowe

wejściowe

miejsca

miejsca

wyjściowe

wyjściowe

2

2

1

1

Sieci miejsc i przejść

Sieci miejsc i przejść

Przejście się

Przejście się

odpala

odpala

, usuwając z każdego miejsca

, usuwając z każdego miejsca

wejściowego ilość znaczników równą wadze odp. łuku

wejściowego ilość znaczników równą wadze odp. łuku

i dodając do każdego miejsca wyjściowego ilość

i dodając do każdego miejsca wyjściowego ilość

znaczników równą wadze odp. łuku.

znaczników równą wadze odp. łuku.

4

4

2

2

miejsca

miejsca

wejściowe

wejściowe

miejsca

miejsca

wyjściowe

wyjściowe

2

2

1

1

Sieci miejsc i przejść

Sieci miejsc i przejść

Sytuacje, w których przejście nie jest gotowe do odpalenia

Sytuacje, w których przejście nie jest gotowe do odpalenia

K = 2

K = 2

K = 3

K = 3

K = 2

K = 2

2

2

2

2

K = 3

K = 3

K = 4

K = 4

K = 3

K = 3

2

2

3

3

Sieci miejsc i przejść

Sieci miejsc i przejść

Sytuacje, w których przejście nie jest gotowe do odpalenia

Sytuacje, w których przejście nie jest gotowe do odpalenia

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

- bufor może zawierać co najwyżej pięć znaczników

- bufor może zawierać co najwyżej pięć znaczników

- producent generuje w każdym kroku trzy znaczniki

- producent generuje w każdym kroku trzy znaczniki

- co najwyżej jeden konsument ma w danej chwili dostęp

- co najwyżej jeden konsument ma w danej chwili dostęp

do bufora

do bufora

- podczas dostępu do bufora każdy konsument usuwa

- podczas dostępu do bufora każdy konsument usuwa

dwa znaczniki

dwa znaczniki

- kroki produkcji są zliczane

- kroki produkcji są zliczane

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent rozpoczyna

Producent rozpoczyna

działanie w stanie S1

działanie w stanie S1

Bufor

Bufor

Konsumenci rozpoczynają

Konsumenci rozpoczynają

działanie w stanie S6

działanie w stanie S6

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent wytwarza

Producent wytwarza

trzy znaczniki

trzy znaczniki

Bufor

Bufor

Jeden z konsumentów

Jeden z konsumentów

przechodzi na pocz. kolejki

przechodzi na pocz. kolejki

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent

Producent

przetwarza dane

przetwarza dane

Bufor

Bufor

Konsument w S7 może

Konsument w S7 może

pobrać dwa znaczniki

pobrać dwa znaczniki

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent

Producent

przetwarza dane

przetwarza dane

Bufor

Bufor

Konsument pobiera

Konsument pobiera

dwa znaczniki z bufora

dwa znaczniki z bufora

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent

Producent

przetwarza dane

przetwarza dane

Bufor

Bufor

Konsument przetwarza

Konsument przetwarza

dane znajdując się w S5

dane znajdując się w S5

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent

Producent

przetwarza dane

przetwarza dane

Bufor

Bufor

Drugi konsument przecho-

Drugi konsument przecho-

dzi na początek kolejki

dzi na początek kolejki

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent

Producent

przetwarza dane

przetwarza dane

Bufor

Bufor

Drugi konsument czeka

Drugi konsument czeka

na producenta

na producenta

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent kończy

Producent kończy

przetwarzanie danych

przetwarzanie danych

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Drugi konsument czeka

Drugi konsument czeka

na producenta

na producenta

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent może

Producent może

wytworzyć trzy znaczniki.

wytworzyć trzy znaczniki.

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Drugi konsument czeka

Drugi konsument czeka

na producenta

na producenta

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Drugi konsument czeka

Drugi konsument czeka

na producenta

na producenta

Producent wytwarza

Producent wytwarza

trzy znaczniki

trzy znaczniki

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent

Producent

przetwarza dane

przetwarza dane

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Drugi konsument może

Drugi konsument może

pobrać dwa znaczniki

pobrać dwa znaczniki

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Bufor

Bufor

Drugi konsument pobiera

Drugi konsument pobiera

dwa znaczniki z bufora

dwa znaczniki z bufora

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Producent

Producent

przetwarza dane

przetwarza dane

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Bufor

Bufor

Konsumenci

Konsumenci

przetwarzają dane

przetwarzają dane

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Producent

Producent

przetwarza dane

przetwarza dane

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent kończy

Producent kończy

przetwarzanie danych

przetwarzanie danych

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Konsumenci

Konsumenci

przetwarzają dane

przetwarzają dane

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Konsumenci

Konsumenci

przetwarzają dane

przetwarzają dane

Producent może

Producent może

wytworzyć trzy znaczniki.

wytworzyć trzy znaczniki.

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Jeden z konsumentów

Jeden z konsumentów

kończy przetwarzać dane

kończy przetwarzać dane

Producent wytwarza

Producent wytwarza

trzy znaczniki

trzy znaczniki

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Pierwszy konsument

Pierwszy konsument

przeszedł na koniec kolejki

przeszedł na koniec kolejki

Producent

Producent

przetwarza dane

przetwarza dane

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Konsumenci przesuwają

Konsumenci przesuwają

się w kolejce FIFO

się w kolejce FIFO

Producent kończy

Producent kończy

przetwarzanie danych

przetwarzanie danych

Przykład sieci miejsc i przejść:

Przykład sieci miejsc i przejść:

System złożony z producenta i dwóch konsumentów

System złożony z producenta i dwóch konsumentów

Producent

Producent

czeka na opróżnienie bufora

czeka na opróżnienie bufora

Bufor

Bufor

Licznik

Licznik

t

t

1

1

t

t

2

2

s

s

1

1

s

s

2

2

K=1

K=1

K=1

K=1

s

s

6

6

s

s

5

5

s

s

3

3

s

s

4

4

K=

K=





K=5

K=5

t

t

4

4

t

t

5

5

t

t

3

3

s

s

7

7

K=2

K=2

K=2

K=2

K=1

K=1

3

3

2

2

Konsument w S7 może

Konsument w S7 może

pobrać dwa znaczniki

pobrać dwa znaczniki

Żywotność sieci miejsc i przejść

Żywotność sieci miejsc i przejść

Istnieją różne kryteria żywotności sieci.

Istnieją różne kryteria żywotności sieci.

Znakowanie możemy nazwać żywym jeżeli:

Znakowanie możemy nazwać żywym jeżeli:

- dla każdego znakowania następniczego istnieje pewne

- dla każdego znakowania następniczego istnieje pewne

przejście aktywne (przygotowane do odpalenia),

przejście aktywne (przygotowane do odpalenia),

- każde przejście może czasami stawać się aktywne,

- każde przejście może czasami stawać się aktywne,

- przy każdym znakowaniu każde przejście może stać się

- przy każdym znakowaniu każde przejście może stać się

aktywne

aktywne

Sieć można nazwać żywą, jeżeli przyjmując dowolne z

Sieć można nazwać żywą, jeżeli przyjmując dowolne z

powyższych pojęć żywotności, możemy otrzymać

powyższych pojęć żywotności, możemy otrzymać

znakowanie żywe.

znakowanie żywe.

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść jest żywa

Ta sieć miejsc i przejść jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Ta sieć miejsc i przejść nie jest żywa

Ta sieć miejsc i przejść nie jest żywa

Pojemność znaczników każdego miejsca wynosi 1

Pojemność znaczników każdego miejsca wynosi 1

Czasowe sieci Petriego

Czasowe sieci Petriego

Czasową sieć Petriego możemy przedstawić jako zbiór

Czasową sieć Petriego możemy przedstawić jako zbiór

(P, T, B, F, H, M

(P, T, B, F, H, M

0

0

, SIM), gdzie:

, SIM), gdzie:

P = {p

P = {p

1

1

,...,p

,...,p

m

m

}

}

- zbiór miejsc,

- zbiór miejsc,

T = {t

T = {t

1

1

,...,t

,...,t

n

n

}

}

- zbiór przejść (z ang. tranzycji),

- zbiór przejść (z ang. tranzycji),

B: P

B: P





T

T





N

N

- funkcja wagi łuku (przypisująca łukowi liczbę)

- funkcja wagi łuku (przypisująca łukowi liczbę)

z miejsca do przejścia

z miejsca do przejścia

F: T

F: T





P

P





N

N

- funkcja wagi łuku z przejścia do miejsca

- funkcja wagi łuku z przejścia do miejsca

H: T

H: T





P

P





1

1

- funkcja wagi łuku hamującego

- funkcja wagi łuku hamującego

M

M

0

0

: P

: P





N

N

- funkcja inicjująca znakowanie początkowe

- funkcja inicjująca znakowanie początkowe

SIM: T

SIM: T





Q

Q

+

+





(Q

(Q

+

+









) jest funkcją przyporządkowującą

) jest funkcją przyporządkowującą

przejściu statyczny przedział czasu odpaleń. (Q

przejściu statyczny przedział czasu odpaleń. (Q

+

+

jest zbiorem

jest zbiorem

liczb rzeczywistych nieujemnych). Zatem do każdego

liczb rzeczywistych nieujemnych). Zatem do każdego

przejścia t

przejścia t

i

i

zostaną przypisane dwie liczby

zostaną przypisane dwie liczby

takie, że:

takie, że:

oraz

oraz

 









,

i

t

SIM

















0

,

0





,

Czasowe sieci Petriego

Czasowe sieci Petriego

Przejście t

Przejście t

i

i

jest przygotowane (ze względu na znakowanie)

jest przygotowane (ze względu na znakowanie)

do odpalenia wtw gdy spełnione są warunki:

do odpalenia wtw gdy spełnione są warunki:

 

















 









0

1

,

,













p

M

p

t

H

p

t

p

B

p

M

p

i

i

Zatem, wtedy gdy w każdym miejscu, z którego prowadzi łuk

Zatem, wtedy gdy w każdym miejscu, z którego prowadzi łuk

do przejścia t

do przejścia t

i

i

znajduje się co najmniej taka liczba znaczników

znajduje się co najmniej taka liczba znaczników

jaka jest waga łuku, oraz gdy w każdym miejscu,

jaka jest waga łuku, oraz gdy w każdym miejscu,

do którego prowadzi łuk hamujący, nie ma znaczników.

do którego prowadzi łuk hamujący, nie ma znaczników.

Czasowe sieci Petriego

Czasowe sieci Petriego

Przejście t

Przejście t

i

i

jest przygotowane (ze względu na czas)

jest przygotowane (ze względu na czas)

do odpalenia wtw gdy spełniony jest warunek:

do odpalenia wtw gdy spełniony jest warunek:

 

k

i

min











Odpalenie przejścia t

Odpalenie przejścia t

i

i

polega na usunięciu znaczników z

polega na usunięciu znaczników z

każdego miejsca, z którego prowadzi łuk do przejścia t

każdego miejsca, z którego prowadzi łuk do przejścia t

i

i

oraz na dodaniu znaczników do każdego miejsca, do którego

oraz na dodaniu znaczników do każdego miejsca, do którego

prowadzi łuk z przejścia t

prowadzi łuk z przejścia t

i

i

. Ilość usuniętych i dodanych

. Ilość usuniętych i dodanych

znaczników jest równa wadze łuku.

znaczników jest równa wadze łuku.

gdzie:

gdzie:





- względny czas odpalania,

- względny czas odpalania,

t

t

k

k

- przejście przygotowane do odpalenia ze względu na

- przejście przygotowane do odpalenia ze względu na

znakowanie

znakowanie

Przejście jest przygotowane do odpalenia, jeżeli jest

Przejście jest przygotowane do odpalenia, jeżeli jest

przygotowane do odpalenia ze względu na czas i znakowanie.

przygotowane do odpalenia ze względu na czas i znakowanie.

Specyfikacja i

projektowanie

oprogramowania czasu

rzeczywistego

wspomagane przez sieci

Petriego.

Specyfikacja i

projektowanie

oprogramowania czasu

rzeczywistego

wspomagane przez sieci

Petriego.

Paweł Witas

Paweł Witas

Dlaczego należy stosować metody formalne przy

Dlaczego należy stosować metody formalne przy

projektowaniu systemów czasu rzeczywistego ?

projektowaniu systemów czasu rzeczywistego ?

Testowanie i śledzenie wykonania („odpluskwianie”)

Testowanie i śledzenie wykonania („odpluskwianie”)

systemu czasu rzeczywistego jest trudne i czasochłonne.

systemu czasu rzeczywistego jest trudne i czasochłonne.

Awarie systemów czasu rzeczywistego są bardziej

Awarie systemów czasu rzeczywistego są bardziej

niebezpieczne i kosztowne, niż awarie innych systemów.

niebezpieczne i kosztowne, niż awarie innych systemów.

Zachodzi konieczność zapewnienia niezawodności systemu

Zachodzi konieczność zapewnienia niezawodności systemu

Niektóre sytuacje powodujące awarię:

Niektóre sytuacje powodujące awarię:

- niezachowanie kryteriów żywotności (zastój, zagłodzenie)

- niezachowanie kryteriów żywotności (zastój, zagłodzenie)

- przekroczenie maksymalnego czasu reakcji

- przekroczenie maksymalnego czasu reakcji

- brak reakcji na zaistniałe zdarzenie

- brak reakcji na zaistniałe zdarzenie

- usługa dostarczana przez system jest różna od wymaganej

- usługa dostarczana przez system jest różna od wymaganej

Analiza wymagań

Analiza wymagań

Specyfikacja

Specyfikacja

Projektowanie

Projektowanie

Programowanie

Programowanie

Integracja oprogramowania ze sprzętem

Integracja oprogramowania ze sprzętem

Testowanie modułów

Testowanie modułów

Testowanie systemu

Testowanie systemu

Ocena i akceptacja

Ocena i akceptacja

1

1

2

2

1 - Interakcja z klientem

1 - Interakcja z klientem

2 - Brak interakcji z klientem

2 - Brak interakcji z klientem

Fazy realizacji systemu czasu rzeczywistego

Fazy realizacji systemu czasu rzeczywistego

Wdrożenie systemu

Wdrożenie systemu

Analiza wymagań

Analiza wymagań

Analiza wymagań jest procesem iteracyjnym, który kończy

Analiza wymagań jest procesem iteracyjnym, który kończy

się sformułowaniem wymagań.

się sformułowaniem wymagań.

Niezrozumienie wymagań może prowadzić do utworzenia

Niezrozumienie wymagań może prowadzić do utworzenia

systemu innego niż wymagany przez klienta.

systemu innego niż wymagany przez klienta.

Analiza wymagań składa się z następujących etapów:

Analiza wymagań składa się z następujących etapów:

1. Analiza dziedzinowa polegająca na określeniu słownika

1. Analiza dziedzinowa polegająca na określeniu słownika

(pojęć używanych w dziedzinie (branży) klienta)

(pojęć używanych w dziedzinie (branży) klienta)

oraz

oraz

relacji między elementami słownika

relacji między elementami słownika

2.

2.

Zrozumienie i opis koncepcji operacyjnej łącznie z

Zrozumienie i opis koncepcji operacyjnej łącznie z

podaniem ograniczeń czasowych.

podaniem ograniczeń czasowych.

3. Sformułowanie wymagań w postaci dokumentu,

3. Sformułowanie wymagań w postaci dokumentu,

który jest zrozumiały dla klienta.

który jest zrozumiały dla klienta.

Etap 1: Analiza dziedzinowa

Etap 1: Analiza dziedzinowa

Pierwszy etap analizy wymagań polega na zrozumieniu

Pierwszy etap analizy wymagań polega na zrozumieniu

otoczenia i celu konstruowanego systemu. Tworzony jest

otoczenia i celu konstruowanego systemu. Tworzony jest

słownik ułatwiający zrozumienie terminologii używanej

słownik ułatwiający zrozumienie terminologii używanej

przez klienta. Słownik ten składa się zazwyczaj z szeregu

przez klienta. Słownik ten składa się zazwyczaj z szeregu

definicji opisanych z zastosowaniem języka naturalnego.

definicji opisanych z zastosowaniem języka naturalnego.

Podstawowe obiekty definiowane w słowniku są połączone

Podstawowe obiekty definiowane w słowniku są połączone

przez relacje.

przez relacje.

Charakter tych relacji zależy od stosowanego podejścia.

Charakter tych relacji zależy od stosowanego podejścia.

-

-

w podejściu strukturalnym używa się diagramów

w podejściu strukturalnym używa się diagramów

przepływu danych (DFD).

przepływu danych (DFD).

-

-

w podejściu obiektowym używa się diagramów związków

w podejściu obiektowym używa się diagramów związków

encji (ERD) opisujących relacje między danymi.

encji (ERD) opisujących relacje między danymi.

Etap 2:

Etap 2:

Zrozumienie i opis koncepcji operacyjnej

Zrozumienie i opis koncepcji operacyjnej

łącznie z podaniem ograniczeń czasowych

łącznie z podaniem ograniczeń czasowych

W pierwszym podetapie opisuje się zdarzenia i żądania

W pierwszym podetapie opisuje się zdarzenia i żądania

generowane przez otoczenie.

generowane przez otoczenie.

Jest to zazwyczaj realizowane w postaci

Jest to zazwyczaj realizowane w postaci

Tablicy Zdarzeń .

Tablicy Zdarzeń .

Nazwa

zdarzenia

Krótki opis

dotyczący

charakteru

zdarzenia

Źródło

(miejsce

generowania

zdarzenia)

Parametry

zdarzenia

Odpowiedź systemu

na dane zdarzenie

(żądanie)

Etap 2:

Etap 2:

Zrozumienie i opis koncepcji operacyjnej

Zrozumienie i opis koncepcji operacyjnej

łącznie z podaniem ograniczeń czasowych

łącznie z podaniem ograniczeń czasowych

Każda odpowiedź systemu ma podobną postać jak zdarzenie,

Każda odpowiedź systemu ma podobną postać jak zdarzenie,

stąd zbiór wszystkich odpowiedzi systemu może być

stąd zbiór wszystkich odpowiedzi systemu może być

zebrany również w postaci

zebrany również w postaci

Tablicy Odpowiedzi .

Tablicy Odpowiedzi .

Nazwa

odpowiedzi

Krótki opis

dotyczący

charakteru

odpowiedzi

Parametry

Adres przeznaczenia

Etap 2:

Etap 2:

Zrozumienie i opis koncepcji operacyjnej

Zrozumienie i opis koncepcji operacyjnej

łącznie z podaniem ograniczeń czasowych

łącznie z podaniem ograniczeń czasowych

W drugim podetapie statyczny opis z pierwszego podetapu

W drugim podetapie statyczny opis z pierwszego podetapu

uzupełnia się przez podanie scenariuszy opisujących

uzupełnia się przez podanie scenariuszy opisujących

interakcję między otoczeniem a systemem.

interakcję między otoczeniem a systemem.

System jest traktowany jako czarna skrzynka produkująca

System jest traktowany jako czarna skrzynka produkująca

odpowiedzi na zdarzenia występujące w otoczeniu.

odpowiedzi na zdarzenia występujące w otoczeniu.

Scenariusze są bliskie sekwencjom testującym używanym

Scenariusze są bliskie sekwencjom testującym używanym

fazie testowania systemu, gdzie bada się odpowiedzi

fazie testowania systemu, gdzie bada się odpowiedzi

(reakcje) systemu na generowane zdarzenia. Scenariusze

(reakcje) systemu na generowane zdarzenia. Scenariusze

mogą być więc wykorzystane przy planowaniu tych

mogą być więc wykorzystane przy planowaniu tych

sekwencji w fazie testowania systemu.

sekwencji w fazie testowania systemu.

Specyfikacja

Specyfikacja

Specyfikacja jest dokumentem, na podstawie którego

Specyfikacja jest dokumentem, na podstawie którego

wykonana będzie ocena i odbiór wykonanego systemu.

wykonana będzie ocena i odbiór wykonanego systemu.

Powinna ona bardzo precyzyjnie określać działanie

Powinna ona bardzo precyzyjnie określać działanie

tworzonego systemu wewnątrz globalnego systemu,

tworzonego systemu wewnątrz globalnego systemu,

oraz zawierać opis sekwencji testujących.

oraz zawierać opis sekwencji testujących.

Specyfikacja musi zostać zatwierdzona przez klienta

Specyfikacja musi zostać zatwierdzona przez klienta

przed rozpoczęciem projektowania. Faza specyfikacji jest

przed rozpoczęciem projektowania. Faza specyfikacji jest

niezwykle istotna, gdyż błędy w specyfikacji kosztują

niezwykle istotna, gdyż błędy w specyfikacji kosztują

niewspółmiernie dużo, jeśli zostaną wykryte dopiero w

niewspółmiernie dużo, jeśli zostaną wykryte dopiero w

następnych fazach realizacji.

następnych fazach realizacji.

Faza specyfikacji składa się zazwyczaj z dwóch etapów,

Faza specyfikacji składa się zazwyczaj z dwóch etapów,

gdzie w pierwszym etapie definiuje się interfejs między

gdzie w pierwszym etapie definiuje się interfejs między

systemem a otoczeniem, natomiast w drugim etapie

systemem a otoczeniem, natomiast w drugim etapie

opisywane jest zachowanie systemu.

opisywane jest zachowanie systemu.

Etap 1: Interfejs między systemem a otoczeniem

Etap 1: Interfejs między systemem a otoczeniem

Zdefiniowane w fazie analizy wymagań tablice zdarzeń

Zdefiniowane w fazie analizy wymagań tablice zdarzeń

i odpowiedzi są dobrymi danymi wejściowymi do opisu

i odpowiedzi są dobrymi danymi wejściowymi do opisu

interfejsu między systemem a otoczeniem.

interfejsu między systemem a otoczeniem.

Interfejs może być określony przez diagram składający się

Interfejs może być określony przez diagram składający się

z bloków specyfikujących moduły otoczenia (czujniki,

z bloków specyfikujących moduły otoczenia (czujniki,

przyciski, wyświetlacze, urządzenia wykonawcze) oraz

przyciski, wyświetlacze, urządzenia wykonawcze) oraz

ze strzałek łączących bloki.

ze strzałek łączących bloki.

Wyróżnia się strzałki pojedyncze

Wyróżnia się strzałki pojedyncze





reprezentujące przepływ

reprezentujące przepływ

sygnałów oraz podwójne

sygnałów oraz podwójne





specyfikujące przepływ danych.

specyfikujące przepływ danych.

Diagram ten może być uszczegółowiony przez informacje

Diagram ten może być uszczegółowiony przez informacje

zawarte w odpowiednich tablicach. Każdy wiersz tablicy

zawarte w odpowiednich tablicach. Każdy wiersz tablicy

opisuje wówczas jeden przepływ i jego atrybuty, np. źródło

opisuje wówczas jeden przepływ i jego atrybuty, np. źródło

i adres docelowy, typ danych (ciągłe, binarne,dyskretne

i adres docelowy, typ danych (ciągłe, binarne,dyskretne

o zadanym zakresie) i własności dynamiczne (czas życia).

o zadanym zakresie) i własności dynamiczne (czas życia).

Etap 2: Zachowanie systemu

Etap 2: Zachowanie systemu

W tym etapie specyfikacji definiuje się oczekiwane

W tym etapie specyfikacji definiuje się oczekiwane

zachowanie systemu przy pomocy czasowych sieci Petriego.

zachowanie systemu przy pomocy czasowych sieci Petriego.

część buforowa

część buforowa

akcja wykonana

akcja wykonana

przez system

przez system

(uproszczenie)

(uproszczenie)

obsługa

obsługa

sygnał z

sygnał z

otoczenia

otoczenia

bufor

bufor

K = 2

K = 2

K = n

K = n

K = 1

K = 1

K = 1

K = 1

K = 1

K = 1

Etap 2: Zachowanie systemu

Etap 2: Zachowanie systemu

W tym etapie specyfikacji definiuje się oczekiwane

W tym etapie specyfikacji definiuje się oczekiwane

zachowanie systemu przy pomocy czasowych sieci Petriego.

zachowanie systemu przy pomocy czasowych sieci Petriego.

część buforowa

część buforowa

akcja wykonana

akcja wykonana

przez system

przez system

(uproszczenie)

(uproszczenie)

sygnał z

sygnał z

otoczenia

otoczenia

obsługa

obsługa

bufor

bufor

K = 2

K = 2

K = n

K = n

K = 1

K = 1

K = 1

K = 1

K = 1

K = 1

Etap 2: Zachowanie systemu

Etap 2: Zachowanie systemu

W tym etapie specyfikacji definiuje się oczekiwane

W tym etapie specyfikacji definiuje się oczekiwane

zachowanie systemu przy pomocy czasowych sieci Petriego.

zachowanie systemu przy pomocy czasowych sieci Petriego.

część buforowa

część buforowa

akcja wykonana

akcja wykonana

przez system

przez system

(uproszczenie)

(uproszczenie)

sygnał z

sygnał z

otoczenia

otoczenia

obsługa

obsługa

bufor

bufor

K = 2

K = 2

K = n

K = n

K = 1

K = 1

K = 1

K = 1

K = 1

K = 1

Etap 2: Zachowanie systemu

Etap 2: Zachowanie systemu

W tym etapie specyfikacji definiuje się oczekiwane

W tym etapie specyfikacji definiuje się oczekiwane

zachowanie systemu przy pomocy czasowych sieci Petriego.

zachowanie systemu przy pomocy czasowych sieci Petriego.

część buforowa

część buforowa

akcja wykonana

akcja wykonana

przez system

przez system

(uproszczenie)

(uproszczenie)

obsługa

obsługa

sygnał z

sygnał z

otoczenia

otoczenia

bufor

bufor

K = 2

K = 2

K = n

K = n

K = 1

K = 1

K = 1

K = 1

K = 1

K = 1

Etap 2: Zachowanie systemu

Etap 2: Zachowanie systemu

W tym etapie specyfikacji definiuje się oczekiwane

W tym etapie specyfikacji definiuje się oczekiwane

zachowanie systemu przy pomocy czasowych sieci Petriego.

zachowanie systemu przy pomocy czasowych sieci Petriego.

część buforowa

część buforowa

akcja wykonana

akcja wykonana

przez system

przez system

(uproszczenie)

(uproszczenie)

obsługa

obsługa

sygnał z

sygnał z

otoczenia

otoczenia

bufor

bufor

K = 2

K = 2

K = n

K = n

K = 1

K = 1

K = 1

K = 1

K = 1

K = 1

Etap 2: Zachowanie systemu

Etap 2: Zachowanie systemu

W tym etapie specyfikacji definiuje się oczekiwane

W tym etapie specyfikacji definiuje się oczekiwane

zachowanie systemu przy pomocy czasowych sieci Petriego.

zachowanie systemu przy pomocy czasowych sieci Petriego.

część buforowa

część buforowa

akcja wykonana

akcja wykonana

przez system

przez system

(uproszczenie)

(uproszczenie)

obsługa

obsługa

sygnał z

sygnał z

otoczenia

otoczenia

bufor

bufor

K = 2

K = 2

K = n

K = n

K = 1

K = 1

K = 1

K = 1

K = 1

K = 1

Etap 2: Zachowanie systemu

Etap 2: Zachowanie systemu

W tym etapie specyfikacji definiuje się oczekiwane

W tym etapie specyfikacji definiuje się oczekiwane

zachowanie systemu przy pomocy czasowych sieci Petriego.

zachowanie systemu przy pomocy czasowych sieci Petriego.

część buforowa

część buforowa

akcja wykonana

akcja wykonana

przez system

przez system

(uproszczenie)

(uproszczenie)

obsługa

obsługa

sygnał z

sygnał z

otoczenia

otoczenia

bufor

bufor

K = 2

K = 2

K = n

K = n

K = 1

K = 1

K = 1

K = 1

K = 1

K = 1

Etap 2: Zachowanie systemu

Etap 2: Zachowanie systemu

W tym etapie specyfikacji definiuje się oczekiwane

W tym etapie specyfikacji definiuje się oczekiwane

zachowanie systemu przy pomocy czasowych sieci Petriego.

zachowanie systemu przy pomocy czasowych sieci Petriego.

część buforowa

część buforowa

akcja wykonana

akcja wykonana

przez system

przez system

(uproszczenie)

(uproszczenie)

obsługa

obsługa

sygnał z

sygnał z

otoczenia

otoczenia

bufor

bufor

K = 2

K = 2

K = n

K = n

K = 1

K = 1

K = 1

K = 1

K = 1

K = 1

Reguły dotyczące konstrukcji sieci Petriego

Reguły dotyczące konstrukcji sieci Petriego

opisującej

opisującej

zachowanie systemu:

zachowanie systemu:

1.

1.

Przypisz strzałkę wejściową do każdego przejścia,

Przypisz strzałkę wejściową do każdego przejścia,

którego wykonanie (firing) zależy od odpowiednich

którego wykonanie (firing) zależy od odpowiednich

sygnałów/danych generowanych przez otoczenie.

sygnałów/danych generowanych przez otoczenie.

2.

2.

Przypisz strzałkę wyjściową do każdego przejścia,

Przypisz strzałkę wyjściową do każdego przejścia,

którego wykonanie stanowi zakończenie akcji (obsługi)

którego wykonanie stanowi zakończenie akcji (obsługi)

oraz odpowiednie sygnały/dane są wysyłane do otoczenia.

oraz odpowiednie sygnały/dane są wysyłane do otoczenia.

3.

3.

Sprawdź, czy porządek akcji definiowany przez sieć

Sprawdź, czy porządek akcji definiowany przez sieć

Petriego jest zgodny z odpowiadającymi mu sekwencjami

Petriego jest zgodny z odpowiadającymi mu sekwencjami

określonymi w scenariuszach (w fazie analizy wymagań).

określonymi w scenariuszach (w fazie analizy wymagań).

4.

4.

Sprawdź zachowanie dostępności systemu dla sygnałów

Sprawdź zachowanie dostępności systemu dla sygnałów

wejściowych, gdy system jest zajęty przetwarzaniem danych.

wejściowych, gdy system jest zajęty przetwarzaniem danych.

5. Zweryfikuj kompletność sygnałów we/wy, które są użyte w

5. Zweryfikuj kompletność sygnałów we/wy, które są użyte w

sieci Petriego - porównaj z definicją interfejsu.

sieci Petriego - porównaj z definicją interfejsu.

6.

6.

Sprawdź kompletność akcji (obsług) opisanych przez sieć

Sprawdź kompletność akcji (obsług) opisanych przez sieć

Petriego w porównaniu do określonych w scenariuszach.

Petriego w porównaniu do określonych w scenariuszach.

Projektowanie wstępne

Projektowanie wstępne

Celem projektowania wstępnego jest podział systemu na

Celem projektowania wstępnego jest podział systemu na

zadania i zdefiniowanie interfejsu między zadaniami.

zadania i zdefiniowanie interfejsu między zadaniami.

Projektowanie wstępne może być traktowane jako przejście

Projektowanie wstępne może być traktowane jako przejście

od zewnętrznego opisu systemu (specyfikacja) do opisu

od zewnętrznego opisu systemu (specyfikacja) do opisu

uwzględniającego wewnętrzną współbieżność procesów.

uwzględniającego wewnętrzną współbieżność procesów.

Wynik podziału systemu na zadania może być zapisany

Wynik podziału systemu na zadania może być zapisany

w postaci diagramu, gdzie poszczególne bloki odpowiadają

w postaci diagramu, gdzie poszczególne bloki odpowiadają

zadaniom, pojedyncze strzałki opisują przepływ sygnałów

zadaniom, pojedyncze strzałki opisują przepływ sygnałów

synchronizacyjnych, a podwójne opisują przepływ danych.

synchronizacyjnych, a podwójne opisują przepływ danych.

Zestaw reguł podziału systemu na zadania:

Zestaw reguł podziału systemu na zadania:

1. Dla każdej pary zdarzeń (

1. Dla każdej pary zdarzeń (

zdarzenie_i

zdarzenie_i

,

,

zdarzenie_j

zdarzenie_j

) zbadaj,

) zbadaj,

czy odpowiadające im akcje powinny być realizowane w

czy odpowiadające im akcje powinny być realizowane w

porządku sekwencyjnym, czy współbieżnie. Jeżeli wymagane

porządku sekwencyjnym, czy współbieżnie. Jeżeli wymagane

jest, aby po obsłudze

jest, aby po obsłudze

zdarzenia_i

zdarzenia_i

obowiązkowo nastąpiła

obowiązkowo nastąpiła

obsługa

obsługa

zdarzenia_j

zdarzenia_j

, (lub odwrotnie), to obsługi tych zdarzeń

, (lub odwrotnie), to obsługi tych zdarzeń

powinny zostać zawarte w jednym zadaniu. W przeciwnym

powinny zostać zawarte w jednym zadaniu. W przeciwnym

wypadku (współbieżność) obsługi tych zdarzeń należy

wypadku (współbieżność) obsługi tych zdarzeń należy

umieścić w odrębnych zadaniach.

umieścić w odrębnych zadaniach.

2. Dla każdej pary (

2. Dla każdej pary (

zdarzenie_i

zdarzenie_i

,

,

akcja_j

akcja_j

) zbadaj, czy obsługa

) zbadaj, czy obsługa

zdarzenia_i implikuje sekwencyjne wykonanie

zdarzenia_i implikuje sekwencyjne wykonanie

akcji_j

akcji_j

.

.

Jeśli występuje taka sekwencyjna zależność, to obsługę

Jeśli występuje taka sekwencyjna zależność, to obsługę

zdarzenia_i

zdarzenia_i

oraz

oraz

akcję_j

akcję_j

należy umieścić w jednym zadaniu,

należy umieścić w jednym zadaniu,

w przeciwnym przypadku należy zdefiniować dwa zadania:

w przeciwnym przypadku należy zdefiniować dwa zadania:

jedno dla obsługi

jedno dla obsługi

zdarzenia_i

zdarzenia_i

, drugie dla obsługi

, drugie dla obsługi

akcji_j

akcji_j

.

.

Zestaw reguł podziału systemu na zadania:

Zestaw reguł podziału systemu na zadania:

3. Dla każdej pary (

3. Dla każdej pary (

akcja_i

akcja_i

,

,

akcja_j

akcja_j

) zbadaj, czy żądane jest

) zbadaj, czy żądane jest

ich sekwencyjne wykonanie. Jeśli tak, to należy je umieścić

ich sekwencyjne wykonanie. Jeśli tak, to należy je umieścić

w jednym zadaniu, w przeciwnym przypadku należy utworzyć

w jednym zadaniu, w przeciwnym przypadku należy utworzyć

dwa zadania: oddzielne dla

dwa zadania: oddzielne dla

akcji_i

akcji_i

oraz oddzielne dla

oraz oddzielne dla

akcji_j

akcji_j

.

.

Projektowanie szczegółowe

Projektowanie szczegółowe

Celem projektowania szczegółowego jest określenie

Celem projektowania szczegółowego jest określenie

struktury wewnętrznej każdego z zadań.

struktury wewnętrznej każdego z zadań.

Sieć Petriego jest konstruowana dla każdego zadania

Sieć Petriego jest konstruowana dla każdego zadania

określonego w etapie projektowania wstępnego.

określonego w etapie projektowania wstępnego.

Postępowanie jest tu podobne jak w przypadku specyfikacji,

Postępowanie jest tu podobne jak w przypadku specyfikacji,

ale przedmiot rozważań jest inny (dotyczy wewnętrznej

ale przedmiot rozważań jest inny (dotyczy wewnętrznej

struktury zadań). Projektowanie stanowi kolejny krok

struktury zadań). Projektowanie stanowi kolejny krok

w kierunku rozwiązania problemu, zatem struktura zadań

w kierunku rozwiązania problemu, zatem struktura zadań

powinna uwzględniać nie tylko zagadnienia synchronizacji

powinna uwzględniać nie tylko zagadnienia synchronizacji

i komunikacji, lecz również strukturę odpowiednich

i komunikacji, lecz również strukturę odpowiednich

algorytmów.

algorytmów.

Reguły dotyczące konstruowania sieci Petriego:

Reguły dotyczące konstruowania sieci Petriego:

1. Przypisz strzałkę wejściową do każdego przejścia,

1. Przypisz strzałkę wejściową do każdego przejścia,

którego wykonanie zależy od odebrania sygnału

którego wykonanie zależy od odebrania sygnału

synchronizacyjnego lub danych z innego zadania.

synchronizacyjnego lub danych z innego zadania.

2. Przypisz strzałkę wyjściową do każdego przejścia,

2. Przypisz strzałkę wyjściową do każdego przejścia,

którego wykonanie kończy realizację akcji/obsługi

którego wykonanie kończy realizację akcji/obsługi

i wysyła sygnał lub dane do innego zadania.

i wysyła sygnał lub dane do innego zadania.

3. Sprawdź kompletność przepływów wejściowych i

3. Sprawdź kompletność przepływów wejściowych i

wyjściowych w sieci Petriego względem odpowiednich

wyjściowych w sieci Petriego względem odpowiednich

przepływów opisanych w fazie projektowania wstępnego

przepływów opisanych w fazie projektowania wstępnego

Reguły dotyczące konstruowania sieci Petriego:

Reguły dotyczące konstruowania sieci Petriego:

4. Sprawdź dokładnie każdy przypadek, gdy zadanie

4. Sprawdź dokładnie każdy przypadek, gdy zadanie

oczekuje na sygnał lub dane z innego zadania i spróbuj

oczekuje na sygnał lub dane z innego zadania i spróbuj

stosować konstrukcję, która nie blokuje zadania

stosować konstrukcję, która nie blokuje zadania

oczekującego. Można uniknąć zawieszenia zadania przez

oczekującego. Można uniknąć zawieszenia zadania przez

przełączenie zadania na inny rodzaj działań.

przełączenie zadania na inny rodzaj działań.

żądanie

żądanie

obsługi

obsługi

obsługa

obsługa

dostarczona

dostarczona

żądanie

żądanie

obsługi

obsługi

obsługa

obsługa

zakończona

zakończona

Zadanie oczekujące na obsługę

Zadanie oczekujące na obsługę

Zadanie wykonujące obsługę

Zadanie wykonujące obsługę

Reguły dotyczące konstruowania sieci Petriego:

Reguły dotyczące konstruowania sieci Petriego:

5. Przeprowadź adaptację struktury zadania, tak aby

5. Przeprowadź adaptację struktury zadania, tak aby

uwzględnić elementy i konstrukcje docelowego języka

uwzględnić elementy i konstrukcje docelowego języka

programowania, np.. struktura loop-select when c

programowania, np.. struktura loop-select when c

i

i

=> accept e

=> accept e

i

i

dla języka Ada.

dla języka Ada.

. . .

. . .

e

e

1

1

e

e

2

2

e

e

n

n

c

c

1

1

c

c

2

2

c

c

n

n

Weryfikacja poprawności

Weryfikacja poprawności

Systematyczne uwzględnianie poprawności w każdym

Systematyczne uwzględnianie poprawności w każdym

kroku tworzenia oprogramowania, jest cechą charaktery-

kroku tworzenia oprogramowania, jest cechą charaktery-

styczną zaproponowanego podejścia.

styczną zaproponowanego podejścia.

Wyróżnia się dwa uzupełniające się sposoby postępowania:

Wyróżnia się dwa uzupełniające się sposoby postępowania:

•

Tworzenie systemu na podstawie opisu z faz poprzednich

Tworzenie systemu na podstawie opisu z faz poprzednich

z zastosowaniem reguł zapewniających spójność tworzenia.

z zastosowaniem reguł zapewniających spójność tworzenia.

•

Sprawdzanie poprawności jako odpowiedniości opisów

Sprawdzanie poprawności jako odpowiedniości opisów

w bieżącej fazie w porównaniu do poprzedniej.

w bieżącej fazie w porównaniu do poprzedniej.

Weryfikacja poprawności

Weryfikacja poprawności

Zastosowanie sieci Petriego umożliwia komputerowe

Zastosowanie sieci Petriego umożliwia komputerowe

wspomaganie analizy poprawności w fazie specyfikacji i

wspomaganie analizy poprawności w fazie specyfikacji i

projektowania systemu (przy pomocy edytora sieci Petriego,

projektowania systemu (przy pomocy edytora sieci Petriego,

wyposażonego w moduł do badania własności sieci).

wyposażonego w moduł do badania własności sieci).

1. W fazie specyfikacji możliwe jest sprawdzenie czy

1. W fazie specyfikacji możliwe jest sprawdzenie czy

specyfikacja została prawidłowo skonstruowana. Analiza

specyfikacja została prawidłowo skonstruowana. Analiza

dotyczy wówczas zarówno własności bezpieczeństwa,

dotyczy wówczas zarówno własności bezpieczeństwa,

tzn. sprawdzenia, czy niepożądane (złe) stany (blokada,

tzn. sprawdzenia, czy niepożądane (złe) stany (blokada,

zakleszczenie) nigdy nie wystąpią (dowód niewprost),

zakleszczenie) nigdy nie wystąpią (dowód niewprost),

jak również własności żywotności, polegającej na

jak również własności żywotności, polegającej na

sprawdzeniu, czy wybrane (dobre) stany (odpowiedź na

sprawdzeniu, czy wybrane (dobre) stany (odpowiedź na

zdarzenie, dostęp do zasobu) zostaną osiągnięte.

zdarzenie, dostęp do zasobu) zostaną osiągnięte.

Weryfikacja poprawności

Weryfikacja poprawności

2. W fazie projektowania analiza może być prowadzona

2. W fazie projektowania analiza może być prowadzona

dwoma sposobami:

dwoma sposobami:

•

Sprawdzenie, czy analogiczne własności, jak w przypadku

Sprawdzenie, czy analogiczne własności, jak w przypadku

specyfikacji są spełnione. Analiza ta dotyczy innego

specyfikacji są spełnione. Analiza ta dotyczy innego

opisu systemu tj. systemu reprezentowanego przez zbiór

opisu systemu tj. systemu reprezentowanego przez zbiór

współbieżnych zadań. Jest to związane z zachowaniem

współbieżnych zadań. Jest to związane z zachowaniem

spójności tworzonego systemu.

spójności tworzonego systemu.

•

Analiza nowych własności, wynikających z dokładniej-

Analiza nowych własności, wynikających z dokładniej-

szego opisu w danym etapie.

szego opisu w danym etapie.

Dotyczy to osiągalności ważniejszych ścieżek, stanów

Dotyczy to osiągalności ważniejszych ścieżek, stanów

i współpracy między zadaniami.

i współpracy między zadaniami.

Podsumowanie

Podsumowanie

Zastosowanie sieci Petriego umożliwia systematyczne

Zastosowanie sieci Petriego umożliwia systematyczne

rozwijanie systemu z uwzględnieniem analizy poprawności.

rozwijanie systemu z uwzględnieniem analizy poprawności.

Formalny charakter tego narzędzia czyni proces tworzenia

Formalny charakter tego narzędzia czyni proces tworzenia

oprogramowania bardziej deterministycznym i uporządkowa-

oprogramowania bardziej deterministycznym i uporządkowa-

nym. W szczególności istotnie zwiększyły się możliwości

nym. W szczególności istotnie zwiększyły się możliwości

systematycznej analizy poprawności i sterowania procesem

systematycznej analizy poprawności i sterowania procesem

wytwarzania oprogramowania.

wytwarzania oprogramowania.

Sieci Petriego są aktualnie coraz powszechniej stosowane

Sieci Petriego są aktualnie coraz powszechniej stosowane

jako narzędzie do opisu i analizy własności ze względu na

jako narzędzie do opisu i analizy własności ze względu na

następujące cechy:

następujące cechy:

•

przejrzysta i widoczna reprezentacja współbieżności;

przejrzysta i widoczna reprezentacja współbieżności;

•

możliwości hierarchizacji (sieci kolorowane);

możliwości hierarchizacji (sieci kolorowane);

•

komputerowe wspomaganie analizy własności;

komputerowe wspomaganie analizy własności;

•

wyrażanie czasu i zależności czasowych.

wyrażanie czasu i zależności czasowych.

Bibliografia

Gilles Motet, Tomasz Szmuc

Gilles Motet, Tomasz Szmuc

„

„

Specyfikacja i projektowanie oprogramowania czasu

Specyfikacja i projektowanie oprogramowania czasu

rzeczywistego wspomagane przez sieci Petriego”

rzeczywistego wspomagane przez sieci Petriego”

Wolfgang Reisig „Sieci Petriego”

Wolfgang Reisig „Sieci Petriego”