병렬 프로그래밍에서 발생할 수 있는 데드락과 우선순위 역전 문제를 알아보자.
Priority Inversion
우선순위 역전 문제는 우선순위 기반 선점모드인 scheduler에서 발생할 수 있는 문제이다.
실시간 스케줄링 문맥에서 바라보자.
우선순위가 높은 순으로 p1, p2, p3이 있다. p3가 공유 자원을 lock하고 p1이 lock을 시도하다 sleep 상태에 빠진다. 공유자원과 상관없는 p2가 p3을 선점했을 때, p1은 계속해서 잠들게 된다.
이를 unbounded priority inversion이라 칭한다.
만약 p2가 끼어들지 않았다면 p3 p1 순으로 빠르게 진행되어 실시간 시스템에 큰 영향을 안 줄 수도 있다.
그러므로 공유자원 처리 시간뿐만 아니라, 공유자원과 관련없는 task들이 영향을 끼칠 수 있다는 것이다.
위가 우선순위 역전 문제의 예시이다. 만약 P1이 시스템에 이상이 있나 확인하고 P3는 장비의 상태를 테스타할 때, P1 P3의 공유자원이 존재할 것이다. 위에서 얘기한 우선순위 역전이 발생했을 때, P1을 수행하지 못하고 시스템이 reset 될 수 있다.
이걸 어떻게 처리해야할까?
공유자원은 대개 선점 불가능하다. 중간에 처리하다 놓을 수 없다는 것이다.
굉장히 간단하게 처리할 수 있다. P3 \rightarrow P1 순으로 꼭 처리되어야 한다. 우선순위 기반이기 때문이다. 하지만 lock의 원리로 인해 P1이 sleep하고 P2이 실행되어 우선순위가 역전된다. 그럼 P3의 우선순위를 P1 수준의 우선순위로 일시적으로 높히면 된다. 그럼 P3가 처리되고 바로 P1이 처리될 수 있을 것이다.
이를 P1의 우선순위를 P3로 상속하기 때문에 우선순위 상속(Priority Inheritance)라 칭한다.
Priority Ceiling
우선순위 올림은 공유자원에 우선순위를 부여하는 기법이다. 자원을 사용하는 프로세스나 쓰레드는 공유자원에 접근했을 때, 높은 우선순위를 부여받고 선점당하지 않은 상태로 task를 빠르게 처리할 수 있다.
Deadlock
교착상태는 간단하게, blocked된 프로세스들끼리 서로의 event를 기다리는 상태를 의미한다. 다른 표현으로, 이벤트는 절대 일어나지 않는다.
위의 코드에서 만약 프로세스의 코드가 순차적으로 발생하면 데드락은 발생하지 않는다.
하지만 P가 semWait(A)를 수행하고 schedule이 발생한다면, 데드락은 불가피하다.
이렇게 하나의 자원을 가지고 다른 하나의 자원을 위해 기다리는 hold and wait 조건이 발생한다면 데드락이 발생할 수 있다.
두 개의 자원을 모두 취하기 위한 코드이다. 여기서 Get A와 Get B 사이에서 스케줄만 일어나지 않는다면 데드락은 일어나지 않는다.
P가 hold and wait 조건이 아니기 때문에 데드락이 발생하지 않는다.
데드락은 iteration, shared resource가 많을 때 발생할 수 있다.
인터럽트, 시그널 등 자원들은 소모자원이다. 그 외의 것들은 계속해서 사용이 가능하며 데드락이 발생할 수 있다.
첫 번째는 CPU의 데드락, 200KB의 할당 가능한 메모리가 있을 때, 순차적으로 할당하면 가능하지만 중간에 스케줄링되면 둘 다 메모리를 할당받을 수 없다.
또는 서버와 클라이언트가 패킷을 받기만을 원한다면 데드락이 발생할 수 있다.
Resource Allocation Graphs
시스템의 데드락 여부를 알아볼 수 있는 도구로 Resouce Allocation Graph를 사용한다.
digraph의 형태이며, 정점은 resource, process로 나뉘며, resourceprocess는 공유자원 점유이며, 반대는 lock 요청이다.
cycle이 존재하면 deadlock 상태이다. 추가로 자원에 instance가 존재하면 데드락이 발생하지 않는다.
Dining Philosphers problem
식사하는 철학자 문제는 교착상태를 이해하기 위한 도구로 사용된다. 이 문제를 제시하고 어떤 부분에서 데드락이 일어나는지, 데드락을 해결해나가는 과정에서 데드락을 잘 이해할 수 있다.
철학자들은 포크 두 개를 집고 밥을 먹고 포크를 내려두고 생각한다.
철학자들은 왼쪽에 앉아있다고 가정한다.(이다.)
shared resource는 i, (i + 1) mod 5 번째의 포크이며 이 두 개를 모두 가져야(lock) 밥을 먹고(eat()), 생각할 수 있다.(think())
위와 같은 코드로 구현되며 데드락이 발생하는 것을 볼 수 있다.
당연히 교착상태가 발생한다. 왼쪽 포크부터 집어들기 때문에, 모두가 왼쪽 포크를 집어들고 오른쪽 포크를 집어들라고 한다. 간단하게 왼쪽포크를 모두가 점유했을 때, 각각의 오른쪽 포크는 다른 나머지 철학자들의 왼쪽 포크다. 전부 점유당했을 것이다. 이 때 모두 오른쪽 포크를 위해 대기하기 때문에 교착상태에 빠진다.
First Solution
4 명만 들어갈 수 있게 세마포어로 guard를 칠 수 있다. graph로 표현하면 데드락 상태에 빠지지 않을 것이다.
하지만 이는 concurrency를 해친 것이다. 병렬 프로그래맹의 목적과 맞지 않다.
Deadlock conditions
데드락이 발생하는 조건을 알아보자.
- 상호배제: 당연히 resource에 하나의 프로세스만 접근 가능해야 데드락이 발생한다.
- 비선점: 비선점 자원이여야 데드락이 발생한다.
- Hold and wait: 동시에 두 개의 자원을 사용해야하는 상황이여야 데드락이 발생할 수 있다.
하지만 이 세 가지만 있다고 반드시 발생하지 않는다. 마지막으로 다음과 같은 조건이 필요하다.- Circular wait: 그래프의 cycle이 발생할 수 있어야 데드락이 발생할 수 있다.
다음 포스트에서 알아보자.
