최단 작업 우선 스케줄링 구현하기, C++

 

CPU 스케줄링에서도 엄청 많이 나오는데..

우리는 동적으로 사람이 들어오진 않으니까

starving에 대한 걱정은 말고 풀어보자.

 

저런 알고리즘을 적용하는 이유는 평균 대기시간을 줄이기 위해서다.

앞사람이 길수록 뒷사람이 오래기다리는 것과 같은 이치다.

??? 무슨상관이냐고..?

대기는 각각 한다.

즉, 기다리는 사람의 수만큼 한다.

일이 끝난 사람은 대기를 하지 않는다.

그렇다면...?

일을 빨리 끝내서 기다리는 사람을 줄여야 한다.

 

그것을 위한 알고리즘이 바로 Shortest job first algorithm 이다.

 

구현해보자

 

사실 구현할 것은.. 실제로 대기시간이 줄어들었느냐? 확인만하면 된다.

즉, 대기시간만 알아내면 끝이다...ㅎㅎ

 

당연히 입력으로는 작업시간이 주어져야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template<typename T>

//대기시간 계산한 벡터 반환 (작업시간으로 계산함)
auto compute_waiting_times(std::vector<T>& service_times)
{
    std::vector<T> W(service_times.size());
    W[0] = 0;
    
    for(auto i = 1; i < service_times.size(); i++)
        W[i] = W[i-1] + service_times[i-1]; //내 대기 시간은 내 앞 사람의 대기시간  + 앞 사람의 작업시간
    
    return W;
}

//즉, 우리가 할 일은 그저 작업시간이 짧은 순서대로 사람을 놓기만 하면 된다.
//실제로 정렬하지 않은 것보다 줄어들었는가??는 각자 확인해보자