[Operating System] Liveness

• Liveness?
  • 프로세스들이 그들의 execution life cycle동안 progress가 있도록 보장하는, 시스템이 가져야 할 특징들을 말한다.
  • 프로세스가 무한정 기다리는 상황은 "liveness failure"라고 부른다.
  • busy wait 또한 liveness failure의 가능성을 포함하고 있다.
  • 물론 mutex lock이나 semaphore를 사용해도 liveness failure가 발생할 수 있다.

Deadlock

• 2개 이상의 프로세스가 무한정 event를 기다리게 되는 상황을 deadlock이라고 한다.
• 각 event는 waiting processes중 하나가 signal() operation을 하지 않아 발생한다.
• 예시
  
  • $P_0$와 $P_1$이 동시에 실행되었다고 하면, $P_0$는 S를, $P_1$은 Q를 가지고 있고, 각각 Q와 S를 기다리고 있는 상태이다. 그렇기 때문에 이 wait는 해결되지 않고 무한정 기다리게 되어 deadlock상태가 된다.
• 프로세스들의 집합이 deadlocked 상태이다 -> 집합 안의 모든 프로세스들이 waiting 상태이고, 집합 안의 다른 프로세스에 의해 발생할 수 있는 event를 기다리고 있다.
• 일반적으로 "events"는 mutex locks나 semaphores에서의 resource acquisition/release를 의미한다.

Priority Inversion

• high-priority 프로세스가 커널 데이터를 읽거나 바꾸어야 하는 경우, scheduling challenge가 발생할 수 있다.. 기존 low-priority 프로세스를 preempt할 것인가 아니면 끝나고 할 것인가? 에 대한 선택 문제가 발생. (kernel data는 보통 lock이 걸려있기 때문)
• 예시
  • L < M < H의 우선순위를 가지는 세 프로세스가 있다고 하자.
  • H는 semaphore S를 필요로 하지만, S는 L이 사용중이다. -> H는 L이 끝날 때 까지 기다린다.
  • 중간에 M이 깨어나서 L을 preempt해버림 -> H의 대기시간이 M에 의해 바뀌어 버림.
• 위와 같은 liveness problem이 priority inversion이라고 불린다. -> 둘보다 더 많은 우선순위가 존재하는 system에서 발생.
• priority-inheritance protocol에 의해서 avoid할 수 있다.
  • higher-priority process가 요구하는 자원을 사용중인 모든 프로세스들은 그 자원의 사용이 끝날 때 까지 higher-priority process의 priority를 상속받게 된다.
  • 그 자원 사용이 끝나고 나면 priority는 원래대로 돌아간다.

Evaluation

• 언제 무슨 synchronization tool을 쓸 것인가??
• mutex lock이나 semaphore과 같은 synchronization tools보다 6.4에 소개되었던 hardware적 방법(CAS instruction)은 locking이 존재하지 않기 때문에 overhead가 줄어든다. -> 많이 쓰이는 추세이다. 하지만 low-level인 만큼 알고리즘을 짜기가 어려움.
• CAS-based approach : optimistic(낙관적인) approach
  • 값을 먼저 바꾸려고 시도하고 그 다음에 동시에 값이 바뀌지 않았는지 체크한다. (실제 CAS를 사용한 atomic increasement를 보면 일단 바꾸려고 시도하고 그 후에 temp와 memory값을 비교한다.)
• Mutual-exclusion locking : pessimistic(비관적인) strategy
  • lock을 먼저 획득(다른 프로세스가 이미 접근중이라고 가정)한 후에서야 값을 바꾼다.
• CAS-based synchronization과 traditional synchronization(mutex locks & semaphores) 사이의 contention load에 따른 performance difference(guideline) :
  • Uncontended : 둘 다 굉장히 빠르지만 CAS protection이 traditional synchronization에 비해 더 빠르다.
  • Moderate contention : CAS가 traditional synchronization에 비해 상당히 빠르다.
  • High contention : Under very highly contended loads, traditional synchronization will ultimately be faster than CAS-based synchronization.
• Moderate contention이 더 빠른 이유
  • CAS가 실패했을 경우 loop을 도는데, 몇 바퀴 돌지 않고 바로 실행된다.
  • mutual-exclusion locking의 경우, 할 때 마다 lock을 얻으려고 시도하고, context switching이 필요하다.
• 적당히 맞는 상황에서 맞는 방법을 선택하는 것이 좋다.

참고 자료

• Abraham Silberschatz, Operating System Concepts, 10th edition