11 - CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘 종류

10 - CPU 스케줄링

이전 게시물을 통해 CPU 스케줄링에 대한

대략적인 개념과 흐름을 살펴보았다.

 

이번에는 대표적인 스케줄링 알고리즘과

아이디어에 대해 알아보겠다.

 

선입 선처리 스케줄링

선입 선처리 스케줄링은

(FCFS: First Come First Served)

준비 큐에 삽입된 프로세스들의 순서대로

처리하는 비선점 스케줄링 방식이다

 

가장 공정해 보이나,

프로세스들이 기다리는 시간이

매우 길어질 수 있다는 부작용이 있다.

 

CPU 이용 시간이 매우 짧은 프로세스가

준비 큐에 늦게 삽입되었다는 이유로

먼저 삽입된 프로세스들의

긴 처리 시간을 기다려야 하는

호위효과(Convoy effect)가 발생할 수 있다.

 

최단 작업 우선 스케줄링

최단 작업 우선 스케줄링은

(SJF: Shortest Job First)

호위 효과를 방지하기 위해

CPU 이용시간이 짧은 프로세스를

먼저 실행하는 방식이다.

 

기본적으로 비선점 스케줄링 방식으로 분류되지만

선점형 최단 작업 우선 스케줄링도 존재한다.

 

라운드 로빈 스케줄링

라운드 로빈(Round robin) 스케줄링은

선입 선처리 스케줄링에

타임 슬라이스라는 개념이 추가된 방식이다.

 

여기서 타임 슬라이스는 각 프로세스가

CPU를 사용할 수 있는 정해진 시간이다.

 

즉, 프로세스끼리 정해진 시간만큼만

CPU를 번갈아가며 사용하는

선점형 스케줄링 방식이다.

 

이때, 타임 슬라이스의 크기가 매우 중요하다.

 

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

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

(SRT: Shortest Remaining Time)

최단 작업 우선 스케줄링 알고리즘과

라운드 로빈 알고리즘을 합친 방식이다.

 

정해진 타임 슬라이스만큼 CPU를 사용하되,

그 다음에는 잔여 작업 시간이

가장 적은 프로세스를 처리하는

선점형 스케줄링 알고리즘이다.

 

우선순위 스케줄링

우선순위(Priority) 스케줄링은

프로세스들에 부여한 우선순위대로

실행하는 방식이다.

 

앞서 설명한 SJF, SRT 스케줄링 방식도

넓은 의미에서 보면 우선순위 스케줄링이다.

 

이 방식은 준비 큐에 먼저 삽입되었음에도

우선순위가 밀린다는 이유만으로 계속해서

실행이 늦춰지는 기아(Starvation)현상이

발생할 수 있지만,

오래 기다린 프로세스의 우선순위를 점차 높이는

에이징(Aging)방식으로 해결한다.

 

다단계 큐 스케줄링

다단계 큐(multilevel queue) 스케줄링은

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

우선순위 별로 준비 큐를

여러 개 사용하는 방식이다.

 

프로세스 유형별로 편리하게

우선순위를 구분하여 실행이 가능하며,

큐 별로 타임 슬라이스를 지정할 수도 있고

큐 별로 각각 다른 스케줄링 알고리즘을

사용할 수도 있다.

 

다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링은

(multievel feedback queue scheduling)

다단계 큐 스케줄링 내 각 큐에서

발생할 수 있는 기아현상을 해결하기 위해

프로세스가 각 큐 사이를

넘나들 수 있게 한 방식이다.

 

해당 큐 내에서 타임 슬라이스 안에

작업을 다 끝내지 못하면

우선순위가 점차 내려가게 된다.

 

그 결과 CPU 집중 프로세스들은 자연스레

우선순위가 낮아지고 입출력 집중 프로세스들은

자연스레 우선순위가 높은 큐에서 실행이 끝난다.

 

이 방식이 가장 구현이 복잡하지만

가장 일반적인 CPU 스케줄링 알고리즘이다.