模擬處理器調度

一、實習內容

選擇一個調度演算法，實現處理器調度。

二、實習目的

在採用多道程式設計的系統中，往往有若幹個進程同時處於就緒狀態。當就緒進程個數大於處理器數時，就必須依照某種策略來決定哪些進程優先占用處理器。本實習模擬在單處理器情況下的處理器調度，幫助學生加深瞭解處理器調度的工作。

三、實習題目

本實習有兩個題，學生可選擇其中的一題做實習。

第一題：設計一個按優先數調度演算法實現處理器調度的程式。

[提示]：

(1) 假定系統有五個進程，每一個進程用一個進程式控制制塊PCB來代表，進程式控制制塊的格式為：

其中，進程名——作為進程的標識，假設五個進程的進程名分別為P₁，P₂，P₃，P₄，P₅。

指針——按優先數的大小把五個進程連成隊列，用指針指出下一個進程的進程式控制制塊的首地址，最後一個進程中的指針為“0”。

要求運行時間——假設進程需要運行的單位時間數。

優先數——賦予進程的優先數，調度時總是選取優先數大的進程先執行。

狀態——可假設有兩種狀態，“就緒”狀態和“結束”狀態。五個進程的初始狀態都為“就緒”，用“R”表示，當一個進程運行結束後，它的狀態為“結束”，用“E”表示。

(2) 在每次運行你所設計的處理器調度程式之前，為每個進程任意確定它的“優先數”和“要求運行時間”。

(3) 為了調度方便，把五個進程按給定的優先數從大到小連成隊列。用一單元指出隊首進程，用指針指出隊列的連接情況。例：

  隊首標誌

         K₂   

(4) 處理器調度總是選隊首進程運行。採用動態改變優先數的辦法，進程每運行一次優先數就減“1”。由於本實習是模擬處理器調度，所以，對被選中的進程並不實際的啟動運行，而是執行：

優先數-1

要求運行時間-1

來模擬進程的一次運行。

提醒註意的是：在實際的系統中，當一個進程被選中運行時，必須恢復進程的現場，讓它占有處理器運行，直到出現等待事件或運行結束。在這裡省去了這些工作。

(5) 進程運行一次後，若要求運行時間¹0，則再將它加入隊列（按優先數大小插入，且置隊首標誌）；若要求運行時間=0，則把它的狀態修改成“結束”（E），且退出隊列。

(6) 若“就緒”狀態的進程隊列不為空，則重覆上面（4）和（5）的步驟，直到所有進程都成為“結束”狀態。

(7) 在所設計的程式中應有顯示或列印語句，能顯示或列印每次被選中進程的進程名以及運行一次後進程隊列的變化。

(8) 為五個進程任意確定一組“優先數”和“要求運行時間”，啟動所設計的處理器調度程式，顯示或列印逐次被選中進程的進程名以及進程式控制制塊的動態變化過程。

package System;

public class Pcb{
    private String name;    //進程名
    private int time;       //進程時間
    private int priorty;    //優先數;
    private String status;  //狀態
    private Pcb pointer;    //指針

    public Pcb(String name, int time, int priorty, String status, Pcb pointer) {
        this.name = name;
        this.time = time;
        this.priorty = priorty;
        this.status = status;
        this.pointer = pointer;
    }
    public Pcb(){}
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public Pcb getPointer() {
        return pointer;
    }
    public void setPointer(Pcb pointer) {
        this.pointer = pointer;
    }
    public int getTime() {
        return time;
    }
    public void setTime(int time) {
        this.time = time;
    }
    public int getPriorty() {
        return priorty;
    }
    public void setPriorty(int priorty) {
        this.priorty = priorty;
    }
    public String getStatus() {
        return status;
    }
    public void setStatus(String status) {
        this.status = status;
    }

    //顯示進程
    public void show() {
        System.out.println("進程" + name + ", 指針->" + pointer.getName() + ", 進程時間=" + time + "," +
                " 優先數=" + priorty+ ", 狀態=" + status );
    }
}

package System;

import java.util.Iterator;
import java.util.LinkedList;


public class Operate {
    LinkedList<Pcb> TotalPcb =new LinkedList<Pcb>();  //創建存儲PCB的隊列
    Pcb nullPcb = new Pcb("0", 0, 0, "E", null);//創建一個空PCB對象

    //創建PCB進程
    public void CreatePcb(int n){
        for(int i=1;i<=n;i++){
            Pcb pcb=new Pcb();
            pcb.setName("p"+i);
            int priorty=(int)(Math.random()*10);    //產生隨機優先數
            int time=(int)(Math.random()*10)+1;        //產生隨機時間數
            pcb.setPriorty(priorty);
            pcb.setTime(time);
            pcb.setPointer(nullPcb);
            pcb.setStatus("R");
            TotalPcb.add(pcb);
        }
    }

    //顯示PCB隊列
    public void showPcb(){
        Iterator<Pcb> p=TotalPcb.iterator();
        while(p.hasNext()){
            Pcb pcb=p.next();
            pcb.show();
        }
        System.out.println();
    }

    //刪除PCB隊列中運行結束的進程
    public void remove(){
        for(int i=0;i<TotalPcb.size();i++){
            if(TotalPcb.get(i).getStatus()=="E"){
                System.out.println(TotalPcb.get(i).getName()+"運行結束,退出隊列");
                TotalPcb.remove(i);
            }
        }
    }

    //運行後優先數-1，時間-1
    public void renew(Pcb p) {
        if (p.getPriorty()>0) {
            p.setPriorty(p.getPriorty()-1);  //優先數-1
        }
        if (p.getTime()>0) {
            p.setTime(p.getTime()-1);        //時間-1
        }
        if (p.getTime()==0){
            p.setStatus("E");            //若時間=0，狀態置E
        }
    }

    //隊列排序
    public void sortPcb() {
        for(int i=0;i<TotalPcb.size();i++) {
            for(int j=i+1;j<TotalPcb.size();j++) {
                if(TotalPcb.get(i).getPriorty()<TotalPcb.get(j).getPriorty()) {
                    //優先數大的先運行
                    Pcb temp=TotalPcb.get(i);
                    TotalPcb.set(i, TotalPcb.get(j));
                    TotalPcb.set(j, temp);
                }else if(TotalPcb.get(i).getPriorty()==TotalPcb.get(j).getPriorty()&&TotalPcb.get(i).getTime()>TotalPcb.get(j).getTime()) {
                    //優先數相同，時間最少的先運行
                    Pcb temp=TotalPcb.get(i);
                    TotalPcb.set(i, TotalPcb.get(j));
                    TotalPcb.set(j, temp);
                }
            }
        }
        //進程指針指向下一個進程
        for (int k =0;k<TotalPcb.size()-1; k++) {
            TotalPcb.get(k).setPointer(TotalPcb.get(k+1));
        }
        //最後一個進程指向為0
        if(TotalPcb.size()!=0){
            TotalPcb.get(TotalPcb.size()-1).setPointer(nullPcb);
        }
    }

    //進程運行
    public void run(){
        sortPcb();   //排序
        System.out.println("********************************************************");
        while(TotalPcb.size()!=0){
            System.out.println("運行前進程隊列：");
            showPcb();  //顯示隊列
            System.out.println(TotalPcb.get(0).getName()+"進程運行，運行時間-1，優先順序-1");
            renew(TotalPcb.get(0));
            System.out.print(TotalPcb.get(0).getName()+"進程運行之後:");
            TotalPcb.get(0).show();
            remove();  //刪除PCB隊列中運行結束的進程
            sortPcb();
            System.out.println("\n運行後進程隊列：");
            showPcb();
            System.out.println("********************************************************");
        }
        System.out.println("所有進程已運行完畢");

    }
}

package System;

        import java.util.Scanner;

public class Test
{
    public static void main(String[] args) {
        Scanner input =new Scanner(System.in);
        Operate op=new Operate();
        System.out.print("請輸入進程數:");
        op.CreatePcb(input.nextInt());
        op.run();
    }
}