11강. Petri net (1)

11강. Petri net (1)

학습 목표

• 페트리 넷의 특성 파악

• 고전적 페트리 넷의 성질 이해

• 개요

- 1962 Carl Adam Petri에 의해 고안.

- Mathematical formalism에 근거: 모델링 뿐 아니라 분석 도구로도 사용.

- state/event-based

페트리넷 개요

• 페트리넷 특성

- Graphical and mathematical modeling tools developed to represent and analyze the behavior of concurrent and parallel systems.

- First proposed in Carl Adam Petri’s doctorial dissertation for the analysis of concurrent computer systems.

- Is based on a very simple, abstract representation of a system in terms of ‘bipartite directed graph’ made of two types of node and connected by directed arc.

* node:

~ place: represented by circle.

~ transition: represented by vertical bars * arc: directed arc.

페트리넷 특성(1)

• 페트리넷 예

arrives MC

waiting machining

leaves

(Conditions) a. m/c idle b. job waiting c. machining d. job complete

(Events)

1. Job arrives 2. m/c starts 3. m/c finishes 4. Job leaves

• Conditions -> Places

• Events -> transitions

• occurrence of an event -> firing of transition

• holding of a condition -> token

1 b

a c

3 d 4

2

페트리넷 특성(2)

페트리넷 특성(3)

• 페트리넷의 ‘플레이스’와 ‘트랜지션’의 해석

Input place transition Output place

Pre-condition event Post-condition

Input data Data processing Output data

Resource needed Task or job Resource released

• 구성요소

* Place: Passive component (buffer, phase, condition…)

* Transition: active component (an event, an operation, a transformation..) * Directed Arc: connection between a place and a transition

* Token: objects (physical ones, information)

claim record Under

consideration

Pay

Send

Letter for reject

ready place

transition

Directed arc token

< Claim treatment process>

고전적 페트리넷 (1)

• 입력, 출력 플레이스

p1 t1 p4

p2 p3

* Transition t1 has 3 input places: (p1,p2,p3)

* Transition t1 has 2 output places: (p3,p4)

고전적 페트리넷 (2)

• 페트리넷 상태

- indicated by the distribution of tokens over the places.

- state of below Petri Net:

µ=(claim, u_C, ready)=(3,0,0)

claim record Under

consideration Send letter

ready Pay

고전적 페트리넷 (3)

• Enabled

- a transition is enabled if each of the input places contains at least one token.

- 예: ‘record’ transition=enabled,

‘Pay’, ‘send letter’ transition=not enabled

claim record Under

consideration Send letter

ready Pay

고전적 페트리넷 (4)

11/19

• Firing

* firing corresponds to consuming tokens from the input places and producing tokens for the output places

.

고전적 페트리넷 (5)

• Firing 예

‘record’fires

claim record Under

consideration Send letter

ready Pay

State µ=(3,0,0)

claim record Under

consideration Send letter

ready Pay

State µ=(2,1,0)

고전적 페트리넷 (6)

• Non-determinism

t1

t2

* Two transitions fight for the same token: conflict

비결정성

• enabled/Firing 예

claim record Under

consideration Send letter

ready Pay

(2,1,0)

claim record Under

consideration Send letter

ready (2,0,1)

Pay

‘pay’ fires

페트리넷 실행 예

• 자원의 제약 고려

claim record Under

consideration

Send letter

ready pay

자원 제약 (1)

16/19

• 자원의 제약 고려

- 자원 가용도 토큰의 도입

claim record Under

consideration ready

free

claim record Under

consideration ready

free

‘Record’ fires!

자원제약 (2)

• 예제

A

고전적 페트리넷 예제

11강. Petri net (2) 학습 목표

• 도달성 트리 이해

• 고수준 페트리 넷의 특성 파악

• 페트리 넷 모델 예제 이해

• 도달성 트리 (reachability tree)

- 현재의 상태에서 특정한 상태로 전이가 가능한지를 분석하기 위해 ‘도달성 (reachability)’를 트리로 표현.

- 도달성: Given a Perti Net C with marking µ and a marking µ’, is µ’ ∈ R(C, µ) ?

- current state: the current configuration of tokens over the places - reachable state: a state reachable from the current state by firing a sequence of enabled transitions

- dead state: a state where no transition is enabled.

페트리넷 분석

• 10 reachabe states, 1 dead state

도달성 트리

claim

R(ecord)

Under

consideration

S(end) letter

ready P(ay)

(3,0,0) (2,1,0)

(1,2,0) (2,0,1)

(0,3,0) (1,1,1)

(0,2,1) (1,0,2)

(0,1,2) (0,0,3)

R

P/S

P/S

P/S

P/S

P/S R

R

R

R R

Dead state P/S

• 컬러 확장 (Color Extension)

- No distinction between tokens

-> color (value) assignment to tokens

[brand: ’BMW’; registration: ’J144NFX’; year:’ 1995’; color: ’red’]

- firing transition produce tokens which are based upon the values of those consumed during firing.

- the # of tokens produced is determined by the values of those consumed.

고수준 페트리넷-컬러(1)

• 예: 장비 고장 처리 프로세스

- during the execution of transition (e.g., ‘categorize’), a choice is made based upon the value of token.

repair

categorize solved

fault

test

replace nr

nt

고장현상: 고장위치: 고장파트: 고장이력:

Token value

고수준 페트리넷-컬러(2)

• 컬러 확장시 고려 사항.

(“categorize”: ‘fault’ place에 있는 token은 유효한 위치 코드가 있어야 함.) - firing에 있어서 각 output place에 생성될 token의 수, 생성될 token에 부여될 값: -> 소비하는 token의 값에 따라 결정된다.

고수준 페트리넷-컬러(3)

• 시간 확장 (time extension)

- 각 시스템의 performance 평가를 위해서는 duration이나 delay등을 표현 할 수 있어야 함.

* 각 token은 time stamp을 가짐. (token이 available한 시각) * 각 transition은 생성된 token의 delay(∆)를 결정한다.

고수준 페트리넷-시간(1)

waiting start busy finish completed free

1 3

9

0

∆=3 ∆=0

∆=0

(At time:0)

(At time:1)

waiting start busy finish completed free

4 3

9 ∆=3 ∆=0

∆=0

• timed Petri net 예

고수준 페트리넷-시간(2)

• 계층 확장 (hierarchical extension)

- a mechanism to structure complex Petri Nets comparable to IDEF0.

- Building Block: subnet (double-bordered square로 표현)

- Subnet is a net composed out of places, transitions and subnets.

고수준 페트리넷-계층(1)

• 계층적 페트리넷 예

repair

categorize solved

fault test

replace nr

nt

start

ntr

trace

nch

change ne

end

free

고수준 페트리넷-계층(2)

• Customer Order Processing- XOR split

Customer order received

Review customer Order detail

XOR

Customer order

accepted Customer order rejected

Check availability

Customer order received Review customer Order detail

Customer Order rejected Customer order

accepted Check availability

페트리넷 모델 예제(1)

• Customer Order Processing- AND split

Products Need to be

produced

AND

Purchase

material Make

Production plan

material

available plan available

Products Need to be produced

Purchase

material Make

Production plan

material available

plan available

페트리넷 모델 예제(2)

• Processing of Complaints

resister

Send_

questionnaire

evaluate

Process_

questionnaire time-out

Process_

complaint Check- processing archive

Processing _OK

Processing _NOT_OK No_processing

Processing_required start

end

Ready to Evaluate complaint

페트리넷 모델 예제(3)

• 도달성 트리

- 도달성: 현재의 상태에서 파이어링의 연속에 의해 특정한 상태에 도달 가능한가에 관한 특성.

- 도달성 트리: 현재 상태에서 발생 가능한 파이어링에 의해 전이 될 수 있는 모든 상태의 조합을 트리 상태로 표현 한 것.

- reachable state, dead state, live state 등 시스템의 구조를 분석 가능.

• 고수준 페트리넷의 확장 요소

- 시간 - 컬러 - 계층

학습 요약