說明：用高級語言撰寫和除錯一個行程調度程式，以加深對行程的概念及行程調度演算法的理解，
原理：
（1）行程的狀態
（2）行程的結構——PCB
行程都是由一系列操作(動作)所組成，通過這些操作來完成其任務，因此，不同的行程，其內部操作也不相同，在作業系統中，描述一個行程除了需要程式和私有資料之外，最主要的是需要一個與動態程序相聯系的資料結構，該資料結構用來描述行程的外部特性(名字、狀態等)以及與其它行程的聯系(通信關系)等資訊，該資料結構稱為行程控制塊(PCB，Process Control Block)，
行程控制塊PCB與行程一一對應，PCB中記錄了系統所需的全部資訊、用于描述行程情況所需的全部資訊和控制行程運行所需的全部資訊，因此，系統可以通過行程的PCB來對行程進行管理，
（3）演算法
設計一個有 N個行程共行的行程調度程式，
行程調度演算法：采用最高優先數優先的調度演算法（即把處理機分配給優先數最高的行程）和先來先服務演算法，每個行程有一個行程控制塊（ PCB）表示，行程控制塊可以包含如下資訊：行程名、優先數、到達時間、需要運行時間、已用CPU時間、行程狀態等等， 行程的優先數及需要的運行時間可以事先人為地指定（也可以由亂數產生），行程的到達時間為行程輸入的時間，行程的運行時間以時間片為單位進行計算，每個行程的狀態可以是就緒 W（Wait）、運行R（Run）、或完成F（Finish）三種狀態之一，就緒行程獲得 CPU后都只能運行一個時間片，用已占用CPU時間加1來表示，如果運行一個時間片后，行程的已占用 CPU時間已達到所需要的運行時間，則撤消該行程，如果運行一個時間片后行程的已占用CPU時間還未達所需要的運行時間，也就是行程還需要繼續運行，此時應將行程的優先數減1（即降低一級），然后把它插入就緒佇列等待CPU，每進行一次調度程式都列印一次運行行程、就緒佇列、以及各個行程的 PCB，以便進行檢查，
重復以上程序，直到所要行程都完成為止，
調度演算法的流程圖如下 :
源代碼
主函式Main()：
主方法類，主要是為了給所有類進行統一的呼叫，使程式有一定的順序感，并且按順序執行能夠得到正確的答案，主方法中，需要首先對作業類進行初始化資料，模擬行程的初始化；再對行程進行模擬程式執行運行時間，然后執行調度演算法，將輸入佇列行程按照高優先權調度演算法，插入到執行佇列中（使用的是靜態優先權調度），計算執行佇列中各個的行程的開始時間，結束時間，周轉時間等等；列印輸出執行佇列中的作業資訊，
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
/**
* 行程調度演算法實作類
* @author Alice
*
*/
public class Main {
@SuppressWarnings("Do you like what you see?")
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("這是一個高優先權調度演算法，馬上開始：");
System.out.println("請先輸入作業的相關資訊：（輸入no代表結束）");
//輸入作業佇列
List<PCB> pcbs = new ArrayList<>();
//這是執行佇列
List<PCB> execpcbs = new ArrayList<>();
//資訊初始化
do {
PCB P = new PCB();
PCB initP = DynamicJobFirstUtil.init(P);
pcbs.add(initP);
System.out.println("是否繼續輸入作業資訊:( yes or no)");
}while (scanner.nextLine().equalsIgnoreCase("yes"));
System.out.println("............................");
//初始化完場
for (PCB pcb : pcbs){
System.out.println(pcb.toString());
}
//執行調度演算法，將輸入佇列作業按照演算法，插入到執行佇列中
execpcbs = DynamicJobFirstUtil.dispatchpcb(pcbs, execpcbs);
System.out.println("............................");
//求出周轉時間和平均周轉時間并記錄在每一個作業物體中
DynamicJobFirstUtil.turnRoundTime(execpcbs);
for (PCB P : execpcbs){
System.out.println(P.toString());
}
System.out.println("............................");
DynamicJobFirstUtil.showTime(execpcbs);
}
}
PCB類：
封裝行程的相關屬性和方法，主要定義有關行程中封裝的屬性，比如行程名稱，行程服務時間，行程到達時間，行程開始時間，行程優先級，行程狀態，行程結束時間，行程周轉時間，行程平均周轉時間等，以及其get和set方法，
public class PCB {
//行程名
private String pcbName;
//行程到達時間
private int pcbArrivalTime;
//行程服務時間
private int pcbServiceTime;
//行程初始優先權限
private int firstNum;
//行程狀態
private char pcbState;
//行程間的鏈接指標
private PCB nextPCB;
//行程開始時間
private int pcbStartTime;
//行程完成時間
private int pcbOverTime;
//行程周轉時間
private int pcbRoundTime;
//行程帶權周轉時間
private double pcbAvgRoundTime;
public String getPcbName(){
return pcbName;
}
public int getPcbArrivalTime(){
return pcbArrivalTime;
}
public int getPcbServiceTime() {
return pcbServiceTime;
}
public int getFirstNum() {
return firstNum;
}
public char getPcbState() {
return pcbState;
}
public PCB getNextPCB() {
return nextPCB;
}
public int getPcbStartTime() {
return pcbStartTime;
}
public int getPcbOverTime() {
return pcbOverTime;
}
public int getPcbRoundTime() {
return pcbRoundTime;
}
public double getPcbAvgRoundTime() {
return pcbAvgRoundTime;
}
public void setPcbName(String pcbName){
this.pcbName = pcbName;
}
public void setPcbArrivalTime(int pcbArrivalTime) {
this.pcbArrivalTime = pcbArrivalTime;
}
public void setPcbServiceTime(int pcbServiceTime) {
this.pcbServiceTime = pcbServiceTime;
}
public void setFirstNum(int firstNum) {
this.firstNum = firstNum;
}
public void setPcbState(char pcbState) {
this.pcbState = pcbState;
}
public void setNextPCB(PCB nextPCB) {
this.nextPCB = nextPCB;
}
public void setPcbStartTime(int pcbStartTime) {
this.pcbStartTime = pcbStartTime;
}
public void setPcbOverTime(int pcbOverTime) {
this.pcbOverTime = pcbOverTime;
}
public void setPcbRoundTime(int pcbRoundTime) {
this.pcbRoundTime = pcbRoundTime;
}
public void setPcbAvgRoundTime(double pcbAvgRoundTime) {
this.pcbAvgRoundTime = pcbAvgRoundTime;
}
@Override
public String toString() {
return "PCB{" +
"pcbName='" + pcbName + '\'' +
", pcbArrivalTime=" + pcbArrivalTime +
", pcbServiceTime=" + pcbServiceTime +
", firstNum=" + firstNum +
", pcbState=" + pcbState +
", nextPCB=" + nextPCB +
", pcbStartTime=" + pcbStartTime +
", pcbOverTime=" + pcbOverTime +
", pcbRoundTime=" + pcbRoundTime +
", pcbAvgRoundTime=" + pcbAvgRoundTime +
'}';
}
}
動態高優先度演算法工具類DynamicJobFirstUtil()：
調度演算法的工具類，方法有
1.行程初始化 init()
2.按照服務時間去排序 sortByServerTime()（這里寫出來沒有用到）
3.按照到達時間去排序 sortByArrivalTime()
4. 先按照優先度排序，優先度相同的按照到達時間去排序 sortByStateAndArrivalTime()，
4.調度演算法函式，最終將需要按順序執行的行程放入execJobs中dispatchJob()，
5.求出周轉時間,平均周轉時間等其他資訊 turnRoundTime()，
import java.text.SimpleDateFormat;
import java.util.*;
/**
* 動態高優先權優先調度演算法工具類
* @author Alice
*
*/
public class DynamicJobFirstUtil {
private static SimpleDateFormat tm= new SimpleDateFormat("HH:mm:ss");
//行程初始化
@SuppressWarnings("Do you like what you see?")
public static PCB init(PCB pcb){
Scanner scanner = new Scanner(System.in);
System.out.println("請輸入行程名稱：如（行程1）");
pcb.setPcbName(scanner.nextLine());
System.out.println("請輸入行程到達時間：如（1）");
pcb.setPcbArrivalTime(scanner.nextInt());
System.out.println("請輸入行程服務時間：如（3）");
pcb.setPcbServiceTime(scanner.nextInt());
System.out.println("請輸入行程初始優先權：如（1）");
pcb.setFirstNum(scanner.nextInt());
pcb.setPcbState('w');
return pcb;
}
//按照服務時間排序
public static void sortBySeverTime(List<PCB> pcbs){
//使用Collections工具類中的自定義條件排序方法
Collections.sort(pcbs, new Comparator<PCB>() {
@Override
public int compare(PCB pcb1, PCB pcb2) {
return (int) ( pcb1.getPcbServiceTime() - pcb2.getPcbServiceTime());
}
});
}
//按照到達時間排序
public static void sortByArrivalTime(List<PCB> pcbs){
//使用Collections工具類中的自定義條件排序方法
Collections.sort(pcbs, new Comparator<PCB>() {
@Override
public int compare(PCB pcb1, PCB pcb2) {
return (int) (pcb1.getPcbArrivalTime() - pcb2.getPcbArrivalTime());
}
});
}
//按照優先度排序，優先度相同的按照到達時間去排序
public static void sortByStateAndArrivalTime(List<PCB> pcbs){
//使用Collections工具類中的自定義條件排序方法
Collections.sort(pcbs, new Comparator<PCB>() {
@Override
public int compare(PCB pcb1, PCB pcb2) {
int cr = 0;
//首先按照優先級排降序
int a = pcb1.getFirstNum() - pcb2.getFirstNum();
if (a != 0){
cr = (a < 0) ? 3 : -1;
}else{
//然后按照到達時間排升序
a = pcb1.getPcbArrivalTime() - pcb2.getPcbArrivalTime();
if (a != 0){
cr = (a > 0) ? 2 : -2;
}
}
return cr;
}
});
}
/*調度演算法函式，最終將需要按順序執行的行程放入execpcbs中
pcbs，輸入佇列，execpcbs，執行佇列*/
public static List<PCB> dispatchpcb(List<PCB> pcbs, List<PCB> execpcbs){
//中間佇列，用于暫時存盤輸入佇列中挑選出的行程
List<PCB> tempP = new ArrayList<>();
//CPU無作業的時候，給第一個到達的行程服務，結束時間到達的行程在執行
DynamicJobFirstUtil.sortByArrivalTime(pcbs);
execpcbs.add(pcbs.get(0));
pcbs.remove(pcbs.get(0));
//將輸入佇列中的行程一個一個的移動到執行佇列
while (pcbs.size()>0){
//execpcbs佇列的最后一個execpcb的結束時間
PCB exepcb = execpcbs.get((execpcbs.size() - 1));
int endTime = exepcb.getPcbArrivalTime() + exepcb.getPcbServiceTime();
//使用迭代器，便于輸入佇列的洗掉，避免出錯
Iterator<PCB> iterator = pcbs.iterator();
//判斷迭代
while (iterator.hasNext()){
PCB P = iterator.next();
//將執行佇列中的結束時間大于輸入佇列到達時間的所有行程移動到執行佇列
if (endTime >= P.getPcbArrivalTime()){
tempP.add(P);
iterator.remove();
}
}
//如果遍歷之后，執行佇列的結束時間還沒有到達，則按照到達時間排序得到第一個
if (tempP == null){
DynamicJobFirstUtil.sortByArrivalTime(pcbs);
execpcbs.add(pcbs.get(0));
pcbs.remove(pcbs.get(0));
}
//按照服務時間長短進行排序，以免下面移動到執行佇列的行程順序出錯
DynamicJobFirstUtil.sortByStateAndArrivalTime(tempP);
execpcbs.addAll(tempP);
tempP.clear();
}
for (PCB pcb : execpcbs){
pcb.setPcbState('r');
}
return execpcbs;
}
//求出周轉時間，平均周轉時間等其他資訊
public static void turnRoundTime(List<PCB> pcbs){
//第一個的到達時間
int temp = pcbs.get(0).getPcbArrivalTime();
for (PCB pcb : pcbs){
//如果前一個行程的結束時間小魚當前行程的到達時間
if (temp < pcb.getPcbArrivalTime()){
temp = pcb.getPcbArrivalTime();
}
//設定行程的開始時間，前一個的結束時間等于本次的開始時間
pcb.setPcbStartTime(temp);
//得到每個行程的服務時間
int serviceTime = pcb.getPcbServiceTime();
temp+=serviceTime;
//結束時間等于開始時間加服務時間
pcb.setPcbOverTime(temp);
//周轉時間等于結束時間減去到達時間
int turnRound = temp-pcb.getPcbArrivalTime();
pcb.setPcbRoundTime(turnRound);
//帶權周轉時間等于周轉時間除以服務時間
pcb.setPcbAvgRoundTime((1.0*turnRound)/serviceTime);
}
}
//輸出行程運行時間
public static void showTime(List<PCB> pcbs){
System.out.println("行程名稱\t\t到達時間\t\t服務時間\t\t開始時間\t\t優先級\t\t狀態\t\t結束時間\t\t周轉時間\t\t帶權周轉時間");
double turnRound = 0.0;
double avgTurnRound = 0.0;
for (PCB pcb : pcbs){
System.out.println(pcb.getPcbName()+"\t\t\t"+pcb.getPcbArrivalTime()+"\t\t\t"+pcb.getPcbServiceTime()
+"\t\t\t"+pcb.getPcbStartTime()+"\t\t\t"+pcb.getFirstNum()+"\t\t\t"+pcb.getPcbState()+"\t\t\t"+pcb.getPcbOverTime()+"\t\t\t"+pcb.getPcbRoundTime()
+"\t\t\t"+pcb.getPcbAvgRoundTime());
turnRound+=pcb.getPcbRoundTime();
avgTurnRound+=pcb.getPcbAvgRoundTime();
}
System.out.println(pcbs.size()+"個行程的平均周轉時間為："+String.format("%g %n",(1.0*turnRound)/pcbs.size()));
System.out.println(pcbs.size()+"個行程的平均帶權周轉時間為："+String.format("%g %n",(1.0*avgTurnRound)/pcbs.size()));
}
}
效果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/388249.html
標籤：其他