교착상태(Dead Lock)

🏃 경쟁상태(Race Condition) & 임계영역(Critical Section)

• 경쟁상태(Race Condition) : Thread / Process의 타이밍에 따라 결과값이 달라질 수 있는 상태
• 임계영역(Critical Section) : Thread / Process가 동시에 접근해서 안되는 곳

Critical Section을 동시에 수행하지 않도록 하기 위해 Thread 간 협의를 맞춰야함
(Mutex, Semaphore, Spin Lock, Barrier....)

🔒 교착상태(Dead Lock) 발생 조건

상호배제(Mutual Exclusion)

공유 자원을 어느시점에서 단 한개의 프로세스만 사용할 수 있도록 하며, 다른 프로세스가 현재 사용중인 공유 자원에 접근금지하는 행위

Semaphore

공유 자원에 여러 Process 및 Thread 가 접근하는 것을 방지(동기화 대상이 여러개)

<>출처 : https://worthpreading.tistory.com/90

<procedure P(S)   --> 최초 S값은 1임
    while S=0 do wait  --> S가 0면 1이 될때까지 기다려야 함
    S := S-1   --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P

--- 임계 구역 ---

procedure V(S) --> 현재상태는 S가 0임
    S := S+1   --> S를 1로 원위치시켜 해제하는 과정
end V

한 Process가 P 혹은 V를 수행하고 있는 동안 Process가 Interupt에 의해 방해받지 않게됨.

Mutex

공유 자원에 하나의 Process 및 Thread가 접근하는 것을 방지(동기화 대상이 한개)

>출처 : https://worthpreading.tistory.com/90

mutex 예시)

#include <stdio.h>
#include <pthread.h>

pthread_mutex_t mlock;
pthread_t tid[4];
int cnt;

void *run()
{
	pthread_mutex_lock(&mlock);
    for(int i = 0 ; i < 10000 ; i++) cnt++;
    pthread_mutex_unlock(&mlock);
}

int main()
{
	pthread_mutex_init(&mlock, NULL);
    
    for(int i = 0 ; i < 4 ; i++) {
    	pthread_create(&tid[i], NULL, run, NULL);
    }
    for(int i = 0 ; i < 4; i++) {
    	pthread_join(tid[i], NULL);
    }
    
    printf("%d\n", cnt);
    
    return (0);
}

점유대기(Hold and Wait)

이미 실행되고 있는 process가 다른 process의 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 상태

비선점(No Preemption)

이미 할당된 자원을 강제로 빼앗을 수 없음

순환대기(Circular Wait)

대기 프로세스의 집합이 순환형태로 자원을 대기하고 있어야 함

🔓 교착상태(Dead Lock)의 해결방법

1.데드락이 발생하지 않도록 예방(prevention)
=> 데드락의 발생조건(상호배제, 점유대기, 비선점, 순환대기)를 방지
2.데드락 발생 가능성을 인정하고 적절하게 회피(avoidance)
=> Banker's Algorithm
3.데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 회복하기