[운영체제] CPU Scheduling

CPU Scheduling이란 무엇인가

CPU Scheduling이란 Ready Queue에 존재하는 작업들의 CPU 사용 시점을 결정하는 과정을 의미합니다.

멀티 태스킹을 위해 필요한 운영 체제의 핵심 기능이며 효율적인 CPU 사용을 위한 다양한 스케쥴링 알고리즘이 있습니다.

 

CPU Scheduler

CPU Scheduling을 수행하기 위한 소스코드 모듈을 의미합니다.

Ready Queue에 존재하는 작업들 중 다음에 실행할 작업을 선택합니다.

 

Dispatcher

CPU Scheduler 중 context-switch를 담당하는 소스코드 모듈을 의미합니다.

CPU Scheduler에 의해 선택된 작업에게 CPU의 제어권을 넘깁니다. (dispatch)

 

스케쥴링의 두 가지 방식

1. 자진 반납 (Non-preemptive)

CPU의 사용 권한을 자진해서 반납하는 것을 의미합니다.

 

2. 강제 반납 (Preemptive)

CPU의 사용 권한을 Interrupt를 통해 강제로 뺏어오는 것을 의미합니다.

 

Scheduling Algorithm을 평가하는 기준 (Scheduling Criteria)

CPU Utilization (이용률)

일정 시간 내에 CPU가 사용된 시간을 의미한다.

일반적으로 40%~90% 정도를 유지한다.

이 수치는 높을 수록 좋다.

 

Throughput (처리량)

단위 시간 당 처리하는 프로세스의 수를 뜻한다.

높을 수록 좋다.

 

Turnaround time (반환 시간)

프로세스가 ready, running, waiting에 있던 시간을 모두 더한 값이다.

낮을 수록 좋다.

 

Waiting Time (대기 시간)

프로세스가 Ready Queue에서 대기한 시간을 의미한다.

CPU Scheduling Algorithm은 이 수치에 영향을 준다.

낮을 수록 좋다.

 

Response Time (응답 시간)

Ready Queue에 추가된 이후 프로세스가 최초 실행되기까지 걸린 시간을 의미한다.

낮을 수록 좋다.

 

CPU burst time

CPU의 사용 시간을 의미한다.

CPU 사용 시간이 긴 작업을 CPU bound job이라고 하며, 사용 시간이 짧은 작업은 I/O bound job이라고 한다.

I/O bound job은 CPU를 조금만 사용한 후 I/O 작업을 하러가기 때문에 일반적으로 I/O bound job에게 CPU의 사용을 우선 할당하는 것이 성능에 유리하다. 

 

질문

CPU burst time이 짧은 작업을 왜 I/O bound job이라고 할까?

 

CPU Scheduling Algorithms

1. FCFS (First Come First Served) Scheduling

먼저 들어온 작업부터 먼저 실행하는 스케쥴링 방법이다.

non-preemptive scheduling 이다.

 

장점

구현이 간단하다.

 

단점

CPU bound job에 의해 I/O bound job의 waiting time이 길어지는 Convoy Effect 현상이 발생할 수 있다.

 

 

 

2. SJF (Shortest Job First) Scheduling

CPU burst time이 가장 짧은 작업을 먼저 실행하는 스케쥴링 방법이다.

non-preemptive SJF : CPU burst time이 더 짧은 작업이 중간에 들어온다 하더라도 CPU를 넘기지 않는다. 

preemptive SJF (SRTF) : CPU burst time이 더 짧은 작업이 중간에 들어오면 해당 작업에게 즉시 CPU를 넘긴다.

 

CPU burst time을 어떻게 알 수 있을까?

프로세스가 얼마나 CPU를 사용할지는 실행하기 전까진 모르기 때문에, 과거의 데이터를 이용하여 예측할 수 밖에 없다.

exponential moving average 기법을 이용하여 예측할 수 있다.

 

여기서 알파는 가중치이며 [0, 1]의 범위를 가진다.

타우는 예측된 CPU 실행시간을 의미하며, t는 현재의 CPU 실행 시간을 의미한다.

 

장점

이상적으로 평균 Waiting time을 최소화 할 수 있는 스케쥴링 방식이다.

 

단점

예측에 의존하는 방식으로 효율성을 보장할 수 없다. 

실행 시간이 긴 작업을 영원히 실행되지 못하는 Starvation 현상이 일어날 수 있다.

 

 

 

3. RR (Round Robin) Scheduling

일정 시간을 두고 프로세스를 전환하는 방법이다.

이 방법을 구현하기 위해선 Timer라는 하드웨어가 필요하다.

preemptive 방식의 스케쥴링이다.

 

장점

평균 응답시간을 최소화 할 수 있는 스케쥴링 방법이다.

I/O bound job에 대한 평균 waiting time이 낮아진다.

starvation 현상이 발생하지 않는다.

 

단점

context-switch overhead가 많이 발생한다.

time quantum(CPU 사용 시간)의 길이에 따라 성능이 크게 좌우된다.

 

 

 

4. Priority Scheduling

우선순위가 높은 작업부터 먼저 실행하는 스케쥴링 방법이다.

starvation 현상이 발생할 수 있으나 Aging 기법을 사용하여 문제를 해결할 수 있다.

 

Aging

CPU에서 작업이 실행됨에 따라 우선순위를 떨어뜨리는 방법