lock의 목적은 crital section이 atomic하게 동작하는 것을 보장하기 위함이다.
lock variable이 lock의 상태를 지니고 있다.
lock을 만들기 위해서는 하드웨어와 OS의 도움이 모두 필요하다.
single processor 시스템에서 사용하던 초기의 mutual exclusion 방법이다.
critical section에서의 interrupt를 허용하지 않는다.
하지만 이 방법은 single processor 시스템에서 탐욕적인 프로그램이 processor를 독점하고 있다면 문제가 발생할 수 있고, multi processor 시스템에서는 동작하지 않는다.
lock이 되었는지 또는 되지 않았는지를 나타내는 flag를 활용하는 것이다.
하지만 이 방법은 2가지 문제점이 있다.
따라서 이러한 문제를 해결하기위해서 하드웨어가 필요하다.
test-and-set (atomic exchange)라고 불리는 추가적인 하드웨어가 필요하다.
TestAndSet의 동작 방식을 보면 old value를 리턴하고, 그와 동시에 new에 새로운 값을 update한다. 무엇보다도 이 작업이 atomically하게 이루어진다는 것이 중요하다.
ptr의 값이 expect와 같은지 다른지를 판별해서 같다면 값을 업데이트하고 예전값을 리턴, 같지 않다면 그냥 업데이트하지 않은 값을 리턴한다.
MIPS architecture에서는 load-linked 와 store-conditional 명령쌍으로 lock을 구성하는데 도움을 줄 수 있다.load-linked는 단순하게 메모리위치의 값을 가져오는 것이고, store-conditional은 load-linked에 값이 업데이트된 경우가 없을 때 load-linked를 1로 업데이트하고 성공을 리턴하고, 그렇지 않으면 실패를 리턴한다.
atomically하게 메모리의 값을 1증가시키고, 이전 값을 리턴한다.
하드웨어 기반의 spin lock은 쉽고 잘 동작한다. 하지만 몇몇 경우에는 비효율적이다.
thread가 spinning하는 동안에는 값을 확인하는 것 외에는 별다른 행동을 하지 않으나, 이 행동이 time slicing을 낭비하게 만든다.
OS의 도움으로 이 문제를 해소할 수 있다.
단순하게 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문제가 해결되지도 않는다.
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()를 할 것이라고 알려준다.