JAVA 进程调度(先来先服务、短作业优先、时间片轮转、优先级算法)

时间:2021-12-08 21:13:49

设计一:进程调度

  设计目的:    

  进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用CPU的方法。在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本设计模拟在单处理器情况下的进程调度,目的是加深对进程调度工作的理解,掌握不同调度算法的优缺点。

设计内容:

设计程序模拟单处理机系统中的进程调度算法,在短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中选择两种实现。

每个进程由一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等。

进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间。

进程的运行时间以时间片为单位进行计算。

每个进程的状态可以是就绪W(Wait)、运行R(Run)或完成F(Finish)3中状态之一。

以下是最高优先级优先算法思想:

 

就绪进程获得CPU后都只能运行一个时间片,用已占用CPU时间加1来表示。

如果运行一个时间片后,进程的已占用CPU时间已达到所需要的运行时间,则撤销该进程,如果运行一个时间片后进程的已占用CPU时间还未达到所需要的运行时间,也即进程还需要继续运行,此时应将进程的优先数减1(即降低一级),然后把它插入就绪队列等待CPU。

每进行一次调度程序都打印一次运行进程、就绪队列以及各个进程的PCB,以便进行检查。

重复以上过程,直到所有进程都完成为止。

import java.util.Scanner;
public class Hello {
	public static void main(String [] args){
		Scanner reader=new Scanner(System.in);	
		System.out.println("请输入算法:1、时间片轮转调度算法.2、优先级调度算法.3、短作业优先调度算法.");
		int input=reader.nextInt();
		switch(input)
		{
			case 1:
				RR rr=new RR();
				rr.Way();					
				break;
			case 2:
				HPF hpf=new HPF();
				hpf.Way();
				break;
			case 3:
				SJF sjf=new SJF();
				sjf.Way();
				break;
			default:
				System.out.println("非法输入");
				break;			
		}
		reader.close();		
	}
}
class SJF{
	void Way(){
		int i,j;
		int input;       //进程数
		Scanner reader=new Scanner(System.in);		
		System.out.println("请输入进程数");
		input=reader.nextInt();
		PCB[] pcb=new PCB[input];
		Queue Wait=new Queue();     //等待队列
		Queue Ready=new Queue();     //就绪队列
		int CPUTIME=3;       //设置时间片为3
		int a;
		int b,c;
		int t1;
		System.out.println("请依次输入进程名、到达时间、需要运行时间");
		for(i=0;i<input;i++){	
			a=reader.nextInt();
			b=reader.nextInt();
			c=reader.nextInt();
			pcb[i]=new PCB(a,b,c);
		}
		PCB t=new PCB();
		for(i=0;i<input-1;i++){    //排列,先到达的排在前面,如果到达的时间相同,则需要运行的时间更短的排在前面
			for(j=0;j<input-1;j++){
				if(pcb[j].AT>pcb[j+1].AT)
				{
					t=pcb[j];pcb[j]=pcb[j+1];pcb[j+1]=t;
				}
				else if(pcb[j].AT==pcb[j+1].AT){
					if(pcb[j].RT>pcb[j+1].RT)
					{
						t=pcb[j];pcb[j]=pcb[j+1];pcb[j+1]=t;
					}
				}
			}
		}
		System.out.println("进程名  到达时间  需要运行时间");   //输出排序后的进程
		for(i=0;i<input;i++){	
			System.out.print("  "+pcb[i].name+"     ");
			System.out.print(pcb[i].AT+"      ");
			System.out.println(pcb[i].RT);
		}
		int nowtime=pcb[0].AT;  //现在的时间为第一个进程到达的时间
		for(i=0;i<input;i++){
			if(pcb[i].AT==nowtime) {         //如果现在的时间大于到达时间就进入就绪队列
				Ready.come(i);                //否则进入等待队列
				pcb[i].State='W';
			}
			else {                           
				Wait.come(i);	
				pcb[i].State='W';
			}
		}
		while( Wait.isexit()==1 || Ready.isexit()==1 ) {
			while(Ready.isexit()==1) {
				pcb[Ready.a[Ready.F]].RT=pcb[Ready.a[Ready.F]].RT-CPUTIME;   //一个时间片结束后,进程需要的时间减少
				pcb[Ready.a[Ready.F]].CPUT++;                              //已占用CPU时间+1
				pcb[Ready.a[Ready.F]].State='R';                           //状态先置为运行
				if(pcb[Ready.a[Ready.F]].RT>0) {                           //如果进程需要的时间大于0,则进入就绪队列
					Ready.come(Ready.a[Ready.F]);	                         //否则把进程需要的时间置为0、把状态置为结束					
				}
				else {                                                   
					pcb[Ready.a[Ready.F]].RT=0;
					pcb[Ready.a[Ready.F]].State='F';
					Ready.out();
				}
				System.out.println("现在的时间为:"+nowtime);
				System.out.println("进程名  到达时间  需要运行时间  已占用CPU时间  进程状态");  //输出进程名、到达时间、需要运行时间、 已占用CPU时间、进程状态
				for(i=0;i<input;i++){	
					System.out.print("  "+pcb[i].name+"     ");
					System.out.print(pcb[i].AT+"      ");
					System.out.print(pcb[i].RT+"        ");
					System.out.print(pcb[i].CPUT+"         ");
					System.out.println(pcb[i].State);
				}
				if(pcb[Ready.a[Ready.F]].State=='R'){
					pcb[Ready.a[Ready.F]].State='W';
					Ready.out();
				}				
				nowtime=nowtime+CPUTIME;                      //现在的时间为一个时间片后
				for(i=Wait.F;i<Wait.L;i++) {                //如果等待队列里的进程的等待条件满足了,就进入就绪队列
					if(nowtime>=pcb[Wait.a[i]].AT) {
						Ready.come(Wait.a[i]);
						Wait.out();						
					}					
				}
				for(i=Ready.F;i<Ready.L-1;i++) {                //排列,需要运行的时间更短的排在前面
					for(j=Ready.F;j<Ready.L-1;j++){
						if(pcb[Ready.a[j]].RT>pcb[Ready.a[j+1]].RT)
						{
							t1=Ready.a[j];Ready.a[j]=Ready.a[j+1];Ready.a[j+1]=t1;
						}
					}
				}		
			}
			System.out.println("现在的时间为:"+nowtime);       
			nowtime=nowtime+CPUTIME;                         //现在的时间为一个时间片后
			for(i=Wait.F;i<Wait.L;i++) {                    //如果等待队列里的进程的等待条件满足了,就进入就绪队列
				if(nowtime>=pcb[Wait.a[i]].AT) {
					Ready.come(Wait.a[i]);
					Wait.out();	
				}
			}
			for(i=Ready.F;i<Ready.L-1;i++) {                //排列,需要运行的时间更短的排在前面
				for(j=Ready.F;j<Ready.L-1;j++){
					if(pcb[Ready.a[j]].RT<pcb[Ready.a[j+1]].RT)
					{
						t1=Ready.a[j];Ready.a[j]=Ready.a[j+1];Ready.a[j+1]=t1;
					}
				}
			}		
		}
		reader.close();
	}
}
class RR{
	void Way(){
		int i,j;
		int input;       //进程数
		Scanner reader=new Scanner(System.in);		
		System.out.println("请输入进程数");
		input=reader.nextInt();
		PCB[] pcb=new PCB[input];
		Queue Wait=new Queue();     //等待队列
		Queue Ready=new Queue();     //就绪队列
		int CPUTIME=3;       //设置时间片为3
		int a;
		int b,c;
		System.out.println("请依次输入进程名、到达时间、需要运行时间");
		for(i=0;i<input;i++){	
			a=reader.nextInt();
			b=reader.nextInt();
			c=reader.nextInt();
			pcb[i]=new PCB(a,b,c);
		}
		PCB t=new PCB();
		for(i=0;i<input-1;i++){    //排列,先到达的排在前面
			for(j=0;j<input-1-i;j++){
				if(pcb[j].AT>pcb[j+1].AT)
				{
					t=pcb[j];pcb[j]=pcb[j+1];pcb[j+1]=t;
				}
			}
		}
		System.out.println("进程名  到达时间  需要运行时间");   //输出排序后的进程
		for(i=0;i<input;i++){	
			System.out.print("  "+pcb[i].name+"     ");
			System.out.print(pcb[i].AT+"      ");
			System.out.println(pcb[i].RT);
		}
		int nowtime=pcb[0].AT;  //现在的时间为第一个进程到达的时间
		for(i=0;i<input;i++){
			if(pcb[i].AT==nowtime) {         //如果现在的时间大于到达时间就进入就绪队列
				Ready.come(i);                //否则进入等待队列
				pcb[i].State='W';
			}
			else {                           
				Wait.come(i);	
				pcb[i].State='W';
			}
		}
		while( Wait.isexit()==1 || Ready.isexit()==1 ) {
			while(Ready.isexit()==1) {
				pcb[Ready.a[Ready.F]].RT=pcb[Ready.a[Ready.F]].RT-CPUTIME;   //一个时间片结束后,进程需要的时间减少
				pcb[Ready.a[Ready.F]].CPUT++;                              //已占用CPU时间+1
				pcb[Ready.a[Ready.F]].State='R';                           //状态先置为运行
				if(pcb[Ready.a[Ready.F]].RT>0) {                           //如果进程需要的时间大于0,则进入就绪队列
					Ready.come(Ready.a[Ready.F]);	                         //否则把进程需要的时间置为0、把状态置为结束					
				}
				else {                                                   
					pcb[Ready.a[Ready.F]].RT=0;
					pcb[Ready.a[Ready.F]].State='F';
					Ready.out();
				}
				System.out.println("现在的时间为:"+nowtime);
				System.out.println("进程名  到达时间  需要运行时间  已占用CPU时间  进程状态");  //输出进程名、到达时间、需要运行时间、 已占用CPU时间、进程状态
				for(i=0;i<input;i++){	
					System.out.print("  "+pcb[i].name+"     ");
					System.out.print(pcb[i].AT+"      ");
					System.out.print(pcb[i].RT+"        ");
					System.out.print(pcb[i].CPUT+"         ");
					System.out.println(pcb[i].State);
				}
				if(pcb[Ready.a[Ready.F]].State=='R'){
					pcb[Ready.a[Ready.F]].State='W';
					Ready.out();
				}				
				nowtime=nowtime+CPUTIME;                      //现在的时间为一个时间片后
				for(i=Wait.F;i<Wait.L;i++) {                //如果等待队列里的进程的等待条件满足了,就进入就绪队列
					if(nowtime>=pcb[Wait.a[i]].AT) {
						Ready.come(Wait.a[i]);
						Wait.out();						
					}					
				}
			}
			System.out.println("现在的时间为:"+nowtime);        //现在的时间为一个时间片后
			nowtime=nowtime+CPUTIME;                         //如果等待队列里的进程的等待条件满足了,就进入就绪队列
			for(i=Wait.F;i<Wait.L;i++) {
				if(nowtime>=pcb[Wait.a[i]].AT) {
					Ready.come(Wait.a[i]);
					Wait.out();	
				}
			}
		}
		reader.close();
	}
}
class HPF{
	void Way() {
		int i,j;
		Scanner reader=new Scanner(System.in);
		int input;       //进程数
		System.out.println("请输入进程数");
		input=reader.nextInt();
		PCB[] pcb=new PCB[input];
		Queue Wait=new Queue();     //等待队列
		Queue Ready=new Queue();     //就绪队列
		int CPUTIME=3;       //设置时间片为3
		int a;
		int b,c,d;
		int t1;
		System.out.println("请依次输入进程名、到达时间、需要运行时间、优先级");
		for(i=0;i<input;i++){	
			a=reader.nextInt();
			b=reader.nextInt();
			c=reader.nextInt();
			d=reader.nextInt();
			pcb[i]=new PCB(a,b,c,d);
		}
		PCB t=new PCB();
		for(i=0;i<input-1;i++){    //排列,先到达的排在前面,如果到达的时间相同,则优先级高的排在前面
			for(j=0;j<input-1;j++){
				if(pcb[j].AT>pcb[j+1].AT)
				{
					t=pcb[j];pcb[j]=pcb[j+1];pcb[j+1]=t;
				}
				else if(pcb[j].AT==pcb[j+1].AT){
					if(pcb[j].level<pcb[j+1].level)
					{
						t=pcb[j];pcb[j]=pcb[j+1];pcb[j+1]=t;
					}
				}
			}
		}
		System.out.println("进程名  到达时间  需要运行时间  优先级");   //输出排序后的进程
		for(i=0;i<input;i++){	
			System.out.print("  "+pcb[i].name+"     ");
			System.out.print(pcb[i].AT+"      ");
			System.out.print(pcb[i].RT+"        ");
			System.out.println(pcb[i].level);
		}
		int nowtime=pcb[0].AT;  //现在的时间为第一个进程到达的时间
		for(i=0;i<input;i++){
			if(pcb[i].AT==nowtime) {         //如果现在的时间等于到达时间就进入就绪队列
				Ready.come(i);                //否则进入等待队列
				pcb[i].State='W';
			}
			else {                           
				Wait.come(i);	
				pcb[i].State='W';
			}
		}
		while( Wait.isexit()==1 || Ready.isexit()==1 ) {       //当等待队列和就绪队列还有进程时
			while(Ready.isexit()==1) {
				pcb[Ready.a[Ready.F]].RT=pcb[Ready.a[Ready.F]].RT-CPUTIME;   //一个时间片结束后,进程需要的时间减少
				pcb[Ready.a[Ready.F]].CPUT++;                              //已占用CPU时间+1
				pcb[Ready.a[Ready.F]].level--;           //每运行一次,优先级减一                  
				pcb[Ready.a[Ready.F]].State='R';                           //状态先置为运行
				if(pcb[Ready.a[Ready.F]].RT>0) {                           //如果进程需要的时间大于0,则进入就绪队列
					Ready.come(Ready.a[Ready.F]);	                         //否则把进程需要的时间置为0、把状态置为结束
				}
				else {                                                   
					pcb[Ready.a[Ready.F]].RT=0;
					pcb[Ready.a[Ready.F]].State='F';
				}
				System.out.println("现在的时间为:"+nowtime);
				System.out.println("进程名  到达时间  需要运行时间  优先级  已占用CPU时间  进程状态");  //输出进程名、到达时间、需要运行时间、优先级、 已占用CPU时间、进程状态
				for(i=0;i<input;i++){	
					System.out.print("  "+pcb[i].name+"     ");
					System.out.print(pcb[i].AT+"      ");
					System.out.print(pcb[i].RT+"        ");
					System.out.print(pcb[i].level+"        ");
					System.out.print(pcb[i].CPUT+"       ");
					System.out.println(pcb[i].State);
				}
				if(pcb[Ready.a[Ready.F]].State=='R')
					pcb[Ready.a[Ready.F]].State='W';
				Ready.out();
				nowtime=nowtime+CPUTIME;                      //现在的时间为一个时间片后
				for(i=Wait.F;i<Wait.L;i++) {                //如果等待队列里的进程的等待条件满足了,就进入就绪队列
					if(nowtime>=pcb[Wait.a[i]].AT) {
						Ready.come(Wait.a[i]);
						Wait.out();						
					}					
				}
				for(i=Ready.F;i<Ready.L-1;i++) {                //排列,优先级高的排在前面
					for(j=Ready.F;j<Ready.L-1;j++){
						if(pcb[Ready.a[j]].level<pcb[Ready.a[j+1]].level)
						{
							t1=Ready.a[j];Ready.a[j]=Ready.a[j+1];Ready.a[j+1]=t1;
						}
					}
				}			
			}
			System.out.println("现在的时间为:"+nowtime);
			nowtime=nowtime+CPUTIME;                     //现在的时间为一个时间片后
			for(i=Wait.F;i<Wait.L;i++) {                //如果等待队列里的进程的等待条件满足了,就进入就绪队列
				if(nowtime>=pcb[Wait.a[i]].AT) {
					Ready.come(Wait.a[i]);
					Wait.out();						
				}					
			}
			for(i=Ready.F;i<Ready.L-1;i++) {                //排列,优先级高的排在前面
				for(j=Ready.F;j<Ready.L-1;j++){
					if(pcb[Ready.a[j]].level<pcb[Ready.a[j+1]].level)
					{
						t1=Ready.a[j];Ready.a[j]=Ready.a[j+1];Ready.a[j+1]=t1;
					}
				}
			}			
		}
		reader.close();
	}
}
class PCB{       //进程的pcb
	int name;    //进程名
	int level;   //优先级
	int AT;         //到达时间
	int RT;	 		//需要运行时间
	int CPUT=0;		//已用CPU时间
	char State;     //进程状态
	PCB(){}
	PCB(int a,int b,int c){
		name=a;
		AT=b;
		RT=c;
	}
	PCB(int a,int b,int c,int d){
		name=a;
		AT=b;
		RT=c;
		level=d;
	}
}
class Queue{      //队列
	int a[]=new int[1000];
	int F=0;
	int L=0;
	void come(int num){
		if(L>=999)
			System.out.println("队满");
		a[L]=num;
		L++;	
	}
	void out(){
		if(F>L)
			System.out.println("队空");
		F++;
	}
	int isexit() {
		if(L>F)
			return 1;
		else
			return 0;
	}
}