Race Condition & Deadlock

Race Condition(경쟁 상태)

Race Condition이란?

 

공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결과값에 영향을 줄 수 있는 상태

=> 경쟁상태로 생기는 영역을 임계구역(Critical Section)이라고 함

 

ex) 동생이 은행에 20000원의 잔고가 있었고 10000원을 출금하고 있다. 그 사이 언니가 동생에게 용돈 7000원을 입금해주었다. 그렇다면 잔고는 얼마일까? 기대하는 잔고는 17000원!!

 

하지만 경쟁상태일 때,

동생의 입장: 현재 잔고 20000 - 10000 = 10000원

언니의 입장: 현재 잔고 20000 + 7000 = 27000원

 

해결하는 방법? Mutex, Semaphore, Monitor

 

DeadLock(교착 상태)

개념

 

두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태로 무한히 다음 자원을 기다리는 상황

 

 

프로세스 1과 2가 자원 1과 2를 모두 얻어야 한다고 가정

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

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

 

=> 두 프로세스는 결국 무한정 대기 상태(=DeadLock)에 빠짐

 

발생 조건

 

4가지 모두 성립해야 가능

1. 상호 배제(Mutual exclusion): 자원은 한번에 하나의 프로세스만 사용할 수 있음 
2. 점유 대기(Hold & Wait): 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 필요
3. 비선점(Non-Preemptive): 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다. 
4. 순환 대기(Circular Wait): 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 한다. (a는 b의 자원 요구, b는 c의 자원...)

 

해결 방법

1. 예방(Prevention)
   • 교착 상태가 발생하기 전에 미리 조치를 취하는 방식
   • 교착 상태 발생의 4가지 조건 중 어느 하나를 제거함
     • 상호 배제 조건 제거: 모든 자원의 공유 허용
     • 점유 대기 조건 제거: 필요한 모든 자원을 할당 
     • 비선점 조건 제거: 할당 받을 수 없는 자원을 요청할 때 점유하고 있는 모든 자원을 반납 후 대기 
     • 순환 대기 조건 제거: 자원에게 순서 부여하고 특정 방향으로만 자원을 요구하도록 함
   • 자원 낭비가 심함
2. 회피(Avoidance)
   • 교착 상태가 발생하기 전 교착 상태를 예측하고 회피
   • 교착 상태가 발생할 위험이 있는 자원이 생기면 자원 할당 요청 보류
   • 오버헤드 발생
   • Banker's Algorithm: 프로세스가 자원을 요청할 때 안전 상태를 유지할 수 있으면 자원 할당 or 보류
3. 탐지(Detection)
   • 교착 상태를 허용하되 탐지 알고리즘을 실행해 복구
   • 너무 자주 호출할 경우 오버헤드 발생 => 주기적으로 호출
4. 회복(Recovery)
   • 교착 상태를 일으킨 프로세스 모두 종료 or 교착 상태가 제거 될 때까지 한 프로세스씩 중지
   • 교착 상태가 제거될 때까지 프로세스가 점유한 자원을 선점해 다른 프로세스에 할당 

---

 

Q. 기아상태를 설명하는 식사하는 철학자 문제에 대해 설명하시오.

A. 5명의 철학자가 모두 동시에 배가 고파서, 각각 자신의 왼쪽 젓가락을 집을 경우 영원히 아무도 식사를 못함

 

Q. 해결방안?

A. 한 명의 철학자가 젓가락 2개를 모두 집을 수 있을 때만 젓가락 집도록 허용, 테이블에 최대 4명만 앉도록 허용

 

Q. 은행원 알고리즘의 단점?

A. 최대 자원 요구량을 미리 알고 있어야 하고 항상 불안전 상태라 자원 이용도가 낮다.

 

 

 

참고

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/DeadLock.md

https://velog.io/@tjdtn0219/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9CRace-Condition%EA%B3%BC-DeadLock-feat.%EB%AE%A4%ED%85%8D%EC%8A%A4-%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4

velog

 

https://dockdocklife.tistory.com/entry/Dead-lock%EA%B3%BC-%ED%95%B4%EA%B2%B0-%EB%B0%A9%EB%B2%95

Dead-lock과 해결 방법