프로그래머스 | 디스크 컨트롤러 - java

프로그래머스

 

# 핵심

SJF (Shortest Job First) 스케쥴링! <<-- "우선순위 큐 (Priority Queue)" 이용

(= 가장 짧은 작업 우선 처리)

 

# 통과 코드

import java.util.*;

class Solution {

    private static class Job implements Comparable<Job> {
        int requestTime; // 요청 시간
        int runTime; // 서비스 시간

        public Job(int[] job) {
            this.requestTime = job[0];
            this.runTime = job[1];
        }

        @Override // 서비스 시간 오름차순
        public int compareTo(Job o) {
            return this.runTime - o.runTime;
        }
    }

    public int solution(int[][] jobs) {
        PriorityQueue<Job> queue = new PriorityQueue<>();

        // jobs 배열을 꼭 정렬해야함!! (1. 요청 시간 -> 2. 작업 시간 기준 오름차순 정렬)
        Arrays.sort(jobs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) return o1[1] - o2[1];
                else return o1[0] - o2[0];
            }
        });

        int total = 0; // 합계 시간
        int endTime = jobs[0][0]; // 작업 종료시간 (첫 작업 요청 시간으로 초기화)
        int idx = 1;
        queue.add(new Job(jobs[0]));

        while(!queue.isEmpty()) {
            Job currentJob = queue.poll(); // 다음으로 진행할 작업
            total += (endTime - currentJob.requestTime + currentJob.runTime); // 요청~종료시간 추가
            endTime += currentJob.runTime; // 작업 종료시간 계산

            // 작업 종료시간 이전에 새로운 작업 요청이 있는 경우 대기 큐에 삽입
            while(idx < jobs.length && jobs[idx][0] <= endTime) {
                queue.add(new Job(jobs[idx]));
                idx += 1;
            }

            // 작업 종료
            
            // 대기 큐가 비어있는 경우 (작업이 끝날때 까지 다른 작업 요청이 없던 경우)
            // 다음 작업을 대기 큐에 넣는다
            if(idx < jobs.length && queue.isEmpty()) {
                endTime = jobs[idx][0];
                queue.add(new Job(jobs[idx]));
                idx += 1;
            }
        }
        return total / jobs.length;
    }
}

 

<순서>

1. int[][] jobs 배열 정렬 (요청 시간,작업시간 오름차순)

2. 첫번째 작업을 대기 큐(작업시간 기준 오름차순 우선순위 큐)에 넣는다

3. 대기 큐가 비지 않았을 동안

-- 3-1. 1순위 작업을 꺼내서 실행

-- 3-2. 작업이 완료되는 시간을 계산

-- 3-3. 작업이 완료되기 전에 또 다른 작업 요청이 있다면 대기 큐에 삽입

-- 3-4. 만약 작업이 완료되는 동안 작업 요청이이 없었다면 다음 작업을 대기 큐에 삽입

4. 평균값 계산 후 리턴

 

 

CPU 스케쥴링. 이거 정보처리기사나 운영체제 과목 공부하면서 한번씩 배웠던 내용이다

해당 문제에서는 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법을 구하려고 한다.

어떤 스케쥴링 알고리즘을 사용해야 할까?

 

내 생각은 아무래도 대기시간이 포함되다 보니까, 에이징을 포함한 우선순위를 둬서 선택하는 HRN (Highest Response ratio Next) 스케쥴링을 사용하는 것이 맞지 않을까? 싶어서 그걸 적용해봤었다.

--> HRN 스케쥴링의 우선순위 = (대기 시간 + 서비스 시간) / 서비스 시간. 대서서 ㅋㅋ 정처기 준비 할 떄 많이 외운 것.

 

근데 아쉽게도 이 방법으로는 정답을 구하지 못했다.. 

 

이 문제에서 사용해야 하는 스케쥴링 알고리즘은 SJF 스케쥴링이다.

그냥 해당 시점에서 대기 큐에 담겨있는 작업 중 처리시간이 가장 짧은 작업을 선택하는 것이다.

(실제 상황에서는 작업이 얼마나 걸릴지를 예상할 수 없기에 현실적으로 SJF 스케줄링을 사용하는 것이 어렵다. 하지만 이 문제에서는 작업 시간을 미리 알 수 있기 때문에 구현이 가능하다!)

 

 

크게 어려운 것 같지 않으면서도 막상 풀어보려 하면 잘 안풀리는 문제였다.

나중에 다시 한번 복습해 볼 필요가 있겠다..