1. Race Condition
Race Condition(경쟁 상태)이란 공유 자원에 대해 여러 프로세스 혹은 스레드가 동시에 접근할 때, 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 의미한다.
(동시 접속 시 결과의 일관성을 해치는 결과가 나타난다.)
예를 들면, 다음 그림과 같다.
실제 X라는 공유 자원은 `30`이 저장되어야 하지만, 두 프로세스의 접근 타이밍이 서로 꼬여 `20`이 저장된다.
Critical Section
Ciritical Section(임계 영역)은 여러 프로세스 혹은 스레드가 공유 자원을 접근하려는 프로그램 코드 부분이다.
(앞으로 프로세스, 스레드의 경우를 통틀어 프로세스만 다루겠다.)
공유 자원을 여러 프로세스가 동시에 접근할 때, 위에서 언급한 Race Condtion이 발생할 수 있기 때문에, 한 프로세스가 Critical Section을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.
이 방법으로 Mutex Semaphore Monitor 이 3가지 방법이 있다.
올바른 Lock을 구현하기 위한 조건들
- 상호 배제(Mutual exclusion) : 임계 영역에는 한번에 오직 하나의 프로세스/스레드만 들어갈 수 있다
- 융통성(Progress) : 임계 영역에 들어가기를 기다리는 여러 프로세스/스레드들이 wait하고 있으면, 반드시 하나는 임계 영역에 들어가 있어야 한다 ↔ 만약 여러 프로세스/스레드들이 임게 영역을 기다리기만 하고, 임계 영역에 들어가 있는 프로세스가 없다면 Progress 성립 ✖
- 한정 대기(Bounded waiting) : 특정 프로세스가 임계 영역에 들어가지 못하는
Starvation이 있어서는 안된다
Mutex(뮤텍스)
여러 프로세스의 접근을 막기 위해 공유 자원을 Lock()하는 방식이다. 즉, Critical Section을 가진 프로세스들의 Running time이 서로 겨치지 않게 각각 단독으로 실행되게 하는 기술이다. 뮤텍스는 Lock/Unlock 상태만 갖는다.
뮤텍스는 Busy-wait Blocked 방식이다.
- Busy-wait : lock된 프로세스를 계속 흔드는 방식, Spinglock 이라고도 부름
- Blocked : lock을 기다리는 프로세스는 sleep하는 거와 같음
Semaphore(세마포어)
S라는 초기값을 가지고, 이 S은 공유 자원의 상태를 나타내기도 한다. 또한 Wait() Signal() 이 두 함수를 이용하여 여러 프로세스들이 공유 자원에 대한 접근을 처리한다.
- Wait() : 자신의 차례가 올 때까지 기다리는 함수 ♒ (S를 1 감소하고 S>=0 까지 기다린다)
- Signal() : 다음 기다리고 있는 프로세스에게 순서를 넘겨주는 함수 ♒ (S를 1 증가)
코드를 보면 이렇다.
procedure P(S) --> 최초 S값은 1임
while S=0 do wait --> S가 0면 1이 될때까지 기다려야 함
S := S-1 --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P
--- 임계 구역 ---
procedure V(S) --> 현재상태는 S가 0임
S := S+1 --> S를 1로 원위치시켜 해제하는 과정
end VS의 초기값에 따라 하나의 스레드만 들어가게 할 수도 있고 여러 개의 스레드가 들어가게 할 수 있다. 이것이 뮤텍스와의 차이이다.
DeadLock
데드락 예시
프로세스1과 2가 자원1, 2를 모두 얻어야 한다고 가정해보자.
- time1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음
- time2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림
현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐 → 이것이 바로 💣DeadLock💣
데드락 발생 조건
교착상태의 발생 조건은 아래 4가지를 모두 만족하는 것이다.
하나라도 만족하지 않으면 절대로 데드락이 발생하지 않는다.
- 상호 배제(Mutual exclusion)
- 하나의 자원은 한 번에 한 프로세스만 사용할 수 있다.
- 점유와 대기(Hold and wait)
- 어떤 프로세스가 하나 이상의 자원을 점유하고 있으면서 다른 프로세스가 가지고 있는 자원을 기다리고 있다.
- 비선점(No preemption)
- 프로세스가 태스크를 마친 후 자원을 자발적으로 반환할때까지 기다린다.(강제로 빼앗지 않는다)
- 순환 대기(Circular wait)
- 로세스의 집합에서 순환 형태🔁로 자원을 대기하고 있어야 한다.
하지만 데드락을 대처할 수 있다.
대처 방법은 크게 방지 회피 탐지 및 회복 이 있다.
🟡데드락 방지
데드락을 방지하기 위해서는 앞서 말한 4가지 조건중에 하나 이상을 불만족시키면 된다.
하지만 상호 배제, 점유와 대기, 비선점, 환형 대기 중 1가지 조건을 깨는 것은 쉽지 않다.
예)
- 상호 배제 ✖ : 여러 프로세스가 자원을 공유하게 되면서 의도치 않은 결과를 얻을 수 있다.
- 점유와 대기 ✖ : 자원이 오랫동안 할당되고 사용되지 않으면서 낭비될 수 있다.
- 비선점 ✖ : 공유 자원에 대한 동기화(상호 배제) 의미가 없어진다.
- 순환 대기 ✖ : 그나마 가장 가능성 있다. 순환이 아니라, 선형대기(예 : Queue)로 만들어서 공유 자원 사이에 순서를 정해주는 방법이다.
🟢데드락 회피
교착상태 회피 기법은 교착상태를 피해가는 기법이다.
대표적으로 은행원 알고리즘(Banker's Algorithm)이 있다.
은행원 알고리즘(Banker's Algorithm)
- 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
- 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
단점
- 불안정 상태(데드락 존재)로 예상되는 것들에 자원을 할당하면 안되므로, 자원 사용률이 떨어진다.
- 프로세스의 자원 요구량을 미리 파악한다는 것은 매우 어렵다.
🔵데드락 탐지 및 회복
교착상태 회복기법은 교착상태가 발생했을 때, 이를 탐지하고 해결하는 기법이다.
- 프로세스 종료 방법
- 교착 상태의 프로세스를 모두 종료한다.
- 교착 상태가 제거될 때까지 프로세스를 하나씩 종료한다.
- 자원 선점 방법
- 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다. (해당 프로세스 일시정지 시킴)
- 이때, 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점한다. (Starvation 방지 위해)
👍데드락 무시
사실 대부분 운영체제에서 사용하고 있는 방식은 무시이다.
왜냐하면 데드락의 발생 빈도는 굉장히 낮다. 하지만 데드락 방지를 위해 기능을 구현하는 것과 실행시키는 것은 비용 측면에서 매우 손해이다.
따라서 만약 데드락이 발생했다면 그냥 시스템을 껐다가 키는 것이 비용 측면에서 이득이다.
