[운영체제] CPU 스케줄링

CPU Burst

사용자 프로그램이 CPU를 직접 가지고 명령을 수행하는 것.

 

- 계산 위주 프로그램같이 CPU Burst가 IO Burst보다 길 경우 CPU Bound Process라고 한다.

 

- CPU Burst가 균일하지 않은 프로세스를 위해 스케줄링이 필요하다.

=> 보통 CPU Burst가 짧은 프로세스에게 우선적으로 CPU를 할당한다.

I/O Burst

I/O 요청이 발생해 커널에 의해 I/O 작업을 수행하는 것.

 

- 대화형 프로그램같이 IO Burst가 CPU Burst보다 길 경우 IO Bound Process라고 한다.

 

CPU 스케줄링 방식

- 비선점형 방식: CPU를 획득한 프로세스가 스스로 반납하기 전까지는 빼앗기지 않는 방식.

- 선점형 방식: 강제로 CPU를 빼앗는 방식.

 

- 디스패처가 CPU 이양작업을 수행한다.

=> 기존 프로세스의 Context를 PCB에 저장하고, 새로운 프로세스의 PCB를 읽어와 Context를 복원한다.

 

FCFS (first-come first-served)

- 선점형 방식으로, 먼저 온 프로세스부터 CPU를 쓸 수 있게 한다.

 

- 어떤 프로세스가 먼저 큐에 도착하는지에 따라 성능이 달라진다.

 

- 콘보이 현상이 발생할 수 있다.

: CPU Burst가 긴 프로세스 하나가 다른 짧은 프로세스보다 먼저 올 경우, 잠깐 쓰고 IO로 넘어갈 프로세스들이 기다리게 된다.

 

SJF (shortest-job first)

- CPU Burst가 가장 짧은 프로세스에게 먼저 CPU를 할당한다.

 

- 비선점형 방식

=> 현재 수행되고 있는 프로세스보다 Burst가 짧은 프로세스가 와도 제어권을 뺏기지 않는다.

 

- 선점형 방식(SRTF, shortest remaining time first)

=> 평균 대기시간을 최소화할 수 있다.

=> 기아 현상이 생길 수 있다.

: CPU Burst가 짧은 프로세스가 계속 도착할 경우 처음 프로세스는 CPU를 사용하지 못한다.

 

우선순위 스케줄링 

- 우선순위가 높은 프로세스에게 먼저 CPU를 할당한다.

 

- 비선점형 방식, 선점형 방식 모두 기아 현상이 발생할 수 있다.

=> 우선순위가 낮은 프로세스가 계속 들어올 경우.

 

- 에이징 기법으로 기다리는 시간이 늘어날수록 우선순위를 높게 해 기아 현상을 해결할 수 있다.

 

라운드 로빈 스케줄링 (Round Robin, RR scheduling)

- 시분할 스케줄링으로, Time Quantum을 지정해 일정 시간만큼만 프로세스에게 CPU를 할당한다.

=> Time Quantum이 너무 길면 FCFS와 똑같이 동작한다.

=> 대신 짧을수록 Context Switch로 인한 오버헤드가 증가한다.

 

- 선점형 스케줄링이다.

 

- 프로세스의 CPU 사용량에 비례해 대기시간이 늘어난다.

=> SJF보다 평균 대기 시간은 길지만 응답 시간은 짧다.

 

멀티레벨 큐 (Multi-level Queue)

- ready 큐를 여러개로 분할하여 관리한다.

 

- 전위 큐: 대화형 작업을 담는다. 라운드로빈을 사용한다.

 

- 후위 큐: 계산위주 작업을 답는다. FCFS를 사용한다.

 

- 큐 스케줄링 방식

=> 고정 우선순위 방식: 큐에 고정적인 우선순위를 할당한다.

=> 타임 슬라이스: 각 큐에 CPU 시간 비율을 할당한다.

 

멀티레벨 피드백 큐

- 프로세스가 큐를 이동할 수 있다.

=> 에이징 기법으로 큐의 우선순위를 승격시킬 수 있기 때문.

 

- 상위 큐에서는 RR를 사용하고, 하위 큐에서는 FCFS를 사용한다.

=> 상위 큐에서 작업을 완료하지 못하면 하위 큐로 내려가서 수행한다.

 

다중처리기 스케줄링

- CPU가 여러개인 시스템에서 사용한다.

 

- 부하균형 매커니즘을 사용한다고 한다.

=> 대칭형 다중처리(CPU 자율), 비대칭형 다중처리(한 CPU가 통제)로 나눌 수 있다.

 

실시간 스케줄링

- 작업마다 데드라인을 둔다.

 

- Hard real-time system: 데드라인을 정확하게 맞추어야 한다. ex.항공 시스템

- Soft real-time system: 100% 정확하지 않아도 된다. ex. VOD

 

- EDF(Ealist Deadline First) 스케줄링을 사용한다.

 

 

스케줄링 성능 지표

시스템 관점

- CPU 이용률

 

- CPU 처리량 : 일정 시간동안 ready 큐에 있던 프로세스 중에 몇개를 끝마쳤는지

 

사용자 관점

- 기다린 시간: 프로세스가 CPU를 요청한 시점부터 CPU Burst가 끝날 때까지 걸린 시간 (종료 시간x)

 

+ 대기 시간: CPU Burst 기간 중 ready 큐에 있던 시간

+ 응답 시간: ready 큐에서 첫번째 CPU를 얻기까지 기다린 시간.

 

 

 

 

 

(참고)

반효경. 운영체제와 정보기술의 원리 2020개정판. 이화여자대학교출판문화원