[운영체제] 경쟁 상태 (Race Condition)

Letmegooutside·2022년 1월 13일

CS 운영체제

운영체제

목록 보기

11/16

Race Condition (경쟁상태)

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

공유 자원에 여러 프로세스가 동시에 접근할 때 자료의 일관성을 해치는 결과가 나타날 수 있다.

발생하는 경우

커널 코드 실행 중에 인터럽트가 발생할 경우
커널모드에서 데이터를 로드하여 작업을 하던 도중 인터럽트가 발생하여 같은 데이터를 조작하는 경우에 발생할 수 있다.
커널이 가진 전역변수는 모든 프로세스의 공유물이므로 경쟁상태의 가능성이 있다.
- 커널모드에서 작업을 수행하는 동안 인터럽트를 disable시켜 인터럽트가 CPU제어권을 가져가지 못하도록 하여 해결할 수 있다.
프로세스가 시스템 콜을 하여 커널모드로 진입해서 작업을 수행하는 도중에 문맥 교환이 발생할 경우
프로세스1이 커널모드에서 데이터를 조작하던 도중 시간이 초과되어 CPU제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우를 말한다.
- 프로세스가 커널모드에서 작업을 하는 경우에는 시간이 초과되더라도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 한다.
멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근할 경우
멀티프로세스 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우에 발생할 수 있다.
- 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해 lock/unlock함으로써 해결할 수 있다.

이밖에도 멀티스레드 환경에서 두 개 이상의 스레드가 공통의 전역변수에 접근할 경우 등에서 race condition이 발생할 수 있다

Critical Section(임계 영역)

운영체제에서 여러 프로세스가 데이터를 공유하면서 수행될 때 각 프로세스에서 공유 자원에 접근하는 프로그램 코드 부분 을 의미한다.

프로세스간에 공유자원을 접근하는데 있어서 문제가 발생하지 않도록 공유 자원의 독점을 보장해줘야 하는 영역이다.

임계 영역 문제를 해결하기 위해서는 아래의 3가지 조건을 충족해야한다.

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

임계영역 해결

유저모드의 동기화

유저 모드 동기화

커널의 힘을 빌리지 않는(커널 코드가 실행되지 않는) 동기화 기법

Pterson's Algorithm (피터슨 알고리즘)

// Pi
do {
  flag[i] = true;
   // 프로세스i가 지금 임계영역에 들어가고 싶다는 의미를 전달하기 위해 flag를 true로 바꿔준다.

  turn = j; // 1
  // 내가 들어가고 싶다고 선언해주고 j차례로 돌려줌으로써, 
  // 혹시 쓰고 싶은 다른 프로세스가 있나 확인한다.
  // 만약 프로세스j가 이 공유 자원을 쓰고 싶어서 
  // flag[j]=true; turn = i; 까지 실행한 상태라면 
  // i프로세스가 j프로세스로 차례를 넘겨주자마자 while문을 빠져나와 임계영역에 들어갈 것이다.
  // 즉 내가 쓰기 전에 먼저 쓰고 싶어했던 프로세스가 있는 지 
  // 확인하고 수행시켜주는 코드이다.

  while (flag[j] && turn == j); // 2 busy waiting
  // 임계영역에 들어가기 위해서는 내 차례여야 한다.
  // turn==j일 경우는 내 차례가 아닌데 j가 자원까지 쓰고 싶어한다면 
  // 나는 while문에서 머물어야 한다. 
  // 반면에 내 차례거나 j가 자원을 쓰고 싶지 않은 경우(flag[j]==false) 
  // 이제 while문을 빠져나와 진입할 수 있다.
  // 이렇게 turn과 flag변수를 이용해서 동시 접근을 막는다.
  
  // critical section  임계영역 진입

  flag[i]=false;  // 3 다 쓰고 나면 내 flag신호를 false로 바꿔준다.

  // remainder section

} while (true);

// Pj
do {
  flag[j] = true;      
  turn = i; 
  while(flag[i] && turn == i); 
  
  // critical section 
  
  flag[j] = false;  
  // remainder section
} while(1);

turn : ciritical section에 진입하는 프로세스 번호 (진입할 차례인 프로세스)
flag : ciritcal section에 진입할 준비가 되었는지 여부 (진입할 의사가 있는지 여부)

turn = j 는 store명령이므로 atomic한 성질을 가지고 있다. 따라서 동시에 접근하더라도 하드웨어에 의해 순서가 결정되므로 progress조건을 만족한다.
Pi가 ciritical section이면 flag[i] == true이므로 Pj에서 ciritical section에 진입할 수 없다. 따라서 mutual exclusion조건을 만족한다.
Pj가 turn=i, flag[j]=true로 지정하고 ciritical section에 진입해 있다.
그리고 Pi는 ciritical section에 진입하고자 flag[i] = true, turn = j로 지정하고 busy waiting을 하고 있다.
이 때 Pj가 critical section에서 빠져나와 flag[j]=false로 바꿔준다면, 대기하고 있던 Pi가 바로 ciritical section으로 진입할 수 있으므로 bounded-waiting 조건을 만족한다.