[운영체제] Locks

Locks

Thread 포스팅에서 다룬 Race condition 을 해결하기 위한 방법입니다. 임계 구간 즉, critical section 을 Lock 하여 하나의 스레드에게만 권한을 주고 모든 작업이 끝난 후 Unlock 시키는 구조로 돌아갑니다.

Evaluating Locks

• Mutual exclusion
  • critical section 에는 한번에 하나의 thread 만 들어갈 수 있습니다.
• Fairness
  • 여러개의 스레드가 critical section 으로 진입하려고 할 때 특정 thread 가 starvation 하지 않게 방지합니다.
• Performance
  • Time overhead
    • number of threads
    • number of CPUs

Controlling Interrupts

Disable Interrupts 하여 lock 합니다. Enable Interrupts 하여 unlock 합니다. 예를들어 Timer Interrupt 가 발생하지 않게 하여 CPU scheduler가 불려지지 않게 하여 context switch 를 못하게 하는 방법입니다. 매우 간단한 방법이지만 많은 단점을 가지고 있습니다.

• root 권한을 가지고 있어야 합니다.
• multiprocessor 환경에서는 작동하지 않습니다. : 다른 CPU core 쪽으로는 interrupts 가 발생할 수 있습니다.
  • 다른 cpu에서 context switch 가 일어날 수 있고 -> mutual exclusion 을 보장할 수 없습니다.
• interrupt에 대해 처리를 못하게 되므로 성능이 저하될 수 있습니다.

해당 방법은 운영체제 안에서 혹은 Device driver 안에서 사용될 수 있습니다.

Spin Locks

flag 를 이용해 while 문을 spin 하여 critical section 으로 진입하지 못하게 하는 방법입니다. critical section 으로 진입하지 못한 스레드가 while 문에서 spin하고 있으므로 critical section 안으로 진입한 스레드는 cpu를 할당받을 확률이 떨어집니다. 그리고 mutual exclusion 을 보장할 수 없습니다. 해당 문제를 해결하기 위해 여러가지 방법이 등장했습니다

• Test-and-set atomic instruction : mutual exclusion 은 보장하지만 fairness 를 보장할 수 없습니다. 또, overhead 가 커지면서 성능이 저하될 수 있습니다.
• compare-and-swap atomic instruction : Test_and-set instruction 과 동일합니다.

Ticket Locks

• Fetch-and-add atomic instruction : 스레드가 도착할 때 ticket 값을 부여받고 turn 이 될때까지 spin 합니다. unlock 시 turn +=1 이 됩니다.
• mutual exclusion 과 fairness 를 모두 해결해줄 수 있습니다. 하지만 아직 성능관점에서 issue 가 남아있습니다.

Hardware Support

yield() 를 통해 spin중인 스레드를 대상으로 cpu scheduler 에게 다른 스레드를 선택할 수 있는 선택권을 부여합니다. 하지만 여전히 성능관점으로 좋지 않습니다.

OS Support

하드웨어 즉, atomic instruction 만으로 mutual exclusion 과 fairness 를 해결했지만 여전히 performance 가 저하될 여지가 있습니다. 이 부분을 운영체제가 도와줄 수 있습니다.

sleeping instead of spinning

lock 을 acquire 할 수 없다면 blocked state 로 보내지고, unlock 시 다시 ready state 로 불려집니다. cpu scheduling 알고리즘에 의해서 running state 로 가게 됩니다. OS 는 sleeping 기능을 지원해 줍니다.

Locks with Queues

lock을 얻지 못해 Critical section 에 진입하지 못한 스레드는 Queue 로 보내집니다.

• solaris 체계 기준
• sleeping : park()
• awake : unpark()
  flag 와 queue 와 같은 공유 데이터는 guard 에 의해 보호받습니다. 하지만 thread가 실제로 sleeping 하기 전에 critical section 내의 스레드가 unlock 을 호출하면 queue 에 스레드가 대기중이라고 판단하고 Queue에서 sleeping 중인 스레드를 깨우려고 합니다. 하지만 아직 sleeping 되어 있는 스레드가 없으므로 아무도 깨우지 못하게 되고 이후에 처음 스레드가 sleeping 이 된다면 해당 스레드는 깨어나지 못하게 됩니다. 즉 race condition 이 존재하게 됩니다. guard 를 해제하기 전에 sleeping 을 먼저 수행한다고 하더라도 guard 를 잠구고 park 되었기 때문에 guard 를 풀어줄 수 없습니다. 그렇게 되면 다른 스레드들이 guard 를 얻어올 수 없습니다. 이러한 문제를 해결하기위해 setpark() 이 있습니다.

setpark()

guard 해제와 park 이전에 호출됩니다. park 를 부르기 전에 unpark 을 부르게 되면 해당 스레드를 재우지 않고 바로 return 하게 됩니다.

conclusion

lock 기능으로 mutual exclusion 을 보장하고 queue 로 인해 fairness 를 보장해줍니다. 마지막으로 guard 를 얻기 위한 while 문이 있지만 바로 while 문을 빠져나오므로 큰 성능 저하 요소가 없습니다. 또 spin waiting 하던 스레드들을 재우게 되므로 성능을 개선시킬 수 있습니다.