Chapter 10-2. Multiprocessor and Real-Time Scheduling

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 과의 공통점

1. Priority-Driven Preemptive Scheduling
   (우선순위 기반의 Preemptive Scheduling, 내가 어떤 task 를 처리하다가 그것보다 우선순위가 하나라도 높은 task 가 오면 무조건 하던거 중단하고 새로운 프로세스를 처리한다.)
2. 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 을 가진다.)
3. 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번까지 존재한다. 각각 두세트가 있는 상황이다.

1. 40개의 큐 중 현재 4개의 큐에만 프로세스가 들어 있는 상황이다.
2. P3는 timeout 전에 우선순위가 더 높은 프로세스가 등장해서 Preemptive 된다.
   → 이 경우 다시 active queue 로 돌아간다.
3. 어느 순간 active queue 가 모두 비게 되는데, Queue 를 Active 와 Expired 를 서로 바꾸어 준다.

우선순위 기반의 Preemptive Scheduling 이므로 실행을 하다가 우선순위가 더 높은 프로세스가 나타나면 CPU 를 뺏기고, Non-real time task 에서 CPU 를 많이 사용하는 프로세스들은 우선순위를 낮춰주고 우선순위가 낮은 큐로 들어갈 수 있고 일찍 CPU 를 놓고 I/O 작업을 하러간 프로세스들은 우선순위를 높여줘서 Blocked Queue 에 있다가 다시 Ready Queue 로 들어갈 때는 아까보다 우선순위를 더 높여줘서 들어간다.

⇒ Starvation 가능성이 매우 낮다. 굉장히 fair 하다. (기말고사 문제)
↳ WHY?

두 개의 Queue 가 하나의 Queue 보다 Starvation 가능성이 낮아지게 된다.

내 생각엔 우선순위가 높은 스레드들은 다른 우선순위가 높은 task 들에 의해 Preemptive 당할 가능성이 낮으므로 timeout 까지 CPU 를 모두 사용하고 Expired 로 들어가게 된다. 하지만 우선순위가 낮은 스레드들은 다른 다른 우선순위가 높은 task 들에 의해 Preemptive 당할 가능성이 높으므로 Preemptive 되어 active 에 계속 남아있게 된다. 그렇게 되면 결국 active 에 남게된 우선순위가 낮은 스레드들이 우선순위가 높지만 이미 expired 된 스레드들보다 우선적으로 실행을 마칠 수 있게 되므로 starvation 가능성이 낮아지게 된다.