操作系统 - 进程调度FCFS,RR,HPF的Java实现

发布于2021-05-29 21:00 阅读(1125) 评论(0) 点赞(8) 收藏(3)

文章目录

实验要求
具体思路
调度算法
代码实现

实验要求

用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。

编写并调试一个模拟的进程调度程序，采用最高优先数优先调度算法对五个进程
进行调度。 “最高优先数优先”调度算法的基本思想是把 CPU 分配给就绪队列中优先数最高的进程。

静态优先数是在创建进程时确定的，并在整个进程运行期间不再改变。
动态优先数是指进程的优先数在创建进程时可以给定一个初始值，并且可以按一定原则修改优先数。例如：在进程获得一次 CPU 后就将其优先数减少 1，或者，进程等待的时间超过某一时限时增加其优先数的值，等等。

编写并调试一个模拟的进程调度程序，采用轮转法调度算法对五个进程进行调度。

轮转法可以是简单轮转法、可变时间片轮转法，或多队列轮转法。
简单轮转法的基本思想是：所有就绪进程按 FCFS 排成一个队列，总是把处理机分配给队首的进程，各进程占用 CPU 的时间片相同。如果运行进程用完它的时间片后还为完成，就把它送回到就绪队列的末尾，把处理机重新分配给队首的进程，直至所有的进程运行完毕。

具体思路

设计一个有 N 个进程共行的进程调度程序。

进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。

每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用 CPU 时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生），进程的到达时间为进程输入的时间，进程的运行时间以时间片为单位进行计算。

每个进程的状态可以是就绪 W（Wait）、运行 R（Run）、或完成 F（Finish）三种状态之一（这是编程用到的三个模拟状态，并非进程的三基态）。就绪进程获得 CPU 后都只能运行一个时间片，用已占用 CPU 时间加 1 来表示。如果运行一个时间片后，进程的已占用 CPU 时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用 CPU 时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减 1（即降低一级），然后把它插入就绪队列等待 CPU。

每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。
流程图如下
在这里插入图片描述

调度算法

https://blog.csdn.net/luyafei_89430/article/details/12971171

代码实现

在这里插入图片描述

主函数和进程类

MyProcess类存储进程的基本信息，Main类放主函数。

main.java

package ProcessScheduling; 
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		//输入数据
		File file = new File("C:\\Users\\Administrator\\Desktop\\codes\\in.txt");
		Scanner scanner = new Scanner(file);
//		Scanner scanner = new Scanner(System.in);
		System.out.println("请输入进程总数");
		Integer n = scanner.nextInt(); 
		ArrayList<MyProcess> processList = new ArrayList<>();
		for(int i = 0;i<n;i++) {
			System.out.println("请输入"+(i+1)+"号进程的进程名、优先数、到达时间、需要运行时间(空格隔开):");
			String name = scanner.next();
			Integer priority = scanner.nextInt();
			Integer arrivalTime = scanner.nextInt();
			Integer needTime = scanner.nextInt();
			processList.add(new MyProcess(name,priority,arrivalTime,needTime));
		}
//		for(MyProcess i : processList) {
//			System.out.println(i);
//		}
		
		System.out.println("请输入调度算法:");
		n = scanner.nextInt(); 
		
		if(n == 1) {
			FCFS fcfs = new FCFS(processList);
			fcfs.dispatch();
		}else if(n==2){
			HPF hpf = new HPF(processList);
			hpf.dispatch();
		}
		else if(n==3){
			RR rr = new RR(processList);
			rr.dispatch();
		}
	}
}

MyProcess.java 
```css
package ProcessScheduling;

public class MyProcess {
	//进程名、优先数、到达时间、需要运行时间、已用 CPU 时间、进程状态
	private String name;
	private int priority;
	private int arrivalTime;
	private int needTime;
	private int runningTime;
	private String status; // W（Wait）、运行 R（Run）、或完成 F（Finish）
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getPriority() {
		return priority;
	}
	public void setPriority(int priority) {
		this.priority = priority;
	}
	public int getArrivalTime() {
		return arrivalTime;
	}
	public void setArrivalTime(int arrivalTime) {
		this.arrivalTime = arrivalTime;
	}
	public int getNeedTime() {
		return needTime;
	}
	public void setNeedTime(int needTime) {
		this.needTime = needTime;
	}
	public int getRunningTime() {
		return runningTime;
	}
	public void setRunningTime(int runningTime) {
		this.runningTime = runningTime;
	}
	public String getStatus() {
		return status;
	}
	public void setStatus(String status) {
		this.status = status;
	}
	public MyProcess(String name, int priority, int arrivalTime, int needTime) {
		super();
		this.name = name;
		this.priority = priority;
		this.arrivalTime = arrivalTime;
		this.needTime = needTime;
		this.runningTime = 0;
		this.status = "W";
	}
	public MyProcess() {
		super();
	}
	@Override
	public String toString() {
		return "MyProcess [name=" + name + ", priority=" + priority + ", arrivalTime=" + arrivalTime + ", needTime="
				+ needTime + ", runningTime=" + runningTime + ", status=" + status + "]";
	}
	public void processDispatch() { 
		//调度改进程
		this.runningTime++;
		this.priority--;
		this.status = "R";
	} 
	public void processFinish() {
		//结束进程
		this.status = "F";
	} 
	public void processWait() {
		//结束进程
		this.status = "W";
	} 
}

测试数据in.txt

5
name1 2 3 4
name2 9 2 3 
name3 8 9 5
name4 1 2 4
name5 1 8 3
3

最高优先数优先的调度算法

HPF.java

package ProcessScheduling;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
/*
 * 最高优先数优先调度算法(动态优先数)
 * 1.静态优先数是在创建进程时确定的，并在整个进程运行期间不再改变。   2.动态优先数是指进程的优先数在创建进程时可以给定一个初始值，并且可以按一定原则修改优先数。例如：在进程获得一次 CPU 后就将其优先数减少 1，或者，进程等待的时间超过某一时限时增加其优先数的值，等等。
 * */

public class HPF {
	PriorityQueue<MyProcess> processPriorityQueue = null;
	public HPF(ArrayList<MyProcess> processList) {
		processPriorityQueue = new PriorityQueue<MyProcess>(new Comparator<MyProcess>() {
			public int compare(MyProcess mp1,MyProcess mp2) {
				if(mp1.getPriority() == mp2.getPriority()) {
					return mp1.getNeedTime() - mp2.getNeedTime()  ;
				}
				return mp2.getPriority() - mp1.getPriority();
			}
		});
		processPriorityQueue.addAll(processList); 
	}
	 
	public void dispatch() { 
		System.out.println("最高优先数优先调度算法");
		Long timeSlice =  (long) 0;
		while(processPriorityQueue.size()>0) {
			timeSlice++;
			MyProcess mp = processPriorityQueue.poll();
			mp.processDispatch();
			System.out.println("-----------------------------------------------------------------");
			System.out.println("时间片"+timeSlice+":");
			System.out.println("当前运行的进程：");
			System.out.println(mp);
			System.out.println("当前的就绪队列：");
			Iterator<MyProcess> it = processPriorityQueue.iterator();
			while(it.hasNext()) {
				System.out.println(it.next());
			}
			
			mp.processWait();
			if(mp.getNeedTime() > mp.getRunningTime()) {
				//还需要时间片
				processPriorityQueue.add(mp);
			}
		}
	}
}

时间片轮转算法

RR.java

package ProcessScheduling;
 
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class RR {
	private Queue<MyProcess> processQueue = null;
	
	public RR(ArrayList<MyProcess> processList) {
		processQueue = new LinkedList<>();
		processQueue.addAll(processList);
	}
	
	public void dispatch() { 
		System.out.println("时间片轮转调度算法");  
		Long timeSlice =  (long) 0;
		while(processQueue.size()>0) {
			timeSlice++;
			MyProcess mp = processQueue.poll();
			mp.processDispatch();
			System.out.println("-----------------------------------------------------------------");
			System.out.println("时间片"+timeSlice+":");
			System.out.println("当前运行的进程：");
			System.out.println(mp);
			System.out.println("当前的就绪队列：");
			Iterator<MyProcess> it = processQueue.iterator();
			while(it.hasNext()) {
				System.out.println(it.next());
			} 
			mp.processWait();
			if(mp.getNeedTime() > mp.getRunningTime()) {
				//还需要时间片
				processQueue.add(mp);
			}
		}
	}
}

先来先服务调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
FCFS.java

package ProcessScheduling;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
//在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
public class FCFS {
	private ArrayList<MyProcess> processList = null;

	public FCFS(ArrayList<MyProcess> processList) {
		super();
		this.processList = processList;
	}
	
	public void dispatch() { 
		System.out.println("先来先服务调度算法");
		//首先按照时间顺序排列。
		Collections.sort(processList,new Comparator<MyProcess>() {
			public int compare(MyProcess mp1,MyProcess mp2) {
				if(mp1.getArrivalTime() == mp2.getArrivalTime()) {
					return mp1.getNeedTime() - mp2.getNeedTime()  ;
				}
				return mp1.getArrivalTime() - mp2.getArrivalTime();
			}
		}) ; 
		
		System.out.println("开始调度");
		Long timeSlice = (long) 0;
		int num = processList.size();
		for(int i = 0;i < num;i++) {
			//开始调用第i个进程
			MyProcess mp = processList.get(i); 
			while(mp.getNeedTime() > mp.getRunningTime()) {
				timeSlice++;//分配时间片
				mp.processDispatch();
				System.out.println("-----------------------------------------------------------------");
				System.out.println("时间片"+timeSlice+":");
				System.out.println("当前运行的进程：");
				System.out.println(mp);
				System.out.println("当前的就绪队列：");
				for(int j = i + 1; j<num;j++) {
					System.out.println(processList.get(j));
				} 
			}
			
		}
		System.out.println("调度结束");
	}
}

运行结果（因为从文件读取数据，所以看不到数据输入）

请输入进程总数
请输入1号进程的进程名、优先数、到达时间、需要运行时间(空格隔开):
请输入2号进程的进程名、优先数、到达时间、需要运行时间(空格隔开):
请输入3号进程的进程名、优先数、到达时间、需要运行时间(空格隔开):
请输入4号进程的进程名、优先数、到达时间、需要运行时间(空格隔开):
请输入5号进程的进程名、优先数、到达时间、需要运行时间(空格隔开):
请输入调度算法:
时间片轮转调度算法
-----------------------------------------------------------------
时间片1:
当前运行的进程：
MyProcess [name=name1, priority=1, arrivalTime=3, needTime=4, runningTime=1, status=R]
当前的就绪队列：
MyProcess [name=name2, priority=9, arrivalTime=2, needTime=3, runningTime=0, status=W]
MyProcess [name=name3, priority=8, arrivalTime=9, needTime=5, runningTime=0, status=W]
MyProcess [name=name4, priority=1, arrivalTime=2, needTime=4, runningTime=0, status=W]
MyProcess [name=name5, priority=1, arrivalTime=8, needTime=3, runningTime=0, status=W]
-----------------------------------------------------------------
时间片2:
当前运行的进程：
MyProcess [name=name2, priority=8, arrivalTime=2, needTime=3, runningTime=1, status=R]
当前的就绪队列：
MyProcess [name=name3, priority=8, arrivalTime=9, needTime=5, runningTime=0, status=W]
MyProcess [name=name4, priority=1, arrivalTime=2, needTime=4, runningTime=0, status=W]
MyProcess [name=name5, priority=1, arrivalTime=8, needTime=3, runningTime=0, status=W]
MyProcess [name=name1, priority=1, arrivalTime=3, needTime=4, runningTime=1, status=W]
-----------------------------------------------------------------
时间片3:
当前运行的进程：
MyProcess [name=name3, priority=7, arrivalTime=9, needTime=5, runningTime=1, status=R]
当前的就绪队列：
MyProcess [name=name4, priority=1, arrivalTime=2, needTime=4, runningTime=0, status=W]
MyProcess [name=name5, priority=1, arrivalTime=8, needTime=3, runningTime=0, status=W]
MyProcess [name=name1, priority=1, arrivalTime=3, needTime=4, runningTime=1, status=W]
MyProcess [name=name2, priority=8, arrivalTime=2, needTime=3, runningTime=1, status=W]
-----------------------------------------------------------------
时间片4:
当前运行的进程：
MyProcess [name=name4, priority=0, arrivalTime=2, needTime=4, runningTime=1, status=R]
当前的就绪队列：
MyProcess [name=name5, priority=1, arrivalTime=8, needTime=3, runningTime=0, status=W]
MyProcess [name=name1, priority=1, arrivalTime=3, needTime=4, runningTime=1, status=W]
MyProcess [name=name2, priority=8, arrivalTime=2, needTime=3, runningTime=1, status=W]
MyProcess [name=name3, priority=7, arrivalTime=9, needTime=5, runningTime=1, status=W]
-----------------------------------------------------------------
时间片5:
当前运行的进程：
MyProcess [name=name5, priority=0, arrivalTime=8, needTime=3, runningTime=1, status=R]
当前的就绪队列：
MyProcess [name=name1, priority=1, arrivalTime=3, needTime=4, runningTime=1, status=W]
MyProcess [name=name2, priority=8, arrivalTime=2, needTime=3, runningTime=1, status=W]
MyProcess [name=name3, priority=7, arrivalTime=9, needTime=5, runningTime=1, status=W]
MyProcess [name=name4, priority=0, arrivalTime=2, needTime=4, runningTime=1, status=W]
-----------------------------------------------------------------
时间片6:
当前运行的进程：
MyProcess [name=name1, priority=0, arrivalTime=3, needTime=4, runningTime=2, status=R]
当前的就绪队列：
MyProcess [name=name2, priority=8, arrivalTime=2, needTime=3, runningTime=1, status=W]
MyProcess [name=name3, priority=7, arrivalTime=9, needTime=5, runningTime=1, status=W]
MyProcess [name=name4, priority=0, arrivalTime=2, needTime=4, runningTime=1, status=W]
MyProcess [name=name5, priority=0, arrivalTime=8, needTime=3, runningTime=1, status=W]
-----------------------------------------------------------------
时间片7:
当前运行的进程：
MyProcess [name=name2, priority=7, arrivalTime=2, needTime=3, runningTime=2, status=R]
当前的就绪队列：
MyProcess [name=name3, priority=7, arrivalTime=9, needTime=5, runningTime=1, status=W]
MyProcess [name=name4, priority=0, arrivalTime=2, needTime=4, runningTime=1, status=W]
MyProcess [name=name5, priority=0, arrivalTime=8, needTime=3, runningTime=1, status=W]
MyProcess [name=name1, priority=0, arrivalTime=3, needTime=4, runningTime=2, status=W]
-----------------------------------------------------------------
时间片8:
当前运行的进程：
MyProcess [name=name3, priority=6, arrivalTime=9, needTime=5, runningTime=2, status=R]
当前的就绪队列：
MyProcess [name=name4, priority=0, arrivalTime=2, needTime=4, runningTime=1, status=W]
MyProcess [name=name5, priority=0, arrivalTime=8, needTime=3, runningTime=1, status=W]
MyProcess [name=name1, priority=0, arrivalTime=3, needTime=4, runningTime=2, status=W]
MyProcess [name=name2, priority=7, arrivalTime=2, needTime=3, runningTime=2, status=W]
-----------------------------------------------------------------
时间片9:
当前运行的进程：
MyProcess [name=name4, priority=-1, arrivalTime=2, needTime=4, runningTime=2, status=R]
当前的就绪队列：
MyProcess [name=name5, priority=0, arrivalTime=8, needTime=3, runningTime=1, status=W]
MyProcess [name=name1, priority=0, arrivalTime=3, needTime=4, runningTime=2, status=W]
MyProcess [name=name2, priority=7, arrivalTime=2, needTime=3, runningTime=2, status=W]
MyProcess [name=name3, priority=6, arrivalTime=9, needTime=5, runningTime=2, status=W]
-----------------------------------------------------------------
时间片10:
当前运行的进程：
MyProcess [name=name5, priority=-1, arrivalTime=8, needTime=3, runningTime=2, status=R]
当前的就绪队列：
MyProcess [name=name1, priority=0, arrivalTime=3, needTime=4, runningTime=2, status=W]
MyProcess [name=name2, priority=7, arrivalTime=2, needTime=3, runningTime=2, status=W]
MyProcess [name=name3, priority=6, arrivalTime=9, needTime=5, runningTime=2, status=W]
MyProcess [name=name4, priority=-1, arrivalTime=2, needTime=4, runningTime=2, status=W]
-----------------------------------------------------------------
时间片11:
当前运行的进程：
MyProcess [name=name1, priority=-1, arrivalTime=3, needTime=4, runningTime=3, status=R]
当前的就绪队列：
MyProcess [name=name2, priority=7, arrivalTime=2, needTime=3, runningTime=2, status=W]
MyProcess [name=name3, priority=6, arrivalTime=9, needTime=5, runningTime=2, status=W]
MyProcess [name=name4, priority=-1, arrivalTime=2, needTime=4, runningTime=2, status=W]
MyProcess [name=name5, priority=-1, arrivalTime=8, needTime=3, runningTime=2, status=W]
-----------------------------------------------------------------
时间片12:
当前运行的进程：
MyProcess [name=name2, priority=6, arrivalTime=2, needTime=3, runningTime=3, status=R]
当前的就绪队列：
MyProcess [name=name3, priority=6, arrivalTime=9, needTime=5, runningTime=2, status=W]
MyProcess [name=name4, priority=-1, arrivalTime=2, needTime=4, runningTime=2, status=W]
MyProcess [name=name5, priority=-1, arrivalTime=8, needTime=3, runningTime=2, status=W]
MyProcess [name=name1, priority=-1, arrivalTime=3, needTime=4, runningTime=3, status=W]
-----------------------------------------------------------------
时间片13:
当前运行的进程：
MyProcess [name=name3, priority=5, arrivalTime=9, needTime=5, runningTime=3, status=R]
当前的就绪队列：
MyProcess [name=name4, priority=-1, arrivalTime=2, needTime=4, runningTime=2, status=W]
MyProcess [name=name5, priority=-1, arrivalTime=8, needTime=3, runningTime=2, status=W]
MyProcess [name=name1, priority=-1, arrivalTime=3, needTime=4, runningTime=3, status=W]
-----------------------------------------------------------------
时间片14:
当前运行的进程：
MyProcess [name=name4, priority=-2, arrivalTime=2, needTime=4, runningTime=3, status=R]
当前的就绪队列：
MyProcess [name=name5, priority=-1, arrivalTime=8, needTime=3, runningTime=2, status=W]
MyProcess [name=name1, priority=-1, arrivalTime=3, needTime=4, runningTime=3, status=W]
MyProcess [name=name3, priority=5, arrivalTime=9, needTime=5, runningTime=3, status=W]
-----------------------------------------------------------------
时间片15:
当前运行的进程：
MyProcess [name=name5, priority=-2, arrivalTime=8, needTime=3, runningTime=3, status=R]
当前的就绪队列：
MyProcess [name=name1, priority=-1, arrivalTime=3, needTime=4, runningTime=3, status=W]
MyProcess [name=name3, priority=5, arrivalTime=9, needTime=5, runningTime=3, status=W]
MyProcess [name=name4, priority=-2, arrivalTime=2, needTime=4, runningTime=3, status=W]
-----------------------------------------------------------------
时间片16:
当前运行的进程：
MyProcess [name=name1, priority=-2, arrivalTime=3, needTime=4, runningTime=4, status=R]
当前的就绪队列：
MyProcess [name=name3, priority=5, arrivalTime=9, needTime=5, runningTime=3, status=W]
MyProcess [name=name4, priority=-2, arrivalTime=2, needTime=4, runningTime=3, status=W]
-----------------------------------------------------------------
时间片17:
当前运行的进程：
MyProcess [name=name3, priority=4, arrivalTime=9, needTime=5, runningTime=4, status=R]
当前的就绪队列：
MyProcess [name=name4, priority=-2, arrivalTime=2, needTime=4, runningTime=3, status=W]
-----------------------------------------------------------------
时间片18:
当前运行的进程：
MyProcess [name=name4, priority=-3, arrivalTime=2, needTime=4, runningTime=4, status=R]
当前的就绪队列：
MyProcess [name=name3, priority=4, arrivalTime=9, needTime=5, runningTime=4, status=W]
-----------------------------------------------------------------
时间片19:
当前运行的进程：
MyProcess [name=name3, priority=3, arrivalTime=9, needTime=5, runningTime=5, status=R]
当前的就绪队列：
调度完毕