os实验-Java模拟进程调度算法 os

文章目录

内容和数据结构定义
FCFS
RR
SJF
HRN
运行截图

内容和数据结构定义随机给出一个进程调度实例,如:
进程
到达时间服务时间
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2
模拟进程调度,给出按照算法先来先服务 FCFS、轮转 RR(q=1)、
最短进程优先 SJF、最高响应比优先 HRN 进行调度各进程的完成时
间、周转时间、带权周转时间

class Dispatcher { //进程到达序列, 0s到达进程, 要求服务时间3s, ... //proGo.length 进程数量 public static int[][] proGo = {{0, 3}, {2, 6}, {4, 4}, {6, 5}, {8, 2}}; public static Queue readyQueue = new LinkedList<>(); //进程的就绪队列 public static Queue endQueue = new LinkedList<>(); //进程结束队列, 用来最后输出完成时间, 周转时间, 带权周转时间 public static TreeSet readySet = new TreeSet<>(); //用在SJF中的排序树 public static LinkedList readyList = new LinkedList<>(); //用在hrn中//先来先服务算法 public void fcfs() {...}; //时间片轮转 public void rr(int q) {...}; //短进程优先 public void sjf() {...}; //最高响应比 public void hrn() {...};

进程类定义

public class Process implements Comparable{ public int getPid() { return pid; }private int pid; public int arrTime; //到达时间 public int servTime; //要求服务的时间 publicint exeTime; //已经执行时间 private int endTime; //执行完成时间public int getEndTime() { return endTime; }public void setEndTime(int endTime) { this.endTime = endTime; }public Process(int pid, int arrTime, int servTime) { this.pid = pid; this.arrTime = arrTime; this.servTime = servTime; }@Override public int compareTo(Object o) { return this.servTime - ((Process) o).servTime; } }

FCFS 每一次循环代表经过一个单位时间, 循环开始时, 检测是否有进程到达, 有则加入到队列
readyQueue. 之后取队首元素执行一次(exeTime++), 此时如果已执行完, 就出队, 放入 endQueue,
如果没执行完, 不做任何处理, 进行下一次循环

/** * 先来先服务 */ publicvoid fcfs() { boolean flag = false; int time = 0; System.out.println(time + "s: "); while (endQueue.size() < proGo.length) { time++; proArrive(proGo, readyQueue, time - 1); //将到达进程加入到就绪队列 flag = proExecuteFCFS(readyQueue); if (flag) { Process process = readyQueue.poll(); process.setEndTime(time); endQueue.offer(process); System.out.println("进程" + process.getPid() + "执行完成"); } System.out.println(time + "s: "); } //打印统计信息 getParams(endQueue); } /** * 每个单位时间执行一次, 扫描是否有进程到达, 有则加入到就绪队列 * @param proGo进程到达顺序到达时间, 服务时间 * @param readyQueue 就绪队列 * @param times 当前时间 */ public static void proArrive(int[][] proGo, Queue readyQueue, int times) { for (int i = 0; i < proGo.length; i++) { if (times < proGo[i][0]) {//简单优化 return; } if (times == proGo[i][0]) { //进程进入就绪队列 readyQueue.offer(new Process(i, times, proGo[i][1])); System.out.println("进程" + i + "到达"); } } } /** * (队首)进程执行, 如果执行完毕, 返回true(进程出队列在外面完成) * 无就绪进程, 返回false * @param readQueue * @param * @return */ public static boolean proExecuteFCFS(Queue readQueue) { if (readQueue.isEmpty()) { return false; } Process process = readQueue.peek(); process.exeTime++; System.out.println("进程" + process.getPid() + "执行"); return process.exeTime == process.servTime; }

RR 【os实验-Java模拟进程调度算法】每执行一次 while 循环代表执行一个时间片, 时间片 p 是传入的参数. 一个时间片内, 队首元
素执行, 如果进程执行完毕, 就跳出这次循环. 如果没执行完, 就中断执行, 放到队尾.

/** * 模拟时间片轮转 * @param q 时间片大小 */ publicvoid rr(int q) throws Exception { if (q <= 0) { throw new Exception("illegal param!"); }boolean flag = false; int time = 0; System.out.println(time + "s: "); proArrive(proGo, readyQueue, time); while (endQueue.size() < proGo.length) { for (int i = 0; i < q; i++) {//执行一个时间片, q个单位时间 //try { //Thread.sleep(2000); //} catch (InterruptedException e) { //e.printStackTrace(); //}time++; flag = proExecuteFCFS(readyQueue); if (flag) { Process process = readyQueue.poll(); process.setEndTime(time); endQueue.offer(process); System.out.println("进程" + process.getPid() + "执行完毕"); System.out.println(time + "s: "); proArrive(proGo, readyQueue, time); break; } //进程在一个时间片内未执行完 Process pro = null; if (i == q - 1 && !flag && !readyQueue.isEmpty()) { pro = readyQueue.poll(); System.out.println("进程" + pro.getPid() + "在该时间片内未完成, 中断执行"); } System.out.println(time + "s: "); proArrive(proGo, readyQueue, time); if (pro != null) { readyQueue.offer(pro); } } } getParams(endQueue); } /** * 每个单位时间执行一次, 扫描是否有进程到达, 有则加入到就绪队列 * @param proGo进程到达顺序到达时间, 服务时间 * @param readyQueue 就绪队列 * @param times 当前时间 */ public static void proArrive(int[][] proGo, Queue readyQueue, int times) { for (int i = 0; i < proGo.length; i++) { if (times < proGo[i][0]) {//简单优化 return; } if (times == proGo[i][0]) { //进程进入就绪队列 readyQueue.offer(new Process(i, times, proGo[i][1])); System.out.println("进程" + i + "到达"); } } } /** * (队首)进程执行, 如果执行完毕, 返回true(进程出队列在外面完成) * 无就绪进程, 返回false * @param readQueue * @param * @return */ public static boolean proExecuteFCFS(Queue readQueue) { if (readQueue.isEmpty()) { return false; } Process process = readQueue.peek(); process.exeTime++; System.out.println("进程" + process.getPid() + "执行"); return process.exeTime == process.servTime; }

SJF 将按时间顺序到达的进程放入一个 TreeSet 集合中, 按照进程要求的服务时间 servTime 来比较大小, 并放入树中. 这样, 每一次调度都取出树最左叶子节点执行, 这样就能保证最短进程优先.

public void sjf() { boolean flag = false; int time = 0; System.out.println(time + "s: "); Process pro = null; while (endQueue.size() < proGo.length) { time++; proArriveSJF(proGo, readySet, time - 1); if (!flag) { pro = readySet.pollFirst(); } if (pro == null) { System.out.println(time + "s: "); break; } flag = true; pro.exeTime++; System.out.println("进程" + pro.getPid() + "执行"); if (pro.exeTime == pro.servTime) { pro.setEndTime(time); endQueue.offer(pro); System.out.println("进程" + pro.getPid() + "执行完成"); flag = false; } System.out.println(time + "s: "); } getParams(endQueue); } /** * 每个单位时间执行一次, 扫描是否有进程到达, 有就加入到就绪队列(树型结构) * @param proGo * @param tree (底层是堆排序) * @param time */ public static void proArriveSJF(int[][] proGo, TreeSet tree, int time) { for (int i = 0; i < proGo.length; i++) { if (time < proGo[i][0]) { return; } if (time == proGo[i][0]) { tree.add(new Process(i, proGo[i][0], proGo[i][1])); System.out.println("进程" + i + "到达"); } } } //输出统计结果 public static void getParams(Queue endQueue) { int size = endQueue.size(); double total = 0.0; for (Process pro : endQueue) { int endTime = pro.getEndTime(); int turnTime = endTime - pro.arrTime; float turnTimeP = (float) ((turnTime + 0.0) / pro.exeTime); total += turnTimeP; StringBuilder sb = new StringBuilder(); sb.append("进程").append(pro.getPid()).append(" 完成时间: ").append(endTime). append(" 周转时间: ").append(turnTime).append(" 带权周转时间: ").append(turnTimeP); System.out.println(sb.toString()); } System.out.println("平均带权周转时间: " + total/size); }

HRN 和上面的算法类似, 主要区别就是每次从就绪队列中取出进程时, 所有进程都要根据当前时间来算一次响应比, 取出响应比最大值的进程来执行, 执行结束后放到 endQueue.
响应比 = (服务时间 + 等待时间) / 服务时间, 这样即让短作业优先执行, 又保证长作业一定会被执行

publicvoid hrn() { boolean flag = false; int time = 0; System.out.println(time + "s: "); Process pro = null; while (endQueue.size() < proGo.length) { //try { //Thread.sleep(1000); //} catch (InterruptedException e) { //e.printStackTrace(); //} time++; proArriveHRN(proGo, readyList, time - 1); if (!flag) { pro = proExecuteHRN(readyList, time - 1); } if (pro == null) { System.out.println(time + "s: "); break; } flag = true; pro.exeTime++; System.out.println("进程" + pro.getPid() + "执行"); if (pro.exeTime == pro.servTime) { pro.setEndTime(time); endQueue.offer(pro); System.out.println("进程" + pro.getPid() + "执行完成"); flag = false; } System.out.println(time + "s: "); } getParams(endQueue); } public static void proArriveHRN(int[][] proGo, LinkedList readList, int time) { for (int i = 0; i < proGo.length; i++) { if (time < proGo[i][0]) {//简单优化 return; } if (time == proGo[i][0]) { //进程进入就绪队列 readList.add(new Process(i, time, proGo[i][1])); System.out.println("进程" + i + "到达"); } } } /** * 计算响应比, 返回最高响应比的进程对象 * @param readyList * @param now * @return */ public static Process proExecuteHRN(LinkedList readyList, int now) { if (readyList.isEmpty()) { return null; } double max = 0.0; Process maxPro = null; int index = 0; for (int i = 0; i < readyList.size(); i++) { Process pro = readyList.get(i); int arriveTime = pro.arrTime; int servTime = pro.servTime; double power = (servTime + now - arriveTime) / servTime; if (Double.compare(power, max) == 1) { maxPro = pro; max = power; index = i; } } readyList.remove(index); return maxPro; }

运行截图