SDUT操作系统课程（CATS）专题二+专题四(参考总结)

专题二+进程调度算法 RR q=1（含做题代码）

总结：到达时间一到对应进程进入，执行队首进程一次，对应的服务时间划一记号（推荐用正字），队首进程未执行到完成的话重新进入队尾，队首进程执行到完成的话出队，下一秒继续执行队首进程，当5个进程全部入队之后只要执行后两步操作。

基本分为3步操作：执行队首进程pi，加标记。进程pj到达进入就绪队列。pi未执行完重新进入就绪队列。

以下题为例

Process:  p1  p2  p3  p4  p5

Arrival Time:   0   1   2   3   6

Service TIme:  3   5    5   2   3

  p1  p2  p1  p3  p2  p4  p1  p3  p2   p5   p4   p3   p2   p5    p3

0   1   2   3   4   5    6   7  8    9    10   11   12   13    14   

  p2   p5   p3   p3

15  16   17   18   19

就绪队列

0秒时 p1进入就绪队列：p1，p1处于队首运行  p1.servicetime=1，完成操作后到达1秒。

1秒时 p2进入就绪队列：p1p2,此时p1未完成服务时间重新入队，就绪队列为p2p1。

1秒时 p2处于队首运行 p2.servicetime=1，完成操作后到达2秒。

2秒时 p3进入就绪队列：p2p1p3,此时p2未完成重新入队，就绪队列为p1p3p2。

2秒时 p1处于队首运行 p1.servicetime=2，完成操作后到达3秒。

3秒时 p4进入就绪队列：p1p3p2p4,此时p1未完成重新入队，就绪队列：p3p2p4p1。

3秒时 p3处于队首运行 p3.servicetime=1完成操作后到达4秒。

4秒时 p3未完成重新入队：p2p4p1p3。

4秒时 p2处于队首运行 p2.servicetime=2 完成操作后到达5秒。

5秒时 p2未完成重新入队，此时队列：p4p1p3p2。

      此时p4队首运行 p4.servicetime=1 完成操作后到达6秒

6秒时 p5入队，为：p4p1p3p2p5。p4未完成重新入队：p1p3p2p5p4。

       p1队首运行，p1.servicetime=3 p1完成出队：p3p2p5p4到达7秒

7秒时 p3队首运行，p3.servicetime=2 p3未完成入队：p2p5p4p3到达8秒

8秒时 p2队首运行 p2.servicetime=3 p2未完成入队：p5p4p3p2到达9秒

9秒时 p5队首运行 p5.servicetime=1 p5未完成入队：p4p3p2p5到达10秒

10秒时 p4队首运行 p4.servicetime=2 p4完成出队：p3p2p5到达11秒

11秒时 p3队首运行 p3.servicetime=3 p3未完成入队：p2p5p3到达12秒

12秒时 p2队首运行 p2.servicetime=4 p2未完成入队：p5p3p2到达13秒

13秒时 p5队首运行 p5.servicetime=2 p5未完成入队：p3p2p5到达14秒

14秒时 p3队首运行 p3.servicetime=4 p3未完成入队：p2p5p3到达15秒

15秒时 p2队首运行 p2.servicetime=5 p2完成出队：p5p3到达16秒

16秒时 p5队首运行 p5.servicetime=3 p5完成出队：p3到达17秒

17秒时 p3队首运行 p3.servicetime=5 p3完成入队：p3到达18秒

Process从后往前找最后结束的到最早结束的对应完成时间 Turnaround Time=Finish Time-Arrival Time

Wr=Tr/Ts保留三位小数  T=sum（Tr）/5  W=sum( Wr )/5 (保留两位小数)

 算法实现结果图

RR算法代码实现（C++）

/** 来源：网络 **/
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
vector<int> ans;
vector<int> G[20