앞선 락 구현에서 등장했던 Test-and-Set, Fetch-And-Add 명령어 등은 하드웨어의 지원을 받아 Correctness 와 Fairness 를 모두 만족시켰다.

그러나 다른 쓰레드가 락을 풀 때 까지 스핀 상태에 놓이는 현상에 의해 Performance 부분에서는 효율적이지 못하게 된다.

문맥 교환이 되어 쓰레드가 실행 되었음에도 불구하고, 타임아웃이 발생할 때 까지 계속 대기 상태로 놓여있기 때문에 cpu를 낭비하게 되고, 쓰레드가 많아질수록 이런 문제가 더욱 심해진다.

이를 위해 Yield를 통해 쓰레드가 스스로 cpu를 양보할 수 있다.

Yield

Yield는 자신이 cpu를 점유하여 running 상태에 있었음에도 불구하고, 점유를 그만두고 스스로 ready 상태로 바뀐다.

결국 스케줄러가 현재 레디 상태에 놓인 다른 쓰레드(프로세스)에게 CPU를 할당해주게끔 만든다.

이 방식을 적용할 경우에는, 락을 구현하는 부분에 있어서 다른건 다 똑같은 대신 while 루프 안에서 계속 스핀하지 않고 그냥 yield라는 시스템콜 호출하면 된다.

void lock(lock_t* lock) {
    while(TestAndSet(&lock->flag, 1) == 1)
        yield();
}

자기가 락을 걸 수 있는 경우에는(TestAndSet) 반복문을 빠져나가지만, 다른 쓰레드가 락을 점유하고 있는 상태일 경우에는 락이 해제되기까지 무한정 기다리며 busy waiting 상태에 놓여있는 것이 아닌, 그 시간동안 다른 쓰레드(프로세스)가 다른 일을 수행할 수 있도록 CPU를 양보한다.

단순히 생각한다면 당연히 스핀 상태에 있는 시간을 다른 쓰레드에게 양보하기 때문에 훨씬 효율적이겠지만, 상황에 따라 달라진다.

Yield 하는 과정에서 계속 컨텍스트 스위칭이 일어나고, 여기서 발생하는 오버헤드가 존재하기 때문이다.

물론 각 쓰레드들이 스핀상태에 놓여있는 시간보다는 문맥교환에 걸리는 시간이 훨씬 짧은 것은 맞지만, 쓰레드가 많아질수록 비용이 부담되기 시작한다.

또다른 점을 고려했을 때, 우선 단일 프로세서 환경에서는 멀티쓰레드 프로세스를 실행시킬때는 스핀보다 슬립(yeild)이 훨씬 유리한 것은 맞다.

그러나 멀티프로세서 환경에서는, 크리티컬섹션이 그렇게 길지 않으면 슬립보다 스핀이 유리해진다.

만약 특정 쓰레드가 락을 걸고 크리티컬 섹션을 수행하는 시간이 문맥교환에 걸리는 시간보다 짧을 경우에는, 다른 프로세서에서 실행중인 쓰레드는 그냥 스핀을 계속 돌다가 락이 풀리면 바로 가져오는게 훨씬 유리하기 때문이다.

게다가 cpu를 양보하고 슬립 상태로 들어갈 경우에는, 다른 쓰레드가 cpu를 가져간 뒤 타임아웃까지 또 사용할 수 있기 때문에 대기 시간이 더 길어지는 문제도 있다.

이런 문제점들을 해결하기 위해 2-Phase 방식도 고려할 수 있는데, 일단 문맥교환에서 발생하는 시간만큼 스핀을 돌아보다가 그래도 락을 얻지 못하면 그 때 yield 하는 방식이다.

이런 해결책 역시 완전하지는 못한게, 스핀을 도는 시간에다가 문맥교환에 걸리는 시간이 또 추가되기 때문에 비용이 늘어날 뿐 아니라, 문맥 교환 시간 역시 일정하지 않기 때문에 이러한 대기 시간을 결정하기 어렵다는 한계가 있어, 사용이 까다로운 방법들 중 하나이다.

Priority Inversion

스핀락 방식의 구현에서 성능 문제를 해결하기 위해 Yield를 활용하지만, 쓰레드들 간의 우선순위 차이에서 발생하는 문제도 있다.

우선순위가 있는 스케줄링을(preemptive) 하는 경우에, 현재 2개 쓰레드가 있으며 T1보다 T2가 더 높은 우선순위를 갖고 있다고 예를 들어보자.

T1이 먼저 실행 되다가도, 우선순위가 높은 T2가 등장하면 preemption이 일어나면서 T2가 스케줄링 되며 실행될 것이다.

만약 T2가 I/O 요청을 한다면 아무리 우선순위가 높아도 Block 상태로 바뀌면서 대기하게 되고, 스케줄러에 의해 T1이 실행 기회를 가질 수는 있다.

여기서 T1이 락을 걸어서 크리티컬 섹션에 들어가는 경우 문제가 발생한다.

우선순위가 낮은 T1이 계속 락을 걸어놓고 작업을 수행중인 상태에서, T2의 I/O가 끝나면 preemption으로 스케줄링 될텐데, 여기서 T2가 크리티컬 섹션에 진입할 경우 락을 요청할 것이다.

스핀락으로 구현될 경우 T2는 타임아웃 될 때 까지 스핀 상태에 놓이게 되는데, 타임아웃 된다고 하더라도 우선순위 때문에 다시 T2가 스케줄링된다.

이러한 현상이 계속 반복되면서, T2는 타임아웃까지 스핀하다가 인터럽트가 걸리고, 또다시 스케줄링되면서 스핀하는 등 영원히 T2의 스핀상태에서 벗어날 수가 없다.

쓰레드가 2개인 경우에는 스핀락 방식이 아닌 슬립 방식으로 구현함으로써 문제를 해결할 수는 있지만, 쓰레드가 더 많아진다면 슬립으로도 해결하지 못한다.

T1 < T2 < T3 순서의 우선순위를 갖는 쓰레드들이 있다고 했을 때, T1이 락을 걸어놓고 T3가 락을 요청하기 위해 슬립 상태에 들어가면, T2만 계속해서 스케줄링 되기 때문이다.

이런 문제를 해결하기 위해 priority inheritance 기법을 사용함으로써, 일시적으로 자기의 우선순위를 락을 건 쓰레드에게 빌려줄 수 있다.

T1이 낮은 우선순위를 가지고 있지만 락을 걸어놨기 때문에, 높은 우선순위를 가진 쓰레드 T3이 락에 걸렸을때 자신의 우선순위를 T1에게 빌려주는 것이다.

결국 우선순위가 잠시 높아진 T1은 다른 쓰레드들(T2 등)에게 방해를 받지 않고, unlock을 시킬 수 있게 되기 때문에 문제를 해결한다.