3-2] CPU 스케줄링: CPU 스케줄링 알고리즘

선입 선처리 스케줄링

FCFS, First Come First Served 스케줄링

단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링

먼저 CPU를 요청한 프로세스부터 CPU 할당

 

단점: 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용 (= 호위 효과)

 

최단 작업 우선 스케줄링

SJF, Shortest Job First 스케줄링

호위 효과를 방지하기 위해

CPU 사용 시간이 긴 프로세스는 나중에 실행하고

CPU 사용 시간이 짧은 프로세스는 먼저 실행

 

라운드 로빈 스케줄링

RP, Round Robin 스케줄링

선입 선처리 스케줄링 + 타임 슬라이스(time slice)

타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링

 

큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용하고

정해진 시간을 초과했음에도 아직 프로세스가 완료되지 않았다면 큐의 맨 뒤에 삽입 (문맥 교환)

타임 슬라이스의 크기가 매우 중요하게 작용

너무 커지면 선입 선처리 스케줄링과 같은 방식으로 작동됨

 

최소 잔여 시간 우선 스케줄링

SRT, Shortest Remaining Time 스케줄링

최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링

최단 작업 우선 스케줄링: 작업 시간이 짧은 프로세스부터 처리

라운드 로빈 스케줄링: 정해진 타임 슬라이스만큼 돌아가며 사용

따라서,

정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는

남은 작업 시간이 가장 적은 프로세스 선택

 

우선순위 스케줄링

프로세스들에 우선순위를 부여해 우선순위가 높은 프로세스부터 실행

우선순위가 같은 프로세스들은 선입 선처리로 스케줄링

최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 ⊂ 우선순위 스케줄링

 

우선순위 스케줄링의 큰 문제점은 기아(starvation) 현상

우선순위 높은 프로세스만 계속 실행되고

우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었더라도) 실행 연기

 

이를 방지하기 위한 기법이 에이징(aging)

오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법

따라서, 우선순위가 낮아도 언젠가는 우선순위가 높아짐

 

다단계 큐 스케줄링

Multievel queue 스케줄링

우선순위 스케줄링의 발전된 형태

우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

여러 개의 준비 큐는 각각 알고리즘을 다르게 설정이 가능

 

우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리

우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스 처리

 

하지만, 준비 큐 간의 이동이 불가능해서

우선순위 낮은 프로세스는 계속해서 실행 연기가 되며 기아 현상이 발생

이를 해결하기 위해 아래의 다단계 피드백 큐 스케줄링이 탄생

 

다단계 피드백 큐 스케줄링

Multilevel feedback queue 스케줄링

큐 간의 이동이 가능한 다단계 큐 스케줄링

 

처음 준비 큐에 들어올 때, 우선순위 0에서 시작하게 되고

CPU 처리를 하다 끊기면 우선순위를 한 칸씩 낮추는 방식으로

CPU를 많이 이용하는 프로세스일수록 우선순위가 자연스럽게 낮아지도록 설정

 

따라서,

어떤 프로세스의 CPU 시간이 길면 우선순위를 낮아지게 하고

어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 에이징을 통해 우선순위를 높이는 방식

가장 일반적인 CPU 스케줄링 방식이다