경쟁상태(Race condition) 2

Posted May 5, 2024 Updated May 11, 2024

By Blake Woo 12 min read

경쟁 상태 해결법

소프트웨어적 방법

종류

1 Dekker’s Solution

스레드가 두 개일때 사용가능한 방법으로 최초의 상호 배제 알고리즘이다. 이 알고리즘은 상호 배제, 교착 상태 방지, 기아 방지를 보장한다.

의사 코드는 아래와 같다.

// 스레드들을 포함한 프로세스에서 정의
bool WTE[2] ={false, false} // 모두 false로 초기화
int turn = 0

// 스레드 0
while(true) {
  WTE[0] = true
  while (WTE[1]) {
    if (turn != 0) {
       WTE[0] = false
       while (turn == 1) {
          // busy wait
       } 
       WTE[0] = true
    }
  }
  
  // Critical Section
  
  WTE[0] = false
  turn = 1
  
  // Remainder Section
}

// 스레드 1
while(true) {
  WTE[1] = true
  while (WTE[0]) {
    if (turn != 1) {
       WTE[1] = false
       while (turn == 0) {
          // busy wait
       } 
       WTE[1] = true
    }
  }
  
  // Critical Section
  
  WTE[1] = false
  turn = 0
  
  // Remainder Section
}

접근 요청에 대한 정보를 담을 WTE(Want to enter) 배열과 실제로 지금 누가 접근할 차례인지를 나타내는 turn 변수가 있다.

각 스레드는 접근을 원할 시에 WTE에 자신이 접근 요청을 원한다는 정보를 입력 후 자신의 턴이 아니라면
WTE에 요청 정보를 삭제하고 자신의 턴이 돌아올때까지 busy wait을 계속한다.
자신의 턴이 돌아온다면 WTE값에 자신이 접근을 원한다는 정보를 입력 후에 임계 영역으로 접근한다.
이후 임계 영역에서 작업을 다 했다면 WTE에 자신의 정보를 삭제 후 다른 스레드의 턴으로 넘긴다.

이런 데커의 방식은 두 개의 스레드일때 밖에 사용할 수 없는데, 개인적으로 추정하기로는
만약 2 초과의 다수의 스레드 일때 스레드 0에서

...
    while (WTE[1]) {
...

이부분이 WTE[i]에 대해서(i는 0이 아닌 수)에 대한 체크가 이루어져야할 것인데 이 과정은 반복문을 통해서 이루어질 것이고 반복문을 도는 과정에서 WTE 값을 레지스터에 불러와서 체크하는 과정에서 WTE 값들이 변경될 수 있기 때문에 2 초과의 다수 스레드에서는 사용불가능한게 아닌가 싶다.

2. Peterson’s Solution

이 역시 상호 배제를 위한 알고리즘으로 초기 발표에는 2개의 스레드에 대해서 사용가능한 형태로 발표되었다. 기본적으로 데커의 방법과 크게 다르진 않다. 의사 코드는 아래와 같다.

bool WTE[2] ={false, false} // 모두 false로 초기화
int not_my_turn = 0

// 스레드 0
while(true) {
  WTE[0] = true;
  not_my_turn = 0;
  
  while( WTE[1] && not_my_turn == 0); // 대기
  
  //Critical Section
  
  WTE[0] = false;
  
  //Remainder Section
}

// 스레드 1
while(true) {
  WTE[1] = true;
  not_my_turn = 1;
  
  while( WTE[0] && not_my_turn = 1); // 대기
  
  //Critical Section
  
  WTE[1] = false;
  
  //Remainder Section
}

스레드 0을 기준으로 설명을 해보자
스레드 0가 임계 영역에 접근하기 위해 WTE 값을 true로 바꾼다. 그리고 not_my_turn을 true로 변경한다. 그럴 경우 스레드 1이 WTE가 true이면서 not_my_turn이 0인지 확인한다. 이 말인 즉슨 스레드 1이 접근 요청을 한 것인지 확인한 것이며 스레드 1이 접근 요청을 하지 않았다면 스레드 0이 임계 영역으로 돌입하게 된다. 그렇게 되면 스레드 0이 접근 중일때는 스레드 1이 접근할수가 없다면 왜냐하면 스레드 1이 접근하려고하면 not_my_turn이 1로 세팅되어 while 문에서 기다리게 되기 때문이다. 스레드 0가 임계영역을 처리하고 지나면 WTE 값을 false로 바꾸게 되고 비로소 스레드 1이 임계영역에 접근 할수 있게 된다.

소프트웨어적인 방법의 문제

1. spin lock(busy wait)

데커의 방법과 피터슨의 방법은 둘 다 busy wait을 사용한다. 이는 cpu를 계속 사용하면서 대기하는 것이기 때문에 낭비가 크다.

특히 싱글 코어에서 이런 프로그램이 돌아간다고 가정하면 한 개의 코어가 두 개의 스레드를 멀티 태스킹하고 있는 상황에서 가령 피터슨 방법을 사용하고 있다면 아래와 같은 상황이다.

RR로 스케줄링이 되고 있다고 할때 T0가 임계영역에서 컨텍스트 스위칭할 경우 T1은 busy wait만 할 수 밖에 없다.

2. 성능 문제

아무래도 소프트웨어로 구성되어있는 것은 회로로 구성된 것보다 느리다. 그렇기 때문에 하드웨어로 구성할 수 있다면 하드웨어로 구성하는게 성능상 바람직하다.

3. 최적화 불가

현대 컴파일러는 성능의 최적화를 위하여 코드를 컴파일할때 의도적으로 순서를 변경하기도 한다. 그럴 경우 순서가 중요한 코드의 순서가 변경되어버리면 기아현상이 발생하거나 데드락이 발생 할 수 있다. 물론 컴파일 옵션으로 최적화 금지를 넣게 되면 그대로 구동은 할 수 있지만 그렇게되면 다른 코드에 대한 성능이 떨어져 바람직하지 않다.

하드웨어적 방법

프로세서의 인터럽트 방지

싱글 프로세서에서는 효과적일 수 있음
멀티 프로세서의 경우 확장성이 떨어지고 효과적이지 않음

원자적 실행 보장 명령 도입

하드웨어적으로 원자적 실행을 보장하는 명령을 지원한다.

1. 메모리 값을 검사하고 설정

TestAndSet 함수는 하드웨어적으로 원저적 실행을 보장한다. 함수의 의사 코드는 아래와 같다.

bool TestAndSet (bool* target) {
  bool rv = *target;
  *target= true; // 입력된 target을 true로 바꾼다. 
  return rv; // 입력된 값의 이전 값을 반환한다.
}

TestAndSet을 도입했을 때 다음과 같은 코드라면 임계영역의 상호배제를 보장할 수 있다.

// lock은 전역 변수

while(true) {
  while(TestAndSet(&lock));
  
  // Critical Section
  
  lock = false;
  
  // Remainder Section
}

만약 2개의 스레드라면 상호배제에 교착 상태 방지, 기아까지 다 방지가 되겠지만 스레드가 3개 이상이라면 기아 현상에 맞닥들일수도 있다. 요청 순차에 따른 처리가 보장되어있지 않기 때문이다. 그렇기 때문에 스레드가 3개 이상일 경우 queue를 하나 추가해준다면 이러한 기아 현상을 방지할 수 있다.

// 스레드 i의 경우
bool lock = false
bool waiting[n] = false // 전체 false
bool key = false

while(true) {
  waiting[i] = true
  key = true
  
  while(waiting[i] && key)
    key = TestAndSet(&lock)
  
  // Critical Section
  
  j = (i+1) % n;
  while ((j!=i) && !waiting[j])
    j = (j+1) % n;
    
  if (j==i) {
    lock = false;
  }
  else {
    waiting[j] = false;
  }
  
  // Remainder Section
}

2. 메모리 영역 SWAP

다음 함수는 원자적 실행이 보장된 함수이다.

void Swap (boolean *a, boolean *b)  // lock and key
{
  boolean temp = *a; 
  *a = *b;
  *b = temp: 
}

Swap 함수로 임계 영역 제한을 구현하면 아래와 같다.

// 전역 함수로 lock은 false로 초기화
boolean lock = false

while(true) {
  key = TRUE;
  while ( key == TRUE) {
    Swap (&lock, &key );  // 원자적 실행을 보장하는 함수인 Swap으로 lock과 key를 교체
  }
    
  // Critical Section 
  lock = FALSE;
  
  // Remainder Section 
}

이러한 방법은 상호 배제 문제는 해결되나 제한된 대기는 해결 할수 없다.

참고 자료

Operating System Concept (written by Silberschatz, Galvin and Gagne)
동기화 방법 1 : Peterson’s solution - 운동개발좋아

Computer science

Computer science OS

This post is licensed under CC BY 4.0 by the author.