[우선순위큐] 디스크 컨트롤러

이진 힙, 즉 우선순위 큐를 통해 최솟값을 산출하여 푸는 문제이다.

이진 트리, 이진 힙 부분들을 까먹고 있는 부분이 많아서 다시 복습도 하였다.

우선순위 큐는 의외로 쉽게 구현되었던 반면에 

문제 조건에 알맞게 루프의 조건을 잡아주는 것이 매우 헷갈려서 굉장히 오래걸렸다.

 

조건 

1. 한 번에 하나의 작업만 수행

2. 작업을 수행하지 않을 때는 먼저 요청이 들어온 작업부터 수행

3. jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 

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

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.

• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.

• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

반환값: 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리할 때의 평균

 

디스크 스케줄러 알고리즘의 요약은

"작업이 실행되고 있을 시점에 요청이 들어온 다른 여러 작업들 중 소요시간이 가장 적은 것을 선택한다"이다.

실행시간은 어떠한 순서로 하든지 모두 같고, 시간을 줄이기 위해서는 대기 시간을 줄여야한다. 소요시간이 많은 것을 먼저 실행하면 타 작업의 대기 시간이 길어진다. 또한 작업은 모두 이전 작업이 끝나는 시점에서 시작하기 때문에, 다시 말하면 모든 대기 작업이 실행할 수 있는 타이밍은 같기 때문에 먼저 도착한 작업의 대기시간이 오래 걸릴까봐 걱정할 필요도 없다. 

 

따라서 작업 소요시간의 최소값을 구하기 위해 우선순위 큐를 먼저 구현한다.

기본적인 배열에 대한 우선순위 큐는 다음과 같이 구현할 수 있다. 최소힙의 경우이다. 

let que = []; 

function enque(item) {
  que.push(item);
}

function deque() {
  let entry = 0;

  que.forEach((item, index) => {
    if (que[entry][1] > que[index][1]) {
      entry = index;
    }
  });

  return que.splice(entry, 1);
}

예시1)

 

본격적으로 문제 해결을 위한 단계를 거친다. 

먼저 요청 받은 순서대로 입력값이 들어와있는지 확실히 하기 위해 요청받은 시간 순서대로 정렬한다.

 //요청받은 순서대로 정리
    jobs.sort((a, b) => a[0] - b[0]);

예시2)

 

또한 작업이 실행하고 있는 동안 요청 받은 작업들을 모두 큐에 넣는다. 

let idx = 0;
let len = jobs.length;
let curtime = 0;

while( idx < len && jobs[idx][0] <= curtime){
        enque(jobs[idx++])
}

예시3)

 

이 코드에서 주의할 점은 idx++이다. jobs 배열과 우선순위 큐는 다르기 때문에 나중에 우선순위 큐에서 꺼내 쓴다고 해서 jobs 배열에서 사라지는 것은 아니다. 그러나 한 번 큐에 넣은 jobs 요소는 다시 넣으면 안 되기 때문에 idx로 관리한다.

큐에 넣은 것들 중 실행할 작업을 선택하는 과정은 다음과 같다. 

curtime은 현재시간으로 시점이고 answer은 duration 즉 시간이다.

if(que.length ===  0){
	curtime = jobs[idx][0];
}
else{
	let job = deque()["0"];
	answer += curtime - job[0] + job[1]
	curtime += job[1];
}

 

위의 두 과정(실행 중 요청 작업 큐에 넣기, 실행시간 최소 작업 선택)을 ( idx < len || que.length > 0) 일 때까지 반복한다. idx가 jobs의 길이보다 작거나 큐가 아직 남아있을 때까지 반복하는 것이다. 위의 과정을 정리하면 이러하다 

    while(idx < len || que.length > 0){
    
      //실행 시 요청 처리했던 작업들의 큐
      // 요청처리 했던 것은 다시 요청하지 않음
      while( idx < len && jobs[idx][0] <= curtime){
        enque(jobs[idx++])
      }
      
      if(que.length ===  0){
        curtime = jobs[idx][0];
      }
      else{
        let job = deque()["0"];
        answer += curtime - job[0] + job[1]
        curtime += job[1];
      }

    }

예시4)

 

처음에는 for 문을 통해 job의 개수에 따라 반복하면 어떨까 싶었다. 예를 들어 job이 4개일 때 4번 반복하는 식이다. 그렇게 하면 성능 문제가 아닌 아예 정확성까지 영향을 준다. 예시3을 여러 번 반복하게 되는 문제가 생긴다. 

 

마지막으로 이렇게 나온 값을 평균값을 구하기 위해 배열 개수로 나누어주면 답이 나오게 된다.

return Math.floor(answer/len)

예시5)