Windows System Scheduling
Real-time task
→ Round-Robin 방식 사용
↳ 언제나 우선순위 기반의 Preemptive Scheduling 기법이다 🌟
내가 어떤 task 를 실행하고 있다가도 이거보다 조금이라도 우선순위가 높은 프로세스가 갑자기 시스템에 새로 들어오면 하던 거 중단하고 새로 들어온 프로세스를 서비스한다.
Non-Real-time task
→ Feedback 방식 사용
↳ 계속 CPU 를 사용하면 우선순위가 내려가고 CPU 를 사용하면 우선순위가 올라간다.
프로세스들이 한 번 Ready Queue 에 들어가면 끝날 때까지 작업하는 것이 아니라 Ready Queue 에 갔다가 I/O 작업 했다가 Ready Queue 에 갔다가, ... 한 번 Ready Queue 에 갔을 때의 서비스 타임을 Burst time 이라고 부르는데,
Burst time 이 짧다는 뜻은 내가 처음에 0번 큐에서 시작해도 I/O 작업을 반복해서 하다 보니 Burst time 이 계속 짧아지게 되면 2, 3, 4, ... 계속 큐가 올라가게 될 것 이다. 결국 15번 큐에서 서비스가 되게 된다.
Burst time 이 짧은 프로세스는 초기 우선순위에 상관 없이 결국 가장 우선순위가 높은 큐에서 처리가 되게 될 것이다.
⇒ 간단히 말해, SRT 처럼 실행 시간이 짧은 프로세스를 우선으로 하는 Scheduling 방법이라고 생각할 수 있다.
아무리 처음에 15번에서 시작을 했어도 실행시간이 길어서 매번 time quantum 을 끝까지 다 쓰면 14, 13, ... 결국 0번까지 갈 수 있다. 그렇게 되면 CPU 를 잡을 확률이 굉장히 떨어지게 된다.
Windows 는 실행시간이 짧은 프로세스를 먼저 처리하고 실행시간이 긴 프로세스의 우선순위를 낮추어서 나중에 처리되는 방식과 비슷한 성능을 보인다.
즉, SRT 와 비슷한 성능을 보이는 것이므로 성능이 무척 좋다고 할 수 있다.
↔ 그러나 문제점은 Starvation 가능성이 높다는 것이다.
0번 큐는 위에 있는 31개의 큐가 다 비어야 CPU 를 잡을 수 있다.
0 번 큐에 들어 있는 프로세스나 task 들을 위한 어떠한 보호조치가 없다.
UNIX SVR4 Scheduling
160개의 큐로, 큐가 매우 많기 때문에 우선순위를 굉장히 세분화 했기 때문에 완전히 우선순위 기반 시스템이라고 할 수 있다.
Real-time processes (159-100)
- Highest preference to real-time processes (159-100)
- 60개
Kernel-mode processes (99-60)
- Next-highest to kernel-mode processes (99-60)
- 30개
Time-Shared process (59-0)
- Lowest preference to other user-mode processes (59-0)
- 일반적인 유저 프로세스
제일 우선순위가 높은 159번 큐부터 시작해서 0번째 있는 프로세스를 확인하기 위해서는 159번 확인해야 한다.
간단히 우선순위 큐를 살펴보기 위해서 Bit map 을 사용한다. 159번 큐에 누가 있나 없나 한 비트로 표현한 것이다. 각각의 큐에 대기하고 있는 프로세스가 있을 경우엔 1, 없을 경우는 0으로 표현된다. 이렇게 Bit map 을 사용해서 비어 있는 큐를 빠르게 Scan 할 수 있다.
159개를 훑어 보는 거랑 Bit map 을 하나하나 확인하는 것이랑 차이가 있을까? 160bit 는 정수 하나가 32 bit 이므로 5개의 정수로 표현된다. 5개의 정수를 비교하는데 정수가 하필 0이면 32개의 큐가 다 비었다는 의미이다. 그럼 이 32개의 큐는 비교해 볼 필요가 없는 것이다.
그 다음 정수가 또 0이면 여기 32 개의 큐도 다 비었다는 의미이므로 비교해볼 필요가 없다.
그 다음 정수가 0이 아닌 어떤 숫자라면, 나는 거기에 task 가 있는 것이 확실하므로 32 bit 만 검사를 해보면 된다. 그렇게 되면 32개의 bit 만 보게 되므로 Windows 랑 비슷하게 된다.
UNIX SVR4 Scheduling 의 실제 Scheduling 방법
Windows System 과의 공통점
- Priority-Driven Preemptive Scheduling
(우선순위 기반의 Preemptive Scheduling, 내가 어떤 task 를 처리하다가 그것보다 우선순위가 하나라도 높은 task 가 오면 무조건 하던거 중단하고 새로운 프로세스를 처리한다.) - RR for the Jobs w/ the Same Priority (real-time class)
( real time class 에 있는 프로세스 중에 우선순위가 같은 것들이 있다. 이 경우, Round-Robin 으로 작업하게 된다.)- fixed priority and a fixed time quantum
(real time class 에 있는 task 들은 fixed priority 를 가진다. 단, round-robin 을 할 때, time quantum 역시 fixed time quantum 을 가진다.)
- fixed priority and a fixed time quantum
- Priority Feedback (time-sharing class)
(일반 유저 클래스의 경우, CPU 를 많이 사용하면 우선순위를 낮추고 I/O 작업을 많이 하면 우선순위를 높여준다.)- Processor-bound threads down
- I/O -bound threads up
Windows System 과의 차이점
The time quantum allocated to a timesharing process depends on its priority , ranging from 100 ms for priority 0 to 10 ms for priority 59.
Fairness 고려 ⇒ Starvation 줄이려고 노력
timesharing 프로세스인 경우에는 우선 순위에 따라 time quantum 을 다르게 설정한다.
- 0 → 우선순위가 가장 낮음: time quantum 길게 잡아주기
- 59 → 우선순위가 가장 높음: time quantum 짧게 잡아주기
Linux Scheduling
Scheduling classes
0-99 까지의 큐는 real-time class 들을 위한 큐이다.
그런데, 이 클래스를 RR 로 할지 FIFO 로 할지 결정할 수 있다.
1. SCHED_FIFO:
First-in-first-out real-time threads (0-99)
real-time task 들은 실행시간이 매우 짧은 task 들이다.
2. SCHED_RR:
Round-robin real-time threads (0-99)
FIFO 나 RR 둘 중 하나 선택할 수 있다.
3. SCHED_OTHER:
Other, non-real-time threads (100-139)
40개가 존재한다.
Within each class multiple priorities are used
Linux Scheduling for Real-time Classes
FIFO
The system will not interrupt an executing FIFO thread except in the following cases
- Another FIFO thread of higher priority becomes ready
- The executing FIFO threads becomes blocked
- The executing FIFO threads voluntarily gives up the processor following a system call
- If more than one thread has that highest priority, the thread that has been waiting the longest is chosen
CPU 를 잡으면 끝까지 실행한다 생각할 수 있지만,
우선 순위 기반의 Preemptive Scheduling 이므로 FIFO 스레드이기는 하지만,
하나를 실행을 하고 있다 했을 때, 우선 순위 높은 애가 나타나면 무조건 CPU 를 뺏기게 된다.
FIFO 이므로 Block 이 됐을 때, 시스템 콜 같은 것을 요청해서 내가 스스로 CPU 를 반납 했을 때, CPU 를 가져가게 된다.
FIFO 이므로 같은 우선순위인 스레드가 여러개인 경우에 어떤 순서대로 처리할까?
↳ 기다리는 시간이 오래된 프로세스를 먼저 선택한다.
RR
The scheduling policy for RR thread is similar, except for the addition of a time-slice associated with each thread
RR도 우선 순위 높은 스레드가 나타나면 무조건 CPU 를 뺏기게 된다.
Linux Scheduling Data Structures
Non-real time task → 40개의 큐가 존재한다. → 한세트 X, 두세트 O
Active Queue 가 100번 부터 139번 까지 존재하고, Expired Queue 가 100번 부터 139번까지 존재한다. 각각 두세트가 있는 상황이다.
- 40개의 큐 중 현재 4개의 큐에만 프로세스가 들어 있는 상황이다.
- P3는 timeout 전에 우선순위가 더 높은 프로세스가 등장해서 Preemptive 된다.
→ 이 경우 다시 active queue 로 돌아간다. - 어느 순간 active queue 가 모두 비게 되는데, Queue 를 Active 와 Expired 를 서로 바꾸어 준다.
우선순위 기반의 Preemptive Scheduling 이므로 실행을 하다가 우선순위가 더 높은 프로세스가 나타나면 CPU 를 뺏기고, Non-real time task 에서 CPU 를 많이 사용하는 프로세스들은 우선순위를 낮춰주고 우선순위가 낮은 큐로 들어갈 수 있고 일찍 CPU 를 놓고 I/O 작업을 하러간 프로세스들은 우선순위를 높여줘서 Blocked Queue 에 있다가 다시 Ready Queue 로 들어갈 때는 아까보다 우선순위를 더 높여줘서 들어간다.
⇒ Starvation 가능성이 매우 낮다. 굉장히 fair 하다.
↳ 왜? 기말문제임
두 개의 Queue 가 하나의 Queue 보다 Starvation 가능성이 낮아지게 된다.
내 생각엔 우선순위가 높은 스레드들은 다른 우선순위가 높은 task 들에 의해 Preemptive 당할 가능성이 낮으므로 timeout 까지 CPU 를 모두 사용하고 Expired 로 들어가게 된다. 하지만 우선순위가 낮은 스레드들은 다른 다른 우선순위가 높은 task 들에 의해 Preemptive 당할 가능성이 높으므로 Preemptive 되어 active 에 계속 남아있게 된다. 그렇게 되면 결국 active 에 남게된 우선순위가 낮은 스레드들이 우선순위가 높지만 이미 expired 된 스레드들보다 우선적으로 실행을 마칠 수 있게 되므로 starvation 가능성이 낮아지게 된다.
