세마포어? 데드락?

데드락?

프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태를 말한다. 교착 상태라고도 한다.

 

프로세스 1,2가 각 자원 1,2를 모두 얻어야 한다고 가정한 상황이다.

t1 : 프로세스1이 자원 1을 얻음, 프로세스2가 자원 2를 얻음.

t2 : 프로세스1은 자원 2를 기다림, 프로세스2는 자원 1을 기다림.

두 프로세스 모두 원하는 자원이 상대방에 할당되어 있어 무한정 wait에 걸린다. 이러한 상황을 데드락이라 한다.

 

주로 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 경쟁하는 상황에서 발생한다.

프로세스가 자원을 요청했을 때 자원을 사용할 수 없어 대기상태에 들어가는데 대기 상태에서 실행 상태로 변경될 수 없을 때도 데드락이라 한다.

 

데드락 발생조건

1. 상호 배제 (Mutual Exclusion)

• 자원은 한번에 한 프로세스만 사용할 수 있다.

2. 점유대기 (Hold and Wait)

• 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야함

3. 비선점(No preemption)

• 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗아 올 수 없음.

4. 순환 대기 (Circular wait)

• 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함.

 

 

데드락 처리 방법

1. 예방

교착 상태 발생조건 중 하나를 제거하며 해결한다(자원의 낭비가 아주 크다)

• 상호배제 부정 : 여러 프로세스가 공유 자원을 사용한다.
• 점유대기 부정 : 프로세스 실행전 모든 자원을 할당한다.
• 비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 자진 반납.
• 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원을 요구한다.

2. 회피

교착 상태 발생시 피해나가는 방법

은행원 알고리즘

• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태를 회피 한다.
• 안정상태라면 자원을 할당하고, 아니라면 다른 프로세스들이 자원을 해제할 때 까지 대기한다.

3. 탐지

• 자원 할당 그래프를 사용하여 교착 상태를 탐지한다.
• 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드가 발생한다.

4. 회복

교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법.

 

프로세스 종료 방법

• 교착 상태의 프로세스를 모두 중지 시킨다.
• 교착 상태가 제거될 때 까지 하나씩 프로세스를 중지한다.

자원 선점 방법

• 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당
• 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 프로세스 자원 선점.

 

세마포어란?

멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법.

 

임계구역(Critical Section)

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분을 말한다.

 

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 대문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 막아야 한다.

 

세마포어 P,V 연산

• P : 임계 구역 들어가기 전 수행 (프로세스 진입 여부를 자원의 개수를 통해 결정)
• V : 임계 구역에서 나올 때 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

뮤텍스란?

임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술

상호 배제의 약자.

해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

 

lock : 현재 임계 구역에 들어갈 권한을 얻어 온다. ( 다른 프로세스 / 스레드가 임계 구역 수행중이면 종료까지 대기)

unlock : 현재 임계 구역을 모두 사용했음을 알림. ( 대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있다)

 

뮤텍스는 상태가 0,1 로 이진 세마포어라 부르기도 한다.