[운영체제] lock & busy-waiting 문제

Lock

Lock은 의미 그대로 잠군다는 것을 뜻한다. 마치 화장실을 사용하고 있는 동안에 문을 잠궈서 자기가 사용하는 동안 아무도 못 들어오게 하는 것처럼, 특정 프로세스나 스레드가 lock을 통해 임계 영역을 잠궈서 혼자 사용할 수 있게 하는 방법이다. 이는 동기화 기법의 한 가지 방법이다.

은행 계좌 관련 사례를 살펴보자면 다음과 같다. A라는 사람과 B라는 사람이 같은 계좌를 공유하고, 그 계좌에는 현재 100만원 있다. 이때 우연찮게도 A와 B는 동시에 그 계좌에서 10만원을 인출하는 상황이 발생했다. 여기서 A라는 사람이 인출을 했는데 인출함수 수행하는 과정에서 4번째 줄에서 Timer Interrupt가 발생했다면, 스케줄러에 의해 B가 10만원을 인출하는 프로세스가 이 함수를 수행하는데, 이때 A 프로세스에서 계좌를 갱신하기 전에 Interrupt가 발생해서 현재 100만원의 잔액이 남아있는 걸로 나타난다. 그리하여 실질적으로 합쳐서 20만원을 인출했는데, 잔액은 90만원이 되는 사태가 발생하게 된다.

int withdraw(account, amount) // account에서 amount만큼 인출하는 함수
{
    balance = get_balance(account); // account에서 현재 잔액을 가져와서, balance라는 변수에 저장한다.
    balance = balance - amount; // 잔액은 기존 잔액에서 amount 만큼 뺀 금액, balance를 갱신한다.
    put_balance(account, balance); // account에 변경된 잔액을 갱신한다.
    return balance;
}

여기서 account의 데이터베이스가 공유 자원이며, 이 공유 자원을 A와 B가 동시에 접근하려는 상황이니 race condition이라 볼 수 있다. 그리고 공유 자원을 가지고 기능을 수행하는 코드 영역을 임계 영역(critical Section)이라 한다. 이때 race condition을 방지하기 위해 임계 영역에 들어갈 때 lock을 걸어놓고, 나올 때 lock을 풀어주는 방식을 lock 방식이라 한다.

int withdraw(account, amount) // account에서 amount만큼 인출하는 함수
{
    lock(lock); // 임계 영역 잠금
    balance = get_balance(account); // account에서 현재 잔액을 가져와서, balance라는 변수에 저장한다.
    balance = balance - amount; // 잔액은 기존 잔액에서 amount 만큼 뺀 금액, balance를 갱신한다.
    put_balance(account, balance); // account에 변경된 잔액을 갱신한다.
    unlock(lock); //임계 영역 잠금 해제
    return balance;
}

위의 코드처럼 lock을 걸었으면, A가 lock을 건 이후 balance에서 amount를 빼는 5번 라인에서 수행하는 도중 timer Interrupt가 발생했을 때, B가 스케줄러에 의해 수행된다. B가 lock을 걸려고 할 때, 이미 lock이 걸려져 있어서 앞으로 진입하지 못하고 3번 라인에서 A가 해제해 줄때까지 대기하는 상태가 된다. 다시 스케줄러에 의해 A가 수행되면 A는 나머지 코드를 다 수행 후 lock을 해제하고, 이후에 B가 드디어 수행된다.

Lock 구현

struct lock{
    int held = 0; //held가 1이라는 뜻은 이미 임계 영역에 진입했다는 의미이고, 초기에는 진입 안 한 상태이니 0의 값을 갖는다.
}

void lock(struct lock *i) {
        // held가 1이면 무한루프를 돌게 된다. 즉, lock이 풀릴 때까지 계속 반복하는 코드이다.
        // 다시 말해, held가 0일 때까지 돌게 되는데, 이를 spinlocks 또는 busy-waits라 부른다.
        while(i -> held);

        i->held = 1; //spinlocks에 있던 스레드가 빠져 나오면서 held를 1로 만들면서 임계 영역에 진입하게 된다.
}

void unlock(struct lock &i) {
    i -> held = 0; //또 다른 스레드가 unlock이라는 함수를 호출하면 held 값이 0으로 바뀌어 spinlocks에 있던 스레드가 빠져나오게 된다.
}

Lock의 문제점

A 스레드가 while(i -> held) 라인을 수행하다가 held가 0이면 while문을 빠져나온다. 하지만 while 루프를 빠져 나오자마자 Interrupt가 걸릴 수 있다. 이때 B 스레드가 실행되는데, held의 값이 0인 상태이다. A 스레드가 접근했지만 아직 "i -> held = 1"이라는 구문에 접근하기 전이라서 아직 held는 0의 값을 가지고 있는 상태이다. 이런 상황에서 B 스레드가 임계 영역에 접근하여 수행하다가 Interrupt 걸려 다시 A 스레드가 실행하게 되면 "i -> held = 1"의 라인부터 수행하게 된다. 이렇게 되면 A와 B 모두 임계영역에 접근해버린 상태가 되어버린다는 문제가 발생한다.

 

참고자료

https://jhnyang.tistory.com/36

[운영체제]critical section(임계영역) & lock 락 & busy-waits