[OS] CPU Scheduling - 어떤 Job이 CPU를 선점할까

우리는 컴퓨터를 사용할 때 한 가지 작업만 하지 않는다. 크롬도 키고 vscode도 키고 카톡도 하고 유튜브도 봐야된다.

CPU 스케줄링은 여러 종류의 Job들이 섞여있는 운영체제 환경에서 이러한 다중 프로그래밍을 가능하게 하는 동작 기법이다.

 

운영체제의 CPU 스케줄링은 다음의 두 가지 사항을 고려해야 한다.

• Interactive Job에게 적절한 시기에 Response를 제공하는 것
• CPU와 I/O device 등 시스템 자원을 골고루 & 효율적으로 제공(I/O-bound job / CPU-bound job)

 

CPU 스케줄러는 Ready 상태의 프로세스 중 CPU를 할당할 프로세스를 선택하는 역할, Dispatcher는 CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘기는 역할을 수행한다(Context Switching).

 

CPU 스케줄링이 필요한 프로세스의 상태 변화에는 아래와 같은 경우가 존재한다.

• Running ➡ Ready : (ex. 할당 시간 만료로 인한 timer interrupt)
• Blocked ➡ Ready : (ex. I/O 완료 후 인터럽트)
• Running ➡ Blocked : (ex. I/O 요청 시스템콜)
• Terminate

위의 두 상태 변화는 preemtive 스케줄링, 아래의 두 변화는 non-preemtive 스케줄링이 발생한다.

두 가지 스케줄링 방식의 차이는,

preemtive 방식은 task가 다 끝나지 않더라도 OS로부터 다른 프로세스에게 CPU 제어권을 넘겨주는 것이고, non-preemtive 방식은 task가 다 끝나고 자발적으로 반납하는 것이 차이점이다.

 

Scheduling Criteria

• CPU utilization(이용률) : 전체 시간 중 CPU가 놀지 않고 일한 시간
• Throughtput(처리량) : 시간 당 처리할 수 있는 job의 양
• Turn-around Time : (CPU를 쓰기 위해 대기 ~ 끝날 때) 까지 소모된 시간
• Waiting Time(대기 시간) : Ready Queue에서 대기한 시간
• Response Time(응답 시간) : Ready Queue에 들어와서 처음 CPU를 얻기 까지 걸린 시간

 

이제 다양한 스케줄링 기법들에 대해 알아보자 ❗❗

Scheduling Techniques

 

FCFS(First-Come-First-Served)

: job이 도착한 순서대로 처리하는 기법. 들어오는 프로세스의 순서에 따라 평균 대기 시간이 결정된다.

 

SJF(Shortest-Job-First)

: Ready Queue에서 CPU Burst Time이 짧은 job 순서대로 CPU을 할당하는 기법

(현재 수행중인 프로세스보다 CPU Burst Time이 더 짧은 프로세스가 들어올 경우 CPU를 재할당하는 preemtive 스케줄링 기법은 SRJF이다. 이러한 경우에는 minimum average wating time을 보장하지만 context switching이 너무 자주 일어나 overhead가 발생할 수 있다.)

SJF 방식은 CPU Burst가 긴 프로세스는 영원히 CPU를 할당받지 못 하는 starvation 현상이 일어날 수 있다.

CPU Burst time은 예측하기 어렵기 때문에, 과거의 CBT를 이용해 추정하는 수 밖에 없다.

 

RR(Round-Robin)

: 각 프로세스가 동일한 크기의 Time Quantum(할당 시간)을 가지며, 할당 시간이 지난 프로세스는 preemted 당하고 Ready Queue로 돌아가 대기한다. 

이 방식은 현재 대부분의 OS에서 채택하고 있는 CPU 스케줄링 방식이며, Priority Scheduling 기법이다.

Priority Scheduling : highest priority를 가진 프로세스에게 CPU를 할당하는 방식
├ Preemtive Schduling - 더 높은 priority의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 반납
└ Non-Preemtive Scheduling - 더 높은 priority의 프로세스가 도착하면 Ready Queue의 Head에 삽입

우선순위가 낮은 프로세스의 경우 CPU를 점유하지 못 하는 starvation 현상이 발생할 수 있으나, 대기 시간이 길어지면 우선순위는 높여주는 Aging 기법을 사용하여 해결 가능하다. 

 

N개의 프로세스가 Ready Queue에 들어가 있고, Time Quantum이 q time unit이라 할 때

➡ 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 가진다

➡ 어떤 프로세스도 (n-1) q time unit 이상 기다리지 않는다

이 때 q가 너무 클 경우 도착 순서대로 처리하는 방식인 FCFS와 유사하게 되고, q가 너무 작으면 Context Switching이 너무 자주 발생해 오버헤드를 초래하니 적당한 q time unit을 선정하는 것이 중요하다.

일반적으로 SJF 스케줄링 방식보다 Average Turn-around Time(평균 처리 시간)은 길지만 Response Time은 짧다는 특징이 있다.

 

Multi-Level Queue

위의 방식들은 Ready Queue 하나에서 스케줄링을 하는 기법이었지만, 큐를 여러 개 두고 사용하는 스케줄링 방법이 존재한다.

Ready Queue를 여러 개로 분할하여 Interactive Process ↔ Batch Process로 분할하여 관리할 수도 있고, 각 큐 마다 독립적인 스케줄링 알고리즘을 적용할 수도 있다.

모든 큐에 프로세스가 존재할 때, 어떤 큐에 있는 job이 CPU를 선점할 지에 대한 스케줄링 또한 필요한데

• Fixed priority scheduiling : priority가 높은 큐가 빌 때에만 낮은 큐에 있는 job이 serve한다
• Time slice : 각 큐에 CPU time을 적절한 비율로 할당한다

의 두 가지 방법이 있다.

 

Multi-Level Feedback Queue

: priority가 다른 여러 Ready Queue를 사용하는 스케줄링 기법

• 도착하는 프로세스는 최상위 Priority Ready Queue에 진입한다
• 주어진 time quantum 내에 처리하지 못 하면 다음 대기열에 진입한다
• 최하위 Priority Ready Queue는 FCFS 기법을 사용한다

 

기타 스케줄링 기법들

Multi-Processor Scheduling

• Homogeneous processor : Queue에 한 줄로 세운 뒤 프로세스가 알아서 꺼내가기
• Load Sharing : 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘
• Symmetric Multi-Processing : 각 프로세서가 알아서 스케줄링 결정
• Asymmetric Multi-Processing : 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임

 

Real-Time Scheduling

• Hard real-time scheduling : task는 정해진 시간 내에 반드시 끝내도록 스케줄링
• Soft real-time scheduling : task는 일반 프로세스에 비해 높은 priority를 부여

 

Thread Scheduling

• Local Scheduling : User Level Thread의 경우 사용자 수준 쓰레드 라이브러리에 의해 어떤 Thread를 스케줄링 할 지 결정
• Global Scheduling : Kernel Level Thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄링할 지 결정