Resource-Allocation Graph (자원할당그래프)

Deadlock Avoidance

Resource Allocation Graph algorithm

실선은 요청을 한거고 점선은 미래에 요청할 수도 있다는 것이다.

deadlock avoidance는 점선을 포함해서 싸이클이 생길 것 같으면 자원을 주지 않는 것이다.

자원의 인스턴스가 여러개 있는 상황은 다음 알고리즘을 이용한다.

Banker's Algorithm

Example of Banker's Algorithm

0번 프로세스의 경우 최대 쓸 자원이 A 7개 B 5개 C3개다.

만약 0번 프로세스가 C를 1개 요청하면 비록 자원의 여유가 있더라도 주지 않는다. 가용자원은 3,3,2지만 0번 프로세스는 7,4,3까지 요청할 수 있기 때문이다.

1번 프로세스는 1,2,2가 필요하니 자원을 준다.

2번 요청은 A를 6개까지 요청할 수도 있기 때문에 자원을 안준다.

Banker's algorithm은 항상 safe한 상태를 유지한다. safe하다는 것은 가용자원으로 프로세스를 하나씩 끝낼 수 있는 상황을 말한다.

P1 request (1,0,2)

Deadlock의 처리 방법

지금까지 deadlock avoidance에 대한 방법이었다.

Deadlock Detection and Recovery

자원당 인스턴스가 하나 있으면 그래프를 그리고, 여러 개있으면 bankers algorithm처럼 테이블을 만들면 된다.

오른쪽은 자원을 빼버리고 프로세스에서 프로세스로 가는 그래프다.

deadlock detection에서는 여유자원이 있으면 무조건 준다. 0번 프로세스나 2번 프로세스는 요청을 하나도 안했기 때문에 끝나고 자원을 반납할 수 있다. 그 자원들을 모아서 요청된 자원들을 줄 수 있다.

여기서는 데드락이 발생하지 않는다.

여기서는 데드락이 발생한다.

위에는 프로세스를 죽이는 방법이고 아래는 자원을 뺏는 방법이다.

Deadlock Ignorance

아이러니하게도 현대 많은 운영체제는 이 방법을 채택

이하 클린코드 출처

데드락
다음 네 가지 조건을 모두 만족하면 데드락이 발생한다.

상호 배제 (Mutual Exclusion)
잠금 & 대기 (Lock & Wait)
선점 불가 (No preemption)
순환 대기 (Circular Wait)
상호 배제
여러 스레드가 한 자원을 공유하나 그 자원은

여러 스레드가 동시에 사용하지 못하며
개수가 제한적이라면
상호 배제 조건을 만족한다.

좋은 예가 데이터베이스 연결, 쓰기용 파일 열기, 레코드 락, 세마포어 등과 같은 자원이다.

잠금 & 대기 (Lock & Wait)
일단 스레드가 자원을 점유하면 필요한 나머지 자원까지 모두 점유해 작업을 마칠 때까지 이미 점유한 자원을 내놓지 않는다.

선점 불가 (No Preemption)
한 스레드가 다른 스레드로부터 자원을 빼앗지 못한다.

순환 대기 (Circular Wait)
죽음의 포옹이라고도 한다. T1, T2라는 스레드가 두 개 있으며 R1, R2 라는 자원이 두 개가 있다고 가정하자. T1이 R1을 점유하고, T2가 R2를 점유한다. 또한 T1은 R2가 필요하고, T2도 R2가 필요하다.

위의 네 가지 모두를 충족해야 데드락이 발생한다. 네 조건 중 하나라도 깨버리면 데드락이 발생하지 않는다.

상호 배제 조건 깨기
동시에 사용해도 괜찮은 자원을 사용한다. 예를 들어, AtomicIntger를 사용한다.
스레드 수 이상으로 자원을 늘린다.
자원을 점유하기 전에 필요한 자원이 모두 있는지 확인한다.
하지만 대다수 자원은 한정적이고 동시에 사용하기도 어렵다.

잠금 & 대기 조건 깨기
대기하지 않으면 데드라깅 발생하지 않는다. 각 자원을 점유하기 전에 확인한다. 만약 어느 하다라도 점유하지 못한다면 지금까지 점유한 자원을 몽땅 내놓고 처음부터 다시 시작한다.

이 방법은 잠재적인 문제가 있다.

기아(starvation): 한 스레드가 계속해서 필요한 자원을 점유하지 못한다. (점유하려는 자원이 한꺼번에 확보하기 어려운 조합일지도 모른다).

라이브락(Livelock): 여러 스레드가 한꺼번에 잠금 단계로 진입하는 바람에 계속해서 자원을 점유했다 내놨다를 반복한다. 단순한 CPU 스케줄링 알고리즘에서 특히 쉽게 발생한다.

두 경우 모두가 자칫하면 작업 처리량을 크게 떨어뜨린다. 기아는 CPU 효율을 저하시키는 반면 라이브락은 쓸데 없이 CPU만 많이 사용한다.

선점 불가 조건 깨기
데드락을 피하는 또 다른 전략은 다른 스레드로부터 자원을 뺏어오는 방법이다. 일반적으로 간단한 요청 메커니즘으로 처리한다. 필요한 자원이 잠겼다면 자원을 소유한 스레드에게 풀어달라 한다. 소유 스레드가 다른 자원을 기다리던 중이었다면 자신이 소유한 자원을 모두 풀어주고 처음부터 다시 시작한다.

순환 대기 조건 깨기
데드락을 방지하는 가장 흔한 전략이다.

R1을 점유한 T1이 R2를 기다리고 R2를 점유한 T2가 T1을 기다리는 앞서 예제에서 T1과 T2가 자원을 똑같은 순서로 할당하게 만들면 순환 대기는 불가능하다.

좀 더 일반적으로 말해, 모든 스레드가 일정 순서에 동의하고 그 순서로만 자원을 할당한다면 데드락은 불가능하다. 그러나 이 전략도 문제를 일으킬 소지가 있다.

자원을 할당하는 순서와 자원을 사용하는 순서가 다를지도 모른다. 그래서 맨 처음 할당한 자원을 아주 나중에야 쓸지도 모른다. 즉, 자원을 꼭 필요한 이상으로 오랫동안 점유한다.

때로는 순서에 따라 자원을 할당하기 어렵다. 첫 자원을 사용한 후에야 둘때 자원 ID를 얻는다면 순서대로 할당하기란 불가능하다.

이렇게 데드락을 피하는 전략은 많다. 하지만 어떤 전략은 기아를 일으키고, 다른 전략은 CPU를 심하게 사용해 응답도를 낮춘다.