[운영체제] Peterson's Solution

단순한 접근

방법

Critical section (CS)에 들어갈 때 공유 변수 lock을 true로 설정하고 나오면 false로 설정하는 개념입니다. C 코드로 구조를 나타내면

while (true) {

    while (lock); // entry section

    lock = true;

    // critical section

    lock = false;

    // remainder section
}

하지만 큰 문제점이 있습니다. lock 변수도 결국 공유 변수이고 entry section 에서 대기 후 lock을 변경하기 직전에 인터럽트가 발생하여 다음 프로세스를 실행한다면 ?? 해당 프로세스가 만약 lock 변수를 바꿔버리면 ?! 원래 수정 권한이 주어져야할 프로세스가 아닌 다른 프로세스에게 권한이 주어지게 됩니다.

즉, load 와 store 사이에 인터럽트가 걸리지 않는, atomic 한 관계가 있어야만 합니다. 이를 위해, lock 변수가 아닌 현재 수정 권한이 주어질 프로세스를 가리키는 turn 변수를 이용합니다. 아래는 $P_i$ 의 알고리즘 입니다.

while (true) {

    while (turn == j); // entry section

    // critical section

    turn = j;

    // remainder section
}

Correctness

Mutual exclusion is preserved

CS에 두개의 프로세스가 존재할 수 없습니다. 오직 turn 이 자기 차례인 경우에만 접근할 수 있습니다.

Progress requirement

이 경우에는 성립하지 않습니다. 만약 remainder section이 매우매우 긴 프로세스 A가 턴을 넘기고 다른 프로세스 B가 턴을 받아서 작업 후 다시 턴을 넘겨주면 ??

A 프로세스는 remainder section에서 계속 작업을 하고 있기 때문에 받은 턴을 체크하고 cs에 진입하지 못합니다. 이렇기 때문에 B 프로세스는 턴을 받지 못하게 되고, 따라서 Progress requirement는 성립하지 않습니다.

Bounded-waiting requirement

무한 대기가 발생하지 않습니다.

Peterson's Solution

turn 변수에 flag 배열을 추가해서 이 프로세스가 CS에 들어갈 의향이 있는지 검사합니다.

while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j) ;

    // critical section

    flag[i] = false;

    // remainder section
}

이런 흐름을 가지고 있습니다. remainder section에 있을 경우 flag 값은 false 이므로 remainder section에 오래 머물러서 턴을 사용하지 않는 프로세스가 존재하더라도 다른 프로세스가 턴을 사용할 수 있게 됩니다.

Correctness

Mutual execlusion

Yes 입니다. flag[j] = false or turn = i 인 경우 Pi는 CS에 접근할 수 있게 됩니다.

Progress requirement

Yes 입니다. flag 변수로 CS 에 들어갈 준비가 되었는지 체크가 가능하기 때문입니다.

Bounded-waiting

Yes 입니다. turn 변수가 있기 때문에 만족합니다.

하지만, 문제가 있습니다.

Modern Architecture

현대의 아키텍쳐에서는 Peterson Solution은 정상 작동을 보장할 수 없습니다. 성능 향상을 위해 프로세서나 컴파일러가 서로 영향을 주지 않는 명령어들의 위치를 바꾸기 때문입니다. 이는 싱글 쓰레드일 경우에는 발생하지 않지만, 현대에는 대부분이 멀티 쓰레드 환경이기 때문에 예상하지 못한 결과가 나올 수 있습니다.

예를 들어
boolean flag = false; 변수와 int x = 0; 이라는 두 변수를 공유하는 두 쓰레드가 있습니다. 쓰레드 1에서는

while (!flag) ;
print(x);

이러한 작업을 하고 쓰레드 2에서는

x = 100;
flag = true;

라는 작업을 합니다. 이 경우, 예상되는 출력은 100이지만, 컴파일러가 쓰레드 2의 코드 순서를 성능 향상을 위해 바꿔버리면 예상되는 결과는 0일 수도 있습니다.

Peterson's Solution 다시보기

위 경우처럼 순서가 바뀌고 그 사이에 인터럽트가 걸린다면?

while (true) {
    turn = j;
    flag[i] = true;
    while (flag[j] && turn == j) ;

    // critical section

    flag[i] = false;

    // remainder section
}

이렇게 turn, flag[i] 할당 부분이 바뀌고 그 사이에 인터럽트가 걸린다면, i 와 j 프로세스 둘 다 CS에 들어가는 상황이 발생합니다. 따라서 Critical section Problem 을 해결하지 못합니다.

이를 위해서, 하드웨적인 지원 (Memory Barrier) 가 필요합니다.

Memory Barrier

Memory barrier instruction 이 수행되면, 시스템은 현재까지의 load and store 명령어들이 barrier 이후의 load and store 이전에 완료되도록 보장합니다.

• x 미리 로드되는 경우 방지

while (!flag) memory_barrier();
print x

• x = 100 할당 후 flag 할당

x = 100;
memory_barrier();
flag = true;

이런식으로 load and store 이전에 메모리 베리어를 호출하여 선후 관계가 역전을 방지할 수 있습니다.

Peterson Solution

Peterson 솔루션에서 발생하던 문제를 메모리 베리어로 해결할 수 있습니다.

while (true) {
    flag[i] = true;
    memory_barrier();
    turn = j;
    while (flag[j] && turn == j) ;

    // critical section

    flag[i] = false;

    // remainder section
}

문제점

메모리 베리어는 low-level operation 이며, 주로 커널 개발자가 사용합니다. 성능에 큰 영향을 줄 수 있기 때문에 잘 사용하지 않습니다.

따라서 이런 방법 보다는, 하드웨어적인 지원을 받아서 critical section 코드를 작성합니다.

Hardware Instruction

• TAS : Test-and-Set instruction
• CAS : Compare-and-Swap instruction

위에 두 명령어들은 프로세서에서 특정 값에 대한 load and store 과정의 atomic한 실행을 보장합니다.

해결책 (1) : test_and_set()

bool test_and_set(bool *target) {
    bool rv = *target;
    *target = true;
    return rv;
}

해당 값을 리턴하고 그 값을 true로 변경하는 과정을 atomically하게 수행해주는 명령어 (TAS) 입니다. 해당 명령어가 두개 이상의 다른 코어에서 동시에 실행되더라도, 하나씩 순서대로 실행됩니다. (순서는 랜덤)

이 명령어를 이용하여 작성하면 다음과 같습니다. cs 진입 여뷰를 나타낼 공유변수 lock을 이용합니다.

do {
	while (test_and_set(&lock)) ;

	// critical section

	lock = false;

	// remainder section
} while (true);

이렇게 수정된 코드를 사용한다면 해결 가능할까??

• Mutual exclusion : T
• Progress : T
• Bounded Waiting : F

락을 갖고있던 프로세스가 false하고 다시 자신 코드의 처음으로 돌아가버리면 하나만 계속 실행됩니다. 따라서 다른 프로세스는 무한 대기 상태가 나타날 수 있습니다.

해결책 (2) : compare_and_swap()

이 함수는 비교 후 값을 바꾸는 과정이 atomically 하게 실행됩니다.

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) != 0) ;
	
	// critical section

	lock = 0;

	// remainder section
}

이 코드를 사용하면 해결할 수 있을까??

• Mutual exclusion : T
• Progress : T
• Bounded Waiting : F

이 경우에도 마찬가지로 bounded-waiting 은 불가능합니다. (해결책 1과 동일한 상황이 발생한다면 이 방법으로도 탈출 불가)

따라서 공유변수 1개를 추가합니다.

해결책 (3) : bounded-waiting with compare-and-swap()

bool waiting[n];
int lock;

while (true) {
	waiting[i] = true;
	key = i;
	while (waiting[i] && key == 1)
		key = compare_and_swap(&lock, 0, 1);
	waiting[i] = false;

	// critical section

	// 다음 인덱스
	j = (i + 1) % n;
	// waiting이 true 혹은 자기자신일 경우 탈출
	while ((j != i) && !waiting[j])
		j = (j + 1) % n;
	// 자기 자신이면 (대기 중인 프로세스 없으면) lock = 0
	if (j == i) lock = 0;
	// 대기 중인 프로세스 있으면 해당 프로세스로 진입
	else waiting[j] = false;

	// remainder section
}

Atomic Variables

integers, booleans 타입의 데이터에 대해 atomic 한 업데이트를 지원하는 변수를 atomic variables 라고 합니다. 산술 연산에 대해서는 atomic 하지 않습니다.