상호 배제와 교착 상태, 세마포어 개념 정리

개요

• 운영체제의 **상호 배제(Mutual Exclusion)**와 교착(Deadlock) 현상에 대해 설명하고, 이를 해결하기 위한 **세마포어(Semaphore)**와 교착 회피(Deadlock Avoidance) 기법을 다룸.
• 데카(Dean), 데코(Deco) 알고리즘, 세마포어의 동작 원리, 그리고 교착 발생 조건과 예방·회피·복구 전략을 사례와 함께 풀이.

핵심 개념

상세 내용

1. 상호 배제와 데코 알고리즘

• 상호 배제: 공유 자원에 접근할 때 다른 프로세스가 접근하지 못하도록 막음.
• 데코(Deco):
  • 두 프로세스 P0, P1이 flag0, flag1 플래그를 사용.
  • enter: 플래그를 true로 세우고 상대 플래그가 false인지 검사.
    • 둘 다 true면 키(자원) 소유자를 확인해 대기.
  • leave: 플래그를 false로 내려 키를 반환.
• 문제점: CPU 사용률이 낮아지고, 무한 대기 가능성.

2. 세마포어

• 정의: 정수형 변수 s와 두 연산 P()(wait), V()(signal).
• P 연산:
  • s가 0이면 프로세스가 대기 큐(Q)에 들어가서 블록.
  • s > 0이면 s를 감소시키고 실행.
• V 연산:
  • s를 증가시키고, 대기 중인 프로세스가 있으면 한 명을 깨움.
• 세마포어 종류:
  • 이진 세마포어(Binary semaphore): 0과 1만 사용, 상호 배제용.
  • 카운트 세마포어(Count semaphore): 자원 개수만큼 s 초기화 가능, 다수 자원 제어.

3. 교착(Deadlock) 조건

4. 교착 예방(Deadlock Prevention)

• 상호 배제 제외: 불가능(필수 자원 보호 필요).
• 점유 및 대기 제외: P()를 호출할 때 필요한 모든 자원을 한 번에 요청.
• 비선택적 대기 제외: P()를 호출할 때 자원이 없으면 바로 반환.
• 순환 대기 제외: 자원에 번호를 부여하고, 프로세스는 항상 낮은 번호부터 높은 번호 순서로만 요청.

5. 교착 회피(Deadlock Avoidance)

• 안전 상태 정의: 현재 자원 할당 상태에서 모든 프로세스를 순서대로 끝낼 수 있는 실행 순서 존재.
• 시뮬레이션: 프로세스가 요청한 자원을 가정적으로 할당한 뒤, 시스템이 안전 상태인지 확인.
  • 안전 → 요청 허용
  • 불안전 → 요청 거절
• 대표 알고리즘:
  • 헌스(Heaps): 모든 자원을 한 번에 할당하고, 가능 여부를 검사.
  • 마커스(Marques): 각 프로세스의 최대 요구량과 현재 할당량을 비교해 안정성 판단.

6. 세마포어와 교착 회피의 결합

• 세마포어를 이용해 자원 할당을 제어하면서, P() 호출 시 가상의 할당에 대해 안전성 검사를 수행.
• 가상 할당이 안전하면 실제 P()를 실행; 아니면 P()가 블록되거나 요청이 거절됨.

7. 실전 예시

• 자원 할당 그래프: 프로세스 노드와 자원 노드, 요청(→)과 할당(←) 엣지로 구성.
• 사이클: 그래프에 순환이 있으면 교착 가능성 존재.
  • 단, 다중 자원(예: 2개의 프린터)인 경우 사이클이 있어도 교착이 아닐 수 있음.
• 안전 순서: 예시에서 P4 → P1 → P3 순으로 실행하면 모든 프로세스가 종료 → 안정 상태.

8. 교착 회피의 한계

• CPU 오버헤드: 매 요청마다 안전성 검사를 수행해야 함.
• 복잡성 증가: 다중 자원 유형, 다수 프로세스 상황에서 계산 복잡도 상승.
• 자원 효율 저하: 안전성을 확보하기 위해 과도한 자원 예약이 필요할 수 있음.

---

핵심 요약
상호 배제는 필수이지만 무제한 대기와 CPU 차단을 초래할 수 있다. 세마포어는 이진/카운트 형태로 구현되어 임계 영역 접근을 제어하고, P()와 V() 연산으로 동기화한다. 교착은 네 가지 조건이 동시에 충족될 때 발생하며, 예방, 회피, 복구 전략이 존재한다. 회피 기법은 안전 상태를 유지하려는 시뮬레이션 기반 접근이며, 자원 할당 그래프와 안전 순서 분석이 핵심이다.