라이브락 & 데드락

라이브락

프로세스가 실패하는 연산을 반복적으로 실행했을 때 진행하지 못하고 있는 상황을 말한다. 네트워크 충돌이 발생했을 때 랜덤한 시간 동안 기다렸다가 다시 보내는 행위가 라이브락을 해결하기 위한 방법의 일종이다.

 

데드락

자원을 획득하지 못하고 계속해서 waiting state로 남아있는 상태를 dead lock이라고 한다.

필요 조건은 다음과 같다.

1. 상호 배제

2. 자원을 획득한 상태에서 다른 프로세스의 자원을 기다린다.

3. 선점 불가능

4. 순환 대기

 

위 조건 중 하나라도 성립하지 않으면 데드락은 발생하지 않는다.

1이 성립하지 않으면 그냥 아무 프로세스나 자원을 사용할 수 있고

2가 성립하지 않으면 자원을 아무것도 갖고 있지 않기 때문에 다른 프로세스의 진행을 방해하지 않는다.

3이 성립하지 않으면 리소스를 뺏어서 할당하면 되고,

4가 성립하지 않으면 DAG 위상 정렬을 통해 자원을 할당하면 된다.

 

공유 데이타와 관련되어 멀티 쓰레디드 프로그래밍을 하는 경우, 상호 배제가 기본으로 들어가기 때문에 잘못 되면 데드락이 발생할 수 있다.

 

자원 할당 그래프

프로세스, 리소스 타입의 정점과 리소스 인스턴스, request, release를 의미하는 방향 간선을 통해 그래프를 구성할 수 있다. 싸이클은 필요 조건은 아니지만 데드락의 충분 조건이다. 인스턴스의 out degree는 항상 1을 만족한다. (상호 배제)

 

데드락의 해결책

0. 무시

대부분의 OS에 채택하는 방식이다. 데드락이 자주 일어나는 일은 아니기 때문에 무시하고 일어나지 않은 것처럼 동작한다. 비용 효율적이다.

 

1. 예방

4 가지 필요 조건 중 하나를 불만족시킨다.

• 상호 배제: 해결 불가
• hold & wait: 요청 전에 가지고 있던 모든 자원을 버리거나 프로세스 시작 전에 미리 필요 자원을 모두 할당
• 선점 불가능: hold & wait를 하고 있는 쓰레드로부터 자원을 뺏을 수 있게 한다.
• 순환 대기: 리소스 타입에 우선순위를 정하고, 우선 순위가 높은 것부터 요청할 수 있게 한다. (순환 대기 상황에서는 마지막 리소스를 갖고 있는 프로세스가 첫 프로세스가 가진 리소스를 요청해야 하는데, 마지막 리소스는 첫 리소스보다 우선 순위가가 크기 때문에 해당 프로토콜에서는 있을 수 없는 상황이다.)

결론: 순환 대기를 막는 방법만 현실적이고, 나머지는 자원 활용률이 너무 떨어진다.

 

2. 회피

리소스 할당 상태를 파악하여 순환 대기를 막음으로써 데드락을 회피한다.

• 안전 상태: 현재 리소스 할당 상태에서 요청을 순서대로 처리할 수 있는 순서가 존재한다.
• 비안전 상태: 안전 상태가 아니다. 데드락의 충분 조건이다.

 

Banker's 알고리즘

데드락 회피의 대표적인 알고리즘이다.

• need : 쓰레드 가 현재 필요로 하는 리소스 타입 당 리소스의 개수
• allocation: 쓰레드 별로 할당된 리소스 타입 당 리소스의 개수
• max = \(need + allocation\): 쓰레드가 작업하기 위해 요청할 것으로 예상되는 리소스 타입 당 최대 리소스의 개수
• available: 현재 사용 가능한 리소스 타입 당 리소스의 개수

안전 상태 판별 알고리즘

\(work = available\)로 초기화한다. 현재 끝나지 않은 쓰레드 중 need가 work보다 작거나 같은 쓰레드를 찾아서 완료되었다고 치고, 할당된 자원을 풀어서 work에 더해주는 것을 반복한다. 모든 쓰레드가 끝나기 전에 이 loop가 종료되면 비안전, 아니면 안전 상태다.

자원 요청 알고리즘

요청이 들어왔을 때 이 알고리즘을 통해 프로세스에 자원 할당 여부를 결정한다.

우선 requset가 need보다 크면 필요 이상의 요청이므로 거부한다. available보다 크면 기다려야 한다.

이제 request대로 자원을 할당해주고 안전 상태 판별 알고리즘을 실행한다. 비안전이면 기다리게 하고 상태를 이전으로 복구한다.

단점: 요청마다 데드락 판별 알고리즘을 돌려야 하기 때문에 오버헤드가 너무 크다.

 

3. 감지 후 회복

데드락 판별 알고리즘

• 자원 할당이 되지 않은 프로세스를 제외하고 안전 상태 판별 알고리즘을 돌린다. 비안전 상태로 판별되면 데드락이다.
• \(finish[i] = false\)면 i번 쓰레드가 데드락 상태에 있다.
• 자원을 소유하고 있는 프로세스 집합에서 현재 비안전 상태라면 자원을 적절한 순서로 할당할 수 없고, 자원을 뺏을 방법도 없으므로 데드락이다.

 

회복

• 데드락에 걸린 프로세스를 모두 종료시키거나, 데드락이 풀릴 때까지 하나씩 종료시킨다. (종료하는 기준이 필요하다.)
• 데드락에 걸린 프로세스로부터 자원을 빼앗는 방법이 있다. starvation이 생기지 않도록 victim을 적절히 선택하고 선택된 victim을 롤백시켜야 한다.

 

리뷰

예방 및 회피, 감지 및 회복은 특정 자원의 할당과 관련된 데이터를 통해 알고리즘을 계속 돌리면서 안전 상태, 데드락 상태 등을 파악해야 한다. 이 행위는 OS와 같이 복잡한 시스템에서는 자원의 효율성과 성능 측면에서 좋지 않다. 다만 상태 파악과 복구가 쉬운 환경에서는 고려해볼만 하다고 생각한다.