用java语言，模拟实现操作系统的进程调度算法，先来先服务，高优先级、高响应比、时间片轮转和短作业
构思算法的实现过程。
【用java语言，模拟实现操作系统的进程调度算法，先来先服务，高优先级、高响应比、时间片轮转和短作业】①先来先服务算法
一开始我从最简单的先来先服务开始想，既然要排序进程链表的执行顺序，肯定要将链表的头head作为参数传入到方法中。其次为了之后方便一次性检验多种算法，传入进来的head链表我不会对它进行任何改变。所以创建一个新链表head2用CreateHead方法将链表进行复制，这样我就可以拿head2这个复制品随便搞，也不会影响之后调用其他算法，因为head没变。
当我拿到复制链表head2之后，要对他进行先来先服务算法排序，肯定要比较所有进程的到达时间，从到达时间最小的进程先开始执行，需要注意的是将某个进程执行完毕之后，要将它从链表中移除，以确保下一次查找的正确性。所以我用一个大循环，循环次数是链表的结点数，每一次循环都找到本次循环到达时间最小的那个结点，然后将这个结点的所有进程信息进行更新，包括完成时间，周转时间，带权周转时间，打印所有的信息到控制台。并且更新一下总时间线start(一开始为0，每次运行一个进程，它的值都加上这个进程的运行时间，相当于总时间线）。最后将这个结点从链表中删除，再次循环从剩余的节点中找到达时间最小的结点，直到所有结点都被删除了。那么所有结点的执行顺序也已经全部被打印到控制台上了。每次循环都记录周转时间和带权周转时间。最后循环结束计算一下平均值。下面是算法流程图：
文章图片
②短作业优先算法
短作业优先自然要选择运行时间最短的进程先执行，和上面的算法流程图大体一致，就是要找出链表中运行时间最短的节点。并且要注意的是如果最短运行时间的进程的到达时间很迟，而有一个运行时间较长的进程先到达了，就不能让CPU等着。应该先执行到达的进程，等到这个进程执行完毕之后，再次找运行时间最短的进程。直到程序退出。
③高优先级优先算法
高优先级和前两种也类似，主要是找到最高优先级的进程先运行，而且也要和第二种算法一样注意进程的到达时间。
④高响应比优先算法
此算法和前三种稍有不同，虽然大体流程相同，但是响应比有自己的计算公式，响应比 = （等待时间+要求服务时间）/ 要求服务时间。
我封装了一个方法专门求响应比，所以也可以和上面三种程序一样先找到响应比最高的进程运行。需要注意的是，每一个进程运行完毕之后响应比都会发生变化。
⑤时间片轮转算法
这个算法我想它大体是个先来先服务一样的，所以我将所有进程一开始按到达时间排序，因为每次时间片执行完毕进程不一定结束，所以给进程的节点中添加两个新属性int newarrival和int newruntime用来保存更新之后的到达时间和运行时间，每次时间片执行完毕，这个进程的到达时间就是此刻，然后将它的到达时间和链表中所有的进程的到达时间进行比较，插入它比它小和比它大的到达时间之间，如果遇到相等的到达时间就插入到本来存在节点的后面。然后本次时间片结束，头指针向后移动运行下一个排队的进程节点。
源代码如下
import java.util.Scanner;
class Node{
String name;
int priority;
int runtime;
int arrivaltime;
int starttime;
int endtime;
int turntime;
//周转时间
double dturntime;
//带权周转时间
Node nextnode;
int statu;
int newarrival;
int newruntime;
public Node(String name,int priority,int runtime,int arrivaltime, int starttime, int endtime, int turntime, double dturntime){
this.name = name;
this.priority = priority;
this.runtime = runtime;
this.arrivaltime = arrivaltime;
this.nextnode = null;
this.starttime = starttime;
this.endtime = endtime;
this.turntime = turntime;
this.dturntime = dturntime;
this.newarrival = arrivaltime;
this.newruntime = runtime;
}}class Create{
public Node createNode(Node head, String name, int priority, int runtime, int arrivaltime, int starttime, int endtime, int turntime, double dturntime){if(head == null){
Node node = new Node(name,priority,runtime,arrivaltime,starttime,endtime,turntime,dturntime);
head = node;
return head;
}
Node cur = head;
while(cur.nextnode!=null){
cur = cur.nextnode;
}
Node node = new Node(name,priority,runtime,arrivaltime,starttime,endtime,turntime,dturntime);
cur.nextnode = node;
return head;
}public void check(Node head){
if(head == null){
System.out.println("当前没有节点信息");
return;
}
Node cur = head;
while(cur!=null){
System.out.println("名字:"+cur.name+"、优先级:"+cur.priority+"、运行时间:"+cur.runtime+"、到达时间"+cur.arrivaltime);
cur = cur.nextnode;
}
}
}class Algorithm{
private Node pre = null;
private Node prev = null;
private Node min = null;
private int num = 0;
private int start = 0;
private double nums = 0.0;
private int count = 0;
private static Create create = new Create();
private static Node CreateHead(Node head){
Node head2 = null;
Node cur = head;
while(cur!=null){
head2 = create.createNode(head2,cur.name,cur.priority,cur.runtime,cur.arrivaltime,cur.starttime,cur.endtime,cur.turntime,cur.dturntime);
cur = cur.nextnode;
}
return head2;
}private void endFun(){
System.out.println("平均周转时间:" + (double) this.num / this.count + "平均带权周转时间:" + this.nums / this.count);
this.start = 0;
this.num = 0;
this.nums = 0;
this.count = 0;
}private static Node toolMethod(Node min,Node prev,int start,Node head){
min.starttime = start;
min.endtime = min.starttime + min.runtime;
min.turntime = min.endtime - min.arrivaltime;
min.dturntime = (double) min.turntime / (double) min.runtime;
System.out.println("名字:" + min.name + "、优先级:" + min.priority + "、运行时间:" + min.runtime + "、到达时间" + min.arrivaltime + "、开始时间:" + min.starttime + "、结束时间:" + min.endtime + "、周转时间:" + min.turntime + "、带权周转时间:" + min.dturntime);
if (prev == null) {
if (min.nextnode == null) {
return null;
}
return min.nextnode;
} else {
prev.nextnode = min.nextnode;
}
return head;
}private static Node findMin(Node head){
Node cur = head;
Node real = null;
int mintime = cur.arrivaltime;
while(cur!=null){
if(cur.arrivaltime<=mintime){
mintime = cur.arrivaltime;
real = cur;
}
cur = cur.nextnode;
}
return real;
}public void Fcfs(Node head) {
Node head2 = CreateHead(head);
while (head2 != null) {
min = null;
pre = null;
Node cur = head2;
int mintime = cur.arrivaltime;
while (cur != null) {
if (cur.arrivaltime <= mintime) {
mintime = cur.arrivaltime;
prev = pre;
min = cur;
}
pre = cur;
cur = cur.nextnode;
}
if (min.arrivaltime > start) {
start = min.arrivaltime;
}
head2 = toolMethod(min,prev,start,head2);
start = start + min.runtime;
num += min.turntime;
nums += min.dturntime;
count++;
}
this.endFun();
}public void Priority(Node head){
Node head2 = CreateHead(head);
while(head2!=null){
min = null;
pre = null;
Node cur = head2;
int mintime = 0;
while(cur!=null){
if(cur.priority >= mintime && cur.arrivaltime <= start){
mintime = cur.priority;
prev = pre;
min = cur;
}
pre = cur;
cur = cur.nextnode;
}
if(min == null){
min = findMin(head2);
}
if(min.arrivaltime > start){
start = min.arrivaltime;
}
head2 = toolMethod(min,prev,start,head2);
start = start + min.runtime;
num += min.turntime;
nums += min.dturntime;
count++;
}
this.endFun();
}public void ShortProcess(Node head){
Node head2 = CreateHead(head);
while(head2!=null){
min = null;
pre = null;
Node cur = head2;
int mintime = 1000;
while(cur!=null){
if(cur.runtime <= mintime && cur.arrivaltime <= start){
mintime = cur.runtime;
prev = pre;
min = cur;
}
pre = cur;
cur = cur.nextnode;
}
if(min == null){
min = findMin(head2);
}
if(min.arrivaltime > start){
start = min.arrivaltime;
}
head2 = toolMethod(min,prev,start,head2);
start = start + min.runtime;
num += min.turntime;
nums += min.dturntime;
count++;
}
this.endFun();
}private static double resRatio(Node node,int start){
int waittime = start - node.arrivaltime;
return (double)waittime/node.runtime;
}
public void Hreponse(Node head){
Node head2 = CreateHead(head);
while(head2!=null){
min = null;
pre = null;
Node cur = head2;
double mintime = 0.0;
while(cur!=null){
double resratio = resRatio(cur,start);
if(resratio >= mintime && cur.arrivaltime <= start){
mintime = resratio;
prev = pre;
min = cur;
}
pre = cur;
cur = cur.nextnode;
}
if(min == null){
min = findMin(head2);
}
if(min.arrivaltime > start){
start = min.arrivaltime;
}
head2 = toolMethod(min,prev,start,head2);
start = start + min.runtime;
num += min.turntime;
nums += min.dturntime;
count++;
}
this.endFun();
}public static Node QueueHead(Node head){
Node cur = head;
Node nodemin = null;
Node head2 = null;
int min = 1000;
int count = 0;
while(cur!=null){
count++;
cur = cur.nextnode;
}
while(count!=0) {
min = 1000;
cur = head;
while (cur != null) {
if (cur.arrivaltime < min && cur.statu == 0) {
nodemin = cur;
min = cur.arrivaltime;
}
cur = cur.nextnode;
}
nodemin.statu = 1;
count--;
head2 = create.createNode(head2,nodemin.name,nodemin.priority,nodemin.runtime,nodemin.arrivaltime,nodemin.starttime,nodemin.endtime,nodemin.turntime,nodemin.dturntime);
}
return head2;
}public static void insert(Node head,Node min){
Node cur = head;
Node pre = null;
while(cur!=null){
if(cur.arrivaltime > min.newarrival){
pre.nextnode = min;
min.nextnode = cur;
return;
}
pre = cur;
cur = cur.nextnode;
}
pre.nextnode = min;
min.nextnode = cur;
}public void Roundrobin(Node head,int Rtime){
Node newnode = null;
Node head2 = QueueHead(head);
create.check(head2);
System.out.println(head2.newruntime);
System.out.println(head2.newarrival);
while(head2!=null){
min = head2;
if(min.arrivaltime > start){
start = min.arrivaltime;
}
if(min.newruntime > Rtime){
min.newruntime -= Rtime;
start += Rtime;
min.newarrival += Rtime;
newnode = new Node(min.name,min.priority,min.runtime,min.arrivaltime,min.starttime,min.endtime,min.turntime,min.dturntime);
newnode.newarrival = min.newarrival;
newnode.newruntime = min.newruntime;
insert(head2,newnode);
head2 = min.nextnode;
}else{
start += min.newruntime;
min.endtime = start;
min.turntime = min.endtime - min.arrivaltime;
min.dturntime = (double) min.turntime / (double) min.runtime;
head2 = min.nextnode;
num += min.turntime;
nums += min.dturntime;
count++;
System.out.println("名字:" + min.name + "、优先级:" + min.priority + "、运行时间:" + min.runtime + "、到达时间" + min.arrivaltime + "、开始时间:" + min.starttime + "、结束时间:" + min.endtime + "、周转时间:" + min.turntime + "、带权周转时间:" + min.dturntime);
}
}
this.endFun();
}
}public class Test {
public static void dispatchMenu(Node head){Scanner sc = new Scanner(System.in);
Algorithm al = new Algorithm();
int count = 1;
while(count == 1){
System.out.println("请选择调度算法:");
System.out.println("1.先来先服务算法");
System.out.println("2.短作业优先算法");
System.out.println("3.高优先级优先算法");
System.out.println("4.高响应比优先算法");
System.out.println("5.时间片轮转算法");
System.out.println("0.退出");
int num = sc.nextInt();
switch(num){
case 1:al.Fcfs(head);
break;
case 2:al.ShortProcess(head);
break;
case 3:al.Priority(head);
break;
case 4:al.Hreponse(head);
break;
case 5:al.Roundrobin(head,1);
break;
case 0:count = 0;
break;
default:System.out.println("输入错误请重新输入");
}
}
}public static void mainMenu(){
Create create = new Create();
Node head = null;
Scanner sc = new Scanner(System.in);
int count1 = 1;
while(count1 == 1){
System.out.println("请选择你需要的服务:");
System.out.println("1.添加新进程");
System.out.println("2.使用调度算法进行排序");
System.out.println("3.查看当前进程信息");
System.out.println("0.退出");
int num = sc.nextInt();
switch(num){
case 1:
String name;
int priority;
int runtime;
int arrivaltime;
System.out.println("请输入进程名字:");
name = sc.next();
System.out.println("请输入进程优先级:");
priority = sc.nextInt();
System.out.println("请输入进行运行时间:");
runtime = sc.nextInt();
System.out.println("请输入进程到达时间:");
arrivaltime = sc.nextInt();
head = create.createNode(head,name,priority, runtime,arrivaltime,0,0,0,0);
break;
case 2:Test.dispatchMenu(head);
break;
case 3:create.check(head);
break;
case 0:count1 = 0;
break;
default:System.out.println("输入错误请重新输入");
}
}
}public static void main(String[] args) {
// TODO Auto-generated method stub
Test.mainMenu();
}
}推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- Docker应用:容器间通信与Mariadb数据库主从复制
- JS中的各种宽高度定义及其应用
- 由浅入深理解AOP
- 【译】20个更有效地使用谷歌搜索的技巧
- 涉毒患者(新诗)
- 参保人员因患病来不及到指定的医疗机构就医，能否报销医疗费用（）
- mybatisplus如何在xml的连表查询中使用queryWrapper
- MybatisPlus|MybatisPlus LambdaQueryWrapper使用int默认值的坑及解决
- MybatisPlus使用queryWrapper如何实现复杂查询