[CS] 교착상태와 기아상태

🔵 교착상태 (DeadLock)

 

면접 질문 : 

 

1. 교착상태와 교착상태 해결방법에 대해서 설명해주세요.
2. 교착상태 발생조건에 무엇이 있는지 얘기해주세요.

1. 두 개 이상의 프로세스가 자원을 점유한 상태(멀티 프로그래밍 환경)에서 서로 원하는 자원을 얻기 위해 무한정한 기다림 상태에 빠지는 것입니다. 이에 대한 해결방법은 예방, 회피, 탐지 및 회복이 있습니다.

 

2. 상호배제 , 점유와 대기 , 비선점 , 순환대기가 있으며 4가지 조건 모두 성립해야 교착상태가 발생 할 수 있습니다.

 

🔷 교착상태란 ? 

두 개 이상의 프로세스가 서로의 작업이 끝나기만을 기다리고 있어 둘 다 영원히 끝나지 않는 상황

= 데드락(DeadLock) 이라고도 함

 

🔷 교착상태 발생조건

아래 4가지 조건이 모두 만족되는 경우 데드락이 발생할 가능성이 있다.
→ 하나라도 만족하지 않으면 발생하지 않음

 

1. 상호 배제 (Mutual exclusion)
   • 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다 (자원 = 임계영역)
   • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
   • ex) 한 개의 화장실을 한 개의 키를 갖고 여러명이서 사용하려 할 때
2. 점유와 대기(Hold and wait)
   • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
   • ex) 인원이 한정된 오마카세를 먹고 있음과 동시에 유명 카페를 테이블링 할 때 
3. 비선점 (No preemption)
   • 이미 할당된 자원을 강제로 빼앗을 수 없다.
   • 프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때까지 기다려야 한다.
   • ex) 가득 찬 피팅룸을 사용하려 할 때
4. 순환대기 (Circular wait)
   
   • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
   • Hold and wait 관계의 프로세스들이 서로를 기다림
   • ex) 4개의 교차로의 좌회전 신호 대기 중인 차들

 

🔷 교착상태 해결방법

• 데드락이 발생하지 않도록 예방(prevention) 하기
• 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
• 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복(Recovery)하기

 

1️⃣  예방 (Prevention)

교착 상태가 발생하기 전에 미리 조치를 취하는 방식으로, 교착 상태 발생 조건 중 하나를 제거함으로써 해결한다.

 

1. 상호 배제 조건 방지
   • 모든 자원을 공유 허용
2. 점유와 대기 조건 방지
   • 모든 자원에 대해 선점 허용
3. 비선점 조건 방지
   • 필요 자원을 한번에 할당
4. 순환 대기 조건 방지
   • 자원에게 순서 부여를 통해 프로세스 순서의 증가 방향으로만 자원 요청

단점 : 자원낭비가 심함

 

2️⃣  회피 (Avoidance)

프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있는가를 확인하여 교착 상태를 회피하는 방법

 

• 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법이다.
• 리소스 할당의 측면에서, 교착상태가 발생할 가능성이 있는 자원 할당(unsafe allocation)을 하지 않는다.
• 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.

단점 : 오버헤드 발생

 

은행원 알고리즘

• 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법
• 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태는 안전상태, 교착상태가 발생할 수 있는 상태는 불안전 상태 라고 한다.
• 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다.
• 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.

import Foundation

class Bank {
    var available: Bool = true // 은행원의 사용 가능 여부
    
    let queue: DispatchQueue = DispatchQueue(label: "bankQueue") // 공유 자원에 대한 동시 액세스를 관리하기 위한 큐
    
    func deposit(amount: Int) {
        queue.sync {
            guard available else {
                print("은행원이 사용 중입니다. 대기해주세요.")
                return
            }
            
            available = false
            print("입금 처리 중...")
            // 입금 작업 수행
            Thread.sleep(forTimeInterval: 2)
            print("입금 완료.")
            
            available = true
        }
    }
    
    func withdraw(amount: Int) {
        queue.sync {
            guard available else {
                print("은행원이 사용 중입니다. 대기해주세요.")
                return
            }
            
            available = false
            print("인출 처리 중...")
            // 인출 작업 수행
            Thread.sleep(forTimeInterval: 2)
            print("인출 완료.")
            
            available = true
        }
    }
}

// 테스트
let bank = Bank()

DispatchQueue.concurrentPerform(iterations: 10) { index in
    let randomAmount = Int.random(in: 100...1000)
    
    if index % 2 == 0 {
        print("프로세스 \(index): \(randomAmount)원 입금 시도")
        bank.deposit(amount: randomAmount)
    } else {
        print("프로세스 \(index): \(randomAmount)원 인출 시도")
        bank.withdraw(amount: randomAmount)
    }
}

 

3️⃣  탐지 (Detection)

데드락이 발생하면 빠르게 발견하고 문제를 해결하는 것

• 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견한다.
• 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용한다.

 

단점 : 자원을 요청할 때마다 탐지 알고리즘을 실행하면, 오버헤드가 발생

 

 

4️⃣  회복 (Recovery)

교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제하면서 회복

 

1. 프로세스 종료 방법

• 교착 상태의 프로세스 모두 중지
• 교착 상태가 제거될 때까지 한 프로세스씩 중지

2. 자원 선점 방법

• 자원을 빼앗긴 프로세스는 강제 종류 이후 재시작
• 교착 상태에 빠진 프로세스가 필요로 하는 자원을 강제로 가져옴

 

🔵 기아상태 (Starvation)

 

면접 질문 : 

 

1. 교착상태와 기아상태의 차이점에 대해서 설명해주세요.

교착상태와 기아상태는 둘 다 다중 프로세스 환경에서 발생하는 문제지만, 교착상태는 자원의 순환 대기와 관련된 조건을 충족하며 시스템 전체적으로 발생하는 문제이며, 기아상태는 특정 프로세스가 자원에 접근할 수 없는 상태로 인해 발생하는 문제입니다.

 

🔷 기아상태란 ? 

특정 프로세스보다 우선순위가 낮아 원하는 자원을 계속 할당받지 못해 자원을 무기한으로 기다리는 상황

 

🔷 기아상태 발생조건

교착상태의 비선점 현상이 계속된다면 기아상태가 된다. (내피셜)

 

🔷 기아상태 해결방법

에이징(Aging) 기법

• 기아상태를 회피하기 위해 낮은 우선순위를 가진 프로세스들을 기다린 만큼 우선순위를 높여주는 방법이다.
• 아무리 우선순위가 낮은 대상이라도 그 대상을 기다리는 다른 대상이 있을 수 있으니 늦게라도 자원이 할당되어 처리되도록 해야 한다. 대기시간에 비례하여 우선순위를 부여함으로써 기아 현상을 방지한다.
• ex) 피팅룸 사용시 자리가 꽉 찼을 때 직원이 먼저 온 사람들 순서대로 대기표를 부여하는 것