[운영체제] 7. deadlock

Deadlock

• 데드락의 발생 조건
  • Mutual Exclusion : 프로세스 간 자원의 공유(동시 사용)이 불가
  • Hold and Wait : 자원을 한 프로세스가 점유한 경우, 다른 프로세스 접근 시 대기
  • No Preemption : 점유한 자원은 반환하기 전까지 해당 프로세스가 계속 사용
  • Circular wait : 프로세스는 다음 프로세스의 자원을 대기
    • Pa > Pb, Pb . Pc, ... Pz > Pa

---

• Resurce Allocation Graph
  

  

  • 자원의 할당 방향을 표현
  • P : Process, R : Resource, T : Thread
  • 자원 요청 : P에서 R로 화살표
  • 자원 할당 : R에서 P로 화살표
  • R 내의 점 : Resource가 갖는 인스턴스를 의미
• Circular wait에 의한 데드락 발생 조건
  • Cycle 없음 : deadlock x
  • Cycle 있음 : 리소스 내에 인스턴스가 복수개 있을 경우 deadlock x

Handling deadlock

Deadlock Prevention

• Mutual Exclusion - 자원의 공유 허용
• Hold and Wait
  • 프로세스 시작 전에 자원을 미리 할당
  • 자원을 미리 할당해야 하므로 활용성이 떨어지거나, starvation 위험
• No preemption - 자원 선점 허용
• Circular Wait - 자원에 lock 요청 시 우선순위 배정

void transaction(account from, account to, double amount){
  mutex lock1, lock2;
  lock1 = get_lock(from);
  lock2 = get_lock(to);

  acquire(lock1);
  acquire(lock2);
  //from이 먼저 lock acquire

  withdraw(from, amount);
  deposit(to, amount);
  release(lock2);
  release(lock1);
}

Deadlock Avoidance

• 각 프로세스가 요구하는 자원 정보가 필요
• 시스템이 deadlock 진입 여부를 확인한 후 자원을 할당
• safe state : 자원 할당 시 deadlock이 발생하지 않는 상태
• unsafe state : deadlock이 발생할 가능성이 있는 상태
• avoidance algorithm
  • resource-allocation graph
    • 리소스당 인스턴스가 하나인 경우
    • Claim edge : 프로세스/스레드 할당 시 필요 자원을 OS에 요청
    • Claim edge > request > assignment > claim > ...
    • claim edge를 이용하여 요구 자원이 사용중인지 여부를 판단해 deadlock 방지
  • Banker's Algorithm
    • 리소스당 인스턴스가 다수 존재
    • 각 프로세스는 OS에 사용 자원을 알려야 함
    • 자원 부족시 대기
    • 프로세스 실행 후 일정한 시간 후 자원을 반납
    • banker's algorithm의 자료구조
      • available : 사용 가능한 인스턴스를 저장하는 vector
      • max : 리소스 당 사용 가능한 자원을 나타내는 matrix
      • allocation : 각 프로세스가 점유한 자원을 나타내는 matrix
      • Need : 프로세스 완료를 위해 필요한 자원을 나타내는 matrix
        • neet = max - allocation

---

• safety algorithm
  1. 변수 선언
  • work = available
  • finish[i] = false: 프로세스가 끝났는지 여부
  2. i에 대해서
  • finish[i] = false
  • need[i] <= work인 프로세스 탐색
  • 존재하지 않는경우 4로
  3. 자원 반납
  • work = work + allocation
  • finish = true
  • 2 반복
  4. finish[i] == true인 경우, 시스템은 safe state
• resource request algorithm
  • request_i[j] : 프로세스 i의 request vector
    • request_i[j]=k : 프로세스 i는 resource j의 k개 인스턴스를 필요로 함
  • request_i <= need면 진행, 그렇지 않은 경우 error(최대 제한을 초과)
  • request_i <= available이면 진행, 그렇지 않은 경우 자원 할당이 불가하므로 대기
  • 자원 할당
    • available = available - request
    • allocation = allocation + request
    • need = need - request
    • safe인 경우 자원 할당, unsafe인 경우 대기

Deadlock Detection

• deadlock 감지 및 복구
• wait-for-graph
  

  

  • resource allocation graph에서 resource가 빠진 방식
  • cycle 감지 시 n개 프로세스에서 n^2개의 계산 동작이 필요
• detection algorithm
  1. 변수 선언
  • work = available
  • allocation_i != 0인 경우 finish_i = false, 그렇지 않은 경우 true
  2. i에 대해
  • finish[i] == false
  • request_i<=work인 프로세스 탐색
  • 존재하지 않는 경우 4로
  3. work = work + allocation, finish[i] = true, 2 반복
  4. finish[i] == false인 경우 i번째 프로세스는 deadlock

Deadlock recovery

• deadlock된 모든 프로세스를 제거
• deadlock이 풀릴때까지 프로세스를 하나씩 제거
• 프로세스를 rollback
  • rollback당한 프로세스는 starvation 위험이 존재