Race Condition

Race Condition?

이전의 글에서 Thread에 관련하여 작성하였다. 그 안에는 동기화와 관련된 내용도 있는데 본 글은 동기화를 할때 생기는 상황들에 대해서 설명해 보겠다. 먼저, 레이스 컨디션이란 두개 이상의 스레드나 프로세스가 하나의 자원을 두고 경쟁하는 상황을 말한다. 이를 해결하기 위해 임계영역을 생성해 하나의 자원에는 하나의 스레드만 접근할 수 있도록 동기화를 해준다. 

 

세마포어 뮤텍스?

이때 동기화 방법에는 세마포어와 뮤텍스가 있는데, 둘의 가장 큰 차이는 동기화 대상의 개수이다. 세마포어인 경우 동기화의 대상이 여러개로 임계영역에 들어갈 수 있는 프로세스나 스레드의 개수를 카운트로 표시해 카운트 값에 따라 스레드나 프로세스가 임계영역에 접근할 수 있다. 반면 뮤텍스의 경우 임계영역에 한개의 스레드만 접근이 가능하여 해당 스레드의 작업이 종료 될때 까지 다른 스레드는 접근이 불가능 하다.

DeadLcok?

근데 동기화를 하는 상황에서 1번 스레드와 2번 스레드가 a라는 공유 자원에 접근을 하려면 어떻게 될까? 일반적으로 1번 스레드가 a에 접근을 한 후 작업이 끝난 후 2번 스레드가 a에 접근을 할 것이다. 근데 만약 1번 스레드가 a라는 자원을 갖고 있고, 2번 스레드가 b라는 자원을 갖고있는 상황에서 1번스레드가 b자원을 필요로 하고, 2번스레드는 a자원을 필요로 한다면 1번 스레드와 2번 스레드 모두 서로의 작업이 끝나기를 대기하는 상황이 발생할 것이다. 이러한 상황을 DeadLock이라고 한다. 

 

이를 바탕으로 데드락의 발생하는 조건은 다음과 같다.

1. 상호 배제(Mutual exclusion)자원은 한번에 한 프로세스만 사용할 수 있음
2. 점유 대기(Hold and wait)최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함
3. 비선점(No preemption)다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
4. 순환 대기(Circular wait)프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

데드락에 대한 처리는 다음과 같이 예방하거나 회피 할 수 있다.

 

1. 예방

 

예방(prevention)교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)

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

2. 회피

 

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

 

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

• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
• 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

교착 상태를 탐지 & 회복

교착 상태가 되도록 허용한 다음 회복시키는 방법

1. 탐지(Detection)자원 할당 그래프를 통해 교착 상태를 탐지함
2. 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함
3. 회복(Recovery)교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
4. 프로세스 종료 방법
   • 교착 상태의 프로세스를 모두 중지
   • 교착 상태가 제거될 때까지 하나씩 프로세스 중지
   자원 선점 방법
   • 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
   • 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

starvation?

위에서 말한 예방책중에 순환대기 부정이라는 예방책이 있었다. 하지만 고유 번호를 부과하더라도 순위에서 계속 밀리는 상황이 생길 수 있고, 이러한 상황에서 특정 프로세스나 스레드가 원하는 자원을 계속해서 얻지 못하는 경우를 기아상태라고 한다.

 

일반적으로 기아상태는 다음과 같은 스케줄링 방법에서 발생한다.

SJF(Shortest - Job - First) : 이 스케줄링은 극단적으로 CPU 사용이 짧은 job을 선호하기 때문에 사용 시간이 긴 프로세스는 거의 영원히 CPU를 할당 받을 수 없다.

SRT(Shortest Remaining time First) : 새로운 프로세스가 도달할 때마다 남은 burst time보다 더 짧은 CPU burst time이 있다면 선점하기 때문에 긴 burst time을 가진 프로세스는 영원히 할당 받을 수 없다.

 

해결

기아상태는 우선순위를 변경함으로서 해결할 수 있다. 우선순위 알고리즘을 수시로 바꾸어 주거나, 먼저 한 요청 먼저 처리를 하거나, 가장 오래 기다린 자원부터 처리를 하는 방식으로 바꿔주면 된다.