CPU 스케쥴링

스케쥴링 개요

스케쥴링이 필요한 이유?

• 제한된 컴퓨팅 자원 위에서의 멀티 프로세싱을 해야 하기 때문
• 단일 CPU코어에서는 한 시점에 오직 하나의 프로세스만 처리 가능

CPU 스케쥴링

• 레디큐에 있는 프로세스 중 하나를 선택하여 CPU 자원 할당

스케쥴링 수행 시점

• 프로세스가 running 상태에서 waiting상태로 변경될 때
• 프로세스가 running 상태에서 ready상태로 변경될 때
• 프로세스가 waiting 상태에서 ready상태로 변경될 때
• 새로운 프로세스가 ready 상태가 될 때
• running상태의 프로세스가 종료될 때

비선점 스케쥴링(Nonpreemptive scheduling)

• Running 상태의 프로세스가 waiting상태로 바뀌면 트리거링
• Running 상태의 프로세스가 종료되면 트리거링
• 비탄력적(non-flexible)

선점 스케쥴링(Preemptive scheduling)

• Running상태의 프로세스가 waiting상태로 바뀌면 트리거링
• Running상태의 프로세스가 ready상태로 바뀌면 트리거링
• Waiting상태의 프로세스가 ready상태로 바뀌면 트리거링
• Running상태의 프로세스가 종료되면 트리거링
• 현대의 대부분의 운영체제(Windows,MacOS,Linux,Unix)에서 채택
• 복잡한 설계가 요구됨

디스패쳐(Dispatcher)

• 레디큐에서 스케쥴러에 의해 선택된 프로세스에게 CPU코어를 할당하는 모듈

디스패칭 절차

• 프로세스간 문맥 교환(context switching) 수행
• 커널모드에서 사용자모드로 변환
• 중단된 task를 재개하기 위해 사용자 프로그램의 적절한 위치로 점핑

디스패칭 지연(latency)

• 디스패처가 프로세스 하나를 중단시키고 새로운 프로세스를 실행시킬 때까지의 시간

스케쥴링 성능 지표

CPU 이용률(Utilization)

• CPU가 얼마나 바쁜지에 대해 나타내는 척도
• 높을수록 좋음(ideal = 100%)

처리량 (Throughput)

• 단위시간당 완료하는 프로세스 개수
• 높을수록 좋음

전환시간(Turnaround time)

• 프로세스의 레디큐 입장부터 종료까지 걸린 총 시간

대기시간(Waiting time)

• 프로세스가 레디큐에서 머무른 시간
• 전환시간에서 프로세스가 CPU에서 자원을 할당받아 일을 한 시간을 빼면 남는 시간

응답시간(Response time)

• 프로세스 실행 요청 시점 이후에 첫 번째 응답까지 걸린 시간
• 인터럽트 애플리케이션과 관련이 있다.
• 렉 없이 즉각적으로 반응할수록 성능이 좋음 → 짧을수록 좋음

스케쥴링의 목적

• CPU이용률 최대화
• 처리량 최대화
• 전환시간 최소화
• 대기시간 최소화
• 응답시간 최소화

First Come First Served(FCFS) 스케쥴링

스케쥴링 방법

• CPU자원 할당 요청을 한 순서대로 프로세스에게 CPU코어 할당

스케쥴링 구현

• First Input, First Output(FIFO) 큐를 기반으로 FCFS정책 진행
• FIFO기반 레디큐에 프로세스가 삽입되면 PCB는 레디큐의 tail과 연결
• CPU코어는 FIFO기반 레디큐의 head와 연결된 프로세스에게 할당
• 프로세스는 running상태가 되고 PCB는 큐에서 제거

스케쥴링 특성

• 비선점 스케쥴링 방식으로 동작
• 코드 구현이 쉽고 간단

시나리오

단점

• 각 프로세스가 요구하는 CPU burst time이 다른 경우 비효율적
• Convoy effect 발생

시나리오

Shortest Job First(SJF) 스케쥴링

스케쥴링 방법

• CPU burst time이 짧은 순서대로 프로세스에게 CPU코어 할당

스케쥴링 특성

• 각 프로세스의 다음 CPU burst time 길이를 고려하여 CPU스케쥴링 수행
• 주어진 프로세스 집합에 대해서 최소 average turnaround time 및 average waiting time 보장
• 비선점 스케쥴링 방식으로 동작

시나리오

단점

• 프로세스가 서로 다른 시간에 도착할 수 있음

시나리오

Shortest Remaining Time First(SRTF) 스케쥴링

스케쥴링 방식

• 프로세스가 새롭게 레디큐에 입력될 때마다 남은 처리시간이 가장 짧은 순서대로 프로세스에게 CPU코어 할당

스케쥴링 특성

• 프로세스 도착 시간을 고려하여 스케쥴링 수행
• 프로세스의 레디큐 입력시간이 다양한 경우에도 좋은 시스템 성능 도출
• 선점 스케쥴링 방식으로 동작

시나리오

CPU Burst Time 예측

Approximated SJF/SRTF 스케쥴링

• 각 프로세스의 정확한 다음 CPU burst time을 미리 알 수는 없음
• 그러나 예측은 가능
• 예측된 CPU burst time을 기반으로 (근사) 스케쥴링 수행

지수 평균(Exponential averaging) 기반 예측 기법

• 이전 CPU burst time을 토대로 다음 CPU burst time을 추정

Round Robin(RR) 스케쥴링

스케쥴링 방법

• 미리 정의된 CPU 시간만큼 각 프로세스가 CPU코어를 할당받음
• 미리 정의된 CPU 시간을 time quantum 또는 time slice라고 부름

스케쥴링 특성

• Response time(응답시간)을 고려한 스케쥴링
• 스케쥴러는 레디큐를 돌면서 각 프로세스에게 1 time quantum동안 CPU코어를 할당
• 매 time quantum이 지날 때마다 타이머를 통한 인터럽트 발생, 다음 프로세스를 위한 스케쥴링 수행
• Time quantum은 일반적으로 10-100밀리 초정도로 정의됨
• 레디큐는 순환큐(circular queue)로서 동작

Time quantum

• Time quantum의 길이에 따라 시스템 성능이 달라짐
• Time quantum의 길이가 짧을수록 응답시간(response time)이 짧아짐
• Time quantum의 길이가 길수록 문맥교환(context switching) 오버헤드가 감소
• Time quantum이 매우 길어지면 RR스케쥴링은 FCFS스케쥴링과 동일해짐
• Time quantum이 매우 짧아지면 문맥교환이 너무 자주 발생하여 시스템 성능 저하 발생

Priority 스케쥴링

스케쥴링 방법

• 각 프로세스에게 우선순위(priority)가 할당됨
• 우선순위가 높은 순서대로 프로세스에게 CPU코어 할당

스케쥴링 특성

• SJF스케쥴링은 priority 스케쥴링의 특별 범주에 속함
  • CPU burst time이 길수록 priority는 낮아짐
  • 다음 CPU burst time의 역수(reciprocal)가 priority로 정의됨
• 모든 프로세스의 priority가 동일한 경우 FCFS스케쥴링과 동치

단점 : 기아(Starvation)

• 바닐라 Priority 스케쥴링에서 발생
• 끝이 없는 블록(indefinite blocking)이 발생할 수 있음
• 낮은 우선순위를 가지는 프로세스는 결코 CPU코어를 할당받을 수 없음

해결책 : 노화(Aging)

• 끝이 없는 블록 문제 해결
• 프로세스의 대기시간이 길어질수록 우선순위를 점차적으로 높여감