[OS] Critical section (임계구역), test_and_set, compare_and_swap

Critical Section(임계 구역)

두 개 이상의 thread 가 동시에 접근하면 안되는 영역을 말함. 여러 스레드가 동시에 공유 자원에 접근하고, 이에 수정을 가하는 경우 원하지 않는 결과가 도출될 수 있기 때문에 정의된 영역임

 

while (true) {
  <Entry section, 진입 영역>
  <Critical section, 임계 영역>
  <Exit section, 진출 영역>
  <Remainder section, 나머지 영역>
}

 

Critical section 문제를 잘 해결하지 않으면 서로 다른 프로세스에서 fork() 함수가 동시에 호출되었을 때 두 프로세스가 동시에 Process descriptor 로부터 pid 를 할당받게되고, 둘이 같은 pid 를 할당 받을 수도 있음

Critical section 문제의 해결을 위한 조건

1. Mutual exclusion(상호배제) : 한 프로세스가 임계 구역을 수행하고 있다면 다른 프로세스 그 누구도 임계 영역을 수행할 수 없음

2. Progress(진행) : Critical section 을 수행하는 프로세스가 없고, critical section 에 들어가고자 하는 프로세스들이 있다면 다음에 critical section 에 들어갈 프로세스를 선택하는 것이 무한 지연 되어서는 안됨     → Deadlock-free, Livelock-free 조건

3. Bounded waiting : 프로세스가 Critical section 에 들어가기를 요청하고 대기하는 시간은 유한해야함   → Starvation free 조건

Critical section 문제의 해결

단일 코어 환경 : 한 프로세스가 리소스에 접근하면 인터럽트를 막아 원자성을 보장하는 방식으로 구현. 멀티 코어에서는 이렇게 하면 성능이 크게 저하

Peterson’s Solution

int turn;  // 누구의 차례인지

Boolean flag[n]  // 각 프로세스가 경쟁에 참가하는지에 대한 여부, n = 프로세스의 수

 

do {
  flag[i] = true; // 나 경쟁에 참가할래!
  turn = j; // 하지만 지금 순서는 j 에게 양보하겠어
  while( flag[j] && turn == j); // 현재 순서가 j 차례가 아니거나 j 가 경쟁에서 빠질때까지 대기!
  	<critical section> // critical section 수행
  
  flag[i] = false; // 나 critical section 수행 마쳤으니 이제 경쟁에서 빠질래
  	<remainder section>
} while (true);

 

peterson 해결책은 critical section 문제를 해결하기 위한 3가지 조건을 모두 만족

• Mutual exclusion

• Pi 는 flag[j] == false ( j가 경쟁에 참여하지 않음)거나 turn == i (내 차례) 일때만 Critical section 에 들어감

• Pi 는 flag[i] == true ( 내가 경쟁에 참여하고 싶을 때) 에만 Critical section 에 들어감

• Pi 와 Pj 는 동시에 임계 구역에 들어갈 수 없음

• Progress

• Pi는 flag[j] == true 이고 turn == j 인 경우에만 멈춤

• Bounded waiting

• Pi 는 Pj 가 모두 들어갔다 나오면 무조건 들어갈 수 있음

 

하지만 최신 컴퓨터 구조에서는 명령어가 Out of order 로 수행되기 때문에 적용 될 수 없음

Out of order = 코드간의 연관성이 없어서 선후 관계가 중요치 않은 경우 컴파일러가 임의로 순서를 바꾸어 실행

 

예를 들어

-- Thread1

while (!flag);
print x;

 

-- Thread2

 

 

와 같다면 Thread2 가 flag 를 true 로 바꾸기 전에 x 를 100으로 바꿈으로서 Thread1에서는 100이 출력되어야함

하지만 Out of order 로 인해 x = 100; 과 flag = true; 의 순서가 바뀌어 실행될 수 있음. 이 경우 0이 출력됨   → Mutual exclusion 이 보장되지 않음

Synchronization hardware

Critical section 문제를 해결하려면 우선 Atomic 한 하드웨어 명령어인 lock을 제공해줘야함

do {
  <acquire_lock>
  <critical section>
  <release_lock>
  <remainder_section>
} while(true);

 

Lock 은 하드웨어 레벨에서 Atomic 함을 보장하며 이를 위해 test_and_set, compare_and_swap 명령어를 통해 lock 을 구현하여 사용자에게 제공

test_and_set

boolean test_and_set(boolean *target) {
  boolean rv = *target;
  *target = TRUE;
  return rv;
}

target 이 1이면 다른 누군가가 lock 을 갖고음. 0이면 아무도 갖고 있지 않음 (내가 가지면 됨)

target 값과는 상관 없이 무조건 *target = TRUE 를 호출한다는 특징이 있음

 

Atomic 한 test_and_set() 함수가 제공된다면 사용자는 다음과 같이 코딩함

do {
  while (test_and_set(&lock));
  	<critical_section>
  lock = false;
  	<remainder_section>
} while (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;
}

test_and_set 과 거의 유사하지만 target 이 참이든 거짓이든 값을 assignment 했던 test_and_set 과 달리 if 문으로 값을 비교하고 넣는다는 점이 다름

보통 value 에는 lock 변수의 주소, expected 에는 가용 상태를 나타내는 0, new_value 는 해당 lock 변수를 사용하겠다는 의미의 1을 넣음

 

활용법

do {
  while (compare_and_swap(&lock, 0, 1) != 0);
  	< critical_section >
  lock = 0;
  	< remainder_section >
} while (true);

하지만 이는 이 compare_and_swap 은 bounded waiting 을 보장하지 않는다는 문제가 있음

예를 들어 여러 스레드가 위 코드를 무한으로 수행하고 있다면 하나의 스레드가 독점적으로 critical section 에 계속 접근할 수도 있는 문제가 발생

Bounded-waiting test_and_set

do {
  waiting[i] = true;
  key = true;
  while (waiting[i] && key); // 일단 대기
    key = test_and_set(&lock); // C.S.에 접근 중인 스레드가 없으면 내가 들어감
    // key = compare_and_swap(&lock, 0, 1);
    
  waiting[i] = false; // 대기 해제
  	< critical_section >
  j = (i + 1) % n;
  while ((j != i) && !waiting[j]) // 나 이외에 대기하고 있는 스레드가 있는지 검사
  	j = (j + 1) % n;
    
  if (j == i)
  	lock = false; // 아무도 없다면 아무도 접근 중이지 않다는 의미로 lock 변수를 놓아줌
  else
  	waiting[j] = false; // j가 대기중이라면 대기상태를 해제 (4번 라인에의해 j 는 C.S.에 접근)
  
  < remainder_section >
} while (true);