实验目的：

  1. 用C++编写一个进程调度算法模拟程序。

  2. 对现有进程调度算法进行理解，并对其进行优化。

实验要求：

  1. 通过动态优先权轮转调度算法的学习，理解和掌握动态优先权以及轮转调度算法的思想、 设计与实现方法。

  2. 实现高优先权优先调度或轮转调度算法的数据结构设计、算法流程设计、模拟实现

与验证。

算法设计注意点:

在资源一定的情况下，调度算法需要在吞吐量，平均响应时间，公平性，调度引起的额外开销以及权重等方面做权衡，接下来对算法性能适用场所的讨论都是基于此的，因此对于不同的场景有不同适用的算法。

调度算法：

  1. 先进先出算法：

顾名思义也就是满足先进先出（First-In-First-Out,FIFO）规则的进程调度算法，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。并且不会设计抢占，看上去似乎很公平，这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业，平均响应时间也会很长。

优点：

· 公平性：满足先来后到的顺序且是非抢占式的也就是不会插队。

· 最少任务切换开销：因为先来的先完成所以不会涉及任务执行过程中发生切换也就不会有切换开销开销为0.

· 最大的吞吐量：没有任务切换开销，在其他一定的情况下，吞吐量肯定最大。

缺点：

· 平均响应时间高：假如队头是一个1000ms的任务，队列其他的均为10ms左右的任务，但是因为队头保证先完成在进行剩下的，那么后面的任务都要等待起码1000ms才能进行，这就导致了平均响应时间的增大。

适用场景：队列中任务耗时差不多

  1. 最短耗时任务优先算法：

最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。但这个是抢占式的，也就是如果这时候新增了一个耗时比现在进行的任务剩余耗时短的，那么就会执行这个新的所需耗时短的任务，也就会导致耗时长的任务长时间不会被调用。

优点：

平均响应时间低：因为保证进行的是所需耗时最短的任务那么平均耗时一定最短。

缺点：

不公平：他凭什么后来居上！

额外开销大：因为是抢占式也就是会频繁任务切换，调度额外开销大。

最重要的一点几乎没有适用场景，因为正常情况下你是不知道一个进程所需要的时间，不过你可以设计一些启发式算法去写一个估计函数，去大概预测这个时间。

  1. 时间片轮转算法：

最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法。接下来说的几个时间调度算法都是基于此算法进行的优化。

给队列中的每个任务一个时间片，第一个任务先执行，时间片到了之后，将此任务放到队列尾部，切换到下个任务执行，这样能解决SJF中耗时长任务饥饿的问题。算法介于FIFO和SJF之间，若时间片足够大，则退化到FIFO，若分片足够小（假设不考虑任务切换的开销），则任务的完成时间顺序是以耗时从小到大排列（相比SFJ，任务执行的绝对时间会长，取决于队列中任务的个数）。

优点：

每个任务都能够得到公平的调度

耗时短的任务即使落在耗时长的任务后面，也能够较快的得到调度执行

缺点：

任务切换引起的调度开销较大，需要多次切换任务上下文（特别是CPU的Cache，多次切换容易导致Cache完全不命中，需要重新从内存加载，这个非常耗时）

· 时间片不太好设置（若设置短了，调度开销大，若设置长了，极端情况是退化到FIFO*）*

动态优先权轮转调度算法及优先队列优化：

前面所说的轮转调度算法有个假设性前提，那就是所有进程都一样重要，因此每个进程执行相同时间片时间，这样看上去是公平的，但实际上我们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。

而最高优先级调度算法分为两种，一种是静态优先级，也就是创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化。另外一种就是重点要说的动态优先级。

动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级，但是实际上你想去让等待进程的优先级随着等待时间增高，不如让正在进行的进程优先级降低，因为正在进行的进程是很好被操作的，而且你要去处理等待进程就意味着额外开销，并且不好去处理，所以相对来说等待进程优先增加就等于正在进行的进程优先级降低。

但是这时候又会涉及一个问题也就是是否抢占，意思就是如果现在队伍中出现一个进程优先级比正在进行的进程优先级要高的进程是否要结束这个正在进行的进程去进行这个新的优先级最高的进程，在我看来，我认为非抢占式是合理的，但不意味着抢占式就不合理我一开始也说了，只有最合适，没有哪个是最好的，我采取非抢占式的原因就是，当你进行抢占的时候就会意味着额外开销，并且正在进行的进程他优先级也不低，他能进行肯定有他能进行的理由（也就是优先级高但不是最高），与其打断他的进行最选择优先级最高的来达成看上去最优的操作（因为从设计思路出发来看应该一直处理优先级最高的），但实际上开销带来的损失不一定让其是最优的。

算法实现优化：

说完了原理和思路，我说一下我的实现和优化，我看了很多网上别人的代码，大多都采取了排序这一方法来进行动态优先处理，但是每次排序都意味着O(NlogN)的时间复杂度，而且这还是理论最优的（《算法导论》证明过一切比较式的排序时间复杂度下限是O(NlogN)。但是他们这么处理是因为他们处理优先级的时候选择的是让等待时间长的进程优先级增加，所以要对所有的进程进行排序，但是我这里采用的是优先队列去优化，也就是大根堆（优先级最高的在堆顶），我刚刚也说了，我只处理正在进行的进程，让其优先级降低，这样也能使算法实现，并且更好操作，也就是每次执行进程的时候，我让其优先级降低，然后执行一次pushdown()操作，时间复杂度是(MlogN)，M一点比N小，因为M是正在进行的线程N是总线程数。而且这也解决了一个问题就是，优先级高的会一直在堆顶，那他执行完一个时间片还是执行他但这样就不会了因为他优先级下去了。

img

接下来的操作就很简单了，每次取出堆顶，然后运行一个时间片，如果进程运行结束就弹出队列，否则更改优先级重新入队

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
struct Node{
	int priority;//设置优先级  
	string name;
	int time;//根据优先级设置时间 
	int startTime;//开始时间 
	int endTime;//结束时间 
	//通过开始和结束时间我知道其执行的时间，优先级
	//减去这个执行时间+x(这个x要满足当前堆顶减去这个值后要比所有进程
	//优先级都要小很简单记录一下最小的就行了）便是更新后的优先级然后pushdown入队 
	bool operator < (const Node &a) const//重载运算符 
    {
        return priority>a.priority;
    }
	
};
priority_queue <Node,vector<Node> > q;
void print(Node x,bool flag){
	cout<<"进程名称："<<x.name<<" "<<x.priority<<' ';
	if(flag) cout<<"正在进行";
	else cout<<"运行完毕";
	cout<<endl;
}
int time,Min=0x3f3f3f3f;//time是时间片大小一般为25~50ms,Min为当前队列最小优先级 
vector <Node> v;
void solve(){
	bool flag=true;
	while(q.size()){
		Node x=q.top();//取出堆顶
		if(x.endTime<=time){
			print(x,!flag);//自定义输出函数 
			q.pop();
		} 
		else{
			x.priority=(Min-time);//自动进行pushdown 
			Min=min(x.priority,Min);
			x.endTime-=time;
			print(x,flag);
			q.pop();
			q.push(x);
		}
	}
	
}
bool cmp(Node x,Node y){
	return x.startTime<y.startTime;
}
int main(){
	ios::sync_with_stdio(false);
	cout<<"输入进程数："<<endl;
	int n;
	cin>>n;
	cout<<"设置时间片时间："<<endl; 
	cin>>time;
	Node x;
	cout<<"输入进程信息："<<endl; 
	cout<<"进程名称："<<"	"<<"进程优先级"<<"	"<<"进程开始时间："
	<<"	 "<<"进程结束时间："<<endl;
	for(int i=0;i<n;i++){
		cin>>x.name;
		cin>>x.priority;
		cin>>x.startTime;
		cin>>x.endTime;
		v.push_back(x);
		Min=min(Min,x.priority);
	} 
	int cou=1;
	sort(v.begin(),v.end());
	for(auto it : v){
		q.push(it);
	}	
	solve();
	return 0;
}

结果展示：

img

img

总结：

  1. 通过此次设计优化算法大大加深了我对算法以及设计算法出发点和数据结构的理解和运用。

  2. 学习并理解了理解和掌握动态优先权以及轮转调度算法的思想、 设计与实现方法和进程概念。