[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을 하지 않아 발생한다.
- 예시
![](https://velog.velcdn.com/images/dandb3/post/91fc574d-a854-461a-abd0-b89c6f0e2ca9/image.png)
- P0와 P1이 동시에 실행되었다고 하면, P0는 S를, P1은 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