Operating System 8 - Mutex lock

 problem of semaphore
timing error : 될 때도 있고 안 될 때도 있다. 왜냐하면 초기값의 상태에 따라 먼저 수행할 프로세스가 바뀔 수 있기 때문이다.

초기 상태가 1일 경우 signal / wait의 순서로 실행한다면 critical section에 두 프로세스가 동시에 들어가게 된다. 만약 wait/wait라면 자기 자신에 대한 데드락이 걸려 시스템이 멈추게 된다. 또 wait 없이 시작되거나 signal을 안해준다면 마찬가지로 critical section에서 race condition이 생기거나 해당 구역에 아무도 접근하지 못하는 문제점이 발생한다.

Monitor
이런 동기화 문제를 해결하기 위해서 HLL에서 이런 문제를 풀어주는 모듈을 제공해준다. 이것이 Monitor이다.
semaphore와 역할이 같지만 컨트롤하기 더 편리하다. 각 프로시저 내부에서만 접근이 가능한 local data variable을 가지고 있다. 그리고 하나의 모니터 안에는 하나의 프로세스만 들어가서 수행가능하다. (한놈만 monitor 안에 들어오도록 하여 상호배제를 구현)
- condition variable & x.wait() / x.signal() : 동기화를 하는데는 앞서와 동일하게 condition variable과 wait / signal 함수를 통해 조작할 수 있다. 이 때 원하는 조건을 condition variable x에 설정하고, 이를 사용할 때 알맞은 wait/signal을 호출하면 된다. 그래서 여러 condition variable이 자신의 큐를 가지고 있고 wait와 signal이 호출되면 조작되어 작동된다. 어느 시점에 반드시 하나만 실행되므로 mutual exclusion을 보장할 수 있다. 따라서 코딩에서 이런 문제점을 고려하지 않아도 된다.

semaphore는 프로그래머가 누가 들어오고 막는지를 모두 설정해줘야 하지만 monitor는 모두 구현되어 있으므로 상호배제와 동기화를 더 쉽게 사용할 수 있다. 그렇기에 상황에 맞게 mutex / semaphore / monitor를 알맞게 선택하여 사용하면 된다.

- condition variable choice
signal을 하면 wait 큐에 대기하던 프로세스가 실행되어야 한다. 그러나 monitor는 반드시 하나만 수행될 수 있으므로 signal을 한 프로세스가 자신을 모두 다 수행하고 wait 프로세스를 수행할 지 아니면 바로 wait 프로세스를 수행할 지 선택해야 한다. monitor는 concurrent pascal comprise의 방식으로 구현되어 있는데, 이는 signal을 한 프로세스는 바로 끝나고, wait의 프로세스가 바로 호출되자마자 실행되어야 한다. 그래서 signal은 해당 프로세스의 모든 작업을 다 끝낸 다음 호출하고, wait는 프로세스의 시작 부분에서 호출되도록 코드를 짜야 한다.

wait()에 걸리는 프로세스들은 monitor의 waiting area에 존재하는 큐에서 대기하게 된다. 그래서 모니터 외부에서 들어오는 큐보다 내부에서 다른 wait를 풀어줄 수 있는 signal을 가지고 대기하는 프로세스를 먼저 처리해준다.

Liveness
mutex lock / semaphore는 상호배제는 가능하지만 progress / bounded waiting에 대한 보장은 해주지 않는다. (코딩으로 프로그래머가 직접 알아서 구현해야 한다.) 따라서 무한히 대기해야할 프로세스가 생길 수도 있다.
그래서 liveness는 progress를 보장하기 위해 만족해야 하는 특성들이다. 그런데 이것들이 보장되지 않는 경우가 deadlock과 priority inversion이다.


Real-Time CPU scheduling
RT-OS scheduler : 논리적인 판단을 내리는 것 뿐 아니라 그 판단을 내리고 수행하는 시점도 중요한 real-time system에서 처리. 실시간 유도 미사일, 위성체 조작 등에서 많이 사용.

실시간에 대해 빠른 대응이 중요하므로 short-term task scheduler가 가장 중요하다. 따라서 공정성, 평균 응답 시간 등을 상대적으로 신경쓰지 않는다. 이 정도에 따라 hard/soft 로 구분한다. hard는 불이 난 것, 브레이크를 밝는 것 처럼 바로 응답해야해서 deadline을 반드시 충족시켜야 하는 것들이고, soft는 에어컨의 설정 온도를 맞추는 것들이 된다.

또한 주기적으로 체크하여 확인하는 것과 비주기적으로 시작/끝내야 할 시간을 설정하며 들어오는 것들이 있다.

따라서 RT에서는 일반적인 시스템보다 priority의 파워가 더 세다. 따라서 preemptive scheduling이 사용된다. (실생활에 빠른 응답을 하기 위해) 그리고 interrupt latency도 최대한 줄여야 한다.

Characteristic of RT system

- Determinism(인식 전) : 설정한 시간 내에 반드시 완료되어야 한다. 이는 해당 컴퓨터 환경에 따라 결정된다. 그리고 실생활에서 다수의 인터럽트가 발생하므로 interrupt를 인지하는 시간이 짧아야 한다. 따라서 일반적인 시스템보다 이를 인식하는 텀이 짧다.

- Responsiveness (인식 후): 위와 합쳐서 총 response time을 구할 수 있다. 따라서 이는 인터럽트를 인식하고 처리하는데 걸리는 시간이 된다.
- User control : 유저가 priority에 대한 정보를 모두 입력해주어야 한다. 또한 페이징 기법, 처리 알고리즘 등도 모두 유저가 해야 한다. 따라서 실시간 시스템에서 원하는데로 작동하기 위해서는 유저가 많은 작업을 해주어야 한다.
- Reliability : 실시간 시스템은 종료되면 안되므로 신뢰성이 높아야 한다.
- Fail soft operation : 중대한 오류가 발생하더라도 현재 자료 등을 유지해야 한다. 그리고 stability (soft는 무시하더라도 hard는 무조건 맞추는 것)가 높아야 한다.

RT scheduling
- Priority driven non-preemptive scheduler on preemption points : 짧은 interval 마다 확인하여 가장 높은 priority로 교체
- immediate scheduling : 이전 실행중인 것이 critical section만 아니면 priority가 높은 것으로 바로 교체하는 것.

Scheduling algorithm
- static table driven : 모든 것들의 실행시간과 우선순위를 모두 연산하여 테이블에 저장. 주기적인 task가 있고 모두 예측 되었을 때 사용하기 좋다. 그러나 유연성이 떨어진다. (새로운 task가 있으면 표를 다 뜯어고쳐야 함) earliest-deadline first
- static priority-driven preemptive scheduling : priority가 높은 것이 들어오면 바로 선점 해주는 것. time constraint에 대해 priority가 설정된다. rate monotonic algorithm.
- dynamic planning based scheduling : task가 오면 이를 실행하기 전에 이전 scheduling 한 계획과 비교하여 이를 실행할 수 있는지 확인하고 만약 할 수 없다면 거부한다.
- dynamic best effort scheduling : task가 올 때마다 priority를 배정하여 실행한다. 반드시 요구사항을 맞출 수는 없지만 유연성이 좋고 구현하기 간단하기에 실생활에서 많이 사용한다.

Deadline scheduling
그러나 실제 이런 RT system은 어떻게 스케쥴링하고 priority를 설정하는 것보다 deadline에 맞도록 들어온 task들을 처리하는 것이 더 중요하다. 따라서 이를 만족하기 위해서 필요한 정보들이 추가로 더 존재한다.
- ready time : 실행이 가능한 시간
- starting deadline : task가 시작해야 하는 시간
- completion deadline : task가 끝나야 하는 시간
- processing time : 처리 시간 - 예측에 사용됨
- resource requirement : 필요한 리소스를 알려주면 상태를 고려하여 계획할 수 있음
- priority
- subtask scheduler : fork/thread에 대한 여러 deadline 설정을 관리 (soft/hard 등)

Earliest deadline : deadline이 가장 먼저 오는 것을 먼저 수행. (비선점)
Earliest deadline with unforced idle time : deadline이 급하지 않다면, 다른 작업이 들어올 수 있으므로 바로 시작하지 않고 deadline이 급할 때 되어서 시작하는 것. 주로 starting deadline에 대해서 적용한다. (비선점) 이 경우 response time은 안좋아질 수 있지만 requirement를 더 잘 맞출 수 있다.

rate monotonic scheduling : 주기가 짧게 들어오는 것들일 수록 priority를 높게 주는 방법. 이 때 RT를 만족하기 위해서는 cpu가 처리 가능한 프로세스보다 더 많이 들어오면 안되므로 주어진 시간에 대해 처리 가능한 최대 프로세스 개수 n을 찾아야 한다. 따라서 C/T < n(2 ^ 1/n -1)을 만족하는 n을 찾으면 된다.
이 때 C/T는 전체 프로세스의 주기마다 들어오는 작업량을 전체 합친 것이 된다. 따라서 만약 C/T가 현재 프로세스 n의 연산 값보다 작다면 deadline에 알맞게 수행할 수 없다.

Priority inversion
lower priority를 가지는 task가 higher priority task를 밀어내고 수행되는 상황. 실제로 화성 탐사선 패스파인더에서 발생하였기에 유명해졌다.
이는 block 상황에서 critical section에서 수행중인 우선순위가 낮은 것을 높은 것이 기다리는 중에 그것보다 높은 우선순위가 들어와서 낮은 것이 막히고, 이를 기다리는 더 높은 우선순위도 밀리는 방식으로 발생한다.
이는 별 문제 없어보일 수 있지만, 만약 새로 들어온 우선순위가 매우 길다면 가장 우선순위가 높은 것의 deadline을 맞출 수 없어서 무한 재부팅을 하는 경우가 발생할 수 있다.

이는 critical section에서 수행되는 낮은 우선순위의 프로세스들을 자신의 작업에 block이 걸린 가장 높은 우선순위를 상속받도록 하는 priority inheritance 를 적용하여 해결할 수 있다. 따라서 이럴 경우 더 높은 우선순위가 들어오더라도 더 높은 우선순위를 상속받았으므로 먼저 수행될 수 있다. 그리고 모두 수행하여 가장 높은 우선순위의 block이 해제된 이후에는 낮은 우선순위는 다시 자기자신의 우선순위로 돌아가도록 하면 된다.