调度算法是什么：
根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法。
先来先服务（First Come First Served，FCFS）
一种最简单的调度算法，在进程中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机。
最短作业优先（Shortest Job First，SJF）
每次从就绪队列中选出一个估计运行时间最短的作业，为它分配处理机。
SJF是改进版本的FCFS，在短作业优先前提下，短作业不必等待长作业，从而可以处理更多的短作业。
优先权调度算法
高响应比优先调度算法（Highest Response Ratio Next,HRRN）
HRRN是对FCFS和SJF的一种综合改进，FCFS只考虑等待时间而未考虑执行时间，SJF方式只考虑执行时间而未考虑等待时间，HRRN同时考虑作业的等待时长和估计执行时长，从中选出响应比最高的作业执行。
响应比R: (W+T)/T = 1+W/T
T:作业估计执行时长
W：作业等待时长
基本流程：每当进行作业调度时，系统计算每个作业的响应比R，选择其中R最大者执行
时间片轮转调度算法（RR，Round-Robin）
RR是一种最古老、最简单、最公平且使用最广的算法，每个进程会被分配一个时间片（进程的执行时间）。
基于FCFS算法，给予每个进程一个时间片，当一个进程的时间片用完时，将发生时钟中断，调度程序暂停运行进程，将进程送到就绪队列队尾，接着通过上下文执行就绪队列队首的进程。
系统将所有的就绪进程按照先来先服务的原则排成一个队列，每次调度时，让CPU为队列的首进程服务一个时间片（几ms 到几百ms），当时间片到了时，由一个计时器发出时钟中断请求，调度程序就以此信号停止进程，并将停止了的进程送往就绪队列的末尾。
如何确定进程的时间片：
- 系统对进程响应时间的要求
- 就绪队列进程的数量
- 系统的性能
多级反馈队列调度算法
目前被公认的一种较好的进程调度算法，Unix系统采取的是这种调度算法，可以满足短进程和长进程的要求。
-
设置多个就绪队列，从第一个队列到最后一个队列，优先权从高往低，时间片长度从成倍递增。
-
当新进程进入内存后，首先放在第一队列的队尾，按FCFS原则等待调度，如果在分配的时间片中进程可以完成，则准备撤离系统，否则调度到第二队列的队尾，再同样按FCFS的原则等待调度执行，如此下去。
-
当第1（i-1）队列均空时，才会调度第i队列中的进程运行。又有新的进程进入优先权较高的队列（第1（i-1）中的任何一个队列），则正在运行的进程放回到第i队列的队尾，此时处理机将为新进程服务。
各类调度算法优缺点
| 优点 | 缺点 | |
|---|---|---|
| FCFS | 利于长作业和CPU繁忙工作 | 不利于短作业和I/O繁忙工作 |
| SJF | 有利于系统的吞吐量。 | 长作业的运行得不到保障 |
| HRRN | 综合了FCFS和SJF算法的优点，兼顾了长进程和短进程的调度执行。 | 每次调度前需计算响应比，会给系统带来开销 |
| RR | 简单易行，平均响应时间短 | 不利于紧急作业，时间片会影响系统性能 |
代码实现：
# -*- coding: utf-8 -*-
"""
Created on Sun Nov 1 14:25:56 2020
@author: 11099
设数据是以表格的形式存在，包含的属性有进程名、到达时间、服务时间、开始时间、完成时间、周转时间、带权周转时间、平均值
所有算法均遵从以下步骤：
1.准备好数据(要求输入进程名、到达时间、服务时间，并准备好其他属性的变量)
2.实现算法(该步骤生成开始时间、完成时间、周转时间、带权周转时间、平均值的具体数值)
3.展示结果(都是两位有效数字的浮点数)
"""
import pandas as pd
# 定义调度算法的类
class schedule_algorithm:
# 初始化方法
def __init__(self, name, arrived_time, served_time):
self.data = pd.DataFrame({'到达时间': arrived_time, '服务时间': served_time}, dtype='float16', index=name, columns=['到达时间', '服务时间', '开始时间', '完成时间', '周转时间', '带权周转时间'])
self.data.sort_values(['到达时间', '服务时间'], inplace=True) # 先按到达时间从小到大排序，再按服务时间进行微调，意义在于同一到达时间可以先按服务时间进行调度
self.data.iloc[0, 2], self.data.iloc[0, 3], self.data.iloc[0, 4], self.data.iloc[0, 5] = self.data.iloc[0, 0], self.data.iloc[0, 0]+self.data.iloc[0, 1], self.data.iloc[0, 1], 1.
# 计算过程，单独写成一个方法方便算法的调用
def cal(self, code):
data, finish_time = self.data.copy(), self.data.iloc[0, 3].copy()
for idx in data.index[1:]:
ind = (data.loc[data['开始时间'].isnull(), '到达时间'] <= finish_time)
if ind.any():
exec(code)
data.loc[self.ind, '开始时间'],
data.loc[self.ind, '完成时间'],
data.loc[self.ind, '周转时间'],
data.loc[self.ind, '带权周转时间'],
finish_time = finish_time,
finish_time+data.loc[self.ind, '服务时间'],
finish_time+data.loc[self.ind, '服务时间']-data.loc[self.ind, '到达时间'],
(finish_time+data.loc[self.ind, '服务时间']-data.loc[self.ind, '到达时间'])/data.loc[self.ind, '服务时间'], finish_time+data.loc[self.ind, '服务时间']
else:
data.loc[idx, '开始时间'], data.loc[idx, '完成时间'], data.loc[idx, '周转时间'],
data.loc[idx, '带权周转时间'], finish_time = data.loc[idx, '到达时间'],
data.loc[idx, '到达时间']+data.loc[idx, '服务时间'],
data.loc[idx, '服务时间'], 1.,
data.loc[idx, '到达时间']+data.loc[idx, '服务时间']
data.loc['平均'] = data.mean()
return data.applymap('{:.2f}'.format)
# 先来先服务调度算法，基本思想是按进程或作业到达的前后顺序进行调度
def FCFS(self):
return self.cal('''self.ind = data.loc[ind[ind].index].index[0]''') # 返回第一个值进行计算，先来先服务调度
# 短作业优先是指对短作业或短进程优先调度的算法。设计目标是改进FCFS算法，减少作业或进程的平均周转时间
def SJF(self):
return self.cal('''self.ind = data.loc[ind[ind].index, '服务时间'].idxmin()''') # 返回第一个最小值，若多个服务时间相同，则相当于按先来先服务调度
# 响应比高者优先算法，基本思想是计算响应比(即1+等待时间/服务时间)，选择响应比最高的进程运行
def HRRN(self):
return self.cal('''self.ind = (1+(finish_time-data.loc[ind[ind].index, '到达时间'])/data.loc[ind[ind].index, '服务时间']).idxmax()''') # 返回第一个最大值，若多个响应比相同，则相当于按响应比中的先来先服务调度
# 时间片轮转调度算法
def RR(self):
pass
# 优先权调度算法
def Priority(self):
pass
# 多级反馈队列调度算法
def MFQ(self):
pass
# 只能在本文件中运行的代码块(即python的main文件名)
if __name__ == '__main__':
def input_data():
name = input('请输入程序名(空格隔开)：').split()
arrived_time = input('请输入到达时间(空格隔开)：').split()
served_time = input('请输入服务时间(空格隔开)：').split()
try:
s_a = schedule_algorithm(name, arrived_time, served_time)
return s_a
except:
raise Exception('数据输入错误！')
s_a = input_data()
while True:
print('
请选择调度算法(1~6 or y,n)：
1.先来先服务
2.短作业优先
3.响应比高者优先
4.时间片轮转
5.优先权
6.多级反馈队列
y.重新输入数据
n.退出')
option = input('输入：')
if option == 'n':
break
elif option == '1':
fcfs = s_a.FCFS()
print('对进程按先来先服务调度：
{}
{}'.format(fcfs, '-' * 30))
elif option == '2':
sjf = s_a.SJF()
print('对进程按短作业优先调度：
{}
{}'.format(sjf, '-' * 30))
elif option == '3':
hrrn = s_a.HRRN()
print('对进程按响应比高者优先调度：
{}
{}'.format(hrrn, '-' * 30))
elif option == '4':
print('对进程按时间片轮转调度：
{}
{}'.format(None, '-' * 30))
elif option == '5':
print('对进程按优先权调度：
{}
{}'.format(None, '-' * 30))
elif option == '6':
print('对进程按多级反馈队列调度：
{}
{}'.format(None, '-' * 30))
elif option == 'y':
s_a = input_data()
else:
print('命令输入错误！')
package test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
public class processMenu {
ArrayList<JCB> jcb;// 存放所有进程
LinkedList<JCB> link;// 存放已经进入队列的进程
ArrayList<JCB> new_jcb;// 存放按指定调度算法排序后的进程
JCB nowProess;// 当前应执行进程
public void init() {//初始化
jcb = new ArrayList<JCB>();
link = new LinkedList<JCB>();
new_jcb = new ArrayList<JCB>();
JCB p1 = new JCB("1", 0, 4, 3);
JCB p2 = new JCB("2", 1, 3, 2);
JCB p3 = new JCB("3", 2, 5, 3);
JCB p4 = new JCB("4", 3, 2, 1);
JCB p5 = new JCB("5", 4, 4, 5);
jcb.add(p1);
jcb.add(p2);
jcb.add(p3);
jcb.add(p4);
jcb.add(p5);
//先将jcb排序，便于下面的算法实现，就不需要再定义一个标识进程是否已到达的boolean,即无需每次都从头开始扫描jcb容器，
//而是用一个K记录下当前已经扫描到的位置，一次遍历即可，提高了算法效率。
Collections.sort(jcb, new compareAt_St());
}
public void FCFS() {//先来先服务算法
ProcessQueue pq = new ProcessQueue();//调用内部类
pq.EnqueueLast();//让最先到达的进程先入队
System.out.println("*****************************************************");
while (!link.isEmpty()) {//while(new_jcb.size()!=jcb.size())
pq.DisplayQueue();//打印当前队列中的进程
pq.Dequeue();//出队，一次一个
pq.EnqueueLast();//已到达的进程入队
}
}
public void SJF() {// 短作业优先算法
ProcessQueue pq = new ProcessQueue();
pq.EnqueueLast();
System.out.println("*****************************************************");
while (!link.isEmpty()) {
pq.DisplayQueue();//打印当前队列中的进程
pq.Dequeue();//出队，一次一个
pq.EnqueueLast();//已到达的进程入队
Collections.sort(link, new compareSt());//队列中的进程还需按服务时间长度进行排序
}
}
public void RR() {//时间片轮转调度算法
ProcessQueue pq = new ProcessQueue();
pq.EnqueueLast();
System.out.println("*****************************************************");
while (!link.isEmpty()) {
pq.DisplayQueue();//打印当前队列中的进程
pq.Dequeue(1);//出队，一次一个，因为上一轮出的得让刚到达的进程先进队列，所以没办法，进队操作只能也放在这个函数里了
}
}
public void HRN() {//最高响应比优先调度算法
ProcessQueue pq = new ProcessQueue();
pq.EnqueueLast();
System.out.println("*****************************************************");
while (!link.isEmpty()) {
pq.DisplayQueue();//打印当前队列中的进程
pq.Dequeue();//出队，一次一个
pq.EnqueueLast();//已到达的进程入队
Collections.sort(link, new comparePriority());//队列中的进程还需按响应比进行排序
}
}
class ProcessQueue {
int k = 0;// jcb中的进程遍历时的下标
int nowTime = 0;// 当前时间
double sliceTime;//轮转调度时间片
int i = 0;//记录当前出入队列的次数
public void EnqueueLast() {//进程首次入队，可一次进多个,从队尾进入
while (k < jcb.size()) {//当遍历完jcb中的所有进程时结束
if (jcb.get(k).arriveTime <= nowTime) {//已经到达的进程按到达时间先后进入队列
link.addLast(jcb.get(k));
k++;
} else {
break;//如果该进程还未入队，即先结束遍历，保留当前下标k值，注意：此处不要k--；
}
}
}
public void EnqueueFirst() {//进程首次入队，可一次进多个,从队首进入
while (k < jcb.size()) {//当遍历完jcb中的所有进程时结束
if (jcb.get(k).arriveTime <= nowTime) {//已经到达的进程按到达时间先后进入队列
link.addFirst(jcb.get(k));
k++;
} else {
break;//如果该进程还未入队，即先结束遍历，保留当前下标k值，注意：此处不要k--；
}
}
}
public void Dequeue() {//进程出队，一次只出一个
nowProess = link.removeFirst();//移除队列的队首元素并且返回该对象元素
nowProess.beginTime = nowTime;//计算开始时间，即为上一个进程的结束时间
nowProess.finshTime = nowProess.beginTime + nowProess.serveTime;//计算结束时间，该进程开始时间+服务时间
nowProess.roundTime = nowProess.finshTime - nowProess.arriveTime;//计算周转时间
nowProess.aveRoundTime = (double) nowProess.roundTime / nowProess.serveTime;//计算平均周转时间
nowTime = nowProess.finshTime;//获得结束时间，即当前时间，方便判断剩下的进程是否已到达
new_jcb.add(nowProess);//经处理过数据后加入new_jcb容器
for (int i = 0; i < link.size(); ++i) {
link.get(i).waitTime++;//所有进入等待队列的进程等待时间+1,此处只为最高响应比算法所用
}
}
public void Dequeue(double sliceTime) {//重载Dequeue方法，实现轮转调度算法的出队
nowProess = link.removeFirst();//移除队列的队首元素并且返回该对象元素
if (nowProess.firstTimeTag == false) {
/*轮转调度进程可能会多次反复进出队列，不像FCFS和SJF的进程只会进出一次，所以计算开始时间可以设个标志位，让每个进程在
* 第一次执行时记录一遍即可*/
nowProess.beginTime = nowTime;//进程开始执行的时间
nowProess.firstTimeTag = true;//计算第一次即可，下次无需更新计算
}
nowTime += sliceTime;//每次出队，用时一个时间片，更新当前时间
nowProess.clock += sliceTime;//更新当前出队列的进程已服务时间
if (nowProess.clock >= nowProess.serveTime) {
nowProess.finshTime = nowTime;//计算该进程完成时间
nowProess.roundTime = nowProess.finshTime - nowProess.arriveTime;//计算周转时间
nowProess.aveRoundTime = (double) nowProess.roundTime / nowProess.serveTime;//计算平均周转时间
new_jcb.add(nowProess);//经处理过数据后加入new_jcb容器
EnqueueFirst();//已到达的进程先入队
} else {
EnqueueFirst();//已到达的进程先入队
link.addLast(nowProess);//上一轮出的再紧接着进入队尾
}
}
public void DisplayQueue() {//队列中等候的进程
i++;
System.out.println("第" + i + "次队列中排队的进程：" + link);
}
}
public void printProcess() {
System.out.println("进程名 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间");
for (int i = 0; i < new_jcb.size(); ++i) {
System.out.println(" "+"P" + new_jcb.get(i).name + " " + new_jcb.get(i).arriveTime + " " +
new_jcb.get(i).serveTime + " " + new_jcb.get(i).beginTime + " " + new_jcb.get(i).finshTime +
" " + new_jcb.get(i).roundTime + " " + new_jcb.get(i).aveRoundTime);
}
new_jcb.clear();//清空new_jcb容器内的内容，方便存储各种算法的结果并展示
}
}
class compareSt implements Comparator<JCB> {// 按服务时间升序
public int compare(JCB arg0, JCB arg1) {
return arg0.serveTime - arg1.serveTime;
}
}
class compareAt_St implements Comparator<JCB> {// 按到达时间升序，若到达时间相同，按服务时间升序
public int compare(JCB o1, JCB o2) {
int a = o1.arriveTime - o2.arriveTime;
if (a > 0)
return 1;
else if (a == 0) {
return o1.serveTime > o2.serveTime ? 1 : -1;
} else
return -1;
}
}
class comparePriority implements Comparator<JCB> {//按响应比升序排序
public int compare(JCB o1, JCB o2) {
double r1 = (double) o1.waitTime / o1.serveTime;
double r2 = (double) o2.waitTime / o2.serveTime;
return r1 > r2 ? 1 : -1;
}
}
运行结果：
输入数据，并选择调度算法
先来先服务（FCFS）
短作业（SJF）
时间片轮转（RR）
高响应优先（HRRN）
总结
此次调度算法由我们小组成员共同完成，使用Java与Python语言模拟。
组内分工如下
| 姓名 | 负责 |
|---|---|
| 廖涛 | 博客园文档撰写 |
| 李威剑 | 使用Python编码实现 |
| 邓强 | 测试用例（Python） |
| 周颖 | 测试用例（Java） |
| 苏智勇 | 使用Java编码实现 |