设计一:进程调度
设计目的:
进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用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; } }