计算机操作系统实验一：进程调度
[目的要求]
用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解．
[准备知识]
一、基本概念
1、进程的概念；
2、进程的状态和进程控制块；
3、进程调度算法；
二、进程调度
1、进程的状态
**
2、进程的结构——PCB
进程都是由一系列操作(动作)所组成，通过这些操作来完成其任务。因此，不同的进程，其内部操作也不相同。在操作系统中，描述一个进程除了需要程序和私有数据之外，最主要的是需要一个与动态过程相联系的数据结构，该数据结构用来描述进程的外部特性(名字、状态等)以及与其它进程的联系(通信关系)等信息，该数据结构称为进程控制块(PCB，Process Control Block)。进程控制块PCB与进程一一对应，PCB中记录了系统所需的全部信息、用于描述进程情况所需的全部信息和控制进程运行所需的全部信息。因此，系统可以通过进程的PCB来对进程进行管理。[试验内容] 设计一个有 N个进程共行的进程调度程序。
进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名（给定值）、优先数（给定值或者随机数）、到达时间（给定值）、需要运行时间（给定值）、已用CPU时间（计算）、进程状态（判断）等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。
进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。
重复以上过程，直到所要进程都完成为止。调度算法的流程图如下 : **
package Process;
public class JCPro {
String name;//进程名
int arriveTime = 0;//到达时间（调入CPU时间）
int serveTime;//服务时间（给定值，单位ms）
int priority;//优先级数字
int beginTime;//开始时间：为到达时间
int finshTime;//结束时间
int roundTime;//周转时间
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getArriveTime() {
return arriveTime;
}
public void setArriveTime(int arriveTime) {
this.arriveTime = arriveTime;
}
public int getServeTime() {
return serveTime;
}
public void setServeTime(int serveTime) {
this.serveTime = serveTime;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
public int getBeginTime() {
return beginTime;
}
public void setBeginTime(int beginTime) {
this.beginTime = beginTime;
}
public int getFinshTime() {
return finshTime;
}
public void setFinshTime(int finshTime) {
this.finshTime = finshTime;
}
public int getRoundTime() {
return roundTime;
}
public void setRoundTime(int roundTime) {
this.roundTime = roundTime;
}
}
package Process;
import java.util.ArrayList;
public class Cpu {
private int timeSlice = 20;//CPU一个时间片时长
//processArriveTime 记录进程的进入时间，每当运行一个进程，该数字需要相应增加
static int processArriveTime = 0;
public JCPro Cpu(JCPro jcPro){
//设置进程进入CPU的时间
jcPro.setArriveTime(processArriveTime);
//设置进程开始时间
jcPro.setBeginTime(processArriveTime);
//取得该进程需要运行的时间
int serverTime = jcPro.getServeTime();
//把该进程需要运行的时间和CPU时间片进行比较
//判断进程需要运行的时间和CPU时间片的大小
if (serverTime <= timeSlice) {
//如果进程需要运行的时间小于等于CPU一个时间片的时间
//则该进程直接完成，记录进程的进入时间的变量增加
jcPro.setFinshTime(processArriveTime + serverTime);
processArriveTime += serverTime;
//设置进程的周转时间roundTime，已经运行了多少时间
jcPro.setRoundTime(serverTime);
//设置运行完了的进程对象的需要运行的时间为0
jcPro.setServeTime(0);
System.out.println("【CPU时间片大小" + timeSlice + "】" + "; 进程名：" + jcPro.getName() +"; 进程进入CPU时间：" + jcPro.getArriveTime() + "; 进程需要运行的时间：" +
serverTime + "; 进程结束时间：" + jcPro.getFinshTime());
}else {
//进程需要运行的时间，大于一个CPU时间片的时间
//这里要进行把进程初始需要的运行时间，减去CPU单个时间片时间
//该进程剩余运行时间
int serverTimeResidue = serverTime - timeSlice;
//设置运行完了的进程对象还有需要运行的时间
jcPro.setServeTime(serverTimeResidue);
//进程优先级减1
jcPro.setPriority(jcPro.getPriority() - 1);
//记录进程的进入时间的变量增加
processArriveTime += timeSlice;
System.out.println("【CPU时间片大小" + timeSlice + "】" + "; 进程名：" + jcPro.getName() +"; 进程进入CPU时间：" + jcPro.getArriveTime() + "; 进程还需要运行的时间：" +
serverTimeResidue + "; 进程优先级数减1");
}
return jcPro;
}
}
package Process;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class ProcessSort {
public ArrayList<JCPro> ProcessSort(ArrayList<JCPro> notSortProcessList) {
//根据用户输入的进程优先级数对进程进行排序(根据数字降序排序，优先级数大的先运行)
//Map集合，用于存储进程的优先级数和该进程在未排序集合中的位置index
//第一个Integer是该进程在notSortProcessList中的index，第二个Integer是该进程的优先级数（不能重复）
Map<Integer, Integer> notSortIndexAndPriority = new HashMap<Integer, Integer>();
//排序后的进程集合
ArrayList<JCPro> alreadySortProcessList = new ArrayList<JCPro>();
for (int i = 0; i < notSortProcessList.size(); i++) {
//取出未排序集合中进程的优先级数
int priority = notSortProcessList.get(i).getPriority();
notSortIndexAndPriority.put(i, priority);
}
//HashMap根据Value值进行排序
List<Map.Entry<Integer, Integer>> list = new ArrayList<>(notSortIndexAndPriority.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
// TODO Auto-generated method stub
return o2.getValue().compareTo(o1.getValue());
}
});
for (Map.Entry sEntry : list) {
JCPro jcPro = notSortProcessList.get((int) sEntry.getKey());
alreadySortProcessList.add(jcPro);
}
return alreadySortProcessList;
// TODO Auto-generated constructor stub
}
}
package Process;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class ProcessL {
public void arCPU(ArrayList<JCPro> jcProArrayList){
//调用根据优先级数排序的函数
ProcessSort processSort = new ProcessSort();
//根据优先级数排序后的进程集合
ArrayList<JCPro> sortProcessList = processSort.ProcessSort(jcProArrayList);
//遍历排序后的进程集合
System.out.println("-------------就绪进程----------");
System.out.println("进程名 优先级 需要运行时间");
for (int i = 0; i < sortProcessList.size(); i++) {
String name = sortProcessList.get(i).getName();//进程名
int priority = sortProcessList.get(i).getPriority();//优先级
int serverTime = sortProcessList.get(i).getServeTime();//运行时间
System.out.println(name + " " + priority + " " + serverTime);
}
System.out.println("-------------运行进程----------");
Cpu cpu = new Cpu();
for (JCPro jcPro : sortProcessList) {
//进程第一次进入CPU
JCPro jcPro2 = cpu.Cpu(jcPro);
//进程剩余运行时间
int serverTime = jcPro2.getServeTime();
sortProcessList.remove(jcPro2);
if (serverTime > 0) {
sortProcessList.add(jcPro2);
}
if (sortProcessList.size() > 0) {
arCPU(sortProcessList);
}else {
System.out.println("结束");
}
}
System.out.println("---------------------------------------------");
}
}
package Process;
import java.util.ArrayList;
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
Scanner scanner1 = new Scanner(System.in);
System.out.println("请输入进程总数：");
//processNum为进程总数
int processNum = scanner1.nextInt();
Scanner scanner2 = new Scanner(System.in);
System.out.println("请输入进程名字，每个名字用一个空格隔开：");
String names = scanner2.nextLine();
//存储进程名字分割后的数组
String[] nameList = names.split(" ");
//输入每个进程需要运行的时间，以空格分开
//如10 20 10 30 50
Scanner scanner3 = new Scanner(System.in);
System.out.println("请输入每个进程的运行时间，并以空格分开，如（10 20 10 30 50）");
String proRunTimeStr = scanner3.nextLine();
//存储进程时间字符串分割后的数组
String[] proRunTimeStrList = proRunTimeStr.split(" ");
//进程运行时间的个数
int proRunTimeLength = proRunTimeStrList.length;
//int类型存储进程时间(每个进程需要运行的时间)的数组
int[] proRunTimeNumList = new int[proRunTimeLength];
//把字符串类型存储进程时间的元素，存储到int类型的数组中
for (int i = 0; i < proRunTimeLength; i++){
proRunTimeNumList[i] = Integer.parseInt(proRunTimeStrList[i]);
}
//输入每个进程的优先级数
System.out.println("请输入每个进程的优先级数，每个数用空格隔开，不能重复：");
Scanner scanner4 = new Scanner(System.in);
String priorityString = scanner4.nextLine();
//存储优先级数的数组
String[] priorityStrList = priorityString.split(" ");
//存储所有已就绪进程对象的集合
ArrayList<JCPro> jcProArrayList = new ArrayList<JCPro>();
//循环设置进程对象
for (int i = 0; i < processNum; i++) {
//进程名字
String name = nameList[i];
int serverTime = proRunTimeNumList[i];
int priority = Integer.parseInt(priorityStrList[i]);
JCPro jcPro = new JCPro();
jcPro.setName(name);
jcPro.setServeTime(serverTime);
jcPro.setPriority(priority);
//把设置完毕的进程存入存储就绪进程的集合
jcProArrayList.add(jcPro);
}
ProcessL processL = new ProcessL();
processL.arCPU(jcProArrayList);
}
}
运行结果