进程调度算法FCFS和RR

一、 实验题目
本次试验要求编写的是进程调度中的FCFS算法和RR算法（轮转法）。
FCFS算法：最简单的CPU调度算法，采取先到先服务的规则，不存在进程优先级之说，也不管进程服务时间的长短，只有前面的进程完成或者阻塞后面的进程才会开始处理。这种算法不利于短进程，因为短进程要等待很久，而CPU繁忙进程则比较适合这种调度算法。
RR算法：这是一种轮询算法，每次将时间片给队首的进程去使用，如果该进程在时间片内结束的话，就切换到下一进程；如果时间片用完该进程仍未结束，把处理器给下一进程，该进程排到就绪队列队尾等待下一次被分配处理器；
当时间片被分配的特别长的话，RR会变为的FCFS算法，当时间片非常短的话，就会成为一种均等分配的算法，适用于IO繁忙型调度。
我们可以看一下示意图
题目是：

下面是我画的各个时间段的各种算法的执行情况，今天我们主要讲述FCFS和RR两种，其余两种类比也可以实现

二、 数据结构及符号说明
因为这两种算法中都有一个优先的顺序，FCFS中优先级是到达的时刻，RR中优先级也是到达的时间，因此我在算法中用的是优先队列priority_queue<proc,vector,cmp> q;
队列中元素是一个结构体，容器为vector，优先定义方式为自己定义的cmp(见下)
 
struct cmp
{
bool operator()(proc a,proc b)
{
return a.arrive_time>b.arrive_time; //到达时间小的，优先级高
}
};
每次添加结点的时候都会自动排序将到达时间最小的进程调到队首
三、 源代码
FCFS：

#include <iostream> #include <iomanip> #include <queue> using namespace std; //进程结构体，包含时间长度，进程ID，到达时间，结束时间和开始时间等几个属性 struct proc {int time,arrive_time,end_time,start_time;char name; }; //重新定义优先队列的规则 struct cmp {bool operator()(proc a,proc b){return a.arrive_time>b.arrive_time; //到达时间小的，优先级高 } }; //进程个数 int n; //当前时间 int current_time; int main() {priority_queue<proc,vector<proc>,cmp> q;//声明优先队列对象qcin>>n;proc p;for(int i=0;i<n;i++){ cin>>p.name>>p.arrive_time>>p.time;q.push(p);}current_time=0;cout<<"Process_ID Arrive_Time Start_Time Length End_Time Revolve_Time Right_Time"<<endl; //当队列非空的时候，说明尚有进程未处理完毕，进入循环 while(!q.empty()){p=q.top(); //取优先级最高的进程进入处理器（即到达时间最早的进程） q.pop();//当优先级最高的进程到达时间还高于当前时间，我们就让当前时间往后加 while(current_time<p.arrive_time){current_time++;}//如果当前时间比优先级最高的要大，那么就可以进行处理 if(current_time>=p.arrive_time){p.start_time=current_time; //设置p进程的开始时间 p.end_time=p.start_time+p.time; //设置进程的结束时间 current_time=p.end_time; //当前时间往后移 }//设置输出格式 cout<<setfill(' ')<<setw(5)<<p.name;cout<<setw(11)<<p.arrive_time;cout<<setw(11)<<p.start_time;cout<<setw(10)<<p.time;cout<<setw(8)<<p.end_time;cout<<setw(11)<<p.end_time-p.arrive_time;cout<<setw(14)<<setiosflags(ios::fixed)<<setprecision(2)<<(double)(p.end_time-p.arrive_time)/p.time<<endl;}return 0; }

RR：

#include <iostream> #include <iomanip> #include <queue> using namespace std; int n; int time_slice; //时间片 int current_time; //当前时间 struct proc{int arr_time; //第一次入队的时间 int arrive_time; //每一次的到达时间 int time; //剩余需要的时间 int start_time; //开始的时间 int end_time; //结束的时间 int haoshi; //总共需要的时间 char a; //进程ID }; //重新定义队列的优先级 struct cmp{bool operator()(proc a,proc b){return a.arrive_time>=b.arrive_time;} }; int main() {priority_queue<proc,vector<proc>,cmp> q;cin>>n>>time_slice; //输入时间片 current_time=0; //初始化当前时间片 proc p;for(int i=0;i<n;i++){cin>>p.a>>p.arrive_time>>p.time;p.start_time=-1;p.end_time=-2;p.arr_time=p.arrive_time;p.haoshi=p.time;q.push(p);}cout<<"Process_ID Arrive_Time Start_Time Length End_Time Revolve_Time Right_Time"<<endl; while(!q.empty()) //只要队列不为空，就说明还有进程未处理完毕{p=q.top(); //获取队首元素q.pop(); //将队首元素出队列//若是当前时间比队首进程的到达时间还小，那么我们就让当前时间自增while(current_time<p.arrive_time) {current_time++;}//如果start_time为-1，说明这个变量没被赋值，我们就给他赋值，标志该进程开始处理了if(p.start_time==-1) p.start_time=current_time;if(time_slice>=p.time) //如果当前时间片大于进程p所需要的时间p.time，那么我们可以在本次时间片之内结束该进程 {current_time+=p.time; //当前时间往后加 p.end_time=current_time; //结束时间改变 cout<<setw(5)<<setfill(' ')<<p.a; //输出相关信息 cout<<setw(11)<<p.arr_time;cout<<setw(11)<<p.start_time;cout<<setw(11)<<p.haoshi;cout<<setw(11)<<p.end_time;cout<<setw(11)<<p.end_time-p.arr_time;cout<<setw(15)<<setiosflags(ios::fixed)<<setprecision(2)<<(double)(p.end_time-p.arr_time)/p.haoshi<<endl;}else if(time_slice<p.time) //如果p进程所需时间大于时间片，那么我们本次尚不能完全结束p进程，而把他重新放到就绪队列中 {current_time+=time_slice; //当前时间加上时间片的值 p.arrive_time=current_time; //p的到达时间(即此次到达就绪队列的时间)改为当前时间 p.time-=time_slice; //p进程所需时间减去当前时间片的大小变为新的所需时间 q.push(p); //重新把修改过相关参数的p进程压入队列中 }}return 0; }

四、 运行结果
输入次序依次为进程ID，到达时间和耗费时间
FCFS

RR

五、 实验思考
本次我们用模拟调度的办法展现了CPU进程调度的过程，计算了相对周转时间和带权周转时间，但是这并不能代表真正的CPU调度，因为在实际过程中，这个时间是非常快速的，而且我们要考虑阻塞的情况，应该有一个阻塞队列；并且还应该有接收外部信号（比如IO或者时间）唤醒进程的过程。实际的进程调度中还包含抢占式的调度，即后来的进程会根据优先级强弱决定是否直接打断当前进程。进程调度算法使我进一步对进程调度有了深刻的思考。
思考题：FCFS算法是非抢占式的算法，易于实现，有利于CPU繁忙型作业不利于I/O繁忙型作业；RR算法如果是非抢占式的话，其优劣程度取决于时间片的大小，如果时间片过大，那么所有进程基本能在一个时间片内完成则退化成了FCFS算法，如果时间片过小，需要频繁的进行上下文切换，会产生额外的开销。RR算法比较适合分时系统。其他的：短进程优先算法总是让时间耗费短的进程优先处理，这样子周转时间少，但是可能会导致饥饿；优先级调度也会导致饥饿的情况发生。动态优先级调度算法的优先级会根据等待时间的延长而增加，这样子兼顾了进程的优先级又不会出现饥饿的情况。
-----------------------------------今天也要加油鸭--------------------------------------

总结

以上是生活随笔为你收集整理的进程调度算法FCFS和RR的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。