[운영체제] 메모리 베리어

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 하지 않습니다.