[pintOS]-Priority Inversion, Multiple, Nested 정리

Priority Inversion 문제

• 우선순위 역전. 우선순위가 높은 쓰레드가 우선순위가 낮은 쓰레드를 기다리는 현상
• Critical Section(이하 CS)를 접근하지 못하도록 락을 거는 경우에 발생한다.
  • 락은 우선순위와 상관 없이, 락 홀더가 끝날 때까지 다른 쓰레드들이 락이 풀릴때까지 CS 앞에서 대기한다.
• L(낮은 priority) 이 lock holder고 H(높은 priority)가 락 해제를 기다리는 경우에도 우선순위 역전이라고 할 수 있다.(나의 생각)
• 일반적으로는 CS에 접근하지 않는 M(L과 H의 중간 priority) 이 들어오는 경우에 이 역전이 더 극명하게 나타난다.
  • L이 time_slice 때 cpu를 반환하면, L보다 우선순위가 높은 M이 먼저 실행된 뒤에야 L이 실행되어 락해제를 하고, 이후에 H가 실행을 끝마칠 수 있기 때문이다.
• 극단적으로는, 락이 걸려있는 상태에서 M 쓰레드가 계속 들어왔을 때, H가 높은 우선순위를 가졌음에도 starvation을 겪게 된다.

해결

• priority donation개념을 도입한다.
• H가 lock acquire를 하려고 하는 경우에 락 holder에게 priority를 기부하여 최소한 H와 같은 수준으로 실행되게(혹은 같은 수준으로 굶주리게) 만든다.
  • 이후 priority는 반환한다.

정리

• priority scheduling system에서 락을 사용하는 경우에 필연적으로 발생할 수 밖에 없는 문제다.
• 해결을 위해 donation을 도입한다.

Multiple donation

• 위의 priority donation 해결법에서 L쓰레드가 여러 락(Lock A, Lock B)을 가지고 있는 경우에, 각 락을 기다리는 쓰레드들(L,M)에게 donation을 중복해서 받는 경우를 말한다.

구현

• lock을 acquire 요청할 경우, 어떤 락을 기다리고 있는지 저장해야 한다. (wait_on_lock)
• wait_on_lock에 있는 lock 홀더를 찾아 donation 한다.
• 요청한 락을 해결한 경우에는 해당 락에 대한 donation만 반환해야 한다.
• 따라서 donation받은 내역을 저장하는 list가 필요하다 (donation list)

정리

• 락이 어려개인 경우 해당 락을 풀면서(lock release) donation을 반환하더라도, 원래 priority(base_priority)로 바로 돌아가지 않고 남아있는 donation 중 높은 priority가 현재 priority(superficial_priority)가 된다.
• 이 높은 priority를 가지고 lock을 풀면
  • M이 요구하는 lock을 먼저 풀더라도(코드 상 앞쪽에 있어서), H의 donation이 남아있어 H의 lock도 한번에 풀 수 있다.
  • H가 요구하는 lock을 먼저 푼다면, M의 donation이 남아있어, M의 lock도 문제 없이 풀 수 있다.

Nested Donation

• H가 lock B를 가지고 있는 M을 기다리고, M은 lock B를 release하기 위해 lock A를 가지고 있는 L을 기다리는 상황.

해결

• H은 자신의 priority를 M과 L에게 둘 다 기부해야 한다.

구현

donation

• 내가 기다리는 lock_holder에게 donation 하면서, 그 lock_holder 쓰레드도 기다리고 있는 lock이 있는지 확인해야 한다. (wait_on_lock 확인)
• wait_on_lock이 있다면 그 lock의 holder에게도 내 priority를 donation한다.
• wait_on_lock이 null일 때까지 이 작업을 반복한다.

반환

• nested donation 이후에 반환은 multiple과 같다.

궁금한 점

• donation할 때 H의 priority를 모두 주는 것이 아니라 H는 M에게, M은 L에게 donation을 순차적으로 하면 안 될까?
  • 최종적으로 기다리고 있는 쓰레드가 H라면, 위에서의 Priority Inversion이 일어나지 않도록 하기 위해서 H가 nested의 최종 lock_holder까지 전달되는 것이 맞을 것이다.
  • M의 L에 대한 donation은 M이 L의 lock을 기다리면서 이미 이루어졌을 것이다.
  • multiple과 같은 상태가 되므로 이후에는 L에서 M의 락이 먼저 풀리든, H의 락이 먼저 풀리든 같은 시나리오로 간다.
  • H의 락이 먼저 풀린다면, 아직 M의 락이 풀리기를 기다려야 하므로 L에서의 M락 release → M에서의 H lock release 이후 H가 실행되긴 할 것이다.