CPU 스케쥴링

cpu를 더 효율적으로 사용하기 위해 여러 cpu 스케쥴링 알고리즘이 고안되었다. 

스케쥴링 대상은 커널 쓰레드이다.

 

싸이클

프로세스의 실행은 CPU burst, I/O burst가 교차하여 일어난다. CPU burst의 지속 시간에 따른 빈도수 분포는 다음과 같다.

[cpu burst의 시간에 따른 빈도수]

선점적/비선점적 스케쥴링

- 비선점적 스케쥴링은 cpu를 사용 중인 프로세스가 있을 때 그 프로세스가 waiting 또는 종료 상태로 들어갈 때만 발생한다.

- 선점적 스케쥴링은 cpu를 사용 중인 프로세스로부터 스케쥴링 기준에 따라 강제로 cpu를 ready state에 있는 프로세스로 넘겨 줄 수 있다.

 

스케쥴링 기준

1. cpu이용률: 0~100%의 값을 가진다.

2. throughput: 특정 시간 동안 완료되는 프로세스의 개수

3. waiting time: ready queue에서 기다리는 시간

4. response time: 요청에 대해 프로세스가 처음 반응하는 시간

5. turnaround time: 프로세스가 시작되서 완료될 때 까지의 시간

 

많은 스케쥴링 알고리즘이 평균 소요 시간을 줄이려고 하지만, 반응형 시스템에서는 반응 시간의 분산을 줄이는 것이 더 중요하다.

 

FCFS 스케쥴링

- ready 큐에 먼저 도착한 순서대로 실행한다. 

- 비선점적이다.

- 도착하는 순서에 따라 cpu활용률에 많은 차이가 있다.

- CPU bound 프로세스가 I/O bound 프로세스보다 먼저 실행되는 경우 cpu활용률에 큰 저하가 생긴다.

SJF 스케쥴링

- 다음 cpu burst시간이 가장 짧은 프로세스를 먼저 실행한다.

- 최소 waiting time을 보장하는 최적의 알고리즘이다.

- 다음 cpu burst를 알 수 없지만 cpu burst의 지수 평균을 통해 예측하여 사용할 수 있다.

- 선점적일 때는 현재 실행 중인 프로세스의 남은 cpu burst와 레디 상태의 cpu burst를 비교한다.

RR 스케쥴링

- 한 프로세스가 cpu를 사용하는 시간이 time quantum을 넘지 않도록 스케쥴링한다.

- 이 시간을 넘기면 다른 프로세스를 실행하므로 선점적이다.

- time quantum이 너무 작으면 FCFS에 가까워지고, 매우 크면 SJF에 가까워진다.

- time quantum이 cpu burst보다 커지면 turnaround time이 감소한다. 

- 너무 작으면 context switch로 인한 오버헤드가 커진다.

- 일반적으로 time quantum은 80%의 cpu burst보다 크면 좋다.

우선순위 스케쥴링

- 우선순위가 높은 프로세스를 먼저 실행한다.

- 낮은 우선순위의 프로세스가 영원히 실행되지 않는 starvation이 발생할 수 있다.

- starvation을 해결하기 위해 대기 시간에 따라 우선순위를 높이는 aging, 같은 우선순위에 RR 스케쥴링을 적용하는 방법이 있다. 

멀티레벨 피드백 큐 스케쥴링

- 멀티 레벨 큐에서 프로세스의 큐 간 이동이 가능하다.

- RR과 조합하여 time quantum내에 끝나지 않은 프로세스를 낮은 우선순위 큐로 강등시킬 수 있다.

다중 프로세서 스케쥴링

- 시스템 관련 작업을 하나의 코어에서 실행하고, 나머지 코어는 유저의 프로세스를 실행하도록 하는 것을 비대칭 멀티 프로세싱이라고 한다.

- 대칭 프로세싱(SMP)은 cpu코어 별로 각자 스케쥴링을 하는 것을 말한다.

- 공용 레디 큐를 관리하거나, 코어 별 레디 큐를 관리할 수 있다. 공용 레디 큐를 관리할 때는 lock을 사용해야 해서 bottleneck이 발생할 수 있다.

 

멀티 레벨 큐

준비 큐 하나에 모든 프로세스를 다 넣으면 자료 구조에 따라 우선 순위가 가장 높은 프로세스를 찾는데 \( O(N) \)의 시간이 소요될 수 있다. 여러 ready queue를 관리하는 것이 멀티 레벨 큐이다. 우선 순위가 같은 프로세스를 같은 큐에 넣는다.

각 큐 별로 다른 스케쥴링 알고리즘이 적용될 수 있고, 큐 레벨의 스케쥴링이 필요하다.

 

디스패치 레이턴시

- 컨텍스트 스위치에 소요되는 시간을 말한다.