개요

운영체제에서 데드락(교착상태)란, 시스템의 여러 곳에서 자원을 사용하려고 할 때(다중 처리 환경), 프로세스가 자원을 얻지 못해 다음을 처리하지 못하는 상태(특정 자원을 무한정 기다리는 상태)이다.

발생원인

1. 상호 배제
   • 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다.
2. 점유와 대기
   • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
3. 비선점
   • 이미 할당된 자원을 강제로 빼앗을 수 없다
4. 환형 대기
   • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

해결 방법

1. 예방
   • 발생 가능성을 사전에 제거하도록 시스템 조절.
   • 자원의 상호 배제 조건 방지: 여러 프로세스가 자원을 공유
     - 동기화 문제가 발생 가능
   • 점유 대기 조건 방지: 실행에 필요한 자원 모두 요구
   • 비선점 조건 방지: 우선순위가 높은 쓰레드에 자원 선점
   • 순환 대기 조건 방지: 자원을 일정한 방향으로 요구
2. 회피
   • 데드락이 일어날 가능성을 예측하고, 프로세스를 제어
   • 회피 알고리즘으로 safe state 및 safe sequence를 만든다.
3. 발견
   • 교착상태가 발생하면 판단 및 조치
4. 복구
   • 프로세스를 식별하여 중지하고 재할당(희생자 설정)

swift에서의 dead lock

let queue = DispatchQueue(label: "label")
queue.async {
    queue.sync {
        // outer block is waiting for this inner block to complete,
        // inner block won't start before outer block finishes
        // => deadlock
    }
    // this will never be reached
}

RaceCondition

두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황. 따라서 데이터 일관성(Data Consistency) 를 해칠 수 있는 상태

해결 방법으로는

1. Mutual Exclusion(Mutex)
2. Semaphore 등이 있다.

swift에서 Thread Explosion 방지

iOS앱을 개발하며 Thread를 사용하는 것은 쉽지 않다. 하나의 concurrent queue에서 sync로 막혀있을때, 여러개의 task를 할당할 경우 thread explosion이 발생해 deadlock 상태에 빠지게 된다.

다음과 같은 상황에서는 Thread Explosion 이 일어난다.

// Create Concurrent Queue
let queue = DispatchQueue(label: "com.swiftpal.dispatch.explosion", attributes: .concurrent)

for i in 0 ... 1000 {
    // Async Tasks
    // 여기서 Thread들이 많이 생성됨
    queue.async {
        Thread.sleep(forTimeInterval: 1)
        print("Executed Task \(i)")
    }
}

// Sync Task
// 위의 작업때문에 pool안에 사용할 수 있는 thread가 없음
DispatchQueue.main.sync {
    print("All Tasks Completed")
}

따라서 우리는 우리의 task의 갯수를 제한할 필요가 있고, 이런 상황에서 우리는 DispatchSemaphore를 사용한다.

let concurrentTasks = 4

        // Create Concurrent Queue
        let queue = DispatchQueue(label: "com.swiftpal.dispatch.explosion", attributes: .concurrent)

        // Create Semaphore object
        let semaphore = DispatchSemaphore(value: concurrentTasks)

        for i in 0 ... 100 {
            // Async Tasks
            queue.async {
                Thread.sleep(forTimeInterval: 1)
                print("Executed Task \(i)")
                semaphore.signal()   // Sema Count Increased
            }
            semaphore.wait() // Sema Count Decreased
        }

        // Async Task
        DispatchQueue.main.async {
            print("All Tasks Completed")
        }

Semaphore vs mutex

mutex로 lock을 걸면 락을 건 쓰레드만 임계영역에서 나갈 때 뮤텍스를 해제할 수 있다.

하지만 세마포어는 락을 걸지 않은 쓰레드도 signal을 통해 락을 해제할 수 있다.