[Algorithm] Programmers :: 디스크 컨트롤러 (CPU스케줄링 비선점형 SJF알고리즘)

https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

struct Node
{
    int requestedTime;
    int workTime;
 
    Node() {};
    Node(int _requestedTime, int _workTime) : requestedTime(_requestedTime), workTime(_workTime) {};
};
 
struct pqCmp
{
    bool operator()(const Node& a, const Node& b)
    {
        return a.workTime > b.workTime; // 최상단 노드가 제일 작은값.
    }
};
 
bool cmp(const vector<int>& a, const vector<int>& b)
{
    if (a[0] == b[0]) // 요청시간이 동일하면
    {
        return a[1] < b[1];
    }
    return a[0] < b[0];
}
 
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int currentProcessWorkEndTime = 0;
    int nextJobsIndex = 0;
    Node currentWorkNode;
    sort(jobs.begin(), jobs.end(), cmp); // 요청시간순으로(requestedTime) 오름차순정렬.
 
    priority_queue<Node, vector<Node>, pqCmp> pq;
 
    while (!pq.empty() || nextJobsIndex < jobs.size()) // 잔여 프로세스가 존재한다면
    {
        if (!pq.empty()) 
        {
            currentWorkNode = pq.top(); // 새로 작업할 노드.
            pq.pop();
 
            int timeFromRequestToEnd = (currentProcessWorkEndTime + currentWorkNode.workTime) - currentWorkNode.requestedTime;
            answer += timeFromRequestToEnd;
            currentProcessWorkEndTime = currentProcessWorkEndTime + currentWorkNode.workTime; // 종료시간 갱신
 
            // 새로 작업할 노드가 끝나기 이전에 요청되어진 프로세스가 있을경우 큐에 삽입.
            while (nextJobsIndex < jobs.size()) 
            {
                if (jobs[nextJobsIndex][0] < currentProcessWorkEndTime) // 요청시간이 종료시간보다 앞일 경우 (큐에 넣어야 하는 상황)
                {
                    pq.push(Node(jobs[nextJobsIndex][0], jobs[nextJobsIndex][1])); // 큐에삽입.
                    nextJobsIndex++;
                }
                else break;
            }
        }
 
        else // 잔여 프로세스가 있는데 큐에 아무값도 없으면. 즉 요청시간이 너무 뒤일경우 강제로 바로 넣어버리기.
        {
            pq.push(Node(jobs[nextJobsIndex][0], jobs[nextJobsIndex][1]));
            currentProcessWorkEndTime = jobs[nextJobsIndex][0];
            nextJobsIndex++;
        }
    }
 
    return answer / jobs.size();
}

 

위 문제는 CPU스케줄링 알고리즘 중 하나인 SJF알고리즘을 구현하는 문제이다.

기본적으로 작업시간이 짧은 프로세스에 CPU를 할당한다.

선점형, 비선점형 둘 다 있는데 위 문제같은 경우는 비선점형 문제이다. 한 프로세스의 요청작업이 완료되기 전까지는 다른 프로세스에게 CPU를 할당하지 않는다.

선점형은 조건에 따라 현재 프로세스의 CPU할당을 멈추고, 다른 프로세스에 CPU가 할당되기도 한다.

 

일단 요청작업 벡터를 요청시간 기준으로 오름차순 정렬을한다(요청시간이 같을 경우 작업시간이 짧은걸 우선으로 한다). 그리고 새로운 프로세스의 작업요청을 업데이트할 때마다(노드를 큐에서 꺼낼 때마다) 작업종료시간을 업데이트하고 jobs를 앞에서부터 탐색하면서 작업종료시간보다 이전에 작업요청이 있는 프로세스의 요청을 큐에 넣는다. 큐에 넣은 프로세스는 다시 검사하면 안되기 때문에 인덱스를 따로 저장한다.

 

큐의 우선순위는 작업시간이 짧은 프로세스이다. 그렇기 때문에 pop을 할 때마다 요청시간이 가장 짧은 프로세스가 꺼내지게 우선순위비교함수를 priority_queue의 매개변수에 넣으면 된다.

 

예외상황 한가지 빼고는 알아서 큐에넣고 꺼내서 값 계산하고 한다. 한가지의 예외상황은, 큐는 비어있는데 아직 프로세스가의 요청이 남아있는 경우이다. 즉, 큐의 마지막 프로세스가 작업을 마친 이후의 시점보다 잔여프로세스의 요청시간이 더 큰 경우이다. 

큐가 비어있는데 잔여프로세스가 있으면 그냥 바로 큐에 넣어버리면 된다. CPU가 놀고 있기 때문이다.

 

다만 아직 이해 못한 부분이 있는데, 처음 짰을때는 jobs를 정렬할 때 그냥 요청시간으로만 오름차순 정렬했다.

요청시간이 같을 경우 작업시간순으로 정렬하는 코드는 없었다. 이 상태로 검사를 하니까 테스트케이스 18번만 실패해서 다른사람 글을 찾아보니까 요청시간이 같을경우엔 작업시간순으로 정렬하는 코드를 추가하라고 해서 추가했다.

근데 둘 다 요청시간이 같기 때문에 우선순위큐에 push될 것이고, 우선순위큐에 넣어버리면 알아서 꺼낼 때 작업시간 짧은걸로 꺼내지는데 어떤 차이가 있는지 잘 모르겠다...