최단 작업 우선(SJF) 스케줄링

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

최단 작업 우선 스케줄링

• 처리 시간이 짧은 작업을 우선적으로 배치해 전체 수행 시간을 줄이는 방법이다.
• 가능한 많은 작업의 대기 시간을 줄이기 위해서는 짧은 작업을 우선적으로 처리해야 한다.

 

최단 작업 우선 스케줄링의 예

• 프로세스 수행 시간에 따른 CPU 할당 순서 지정
• ...

 

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

using namespace std;

template <typename T>
auto compute_waiting_times(vector<T>& service_times)
{
    size_t size = service_times.size();
    vector<T> W(size, 0);

    for (int i = 1; i < size; ++i)
        W[i] = W[i - 1] + service_times[i - 1];

    return W;
}

template <typename T>
auto print_vector(vector<T>& V)
{
    for (auto& i : V)
        cout << i << " ";

    cout << endl;
}

template <typename T>
void compute_and_print_waiting_times(vector<T>& service_times)
{
    auto waiting_times = compute_waiting_times<T>(service_times);

    cout << "- 처리 시간: ";
    print_vector<T>(service_times);

    cout << "- 대기 시간: ";
    print_vector<T>(waiting_times);

    auto avg_waiting_times = accumulate(waiting_times.begin(), waiting_times.end(), 0.0f) / waiting_times.size();

    cout << "- 평균 대기 시간: " << avg_waiting_times << endl;
}

void main()
{
    vector<int> service_times{8, 1, 2, 4, 9, 2, 3, 5};

    cout << "[처음 일 처리 시간 & 대기 시간]" << endl;
    compute_and_print_waiting_times<int>(service_times);

    // 일 처리 시간을 오름차순으로 정렬
    sort(service_times.begin(), service_times.end());

    cout << endl << "[정렬 후 일 처리 시간 & 대기 시간]" << endl;
    compute_and_print_waiting_times<int>(service_times);
}

 

출력

[처음 일 처리 시간 & 대기 시간]
- 처리 시간: 8 1 2 4 9 2 3 5
- 대기 시간: 0 8 9 11 15 24 26 29
- 평균 대기 시간: 15.25

[정렬 후 일 처리 시간 & 대기 시간]
- 처리 시간: 1 2 2 3 4 5 8 9
- 대기 시간: 0 1 3 5 8 12 17 25
- 평균 대기 시간: 8.875