[운영체제/OS] CPU Scheduling

✅ Scheduling이란?

우선 멀티프로그래밍이 뭔지 알아야 한다.

멀티프로그래밍은 프로세서의 자원낭비를 최소화 하기 위해 낭비되는 시간을 다른 프로그램(프로세스) 수행에 쓰게 하여, 하나의 프로세서에서 여러 프로그램(프로세스)을 교대로 수행할 수 있게 하는 것입니다
출처: https://jwprogramming.tistory.com/19
[개발자를 꿈꾸는 프로그래머:티스토리]

 

이렇게 CPU가 멀티프로그래밍 할 때, ready 상태에 있는 process들은 CPU를 차지하기 위해 경쟁하게 된다. 만약 하나의 CPU만이 있다면 다음에 어떤 프로세스를 실행할지 결정해야 한다. 이런 결정을 내리는 OS의 일부분을 scheduler라고 하고, 여기에 사용되는 알고리즘은 scheduling algorithm이라고 한다.

 

process scheduling에 적용되는 이런 대부분의 이슈는 thread scheduling에도 비슷하게 적용된다. 하지만 조금 다른 것은 kernel이 thread들을 관리할 때, 스케줄링은 대부분 thread 단위로 실행되는데 이 thread가 어떤 process에 속한지는 신경쓰지 않는다는 점이다. 

 

아래에서는 우선 process scheduling에 대해 이야기해본다.

 

✅ 언제 scheduling을 하는가

1. 새 process를 생성할 때
2. process가 exit됐을 때
3. process가 block됐을 때
4. I/O interrupt 발생할 때
5. clock interrupt될 때

✔️ Scheduling의 2가지 종류

Nonpreemptive

run되고 있는 process가 block되거나 자발적으로 CPU를 release할 때까지 run하게 냅둔다.

장점 : 강제적으로 CPU를 뺏지 않기 때문에 context switch 발생 가능성이 낮다.

단점 : 무한 루프 발생 가능성이 있다.

Preemptive

일정 시간마다 interrupt 걸어서 run되고 있던 process 중지시키고 scheduler가 다시 scheduling한다.

이 방법을 사용하려면 time interval의 끝에 clock interrupt가 발생해서 CPU 제어권이 scheduler한테 가야 한다. 만약 clock이 없다면 nonpreemptive scheduling 쓰는 방법 밖에 없다.

 

✅ Schduling하기 위한 3가지 환경

Batch

배치 시스템에서는 짧은 요청에 대한 빠른 응답을 초조하게 단말기에서 기다리는 사용자가 없다. 따라서 Nonpreemptive algorithm, 또는 각 프로세스가 오랜 시간을 사용할 수 있는 Preemptive algorithm을 사용할 수 있는 경우가 많다. 여기서는 process switch가 감소하여 성능을 향상시킬 수 있다.

Interactive

한 process가 CPU를 독점하고 다른 프로세스에 대한 서비스를 거부하는 것을 방지하기 위해 Preemptive algorithm이 필수이다.

Real time

process가 오랜 시간동안 실행되는 것이 아닐 수도 있고, 대체로 작업을 빠르게 수행하고 block된다는 것을 알고 있기 때문에 Preemption이 필요하지 않은 경우가 있다.

 

✔️ 환경에 따른 scheduling의 목적

모든 시스템

- Fairness : 모든 process가 공정하게 CPU를 사용하는지

- Policy enforcement : 정책이 예외없이 적용되는지

- Balance : 시스템의 모든 부분이 바쁘도록 (utilization 높게)

Batch systems

- Throughput : 시간당 처리량 극대화

- Turnaround time : submission과 termination 사이의 시간( job을 submit하고 결과를 받는데 걸리는 시간) 최소화.

- CPU Utilization : CPU를 항상 바쁘게 유지

Interactive systems

- Response time : request에 빠르게 응답

- Proportionality : 사용자들의 기대에 부응

Real-time systems

- Meeting deadlines : 손실되는 데이터 막기. (특히 hard real-time에서 중요)

- Predictability : 멀티미디어 시스템에서 품질 저하를 방지. (soft real-time에서 퀄리티 너무 안 떨어지게)

 

✅ Batch system에서의 Scheduling

First-Come, First-Served (FCFS)

요청한 순서대로 CPU에 process 할당

일반적으로 Nonpreemptive

❕ 장점

- 간단함- context switch overhead 없음

- starvation 없음

❗ 문제점

- waiting time(=turnaround time 또는 response time) 증가

- 짧은 일이 긴 일 뒤에 걸리면 안 좋음

 

Shortest Job First (SJF)

CPU time을 미리 아는 경우 짧은 job부터 처리

Nonpreemptive

❗ 문제점

- CPU time 미리 예측하기 어려움 (다만 real-time system 같은건 예외)

- job들의 도착시간이 다르면 waiting time이 가장 적게 보장해줄 수 없음.

- CPU time이 짧은 job들이 계속 들어오면 starvation 발생 가능

 

Shortest Remaining Time Next (SRTN)

- CPU는 남은 run time이 짧은 process부터 선택.

- SJF의 preemptive한 버전

❗ 문제점

- 미리 CPU burst 알아야 함.

- starvation 문제

 

✅ Interactive system에서의 Scheduling

Round-Robin (RR)

- job을 quantum(일정 시간 간격)만큼만 실행. I/O 발생하거나 quantum보다 빨리 끝나면 미리 종료도 가능하다.

- quantum만큼 사용하고 나면 큐의 맨 뒤로 간다. 

❕ 장점

- CPU 얼마나 사용하는지 알 필요가 없다.

- starvation이 없다.

❗ 문제점

- quantum을 얼마로 설정해야 할지 정하기 어렵다. 작으면 context switch가 빈번하고, 크면 response time이 커진다.

 

Priority Scheduling

- ready queue에 있는 process 중 가장 우선순위가 높은 process에게 CPU를 할당

- 우선 순위를 정하는 방법은 static, dynamic 2가지로 나눌 수 있다.

1. static : 한 번 정해지면 변하지 않음.
2. dynamic : I/O bound job에게 높은 우선순위를 줌. => 퀀텀을 조금만 썼던 process에게 우선권 준다는 말. 1/f로 우선권 줌. (f : 지난 퀀텀에서 process가 사용한 비율)

❗ 문제점

- starvation 문제 => 만약 높은 우선순위의 job이 계속 들어오면 낮은 우선순위의 job은 계속 실행될 수 없다.

(※우선순위에 기반한 알고리즘에서는 항상 starvation 문제가 존재한다) 

💡 해결

age

- 기다린 시간에 비례하여 우선순위를 높여준다.

- waiting time이 길어지면 우선순위를 높여주고, CPU를 사용하거나 퀀텀을 다 썼다면 우선순위를 낮춘다.

 

Multiple Queues

Scheduling algorithm들은 실제에서는 여러 개가 결합되어 사용될 수 있다. 바로 Multiple queue를 사용해서 말이다. 

- class : process들을 같은 priority끼리 묶은 것.

- class들 간에는 Priority scheduling

- class 내에서는 Round-Robin scheduling

❗ 문제점

age 적용을 하지 않기 때문에 starvation 문제가 있다.

 

Multi-level feedback queues (MLFQ)

- 각 큐는 다른 타입의 job들 (batch, interactive, system, CPU-bound 등)

- priority 낮을수록 긴 quantum을 가진다.

- 같은 큐에서는 Round-Robin 적용.

- job 특성이 바뀌면 다른 큐로 갈 수 있다. => feedback : CPU-bound ↔ I/O-bound

❗ 문제점

starvation 존재

 

Guaranteed Scheduling

n개의 process가 있다고 할 때 모든 process는 공평하게 총 CPU cycle의 1/n을 갖는다는 전제를 바탕으로 한다.

- ratio는 실제 사용 시간/할당된 시간인데 이 ratio가 낮아지면 우선순위가 올라간다. 즉, 할당된 시간에 비해 실제 사용을 적게 하는 job의 우선순위가 올라간다는 말이다. 이 방법을 사용하면 결국 전제 process들의 ratio가 비슷하게 유지되게 된다.

- ready queue에 있던 process들 중 가장 ratio가 낮은 것부터 실행한다.

 

Lottery Scheduling

이름처럼 복권에 당첨된 process에게 CPU를 할당해준다. 그러니까 process들은 ticket을 갖고 있고, scheduler가 뽑은 ticket을 갖고 있는 process에 CPU 할당해주는 방식이다.

💡 특징

- performance assurance => process가 갖고 있는 티켓 수만큼 CPU 사용이 보장됨.

- 새로 들어온 process들도 운이 좋으면 바로 뽑힐 수 있다.

- lottery ticket을 상황에 따라 다른 프로세스에게 넘길 수 있다.

- 원하는 CPU 사용 비율만큼 할당해줄 수 있다.

❕ 장점

- starvation이 없음.

 

Fair-Share Scheduling

- 프로세스 관점에서 할당하는 것이 아닌 사용자 관점에서 할당한다.

 

✅ Real-Time System에서의 Scheduling

Real-time에서 scheduling은 process behavior이 예상 가능하고 미리 알 수 있다는 전제를 바탕으로 한다.

✔️ 목적 : schedulable?

scheduling했을 때 이벤트를 어떻게 scheduling하는지보다는 deadline 안에 처리 가능한지 여부가 가장 중요하다.

예를 들어, m개의 periodic한 이벤트가 있다. 이벤트 i는 Pi의 주기로 발생하고, 처리에 Ci만큼의 시간이 소요된다고 할 때 schedulable한지 알아보려면 아래의 값이 1을 넘는지 알아보면 된다.

이 조건을 만족하지 못한다면 이벤트 처리가 계속 밀리다가 다음 이벤트 발생까지 다 처리하지 못하고 deadline을 넘기게 된다.

 

[참고] Andrew S.Tanenbaum, Herbert Bos, ⌜Modern Operating Systems⌟, PEARSON, 2015, 149-165