Race Conditions, Deadlocks, Process Starvation

Race Condition (경쟁 상태)

두 개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓸 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황
두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황을 말함

 

 

Critical Section (임계 영역)

• 운영체제에서 여러 프로세스가 데이터를 공유하면서 수행될 때 각 프로세스에서 공유 자원에 접근하는 프로그래밍 코드 부분을 의미
• 프로세스간에 공유자원을 접근하는데 있어서 문제가 발생하지 않도록 공유 자원의 독점을 보장해주어야 하는 영역

 

 

임계 영역 문제을 해결하기 위한 3가지 조건

• Mutual Exclusion (상호 배제)
  한 프로세스가 자신의 임계 영역이면 다른 프로세스들은 임계영역에 진입할 수 없음
• Progress (진행)
  아무도 임계 영역에 있지 않다면, 진입하고자 하는 프로세스를 진입하게 해줘야 함
  임계영역에 아무도 진입하지 못하면 안되며 다음에 어떤 프로세스가 임계 영역에 진입해야 하는지는 유한한 시간에 결정되어야 함
• Bounded Waiting (유한 대기)
  프로세스가 임계영역에 집입하기 위해 무한정으로 기다리는 현상이 발생해서는 안됨

 

 

Race Condition 해결방안

Semaphore

• 공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 것
• 리소스의 상태를 나타내는 간단한 카운터
  • 일반적으로 비교적 긴 시간을 확보하는 리소스에 대해 이용하게 되며, 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에서 행동을 조정하거나 동기화 시키는 기술
• 하나의 스레드만 들어가게 할 수도 있고 여러 개의 스레드가 들어가게 할 수 있음
  • Mutex와의 차이점

 

 

Mutex

• 공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막는 방법
• 임계 영역을 가진 쓰레드들의 Running time이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술
• 다중 프로세스들이 공유 리소스에 대한 접근을 조율하기 위해 locking과 unloking을 사용
  • 상호배제를 함으로써 두 쓰레드가 동시에 사용할 수 없다는 것

 

 

 

Deadlock

• 상호 배제를 시행하면 추가적인 제어 문제가 발생
• 프로세스가 각자 프로그램을 실행하기 위해 두 자원 모두에 엑세스 해야 한다고 가정할 때 프로세스는 두 자원 모두를 필요로 하므로 필요한 두 리소스를 사용하여 프로그램을 수행할 때까지 이미 소유한 리소스를 해제하지 않음
• 이러한 상황에서 두 프로세스는 교착 상태에 빠지게 됨

 

 

Deadlock 발생조건

1. Mutual exclusion (상호 배제)

•  매 순간 하나의 프로세스만이 자원을 사용할 수 있음

 

2. Hold and wait (보유 대기)

•  자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유하고 있는 자원을 놓지 않고 계속 가지고 있음

 

3. No preemption (비선점)

•  프로세스는 OS에 의해 강제로 자원을 빼앗기지 않음

 

4. Circular wait (순환 대기)

•  자원을 기다리는 프로세스 간에 사이클이 형성되어야 함

 

교착 상태 예방

교착 상태 발생 조건 중 하나를 제거하면서 해결

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

-> 자원 낭비가 시함

 

 

교착 상태 회피

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

 

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

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

 

교착 상태를 탐지 및 회복

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

 

탐지

• 자원 할당 그래프를 통해 교착 상태를 탐지함
• 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함

 

회복

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

 

 

프로세스 종료 방법

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

 

자원 선점 방법

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

 

 

Starvation

• 프로세스들이 더 이상 진행을 하지 못하고 영구적으로 블록되어 있는 상태
• 시스템 자원에 대한 경쟁 도중에 발생할 수 있고 프로세스 간의 통신 과정에도 발생할 수 있는 문제
• 프로세스의 우선순위가 낮아서 필요한 자원을 결코 할당받지 못하고 계속 기다리고 있음

 

Starvation 해결방안

우선순위 변경

• 프로세스 우선순위를 수시로 변경해서 각 프로세스가 높은 우선순위를 가질 기회를 줌
• 오래 기다린 프로세스의 우선순위를 높여줌
• 우선순위가 아닌 요청 순서대로 처리하는 FIFO 기반 요청 큐를 사용