プログラマディスクコントローラ

🔗 質問リンク

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

🤔 質問する

HDDは一度に1台しか処理できません.ディスクコントローラを実装する方法はいくつかあります.最も一般的な方法は、リクエストの受信順序に従って処理することである.
例:

`0 ms時点3ミリ秒のA要求

Bジョブ要求

ミリ秒(

ミリ秒)

C要求「

ミリ秒時6ミリ秒」

受け取った要求は同じです.下図のように.

一度に1つのリクエストしか実行できないため、各タスクをリクエストの順序で処理する場合:

`A:3ミリ秒(リクエストから終了まで:3ミリ秒)

B:1 ms待機開始、3 ms動作開始、12 ms完了(リクエストから終了:11 ms)

C:2ミリ秒から待機、12ミリ秒から動作、18ミリ秒で終了(リクエストから終了まで:16ミリ秒)`

各タスクの要求から終了までの平均時間は10ミリ秒(=(3+11+16)/3)である.
でもA→C→B順に処理すると

`A:3ミリ秒(リクエストから終了まで:3ミリ秒)

C:2ミリ秒～2ミリ秒、3ミリ秒～9ミリ秒、7ミリ秒～

B:1 ms待機開始、9 ms動作開始、18 ms完了(リクエストから終了まで:17ミリ秒)`

A→C→Bの順に処理すると,各タスクの要求から終了までの平均時間は9 ms(=(3+7+17)/3)となる.
各タスクについて、「要求タスクの時点、タスク所要時間」を含む2 Dタイルジョブをパラメータとして指定した場合は、要求から終了までのタスクの平均値を最小限に抑えるためのソルバを作成します.(ただし小数点以下)

📌 せいげんじょうけん

作業の長さは500を超えない.

ジョブの各ローは、単一のタスクの[タスクを要求する時間、タスクに必要な時間]です.

各タスクの要求時間は1000時間を超えない.

各操作について、

の所要時間は1000時間を超えない.

HDDが動作していない場合は、リクエストのタスクを先に処理してください.

😮 トラブルシューティング方法

ディスクコントローラの問題は、オペレーティングシステムのスケジューリング方法の1つであるSJF(Shortest Job First)方法の非線形プリエンプト方法と同じです.
したがって、ディスクが作業中に他の短いタスクに遭遇した場合でも、処理を先に行い、次の短いタスクを実行します.
したがって、ディスクコントローラのトラブルシューティングのポイントは、ジョブの並べ替えの開始時間と優先キューを比較するときに、経過した時間順にキューに挿入することです.

static class Disk implements Comparable<Disk> {
        private int start;      //시작 시간
        private int elapsed;    //경과 시간

        public Disk(int start, int elapsed) {
            this.start = start;
            this.elapsed = elapsed;
        }

        public int getStart() {
            return start;
        }

        public int getElapsed() {
            return elapsed;
        }

        // 경과 시간이 짧은 순서로 힙에 넣어줌
        @Override
        public int compareTo(Disk o) {
            if (this.elapsed < o.elapsed) return -1;
            else if (this.elapsed > o.elapsed) return 1;
            return 0;
        }
    }

開始時間と経過時間を変数とするディスククラスを作成します.ディスククラスの実装は、競合インタフェースを短い時間の順序でキューに入れることです.{{4, 9},{5, 6},{1, 1}}要素を有するジョブ配列を例示する.
まず、この配列の開始時間である4、5、1を並べ替えます.(開始時間が短い){{1, 1},{4, 9},{5, 6}}でソートを終了した後、優先順位キューに最初に開始したジョブを入れる.
タスクが完了した後に注意しなければならないのは、現在のタスクが完了したときにまだ開始していないタスクが1つもない場合、最初に要求されたタスクが実行されます.
したがって、クエリー条件にキューがない場合、またはジョブに残りのジョブがある場合は、繰り返しを続行する条件を指定します.1秒開始のタスクは1秒後の2秒で終了しますが、次のタスクは4秒で開始します.まだタスクがあるので、キューが空であってもwhile文にアクセスし続けます.

//큐가 empty가 아니거나 아직 작업이 큐에 다 들어가지 않은 경우
while (!pq.isEmpty() || list.size() > 0) {

最初のタスクが開始された時点を現在の時間(時間変数)に入れ、タスクが完了するたびに経過した時間を加算すると、進行中のタスクが終了する現在の時間となります.
その後、受信したタスクがキューに残っている場合は、すべてのタスクをキューに入れます.また,タスクを繰り返し実行するとスケジューリングに必要なすべての時間が得られ,タスクの数に応じて割り当てられると平均作業時間が得られ,返されると問題が解決される.
次はJavaで実装されたコードです.

🚩 JAVAコード

package com.algorithm.Programmers.Lv3;

import java.util.*;

public class Solution_42627 {
    static class Disk implements Comparable<Disk> {
        private int start;      //시작 시간
        private int elapsed;    //경과 시간

        public Disk(int start, int elapsed) {
            this.start = start;
            this.elapsed = elapsed;
        }

        public int getStart() {
            return start;
        }

        public int getElapsed() {
            return elapsed;
        }

        // 경과 시간이 짧은 순서로 힙에 넣어줌
        @Override
        public int compareTo(Disk o) {
            if (this.elapsed < o.elapsed) return -1;
            else if (this.elapsed > o.elapsed) return 1;
            return 0;
        }
    }

    public static void main(String[] args) {
        int[][] jobs = {{1, 1}, {4, 9}, {5, 6}};
        System.out.println(solution(jobs));
    }

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

        PriorityQueue<Disk> pq = new PriorityQueue<>();

        //Jobs 배열을 시작시간이 빠른 순서로 먼저 정렬
        //시작시간이 동일한 경우 경과 시간이 짧은 순으로 정렬
        Arrays.sort(jobs, (o1, o2) -> {
            if (o1[0] == o2[0])
                return Integer.compare(o1[1], o2[1]);
            else
                return Integer.compare(o1[0], o2[0]);
        });

        LinkedList<Disk> list = new LinkedList<>();
        for (int[] job : jobs)
            list.add(new Disk(job[0], job[1]));

        pq.offer(list.poll());      //가장 빠른 작업 제일 먼저 넣어주기
        int time = pq.peek().getStart();     //가장 빠른 작업 시작시간이 모든 스케줄링 시작 시간

        //time >= start 인 값 큐에 넣기
        //time += elapsed;
        //answer += time - disk.start;
        //큐가 empty가 아니거나 아직 작업이 큐에 다 들어가지 않은 경우
        while (!pq.isEmpty() || list.size() > 0) {
            /*큐가 비었지만 list size가 남은 경우는 (1,1) (4,1)의 경우
             *1초에 시작 2초에 완료, 이후 2초부터 다음 작업 시작시간인 4초까지 작업이 없기 때문에
             *먼저 요청하는 작업 큐에 넣어주기
             */
            if(list.size() > 0 && pq.isEmpty()){
                time = list.peek().getStart();
                pq.offer(list.poll());
                continue;
            }
            Disk disk = pq.poll();
            time += disk.getElapsed();      //경과 시간을 더해주면 작업이 끝난 현재 시간

            while (list.size() > 0 && time >= list.peek().getStart()) {
                pq.offer(list.poll());      //현재 시간보다 전에 요청 받은 작업 큐에 넣어주기
            }
            answer += time - disk.getStart();   //현재 시간부터 요청 시작 시간을 빼주면 요청부터 작업 완료까지의 시간
        }

        return answer / jobs.length;
    }
}

📄 整理する

これは、

オペレーティングシステムスケジューリング技術SJF技術において非プリプロセッシング(非線形)方式が用いられる問題である.スケジューリングテクニックを身につけて、問題解決に役立つようです.スケジューリングテクニックを考え直すきっかけにもなった.

配列は近づきにくいため,コードを実現するためのリストが生成され,配列にパラメータが与えられているため,このパラメータ内で解決する方法を育成する必要があると考えられる.