감 1도 없는 개발자

감 1도 없는 개발자

여행을 꿈꾸는 개발자

운영체제 - 06

Updated:

강의

http://www.kocw.net/home/search/kemView.do?kemId=1226304

운영체제 - 데드락

1. Deadlock

  • 교착상태 : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

2. 발생 조건

  • 아래 조건 하나라도 깨지만 데드락이 풀림

2.1 Mutual Exclusion(상호배제)

  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

2.2 No preemption(비선점)

  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

2.3 Hold and wait

  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
  • 비선점이랑 다른 점은 내가 가진 자원이 필요해서 내놓을 수가 없다는 의미

2.4 Circular wait (환영 대기)

  • 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

3. 자원할당 그래프 - 자원과 프로세스의 관계

  • R은 자원 P는 프로세스. R안에 점은 자원 안에 있는 인스턴스들을 의미
  • 프로세스가 자원의 인스턴스를 가르키는 화살표는 해당 자원의 인스턴스가 필요하다는 의미
  • 자원의 인스턴스가 프로세스를 가르키는 화살표는 프로세스가 이미 해당 자원을 가지고 있다는 의미

  • 왼쪽은 데드락
  • 오른쪽은 데드락이 아니지만 가능성은 있다.

4. 데드락 처리 방법

4.1 데드락 Prevention

  • 데드락 필요조건 4가지중 하나라도 만족하지 않게 하는 것
  • Utilization(이용률) 저하. throughput(처리량) 감소. starvation(낭비, 비효율적) 문제
4.1.1 Mutual Exclusion
  • 근데 이건 해결이 사실 상 안됨. 공유하는 걸 목표로 하는데 이걸 막는게 말이 안됌.
4.2 Hold and wait
  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 방법 1 : 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법. 이건 자원 낭비가 심함. 그때 그때 다름
  • 방법 2 : 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
4.3 No preemption
  • 자원을 기다려야 하는 경우 보유한 자원을 빼앗기게 한다.
  • 상태를 쉽게 변경하고 재설정할 수 있는 자원에서 주로 사용 (CPU, memory)
4.4 Circular wait
  • 모든 자원 유형에 할당 순서를 정해서 순서대로 자원 할당
  • 자원이 1,2,3이 있다면. 2번 자원을 얻기 위해선 1번 자원을 가지고 있는지 확인

4.2 데드락 Avoidance

  • 자원 요청에 대한 부가정보를 이용해서 자원 할당이 데드락으로부터 안전한지 동적으로 조사
  • 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

  • 실선은 이미 자원을 가지고 있거나 요청.

  • 점선을 자원을 요청할 상황이 발생할 수 있는 경우의 수

  • 마지막 상황의 경우 서클은 아니지만 그럴 수 있다고 예측
  • 그래서 P1에게 R2를 제공하지 않음
4.2.1 Banker’s 알고리즘

  • 위 그림 전체적인것은 아니고 프로세스에게 자원을 줄 것인가 말 것인가 판단하는 것만 말함

  • 자원 A,B,C는 최대 가지고 있는 자원이 10, 5, 7

  • P0의 경우 최대 자원 가질 경우가 7(A), 5(B), 3(C)인데 현재 가용자원은 3,3,2밖에 안되서 처음에는 할당 안해줌

  • P1의 경우 가능 하므로 할당. P1이 끝나면 할당 받은거와 기존에 가지고 있던 3,0,2 자원도 반납

  • 이런식으로 반복해서 그림의 아래 시퀀스(safe 시퀀스)대로 실행

4.3 데드락 Detection and Recovery

  • 데드락이 자주 생기는건 아님. 자원이 여유로운데 굳이 매번 확인하는 것도 오버헤드
  • 대신 주기적으로 검사하고 나서 다시 복구
4.3.1 Detection
  1. 자원당 single 인스턴스인 경우에서의 예제 : 자원할당 그래프에서 circle이 곧 데드락을 의미

  • 왼쪽은 데드락이 걸린 상황
  • 여기서 자원을 제거한 그래프를 그리면 오른쪽 처럼 그릴 수 있음.(데드락이 걸렸는지 빠르게 확인 가능) : Wait for graph 알고리즘
Wait for graph 알고리즘

  • 자원당 single 인스턴스인 경우

  • 자원 할당 그래프의 변형

  • 프로세스만으로 node 구성

  • Pi가 가지고 있는 자원을 Pk가 기다리는 경우 Pk->Pi

  • Wait for graph에 사이클이 존재하는지를 주기적으로 검사

  • O(n^2)

  1. 자원당 다중 인스턴스인 경우 : 백커스 알고리즘과 유사한 방법을 활용

  • 다른 점은 가용자원이 없으면 프로세스가 자원을 내놓음
  • 위의 상황은 데드락은 아님. 일부 프로세스가 자원을 내놓으면 모두 해결이 가능
  • 프로세스들이 자원을 내놓아도 해결이 불가능하면 데드락이 되어버림
4.3.2 Recovery

  1. process termination : 모두 죽이는 것 vs 하나씩 죽여보는 것

  2. Resource Preemption : 비용을 최소화할 희생자(프로세스)를 선정. 안전한 상태로 rollback하여 다시 restart.

    • 같은 희생자가 발생. starvation 문제

4.4 데드락 Ignorance

  • 데드락 자체가 드물다.
  • 이걸 해결 하는 거 자체가 그냥 낭비
  • 현대 범용 시스템들은 거의 이걸 채택…
  • 즉, 데드락이 고전적 문제. 점점 사라지는 문제임
  • 만약에 생기면? 그냥 사람이 프로세스 Kill

You may also enjoy