스케쥴링 알고리즘

디스크에서 메모리로 로드된 프로그램을 프로세스라고 한다. 즉, 프로세스는 실행중인 프로그램이다. 이 프로세스는 cpu를 할당 받아서 실행되는데 총 3가지 상태가 있다.

Ready -> Run -> Block 의 3가지 상태가 있다. 여기서 Run 상태란 프로세스가 CPU를 할당받아 실제로 실행되는 상태이다.

스케쥴링이라는 것은 Ready큐에서 실행을 대기 하는 여러개의 프로세스들의 실행 순서를 결정하는 일이다.

레디 큐에 10개의 프로세스들이 있는데, 이 프로세스들중에 중요한것과 그렇지 않은것들이 섞여있을것이다. 중요도를 기준으로 무엇을 먼저 실행시킬까 하는것이 스케쥴링 알고리즘의 핵심이다.

스케쥴링 알고리즘은 두가지 방식이 있다.

1. 선점형 스케쥴링 - cpu를 할당받은 프로세스가 아직 실행을 끝마치지 못했음에도 할당받은 타임 슬라이스가 끝나서 CPU스케쥴러에 의해 교체 되는 방식이다.

2. 비선점형 스케쥴링 - CPU를 할당받은 프로세스가 자신의 일을 다 끝낼때 까지 계속 실행되는 방식이다.

비선점형은 프로세스가 한번 실행되면 끝날때까지 다른일을 하지 못하므로 응답률이 매우 떨어진다. 따라서 요즘은 거의 선점형 스케쥴링 방식을 사용한다.

비선점형 스케쥴링 알고리즘 - FCFS, SJF, HRN 

선점형 스케쥴링 알고리즘 - 라운드로빈, SRT, 다단계 피드백 큐 스케쥴링

대표적으로 위와 같은 알고리즘이 존재한다.

FCFS - First Come First Served

처음 오는것을 먼저 처리한다. 이런뜻이다. 메인 프레임에 잡을 하나하나 넣으면서 실행이 끝마칠때 까지 다른 잡을 실행시키지 않는 방식과 똑같은것이다. 큐와 비슷하다고 생각하면 된다. 이미 실행중인 잡은 실행을 끝마칠때까지 교체 되지 않는다.

이 방식은, 요즘같이 응답성이 중요한 시대에서는 거의 사용되지 않는 방식이다. 일괄처리시에만 사용된다.

시간이 오래걸리는 작업이 실행되면 뒤에 있는 작업들이 실행되지 못하므로 처리율이 떨어진다.

SJF - Short Job First

말그대로 시간이 적게 걸리는 작업부터 먼저 처리하겠다는 것이다. 마찬가지로 비선점형이기 때문에 한번 실행되는 프로세스는 끝날때까지 계속 실행된다. 이 방식의 단점은 프로세스의 실행시간을 정확히 예측하기 힘들다는것이다. 예를 들어, 워드로 작업하고 있는데 스케쥴러 입장에서 이 워드라는 프로세스가 언제 끝날지 어떻게 알것인가? 사용자가 2시간 작업할수도 있고 10분 작업할수도 있다. 그렇기 때문에 이 방식도 요즘에 잘 사용되지 않는 방식이다. 짧은 실행시간을 가진 프로세스만 계속 실행될 수 있기 때문에 실행시간이 긴 프로세스는 실행 되지 못하는 기아 현상이 발생 할 수 있다.

HRN - High Response Rate Next

높은 응답률을 가진 프로세스를 먼저 실행시키겠다는 것이다. 응답률 = 응답시간/실행시간 공식이 성립한다.

응답시간 = 레디큐에서 대기한 시간 + 프로세스가 CPU를 할당받아 실제로 실행된 시간

실행시간 = 프로세스가 CPU를 할당받아 실제로 실행된 시간

즉, 이 방식에서 프로세스는 실행시간이 짧을 수록 레디큐에서 대기한 시간이 높을 수록 높은 우선순위를 갖는다.

아까 SJF방식은 실행시간이 긴 프로세스가 낮은 우선순위를 갖기에 기아 현상이 발생할수 있다고 했는데 이방식은 그 문제점을 해결한 방식이다. 실행시간이 길면 대기시간이 점점 늘어날것이고 그럼 대기한 시간이 늘어날 수록 우선순위가 높아져서 언젠가는 실행된다. 하지만 이 방식도 여전히 실행시간을 정확히 예측하기 힘들기 때문에 잘 사용되지 않는다. 또한, 프로세스마다 실행 시간이 공평하지 않기 때문에 잘 사용되지 않는다.

여기서 부터는 선점형 스케쥴링 알고리즘이다.

라운드 로빈

레디 큐에 있는 프로세스들을 순서대로 실행시키되, 하나의 프로세스가 실행될수 있는 시간을 공평하게 나눈다. 그것을 타임 슬라이스라 또는 퀀텀이라고 한다. 10밀리초의 퀀텀을 가지면 모든 프로세스가 10밀리초씩 돌아가면서 공평하게 실행된다. 실행이 끝난 프로세스는 레디큐의 맨 마지막으로 들어간다. 10밀리초가 지나면 스케쥴러가 강제로 프로세스를 레디상태로 만들기 때문에 선점형 알고리즘이다.

퀀텀을 작게 잡는 경우 - 문맥 교환이 자주 일어나기 때문에 오버헤드가 커진다. 하지만 응답률이 늘기 떄문에 사용자 입장에서 여러개의 프로그램이 동시에 실행되는것처럼 느껴진다.

퀀텀을 크게 잡는 경우 - 문맥 교환에 의한 오버헤드는 줄어들지만 응답률이 떨어진다. 퀀텀이 클 수록 프로그램이 동시에 실행되는 느

낌이 사라질것이다.

그래서 퀀텀은 적당한 크기로 잡아야 한다.

SRT - Shortest Remaining Time

프로세스의 남은 실행시간이 가장 짧은것 부터 실행시키는 알고리즘이다.

기본적으로 라운드로빈처럼 실행되지만 레디큐에 있는 프로세스중에 실행될 프로세스를 선정할때 실행 시간이 가장 적게 남은것부터 실행시키게 된다. 그렇기 때문에 선점형 방식이다. 이것도 마찬가지로 퀀텀이 존재한다.

이것도 마찬가지로 실행시간이 정확히 얼마나 될것인지 예측하기 힘들고, 레디큐에 있는 모든 프로세스에 대해 남은 실행시간을 계산해야 하는 오버헤드가 존재하므로 좋은 알고리즘이 아니다.

다단계 피드백 큐

레디 큐가 하나가 아니라 여러개가 존재한다.

레디큐 1 - 우선순위 1

레디큐 2 - 우선순위 2

레디큐 3 - 우선순위 3

레디큐 4 - 우선순위 4

위에서부터 아래로 갈수록 우선순위가 낮아진다. 각 레디큐에 할당된 퀀텀은 아래로 내려갈수록 커진다. 바로 윗단계의 레디큐에 프로세스가 없어야 현재 단계의 레디큐가 실행 될 수 있다. 위에서부터 아래로 내려가면서 차례로 프로세스를 실행시키는것이다.

현재 레디큐1에 있는 프로세스를 실행한다고 해보자. 이 레디큐1에 있는 프로세스들은 실행이 끝나면 바로 밑인 레디큐2의 맨 뒤로 들어간다. 또한 레디큐2는 레디큐1보다 퀀텀이 더 길다.

이런 방식으로 우선순위가 낮은 레디큐4의 프로세스들도 나중엔 결국 실행 할 수 있는 권한이 생기는 것이다. 즉, 실행 할때마다 프로세스에 나이를 부여하는 에이징 기법이 적용되는것이다.

요즘 시대의 운영체제는 위와 같은 다단계 피드백 큐 스케쥴링 알고리즘을 사용한다. 이런식으로 스케쥴링이 구현되면 우선순위가 중요한 프로세스부터 실행시킬수 있으며 우선순위가 낮다고 하더라도 절대 실행되지 않는 기아 현상도 발생하지 않는다.

또한 각 레디큐에는 퀀텀이 있기 떄문에 각 프로세스들이 공평하게 실행된다.