CS/OS

[OS] Deadlocks (2) - 교착상태

JWonK 2023. 5. 16. 16:03
728x90
반응형

 

 

 

 

  • 사용하는 변수는 4가지
    • Available : 여유분
    • Max : 최대 필요한 자원의 개수
    • Allocation : 할당된 자원의 개수
    • Need : 앞으로 추가적으로 필요한 자원의 개수 
  • 2차원 matrix형태로 모두 존재
  • 앞으로 필요한 자원의 개수는 최대치에서 이미 할당된 자원을 빼준 정도

 

 

 

 



  • 어느 한 순간 Safety한 상태인지 체크
  • 여러 개의 process가 존재할 때 안정적으로 처리할 수 있는 순서도가 있는가 확인
  1. fisnish가 false인 것 중
  2. need(i)가 work보다 작거나 같은 것을 찾는다
  3. 만약 존재하지 않는다면 6단계로
  4. Need는 필요한 만큼 줬다가 다시 회수, 여유분이 늘어나는 것은 이미 할당된 것들 회수
  5. Finish[i]를 True로 전환하고 다시 2단계로
  6. 만약 모든 프로세스가 Finish[i]가 True라면 시스템은 Safe State이다.
  7. Safe State가 아니라면 Deadlock에 관여하는 Process

 

 

 

  • Process : 5, Resouce : 3(A, B, C)
  • 어느 한 순간 확인한 것 빨간 테두리
  • Allocation, Max, Available 상태 확인
  • 실질적으로 필요한 건 Need 정보 (추가적으로 필요한 자원) -> Max - Allocation
  • 모든 Process가 처리될 수 있는 순서가 존재할 때만 Safe State

 

 

  • 자원 요청 알고리즘
  • 자원을 줘도 시스템이 Safe하여 상관 없는지 아닌지 확인하는 알고리즘

 

  1. 요청 자원이 필요한 양보다 작을 때 (2단계로 이동)
  2. 지금 요청하는 자원의 수가 Available에 만족하는지 (3단계로 이동)
  3. Pretend(가정) : 자원을 주었다고 가정하면 자원 단계 변수 값들이 변경된 값들로 확인
    1. 줬다고 가정하여 Available, Allocation, Need값 업데이트
  4. Safety Algorithm 돌려서 확인
  5. Safe State에 만족하면 자원을 실제로 할당시켜준다.

 

 

 

  • P[1]이 (1, 0, 2) 요청
  • Check를 통해 1, 2단계 통과 → 가정 단계 돌입

 

 

 

 

  • Detection Alogorithm : Deadlock상태에 빠진 것을 감지하고 탈출

 

  • 인스턴스가 단일일 때, 여러 개일때
  • 단일일 경우 (= Wait-for graph)
  • 프로세스 사이 관계만 표시, 항상 화살표로 프로세스 사이만 나타냄
  • 주기적으로 계속 체크하고 Cycle 여부를 확인하는 것은 Overhead가 큼

 

 

  • 인스턴스 개수가 한 개일 때 상황
  • 왼쪽 Resource-Allocation Graph로 Wait-for Graph를 그려준다.
  • Graph를 바탕으로 Cycle 여부를 확인하고 Deadlock 여부를 판단한다.

 

 

  • Available : 여유분의 개수
  • Allocation : n x m matrix 자원 할당 개수
  • Request : 요청 개수

 

 

  1. 여유분을 work라는 변수로 넘겨줌
    1. allocation이 0인지 확인, 0이 아니면 할당된 자원이 존재 -> 아직 끝나지 않고 자원 소유  : Finish[i] = False
    2. 0이라면 갖고 있는 자원이 존재하지 않음 : Finish[i] = True
  2. 끝나지 않은 것 중 Work보다 작은 값을 요청

 3. Work 값을 Allocation만큼 할당했다고 가정한 후 2단계로 거슬러 올라감

 4. 만약 Finish[i]가 False인 값이 존재하면 System은 Deadlock state

 

위 과정을 반복해서 진행하면 Overhead가 커지게 됨

 

 

  • p[0]는 request도 (0,0,0)이고 available도 (0,0,0)이라 1st로 가능
  • p[1]은 할당보다 request가 큼, 아직 x
  • p[2]는 가능 + allocation까지 합해줘서 Available (3,1,3) 업데이트
  • p[3], p[4]도 위 과정과 동일하게 진행하면 위에서 해결하지 못한 p[1] Request에 만족할 수 있는Available값을 가지고 있기 때문에 처리할 수 있다.

 

 

  • 만약 p[2]가 (0,0,1)로 된다면 위처럼 진행 불가능
  • Deadlock 상태에 빠지게 되고, p(1, 2, 3, 4)가 deadlock상태에 관여하는 Process라고 볼 수 있다.

 

 

 

  • 빠르게 찾아낼 수 있지만 Overhead가 발생할 수 있음
  • 언제 어떻게 실행해야하는지
    • Deadlock이 얼마나 발생하는지 체크
    • 얼마나 많은 process가 실행 이전단계로 돌아가야하는지
  • 위 2가지 사항에 따라 결정
  • 마지막 문장

 

  • Deadlock을 회복시키기 위한 프로세스 종료 or 자원 회수
  • Deadlock을 탈출하기 위해 모든 process 한 번에 회수
  • 한 번에 하나 씩만 회수

어떤 Process를 회수할지 고려할 사항

  • 우선순위 고려
  • 얼마나 오래동안 일을 해왔고, 잔여 작업도 얼마나 남아있는지
  • Process가 사용한 자원
  • 완료가 요구되는 프로세스인가
  • 몇 개를 더 종료시켜야하는지
  • interactive or batch 프로세스인가

 

 

 

 

 

  • 자원 회수 기법
  • 비용 최소화 기준
  • 프로세스가 갖고 있던 자원을 반납하고 Rollback(안전 단계로 돌아가기)한 후 재실행이 되어야함
  • Starvation 문제 : 특정 Process만 연속해서 자원을 회수 시킬 수 있음, 홧수 제한으로 방지할 수 있음
728x90
반응형