【作業系統】代碼實踐：先來先服務排程算法（FCFS），短程序優先排程算法（SJF），高響應比優先排程算法（HRRN）

文章目錄

• ​​一、實驗需求​​
• ​​二、需求分析​​
• ​​三、效果展示​​

• ​​（1）FCFS 排程算法​​
• ​​（2）SJF 排程算法​​
• ​​（3）HRRN 排程算法​​
• ​​（4）綜合對比​​

• ​​四、具體代碼​​

一、實驗需求

設計一個有N個程序的程序排程程式，實作先來先服務排程算法，

，短程序優先排程算法，動态最高優先數優先排程算法。

二、需求分析

程序對象的資訊抽象成此PCB類

為PCB類編寫常用Getter/Setter，構造方法（利用random随機數實作程序實際情況中的随機性），并模拟實作程序運作及阻塞時對應時間屬性值的動态變化（自減1）等等。

1、FCFS算法最容易實作，是以隻需判斷目前時間time的值，是否等于程序式列中的第一個程序的到達時間即可，并不斷輸出目前時間和程序執行情況，例如其執行時間和剩餘時間，最後再提示程序執行完畢，并輸出周轉時間，在序列中删除此程序結點等等。

2、其次是SJF算法，此算法需額外設定一個就緒程序式列，根據目前time值，将已經達到執行開始時間的程序放入程序的就緒隊列，并删除在原程序式列中的此程序結點，模拟程序的狀态變化與多隊列機制，當就緒隊列中有程序且數量不為一個時，則對此就緒隊列的程序按照程序執行時間從小到大排序，并記錄此次最優先程序（即最短程序的pid），則在下輪進行就緒程序隊列的排序時，便可根據第一個隊列中程序結點的pid是否為之前記錄的pid得知程序是否被搶占，進而輸出提示資訊，進而輸出其他資訊。

3、最後，相對較麻煩的是HRRN算法，此算法，與SJF算法的實作類似，主要差別是，将SJF算法中就緒程序隊列的排序依據，從程序執行時間最短，轉為程序優先級最高，并額外再增加一個程序阻塞隊列（根據實驗要求），而阻塞隊列也是根據阻塞的開始時間，與阻塞的過程時間來與目前time時間值進行判斷的，是以，在SJF算法的基礎上，HRRN算法的實作也就變的不再相對複雜，是以一開始聲明的HRRN的複雜是相對于從0開始編寫的複雜性。

三、效果展示

具體執行結果如下：

（1）FCFS 排程算法

（2）SJF 排程算法

（3）HRRN 排程算法

（還為實作完整，這隻是簡單的優先級排程算法，優先數不具有動态變化性）

（内容較多，隻截取部分）

（4）綜合對比

四、具體代碼

class PCB {
    private int pid; // 程序id
    private int priority; // 程序優先級
    private int arrTime; // 到達時間
    private int allTime; // 還需運作時間
    private int cpuTime; // 已運作時間
    private int startBlockTime; // 開始阻塞時間
    private int blockTime; // 阻塞時間
    private String state; // 狀态

    public PCB(int pid, int priority, int arrTime, int allTime, int cpuTime, int startBlockTime, int blockTime, String state) {
        this.pid = pid;
        this.priority = priority;
        this.arrTime = arrTime;
        this.allTime = allTime;
        this.cpuTime = cpuTime;
        this.startBlockTime = startBlockTime;
        this.blockTime = blockTime;
        this.state = state;
    }

    public int getPid() {
        return pid;
    }

    public void setPid(int pid) {
        this.pid = pid;
    }

    public int getPriority() {
        return priority;
    }

    public void setPriority(int priority) {
        this.priority = priority;
    }

    public int getArrTime() {
        return arrTime;
    }

    public void setArrTime(int arrTime) {
        this.arrTime = arrTime;
    }

    public int getAllTime() {
        return allTime;
    }

    public void setAllTime(int allTime) {
        this.allTime = allTime;
    }

    public int getCpuTime() {
        return cpuTime;
    }

    public void setCpuTime(int cpuTime) {
        this.cpuTime = cpuTime;
    }

    public int getStartBlockTime() {
        return startBlockTime;
    }

    public void setStartBlockTime(int startBlockTime) {
        this.startBlockTime = startBlockTime;
    }

    public int getBlockTime() {
        return blockTime;
    }

    public void setBlockTime(int blockTime) {
        this.blockTime = blockTime;
    }

    public String getState() {
        return state;
    }

    public void setState(String state) {
        this.state = state;
    }

    /**
     * HRRN 執行情況模拟
     */
    public void show_HRRN() {
        System.out.println("程序:" + pid +
                        " 優先級:" + priority +
                        " 到達時間:" + arrTime +
                        " 還需運作時間:" + allTime +
                        " 已運作時間:" + cpuTime +
                        " 開始阻塞時間:" + startBlockTime +
                        " 阻塞時間:" + blockTime +
                        " 狀态:" + state);
    }

    /**
     * SJF FCFS 執行情況模拟
     */
    public void show_SJF_FCFS() {
        System.out.println("程序:" + pid +
                "正在執行，到達時間:" + arrTime +
                " 還需運作時間:" + allTime +
                " 已運作時間:" + cpuTime);
    }

    public void toBlock() {
        state = "Block";
    }

    public void toRun() {
        state = "Run";
    }

    public void toFinish() {
        state = "Finish";
    }

    public void toReady() {
        state = "Ready";
    }

    public void running() { // 程序運作時的狀态變化
        allTime -= 1;
        cpuTime += 1;
    }

    public void toStartBlock() { // 程序将要開始阻塞時的狀态變化
        if (startBlockTime > 0) {
            startBlockTime -= 1;
        }
    }

    public void blocking() { // 程序阻塞時的狀态變化
        if (blockTime > 0) {
            blockTime -= 1;
        }
        priority += 1;
    }
}

public class Main {
    /**
     * 初始化程序，生成四個程序并按到達時間講它們放入清單 list
     * @param num
     */
    public static List<PCB> init(int num) {
        List<PCB> list = new ArrayList<PCB>();
        for (int i = 0; i < num; i++) {
            // 構造參數：程序id，優先級，到達時間，還需運作時間，
            // 已運作時間，開始阻塞時間，阻塞時間，狀态
            list.add(new PCB(i, random(1, 10), random(1, 15), random(1, 10),
                    0, random(5, 10), random(1, 10), "Ready"));
        }

        // 将各程序按 到達時間 從小到大排列
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i).getArrTime() > list.get(j).getArrTime()) {
                    PCB temp = list.get(i);
                    list.set(i, list.get(j));
                    list.set(j, temp);
                }
            }
        }
        return list;
    }

    public static int random(int m, int n) {
        Random random = new Random();
        return (int) Math.round(random.nextDouble() * n) + m;
    }

    /**
     * 先來先服務算法
     * @param list
     */
    public static int FCFS(List<PCB> list) {
        int time = 0;
        while (true) {
            System.out.println("time: " + time);
            PCB pcb = list.get(0);
            if (time >= pcb.getArrTime()) {
                pcb.running();
                pcb.show_SJF_FCFS();
                if (pcb.getAllTime() == 0) {
                    System.out.println("程序" + pcb.getPid() + "執行完畢，周轉時間:" +
                            (time - pcb.getArrTime()) + "\n");
                    list.remove(list.get(0));
                }
            }
            time += 1;
            if (list.size() == 0) {
                return --time;
            }
        }
    }

    /**
     * 搶占式短作業優先
     * @param list
     */
    public static int SJF(List<PCB> list) {
        List<PCB> readyList = new ArrayList<PCB>(); // 就緒隊列
        int time = 0;
        int pid = 0;
        while (true) {
            int readyListLength = readyList.size();
            System.out.println("time: " + time);

            if (list.size() > 0) {
                int i = 0;
                while (true) { // 将程序放入就緒隊列，就緒隊列的第一個是正在執行的程序
                    if (time == list.get(i).getArrTime()) {
                        readyList.add(list.get(i));
                        list.remove(list.get(i));
                        pid = readyList.get(0).getPid(); // 擷取就緒隊列第一個程序的ID
                        i -= 1;
                    }
                    i += 1;
                    if (i >= list.size()) {
                        break;
                    }
                }
            }

            if (readyList.size() >= 2 && readyList.size() != readyListLength) { // 判斷就緒隊列中最短的作業
                readyListLength = readyList.size();
                for (int i = 0; i < readyList.size() - 1; i++) {
                    for (int j = i + 1; j < readyList.size(); j++) {
                        if (readyList.get(i).getAllTime() > readyList.get(j).getAllTime()) {
                            PCB temp = readyList.get(i);
                            readyList.set(i, readyList.get(j));
                            readyList.set(j, temp);
                        }
                    }
                }
            }

            if (readyList.size() > 0) { // 執行程序
                if (pid != readyList.get(0).getPid()) { // 如果正在執行的程序改變，則發送搶占
                    System.out.println("發生搶占，程序" + readyList.get(0).getPid() + "開始執行");
                    pid = readyList.get(0).getPid();
                }
                readyList.get(0).running();
                readyList.get(0).show_SJF_FCFS();
                if (readyList.get(0).getAllTime() == 0) {
                    System.out.println("程序" + readyList.get(0).getPid() + "執行完畢，周轉時間：" + (time - readyList.get(0).getArrTime() + 1));
                    readyList.remove(readyList.get(0));
                    if (readyList.size() > 0) {
                        pid = readyList.get(0).getPid();
                    }
                }
            }
            time += 1;
            if (readyList.size() == 0 && list.size() == 0) {
                break;
            }
        }
        return --time;
    }

    public static int HRRN(List<PCB> list) { // 動态最高優先數優先
        List<PCB> readyList = new ArrayList<PCB>(); // 就緒隊列
        List<PCB> blockList = new ArrayList<PCB>(); // 阻塞隊列
        int time = 0;
        int pid = 0;
        while (true) {
            System.out.println("time: " + time);
            if (list.size() > 0) {
                int i = 0;
                while (true) { // 将程序放入就緒隊列
                    if (time == list.get(i).getArrTime()) {
                        readyList.add(list.get(i));
                        list.remove(list.get(i));
                        pid = readyList.get(0).getPid();
                        i -= 1;
                    }
                    i += 1;
                    if (i >= list.size()) {
                        break;
                    }
                }
            }

            for (int i = 0; i < readyList.size() - 1; i++) { // 将就緒隊列的程序按優先級大小排列
                for (int j = i + 1; j < readyList.size(); j++) {
                    if (readyList.get(i).getPriority() < readyList.get(j).getPriority()) {
                        readyList.get(i).toReady();
                        PCB temp = readyList.get(i);
                        readyList.set(i, readyList.get(j));
                        readyList.set(j, temp);
                    }
                }
            }

            if (readyList.size() > 0) { // 執行過程
                if (pid != readyList.get(0).getPid()) {
                    System.out.println("發生搶占，程序" + readyList.get(0).getPid() + "開始執行");
                    pid = readyList.get(0).getPid();
                }
                if (readyList.get(0).getStartBlockTime() > 0 || readyList.get(0).getBlockTime() <= 0) {
                    readyList.get(0).toRun();
                    readyList.get(0).running();
                    readyList.get(0).toStartBlock();
                }
                for (int i = 1; i < readyList.size(); i++) {
                    readyList.get(i).setPriority(readyList.get(i).getPriority() + 1);
                    readyList.get(i).toStartBlock();
                }
            }

            if (blockList.size() > 0) { // 阻塞隊列
                blockList.forEach(pcb -> {
                    pcb.blocking();
                });
            }

            readyList.forEach(pcb -> {
                pcb.show_HRRN();
            });

            blockList.forEach(pcb -> {
                pcb.show_HRRN();
            });

            if (readyList.size() > 0) { // 當程序開始阻塞事件為0，将程序放入阻塞隊列
                int i = 0;
                while (true) {
                    if (readyList.size() > 0) {
                        if (readyList.get(i).getStartBlockTime() == 0 && readyList.get(i).getBlockTime() != 0) {
                            System.out.println("程序" + readyList.get(i).getPid() + "開始阻塞，進入阻塞隊列");
                            readyList.get(i).toBlock();
                            blockList.add(readyList.get(i));
                            readyList.remove(readyList.get(i));
                            i -= 1;
                        }
                    }
                    i += 1;
                    if (i >= readyList.size()) {
                        break;
                    }
                }
            }

            if (blockList.size() > 0) {
                int i = 0;
                while (true) {
                    if (blockList.get(i).getBlockTime() == 0) {
                        System.out.println("程序" + blockList.get(i).getPid() + "阻塞結束，進入就緒隊列");
                        blockList.get(i).toReady();
                        readyList.add(blockList.get(i));
                        blockList.remove(blockList.get(i));
                        pid = readyList.get(0).getPid();
                        i -= 1;
                    }
                    i += 1;
                    if (i >= blockList.size()) {
                        break;
                    }
                }
            }

            if (readyList.size() > 0) { // 程序執行完畢則移出就緒隊列
                if (readyList.get(0).getAllTime() <= 0) {
                    readyList.get(0).toFinish();
                    System.out.println("程序" + readyList.get(0).getPid() + "執行完畢，周轉時間: " +
                            (time - readyList.get(0).getArrTime() + 1) + "，狀态：" + readyList.get(0).getState());
                    readyList.remove(readyList.get(0));
                    if (readyList.size() > 0) {
                        pid = readyList.get(0).getPid();
                    }
                }
            }

            time += 1;
            if (list.size() == 0 && readyList.size() == 0 && blockList.size() == 0) {
                break;
            }
        }
        return --time;
    }

    public static List<PCB> cloneList(List<PCB> list) {
        List<PCB> listClone = new ArrayList<PCB>();
        for (int i = 0; i < list.size(); i++) {
            PCB pcb = list.get(i);
            PCB pcbClone = new PCB(pcb.getPid(), pcb.getPriority(), pcb.getArrTime(), pcb.getAllTime(),
                    pcb.getCpuTime(), pcb.getStartBlockTime(), pcb.getBlockTime(), pcb.getState());
            listClone.add(pcbClone);
        }
        return listClone;
    }

    public static void main(String[] args) {
        while (true) {
            System.out.println("請選擇算法：---------------");
            System.out.println("1、先來先服務");
            System.out.println("2、搶占式短作業優先");
            System.out.println("3、動态最高優先數優先");
            System.out.println("4、比較上述三種算法");
            System.out.println("------------------------");
            Scanner reader = new Scanner(System.in);
            System.out.print("請輸入選項：");
            int select = reader.nextInt();
            switch (select) {
                case 1:
                    List<PCB> list = init(4);
                    list.forEach(pcb -> {
                        pcb.show_SJF_FCFS();
                    });
                    FCFS(list);
                    break;
                case 2:
                    List<PCB> list2 = init(4);
                    list2.forEach(pcb -> {
                        pcb.show_SJF_FCFS();
                    });
                    SJF(list2);
                    break;
                case 3:
                    List<PCB> list3 = init(4);
                    list3.forEach(pcb -> {
                        pcb.show_HRRN();
                    });
                    HRRN(list3);
                    break;
                case 4:
                    int time_FCFS = 0;
                    int time_SJF = 0;
                    int time_HRRN = 0;
                    List<PCB> list4 = init(4);
                    if (list4.size() > 0) {
                        List<PCB> list4_1 = cloneList(list4);
                        List<PCB> list4_2 = cloneList(list4);
                        List<PCB> list4_3 = cloneList(list4);
                        List<PCB> list4_all = cloneList(list4);
                        System.out.println("**************FCFS******************");
                        for (int i = 0; i < list4_1.size(); i++) {
                            list4_1.get(i).show_SJF_FCFS();
                        };
                        time_FCFS = FCFS(list4_1);
                        System.out.println("********************************");

                        System.out.println("****************SJF****************");
                        for (int i = 0; i < list4_2.size(); i++) {
                            list4_2.get(i).show_SJF_FCFS();
                        };
                        time_SJF = SJF(list4_2);
                        System.out.println("********************************");

                        System.out.println("*****************HRRN***************");
                        for (int i = 0; i < list4_3.size(); i++) {
                            list4_3.get(i).show_HRRN();
                        };
                        time_HRRN = HRRN(list4_3);
                        System.out.println("********************************");

                        System.out.println("=================情況綜述======================");
                        System.out.println("=======程序情況========");
                        for (int i = 0; i < list4_all.size(); i++) {
                            list4_all.get(i).show_HRRN(); // 此方法的程序列印資訊最全
                        };
                        System.out.println("FCFS 算法執行時間：" + time_FCFS);
                        System.out.println("SJF 算法執行時間：" + time_SJF);
                        System.out.println("HRRN 算法執行時間：" + time_HRRN);
                        System.out.println("=======================================");
                    }
                    break;
            }
        }
    }
}