임계구역 문제 해결 방법

hongo·2024년 2월 27일

운영체제

목록 보기

4/10

경쟁 상황(Race condition)과 임계 구역(Critical section)

커널 데이터, 공유메모리등 여러 프로세스가 공유 자원을 동시에 읽고 쓰는게 가능하다면, 예상치못한 결과를 도출할 수 있다. (ex. 공유 변수 count의 값이 5일 때, 프로세스A는 count--을 하고, 프로세스B는 count++을 할 경우, 프로세스A와 B가 어떤 시점에 변수를 읽고 쓰냐에 따라 count의 값이 달라진다. 4 or 5 or 6 )

이처럼 여러 개의 프로세스가 공유 자원에 접근하고, 코드의 실행 순서에 따라 결과가 달라지는 상황을 경쟁 상황(Race condition)이라고 한다. 그리고 경쟁 상황이 발생할 수 있는 코드의 묶음을 임계 구역(Critical section)이라고 한다.

각 프로세스가 임계 구역을 독립적으로 실행해야, 예상치못한 결과를 막을 수 있다! 때문에 프로세스를 어떤 순서로 임계 구역에 들여보내, 안전하게 동기화를 할지 여러 해결방안들이 있는데, 이것을 알아보자~

임계구역 문제 해결안의 세가지 요구 조건

상호 배제(Mutual exclusion) : 특정 프로세스가 임계 구역에서 실행되고 있다면, 다른 프로세스가 침범할 수 없다.
진행(Progress) : 임계 구역에서 실행중인 프로세스가 아무도 없을 때, 임계 구역에서 실행하고자 하는 프로세스가 있다면 그 중 하나는 임계 구역에 들어갈 수 있어야한다.
한정된 대기(Bounded Waiting) : 프로세스가 임계 구역에 들어가기 위한 대기시간이 무한대일수는 없다.

피터슨 알고리즘 - 소프트웨어적인 방법!

피터슨 알고리즘은 두 개의 프로세스가 있을 때, 사용할 수 있는 임계구역 문제 해결방법이다.

프로세스0과 프로세스1이 존재한다고 가정하겠다.

// 프로세스i의 코드

me = i;
other = 1-i;

while(true) {
  flag[me] = true;
  turn = other;
  while(flag[other] && turn == other) {
    // 대기! 
  }
  크리티컬 섹션 실행
  flag[me] = false;
}

위 알고리즘을 사용하면 임계구역 문제를 해결할 수 있다!

물론 여전히 문제가 존재하긴 하는데, busy waiting과 최신 컴퓨터 아키텍처에서는 동작을 보장할 수 없다 는 문제가 있다.

Busy waiting은 프로세스가 할당받은 cpu자원을 대기하는 데만 사용하는 것을 의미한다. while(flag[other] && turn == other)조건이 충족되어있다면 해당 프로세스는 언젠가는 크리티컬 섹션을 실행할 수는 있겠지만, 한 클럭동안 계속 기다릴수도 있는 것이다.

스핀락 : 위 코드처럼 락을 사용할 수 있을 때까지 대기하는 방식을 의미한다.

오래 대기하면 Busy waiting 문제가 발생하기에 락이 짧은 시간동안 유지될 때 많이 사용되는 방식이다. (근데 짧을지 길지 어떻게 앎? 통계로 때려맞추는거임?)

"락이 짧은 시간동안 유지된다"의 기준은 문맥 교환을 두 번하는 시간보다 짧은 경우를 의미한다고 한다.

왜 두 번의 문맥 교환인가? : 락을 기다려야할 경우 두 번의 문맥 교환이 필요하기 때문

대기 상태로 변경되는 문맥

락이 사용가능해지면 대기를 풀기위한 문맥

최신 컴퓨터 아키텍처에서는 동작을 보장할 수 없다 는 문제도 있는데, 특정 아키텍처에서는 성능을 향상하기 위해 종속성이 없는 코드의 순서를 재정렬할수도 있기 때문이다.

예를 들어 프로세스 i의 코드만 봤을 때 flag와 turn은 서로에게 영향을 주지않는, 종속성 없는 변수이므로 (1)과 (2) 코드의 줄이 재정렬이 되어 (2)가 앞으로 갈 수도 있다! 뭐이런등신같은

// 프로세스i의 코드

me = i;
other = 1-i;

while(true) {
  flag[me] = true; // (1)
  turn = other; // (2)
  while(flag[other] && turn == other) {
    // 대기! 
  }
  크리티컬 섹션 실행
  flag[me] = false;
}

그렇다면 코드는 아래처럼 변경되는데, 이 경우 상호 배제 조건을 만족하지 못한다.

me = i;
other = 1-i;

while(true) {
  turn = other; // (2) 
  flag[me] = true; // (1)
  while(flag[other] && turn == other) {
    // 대기! 
  }
  크리티컬 섹션 실행
  flag[me] = false;
}

프로세스0이 먼저 실행되었다고 해보자!

[프로세스0 실행중] turn = 1 <- 여기서 할당된 cpu사이클이 끝나 프로세스 1에게 cpu가 넘어갔다고 해보자!
[프로세스1 실행중] turn = 0
[프로세스1 실행중] flag[1] = true
[프로세스1 실행중] 프로세스1이 크리티컬 섹션에 진입 <- flag[0]이 false라서 while문 빠져나옴
[프로세스0 실행중] flag[ 0 ] = true
[프로세스0 실행중] 프로세스0이 크리티컬 섹션에 진입 <- turn이 0이라서 while문 빠져나옴

프로세스 0과 1이 동시에 크리티컬 섹션에 들어가는 상황이 생길수도 있다!

메모리 장벽 (Memory Barriers)

그러나 시스템에는 메모리 장벽(== 메모리 모델)이라는 것이 존재하는데...

메모리의 변경사항을 모든 프로세스에게 전파하는 명령어이다. 메모리 장벽 명령어가 실행될 때, 시스템은 이후 코드에서 저장연산이 수행되기 전에 현재 시점의 모든 저장연산을 완료한다고 한다. 그래서 코드가 재정렬되더라도... 뭐.. 알아서 순서대로 잘 저장하는듯...

다음과 같이 메모리 장벽 명령어를 사용해서 최신 컴퓨터 아키텍처에서는 동작을 보장할 수 없다 문제를 해결할 수 있다.

me = i;
other = 1-i;

while(true) {
  flag[me] = true; // (1)
  memory_barrier(); // 메모리 장벽
  turn = other; // (2)
  while(flag[other] && turn == other) {
    // 대기! 
  }
  크리티컬 섹션 실행
  flag[me] = false;
}

turn이나 flag를 둘 다 사용해야하나? 하나만 사용하면 안되나?

me = i;
other = 1-i;

while(true) {
  flag[me] = true; // P0이 여기까지 실행한 후에 P1로 컨텍스트 스위칭된다면,
  while(flag[other]) { // P0과 P1의 flag 둘 다 true이므로 P0과 P1은 계속 서로의 flag가 false가 될 때까지 대기해야 함 - 한정된 대기 조건이 충족되지 않는다
    // 대기! 
  }
  크리티컬 섹션 실행
  flag[me] = false;
}

me = i;
other = 1-i;

while(true) {
  turn = other;
  while(turn == other) {
    // 대기! 상대 프로세스가 turn을 내 것으로 만들어주지않는 이상 평생 대기
  }
  크리티컬 섹션 실행
}

test_and_set과 compare_and_swap - 하드웨어적인 방법!

test_and_set과 compare_and_swap은 하드웨어에서 지원하는 원자적인 연산이다. 둘 다 어떤 변수의 값을 테스트하고, 새로 설정하는 작업을 하나로 묶어 원자적으로 실행하는 함수이다.

test_and_set을 사용한 문제 해결 예시

boolean test_and_set(boolean *target) {
  boolean rv = *target;
  *target = true; // 새로운 값으로 설정
  return rv; // 오리지널 값 반환
}

while(true) {
  while(test_and_set(&lock)) {
  	// 대기
  }
  크리티컬 섹션 실행
 	lock = false;
}

-> 두 프로세스가 동시에 test_and_set(&lock)을 실행하면 하나는 true가 반환되고, 하나는 false가 반환되어서 한 프로세스만 크리티컬 섹션에 진입한다.

-> 크리티컬 섹션을 끝낸 프로세스가 lock을 false로 바꿔주기전까지 다른 프로세스들은 test_and_set에서 true가 반환되어 계속 대기한다.

compare_and_swap을 사용한 문제 해결 예시

int compare_and_swap(int *value, int expected, int new_value) {
  int temp = *value;
  if (*value == expected) {
    *value = new_value; // 새로운 값으로 설정
  }
  return temp; // 오리지널 값 반환
}

while(true) {
  while(compare_and_swap(&lock, 0, 1)) {
  	// 대기
  }
  크리티컬 섹션 실행
 	lock = false;
}

한정된 대기 문제까지 해결한 방법

위 두가지 방식은 상호배제와 진행은 만족하지만, 한정된 대기 조건은 만족하지 않는다. 프로세스0이 대기중인데 운좋게 다른 프로세스들만 계속 락을 얻을수도 있기 때문.

한정된 대기 문제를 해결하려면 아래와 같이 변형해볼 수 있다. waiting이라는 배열을 추가하여 프로세스의 대기 상태를 저장하고, 각 프로세스가 크리티컬 섹션을 끝낼 때, waiting 배열을 차례대로 순회하며 대기중인 프로세스에게 임계구역에 들어갈 수 있는 권한을 넘긴다. 이렇게 하면 프로세스들은 최대 n-1개의 프로세스가 한 번씩 임계구역에 들어가는 것만 대기하면 자신의 차례가 오는 것을 보장할 수 있다.

waiting[n]; // 전부 false로 초기화
lock = false;

me = i;

while(true) {
  localLock = true;
  waiting[me]
    
  while(waiting[me] && localLock == true) {
  	localLock = compared_and_set(&lock, 0, 1)
  }
  
  waiting[me] = false;
  크리티컬 섹션 실행
    
  nextProcess = (me + 1) % n;
  while((nextProcess!=me) && !waiting[nextProcess]) {
    nextProcess = (nextProcess + 1) % n;
  }
  
 	if (nextProcess == me) { // 대기중인 프로세스가 없다면
    lock = false; // 락만 풀어두고 종료
  }
  else { // 대기중인 프로세스가 있다면
    waiting[nextProcess] = false; // 해당 프로세스의 대기를 풀어줌
  }
}