lock의 목적은 crital section이 atomic하게 동작하는 것을 보장하기 위함이다.
lock variable이 lock의 상태를 지니고 있다.
- available
아무런 thread도 lock되지 않았음 - acquired
critical section에서 한개의 thread가 lock이 되었음
lock을 만들기 위해서는 하드웨어와 OS의 도움이 모두 필요하다.
Evaluating locks
- Mutual exclusion
여러개의 thread가 critical section에 들어오는 것을 막아줄 수 있는가? - Fairness
lock이 해제된 이후 각각의 thread는 공정하게 lock을 얻을 기회가 주어지는가? - Performance
time overhead가 증가되는 문제가 있는가?
Controlling Interrupts
single processor 시스템에서 사용하던 초기의 mutual exclusion 방법이다.
critical section에서의 interrupt를 허용하지 않는다.
하지만 이 방법은 single processor 시스템에서 탐욕적인 프로그램이 processor를 독점하고 있다면 문제가 발생할 수 있고, multi processor 시스템에서는 동작하지 않는다.
A Failed Attempt: Just Using Loads/Stores
first attempt
lock이 되었는지 또는 되지 않았는지를 나타내는 flag를 활용하는 것이다.
하지만 이 방법은 2가지 문제점이 있다.
- correctness
위의 그림에서 볼 수 있듯이 flag가 0에서 시작하고, thread 1이 flag를 1로 바꾸기 전에 switch가 발생하여 thread 2로 변경되고, 여기서 flag가 1로 바뀐 후 다시 thread 1로 되돌아왔을 때 멈춰진 thread 1의 작업을 이어서 진행하여 flag를 1로 만든다.
이와같은 방법은 mutual exclusion이라고 할 수 없다. - performance
그리고 spin wait이 시간을 낭비하게된다.
따라서 이러한 문제를 해결하기위해서 하드웨어가 필요하다.
Building Working Spin Locks with Test-And-Set
test-and-set (atomic exchange)라고 불리는 추가적인 하드웨어가 필요하다.
TestAndSet의 동작 방식을 보면 old value를 리턴하고, 그와 동시에 new에 새로운 값을 update한다. 무엇보다도 이 작업이 atomically하게 이루어진다는 것이 중요하다.
Evaluating Spin Lock
- correctness
보장됨. - fairness
보장되지 않음.
1개의 thread가 영원히 돌수도 있음 - performance
single cpu에서는 오버헤드가 꽤나 치명적이다. 하지만 multi cpu에서는 꽤나 합리적인 방법이다.
Compare And Swap
ptr의 값이 expect와 같은지 다른지를 판별해서 같다면 값을 업데이트하고 예전값을 리턴, 같지 않다면 그냥 업데이트하지 않은 값을 리턴한다.
Load-Linked and Store-Conditional
MIPS architecture에서는 load-linked 와 store-conditional 명령쌍으로 lock을 구성하는데 도움을 줄 수 있다.
load-linked는 단순하게 메모리위치의 값을 가져오는 것이고, store-conditional은 load-linked에 값이 업데이트된 경우가 없을 때 load-linked를 1로 업데이트하고 성공을 리턴하고, 그렇지 않으면 실패를 리턴한다.
Fetch And Add
atomically하게 메모리의 값을 1증가시키고, 이전 값을 리턴한다.
Too Much Spinning: What Now?
하드웨어 기반의 spin lock은 쉽고 잘 동작한다. 하지만 몇몇 경우에는 비효율적이다.
thread가 spinning하는 동안에는 값을 확인하는 것 외에는 별다른 행동을 하지 않으나, 이 행동이 time slicing을 낭비하게 만든다.
OS의 도움으로 이 문제를 해소할 수 있다.
A Simple Approach: Just Yield, Baby
단순하게 thread가 spin을 한다면 다른 thread에게 CPU를 양보한다.
system call로 spin을 하는 thread의 상태를 running에서 ready로 변경시킨다. 만약 2개의 thread가 하나의 CPU에서 동작할 때는 yeild 방식이 잘 동작한다. 하지만 만약 thread의 수가 100개라면 어떻게될까...?
1개의 thread가 lock이 되어있다면 나머지 99개의 thread는 lock인 것을 확인하고, CPU를 yeild 해야한다. 즉, thread의 수가 많다면 이 방법 또한 효율적이진 않다.
그리고 여전히 thread들이 계속해서 critcal section에 들어왔다 나갔다하면 다른 thread들은 CPU를 yeild해야하므로 starvation문제가 해결되지도 않는다.
Using Queues: Sleeping Instead Of Spinning
yeild 방식은 scheduler가 어떤 thread를 다음에 돌려야할지 모르기 때문에 문제가 발생한다.
만약 lock을 위해 spin하는 thread 또는 바로 yeild 하는 thread라면 CPU의 낭비가 발생한다. 따라서 현재 thread가 release되면 다음에 lock을 가져야하는 thread를 관리할 필요가 있다.
이를 위해서 park() lock을 얻으려고 하는 thread를 sleep시키는 함수, unpark(threadID) threadID를 깨우는 함수를 활용한다.
이를 위해서 다음에 lock을 얻어야 할 thread를 저장 할 queue를 활용한다.
따라서 thread 1이 lock이 되려고할 때 interrupt가 발생하여 thread 2가 실행되는 경우 thread 2를 queue에 저장하고 thread 1을 재개한다. 그 후 thread 1이 release되면 queue에 있던 thread 2를 실행하는 방법이다.
하지만 만약 park()를 하기 이전에 이미 thread가 release가 되었다면 어떻게 될까??
다음에 실행되어야 할 thread는 이미 실행가능한데 park()가 되지 않은 thread를 unpark() 해버리는 경우가 생기게된다.
그래서 이 문제를 방지하기 위해서 setpark()라는 것을 활용하여 문제를 해결한다.
setpark()를 활용하므로써 OS에게 곧 park()를 할 것이라고 알려준다.
