QNX RTOS: 5-8. Deadlock Avoidance

1. 왜 교착 상태(deadlock)가 생기는가?

가장 단순한 예:

• Process A → B로 MsgSend()
• 동시에 Process B → A로 MsgSend()

QNX에서 MsgSend()는:

1. 상대가 MsgReceive()로 받아줄 때까지 block
2. 그리고 상대가 MsgReply() 할 때까지 계속 block

인데,
A는 “내 메시지 받아줘” 하고 B를 기다리고,
B도 “내 메시지 받아줘” 하고 A를 기다리면:

둘 다 Receive를 안 하고 Send만 하고 있으니까
영원히 서로 기다리는 상태 = deadlock

QNX 커널은 일반적인 deadlock을 자동 탐지하지 않음.

• 이유: 이걸 OS 차원에서 일반적으로 잡으려면
  • 스레드 수가 N일 때 복잡도가 거의 N! 수준
  • 실시간 시스템에서 모든 blocking 연산마다 이런 탐지를 돌릴 수 없음
• 결론: 런타임 탐지가 아니라, 설계 단계에서 피해야 한다.

---

2. 교착을 피하는 기본 원칙: “누가 client이고, 누가 server인가?”

핵심 규칙은 딱 하나입니다:

“MsgSend()는 항상 client → server 방향으로만 간다.”
server는 client에게 메시지(MsgSend)를 보내지 않는다.

2.1 데이터 흐름을 이렇게 설계

1. client → server로 data를 보내는 경우
   • client: MsgSend()로 “데이터 여기 있습니다.”
   • server: 그 메시지를 MsgReceive()로 받아 처리
   • 처리 끝나면 MsgReply()로 “끝났습니다.” 응답
   • 여기서 blocking은 항상 “client가 server를 기다리는 방향” 뿐
2. server → client로 data를 보내고 싶은 경우 

• server가 직접 MsgSend()로 client에게 “데이터 줄게요” 하면:
  
  • server도 block
  • client도 뭔가 send 중이면 같이 막혀서 교착 가능성이 생김
• 그래서 이 방향은 반드시 non-blocking으로 처리해야 함 → 여기서 쓰는 게 pulse
  • server: MsgSendPulse() 로 client에게 “야, 데이터 준비됐다(wake up)” 신호만 보냄 (non-blocking)
  • client: pulse를 받으면 MsgSend()로 server에 “그 데이터 주세요”
  • server: 그 요청에 대해 MsgReply()로 실제 데이터 전달
• 이렇게 하면:
  
  • blocking을 동반하는 MsgSend()는 항상 client → server 방향이라
    서버가 client에게 blocking send를 걸 일이 없음 → 교착X

2.2 실무적으로는 어떻게 되냐?

• 많은 client 프로세스들도 channel을 하나씩 만들어 둠
  • 다른 server에게 쓰는 게 아니라,
  • 여러 server들로부터 pulse를 받는 용도로 쓰기도 함
• 즉, “데이터가 준비됨 → pulse → client가 send로 가져가는 구조”가
  교착 회피 + 이벤트 기반 구조를 동시에 만족하는 패턴

---

3. 복잡한 시스템에서의 deadlock 가능성: “cycle = 위험”

2개 프로세스만 있으면:

A ↔ B 양방향 MsgSend 가능 → 위험해 보인다는 걸 쉽게 느낌

근데 실제 시스템은:

• 8개, 20개, 50개, 100개 프로세스가 서로 메시지 주고받는 구조
• 여기서 “누가 누구한테 send 가능한지”를 방향 그래프로 그려보면:
  • 노드: 프로세스
  • 화살표: “여기에서 저기로 MsgSend() 할 수 있다”

교착 가능성이 있는 구조 = 그래프에 cycle(순환)이 존재할 때

예시:

• 1 → 4 → 6 → 7 → 2 → 1 같은 원형 경로
• 또는 1 → 4 → 6 → 3 → 7 → 2 → 1 같은 또 다른 cycle

이런 cycle이 있으면:

“서로 서로를 기다릴 수 있는 잠재적 구조”가 있음 → 설계 상 위험

7개만 있어도 cycle 찾기 힘든데,
50개 넘어가면 사람 눈으로는 거의 불가능.

---

4. 해결책: “Send Hierarchy (전송 계층 구조)” 만들기

그래서 제안하는 설계 원칙:

“모든 MsgSend()는 계층 구조에서 아래로만 간다 (down only)”

• 프로세스를 계층 구조(tree/forest)로 나열하고
• 위의 레벨 → 아래 레벨로만 MsgSend()
• 옆으로, 위로 MsgSend() 하지 않음

이렇게 설계하면:

• 그래프에 cycle이 절대 생길 수 없음 (DAG 구조)
  → deadlock 구조 자체가 원천 봉쇄

4.1 레벨 재배치로 문제 해결

어느 날 보니까:

• “Process 3과 4가 서로 통신 필요해졌다”

그런데 지금 계층도 상에서 같은 레벨에 있음(서로 수평 관계)

• 규칙상 수평/상향 MsgSend()는 금지이므로,
• 해결책:
  1. 한쪽을 위/아래 레벨로 옮길 수 있는지 먼저 검토
     • 예: 3을 위로 올려서 2 → 3 → 4 구조 만들기
     • 또는 4를 아래로 내려서 3 → 4 → 6 이런 구조 만들기
  2. 기존 연결이 깨지지 않는 선에서 이동이 안 되면,
     • 새 레벨을 하나 추가해서 중간에 끼워 넣기
     • 예: 2와 4 사이에 새로운 레벨 추가하고 거기에 3 배치
       • 2 → 3 → 4 형태로 변경

요점:
“가능하면 레벨 조정으로 cycle 없이 메시지 경로를 짜라”

4.2 그래도 위로 보내야 한다면? → non-blocking만 허용

예를 들어:

• Process 8이 Process 2로 “위 방향”으로 뭐라도 알려야 하는 경우
• 계층 구조상 8이 맨 아래, 2가 위에 있는 상태라서:
  • 8 → 2 MsgSend()는 규칙 위반 (위쪽 Send 금지)

이때 선택지:

“위/수평 방향으로는 MsgSend() 대신 non-blocking 메커니즘을 사용한다.”

예:

• Pulse (가장 대표적)
• Signal
• 세마포어 post
• 기타 non-blocking notification

즉, 위나 옆으로는 “알려주기만” 하고,
실제 데이터는 “그쪽에서 다시 아래 방향 MsgSend()로 가져가게” 설계하는 구조.

---

5. 보너스: 이 send hierarchy는 “Dependency + Startup Order” 정보도 준다

이 메시지 그래프(계층)는 단순 deadlock 회피뿐만 아니라:

“누가 누구에게 의존하는지(Dependency)”를 보여주는 구조이기도 함

예를 들어:

• 7이 8에게 MsgSend() 할 수 있다면
  • 7은 8에 의존함
  • 즉, 8이 먼저 살아 있어야 7이 정상 동작 가능
• 1이 4에, 4가 6에, 6이 8에 의존한다면:
  • “1을 빨리 띄우고 싶다”면 8→6→4→1 순서로 부팅하는 게 유리

또한:

• 아래 레벨:
  • 시스템 로그, 하드웨어 드라이버 등 low-level I/O, infrastructure
• 중간 레벨:
  • Middleware, 여러 입력을 모아서 가공하거나
    상위 명령을 쪼개어 하위 모듈에 배분하는 역할
• 최상위 레벨:
  • 사람과 인터페이스하는 UI, 최종 제어 로직
  • 예: “최종 go/no-go, 우회전/좌회전 결정” 같은 high-level 제어

그래서 이 계층 구조는:

1. Deadlock을 설계 단계에서 막는 도구
2. 시스템 의존성 / 부팅 순서 / 역할 분류를 한눈에 보여주는 설계도

역할이 동시에 있는 셈.

---

6. 정리 한 줄 요약

• MsgSend()는 항상 client → server (계층에서 위 → 아래)만 허용
• server가 client에게 뭔가 알릴 때는 pulse(또는 다른 non-blocking) 사용
• 전체 시스템을 send hierarchy(DAG)로 설계하면:
  • cycle이 없어 교착이 원천 봉쇄되고,
  • dependency와 startup order도 자연스럽게 드러난다.