[OS] CPU 스케줄링, 스케줄링 알고리즘(FCFS, SJF, RR, RMS, EDF)

CPU 스케줄링

운영체제는 컴퓨터 하드웨어를 관리하는 소프트웨어를 뜻한다. 운영체제의 목표는 자원을 여러 응용 프로그램이 효과적으로 나누어 사용할 수 있도록 하는 것이다.

단일 코어 CPU는 한 번에 하나의 프로세스만을 실행할 수 있다. CPU가 idle 상태이고 자원이 할당될 수 있는 상태라면 어떤 프로세스에게 할당하는 것이 가장 효율적일까? CPU 스케줄러는 CPU 자원이 할당되기를 준비하고 있는 상태, 즉 Ready 큐에 존재하는 프로세스 중에 하나를 선택하여 CPU 자원을 할당해준다. 이를 CPU 스케줄링이라고 한다. CPU 자원은 한정되어 있기 때문에 CPU 스케줄링은 가능한 빠르게 자주 일어나야 한다. 그래서 CPU 스케줄러를 단기 스케줄러(Short-term scheduler)라고도 한다.

 

• 프로세스 상태 구조

 

CPU 스케줄링 결정은 다음 네 가지의 상태 변환에서 발생한다.

1. running -> waiting : I/O 작업 요청 등으로 wait()하는 상황
2. running -> ready : 인터럽트 발생 시
3. waiting -> ready : I/O 작업 종료
4. terminate : 프로세스 종료

 

1), 4)번은 반드시 ready 큐에서 새로운 프로세스를 선택해야 하는 상황이다. I/O 작업의 발생이나 프로세스의 종료는 꼭 실행되어야 하는 프로세스가 존재하는 상황이기 때문에 다른 프로세스가 CPU 자원을 중간에 선점할 수 없다. 이를 비선점 스케줄링(Non-preemptive scheduling)이라고 한다. 그에 반해 2), 3)번의 상황에서는 다른 프로세스가 자원을 선점할 수 있는 선택의 여지가 있다. 따라서 CPU 자원의 경쟁이 발생할 수 있다. 이를 선점 스케줄링(Preemptive scheduling)이라고 한다. 이렇게 스케줄러가 레디 큐에서 실행할 다음 프로세스를 선택하고 나면, 디스패처가 문맥 교환, 유저 모드로의 전환, PC 이동(program counter jump) 등 자원 관리를 맡는다.

 

---

 

 

CPU 스케줄링 알고리즘

CPU 스케줄링의 목적은 waiting time을 줄이는 것이다. CPU 스케줄링은 스케줄링 알고리즘에 따라 그 성능이 달라지기 때문에 상황에 따라 맞는 CPU 스케줄링 알고리즘을 사용해야 한다.

 

1. First-Come, First-Served (FCFS)

FCFS 알고리즘에선 ready 큐에 삽입된 순서대로 실행한다. 즉 먼저 삽입된 프로세스를 먼저 실행한다. (FIFO) 효율성을 고려하지 않고 무조건 먼저 온 순서대로 실행시키기 때문에, 만약 실행시간이 매우 긴 프로세스가 앞 순서에 몰린다면 평균 대기 시간이 매우 길어질 가능성도 있다. FCFS는 다른 프로세스가 자원을 빼앗을 수 없는 비선점형 알고리즘이다.

 

2. Shortest-Job-First (SJF)

SJF 알고리즘은 CPU burst time이 낮은 순으로 실행한다. 실행시간이 낮은 프로세스부터 실행하기 때문에 평균 대기 시간이 매우 단축되는 이상적인 스케줄링 알고리즘이다. 다만 이 알고리즘의 문제점은 프로세스를 실행해보기도 전에 프로세스의 실행 시간을 알 수 없다는 것이다. 이론적으로 가장 최적화된 스케줄링 알고리즘이지만 이런 문제 때문에 실현가능성은 낮다.

 

SJF는 비선점형 알고리즘이지만 SJF의 선점형 버전으로 Shortest-remaining-time-first (SRTF) 알고리즘이 존재한다. SRTF에서는 선입선출로 자원을 할당하나, 다음 프로세스가 도착했을 때 잔여 작업이 적게 남아 있으면 CPU 자원을 우선 할당해줌으로써 평균 대기 시간을 더욱 단축시킨다.

 

3. Round-Robin (RR)

라운드 로빈은 FCFS와 유사한 선점형 알고리즘으로 CPU 자원을 quantum 시간에 따라 공평하게 나누며 도착한 순서대로 정해진 quantum만큼의 시간만 실행하는 것을 반복한다. 만약 모든 프로세스의 실행 시간이 quantum보다 낮으면 FIFO가 되고, 이 때 문맥 교환은 필요하지 않다. 그에 반해 q가 너무 작다면 프로세스는 제대로 실행되지 못한다. q가 짧을수록 문맥 교환이 많이 일어나기 때문에 오버헤드는 증가하고 효율은 떨어지며, 평균 대기 시간은 매우 길어질 수 있다.

 

프로세스의 우선순위가 계속 밀려 실행되지 못하고 무한정 대기하는 상태를 기아 상태(Starvation)라고 한다. 이는 FCFS와 같은 단순한 스케줄링 알고리즘을 사용할 경우에 발생하기 쉽다. 이런 상태는 Aging을 통해 오래동안 ready 상태였던 프로세스의 우선순위를 점진적으로 증가시킴으로써 해결한다. 

 

 

---

 

 

우선순위 기반 스케줄링 알고리즘

실시간(Real-time) 운영체제의 스케줄러는 선점(preemptive)을 이용한 우선순위 기반의 알고리즘을 지원해야 한다. 리얼타임 운영체제에는 데드라인이 존재하기 때문에 프로세스는 d시간 안에 한번은 실행되어야 실시간성을 만족한다고 본다. 

• 0 < t(실행시간) < d(데드라인) < p(주기)

 

1. Rate Monotonic Scheduling (RMS)

RMS는 선점형 정적 우선순위 스케줄링 알고리즘으로, 주기가 짧은 쪽에 높은 우선순위를 준다. 선점형 알고리즘이기 때문에 한 프로세스의 주기가 끝나기 전에 더 높은 우선순위를 가진 프로세스에게 자원을 빼앗길 가능성이 존재한다. 이 경우 데드라인이 끝나기 전에 실행을 끝마치지 못하게 되는 문제가 발생한다.

 

위의 예시에서 P1의 실행시간은 25ms이고 주기는 50ms이다. P1의 주기가 P2의 주기보다 짧기 때문에 먼저 실행된 후 종료되었다. 그 후에 P2가 실행되는데, 50ms에서 P1의 주기가 다시 돌아오면서 우선순위는 P1에게로 돌아간다. 이 때 P2는 아직 실행을 미처 끝마치지도 못한 상황이다. 이후 80ms에서 P2의 주기가 끝나면서 데드라인을 넘어간다.

 

CPU 이용률은 작업시간/주기 ($t/p$) 로 구할 수 있다. 최악의 경우 CPU 이용률은 $N(2^{1/N}-1)$ 이다. 이에 따르면 2개의 프로세스의 경우, CPU 이용률이 약 83%만 넘어도 스케줄링이 불가하다. ($N =2$,  $83/100$) 위 예시의 경우 각각의 CPU 이용률은

$P1 = 25/50 = 50$%
$P2 = 35/80 = 43..$%
도합 93%가 넘기 때문에 P2가 데드라인을 넘어갔다.

 

2. Earliest Deadline First Scheduling (EDF)

EDF는 마찬가지로 선점형 동적 우선순위 스케줄링 알고리즘으로, 데드라인에 근접한 쪽에 높은 우선순위를 준다. 위 예시의 경우 P1이 먼저 실행된 후 종료되고 P2가 실행된다. RMS에서는 P1의 주기가 다시 돌아오는 50ms 부근에서 우선순위가 P1에게 주어졌지만, EDF에선 데드라인에 근접한 쪽이 높은 우선순위를 가지므로 P2의 우선순위는 P1에게 빼앗기지 않는다.

 

우선순위가 고정되어 있지 않고 시간마다 프로세스들의 데드라인에 따라 동적으로 변화하기 때문에 RMS에서와 같은 데드라인이 넘어가는 문제를 어느 정도 해결 가능한 장점이 있다.

 

 

참고자료
Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 저, 운영체제(Operating System Concepts), 퍼스트북