[OS] 라이브니스(Liveness) 문제 (데드락, 우선순위 역전) 정리

---

라이브니스(Liveness)

---

임계구역 접근을 위해 동기화 도구를 사용할 때 문제

• 임계구역에 들어가려고 시도하는 프로세스가 무기한 대기할 가능성이 생김
  • 무기한 대기는 진행 및 한정된 대기 2개의 기준을 위반한다.

 

---

라이브니스와 라이브니스 실패

• 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성
  • 무기한 대기하는 프로세스는 라이브니스 실패의 한 예시
    
    
• 다양한 형태의 라이브니스 실패 → 결과적으로 성능과 응답성이 나쁜 것이 특징
  • 예시
    • 무한 루프
    • 바쁜 대기 루프 → 라이브니스 실패의 가능성이 있음
      • 특히 프로세스가 임의로 오래 시간 동안 루프 돌고 있는 경우 가능성 높아짐
    • 도구를 통해 상호 배제를 제공하려는 노력이 병행 프로그래밍 환경에선 실패 가능성 존재
      • 도구를 통한 상호 배제 → Mute 락 및 세마포와 같은 동기화 도구

 

 

---

교착 상태(DeadLock)

• DeadLock(교착 상태)
  • 2개 이상의 프로세스들이, 대기 중인 프로세스들의 이벤트가 필요해서 무한정 대기하는 상황
    • 프로세스들의 이벤트 → signal() 연산의 실행을 의미
      
      
  • 한 집합 내의 모든 프로세스가 그 집합 내의 다른 프로세스의 이벤트를 기다릴 때 교착상태 발생
    • 여기서 말하는 이벤트 → mutex락과 세마포 같은 자원의 획득과 방출을 뜻함

 

---

2개의 프로세스로 이해하는 교착 상태(DeadLock)

• 가정
  • 2개의 프로세스 P0과 P1 되고, 이들이 1로 지정된 세마포 S와 Q에 접근한다.
  • P0이 wait(S)를 실행하고, P1이 wait(Q)를 실행한다고 가정
    
    
• 교착 상태(Dead Lock)
  • P0이 wait(Q)를 실행할 때, P0은 P1이 signal(Q)를 실행할 때까지 대기해야 함
  • P1이 wait(S)를 실행할 때는 P0이 signal(S)를 실행할 때까지 대기
    → 두 프로세스 다 signal() 연산이 실행될 수 없기 때문에 교착 상태(Dead Lock) 발생

 

 

---

우선순위 역전(Priority Inversion) - 라이브니스 문제

• 스케줄링의 어려움이 생기는 경우
  • 높은 우선순위 프로세스가 낮은 우선순위 프로세스가 접근하는 커널 데이터를 액세스 할 때
    • 커널 데이터 액세스하는 경우 → 커널 데이터를 읽거나 변경할 필요가 있을 경우
    • 왜?
      • 통상 커널 데이터는 낮은 우선순위 프로세스가 자원 사용이 끝날 때까지
        높은 우선순위 프로세스가 대기 ← 통상 커널 데이터는 락에 의해 보호되기 때문
        
        
    • 낮은 우선순위 프로세스가 높은 우선순위 프로세스에 의해 선점되는 경우엔 더 복잡함

 

---

예시를 통해 이해하기

• 가정
  • 우선순위가 L < M < H 순서인 3개의 프로세스가 존재한다.
  • 프로세스 H가 세마포 S를 필요로 하고, 세마포 S는 현재 프로세스 L에 의해 접근되는 상황
  • 이와 동시에 프로세스 M이 실행가능 상태가 되고, 따라서 프로세스 L을 선점한다고 가정
    • 대기하고 있던 프로세스 H 대신 M이 프로세스 L을 선점하게 됨

• 결론
  • 보통은 프로세스 L이 자원 사용을 마칠 때까지 프로세스 H가 대기
    → But, 우선순위가 상대적으로 낮은 프로세스 M이 H보다 먼저 프로세스 L을 선점
    
    
  • 간접적으로 낮은 우선순위 프로세스(M)는
    프로세스 H가 L이 자원을 양도할 때까지 기다려야 하는 시간에 영향을 주게 된다.
    
    → 이를 우선순위 역전 문제라고 함.
    • 라이브니스 문제에 해당하며, 셋 이상의 우선순위를 가진 시스템에서만 발생

 

---

우선순위 상속 프로토콜(Priority-inheritance protocol)

• 우선순위 역전 문제를 해결하는 방안 → 우선순위 상속 프로토콜을 구현하여 해결
• 더 높은 우선순위 프로세스가 요구하는 자원에 접근하는 모든 프로세스가 해당 프로토콜을 따름
  • 문제가 된 자원의 사용이 끝날 때까지 더 높은 우선순위를 상속받음
  • 자원 사용이 끝나면 원래 우선순위로 돌아감
    
    
• 우선순위 프로토콜 사용 예시(L < M < H 순서의 우선순위를 가진 경우 - 위의 예시)
  1. 프로세스 L이 임시로 프로세스 H의 우선순위를 상속받게 함
     → 따라서 프로세스 M이 L의 실행을 선점하는 것을 방지
     
     
  2. 프로세스 L이 해당 자원의 사용을 마치면, 원래의 우선순위로 돌아간다.
     
     
  3. 프로세스 L이 접근하던 자원이 가용 상태가 되었기 때문에 프로세스 H가 실행된다.