[Chapter 5. CPU 스케줄링] CPU 스케줄링과 성능 평가의 기준

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

CPU 스케줄링 (CPU Scheduling)

---

다중 프로그래밍은 CPU가 실행 중인 프로그램을 항상 가지게 하여 CPU 이용률 최대화하기 위한 것이다.

 

이를 위해서는 현재 실행 상태에 있던 프로세스가 다른 상태로 천이하게 된다면 즉, CPU가 유휴 상태가 될 때마다

운영체제는 그 프로세스로부터 CPU를 회수하고, 실행 상태로 천이시킬 프로세스를 선정하여 할당하여야 한다.

 

 

실행할 프로세스를 선택하는 절차는 CPU 스케줄러에 의해 수행되며, 준비 큐(ready queue)에 들어있는 프로세스들 중 하나를 선택하게 된다.

(스케줄링의 대상 : 준비 큐에 들어있는 프로세스들에 한함)

 

준비 큐에 대기하고 있는 프로세스들은 스케줄링에 의하여 선택만 된다면 언제든지 실행이 될 수 있는 상태이며,

실질적으로 준비 큐에 저장되어 있는 레코드들은 일반적으로 프로세스들의 PCB(Process Control Block)들이다.

 

 

CPU 스케줄링이 일어나는 경우

CPU 스케줄링은 다음의 네 가지 상황 하에서 발생할 수 있다.

 

1. 실행 상태의 프로세스가 대기 상태로 전환되었을 경우

     (1) 입출력 요청

     (2) 사건 대기 (wait() 시스템 호출 → 자식 프로세스가 종료되기를 기다려야 함)

 

2. 실행 상태의 프로세스가 준비 상태로 전환되었을 경우

     (1) 인터럽트의 발생

     (2) 시분할 시스템에서 타임 슬라이스의 소진

 

3. 대기 상태의 프로세스가 준비 상태로 전환되었을 경우

     (1) 입출력의 종료

     (2) 사건의 접수 완료

 

4. 실행 상태의 프로세스가 종료되었을 경우

 

* 참고 : 2022.07.08 - [Computer Science/Operating System] - [Chapter 3. 프로세스] 프로세스의 상태

 

디스패처 (Dispatcher)

디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다.

 

이는 다음의 역할들을 수행한다.

1. 문맥 교환

2. 사용자 모드로 전환

3. 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)

 

문맥 교환이 일어날 때 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지는 시간이 소요되는데,

이 시간을 디스패치 지연(dispatch latency) 시간이라고 부른다.

 

CPU-입출력 버스트 사이클 (CPU-I/O Burst Cycle)

프로세스의 실행은 CPU 실행과 입출력 대기의 사이클로 구성된다.

(CPU burst로 시작 → I/O burst → CPU burst → I/O burst → … → CPU burst → 실행 종료하기 위한 시스템 호출)

 

 

CPU burst time이란 CPU 할당 후 입출력을 요구할 때까지의 시간을 말하는 것이다.

 

CPU burst time을 측정해보았을 때 평균적으로 아래의 표와 같이 초지수형(hyperexponential) 분포를 보인다고 한다.

즉, 보통 짧은 CPU burst를 많이 가지고, 긴 CPU burst는 적게 갖는다는 것이다.

 

 

스케줄링 시 프로세스의 성격을 파악하는 것은 매우 중요하다.

 

입출력 중심 프로세스(I/O Bound Process)일 경우 그래프는 왼쪽으로 치우쳐져 그려질 것이며,

전형적으로 짧은 CPU burst를 많이 가질 것이다.

 

반대로, CPU 중심 프로세스(CPU Bound Process)일 경우 그래프는 오른쪽으로 치우쳐져 그려질 것이며,

다수의 긴 CPU burst를 가질 수 있다.

 

이런 분포는 적절한 CPU 스케줄링 알고리즘을 선택하는 데 유용하게 활용될 수 있다.

 

성능 평가의 기준

CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 존재한다.

 

기준	내용
CPU 사용률 (utilization)	CPU 활용 정도를 나타내는 비율 개념상 0~100%를 가질 수 있는데, 실제 시스템에서는 40~90%까지의 범위를 가져야 한다.
처리율 (throughput)	단위 시간당 완료된 프로세스의 개수
반환(총처리) 시간 (turnaround time)	프로세스가 생성되어 작업을 마치고 종료될 때까지 걸린 시간 메모리에 들어가기 위해 소비한 시간 + 준비 완료 큐에서 대기한 시간 + CPU에서 실행하는 시간 + 입출력 시간(→ 출력 장치의 속도에 의해 제한된다.)
대기 시간 (waiting time)	준비 큐에서 대기하면서 보낸 시간의 합
반응(응답) 시간 (response time)	대화형 시스템에서 임의 요구(ex. 키보드 입력)에 대하여 응답이 시작되는 데까지 걸린 시간

 

스케줄링 알고리즘을 비교하는 데에 사용되는 특성에 따라 최선의 알고리즘을 결정하는 것에 큰 차이가 발생한다.

 

만약 효율성을 추구할 경우

CPU 사용률과 처리율은 최대화,

반환 시간, 대기 시간, 반응 시간은 최소화하는 것이 바람직하다.

 

만약 공평성을 추구할 경우

각 기준에 있어서 최적의 평균값과 이들 간의 편차의 최소화를 함께 고려하여 스케줄러를 선정하여야 한다.

 

대화형 시스템의 경우

반응 시간의 편차가 적은 스케줄러를 선정하는 것이 좋다.

 

즉, 시스템의 용도에 따라 선정 기준이 달라질 수 있고, 기준 간에 trade-off가 있을 수 있다.