[Windows System] 스케줄링 알고리즘과 우선순위

˚ 선점형(Preemptive) OS와 비선점형(Non-Preemptive) OS
- 프로세스의 실행을 다른 프로세스로 넘기는 방식에 따라서 선점형 OS와 비선점형 OS를 구분한다. OS의 기본 개념을 공부한다는 의미에서 이 두 가지 OS의 성격을 간략히 짚고 넘어간다.

· 비선점형(Non-Preemptive) OS : 현재 실행 중인 프로세스보다 높은 우선순위의 프로세스가 등장한다고 해서 실행의 대상을 바로 변경하지 않는다. 새로 등장한, 보다 높은 우선순위의 프로세스가 실행되기 위해서는 현재 실행 중인 프로세스가 명시적으로 CPU를 양보할 때까지, 혹은 I/O 작업 등으로 블로킹 상태에 놓일 때까지 기다려야만 한다.
· 선점형(Preemptive) OS : 현재 실행 중인 프로세스보다 높은 우선순위의 프로세스가 등장하면 스케줄러에 의한 실행순서 조정이 적극!가해진다. 물론 우선순위가 높은 프로세스가 실행된다. (※ 기아(Starvation) 현상 발생가능)

---

˚ (선점형 OS) 우선순위(Priority) 스케줄링 알고리즘
- 우선순위 스케줄링 알고리즘이란 각각의 프로세스마다 우선순위를 부여해서 우선순위가 높은 프로세스를 먼저 실행시키는 방식이다. 우선순위가 다른 두 프로세스를 동시에 실행할 경우 우선순위가 높은 프로세스가 작업을 마치지 않는다면, 우선순위가 낮은 프로세스는 결코 실행되지 않는다. 이러한 현상을 가리켜 기아현상이라고 한다.

˚ (선점형 OS) 라운드 로빈(Round-Robin) 스케줄링 알고리즘
- 우선순위가 동일한 프로세스의 경우 프로세스의 실행에 대해서 형평성의 문제가 발생한다. 이를 해결하기 위해서 Windows는 라운드 로빈 스케줄링 알고리즘을 적용한다.
- 같은 우선순위의 프로세스들간 형평성 유지를 위해, 정해진 시간 간격만큼만 실행을 하고 우선순위가 동일한 다픈 프로세스에게  CPU의 할당을 넘기는 방식을 제공한다. 오로지 형평성 유지를 위해서다.
- 실행의 최소 단위 시간 간격을 가리켜 퀀텀(Quantum) 혹은 타임 슬라이스(Time Slice)라 하는데, 동일한 우선순위의 모든 프로세스들은 이 타임 슬라이스를 기준으로 CPU의 할당을 넘기게 된다.
- 타임 슬라이스를 길게 하면 인터렉티브한 시스템에서 문제가 될 수 있다. 즉 마우스로 드래그앤드롭을 하는데 반응이 늦게 나타나는 일이 발생하게 되는 것이다. 그렇다고 해서 타임 슬라이스를 너무 짧게 잡으면 그만큼 문맥교환이 자주 발생해서 성능에 저하를 가져다 준다.

[Windows의 스케줄링 알고리즘]

- Windows는 우선순위 기반과 라운드 로빈 기반 알고리즘을 적절히 혼용하여 선점형 운영체제 특성을 나타내도록 디자인되었다.


˚ (선점형 OS) 스케줄링 알고리즘에 의해서 스케줄링이 진행되는 시점
- Case 1 : 매 타임 슬라이스(Time Slice)마다 스케줄러 동작
- Case 2 : 프로세스가 생성 및 소멸될 때마다 스케줄러 동작
- Case 3 : 현재 실행 중인 프로세스가 블로킹 상태에 놓일 때마다 스케줄러 동작


˚ (선점형 OS) Priority Inversion
- 이것은 말 그대로 프로세스의 우선순위가 뒤 바뀌는 현상을 말한다. 일단 상황을 먼저 연출해 보겠다. 다음과 같은 우선순위를 가지는 프로세스가 있다. 

프로세스 A > 프로세스 B > 프로세스 C

- 프로세스 A와 프로세스 C가 IPC로 연결되어 있는 상태라고 가정한다. 프로세스 A가 실행도중 프로세스 C가 계산해서 던져주는 값을 받기 위해서는 프로세스 A는 잠시 블로킹 상태에 놓이며 프로세스 C에게 자신의 CPU 실행순서를 넘기고자 한다. 하지만 프로세스 A가 불로킹 된 순간 잠시 대기하고 있던 프로세스 B가 실행된다. 프로세스 C보다 우선순위가 높기 때문이다. 이 순간 프로세스 B는 프로세스 A보다 우선순위가 높은 것처럼 행동하게 되는 것이다.
- Priority Inversion 방지 방법 : 프로세스 A가 무책임하게 그냥  블로킹 상태로 빠질 것이 아니라, 프로세스 C에게 자신의 우선순위를 잠시 위임하고 블로킹 상태로 빠지면 해결된다.

---

˚ Windows 프로세스 우선순위
- Windows는 총 6단계의 우선순위 계층을 제공한다. 각 우선순위의 상대적인 높고 낮음을 보기 바란다. 숫자가 높을수록 높은 우선순위를 지닌다.

Priority	의미
IDLE_PRIORITY_CLASS	기존 우선순위 4
NORMAL_PRIORITY_CLASS	기존 우선순위 9
HIGH_PRIORITY_CLASS	기존 우선순위 13
REALTIME_PRIORITY_CLASS	기존 우선순위 24
ABOVE_NORMAL_PRIORITY_CLASS	NORMAL_PRIORITY_CLASS 보다 높고  HIGH_PRIORITY_CLASS 보다 낮다.( 9< x < 13 )
BELOW_NORMAL_PRIORITY_CLASS	IDLE_PRIORITY_CLASS 보다 높고  NORMAL_PRIORITY_CLASS 보다 낮다. ( 4 < x < 9 )