CPU 스케줄링 알고리즘

스케줄링 알고리즘의 종류

비선점형 스케줄링

한 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 자원을 반환할 때까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식을 의미한다. 즉, 하나의 프로세스가 CPU 자원을 독점할 수 있다.

모든 프로세스에 대한 요구를 공정하게 처리할 수 있지만, 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기해야하는 콘베이 현상이 발생할 수 있다.

처리 시간의 편차가 적은 특정 프로세스 환경에서 용이하다.

선입 선처리 스케줄링(FCFS 스케줄링)

FCFS 스케줄링은 First Come First Served Scheduling의 약자로 먼저 온 곳이 먼저 제공받는다는 의미이다.

단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다.

 

FCFS는 CPU를 오래 사용하는 프로세스가 먼저 도착하면 뒤에 있는 다른 프로세스들은 하염없이 기다릴 수 밖에 없다.

이런 현상을 호위 효과라고 한다.

 

FCFS 스케줄링

 

이런 호위 효과를 막기 위해 등장한 것이 최단 작업 우선 스케줄링이다.

최단 작업 우선 스케줄링(SJF 스케줄링)

SJF스케줄링은 Shortest Job First Scheduling의 약자로 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식이다.

SJF 스케줄링

 

SJF 스케줄링은 비선점형 스케줄링 알고리즘으로 분류되지만 선점형으로도 구현될 수 있다.

선점형 최단 작업 우선 스케줄링은 최소 잔여 시간 우선 스케줄링이다.

우선순위 스케줄링

프로세스들에게 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다.

위에서 살펴본 SJF 스케줄링도 우선순위 스케줄링의 일종으로 볼 수 있다. 왜냐하면 실행 시간이 가장 적은 프로세스부터 우선순위를 부여하는 방식이기 때문이다.

 

우선순위 스케줄링은 기아 현상이 발생할 수 있다.

기아 현상이란 우선순위가 높은 프로세스만 계속 먼저 실행되서 우선순위가 낮은 프로세스의 실행은 계속 뒤로 밀리는 것이다.

이를 방지하기 위한 기법으로 에이징 기법이 있다. 에이징 기법이란 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

---

선점형 스케줄링

하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식이다. 즉, 어느 하나의 프로세스가 자원 사용을 독점할 수 없다.

선점형 스케줄링은 더 급한 프로세스가 언제든지 끼어들어 사용할 수 있는 스케줄링 방식이므로 프로세스들에 골고루 자원을 배분할 수 있다는 장점이 있지만 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

실시간 응답환경, Deadline 응답환경 등 우선순위가 높은 프로세스를 빨리 처리해야할 경우에 유용하다.

라운드 로빈 스케줄링

FCFS 스케줄링에 타임 슬라이스라는 개념을 더한 스케줄링 방식이다.

타임 슬라이스는 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다.

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

 

round robin scheduling

 

준비 큐에 삽입된 프로세스들은 삽입된 순서대로 CPU를 이용하되 정해진 타임 슬라이스만큼 CPU를 이용한다.

정해진 시간을 모두 사용했음에도 아직 프로세스를 완료하지 못했다면 다시 큐의 맨 뒤에 삽입된다. 이때 문맥교환이 발생한다.

균등한 CPU 점유 시간을 보장하며 시분할 시스템을 사용한다. 시분할 시스템은 CPU 스케줄링과 다중 프로그래밍을 이용해서 각 사용자들에게 컴퓨터 자원을 시간적으로 분할하여 사용할 수 있게 해주는 시스템이다.

 

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

SRT 스케줄링은 Shortest Remaining Time의 약자로 최단 잔여시간을 우선으로 하는 스케줄링이다.

진행중인 프로세스가 있어도 작업 시간이 짧은 프로세스에게 CPU 자원을 할당한다.

 

간단하게 문제를 통해 알고리즘의 원리를 배워보자.

프로세스	도착시간	실행시간
P1	0	8
P2	2	4
P3	4	1
P4	6	4

 

프로세스 간 문맥 교환에 따른 오버헤드는 무시한다고 할 때 SRT 스케줄링 알고리즘을 사용한 경우 평균 반환 시간은 어떻게 될까?

 

먼저 평균 반환 시간은 모든 프로세스가 작업을 완료한 평균값이기 때문에 다음과 같은 수식으로 구할 수 있다.

 

( 모든 프로세스 실행시간 + 모든 프로세스 대기시간 ) / 모든 프로세스 갯수 = 평균 반환 시간

 

 

먼저 P1의 도착시간이 0이기 때문에 준비 큐에는 P1이 들어오게 되고 P1이 실행된다.

그 다음 도착하는 프로세스는 P2인데 도착시간이 2이다. 따라서 P1은 2초동안 실행되고 남은 실행시간은 6초가 된다.

 

 

시간이 2초가 되었을 때 준비큐에 있는 프로세스는 P1과 P2이다. 이제 두 개 중에 하나의 프로세스에게 CPU를 할당해야한다.

SRT 스케줄링은 작업시간이 짧은 것부터 수행하기 때문에 P2를 수행해야한다.

왜냐하면 2초시점에서 P1은 실행시간이 6초 남았고, P2는 4초 남았기 때문이다.

그리고 다음번에 들어오는 프로세스는 P3이고 4초에 들어오기 때문에 P2를 2초에서 4초동안 수행하고 남은 실행시간은 2초가 된다.

 

 

4초에서 준비큐에 있는 프로세스는 P1, P2, P3이다. 이 세 개의 프로세스 중 실행시간이 가장 짧은 P3를 수행한다.

P3의 실행시간은 1초이므로 4초에서 5초까지 수행되고 실행시간은 0으로 종료된다.

 

 

5초 시점에서 준비 큐에 있는 프로세스는 P1과 P2이다. P4는 6초에 도착하므로 아직 준비큐에 없는 상태이다.

그렇기 때문에 5초에서 실행되는 프로세스는 실행시간이 적은 P2가 실행된다.

그런데 6초가 되면 P4가 들어오지 않는가. P4가 6초에 들어와도 6초 시점에서 가장 실행시간이 짧은 프로세스는 P2이다.

따라서 P2가 2초동안 실행되고 종료된다.

 

 

이제 7초 시점에서 준비큐에 존재하는 프로세스는 P1과 P4이다. P4의 실행시간이 적으므로 P4가 4초동안 수행된다.

그리고 P1의 나머지 실행시간이 수행되고 모든 프로세스가 종료된다.

 

그렇다면 대기시간을 어떻게 구할 수 있을까?

대기시간은 각 프로세스가 종료된 시점 이전의 수행시간 중에 자신을 제외한 모든 수행시간을 더하고 도착시간을 빼주면 된다.

이 말 그대로 숫자를 대입해보자.

 

P1의 대기시간 = ( 2 + 1 + 2 + 4 ) - 0 = 9

P2의 대기시간 = ( 2 + 1 ) - 2 = 1

p3의 대기시간 = ( 2 + 2 ) - 4 = 0

p4의 대기시간 = ( 2 + 1 + 2 + 2 ) - 6 = 1

 

따라서 평균 반환 시간은 ( 17 + 11 ) / 4 = 7 이다.

 

다단계 큐 스케줄링

다단계 큐 스케줄링은 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.

 

이렇게 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다.

예를 들어 어떤 큐에는 우선순위가 비교적 높아야하는 입출력 집중 프로세스가 삽입될 수 있고, 어떤 큐에는 우선순위가 비교적 낮아도 괜찮은 CPU 집중 프로세스가 삽입될 수 있다.

또한 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.

즉, 큐별로 스케줄링을 다르게 적용해서 프로세스 유형별 처리가 쉬워진다.

다단계 피드백 큐 스케줄링

다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없다. 그렇기 때문에 우선순위가 낮은 큐에 저장된 프로세스들은 계속 연기될 여지가 있다. 기아 현상이 발생할 수 있다는 말이다. 이를 보완하기 위해 등장한 스케줄링 기법이 다단계 피드백 큐 스케줄링이다.

그렇다면 다단계 피드백 큐 스케줄링이 다단계 큐 스케줄링과 다른 점은 무엇이겠는가?

그렇다. 프로세스들이 큐 사이를 이동할 수 있다는 점이다.

multilevel feedback queue scheduling

 

만약 새로 준비 상태가 된 프로세스가 있다면 우선 순위가 가장 높은 큐에 삽입되고 일정 시간동안 실행된다.

일정 시간동안 실행했음에도 완료하지 못했다면 다음 우선 순위 큐에 삽입되어 실행된다.

그리고 또 완료하지 못했다면 그 다음 우선 순위 큐에 삽입된다.

결과적으로 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아지게 된다.

반대로 CPU를 적게 사용하는 입출력 집중 프로세스 같은 경우에는 우선순위가 높은 큐에서 실행이 끝난다.

 

정리하자면 다단계 피드백 큐 스케줄링 알고리즘은 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동(에이징)시킬 수 있는 알고리즘이다.

 

가장 일반적인 CPU 스케줄링 알고리즘이지만 구현이 복잡하다.