Critical Section Problem

Atomic instructions

원자와 같은 명령어. 한번 시작을 하면 끝을 내야하는 명령어. 실행 도중에는 멈추지 않는다. 

Spin lock에서 숫자를 확인하고, 설정하는 그 사이에 switch가 발생하는데, 원자 명령어는 이것을 하나의 명령어로 구현하면 switch가 발생하지 않는다. all or nothing이라는 이름으로도 불린다. 

Test-and Set instruction

bool test_and_set(bool *flag) {
    bool old = *flag;
    *flag = True;
    return old;
}

<Solution>
lock = false
repeat
	while test-and_set(lock) do no-op;
    	ciritical section;
    lock - false;
    	remainder section;
until false

test_and_set()함수에 lock변수의 주소값을 넘겨준다. *flag는 lock의 주소를 old에 담고, *flag는 True로 바꾸면 old = false, lock = true가 되서, while문이 실행되고 no-op가 되어서 test_and_set을 반복 호출한다. 그리고 lock = false가 되면 반복문을 빠져나와서 문제를 해결한다.

하지만 이 방법은 여전히 busy-waiting이 발생한다는 문제가 남아있다. 

Peterson's Solution

#define FALSE 0 
#define TRUE 1
#define N 2

int turn;
int interested[N];
void enter_region(int process) {
	int other = 1 – process;
	interested[process] = TRUE;
	turn = process;
	while (turn == process && interested[other] == TRUE);
}

void leave_region(int process) {
	interested[process] = FALSE;
}

Peterson's Solution으로 문제를 해결할 수 있다. 그러나 busy waiting이 발생하고, 구현을 하면 가끔 오류가 생긴다. 즉 완전한 프로그램은 아니기 때문. 첫번째는 compiler optimization이 오류를 일으킨다. 컴파일러는 번역 & 코드를 살짝 수정해주는 역할을 하기 때문. 그리고 CPU는 1개의 코어를 가지고 있어도 병렬 처리 기능이 오류를 일으킨다. 

해결책

sleep()
wakeup()

Producer-Consumer Problem

#define N 100
int count = 0;

void producer() {
    int item;
    
    while(TRUE) {
    	item = produce_item();
        if(count == N) sleep();
        insert_item(item);
        count += 1;
        if(count == 1) wakeup(consumer);
    }
}

void consumer() {
    int item;
    
    while(TRUE) {
    	if(count == 0) sleep();
        item = remove_item();
        count -= 1;
        if(count == N-1) wakeup(producer);
    }
}

busy waiting을 없애고자 제안한 해결법. 그러나 문제는 둘 다 sleep()을 수행해서 동작하지 않는다는 문제가 발생.

producer가 if를 통해 count == N을 확인하고, sleep()을 하기 전, CPU는 consumer가 되서, 수행 한 뒤, if문을 통해 count == 0 을 확인하고, sleep()을 하면, consumer도 sleep, producer도 sleep을 해서 둘 다 sleep가 된다.