[OS] 페트리 넷(Petri Net) 4가지 핵심 속성 - 그림으로 판별하기

페트리 넷의 4가지 속성을 그래프와 구조로 판별하는 완벽 가이드! “토큰이 폭발하나?”, “멈추나?”, “영원히 살아있나?”, “굶어 죽나?”를 보는 싸움입니다.

---

0️⃣ 페트리 넷의 4가지 속성 개요

페트리 넷을 분석할 때 체크해야 할 4가지 핵심 속성이 있습니다. 모두 Coffman Conditions와는 다른 차원의 분석입니다.

속성	독일어	핵심 질문	레벨
한정성	Beschränktheit	토큰이 폭발하는가?	기본
무교착성	Verklemmungsfreiheit	완전히 멈추는가?	중요
활성	Lebendigkeit	모든 기능이 살아있나?	고급
공정성	Fairness	굶어 죽는 놈이 있나?	고급

---

1️⃣ 한정성 (Beschränktheit)

🤔 “토큰 개수가 무한히 늘어나지 않는가?”

의미: 어떤 상태에서도 모든 Place의 토큰 개수가 특정 숫자 $k$를 넘지 않습니다.

수학적 정의: 페트리 넷이 $k$-한정(bounded)이면, 어떤 도달 가능 상태 $m$에서도 모든 place $p$에 대해 $m(p) \leq k$입니다.

👁️ 그래프로 판별하기

도달성 그래프(Reachability Graph)를 그리면서 다음을 확인합니다:

• $\omega$ (오메가)가 나타난다? → 비한정(Unbeschränkt)
• 어떤 place의 토큰 개수가 계속 증가하는 상태가 있다? → 비한정

예시:

초기 상태: (1, 0, 0)
t1 발화: (0, 1, 1)
t2 발화: (0, 0, 2)
t3 발화: (0, 0, 3)
...

토큰이 계속 쌓이면 \(m_3 = (0, 0, \omega)\) 로 표기하고, 이는 비한정입니다.

🔧 구조로 판별하기

구조를 보면 바로 판단할 수 있습니다:

① 토큰 복사기 (Source-to-Sink)

입력보다 출력이 많은 루프가 있는가?

• 하나의 Place에서 나가는 화살표가 여러 개 → 하나 집었는데 여러 개 쏟아낸다?
• 특히 루프(피드백) 구조에서 이렇게 되면 폭발입니다.

② 소스(Source) Transition

아무 조건 없이 토큰을 뿜어내는 Transition이 있는가?

• 입력 화살표가 없는데 출력만 있는 Transition
• 예: 제너레이터, 스트림 source 등
• 이 Transition이 계속 발화하면 → 비한정

📋 판결 체크리스트

• 도달성 그래프에 $\omega$가 있는가? → 비한정(Unbeschränkt)
• 출력이 입력보다 많은 루프가 있는가? → 비한정
• 입력이 없는 Transition이 계속 발화하는가? → 비한정
• 위의 모든 경우가 없다? → 한정(Beschränkt) ✅

💡 팁: 대부분의 시스템 설계(특히 생산자-소비자)에서는 한정성이 필수입니다. 무한정으로 메모리가 쌓일 수는 없으니까요!

---

2️⃣ 무교착성 (Verklemmungsfreiheit)

🚨 “시스템이 완전히 멈추는 일이 없는가?”

의미: 어떤 상태에서 도달하더라도, 최소한 하나 이상의 Transition은 실행(Fire) 가능해야 합니다.

수학적 정의: 페트리 넷이 교착 상태(Deadlock)가 없으려면, 도달 가능한 모든 상태 $m$에 대해 최소 하나의 Transition $t$가 $m$에서 활성화되어야 합니다.

👁️ 그래프로 판별하기

도달성 그래프에서 다음을 확인합니다:

도달성 그래프
초기 → m1 → m2 → m3
              ↓
             m4 (화살표 끝!)

• 화살표가 나가지 않는 노드(Terminal Node)가 있는가? → 데드락(Verklemmung)
• 모든 노드에서 최소 하나의 화살표가 나간다? → 무교착(Verklemmungsfrei) ✅

예시 - 데드락 있음:

상태 m3: (0, 0)
어떤 Transition도 발화할 수 없음
→ 화살표가 없음 → 데드락!

예시 - 데드락 없음:

상태 m1: (1, 1) → t1 발화 가능 → m2로 이동
상태 m2: (0, 2) → t2 발화 가능 → m3로 이동
...
모든 상태에서 최소 하나는 발화 가능 → 안전!

🔧 구조로 판별하기

구조를 보면서 다음을 확인합니다:

① Coffman Conditions 재확인

4가지 조건 중 하나라도 깨졌는가?

• 예: 페트리 넷의 “All-or-Nothing” 규칙으로 점유 대기 깨짐
• → 데드락 안 생김

② 원형 대기 구조

Resource R1 ← Process A ← Resource R2 ← Process B ← Resource R1

원형 고리가 있는가? 있으면 위험합니다.

③ 특이한 분기 (Split) 없는가?

한 Place에서 여러 Transition으로 분기되는데,
그 중 일부는 돌아오지 않는 경로로 빠진다?

📋 판결 체크리스트

• 도달성 그래프에 막다른 노드(출력 화살표 없음)가 있는가? → 교착(Verklemmung)
• 모든 노드에서 최소 하나의 화살표가 나가는가? → 무교착(Verklemmungsfrei) ✅

⚠️ 중요: “뱅글뱅글 도는 루프에 갇혀있다”는 것은 데드락이 아닙니다! Transition이 발화 가능하니까요. (다만 다른 곳으로는 못 간다는 뜻입니다.)

---

3️⃣ 활성 (Lebendigkeit)

💪 “모든 기능이 영원히 살아있는가?”

의미: 어떤 상태에 도달하더라도, 모든 Transition이 언젠가는 다시 발화될 기회가 있어야 합니다.

이건 무교착성보다 훨씬 엄격한 조건입니다.

수학적 정의: 페트리 넷이 활성(Live)이려면, 모든 Transition $t$와 도달 가능한 상태 $m$에 대해, $m$에서 $t$를 발화 가능한 상태 $m’$이 존재해야 합니다.

👁️ 그래프로 판별하기

도달성 그래프에서 다음을 확인합니다:

초기 상태 m0 → m1 → m2 → m3 → m4
                     ↓
              (m2로 돌아올 수 없음)

• 특정 상태에 도달하면 초기 상태로 못 돌아오는 경로가 있는가? → 비활성(Not live)
• 모든 Transition에 대해 계속 발화할 기회가 있는가? → 활성(Live) ✅

활성 판별의 핵심: 도달성 그래프가 강하게 연결(Strongly Connected)되어 있는가?

• 강하게 연결: 어디서든 어디든 갈 수 있는 그래프
• 약하게 연결: 일방통행이 있는 그래프 → 비활성!

🔧 구조로 판별하기

① 원형 구조 확인

페트리 넷이 순환 구조를 가지는가?
t1 → t2 → t3 → t1 (뱅글뱅글 도는가?)

② 막다른 경로(Dead Code)가 있는가?

어떤 Transition으로 가는 길이 있지만,
그 Transition에서는 나갈 수 없는 경로?

예시 - 활성 없음:

초기: Place A에 토큰 있음
t1 발화: A → B로 토큰 이동
이제 A는 영영 빈 상태
t1은 다시 발화할 기회가 없음 → 비활성!

예시 - 활성 있음:

t1: A → B
t2: B → A  (피드백!)
→ 둘이 뱅글뱅글 돈다
→ 둘 다 영원히 발화 기회가 있음 → 활성!

📋 판결 체크리스트

• 도달성 그래프가 강하게 연결되어 있는가? → 활성(Live) ✅
• 특정 구역으로 가면 초기 상태로 못 돌아오는가? → 비활성(Not live)
• 어떤 Transition이 영원히 발화 안 될 가능성이 있는가? → 비활성

💡 팁: 페트리 넷이 활성이면, 시스템이 무한정 돌아가므로 리소스 누수(메모리, 연결 등)가 없어야 합니다. 활성은 매우 강력한 보장입니다!

---

4️⃣ 공정성 (Fairness)

😢 “굶어 죽는 놈(Starvation)이 없는가?”

의미: 어떤 Transition이 실행될 조건(토큰)이 충분히 자주 주어지면, 결국에는 실행되어야 한다. (계속 무시당하면 안 됨)

수학적 정의: Transition $t$가 공정(fair)이려면, $t$가 무한번 활성화되는 어떤 경로에서, $t$도 무한번 발화되어야 합니다.

👁️ 그래프로 판별하기

도달성 그래프에서 다음을 확인합니다:

상태 m에서:
t1과 t2가 동시에 활성화 가능
↓
t1만 계속 발화되고, t2는 영원히 무시당함?
→ t2가 굶어 죽음(Starvation)

공정성 분석:

• 도달성 그래프에서 “경쟁(Conflict)” 상황을 찾습니다.
• 경쟁: 하나의 Place에서 여러 Transition으로 화살표가 나갈 때

Place P → Transition t1
       ↘ Transition t2

"t1이 나가는 화살표에만 토큰이 쏠려서 t2는 영원히 기다린다"
이런 경우를 피할 수 있는가?

🔧 구조로 판별하기

① 경쟁(Conflict) 찾기

한 Place에서 두 Transition으로 나간다?
P → t1
P → t2

이때 운 나쁘게 t1만 계속 선택되면
t2는 굶어 죽을 수 있음!

② 중재(Arbiter) 기구가 있는가?

경쟁을 해결하는 메커니즘이 있는가?
- 추가 토큰으로 순서를 강제?
- "t1 → t2" 식의 순서 정하기?
→ 있으면 공정성 강화!

구조적 공정성:

• 무조건적 공정성(Unconditional Fairness): 구조상 전혀 경쟁이 없음
• 약한 공정성(Weak Fairness): 경쟁이 있지만, 조정 메커니즘이 있음
• 강한 공정성(Strong Fairness): 최악의 상황(adversarial scheduling)에서도 공정함

📋 판결 체크리스트

• 경쟁 상황(하나의 Place → 여러 Transition)이 있는가? → 잠재적 불공정
• 경쟁을 조정하는 토큰/규칙이 있는가? → 공정성 강화 ✅
• 구조상 경쟁이 전혀 없는가? → 무조건적 공정(Fair) ✅✅

💡 팁: 공정성은 실제 스케줄러(Scheduler) 구현에 달려있을 수도 있습니다. 페트리 넷 구조만으로는 판단 못 할 수도 있으니 문제에서 명시해줄 때까지 기다리세요!

---

📊 한눈에 보는 판별 체크리스트

속성	독일어	그래프 판별	구조 판별	핵심
한정성	Beschränkt	$\omega$ 없음	토큰 폭발 없음	메모리 폭발?
무교착	Verklemmungsfrei	막다른 노드 없음	Coffman 깨짐	완전히 멈춤?
활성	Lebendig	강한 연결	순환 구조	영원히 죽은 코드?
공정성	Fair	경쟁 조정	중재 기구	굶어 죽는 놈?

---

🚀 실전 예제

문제: 다음 페트리 넷을 분석하세요

구조:
P1 --t1--> P2 --t2--> P3
 ↑                    |
 └────────t3──────────┘

초기 상태: m0 = (1, 0, 0)

분석:

1. 한정성?
   • 도달성 그래프: $(1,0,0) → (0,1,0) → (0,0,1) → (1,0,0) → \cdots$
   • 토큰은 계속 1개만 순환 → 한정(Beschränkt) ✅
2. 무교착?
   • 모든 상태에서 다음 Transition이 발화 가능 → 무교착(Verklemmungsfrei) ✅
3. 활성?
   • 도달성 그래프가 순환 구조 → 모든 Transition이 무한 발화 기회 → 활성(Lebendig) ✅
4. 공정성?
   • 경쟁 상황이 없음 (일렬로 순환) → 무조건적 공정(Fair) ✅✅

결론: 이 페트리 넷은 모든 조건을 만족하는 이상적인 시스템입니다!

---

📚 4가지 속성의 포함 관계

\[\text{Live} \subset \text{Deadlock-free} \subset \text{All states}\]

• 활성(Live) → 항상 무교착(Deadlock-free)
• 무교착(Deadlock-free) → 항상 상태 존재
• 반대 방향은 성립하지 않음

즉, 조건의 강함 순서:

1. 활성(Live) - 가장 엄격 (영원히 모든 기능 살아있음)
2. 무교착(Deadlock-free) - 중간 (최소한 일부 기능은 작동)
3. 한정성(Bounded) - 기본 (메모리 안정성)

---

🎓 최종 정리

질문	판별 방법	핵심 개념
“토큰이 폭발하나?”	$\omega$ 확인	메모리 유한성
“멈춰 있나?”	막다른 노드	Deadlock 없음
“영원히 살아있나?”	강한 연결성	모든 기능 활동
“왕따 당하나?”	경쟁 조정	모든 Transition 발화

이 4가지만 체크하면 어떤 페트리 넷 문제도 완벽 분석이 가능합니다! 🎯

시험 꿀팁: 도달성 그래프를 먼저 그려보고, 위 체크리스트를 하나씩 확인하세요. 99%의 경우 정답을 찾을 수 있습니다!