CPU Scheduling

June·2022년 2월 8일

1. CPU 스케줄링이란?

CPU 스케줄러는 다중 프로그램 운영체제의 기본이다. 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다.(자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것)

좋은 스케줄링 조건
1) 오버헤드 ↓
2) 사용율(CPU를 최대로 바쁘게) ↑
3) 기아 현상(starvation) ↓

스케줄링의 필요성

I/O, interrupt(trap)등이 발생하면 해당 원인 선처리 후, main program으로 복귀하는데
이 때 waiting 상태로 바뀐 main program 혹은 다른 wait 상태의 program 들을 우선순위를 결정하여
(wait 상태이어도 CPU를 점유하고 있음)
최종적으로 가장 효율적인 process 우선순위를 결정하는 것이 CPU 스케줄링의 의미

2. 선점 / 비선점 스케줄링

선점( Preemptive )
OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우
- CPU 이용을 우선순위 높은 프로세스가 강제로 차지할 수 있음
- 우선순위 높은 프로세스 처리가 먼저 일어나야할 경우 유용, 추가적인 overhead 발생으로 처리시간 예측 힘듦
- IO요청 / 응답, Interrupt, 작업완료 시점에서 스케줄링이 일어날 수 있음
비선점( Non-Preemptive )
프로세스 종료 OR I/O 등의 이벤트가 있을 때까지 실행 보장
- 작업 완료시에만 스케줄링

3. 비선점 /선점 스케줄링 종류

비선점 스케줄링 (Nonpreemptive Scheduling)

이미 할당된 자원을 다른 프로세스가 뺏을 수 없음

응답시간의 예측이 편하며, 일괄처리 방식에 적합함

단점으로는 덜 중요한 작업이 자원을 할당 받으면 중요한 작업이 와도 먼저 처리 될 수 없음

FCFS (First-Come First-Served)
프로세스는 Ready Queue 에 도착한 순서대로 CPU를 할당 받는다. 작업 완료 시간을 예측하기에 매우 용이하다. 하지만 덜 중요한 작업으로 인해 중요한 작업이 기다릴 수도 있다. Convoy effect 가 발생할 수 있다.
(Convoy effect : 수행 시간이 짧은 프로세스가 CPU를 오래 기다리는 현상)
SJF (Shortest-Job-First)
Ready Queue 에 있는 프로세스 중, 수행시간이 짧은 것을 먼저 수행한다. 평균 대기 시간을 감소시킨다.
HRN (Hightest Response-ratio Next)
긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법이다. 수행시간의 길이와 대기 시간을 모두 고려해 우선순위를 정한다.
(우선순위 = (대기 시간 + 실행 시간) / 실행 시간)
Priority Scheduling
프로세스마다 우선운위를 부여하여 높은 우선순위를 가진 프로세스에게 먼저 자원을 할당하는 기법이다. 우선순위가 낮을 경우 기아(Starvation) 현상이 일어날 수 있다.
(기아현상(Starvation) : Ready Queue 에서 대기하고 있는 낮은 우선순위의 프로세스가 무한정 기다리는 현상
에이징(Aging) : 기아현상을 해결하기 위한 방법으로 오랫동안 기다린 프로세스에게 우선순위를 높여주는 기법)

선점 스케줄링 (Preemptive Scheduling)

우선순위가 높은 프로세스를 빠르게 처리할 수 있음

어떤 프로세스가 자원을 사용하고 있을 때, 우선순위가 더 높은 프로세스가 올 경우 자원을 뺏음

빠른 응답시간을 요구하는 시스템에서 사용

단점으로는 잦은 문맥 교환으로 오버헤드가 증가함

SRT (Shortest Reamining Time)
짧은 시간 순서대로 프로세스를 수행한다. 남은 처리 시간이 더 짧은 프로세스가 Ready Queue 에 들어오면 그 프로세스가 바로 선점된다. SJF 기법의 preemptive 버전 이라고 생각할 수 있다
Round-Robin
시분할 시스템에 사용되는 기법으로, 각 프로세스는 같은 크기의 CPU 시간을 할당 받고 선입선출에 의해 수행된다. 할당시간이 클 경우 FCFS 와 비슷해지고, 할당시간이 작은 경우 오버헤드가 증가한다.
Multi-level Queue
MQ 의 핵심은 Ready Queue 를 여러 개로 분할 하고, 이 Ready Queue 사이에 우선순위가 존재하는 것이다. 따라서 큐 사이에도 스케줄링 이 일어나게 된다. 따라서 각각의 큐에서 스케줄링 이 일어나며 Ready Queue 사이에서 스케줄링이 일어나 MQ 의 큐 개수 보다 한 개 더 많은 스케줄러가 필요하다. 또한 우선순위가 높은 큐에 지속적으로 프로세스가 들어오면 낮은 우선순위를 가진 프로세스에 기아현상(Starvation) 이 발생할 수 있다.

Foreground
-interactive 한 작업을 배치Round-Robin 으로 CPU 스케줄링
Background
-interactive 하지 않은 작업을 배치FCFS 으로 CPU 스케줄링

Multi-level Feedback Queue
MQ 와의 가장 큰 차이점은 큐 사이의 프로세스 이동 이다. 우선순위가 높은 프로세스에게는 불이익을, 낮은 프로세스에게는 이익을 제공하는 에이징(Aging) 을 통해 기아현상을 방지한다.

기본적으로 MFQ 에서는 가장 우선순위가 낮은 큐를 제외하고는 모두 Round-Robin 스케줄링을 사용한다. (가장 낮은 큐는 FCFS or RR)

이 때, 우선순위가 높은 큐 일 수록 짧은 Time slice 를 주고 한번의 Time Slice 안에 그 프로세스의 실행이 끝나지 않으면 한단계 낮은 우선순위를 가지고 있는 큐로 보내게 된다.

반대로, 어떤 큐에서 일정시간동안 실행되지 못한 프로세스는 한단계 높은 우선순위의 큐로 보내게 되는 것이다.