[CS] 운영체제 - 병행제어 II

Deadlock and Starvation

• Deadlock
  • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 이벤트를 무한히 기다리는 현상
• Starvation
  • indefinite blocking
  • 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
• Classical Problems of Synchronization(전통적인 동기화 문제)
  • Bounded-Buffer Problem(공유 버퍼)
    • 생산자는 저장을 할때 미리 락을 걸고, 저장한 후에 락을 풀고 소비자는 사용 전에 락을 건다.
    • 락을 걸고 포인터를 조작해서 다음 버퍼를 가르킨다.

이미지 설명

• Readers-Writers Problem
  • 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안 된다.
  • Read는 동시에 가능
  • readCount 변수를 이용해서 양수일 때는 락이 걸려있어도 Read는 할 수 있도록 조정
  • readCount도 공유데이터이기 때문에 락을 걸어줘야 함
  • Starvation이 발생 가능
  • Reader가 계속 온다면 Writer는 계속 대기 상태가 될 수 있음
  • 시간 간격을 둬서 해결가능 (타이머)

코드 설명

 

Dining-Philosophers Problem

• 젓가락을 공유해서 밥을 먹어야 할 때 
• 무한 대기 상태가 없어야 한다.
• 4명의 철학자만 테이블에 앉게 하기
• 두 젓가락을 사용이 가능할 때만 젓가락을 사용하기
• 짝수 철학자는 왼쪽, 홀수는 오른쪽 젓가락부터 사용하도록

• 모니터를 이용해서 해결한 문제를 세마포어로 변경한 코드라서 참고만 하기
  • state를 lock하기 위해서 mutex변수 이용
  • 양 젓가락을 사용할 수 있으면 V()연산으로 젓가락 사용가능으로 권한 부여
  • 그리고 P()연산을 해서 권한을 확인 후 잠들거나 식사시작

 

Monitor

• 세마포어의 문제점
  • 코딩하기 힘듦
  • 정확성의 입증이 어려움
  • 자발적 협력이 필요
  • 한 번의 실수가 모든 시스템에 치명적 영향
• 세마포어의 문제를 해결하기 위해 모니터를 사용
  • 세마포어는 공유데이터를 관리하는 도움을 주지만 모니터는 모니터 안에 함수로만 공유데이터에 접근가능
  • condition 변수로 자원의 여부를 확인
  • 자원이 없으면 wait()함수로 큐에서 대기
  • 자원이 생기면 signal()로 대기 중인 작업 처리
  • 모니터는 락을 걸고 푸는 과정이 없음
  • 동기화 문제를 모니터가 관리해주기 때문

Bounded-Buffer Problem(공유 버퍼)

Dining-Philosophers Problem

데드락(교착 상태)

• 프로세스들이 서로가 가진 자원을 서로 기다리며 block 된 상태
• Resource(자원)
  • 하드웨어, 소프트웨어 등을 포함하는 개념

데드락 발생 조건

• Mutual exclusion(상호 배제)
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No preemption(비선점)
  • 프로세스에게 자원을 강제로 빼앗을 수 없음
• Hold and wait(보유 대기)
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 내놓지 않고 기다림
• Circular wit(환형 대기)
  • 자원을 기다리는 프로세스 간에 사이클리 형성되어야 함
  • 서로가 가진 자원을 내놓기를 기다림

 

자원할당그래프 (Resource-Allocation Graph)

그래프에 사이클이 없으면 데드락이 아님

데드락이 있는 그래프

데드락이 없는 그래프

데드락의 처리 방법

데드락을 예방하자!

Deadlock Prevention

• Mutual Exclusion
  • 공유해서는 안 되는 자원의 경우 반드시 성립
• Hold and Wait
  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 함
  • 프로세스 시작 시 모든 필요한 자원을 할당
    • 낭비
  • 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
• No Preemption
  • 자원을 강제로 빼앗음
  • 상태를 쉽게 저장하고 복구할 수 있는 자원에서 주로 사용
    • CPU, memory
• Circular Wait
  • 모든 자원 유형에 할당 순서를 정해서 정해진 순서대로 자원 할당
  • 비효율적
  • 이용률이 저하되고, starvation 문제도 발생

Deadlock Avoidance

• 추가적인 정보를 이용해서 데드락 방지
• 프로세스마다 최대로 사용할 자원의 정보를 미리 알고 있는 경우
• 싱글 인스턴스의 경우
  • 불안정한 상태라면 아예 자원 접근을 막는다
  • Resource Allocation Graph algorithm
    • 그래프가 점선일 경우 접근 막기
• 싱글 인스턴스가 아닐 경우
  • Banker`s Algorithm
    • 테이블을 만들어 각 프로세스의 현재 자원 요청량, 최대 요청량을 저장해 놓고, 최대 요청량이 가용자원량으로 처리가 불가능한 수준이면 자원 요청을 받아주지 않음
    • 자원의 여유가 있어도 불안정해질 가능성이 있다면 허용하지 않음

뭐 하러 걱정하냐! 사고 나면 수습하자!

 

Deadlock Detection and Recovery

• 여유자원이 있으면 무조건 허용하고, 문제가 발생하면 Detection 하고 Recovery 함
• 요청이 없는 프로세스들이 자원을 내놓는다고 예측하고 가용자원을 계산함
• 미리 차단하지 않아서 모든 자원을 사용가능
  • Recovery
    • Process temination
      • 프로세스를 모두 죽임
      • 하나씩 죽임
    • Resource Preemption
      • 비용을 최소화할 victim의 선정
      • safe state로 롤백 후 재시작
      • starvation 문제
        • 동일한 프로세스가 계속 victim으로 선정되면 같은 현상이 계속 일어나니 횟수를 잘 선정해야 함

Deadlock Ignorance

• Deadlock은 자주 일어나지 않는 현상이므로 무시한다
• 현대 운영체제에서 많이 차용 중
• Deadlock이 발생하면 이용자가 직접 처리