임계 영역 (Critical Section) , 교착 상태 (Dead Lock)

임계 영역 (Critical Section)

 혹은 공유 변수 영역 이라고도 한다.

- 병렬 컴퓨팅에서 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부

- 프로세스 간에 공유 자원을 접근하는 데 있어서 문제가 발생하지 않도록 한 번에 하나의 프로세스만 이용하게 끔 보장해줘야 하는 영역

 

임계 영역 문제를 해결 하는 법

- Lock, 뮤텍스, 세마포어, 모니터 등 이 있다.

1. 상호 배제 (Mutual exclution)

 : 한 프로세스가 임계 영역에 들어가 있다면 다른 프로세스는 들어갈 수 없다.

2. 진행 (Progress)

 : 임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러개 있다면 어느 것이 들어갈 것인지 결정해 주어야 한다.

3. 한정 대기 (Bounded wating)

 : 다른 프로세스의 기아(Starvation)를 방지하기 위해, 한번 임계 영역에 들어간 프로세스는 다음번 임계영역에 들어갈 때 제한을 두어야 한다. 

 

 

교착 상태 (Dead Lock)

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기에 아무것도 완료되지 못하는 상태

 

 

교착 상태 발생의 필요 충분 조건

다음 네가지 조건이 충족되면 교착 상태가 발생한다. 하나라도 충족되지 않으면 발생하지 않는다.

 

1. 상호 배제 (Mutual Exclusion) : 한번에 한개의 프로세스만이 공유 자원을 사용해야 한다.

2. 점유대기 (Hold and Wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

3. 비선점 (No Preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.

4. 순환 (환형 )대기(Circular Wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 갖고 있다.

 

이중 순환대기는 점유대기 와 비선점 조건을 만족해야 성립하는 조건, 4가지 조건이 서로 완전히 독립적인 것은 아니다.

 

 

교착 상태의 관리

현재의 대부분의 운영 체제들은 교착 상태를 막는 것은 불가능하다. 

 

예방

사전에 시스템을 제어하는 방법으로 교착 상태 발생의 네가지 조건중 어느 한가지를 제거함으로써 수행

자원 사용의 효율성이 떨어지고 비용이 많이든다.

- 상호 배제 부정 (제거): 한번에 여러개의 프로세스가 공유 자원을 사용할 수 있게 한다.

- 점유 대기 부정(제거) : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구

- 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.

- 순환( 환형 ) 대기 부정 : 자원을 선형 순서로 분류하여 고유번호 할당, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 한쪽 방향으로만 자원을 요구

 

회피

- 자원이 어떻게 요청될지에 대한 추가정보를 제공하도록 요구하는 것, 시스템에 circular wait가 발생하지 않도록 자원 할당 상태를 검사 

- 교착 상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법

 

1. 자원할당 그래프 알고리즘

2. 은행원 알고리즘 

<참고>

https://jhnyang.tistory.com/102

[운영체제]교착상태 회피-은행원 알고리즘(Banker's Algorithm) 쉬운 예시, 안전상태, 불안전상태

 

무시

예방 혹은 회피기법은 성능에 큰 영향을 미칠 수 있다.

데드락의 발생 확률이 비교적 낮은 경우 별다른 조치를 취하지 않는다.

 

발견

감시/발견을 하는 detection 알고리즘으로 Deadlock 발생을 체크하는 방식. 이 역시 성능에 큰 영향을 미칠 수 있다.

 

회복기법 (Recovery)

교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 기법

 

프로세스 종료 

방법 1. 교착 상태에 있는 모든 프로세스를 종료한다

방법 2. 교착 상태에 있는 프로세스를 하나씩 종료한다.

 

자원 선점

- 교착 상태에  있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지 시키는 방법

- 우선순위가 늦은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스 자원을 선점

 

자원 선점시 고려사항

1. 자원을 선점할 프로세스 선택 문제 : 최소의 피해를 줄 수 있는 프로세스를 선택

2. 자원을 선점한 프로세스의 복귀 문제 : 자원이 부족한 상태이므로 대부분 일시 정지 시키고 다시 시작하는 방법을 사용

3. 기아 현상 문제 : 한 프로세스가 계속하여 자원 선점 대상이 되지 못하도록 고려