Operating System 9 - Deadlock

 Liveness
어떤 프로세스들이 상호배제에 의해 무한 대기가 걸리지 않도록 보장하는 것. 이것이 보장되지 않는 경우가 deadlock과 priority inversion이 있다.
- priority inversion = 화성탐사선 사진 -  system. critical section 때문에 더 낮은 우선순위를 가지는 프로세스가 먼저 수행되는 상황이 발생. 이를 해결하는 방법은 critical section을 수행하고 있는 프로세스의 우선순위를 이것을 대기하는 프로세스의 우선순위 값으로 상속시키는 방법이다. 이후 critical section이 끝나면 상속된 값이 사라지도록 하면 이를 해결할 수 있다.


Synchronization problem
1. Bounded-buffer problem
2. Reader & Writers problem
3. Dining-Philosophers problem

- Bounded-Buffer problem
생산자 - 소비자가 공유하는 버퍼를 사용할 때 발생하는 문제. (없다면 소비 불가능, 가득 찼다면 생산 불가능)( 이는 counting semaphore를 이용해서 해결할 수 있다. mutex는 0, 1, full은 0부터 buffersize까지, empty도 buffersize부터 0까지 값을 가진다. full과 empty는 더해서 전체 사이즈가 되어야 하므로 하나가 변하면, 나머지 하나도 변하게 된다.

- Readers-Writers problem
reader = 읽기만 가능하고 쓰기는 불가능. writer = 읽기/쓰기가 모두 가능함. 이런 두 종류의 사용자가 있을 때 동시에 여러 reader는 접근할 수 있지만, writer가 있다면 상호배제를 수행해야 하도록 만들 필요가 있다. 이를 해결하는 것이 reader-writer problem이다.

이를 해결하는 방법은 각각 writer/reader를 완전히 차단하는 방법이 있다. 그러나 이렇게 단순한 두 가지 방법은 각각의 사용자 유형이 기아 상태에 빠질 수 있다는 문제점이 있다.

rw_mutex : 초기 값 1. reader/writer 모두 사용하는 뮤텍스로 상호배제를 구현.
mutex : 초기 값 1. 현재 대기 중인 reader의 수
read_count : 초기 값 0.

writer는 rw_mutex를 확인하여 쓸 수 있는지 없는지 확인. 그러나 reader는 첫 reader가 읽고 있을 때는 reader가 제한 없이 진입 가능. 그러나 첫 reader가 끝나고 대기하는 writer가 있다면 해당 첫 reader가 끝나고 진입한 reader들만 다 읽고 난 다음 writer를 이어서 실행 (count 변수)
따라서 수정한 어떤 파일을 읽는 것은 첫 reader부터 다음 writer가 들어온 순간까지 진입한 reader만 가능하다. (만약writer가 끝날 경우, 다음 수행될 reader/writer를 결정하는 것은 스케쥴러가 결정한다.)
이런 reader-writer lock은 주로 사용자가 reader/writer 명시되어 있고, reader가 많은 경우에 사용한다.

Dining-Philosopher problem(철학자의 저녁식사)
원형 테이블에 각 자리에 양 옆에 젓가락이 하나씩 있을 때, 각 철학자는 자신에게 가장 가까운 두 개를 집는다. 이 때 집으면 해당 젓가락을 wait(), 다 사용하면 signal() 한다. 이 순서는 왼쪽->오른쪽으로 이루어진다.
따라서 만약 모든 자리에 모든 사람이 와서 왼쪽 젓가락을 동시에 잡을 경우, 젓가락 개수가 0이 되므로 모두 오른쪽을 무한대기하게 된다. (deadlock이 됨)
따라서 이를 해결하는 방법은 전체 자리 수 보다 하나 적은 수의 사람만 앉게 하는 것이다. 이 경우, 한 명은 반드시 두 개를 잡을 수 있으므로 deadlock을 방지할 수 있다. (대신 나머지는 차례로 기다려야 함)
또 다른 방법은 무조건 한 쌍을 잡을 수 있을 때만 잡게 하도록 할 수 있다.
또 다른 방법은 홀, 짝을 나누어 홀은 왼쪽, 짝은 오른쪽을 먼저 잡도록 나누어서 설정할 수도 있다.

그러나 이런 해결책들은 여전히 프로세스의 선점 상화엥 따라 starvation 상황이 일어난다. 따라서 이는 코딩하는 프로그래머가 해결해야 한다.

환형, 상호 대기,  .... -> deadlock 4 요소에 포함됨!!!


Deadlock
면접에서 많이 나오는 것 중 하나. (데드락의 4요소(3가지 필수 & 1가지 충분), osi 7계층 등)

데드락이란 서로가 필요한 리소스를 점유하여 서로를 기다리는 상황이 발생해 무한 대기에 빠지는 것을 가리킨다. 데드락이 발생할 수 있는 상황이더라도 각 프로세스가 실행되는 시점에 따라 데드락이 발생되지 않을 수도 있다. 그래서 많은 코드 사이에서 데드락을 찾기가 매우 어렵다.

resource
리소스는 소비되는 것(메시지 , 인터럽트, signal 등)들과 재사용 가능한 것(프로세서, 메모리, 파일 등)으로 구분할 수 있다. 두 경우 모두 데드락이 발생할 수 있다.

Deadlock's characteristics (4 component of deadlock)
- Mutual exclusion : 상호 배제.
- Hold & wait : 자신이 리소스를 점유하면서도 다른 것을 요구하는 것.
- No preemption : 선점한 프로세스의 자원을 가져올 수 없음.
- Circular wait : 이 때, 서로의 프로세스들이 서로 쳐다보고 있을 때 데드락이 발생한다.

위의 3개가 필수 조건, circular wait는 충분 조건.

Resource-Allocatoin graph : deadlock detection
vertice는 active thread T와 resource type R로 구성된다. edge는 방향성에 따라 T가 R을 요구할 때는 T-> R, R이 T에 할당되어 사용 중일 때는 T<-R로 표기한다.

cycle이 없다면 deadlock이 발생하지 않는다. 그러나 cycle이 있다고 무조건 deadlock이 발생하지는 않는다. 왜냐하면 리소스 상태에 따라 서로 쳐다보지 않는 경우가 있을 수 있기 때문이다. (리소스의 instance 수가 2개 이상일 경우)
만약 resource의 instance가 하나 뿐이라면 cycle이 있을 때 반드시 deadlock이 발생한다. 반면에 여러 instance가 존재한다면 deadlock의 가능성이 있지만 반드시 발생하지는 않는다.


Deadlock handling

-Deadlock prevention : deadlock의 4요소가 일어나지 않도록 만듬.
그러나 상호 배제는 제거할 수 없다. (운영체제에 필수).

hold & wait의 경우, 필요한 것을 모두 한 번에 모두 받는 방법으로 해결할 수 있다. (앞서 철학자 문제에서 본 것 처럼 2개가 가능할 때만 획득) 그러나 이 경우 대기 시간이 길어지고 자원 분배가 비효율적이라는 문제점이 발생한다. (병행성이 급감) 또한 프로그램이 앞으로 어떤 리소스가 얼마나 더 필요할 지 예측하기 어렵다는 문제점도 있다.

비선점의 경우, 만약 어떤 필요한 리소스가 있는데 이 것에 대한 대기가 발생한다면 자신이 가지고 있던 리소스까지 모두 해제하고, 다음 번에 한 번에 가져올 수 있을 때 수행하도록 할 수 있다. 또는 선점형으로 설정할 수 있다. 그러나 선점 형으로 구성하더라도 priority가 같은 프로세스가 있다면 데드락이 발생할 수 있다.

환형대기를 해결하는 방법은 리소스를 점유할 때 리소스 간의 순서를 설정하여 이 순서대로만 획득하도록 하는 것이 있다. 그러나 이 경우 프로그램을 작성할 때 argument의 순서만 바꾸어도 제대로 작동하지 않을 수 있다.

-Deadlock avoidance : 리소스 자원을 모두 확인하여 이를 할당하기 전에 조건을 확인하고 할당.
이 방법은 각 스레드/프로세스가 요구하는 리소스와 해당되는 리소스의 개수, 현시점에 가용 가능한 리소스 개수 및 할당된 리소스 개수를 모두 알아야 가능하다.
시스템이 리소스를 할당했을 때 데드락이 발생하지 않은 것을 safe state라 하고, 해당 리소스 할당 순서를 safe sequence라 한다. unsafe state 이더라도 데드락이 발생하지 않을 수도 있다. 그러나 발생할 가능성이 있으므로 safe state인 부분에서만 실행하는 방법이 이 회피 방법이다.
이를 계산하는 방법은 리소스의 인스턴스 수에 따라 한 개라면 resource-allocation graph를 사용할 수 있고, 여러 개의 인스턴스를 가지는 리소스가 있다면 banker's algorithm을 사용할 수 있다.
resource-allocation graph는 앞서 내용에 추가해, 현재 사용되고 연결된 리소스를 연결하는 것 뿐 아니라 점선으로 앞으로 요구하는 리소스까지 표기한다. 이를 통해 unsafe state를 판별해 만약 unsafe하다면 리소스를 할당하지 않은 방식으로 작동한다.

Banker's Algorithm
여러 개의 인스턴스가 있을 떄 일일이 개수를 세는 방식으로 safety algorithm을 구현. 그래프보다 비효율적이지만 다른 방법이 없으므로 사용. Available/Max/Allocation/Need 등 matrix에 리소스 할당 상태와 스레드의 요구 상태를 저장하고 연산을 하여 final state의 모든 상태를 판별해 하나라도 false가 나오면 unsafe라 판단하는 방법이다.
 


-Deadlock detection : 데드락이 발생하게 그냥 두고, 발생했을 때 이를 복구.

* 일반적으로 윈도우, 리눅스의 경우, 시스템이 복잡해짐에 따라 3번째 방법을 채택한다. 데드락은 잘 발생하지도 않고 검출하기도 어려우므로 일정 간격마다 확인하여 이를 해결하는 것이 더 효율적이기 때문이다.