디스크 컨트롤러

디스크 컨트롤러

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

• 0ms 시점에 3ms가 소요되는 A작업 요청
• 1ms 시점에 9ms가 소요되는 B작업 요청
• 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

• A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
• B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
• C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)
  이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

• A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
• C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
• B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)
  이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한 사항

jobs의 길이는 1 이상 500 이하입니다.
jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입력

[[0, 3], [1, 9], [2, 6]]

출력

9

구현 코드

import java.util.*;
public class Solution {

    public int solution(int[][] jobs) {
                int answer = 0;
                int totalJobLength = 0;

                PriorityQueue<int[]> waitQueue = new PriorityQueue(new Comparator<int[]>() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        return (o1[0]>o2[0]) ? 1 : -1;
                    }
                });

                PriorityQueue<int[]> jobQueue = new PriorityQueue(new Comparator<int[]>() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        return (o1[1]>o2[1]) ? 1 : (o1[1]<o2[1]) ? -1 : ((o1[0] > o2[0]) ? 1:-1);
                    }
                });

                for (int i = 0; i < jobs.length; i++) {
                    waitQueue.add(jobs[i]);
                }

                while (!waitQueue.isEmpty()) {
                    while (!waitQueue.isEmpty() &&waitQueue.peek()[0] <= totalJobLength) {
                        jobQueue.offer(waitQueue.poll());
                    }

                    if (!jobQueue.isEmpty()) {
                        int[] job = jobQueue.poll();
                        totalJobLength += job[1];
                        answer += totalJobLength - job[0];
                    } else {
                        totalJobLength++;
                    }
                }
                //하나가 비어서 다시 돌림
                while (!jobQueue.isEmpty()) {
                    int[] job = jobQueue.poll();
                    totalJobLength += job[1];
                    answer += totalJobLength - job[0];
                }

                return answer / jobs.length;
    }
}

이 문제는 스케쥴링 알고리즘 중 하나인 SJF 알고리즘 문제라고 한다.

SJF(Shortest Job First)

• 준비 큐에서 가장 짧은 (CPU 요구량이 적은) 프로세스에게 CPU 할당.
• starvation 발생 가능, aging 기법으로 해결
• 실행 전에는 실행 시간을 알 수 없다. 지수 평균 방법을 통해 추측한다.

정말 오래걸렸다... 분명 운영체제 시간에 배웠던 처리방식인데 기억이 안나서 어떻게 풀어야할지 생각을 오래했음.. 이문제만 약 이틀정도 고민한듯.

처음에 짠 알고리즘은 기존에 처리하는 작업이 있을 경우, 새로운 작업을 작업큐에 넣을 때 기준을 현재 처리하는 작업의 작업 길이보다 요청시간이 작은 작업을 작업큐에 넣도록 하고, 작업길이가 짧은 순으로 들어가도록하였는데 이러면 테스트케이스는 맞으나 제출시에 아주 많은 실패를 겪게된다...
또한 시간을 계산할때 [(이전 작업 작업길이 - 현재 작업 요청시간) + 작업 길이 +..+ 현재 작업 길이] 이런식으로 계산을 했음. 아주 큰 실패 요인..

수정한 버전은 현재 처리하는 작업 길이 기준으로 작업큐에 넣는게 아닌 현재까지 처리한 totalLength를 계속 계산하여 totalLength보다 작은 경우 작업큐에 넣도록 하였다. 또한 작업큐가 비어 있는 경우에 totalLength를 증가시켜주었다.(현재시간 개념으로 생각)
기존에는 작업큐에 모든 작업을 모두 넣은 다음 반복문을 돌리면서 시간을 계산하였는데, 기존에 이미 totalLength가 계산된 상태에서 다시 계산하려니까 코드도 복잡하고 답도 안맞았다. 그래서 아예 작업을 처리해줄때 답을 계산하도록 하였다.

• 알고리즘

  작업 큐 기준 - 작업시간이 짧은 순 (작업시간 같을 경우 요청시간 짧은 순)
  대기 큐 기준 - 요청시간 짧은 순
  대기큐에 모두 넣기
  대기큐가 없어질때까지 while
  대기큐에서 하나씩 빼기
  요청시간이 현재시간(totallength) 이하인 작업을 while문 돌면서 모두 작업 큐에 저장.
  작업큐에 작업 있는 경우 -> 작업 뺌 & 답 계산
  (계산 공식 : totalLength - 요청시간)
  작업큐에 작업 없는 경우 -> 시간 증가

+ 2021년 8월 프로그래머스 복습겸 다시 푼 풀이

package Problem.힙;

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LV3_디스크컨트롤러_sol2 {
    public static void main(String[] args) {
        int[][] jobs = {{0, 3}, {1, 9}, {2, 6}};
        int answer = solution(jobs);
        System.out.println(answer);
    }

    static int solution(int[][] jobs) {
        int answer = 0;
        PriorityQueue<Job> waitQueue = new PriorityQueue<>(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                return o1.requestTime - o2.requestTime;
            }
        });
        PriorityQueue<Job> jobQueue = new PriorityQueue<>(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                return o1.workTime - o2.workTime;
            }
        });

        for(int i=0;i<jobs.length;i++){
            waitQueue.add(new Job(jobs[i][0],jobs[i][1]));
        }

        int now = 0; //현재 시간
        int cnt = 0; //처리한 작업 개수
        while(cnt<jobs.length){
            while(!waitQueue.isEmpty() && waitQueue.peek().requestTime <= now){
                jobQueue.add(waitQueue.poll());
            }

            System.out.println("now: "+now);
            if(!jobQueue.isEmpty()){
                Job job = jobQueue.poll();
                now += job.workTime;
                answer += now - job.requestTime;
                cnt++;
            }
            else{
                now++;
            }
        }

        answer = answer/ cnt;
        return answer;
    }

    static class Job{
        int requestTime;
        int workTime;
        public Job(int request, int work){
            this.requestTime = request;
            this.workTime = work;
        }
    }
}

참고

조건부 연산자
디스크 컨트롤러 자바

코딩 후 참고한 개념자료 : https://junboom.tistory.com/24