进程调度 非抢占式优先权调度算法 java实现

非抢占式优先权调度

非抢占式静态优先权调度策略:静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。一般地,优先权是利用某一范围内的一个整数来表示的,例如,0~255中的某一整数,当数值愈大时,其优先权愈低。

非抢占式优先权调度:系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。

数据结构和符号说明

本调度算法的数据结构PCB共包含了四个公共变量``,四个私有变量timeStart、timeComplete、timeTurnaround、timeWeightedTurnaround

// 四个公共变量:作业名、到达时间、服务时间、优先级
String threadName; int timeArrival; int timeSever; int priority
// 四个私有变量:开始执行时间、完成时间、周转时间、带权周转时间
private int timeStart; private int timeComplete; 
private int timeTurnaround; private double timeWeightedTurnaround;

在主类NPPS中有一个进程调度函数dispatch(PCB[] starr),一个根据到达时间进行排序的sort(PCB[] starr, int num)函数,以及一个根据优先级进行排序的函数sortPriority(PCB[] starr, int left, int right)。根据到达时间的sort函数只有在一开始时调用一次排序;根据优先级的sortPriority函数为了减少无意义调用从而节约时间资源,只有rightcount <= num && lastsortflag成立时才会进行一次排序,保证所有进程都进入等待状态并完成排序后不再重复调用浪费资源。

测试类Test包含一个主函数用于启动,以及一个专门用于接受输入进程信息的函数。并且输入的进程数组在测试类中定义,也能实现在NPPS类中的函数直接更改进程的信息。

流程图

进程调度 非抢占式优先权调度算法 java实现_第1张图片

源程序

PCB类
import java.text.DecimalFormat;

public class PCB {
     
    /**
     * 四个公共变量:作业名、到达时间、服务时间、优先级
     */
    String threadName;
    int timeArrival;
    int timeSever;
    int priority;
    /**
     * 四个私有变量:开始执行时间、完成时间、周转时间、带权周转时间
     */
    private int timeStart;
    private int timeComplete;
    private int timeTurnaround;
    private double timeWeightedTurnaround;

    public PCB() {
     
    }

    public PCB(String threadName, int timeArrival, int timeSever, int priority) {
     
        this.threadName = threadName;
        this.timeArrival = timeArrival;
        this.timeSever = timeSever;
        this.priority = priority;
    }

    public void setTimeStart(int timeStart) {
     //将由算法调度程序分配开始时间
        this.timeStart = timeStart;
    }

    public int getTimeComplete() {
     
        return timeComplete;
    }

    public int getTimeTurnaround() {
     
        return timeTurnaround;
    }

    public double getTimeWeightedTurnaround() {
     
        return timeWeightedTurnaround;
    }

    public void run() {
      //开始调度后的运行内容
        /* 计算出完成时间、周转时间、带权周转时间 */
        timeComplete = timeStart + timeSever;
        timeTurnaround = timeComplete - timeArrival;
        DecimalFormat dF = new DecimalFormat("0.00");
        timeWeightedTurnaround = Double.parseDouble(dF.format((double) timeTurnaround / timeSever));
        //调用toString()将内容输出
        System.out.println(this);

    }

    @Override
    public String toString() {
     
        return "'" + threadName + '\'' +
                "\t\t" + timeArrival +
                "\t\t" + timeSever +
                "\t\t\t" + timeStart +
                "\t\t" + timeComplete +
                "\t\t" + timeTurnaround +
                "\t\t" + timeWeightedTurnaround;
    }
}
NPPS类
public class NPPS {
     
    public void dispatch(PCB[] pcbarr) {
     
        System.out.println("非抢占式优先权算法");
        System.out.println("作业名\t到达时间\t服务时间\t开始执行时间\t完成时间\t周转时间\t带权周转时间");
        int num = pcbarr.length;
        //周转时间之和与带权周转时间之和
        int timeTurnaroundSum = 0;
        double timeWeightedTurnaroundSum = 0;
        sort(pcbarr, num);

        /* 当前执行进程、系统调度此次作业的时间、调度完成的作业数目*/
        PCB item = pcbarr[0];
        int timeStart = pcbarr[0].timeArrival;
        int count = 0;
        boolean lastsortflag = true;
        for (int i = 0; i < num; i++) {
     

            // 三元运算符,确保系统调度作业时作业已经到达
            timeStart = timeStart > item.timeArrival ? timeStart : item.timeArrival;
            item.setTimeStart(timeStart);
            item.run();
            //完成作业+1,并在将此次完成时间作为下一个已到达作业的开始时间
            count++;
            timeStart = item.getTimeComplete();
            timeTurnaroundSum += item.getTimeTurnaround();
            timeWeightedTurnaroundSum += item.getTimeWeightedTurnaround();
            //已到达的作业再依照优先级重排,先确立左右边界
            int rightcount = count;
            for (int j = 0; j < num - count; j++) {
     
                if (pcbarr[j + count].timeArrival <= timeStart) {
     
                    rightcount++;
                }
            }
            // 需要重排的数组切片,当所有作业都重排后停止
            if (rightcount <= num && lastsortflag) {
     
                sortPriority(pcbarr, count, rightcount);
            }
            if (rightcount == num) {
      // 代表已经将所有作业重排,此后无需重排
                lastsortflag = false;
            }
            item = pcbarr[(i + 1) % num];
        }
        System.out.println("平均周转时间:" + (double) timeTurnaroundSum / num +
                ",平均带权周转时间:" + timeWeightedTurnaroundSum / num);
    }

    public void sort(PCB[] pcbarr, int num) {
     
        //根据到达时间对作业进行升序排序,排序方式:选择排序
        for (int i = 0; i < num - 1; i++) {
     
            int index = i;
            for (int j = i + 1; j < num; j++) {
     
                if (pcbarr[j].timeArrival < pcbarr[index].timeArrival) {
     
                    index = j;
                }
            }
            //将找到的最小值放到第一的位置,进行下一遍循环
            PCB temp = pcbarr[index];
            pcbarr[index] = pcbarr[i];
            pcbarr[i] = temp;
        }
    }

    public void sortPriority(PCB[] pcbarr, int left, int right) {
     
        //根据服务时间对作业进行升序排序,排序方式:选择排序
        int num = right - left;
        for (int i = 0; i < num - 1; i++) {
     
            int index = i;
            for (int j = i + 1; j < num; j++) {
     
                if (pcbarr[left + j].priority > pcbarr[left + index].priority) {
     
                    index = j;
                }
            }
            //将找到的最大值放到第一的位置,进行下一遍循环
            PCB temp = pcbarr[left + index];
            pcbarr[left + index] = pcbarr[left + i];
            pcbarr[left + i] = temp;
        }
    }
}
Test类
import java.util.Scanner;

public class Test {
     
    public static void main(String[] args) {
     
        // 读取输入的数组
        PCB[] arr1 = dataReadIn();

        //调用两大算法
        NPPS fcfs = new NPPS();
        fcfs.dispatch(arr1);
    }

    public static PCB[] dataReadIn() {
      //数据读入函数,直接设为静态函数,强制要求写入数据
        System.out.print("请输入本次需要调度的作业数目:");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PCB[] starr = new PCB[n];
        System.out.println("请输入每一个作业的作业名、到达时间、服务时间、优先级(一行一个,中间用空格区分,优先级为数字越高越优先)");
        for (int i = 0; i < n; i++) {
     
            starr[i] = new PCB(sc.next(), sc.nextInt(), sc.nextInt(), sc.nextInt());
        }
        return starr;
    }
}

运行时的初值和结果

A 0 3 3
B 1 6 5
C 2 1 1
D 3 4 4
E 4 2 2

进程调度 非抢占式优先权调度算法 java实现_第2张图片

你可能感兴趣的