Powtórka oparta na tokenach

odtwarzania oparta na tokenach to algorytm sprawdzania zgodności , który sprawdza, jak dobrze proces jest zgodny z jego modelem, odtwarzając każdy ślad w modelu (w notacji sieci Petriego ). Używając czterech żetonów wyprodukowanych, zużytych żetonów, brakujących żetonów i pozostałych żetonów, rejestruje sytuacje, w których przejście jest wymuszone odpaleniem, oraz pozostałe żetony po zakończeniu powtórki. Na podstawie zliczeń na każdym liczniku możemy obliczyć wartość dopasowania między śladem a modelem.

Algorytm

Technika token-replay wykorzystuje cztery liczniki do śledzenia śladu podczas odtwarzania:

$p$ : Wyprodukowane tokeny
$c$ : Zużyte żetony
$m$ : Brakujące żetony (zużyte pod nieobecność)
$r$ : Pozostałe żetony (wyprodukowane, ale nie zużyte)

niezmienniki:

w dowolnym momencie: ${\ Displaystyle p + m \ geq c \ geq m}$
na koniec: ${\ Displaystyle r = p + mc}$

Na początku tworzony jest token dla miejsca źródłowego (p = 1), a na końcu token jest konsumowany z miejsca ujścia (c' = c + 1). Po zakończeniu powtórki wartość sprawności można obliczyć w następujący sposób:

{\ Displaystyle {\ Frac {1} {2}} (1- {\ Frac {m} {c}}) + {\ Frac {1 }{2}}(1-{\frac {r}{p}})}

Przykład

następujący model procesu w notacji sieci Petriego :

Model procesu M z czynnościami a, b, c, d

Przykład 1: Odtwórz ślad ( $a, b, c, d$ ) na modelu M

Krok 1: Token jest inicjowany. Jest jeden wyprodukowany token ( ${\ displaystyle p = 1}$ ).

Krok 2: Czynność zużywa 1 żeton do wystrzelenia i produkuje 2 żetony ( ${\ displaystyle p = 1 + 2 = 3}$ displaystyle $mathbf$ $} styl wyświetlania c=1}$ ).

3: Działanie $p$ 1 token i produkuje 1 token ( ${\ Displaystyle p = 3 + 1 = 4}$ i do $\ Displaystyle c = 1 + 1 = 2}$ ).

$}$ 4: Działanie zużywa 1 żeton i wytwarza 1 żeton ( ${\ Displaystyle p = 4 + 1 = 5$ i $c=2+1=3$ ).
$}$ 5: Czynność zużywa 2 żetony i produkuje 1 żeton ( ${\ Displaystyle p = 5 + 1 = 6$ , $c=3+2=5$ ).

$:$ na miejscu końcowym jest Śledzenie jest zakończone.

Dopasowanie śladu ( ${\ Displaystyle \ mathbf {a, b, c, d}} )$ na modelu wynosi: ${\ Displaystyle \ mathbf {M}}$

{\ Displaystyle {\ Frac {1} {2}} (1 -{\frac {m}{c}})+{\frac {1}{2}}(1-{\frac {r}{p}})={\frac {1}{2}}(1 -{\frac {0}{6}})+{\frac {1}{2}}(1-{\frac {0}{6}})=1}

Przykład 2: Odtwórz ślad (a, b, d) na modelu M

Krok 1: Token jest inicjowany. Jest jeden wyprodukowany token ( ${\ displaystyle p = 1}$ ).

Krok 2: Czynność zużywa 1 żeton do wystrzelenia i produkuje 2 żetony ( ${\ displaystyle p = 1 + 2 = 3}$ displaystyle $mathbf$ $} styl wyświetlania c=1}$ ).

3: Działanie $p$ 1 token i produkuje 1 token ( ${\ Displaystyle p = 3 + 1 = 4}$ i do $\ Displaystyle c = 1 + 1 = 2}$ ).

Krok 4: Działanie $.$ zostać uruchomione, ale nie ma wystarczającej liczby tokenów Wyprodukowano jeden sztuczny token, a brakujący licznik żetonów zwiększono o jeden ( ${\ displaystyle m = 1}$ ). Sztuczny $_$ $token$ ) _ token jest tworzony na końcu miejsca ( ${\ displaystyle p = 4 + 1 = 5}$ ).
$Krok$ 5 : miejscu końcowym Śledzenie jest zakończone. Na $)$ pozostaje jeden żeton ( $r = 1$ \