[OS] 교착 상태(Deadlock)

Q . 교착 상태란?

둘 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하여, 무한 대기하는 상태

 

Deadlock

 

- 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생함.

 

 

 

Q . 교착 상태의 발생 조건이란?

4가지 조건이 존재하며, 모든 조건이 충족되어야 교착 상태가 발생함.

 

 

1. 상호 배제(Mutual exclusion)

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

 

 

2. 점유 대기(Hold and wait)

최소한 하나의 자원을 점유하고 있는 동시에, 

다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함.

 

 

3. 비선점(No preemption)

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

 

4. 순환 대기(Circular wait)

대기 프로세스들이 순환하는 형태로 다음 자원을 대기하고 있는 상태를 말함.

 

 

모든 조건들이 충족되는 경우를 위에서 확인 가능함.

 

 

Q . DeadLock 해결 방법이란?

 

교착 상태를 예방/회피

- 교착 상태가 발생하기 전 가능성을 제하는 해결 방식.

 

1. 예방(prevention)
교착 상태 발생 조건 중 하나를 제거하며 해결함

 

-> (-) 자원 낭비가 심함.

 

2. 회피(Avoidance)
교착 상태 발생을 피하는 방식

 

안정 상태(Safe state) : 프로세스들이 요청하는 모든 자원을 교착 상태 없이 할당 가능한 상태

안전 순서(Safe sequence) : 프로세스들에게 자원을 할당하는 작업을 할 때 교착 상태가 발생하지 않는 특정 순서

 

-> 자원의 할당 후에도 시스템이 항상 safe state에 있을 수 있도록 자원을 할당하는 방식

 

Q . Banker's Algorithm

- 은행원 알고리즘(Banker's Algorithm)

  - 다익스트라 알고리즘에서 기반함

  - 프로세스의 자원 요구가 있을 때, 자원 할당 후에도 safe state로 남아 있는지 시뮬레이션하여 교착 상태를 회피함.

  - 대기 중인 모든 프로세스들에 대하여 교착 상태 가능성을 조사함

  - 안정 상태이면 자원을 할당하고, 아닐 시에는 다른 프로세스가 자원을 해지할 때까지 대기함.

 

 

 

교착 상태를 탐지/회복

- 교착 상태가 되는 것을 허용하며, 그 후 회복을 위해 교착 상태를 탐지하고, 회복하는 해결 방식

 

1. 탐지(Detection)

자원 할당 그래프(위의 그림과 동일!!)를 통하여 교착 상태를 탐지함.

(사이클 o -> 교착 상태 o)

자원 요청 시, 탐지 알고리즘을 실행시킴 

 

2. 회복(Recovery)

탐지 기법을 통하여 교착 상태를 발견한 후, 회복하기 위한 방식을 사용

교착 상태를 일으킨 프로세스를 종료하거나(1), 할당된 자원을 해제(2)시켜 회복함.

 

(1) 프로세스 종료

 

 1) 교착 상태에 빠진 모든 프로세스를 중단

 

 2) 교착 상태가 해결될 때까지 하나씩 프로세스를 중지함

  프로세스들을 하나씩 중단시킬 때마다 탐지 알고리즘을 호출, 교착 상태를 탐지하며 회복

  -> 이에 따른 오버헤드가 존재

 

 

(2) 할당된 자원을 해제

이미 할당된 자원을 교착 상태가 해결될 때까지 다른 프로세스에 할당한 후, 되돌려 주는 방식

 

 

 

 

++

Q . 뮤텍스와 스핀락이란?

다수의 프로세스가 공유 중인 자원을 동시에 수정할 때 생기는 "동기화 문제" 를 해결하는 방식 

상호 배제(mutual exclusion)과 연관이 있음.

 

 

임계 구역(Critical section)

프로세스 간 공유 자원에 접근할 때 문제가 발생하지 않도록 접근을 제한하는 영역

lock - unlock

임계 구역에 접근 - 임계 구역에 접근하지 못함

세마포어(Semaphore)

 

 

스핀락

특정 자원에 대한 접근 권한을 획득(lock)하기 전,

busy waiting 상태로 접근 가능할 때까지 재시도하는 방식으로 대기하며,

권한을 획득한 후엔 내부 코드 작업을 수행하고 종료 후에는 권한을 해제(unlock)하는 방식으로 작동함

 

 

-> 스레드에 대하여 문맥 교환(context switching)가 일어나지 않음

--> 선점 기간 동안에는 다른 프로세스의 작업이 지연될 수 있음

 

wait(S){
	//busy waiting
	while(S<=0);
    
	//lock
	S--;
}

//unlock
signal(S){
	S++;
}

 

--> 짧게 수행될 수 있는 작업에 대하여 주로 사용됨.

 

 

뮤텍스(Mutex, MUTual EXclusion)

접근 권한 획득(lock) 전에는 sleep 상태로 대기하며,

wakeup 후에 권한 획득을 시도함

 

do{
	//sleep(대기 상태)
	wait(mutex);
    
	//**
    
	대기 상태 종료 후 lock
	critical section
    
	**//
    
	//unlock
	signal(mutex);
    
}while(true);

 

Q . 스핀락과 뮤텍스 방식의 공통점

자원의 획득(lock) 해제(unlock)를 통하여 공유 자원에 대한 접근 권한을 관리함

 

 

 

Q . 스핀락과 뮤텍스 방식의 차이

lock 상태를 갖기 전 대기할 때, 

스핀락 방식은 busy-waiting 상태로 대기하며, 다른 작업을 하지 않음(context switching을 하지 않음)

뮤텍스 방식의 경우에는 자원의 접근을 대기할 때 다른 작업을 동시에 진행하며 대기함(context switching)

 

 

 

 

 

 

---

[OS] 스핀락(Spinlock), 뮤텍스(Mutex), 세마포어(Semaphore)의 특징과 차이점 :: 코딩 공부 일지 (tistory.com)

[OS] 스핀락(Spinlock), 뮤텍스(Mutex), 세마포어(Semaphore)의 특징과 차이점

 

스핀락(Spin lock), 뮤텍스(Mutex), 세마포어(Semaphore) 알아보기 (tistory.com)

스핀락(Spin lock), 뮤텍스(Mutex), 세마포어(Semaphore) 알아보기

 

Re: 제로부터 시작하는 블로그 생활 :: 스핀 락(Spin lock)과 뮤텍스(Mutex)의 차이 (tistory.com)

스핀 락(Spin lock)과 뮤텍스(Mutex)의 차이

 

[운영체제] 데드락(Deadlock, 교착 상태)이란? | ChanBLOG (chanhuiseok.github.io)

[운영체제] 데드락(Deadlock, 교착 상태)이란?