레디 큐, 메인 메모리에 여러 개의 프로세스가 기다리고 있을 때 현재 실행 중인 게 끝나면 어느 프로세스를 실행해 서비스를 할 것인가를 정해주는 알고리즘을 CPU Scheduling 알고리즘이라고 한다.

1. Preemptive vs Non-preemptive

병원에서 환자가 진료를 기다리고 있는 상황을 생각해 보자.

대기실(Ready Queue)에서 환자(Process)가 진료(CPU)를 기다린다.

앞의 환자가 진료가 끝날 때까지 환자들은 대기실에서 기다린다. 이는 Non-preemptive 스케줄링이라고 한다.

반면, 응급 환자가 나타나면 앞의 환자의 진료가 끝나지 않아도 진료를 시작한다. 이를 Preemptive 스케줄링이라고 한다.

1.1. Preemptive

프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다. 즉, 프로세스가 정상적으로 수행 중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있다.

1.2. Non-preemptive

한 프로세스가 한 번 CPU를 점유했다면, I/O 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못한다.

2. Scheduling criteria

하나의 프로세스가 종료되면 큐에 올려져 있는 다음 프로세스를 실행하는 것이 가장 일반적이고 자연스러울 것이다. 하지만 필요에 따라 여러 방법을 이용할 수 있고, 이때 어떤 방법이 가장 적합할지 비교하기 위한 척도가 필요하다.

• CPU Utilization(CPU 이용률): CPU가 얼마나 놀지 않고 부지런히 일하는가
  • e.g. $P_1$→$P_2$→$P_3$로 실행하니 CPU가 100%로 사용되는데, $P_2$→$P_1$→$P_3$로 실행하니 CPU가 80%는 일하고 20%는 놀더라
• Throughput(처리율): 단위 시간당 몇 개의 작업을 처리하는가
• Turnaround time(반환시간): 어떤 작업이 메인 메모리로 들어가 작업을 끝내고 나올 때까지 걸리는 시간이 얼마나 걸리는가
• Waiting time(대기시간): CPU의 서비스를 받기 위해 Ready Queue에서 얼마나 기다리는가
• Response time(응답시간): 명령을 내리고 첫 응답을 받을 때까지 시간이 얼마나 걸리는가, 주로 interactive system에서 중요한 척도로 사용.

3. CPU Scheduling Algorithms

3.1. First-Come, First-Served(FCFS)

먼저 온 것을 먼저 서비스 해준다. 가장 간단하고 공평한 방법이나, 반드시 좋은 성능을 나타내진 않는다. 아래 Gantt Chart의 Average Waiting Time을 구해보자.

Process	Burst Time(ms)
$P_1$	24
$P_2$	3
$P_3$	3

1. $P_1$→$P_2$→$P_3$

   

   단순히 $P_1$이 먼저 도착했다고 해서 먼저 처리할 경우 AWT는 17ms가 된다.

2. $P_3$→$P_2$→$P_1$

   

   반면 짧게 걸리는 $P_2$, $P_3$를 먼저 처리할 경우 AWT는 3ms가 된다.

⇒ 평균 대기 시간 측면으로 보았을 때 FCFS가 반드시 좋은 방법은 아니란 것을 알 수 있다.

위의 예시처럼 CPU 점유 시간이 긴 프로세스($P_1$)를 CPU 점유 시간이 짧은 프로세스들($P_2$, $P_3$)이 뒤에서 오랫동안 기다리며 시중처럼 따라다니는 것 같은 모습을 Convoy Effect(호위효과)라고 한다.

정리하자면 FCFS에는 호위효과라는 단점이 나타날 수 있고, 이 방식은 Non-preemptive 스케줄링이다.

3.2. Shortest-Job-First(SJF)

가장 짧은 실행 시간이 걸리는 작업부터 먼저 처리한다. 이는 Provably optimal, 즉 수학적으로 증명은 생략하겠으나 가장 이상적인 방법이라고 할 수 있다. 아래 예시를 보자.

Process	Burst Time(ms)
$P_1$	6
$P_2$	8
$P_3$	7
$P_4$	3

SJF 방식을 이용하여 AWT를 구한 결과 7ms가 나온다.

앞서 배운 FCFS 방식을 이용해 구한 AWT는 10.25ms로 역시나 SJF이 가장 효율적인 걸 알 수 있다.

그럼 항상 SJF를 사용하면 최고의 효율을 뽑을 수 있는 거 아닐까?

SJF 방식은 Not realistic하다. 실제 돌아가는 프로세스들은 CPU 점유 시간이 얼마나 걸릴지는 알 수 없기에 prediction이 필요하다. 하지만 프로세스의 예상 점유 시간을 구하기 위해 과거 실행 시간을 기억하고 계산하면 되려 오버헤드가 커진다. 따라서 현실적으로 적용하기 어려운 방법이라고 할 수 있다.

SJF는 Preemptive, Non-preemptive 두 가지 방식으로 만들 수 있다.

Process	Arrival Time	Burst Time(ms)
$P_1$	0	8
$P_2$	1	4
$P_3$	2	9
$P_4$	3	5

• Non-preemptive

  

  레디 큐에 올라와 있는 프로세스 중 가장 짧은 점유 시간을 가진 프로세스가 우선적으로 실행된다. 한 프로세스가 실행 중에 있을 때 점유 시간이 더 짧은 프로세스가 들어온다 하더라도 실행되는 프로세스가 바뀌지 않는다.
  

• Preemptive

  

  한 프로세스가 실행 중에 있더라도, 남아 있는 시간이 짧은 순서대로 점유하는 프로세스가 달라진다. Shortest-Remaining-Time-First(최소잔여시간 우선)이라고도 한다.
  

3.3. Priority Scheduling

우선순위가 더 높은 프로세스를 먼저 서비스해준다.

우선순위는 보통 컴퓨터에서 정수값으로 표기되고, 대부분의 운영체제(Unix/Linux)에서는 숫자가 작은 게 더 높은 우선순위를 나타낸다. 아래 예시를 보자.

Process	Burst Time(ms)	Priority
$P_1$	10	3
$P_2$	1	1
$P_3$	2	4
$P_4$	1	5
$P_5$	5	2

그럼 우선순위는 어떻게 정해질까? 내부적, 외부적 요인에 따라 결정된다.

• Internal: time limit, memory requirement, I/O to CPU burst, …
• External: amount of funds being paid, political factors, …

실제로 컴퓨터가 돌아갈 때 외부에서 계속해서 새로운 프로세스가 들어온다. 이때 우선순위가 낮은 프로세스의 경우, 아무리 오래 기다려도 해당 프로세스보다 우선순위가 높은 작업이 들어오면 계속해서 대기하게 된다. 이렇게 아무리 기다려도 CPU 시간을 차지하지 못하는 상황을 starvation이라고 한다.

이를 해결하기 위해 Ready Queue에서 오래 기다린 프로세스일수록 점진적으로 우선순위를 높여주는 방법을 aging이라고 한다.

3.4. Round-Robin

뿅망치로 머리를 때리면 머리 위에 빙빙 도는 새처럼 빙빙 돌며 스케줄링하는 방식이며, Time-sharing system(시분할/시공유 시스템)에서 많이 사용되는 방법이다.

시간축을 길게 늘여뜨려 놓고 보았을 때, 일정 간격으로 시간축을 나눈다. 이를 Time Quantum 혹은 Time Slice라고 한다. 기호로는 델타(Δ)를 사용한다.

이 방식은 Time Quantum이 지나면 자동으로 다음 프로세스가 CPU를 점유하기 때문에 Preemptive 스케줄링에 해당된다. 아래 예제를 살펴보자.

Process	Burst Time(ms)
$P_1$	24
$P_2$	3
$P_3$	3

Δ = 4ms일 때 AWT를 구하면 아래와 같다.

이 방식은 Time Quantum의 size에 의존적이다.

만약 위의 예제에서 $∆→∞$일 경우 점유 중인 프로세스가 실행이 끝날 때까지 switching이 일어나지 않는다. 즉, FCFS와 동일한 방법이 된다.
$∆→0$인 경우 switching이 빈번하게 일어나 여러 프로세스들이 거의 동시에 일어나는, Processor sharing과 동일하게 본다. 하지만 이 경우 context switching overhead가 커져 결코 좋은 방법으로 볼 수는 없다.

아래 예제에서 Average turnaround time을 구해보자.

Process	Burst Time(ms)
$P_1$	6
$P_2$	3
$P_3$	1
$P_4$	7

Δ = 1ms일 때

Δ = 5ms일 때

이처럼 델타에 따라 turnaround time이 상이하게 나타나는 것을 알 수 있다. 즉, Δ를 얼마로 잡을 것이냐가 성능에 중요한 포인트가 된다.

3.5. Multilevel Queue Scheduling

먼저 프로세스 그룹에 대해 살펴보자. 프로세스는 기준에 따라 몇 가지 그룹으로 나눌 수 있다.

• System processes: OS 커널 수준의 프로세스
  • e.g. 가상 메모리 매핑, 파일 읽기, 통신 등
• Interactive processes: 유저 수준의 대화형 프로세스
  • e.g. 게임
• Interactive editing processes
  • e.g. 워드 프로세서
• Batch processes: 대화형이 아닌 프로세스, 일괄적으로 컴퓨터가 알아서 처리
  • e.g. 컴파일러
• Student processes

Interactive editing 프로세스는 컴퓨터 앞에 직접 앉아서 작업을 하는데 응답이 없으면 답답하다.
반면 Batch 프로세스는 돌려놓고 집에 가도 되기 때문에 조금 느리게 처리되어도 크게 문제가 없다.

이렇게 다양한 성격의 프로세스를 동일한 Ready Queue에 두는 것은 비효율적이게 보인다. 즉, Queue를 여러 개 두고 서비스하는 것이 더 효율적이다. 이를 Multilevel Queue Scheduling이라고 한다.

이 방식의 경우 각각의 Queue에 절대적 우선순위가 존재하거나 CPU time을 각 Queue에 차등 배분한다. 또한 각 Queue는 독립된 scheduling 정책을 사용한다.

3.6. Multilevel Feedback Queue Scheduling

3.5와 마찬가지로 복수 개의 Queue를 두고 프로세스는 하나의 입구로 진입한다.

해당 Queue의 스케줄링 방식대로 처리가 되다가, 일정 시간이 지나도 Queue가 줄지 않으면, 즉 너무 많은 CPU time을 사용하면 해당 스케줄링 방식이 맞지 않는다고 판단(feedback)하고 다른 Queue로 넘긴다.

또한 기아 상태 우려 시 우선순위가 높은 Queue로 프로세스를 옮긴다.

---

Reference

• KOCW 양희재 운영체제