Seungho Jeong

Backend Problem Solver (feat. Python)

게시:
수정:

일반적인 CPU 스케줄링 알고리즘에 대한 포스팅이다.
여기서 일반적이라함은 단일 프로세서(CPU)･스레드(Thread), 비실시간(Unreal-time)을 의미한다.

FCFS (First-Come First-Served)

가장 쉽게 떠올릴 수 있는 솔루션으로 큐(Queue)에 도착한 순서대로 처리하는 스케줄링이다. 마치 인간 세계에서 은행에 먼저 도착한 사람의 볼 일이 끝날 때 까지 뒤에 있는 사람이 기다려야 하는 것과 같은 방식이다. 순전히 선착순으로 먼저 도착한 프로세스는 볼 일이 끝날 때까지 CPU를 보장받는다. 즉, 비선점형(Non-Preemptive)이다.

문제점 (Problem)

꽤 공정하지만 앞에 어떤 프로그램이 있느냐에 따라 기다리는 시간에 대한 영향이 크기 때문에 그다지 효율적이지 않다. 같은 프로그램들이 실행되어도 도착 순서에 따라서 평균 대기 시간(Averaging waiting time)이 크게 차이 나기 때문이다.

우연히 CPU를 오래 쓰는 프로세스(Longer Job)가 다른 프로세스보다 먼저 도착해서 CPU를 잡고 있으면 Interactive한 Job과 같이 CPU를 짧게 쓰는 프로세스가 계속 기다려야 한다. 만약 처리하는데 1억 초가 걸리는 Job이 먼저 큐에 들어오면 뒤에 있는 Job들은 1억 초를 기다려야 할 수도 있다.

참고로 이렇게 CPU 사용시간이 긴 프로세스로 인해 짧은 프로세스들이 오래 기다리는 현상을 호위 효과(Convoy effect)라고 한다.

하지만 컨텍스트 스위치가 별로 없고 오히려 오버헤드로 작용하는 복잡한 과학 연산이나 행렬 계산 같은 경우에는 오히려 이러한 방식이 적합하다.

SJF (Shortest Job First)

수저론 알고리즘으로 CPU Burst time이 가장 짧은 프로세스한테 CPU를 넘겨 주는 스케줄링이다. CPU 사용시간이 짧은 금수저로 태어난 프로세스는 빨리 처리되고 CPU 사용시간이 긴 흙수저로 태어난 프로세스는 늦게 처리된다.

각 프로세스의 다음(Next) CPU Burst time 추정치를 스케줄링에 활용한다.

Next CPU Burst time 추정방법
어떠한 프로세스가 다음 번에 CPU를 얼마나 사용하는 것은 불가능하다. 다만 과거의 흔적으로 예측할 뿐이다.
이 추정치는 과거 CPU Burst time으로 추정하며 이렇게 추정한 값은 Exponential Averaging이라 한다.

𝛕n+1 = ɑTn + (1-ɑ)𝛕n (여기서 ɑ는 상수이며, 0 ≤ ɑ ≤ 1)

Tn : 실제 CPU 사용 시간 (Actual length of CPU burst.)
𝛕n+1 : 예측한 CPU 사용 시간 (Predicted value for the next CPU burst.)

SJF의 분류

스케줄링을 언제 다시 할 것인가에 따라 또 Preemptive 방식과 Non-Preemptive 방식으로 나뉜다.

① Non-Preemptive

일단 CPU를 잡으면 더 짧은 프로그램이 도착하더라도 CPU Burst가 끝날 때 까지 CPU를 보장한다. 이 방식은 CPU Burst가 끝나면 그제서야 스케줄링한다.

② Preemptive

현재 수행 중인 프로세스의 남은 Burst time보다 더 짧은 CPU Burst time을 가지는 새로운 프로세스 도착하면 그냥 CPU를 뺏어버린다. 항상 가장 짧은 시간을 갖는 프로세스를 찾으며 스케줄링한다.

이러한 특성으로 인하여 SRTF(Shortest Remaining Time Find)라고도 한다.

문제점 (Problem)

① Starvation (기아 현상)

흙수저 프로세스는 영원히 구제 받지 못할 수도 있는 문제가 있다.

SJF는 CPU 사용 시간이 짧은 Job을 극도로 선호하기 때문에 경우에 따라서 CPU 사용 시간이 긴 프로세스는 영원히 CPU를 못 쓸 수도 있다. 이와 같이 흙수저 프로세스가 구제받지 못하는 안타까운 현상을 기아 현상(Starvation)이라 한다.

② CPU 사용 시간을 미리 알 수 없다.

프로세스는 때론 사용자의 입력(User input)을 받고 브랜치(Branch)도 일어나기 때문에 각 프로세스마다 CPU를 얼마나 쓰고 나갈지 정확하게 아는 것 자체가 불가능하다.

정확하게 Shortest Job에게 CPU를 주고 싶지만 완전한 실제 구현은 불가능한 것이다.

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

마찬가지로 수저론 알고리즘이다. 어떠한 기준으로 각 프로세스에 우선순위를 메겨서 우선순위가 높은 것부터 처리하는 방식이다. 각 프로세스마다 우선 순위를 나타내는 숫자(Priority Number)가 정수로 주어지고 우선 순위가 가장 높은 프로세스(Highest priority process)에게 CPU를 주는 개념이다. 우선 순위가 높은 프로세스(금수저)에게 낮은 정수(Integer)를 붙여 표현한다.

SJF도 Predicted next CPU burst time을 Priority로 사용한 일종의 우선 순위 스케줄링으로 볼 수 있고 SJF와 마찬가지로 CPU 선점 여부에 따라 Non-Preemptive와 Preemptive로 나눈다.

문제점 (Problem)

SJF와 같이 우선 순위가 낮은 Job은 영원히 실행되지 않는 가능성을 갖는 Starvation 문제가 있다.
Low priority processes may never execute.

해결 방법 (Solution)

아무리 우선 순위가 낮아도 오래되면 우선 순위를 올려주어 해결한다. 이를 Aging이라고 한다.
As time progresses increase the priority of the process.

RR (Round Robin)

선착순으로 줄을 서긴 서는데 모든 프로세스가 공평하게 짧은 시간으로 CPU를 돌려쓰는 방식이다. 각 프로세스가 동일한 크기의 할당 시간(Time Quantum)을 가짐으로써 할당 시간이 지나면 프로세스가 선점(Preempted) 당하고 레디 큐(Ready Queue)의 제일 뒤에 가서 다시 줄을 서는 알고리즘이다. 흙수저 프로세스도 구제받을 수 있는 이 알고리즘이 바로 현대적인 OS에서 사용하는 방식이다.

n 개의 프로세스가 레디 큐에 있고 할당 시간이 q 인 경우, 각 프로세스는 q 시간단위로 1/n의 CPU 시간을 확보하며 최대 대기 시간은 (n-1)q 를 넘지 않는다.

일반적인 할당 시간은 10~100 milliseconds이다. 할당 시간을 짧게 잡으면 CPU 차례도 빨리 돌아오며 CPU 사용 시간이 짧은 프로세스는 한 번에 쓰고 나가버릴 수 있다.

문제점 (Problem)

문제점까지는 아니고 단점이라 할 수 있다. 할당 시간이 너무 짧으면 약간 길 때 보다 한 번에 쓰고 나갈 수 있는 프로세스가 적어지게 되어 대기 시간(Waiting)이 증가하고 잦은 컨텍스트 스위치(Context switch)로 시스템 오버헤드가 증가하게 되어 전체적인 시스템 전체 퍼포먼스가 감소한다.

특징

① 빠른 응답 시간

가장 큰 장점으로는 응답 시간이 빨라진다는 점이다. 대기열 앞에 있는 프로세스들의 CPU 사용 시간에 관계없이 최대 (n-1)q 시간 후에는 CPU를 얻을 수 있으므로 CPU를 최초로 얻기까지 걸리는 시간이 짧다.

또한 누가 CPU를 사용할지 모르는 상황속에서 굳이 다음 번 CPU burst time을 예측할 필요없이 할당 시간(Time quantum)보다 CPU를 짧게 쓰는 프로세스가 CPU를 빨리 쓰고 나갈 수 있게 해준다.

② 대기시간이 CPU 사용 시간에 비례한다.

CPU 사용 시간이 긴 프로세스는 할당 시간이 끝나면 강제로 CPU를 빼앗기고 레디 큐의 제일 뒤에 가서 다시 줄을 선다. 다시 차례가 됐을 때에도 작업을 못 끝내면 앞의 사이클을 다시 반복하고 프로세스가 끝날 때 까지 이를 되풀이하게 되므로 전체적인 대기 시간(Waiting time)이 증가한다.

반면 CPU 사용 시간이 짧은 프로세스는 이 반복 횟수가 줄어 대기 시간도 짧아지며 만약 CPU 사용 시간이 할당 시간보다 짧은 경우에는 응답 시간(Response time)이 대기 시간이 된다.

Reference

반효경, “ 반효경 [운영체제] 11. CPU Scheduling 2 / Process Synchronization 1” KOCW. 2014년 4월 1일. video, http://www.kocw.net/home/cview.do?lid=aa53d6aa576466ee


OS 시리즈 모두보기 (펼치기)


댓글남기기