[ 운영체제 ] CPU Burst Prediction

CPU 스케줄링 알고리즘 중 SJF 또는 SRTF는 CPU Burst Time 값을 통해 CPU를 할당할 프로세스를 결정한다. 그런데 어떤 프로세스의CPU Burst Time은 CPU에 직접 돌리기 전까지 알 방법이 없다. 그래서 CPU 스케줄링에 사용되는 CPU Burst Time은 실제값이 아닌 예측값이다. 이번 글은 CPU Burst Time을 예측하는 방법에 대한 글이다. 

 

CPU Burst Time은 편의상 CBT라고 하겠다.

 

CBT를 예측하는 방법에는 크게 Static한 방법과 Dynamic한 방법이 있다. Static한 방법은 말 그대로 상수처럼 미리 정해놓은 값을 기반으로 예측하는 방법이고, Dynamic한 방법은 유동적인 예측 방법이다. 

1. Static Method

[1] Process Size

프로세스의 용량으로 CBT를 예측하는 방법이다. 이미 실행된 P_old라는 프로세스의 크기가 200KB 이고, CBT가 20ms라고 하자. P_new라는 새로운 프로세스가 레디 큐에 들어왔는데 프로세스의 용량이 201KB라고 한다. 이미 실행된 P_old의 용량과 아직 실행되지 않은 P_new의 용량이 거의 같으므로, P_new의 CBT는 대략 20ms로 예측할 수 있다.

[2] Process Type

프로세스 타입으로 CBT를 예측하는 방법이다. 프로세스 타입은 크게 OS 프로세스와 User 프로세스로 구분할 수 있다. OS 프로세스는 scheduler, dispatcher, segmentation, fragmentation과 같은 프로세스를 말하며 User 프로세스는 gaming, application software와 같은 프로세스를 말한다. 일반적으로 OS 프로세스가 빨리 끝나고, User Process가 오래 걸린다.

 

만약에 새로운 dispatcher 프로세스가 레디 큐에 들어오면 이전에 이미 수행된 dispatcher 프로세스의 CBT를 통해 새로운 dispatcher 프로세스의 CBT를 예측할 수 있다. 

2. Dynamic Method

[1] Simple Moving Average (SMA)

 

이미 수행된 n개의 프로세스 CBT로 새로운 프로세스의 CBT를 예측하는 방법이다. 위 그림은 n=4인 예시다. 

[2] Weighted Moving Average (WMA)

 

SMA에서 가중치를 부여한 방법이다. 가중치 설정 방법은 마음대로지만, 일반적으로 최근값에 큰 가중치를 두는데 이는 최근값을 더 많이 반영하겠다는 뜻이다. 가중치를 전부 1로 설정하면 SMA와 완벽하게 일치한다. 

[3] Exponential Moving Average (EMA)

좌, 우는 같은 식이다

 

WMA에서 가중치를 지수 함수 형태로 설정한 방법이다. 지수함수는 증가폭이 크기 때문에 n이 충분히 커지면 가중치가 0으로 수렴하게 된다. 이전 데이터와 가중치 차이가 WMA에 비해서 크다. 

 

이전 두 방식은 n개의 데이터를 알고 있어야 했다. 그러나 EMA 방식은 직전값만 알고 있으면 된다. 왜냐하면 직전값에 이전 데이터의 이력들이 모두 반영되어 있기 때문이다. 위 그림에서 EMA_5를 구하는 식을 살펴보자. 우측 그림을 먼저 보면 EMA_5를 구할 때 EMA_4와 직전값 P4가 사용됨을 확인할 수 있다. EMA_4는 좌측 그림에서 찾을 수 있는데 P1, P2, P3가 모두 반영되어 있다. 식을 다시 정리하면 아래와 같다.

 

새로운 EMA = 가중치*직전 EMA + (1 - 가중치)*직전 P

 

Moving Average Graph (SMA, WMA, EMA)