Deadlock
•
프로세스나 스레드가 자원을 얻지 못해 다음 작업을 수행하지 못하는 상태로, 교착 상태라고도 불린다. 주로 멀티 프로그래밍 환경에서 한정된 자원을 사용하려 서로 경쟁하는 과정에서 발생한다.
•
Deadlock의 발생 조건은 4가지가 있다.
◦
상호 배제(Mutual exclusion)
▪
자원은 한 번에 하나의 프로세스만이 사용할 수 있어야 한다.
◦
점유 대기(Hold and wait)
▪
최소 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
◦
비선점(No preemption)
▪
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
◦
순환 대기(Circular wait)
▪
프로세스의 집합이 있다면 P1→P2→…→P1→P2 순으로 프로세스가 각자의 자원을 점유하고 있으며 다른 프로세스가 가진 자원을 대기하는 순환이 발생해야 한다.
•
Deadlock의 처리
◦
Prevention(예방)
▪
교착 상태의 발생 조건 중 하나를 미리 제거함으로써 해결하는 방법이다.
▪
상호 배제(Mutual exclusion) 부정
여러 개의 프로세스가 공유 자원을 동시에 사용할 수 있도록 한다.
▪
점유 대기(Hold and wait) 부정
프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
▪
비선점(No preemption) 부정
자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때는 점유하고 있는 자원을 반납 후 다른 자원의 반납을 기다리도록 한다.
▪
순환 대기(Circular wait) 부정
자원에 고유한 번호를 할당하고 번호 순서대로 자원을 요구하도록 한다.
▪
자원의 낭비가 매우 심하다.
◦
Avoidance(회피)
▪
교착 상태가 발생하면 해당 상황을 피해가는 방법으로, 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있는지(교착 상태가 발생하지 않는지) 사전에 검사하여 교착 상태를 회피하는 방법이다.
▪
안정 상태(safe state)
프로세스들이 요구하는 모든 자원을 교착 상태 없이 모두 할당할 수 있다면 안정 상태에 있다고 말한다.
▪
안전 순서(safe sequence)
특정한 순서로 프로세스들에게 자원을 할당하고 실행 및 종료 등 작업을 할 때 교착 상태가 발생하지 않는 순서를 안전 순서라고 부른다.
▪
대표적으로 은행원 알고리즘이 있으며, 회피 방식은 미리 최대 자원 요구량을 알아야하고 할당할 수 있는 자원 수가 일정해야 하는 등의 사용 조건에 제약이 많다. 또한 사용 조건 제약에 따른 자원의 이용률이 낮아진다는 단점도 있다.
◦
교착 상태 탐지 및 회복
▪
교착 상태가 되도록 허용한 다음 교착 상태가 발생하면 회복시키는 방법으로, 대부분의 시스템은 교착 상태가 잘 발생하지 않고 교착 상태를 예방, 회피하는 것은 비용이 많이 들기 때문에 사용하는 방법이다.
▪
탐지 기법
현재 시스템의 자원 할당 상태를 확인하여 시스템에 교착 상태가 발생했는지를 파악한다.
▪
회복 기법
교착 상태가 발생했다면, 순환 대기 상태에서 벗어나 교착 상태를 회복한다. 순환 대기를 벗어나는 방법은 프로세스를 1개 이상 중단시키거나, 프로세스에 할당된 자원을 뺏어와(선점) 교착 상태가 해결될 때까지 해당 자원을 다른 프로세스에 할당해주는 방법이 있다.
▪
자원을 요청할 때마다 교착 상태가 발생했는지 확인하는 탐지 알고리즘을 실행하기 때문에, 그에 따른 오버헤드가 발생한다.
Starvation
•
일부 프로세스가 자원을 요청하지만, 우선순위가 낮거나 다른 이유로 인해 자원을 계속 할당 받지 못하고 있는 상태를 말한다.
•
Deadlock의 경우에는 여러 프로세스가 동일 자원을 점유하려 할 때 발생하고, starvation은 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁하는 상황에서 발생한다.
•
starvation이 발생하지 않는 알고리즘을 적용하거나, 오랫동안 자원을 할당받지 못하는 프로세스에 높은 우선 순위를 가질 수 있는 기회를 주어 해결할 수 있다.
고전적인 동기화 문제들
•
Bounded-Buffer Problem(Producer-Consumer Problem)
◦
생산자(Producer) 프로세스와 소비자(Consumer) 프로세스가 있을 때, 유한한 개수의 데이터를 보관할 수 있는 버퍼에 여러 생산자 프로세스와 소비자 프로세스가 접근한다.
◦
생산자 프로세스는 데이터를 버퍼에 저장하고, 버퍼가 가득 차 있다면 기다린다.
◦
소비자 프로세스는 버퍼에서 데이터를 꺼내 읽고, 버퍼가 비어있다면 기다린다.
◦
위 과정을 동기화 없이 진행하게 되면, 버퍼가 비어있는데 소비자가 데이터를 꺼내려하거나 버퍼가 가득 차있는데 데이터를 넣으려 하는 상황이 발생할 수 있다.
◦
또한 유한 버퍼 문제는 위 그림처럼 생산자는 넣을 버퍼가 비어있지 않고, 소비자는 꺼낼 버퍼가 비어있어 서로를 기다리는 상황에서 교착 상태가 발생할 수 있다.
◦
mutex lock이나 semaphore를 사용하거나 monitor를 통해 해결할 수 있다.
•
Readers-Writers Problem
◦
위의 유한 버퍼 문제와 비슷한 상황으로 Readers는 공유되는 데이터베이스를 읽는 역할을 하고, Writers는 공유되는 데이터베이스를 수정하는 역할을 한다.
◦
해당 상황에서는 효율성을 위해 쓰는 과정에서는 상호 배제(해당 스레드 제외 읽기/쓰기 불가) 방식으로, 읽는 과정에서는 해당 데이터를 읽으려는 모든 스레드를 허용하는 방식으로 사용한다.
◦
일부 시스템에서는 이렇게 쓰기 모드와 읽기 모드가 분리된 reader-writer lock을 제공하며, mysql에서는 읽기 락을 s lock, 쓰기 락을 x lock이라 부른다.
◦
데이터를 읽고 그 값을 변경하는 동작이 있다고 하면, 해당 동작을 동시에 두 프로세스에서 실행하게 되면 각자 s lock을 얻어 값을 읽은 후 값을 수정하기 위해 x lock을 얻으려 서로 s lock이 해제 되기를 기다리는 교착 상태가 발생한다.
•
Dining-Philosophers Problem
◦
위와 같이 N명의 철학자가 원탁에 둘러앉아 있고, 각 철학자 사이에는 젓가락 1개씩 놓여있는 상황이다. 철학자가 식사를 하기 위해서는 자신의 좌우 양쪽 젓가락을 모두 집어야한다.
◦
이런 문제에서 모든 철학자가 자신의 우측 젓가락을 들고 좌측 젓가락을 기다리는 상황에서 교착 상태가 발생할 수 있다. 또한 특정 철학자가 오랫동안 젓가락을 집지 못해 아사 현상이 발생하기도 한다.
◦
이때 젓가락은 공유 자원이므로 mutex lock이나 semaphore를 통해 보호되어야 한다.
◦
교착 상태와 아사 현상을 피하기 위해 짝수 번째 철학자들이 먼저 식사하고, 홀수 번째 철학자들이 다음으로 식사를 하는 식으로 번갈아가며 식사를 하도록 구현하여 해결할 수 있다.