[운영체제] 9. 스케줄링 (3) - Interactive System 스케줄링

인터렉티브 시스템은 사용자의 요청에 얼마나 빠르게 응답하는지를 중점적으로 보는 시스템이다.

따라서 인터렉티브 시스템은 선점형 스케줄링 알고리즘을 사용하며 response time 을 낮추는 것을 목표로 하였다.

 

이번 글에서는 인터렉티브 시스템의 스케줄링 알고리즘들을 정리해보자.

 

 

Round Robin Scheduling

라운드 로빈 스케줄링은 이름 그대로 빙글빙글 돌아가면서 프로세스를 실행하는 알고리즘이다.

배치 시스템 스케줄링에서 봤었던 FCFS 스케줄링처럼 앞에 것을 실행하고 뒤로 보내는 것을 반복하면서 마치 원형큐를 사용하듯 쓰는 방법인데, 여기에 선점형 스케줄링의 속성이 추가되었다고 보면 된다.

 

 

 

(a) 그림에 있는 프로세스들이 runnable 프로세스 ( = ready 상태에 있는 프로세스, running 아님!) 이고,

(b) 그림은 B 프로세스가 running 상태에서 동작하고 돌아온 이후의 모습을 보여준다.

 

라운드 로빈 스케줄링은 선점형이므로 각 프로세스가 CPU를 사용할 수 있는 고정된 시간을 가져야 한다.

이 고정된 시간을 가리켜 퀀텀(quantum) 이라고 부른다.

 

만약 퀀텀의 길이가 10ms 라면, B가 running 상태가 되고 10ms가 지나도 B의 실행이 끝나지 않은 경우, B를 ready상태로 내려서 기존의 runnable process list 뒤에 붙이게 된다.

 

라운드 로빈에서는 퀀텀의 길이를 적절하게 설정하는 것이 중요하다.

만약 퀀텀의 길이가 너무 짧다면 프로세스 스위칭이 너무 자주 발생하므로 CPU가 프로세스 스위칭에 많은 시간을 쓰게 되므로 오버헤드가 발생하여 CPU 효율이 낮아지고,

퀀텀의 길이가 너무 길다면 response time 이 길어지게 되므로 인터렉티브 시스템의 목표를 달성하지 못하게 된다.

 

 

 

Priority Scheduling

우선순위 스케줄링은 각 프로세스에 우선순위를 매기고, 한 프로세스의 실행이 끝난 뒤에는 runnable 프로세스 중 우선순위가 가장 높은 프로세스를 실행하는 스케줄링 방법이다.

 

이 방법은 우선순위가 높은 프로세스만 계속 실행되는 문제가 발생할 수 있기 때문에, 모든 프로세스가 균등하게 실행될 수 있도록 몇 가지 장치를 더 추가할 수 있다.

 

첫 번째는 실행중인 프로세스의 우선순위를 클락 틱마다 깍는 방법이다.

계속 우선순위를 깎다가 그 다음 차례 프로세스보다 우선순위가 낮아지면 프로세스 스위칭이 발생한다.

두 번째는 각 프로세스마다 실행 가능한 시간(퀀텀)을 정해놓고, 그 시간이 지나면 강제로 다른 프로세스와 교체한다.

(혼공운체 책에서는 에이징 기법을 사용하여 일정 시간이 지날 때마다 전체 프로세스의 우선순위를 높이는 방법을 사용하였다.)

 

 

프로세스에 우선순위를 부여하는 방법도 다양하게 있을 수 있다.

먼저 static하게 우선순위를 부여하는 경우 프로세스를 실행하는 유저의 권한 등급이 높은 순으로 실행을 시킬 수도 있고,

돈을 지불하는 프로세스에게 우선순위를 부여할 수도 있고, 리눅스에서는 nice 라는 명령어를 통해 현재 실행중인 프로세스의 우선순위를 내릴 수 있는데, 이런 방법이 정적 우선순위 부여 방법이다.

 

다음으로 dynamic하게 우선순위를 지정하는 경우, 상대적으로 CPU를 적게 사용하는 I/O bound 프로세스에게 높은 우선순위를 준다.

이때 우선순위는 1/f (f의 역수) 로 주는데, f = 실세 실행 시간 / 퀀텀 길이 이다.

즉, 내가 할당받은 퀀텀에 비해 실제로 실행한 시간이 짧을 수록 높은 우선순위를 부여받는 것이다.

 

 

다단계 큐 스케줄링 (Priority Class)

 

우선순위 스케줄링의 발전된 버전이다.

우선순위 클래스별로 나눠서 runnable process list 를 만들고, 그 안에서는 라운드 로빈 스케줄링으로 한 퀀텀씩 실행한다.

제일 높은 우선순위의 runnable process list 가 비게 되면, 그 다음 우선순위에 대해서 다시 라운드 로빈 스케줄링이 실행된다.

이 방법은 여전히 낮은 우선순위에 있는 프로세스들이 계속 실행되지 못하는, 기아 문제가 발생할 여지가 있다.

 

 

CTSS

1962년에 등장한 이 알고리즘은 CPU bound 프로세스에게 높은 퀀텀을 주는 것이 효율적이라는 아이디어에서 시작되었다.

하지만 모든 프로세스에게 높은 퀀텀을 주면 response time 이 길어지므로, 다음과 같은 방법을 사용한다.

 

1. 가장 높은 우선순위에 있는 프로세스에게 1퀀텀을 준다.

2. 이 프로세스가 1 퀀텀을 소모하고도 여전히 할 일이 남았다면, 한 단계 낮은 우선순위로 넘기고 차례가 왔을 때 2퀀텀을 준다.

3. 퀀텀의 크기를 2배씩 늘리면서 이 프로세스가 필요로 하는 퀀텀을 모두 소모할 때까지 반복한다.

 

즉 제일 높은 우선순위에는 1퀀텀, 그 다음에는 2퀀텀, 그 다음에는 4퀀텀 이렇게 2배씩 늘어난 크기의 퀀텀을 할당받도록 세팅해두고, 매번 퀀텀을 소모할 때마다 우선순위를 낮추는 방식이 CTSS 방식이다.

 

만약 어떤 프로세스가 100 퀀텀을 소모해야만 종료될 수 있다면, 이 프로세스는 1 + 2 + 4 + 8 + 16 + 32 + 64 퀀텀이 주어져아먄 종료된다. (물론 64퀀텀이 주어졌을 때는 실제론 37 퀀텀만 소모하면 종료될 것이다.)

 

만약 기존의 라운드로빈 방식을 사용한다면 100번의 프로세스 스위칭이 필요하겠지만, 이 방법을 사용하면 총 7번의 프로세스 스위칭으로 프로세스의 실행을 마칠 수 있다.

또한 CPU bound 프로세스는 점점 우선순위가 낮아지기 때문에 상대적으로 cpu burst가 작은 I/O bound 프로세스가 높은 우선순위에서 빠르게 실행되므로 인터렉티브 시스템의 목적에 맞게 동작한다는 장점도 있다.

I/O bound 프로세스는 높은 우선순위에서  I/O를 요청하고 blocked 상태로 빠진 뒤, I/O가 끝나면 다시 높은 우선순위의 큐 뒤로 들어가 실행차례를 기다리므로 빠르게 실행될 수 있다.

또한 이때 다시 실행될 때는 기존에 자신이 사용했던 시간은 생각하지 않고 동일한 퀀텀을 그대로 받는다. (어떻게보면 당연하다.)

 

예를 들어 1퀀텀이 10ms 인데, 5ms를 사용하고 I/O를 요청해서 Blocked 상태에 갔다가 같은 우선순위 클래스의 ready로 돌아와서 실행되더라도, 나머지 5ms 만큼의 시간만 받는게 아니라, 똑같이 1퀀텀 10ms 의 시간을 받게 된다.

 

XDS 940

(설명하지 않고 넘어가셨다.)

 

 

 

Shortest Process Next

이 스케줄링은 평균 response time을 낮추는 스케줄링 기법이다.

 

먼저 프로세스의 과거 행동을 기반으로 실행 시간의 추정치를 계산한다.

그리고 프로세스를 실행할 때는 이 추정 실행 시간이 제일 짧은 프로세스부터 실행한다.

 

추정치를 계산할 때는 다음 공식을 사용하는 aging 기법을 사용하여 계산한다.

 

a * T0 + (1-a) * T1  (0 < a < 1)

 

T0 은 과거에 추정했던 시간이고, T1 은 실제로 실행하면서 걸린 시간이다.

만약 a = 1/2 을 넣는다고 하면 다음과 같이 동작한다.

 

1. 처음에는 실제로 실행하면서 길린 시간이 없으니 T0 으로 예측한다.

 

T0 추정치 : T0

 

2. T0 에서 예측한 시간과 실제로 실행하면서 걸린 시간 T1 을 1/2 비율로 반영하여 새로운 추정치를 계산한다.

 

T1 추정치 : 1/2 * (T0) + 1/2 * T1

 

3. T1에서 예측한 추정치와 실제로 T2에서 실행하면서 걸린 시간을 1/2 비율로 반영하여 새로 추정치를 계산한다.

 

T2 추정치 : 1/2 * ( 1/2 * (T0) + 1/2* T1 ) + 1/2 * T2

 

4. T2에서 예측한 추정치와 실제로 T3에서 실행하면서 걸린 시간을 1/2 비율로 반영하여 새로 추정치를 계산한다.

 

T3 추정치 : ... (이하 재귀적으로 반복)

 

 

따라서 이 식을 풀어서 작성하면

 

이렇게 각 시간마다 연산한다.

그러면 과거의 측정치는 점점 반영되는 비율이 낮아지고, 최근에 측정된 데이터는 점점 반영되는 비율이 높아진다.

 

 

이 방식은 리눅스 시스템에서 여러 명의 사용자가 접속해서 각자의 쉘에서 커맨드를 입력하는 상황을 예로 볼 수 있다.

이때 각각의 사용자가 실행하는 프로그램은 사실 하나의 리눅스에 있는 프로그램을 같이 실행하는 것이므로 리눅스 시스템 입장에서는 전체 쉘에서 들어오는 커맨드 입력이 주어질 때마다 매번 추정치를 계산을 해서 가장 작은 추정치의 프로세스를 우선적으로 CPU할당하는 정책을 취한다.

 

하지만 이 방법이 실제로는 그렇게 도움이 되지 않을 수 있다.

각 사용자가 서로 제각각의 프로그램을 돌리면 추정치를 제대로 계산하는 것이 힘들어지기 때문이다.

 

 

Guaranteed Scheduling

이름 그대로 보장을 해주는 스케줄링 방식이다.

만약 어떤 프로세스가 생성되었을 때, 생성되고 보니 자신을 포함해 10개의 프로세스가 있었다고 해보자.

그리고 시간이 지나서 뭔가 스케줄링이 발생을 하면 운영체제는 그때까지의 프로세스의 CPU 사용 시간을 측정한다.

 

만약 스케줄링이 발생한 시간이 어떤 프로세스가 성성된 이후에 100ms 가 지났을 때라고 해보자.

그러면 마지막 스케줄링 이후부터 지금 스케줄링 사이에 적어도 새로 생성된 프로세스는 100ms의 CPU time 중 10ms 의 CPU time을 보장받아야 한다. (10개의 프로세스가 있다고 하였으므로)

 

그런데 실제로 측정을 해보니 7ms 밖에 사용하지 않았다고 해보자.

그러면 이 프로세스는 1/n 목표치인 10ms 보다 부족한 7ms 를 사용했으므로, 그 ratio 가 7/10 이 된다.

 

만약 어떤 프로세스는 생성된 이후에 지금까지 5ms 밖에 사용하지 못했다면 목표치인 10ms 에 비해서 5/10 50%밖에 보장받지 못한 것이다.

 

이렇게 각각의 모든 프로세스마다 보장 시간 대비 사용시간의 비율을 계산해서, 그 비율이 제일 낮은 억울한 프로세스를 우선적으로 running 상태로 올려서 1/n을 보장받을 수 있도록 만드는 것이 Guaranteed Scheduling 방식이다.

 

 

 

Lottery Scheduling

이름 그대로 프로세스들에게 복권 티켓을 주고, 복권에 당첨된 프로세스에게 자원을 할당하는 스케줄링 방법이다.

프로세스마다 어떤 프로세스는 1장, 어떤 프로세스는 2장 이렇게 복권 티켓을 주고, 스케줄링을 할 때마다 복권을 추첨해서 CPU 자원을 할당한다. 그래서 전체 복권의 개수 대비 보유하는 비율이 f 인 프로세스는 CPU 리소스 역시 전체 프로세스의 cpu time 대비 f의 비율을 갖는 cpu time 을 가지게 될 것이라고 에측할 수 있다.

 

또 이 스케줄링 방식은 High Responsive 해서,티켓을 받는 즉시 CPU 쟁탈전에 참여할 수 있으며,

자신의 티켓을 동료 프로세스에게 넘겨줘서 동료 프로세스의 당첨 확률을 높이도록 동작할 수도 있다.

 

예를 들어 어떤 비디오 스트리밍 서버가 있다고 할 때, 이 스트리밍 서버의 유료 구독자가 있고 무료 구독자가 있다고 하자.

그러면 유료 구독자를 상대하는 프로세스와 무료 구독자를 상대하는 프로세스가 있을 텐데, 고화질을 처리해서 전송해야하는 유료 구독자의 프로세스에게는 복권 티켓을 많이주고, 저화질로 처리해도 괜찮은 무료 구독자를 상대하는 프로세스는 적은 복권 티켓을 줌으로써 CPU 할당량의 비율을 조절할 수 있다.

 

 

Fair Share Scheduling

이름을 직역하면 공평한 몫을 배분하는 스케줄링이다.

지금까지는 자원을 '프로세스' 에게 균등하게 분배하는 것에 집중했다면

이 스케줄링 방식은 '유저' 에게 균등하게 분배하는 것에 집중한다.

 

예를 들어 라운드 로빈 방식을 사용하여 스케줄링할 때, User 1 이 9개 프로세스를 사용하고 User 2 가 1개 프로세스를 사용한다면, User2는 전체 CPU 자원의 10%만 할당받게 되므로 억울할 수 있다.

그래서 이 이케줄링 방식은 프로세스를 실행시키는 (소유한) 유저를 고려한 뒤에 스케줄링한다.

 

그래서 만약 User 1 이 A, B, C, D 4개 프로세스를 실행시키고, User 2가 E 1개의 프로세스를 실행시킨다면,

두 유저 입장에서는 50% 씩 프로세스를 할당해서 A E B E C E D E A E B E C E D E ... 순으로 스케줄링 하는 것이 Fair Share 스케쥴링이다.