지금까지의 방법들은 매우 비효율적이다.
왜냐하면 lock을 얻기위해서 spin-wait를 하게되는데,
이러한 방식은 CPU를 불필요하게 계속 소모해서 다른 활동을 하지 못하기 때문이다.
따라서 위 문제를 해결할 수 있는 방법들을 알아보자
Just Yield
가장 간단한 구현 방법이다.
만약 lock이 사용중이라면 깔끔하게 CPU를 반납하고 다음 time-slice에 자신의 차례가 올 때까지 기다리는 방법이다.
이러한 방법은 다음 차레에 내가 lock을 받는다는 확신을 할 수 없기 때문에 운이 나쁘면 lock을 얻지 못하게 되는 starvation문제가 존재한다.
Using Queues: Sleeping Instead of Spinning
Queue를 사용해서 쓰레드를 sleep track에 넣어주는 방식이다.
- park() : 쓰레드를 sleep상태로 만들어 준다
- unpark(threadID) : threadID에 맞는 쓰레드를 깨운다.
Using Queues: Sleeping Instead of Spinning
guard는 queue와 flag에 접근하기 위해 사용하는 또다른 lock 변수라고 이해하면 된다.
문제점 : Wakeup/waiting race
위 문제를 해결하기 위해 Solaris운영체제에서는 setpark()라는 새로운 syscall을 도입했다.
setpark()는 현재 쓰레드가 park()를 하기 직전임을 알리는 syscall이다.
만약 현재 쓰레드의 park()직전에 다른 쓰레드에서 unpark()가 수행되면
interrupt가 발생해서 현재 쓰레드를 바로 return하는 방식으로 문제를 해결한다.
Futex : 리눅스가 제공하는 park(), unpark()와 비슷한 방법
- futex_wait(address, expected) : park()와 비슷하고, setpark()가 섞인 기능이다.
- 만약 address가 expected와 다르면 현재 쓰레드를 즉시 return
- futex_wake : 쓰레드를 깨우는 기능
Futex
int의 최상위 1bit만을 사용해서 lock 상태를 제어한다.
나머지 bit는 현재 lock을 기다리고 있는 대기 쓰레드의 개수가 된다.
만약 v >= 0(최상위 bit가 0이라는 뜻이다) 이면 현재 lock이 사용중이 아니라는 말이므로 continue를 통해서 lock을 얻으러 간다.
unlock에서 mutex에 0x80000000을 더해준 값이 0인지를 비교하는 이유는
만약 lock이 사용중이고 현재 대기중인 쓰레드의 개수가 0이라면(나머지 31비트가 모두 0) 오버플로우가 발생해서 lock bit를 모두 0으로 만들고 return한다.
Two-Phase Locks
lock을 얻지 못했을 때 바로 CPU를 반납하고 lock을 기다리는 것보다
잠시 spin-wait상태에 있는게 더 효율적인 경우도 있다.
- First phase : 잠깐 spinning-wait를 해본다.
- Second phase : sleep한다.
'CS > OS' 카테고리의 다른 글
[OS] Process #1 (0) | 2021.07.05 |
---|---|
[운영체제] Semaphore (0) | 2021.06.13 |
[운영체제] Locks #2 (0) | 2021.06.11 |
[운영체제] Locks #1 (2) | 2021.06.11 |
[운영체제] Page Replacement Policy (페이지 교체 알고리즘) (0) | 2021.06.09 |