[운영체제] Test_and_Set, Compare_and_Swap, Bounded-waiting

최근에 lock 방법이 지닌 문제점을 해결하기 위하여 소프트웨어적 방법을 이용하기보다는 더 이상 쪼개지지 않는 원자적 명령어로 구현하거나 Interrupt 제어로 해결한다.

하드웨어 명령어

lock 함수 코드부분

void lock(struct lock *i) {
    while(i->held);   
    i->held=1;
}

이 lock 함수의 문제점은 A 프로세스가 2번 라인의 코드를 실행하고 다음에 3번 라인의 코드를 실행하기 직전에 Interrupt 걸렸을 상황에서 두드러진다. 즉, A 프로세스가 3번 코드인 'i->held=1'을 실행하기 직전에 Interrupt 걸려서 B 프로세스로 전환된 것이다. 그럼 B 프로세스는 아직 held 값이 0인 걸 보고 바로 임계영역에 진입해버리므로 Race Condition이 발생하게 된다. 이러한 상황이 발생하는 이유는 진입 후 바로 held를 1로 바꿔줘야 하는데, 이 코드가 2개의 라인에 걸쳐 이루어지므로 남이 낄 수 있는 여지가 발생하기 때문이다.

Test_and_Set은 이런 문제를 해결하기 위해 위의 2~3번 코드를 한 라인으로 구현한다.

while(test_and_set(&lock));

쪼개지지 않고 한번에 수행하므로 이를 atomic operation이라 한다. 이는 쪼개질 수 없는 하나의 Unit이다. 이는 하드웨어 명령어 API를 이용한 것이고, 또 다른 atomic operation으로는 compare_and_swap이 있다. 이로써 속도도 더 빠르고 쪼개질 수 없다는 특징을 지닌다.

test_and_set 함수

do {
    while(test_and_set(&lock)); //lock이라는 변수의 값을 먼저 test해서 값이 false인지 true인지 return 
                                // 이후 lock이라는 변수를 true로 설정

    //critical section

    lock = false; // 임계 구역 나올때 lock을 false로 설정

    //remainder section

} while(true);

compare_and_swap

while(true) {
    // compare_and_swap은 세 개의 매개변수를 필요로 한다.
    // 첫 번째 매개변수와 두 번째 매개변수가 같을 때, 즉 lock이 0일 때에만 lock을 1로 설정
    // return 할 때는 항상 lock의 상태를 반환
    // lock이 걸려 있지 않으면 0을 반환한 후 1로 바꿔주고, lock이 걸려 있으면 1 반환 후 그대로 둔다.
    // lock이 1이면 while문에서 빠져나오지 못하고 무한반복한다.
    while(compare_and_swap(&lock, 0, 1) != 0);

    //critical section

    lock = 0; // 임계 구역에서 일을 마치고 다른 프로세스가 들어갈 수 있게 lock을 해제한다.

    //remainder section
}

Bounded-waiting mutual exclusion

위의 코드들은 mutual-exclusion을 만족시키나 bounded-waiting requirement, 즉 한정 대기 조건을 만족시키지 못한다. 따라서 이를 해결하기 위해 compare_and_swap()을 이용하면서 모든 임계영역 해결조건을 만족시키는 알고리즘이 존재한다.

while(true) {
    waiting[i] = true; // i번째 프로세스가 공유 자원을 쓰고 싶다는 신호
    key = 1;
    while(waiting[i] && key == 1) // i번째 프로세스가 쓰고 싶어도 key가 1이라면 들어가지 못하고 while문에 머무름
        key = compare_and_swap(&lock, 0, 1); //key는 compare_and_swap을 이용해서 lock을 반환, 누가 사용하고 있으면 진입 불가능
    waiting[i] = false; // 임계 영역에 진입할 수 있는 6번 라인에 오면 임계 영역 코드를 수행중이므로 기다리는 대기 배열에서 빼준다.

    //critical section


    // i 번째 프로세스가 독차지 하지 않도록 다른 프로세스에 권한을 넘겨주는 코드이다. 실행 시켜줄 j 프로세스를 찾는다.
    // 예를 들어 n이 7일때, i가 1이라면 j는 2가 되고, i가 2라면 j는 3이 되는 방식이다.
    // 여기서 j가 자원을 쓰고 싶어하지 않으면 수행시킬 필요가 없으므로 자원 쓰고 싶어하는 j가 나올 때까지 while문을 돌려준다.
    j = (i + 1) % n;
    while((j != i) && !waiting[j])
        j = (j + 1) % n; // j를 1씩 증가시킨 후에 n으로 나누었을 때의 나머지를 j 값으로 설정한다. 

    if(j == i) //j가 i일 경우는 한 바퀴 다 돌았는데 공유자원을 사용하고 싶어하는 프로세스가 없다는 의미이다.
        lock = 0; // 이때 lock을 해제해준다. (lock이 0인 의미는 lock을 해제해주는 의미이다.)
    else // 이 때는 공유자원을 사용하고 싶어하는 프로세스를 발견했다는 의미이다.
        waiting[j] = false; // 이때 waiting[j]를 false로 바꿔주는데, j는 4번 while문에서 계속 무한루프에 있는 상황이었다.
                            // 그래서 false로 바꿔주면 while문에서 빠져나와 임계 구역에 진입할 수 있다.
                            // 이후 i번째 프로세스는 남은 코드 수행 후 종료한다.
                            // lock은 풀 필요가 없는데, 어차피 j가 사용하면 lock은 유지되어야 하기 때문이다.

    //remainder section
}    

참고자료

https://jhnyang.tistory.com/41?category=815411 

[운영체제 Atomic방법]test_and_set, Compare_and_Swap, Bounded-waiting