동기화와 교착상태(Deadlock)

이창윤·2022년 8월 10일

동기화

공유된 자원에 여러 프로세스/쓰레드가 동시에 접근하면 Critical section 문제가 발생하여 원하는 결과가 나오지 않을 수 있기 때문에 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다 (동기화를 해야한다).

임계 구역(Critical Section):
각 프로세스에서 공유 자원에 접근하는 프로그램 코드 영역

동기화 기법

wait과 signal이라는 2개의 atomic operations를 사용한다.

Atomic operation: 원자와 같이 기능적으로 분할할 수 없거나 분할되지 않도록 보증된 조작

Wait: 임계 구역에 들어가도 되는지 확인하고, 안되면 계속해서 기다린다.
Signal: 임계 구역에서 작업을 마치고 Wait중인 프로세스/쓰레드를 깨워줘서 들어갈 수 있도록 한다.

◻ 뮤텍스(Mutex)

자원의 동시 사용을 피하는 기법

임계 구역을 가진 쓰레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되도록 하는 기술
한 프로세스/쓰레드에 의해 소유될 수 있는 Key🔑를 기반으로 한 상호배제기법
Locking 메커니즘으로 락을 걸은 쓰레드만이 임계 영역을 나갈 때 락을 해제할 수 있다.
동기화 대상이 1개일 때만 사용한다.

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
...
do {
	pthread_mutex_lock(&mutex);
    ...
    //critical section
    ...
    pthread_mutex_unlock(&mutex);
}

◻ 세마포어(Semaphore)

공유 자원에 대한 접근을 제한하는 기법

공유 자원에 접근할 수 있는 프로세스/쓰레드 수를 나타내는 값( = 자원의 개수)을 두어 상호배제를 달성한다.
Signaling 메커니즘으로 락을 걸지 않은 쓰레드도 signal로 락을 해제할 수 있다 (뮤텍스와 다른 점)
동기화 대상이 1개 이상일 때 사용한다.
Counting Semaphore, Binary Semaphore 두 종류가 있는데 이진 세마포어는 세마포어의 카운트가 1이라서 뮤텍스와 같은 기능을 한다. (뮤텍스 대신 사용할 수 있다)
Wait 호출 -> 세마포어의 카운트 1 감소(사용 가능한 자원이 1 줄어든다), 카운트가 0보다 작거나 같아질 경우 락이 실행
Signal 호출 -> 세마포어의 카운트 1 증가, 락이 걸린 상태일 경우 락에서 나올 수 있다.(자리가 없었다면 기다리던 쓰레드가 자원을 사용할 수 있다)

sem_t semaphore;

sem_init(&semaphore, 0, 3); //3으로 초기화
...
do {
	sem_wait(&semaphore);
    ...
    //critical section
    ...
    sem_post(&semaphore);
}

교착상태(Deadlock)

뮤텍스와 세마포어를 사용해서 상호배제를 달성하더라도 교착상태와 같은 문제가 생길 수 있다!

둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한 대기를 하는 상태를 교착상태라고 한다.

발생 조건

4가지 모두 성립해야 교착상태가 발생한다.

상호 배제 (Mutual Exclusion): 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있음
점유 및 대기 (Hold and Wait): 프로세스가 공유 자원을 점유한 상태에서 다른 자원을 얻기 위해 대기하고 있는 상태여야 함
비선점 (No preemption): 프로세스가 한 자원을 점유하고 있으면 다른 프로세스가 강제로 빼앗을 수 없음
순환 대기 (Circular Wait): 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

해결 방법

교착상태 예방 또는 회피: 교착 상태가 되지 않도록 한다.
교착상태 탐지 및 복구: 교착 상태가 탐지되면 조치를 취한다.
교착상태 무시: 교착상태가 엄청 드문 경우 교착상태가 발생하도록 놔두고 필요에 따라 재부팅을 한다.

◻ 데드락 예방 (prevention)

교착상태 발생 조건 중 하나라도 발생하지 않게 하여 예방하는 방법
조건 중 하나 이상을 부정하여 방지할 수 있다.
- 상호 배제 부정: 읽기 전용 공유 자원을 사용한다.
- 점유 및 대기 부정: 프로세스가 실행되기 전 필요한 모든 자원을 할당(자원 낭비 발생)하거나 자원을 점유하고 있지 않을 때만 다른 자원을 요청할 수 있도록 한다.(기아상태가 될 수 있다)
- 비선점 부정: 모든 자원에 대해 선점을 허용한다 -> 자원 낭비가 발생한다.
- 순환 대기 부정: 자원에 고유한 번호를 할당하고 번호 순서대로 자원을 요구하도록 한다.(자원 낭비 발생)
시스템의 처리량이나 효율성을 떨어뜨리고 비현실적이다.

◻ 데드락 회피 (avoidance)

교착 상태가 발생하기 전에 안전한 상태에서만 자원 요청을 허용하는 방법

안전 상태 (Safe state): 교착상태를 발생시키지 않고 자원을 할당하는 순서 (safe sequence)가 존재해서 모든 프로세스가 정상적으로 종료할 수 있는 상태

불안전 상태 (Unsafe state): 교착상태가 발생할 수 있는 상태

다음과 같은 가정이 필요함
- 프로세스 수가 고정되어 있어야 한다.
- 자원의 종류와 수가 고정되어 있어야 한다.
- 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
- 프로세스는 반드시 자원을 사용 후 반납해야 한다.
자원 할당 그래프 (Resource-Allocation Graph) 알고리즘: 자원 인스턴스가 하나만 있는 경우 사용, 자원을 할당 받을 때 그래프에 사이클이 생기면 요청을 거부하는 방식
은행원 알고리즘 (Banker's Algorithm): 자원 인스턴스가 여러개일 경우 사용, 자원 요청을 승인했을 때 안전한 상태가 유지되는 경우만 자원 할당, 불안전 상태가 예상되면 다른 프로세스가 끝날 때 까지 대기

-> 현실성이 부족하고 자원 요청이 있을 때마다 회피 알고리즘을 사용하는 것은 상당한 오버헤드다.

◻ 교착상태 탐지 (detection)

탐지 알고리즘을 사용하여 교착상태가 발생했는지 탐지한다.
대기 그래프 (Wait-for Graph) 알고리즘: 자원할당 그래프를 변형해서 각 프로세스가 다른 프로세스가 보유하고 있는 자원을 기다리는 경우 간선을 추가하고, 사이클이 생기면 교착상태를 탐지한다.
은행원 알고리즘: 현재 상태가 안전 상태인지 확인하고, 불안전 상태면 교착상태라고 판단한다.
탐지 알고리즘은 자원을 요청했으나 즉시 할당받지 못할 때, CPU 이용률이 특정 값 이하로 떨어질 때, 또는 주기적으로 일정 시간마다 호출을 해서 오버헤드를 최소한으로 한다.

◻ 교착상태 복구 (recovery) - 교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제시키는 방법

프로세스 종료
- 교착상태의 프로세스를 모두 중지 or 교착상태가 풀릴 때 까지 프로세스를 하나씩 중지
자원 선점: 교착상태에 있는 프로세스의 자원을 다른 프로세스에게 선점 할당해서 해당 프로세스를 정지시키는 방법
- 최소의 피해를 줄 수 있는 프로세스를 선택한다.
- 기아상태를 방지해야 한다.