OS课设之CPU调度算法的模拟实现

1、CPU调度算法的模拟实现一、设计目的 利用C+编写CPU调度算法，实现先来先服务调度算法FCFS、优先级调度算法PS、短作业优先调度算法SJF、时间片轮转调度算法RR的运行过程和实现的结果，针对模拟进程，利用编写的CPU调度算法对需要运行的进程进行调度。进行算法评价，计算平均周转时间和平均等待时间。 二、设计要求 针对模拟进程，利用CPU调度算法进行调度，最后要进行算法评价，计算平均周转时间和平均等待时间，并且输出调度结果和输出算法评价指标。 调度所需的进程参数由输入产生（手工输入或者随机数产生）。三、设计说明 CPU调度决策可在如下4种情况环境下发生： (1)当一个进程从运行切换到等待状态（

2、如：I/O请求，或者调用wait等待一个子进程的终止） (2)当一个进程从运行状态切换到就绪状态（如：出现中断） (3)当一个进程从等待状态切换到就绪状态（如：I/O完成） (4)当一个进程终止时对于第1和4两种情况，没有选择而只有调度。一个新进程（如果就绪队列中已有一个进程存在）必须被选择执行。对于第和第两种情况，可以进行选择。当调度只能发生在第1和4两种情况下时，称调度是非抢占的（nonpreemptive）或协作的（cooperative）；否则，称调度方案为抢占的（preemptive）。采用非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。

3、抢占调度对访问共享数据是有代价（如加锁）的，有可能产生错误，需要新的机制（如，同步）来协调对共享数据的访问。抢占对于操作系统内核的设计也有影响。在处理系统调用时，内核可能忙于进程活动。这些活动可能涉及要改变重要内核数据(如I/O队列)。因为根据定义中断能随时发生，而且不能总是被内核所忽视，所以受中断影响的代码段必须加以保护以避免同时访问。操作系统需要在任何时候都能够接收中断，否则输入会丢失或输出会被改写。为了这些代码段不被多个进程同时访问，在进入时就要禁止中断，而在退出时要重新允许中断。调度准则为了比较CPU调度算法所提出的准则：CPU使用率 : 需要使CPU尽可能忙吞吐量 : 指一个时间单元

4、内所完成进程的数量周转时间 :从进程提交到进程完成的时间段称为周转时间，周转时间是所有时间段之和，包括等待进入内存、在就绪队列中等待、在CPU上执行和I/O执行平均周转时间 :即周转时间的算数平均值等待时间 : 在就绪队列中等待所花费时间之和平均等待时间 : 即等待时间的算数平均值响应时间 : 从提交请求到产生第一响应的时间。需要使CPU使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化。绝大多数情况下需要优化平均值，有时需要优化最大值或最小值，而不是平均值四、详细设计4.1先到先服务调度(First-Come，First-Served scheduling)最简单的CPU调度算法是

5、先到先服务算法（First-Come，First-Served scheduling）：先请求CPU的进程先分配到CPU。FCFS策略可以用FIFO队列来容易实现。当一个进程进入就绪队列，其PCB链接到队列的尾部。当CPU空闲时，CPU分配给位于队列头的进程，接着运行进程从队列中删除。FCFS策略的代码编写简单且容易理解，不过采用FCFS策略的平均等待时间通常比较长。当进程CPU区间时间变化很大，平均等待时间会变化很大。算法原理：假设有n个进程分别在T1, ,Tn时刻到达系统，它们需要的服务时间分别为S1, ,Sn。分别采用先来先服务FCFS调度算法进行调度，计算每个进程的完成时间，周转时间和

6、带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。 程序要求如下： 1）进程个数n；每个进程的到达时间T1, ,Tn和服务时间S1, ,Sn。 2）要求采用先来先服务FCFS调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间； 3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等； 4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。实现简要过程：1）变量初始化； 2）接收用户输入n，T1, ,Tn，S1, ,Sn； 3）按照选择算法进行进

7、程调度，计算进程的完成时间、周转时 间和带权周转时间； 4）按格式输出调度结果。测试结果：案例分析： 进程区间时间 P1 24 P2 3 P3 3如果按照P1P2P3顺序到达，Gantt图如下： P1 P2 P3 0 24 27 30平均等待时间：（0+24+27）3=17平均周转时间：（24+27+30）3=27如果按照P2P3P1顺序到达，平均等待时间：（0+3+6）3=3平均周转时间：（3+6+30）3=13 另外考虑在动态情况下的性能，假设有一个CPU约束进程和许多I/O约束进程，CPU约束进程会移回到就绪队列并被分配到CPU。再次所有I/O进程会在就绪队列中等待CPU进程的完成。由于

8、所有其他进程都等待一个大进程释放CPU，这称之为护航效果（convoy effect）。与让较短进程最先执行相比，这样会导致CPU和设备使用率变的很低。 FCFS调度算法是非抢占的。对于分时系统（每个用户需要定时的等待一定的CPU时间）是特别麻烦。允许一个进程保持CPU时间过长是个严重错误。4.2 优先级调度(priority scheduling algorithm)算法：每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达

9、时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。 重复以上过程，直到所要进程都完成

10、为止。SJF算法可作为通用的优先级调度算法的一个特例。每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU。具有相同优先级的进程按FCFS顺序调度。SJF，其优先级（p）为下一个CPU区间的倒数。CPU区间越大，则优先级越小，反之亦然。优先级通常是固定区间的数字，如，但是数字大小与优先级的高低没有定论。测试结果：案例分析：（假设数字越小优先级越高） 进程 区间时间 优先级 P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2画出Gantt图：P2 P 5 P 1 P 3P4 0 1 6 16 1819 平均等待时间：（0+1+6+16+18）5=8.2平均周转时

11、间：（1+6+16+18+19）5=12优先级可通过内部或外部方式来定义。内部定义优先级使用一些测量数据以计算进程优先级。外部优先级是通过操作系统之外的准则来定义，如进程重要性等。优先级调度可以是抢占的或非抢占的。优先级调度算法的一个重要问题是无限阻塞（indefinite blocking）或饥饿（starvation）。可以运行但缺乏CPU的进程可认为是阻塞的，它在等待CPU。优先级调度算法会使某个有低优先级无穷等待CPU。低优先级进程务求等待问题的解决之一是老化（aging）。老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。4.3 时间片轮转调度算法(round-robin

12、,RR)专门为分时系统设计。它类似于FCFS调度，但是增加了抢占以切换进程。定义一个较小的时间单元，称为时间片（time quantum，or time slice）。将就绪队列作为循环队列。CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片段的CPU。系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。如果在时

13、间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后,它被移到队列的末尾。RR策略的平均等待时间通常较长测试结果： 案例分析：（使用4ms时间片） 进程 区间时间 P1 24 P2 3 P3 3画出Gantt图： P1 P2 P3 P1 P1 P1 P1 P10 4 7 10 14 18 22 26 30 平均等待时间：0+4+7+（10-4）3=5.66平均周转时间：（7+10+30）3=15.67 如果就绪，那么每个进程会得到1n的CPU时间，其长度不超过q时间单

14、元。每个进程必须等待CPU时间不会超过(n1)q个时间单元，直到它的下一个时间片为止。 RR算法的性能很大程度上依赖于时间片的大小。在极端情况下，如果时间片非常大，那么RR算法与FCFS算法一样。如果时间片很小，那么RR算法称为处理器共享，n个进程对于用户都有它自己的处理器，速度为真正处理器速度的1/n。 小的时间片会增加上下文切换的次数，因此，希望时间片比上下文切换时间长，事实上，绝大多数现代操作系统，上下文切换的时间仅占时间片的一小部分。 周转时间也依赖于时间片的大小。4.4 最短作业优先调度(shortest-job-first scheduling,SJF)将每个进程与下一个CPU区间

15、段相关联。当CPU为空闲时，它会赋给具有最短CPU区间的进程。如果两个进程具有同样长度，那么可以使用FCFS调度来处理。注意，一个更为适当地表示是最短下一个CPU区间的算法，这是因为调度检查进程的下一个CPU区间的长度，而不是其总长度。这种策略是下一次选择所需处理时间最短的进程。是非抢占策略，目的也是为减少FCFS策略对长进程的偏向。测试结果： 案例分析： 进程 区间时间 P1 6 P2 8 P3 7 P4 3画出Gantt图： P4 P1 P3 P20 3 9 16 24SJF平均等待时间：（0+3+9+16）4=7SJF平均周转时间：（3+9+16+24）4=13FCFS平均等待时间：（0

16、+6+14+21）4=10.25FCFS平均周转时间：（6+14+21+24）4=16.25 SJF算法的平均等待时间最小。SJF算法的真正困难是如何知道下一个CPU区间的长度。对于批处理系统的长期（作业）调度，可以将用户提交作业时间所制定的进程时间极限作为长度。SJF调度经常用于长期调度。 它不能在短期CPU调度层次上加以实现。我们可以预测下一个CPU区间。认为下一个CPU区间的长度与以前的相似。因此通过计算下一个CPU区间长度的近似值，能选择具有最短预测CPU区间的进程来运行。下一个CPU区间通常可预测为以前CPU去剪的测量长度的指数平均（exponential average）。4.5

17、最短剩余时间优先调度（shortest-remaining-time-first scheduling）SJF算法可能是抢占的或非抢占的。抢占SJF算法可抢占当前运行的进程，而非抢占的SJF算法会允许当前的进程先完成其CPU区间。抢占SJF调度有时称为最短剩余时间优先调度。这种策略下调度器总是选择预期剩余时间最短的进程。是抢占策略。测试结果： 案例分析： 进程 到达时间 区间时间 P1 0 8 P2 1 4 P3 2 9 P4 3 5画出Gantt图：P1 P2 P4 P1 P30 1 5 10 17 26平均等待时间：0+0+(5-3)+(17-2)4=6.5平均周转时间：（17-0）+（5

18、-1）+（26-2）+（10-3）4=13非抢占的SJF平均等待时间：0+（8-1）+（12-3）+（17-2）4=7.75源代码/最短剩余时间优先算法的实现#include #include #include typedef structint remain_time;/进程剩余执行时间int arrive_time;/进程到达时间int Tp;/进入就绪队列的时间int Tc;/进入执行队列的时间int To;/进程执行结束的时间int number;/进程编号Process_Block;/定义进程模块typedef struct _QueueProcess_Block PB;struct

19、 _Queue *next;_Block, *Process;/定义一个进程模块队列中结点typedef structProcess head;/队列头指针Process end;/队列尾指针Process_Queue;/进程队列Process_QueuePQ;/定义一个全局队列变量intt;/全局时间ProcessRun_Now; /当前正在运行的进程，作为全局变量void InitQueue(Process_Queue PQ)PQ.head-next = NULL;PQ.end-next = PQ.head;/*初始化队列*/int IsEmpty(Process_Queue PQ)if

20、(PQ.end-next = PQ.head)return 1;/队列空的条件为头指针指向尾指针并且尾指针指向头指针elsereturn 0;/*判定队列是否为空队列*/void EnQueue(Process_Queue PQ, Process P)Process temp = (Process)malloc(sizeof(_Block);temp = PQ.end;temp-next-next = P;PQ.end-next = P;/*插入队列操作*/Process DeQueue(Process_Queue PQ)if (IsEmpty(PQ)return NULL;Process t

21、emp = PQ.head-next;PQ.head-next = temp-next;if (PQ.end-next = temp)PQ.end-next = PQ.head;return temp;/*出列操作*/Process ShortestProcess(Process_Queue PQ)if (IsEmpty(PQ) /如果队列为空，返回if (!Run_Now)return NULL;elsereturn Run_Now;Process temp, shortest, prev;int min_time;if (Run_Now) /如果当前有进程正在执行，shortest = R

22、un_Now;/那么最短进程初始化为当前正在执行的进程，min_time = Run_Now-PB.remain_time;else/如果当前没有进程执行，shortest = PQ.head-next;/则最短进程初始化为队列中第一个进程min_time = PQ.head-next-PB.remain_time;temp = PQ.head;prev = temp;while (temp-next) if (temp-next-PB.remain_time next;/则保存当前进程， min_time = shortest-PB.remain_time; prev = temp;/及其前

23、驱 temp = temp-next;if (shortest = PQ.end-next)/如果最短剩余时间进程是队列中最后一个进程，PQ.end-next = prev;/则需要修改尾指针指向其前驱prev-next = shortest-next;/修改指针将最短剩余时间进程插入到队头return shortest;/*调度最短剩余时间的进程至队头*/void Run()Run_Now-PB.remain_time-;/某一时间运行它的剩余时间减return;/*运行函数*/void Wait()return;int sum(int array, int n)int i, sum = 0

24、;for (i = 0;in;i+)sum += arrayi;return sum;int main()PQ.head = (Process)malloc(sizeof(_Block);PQ.end = (Process)malloc(sizeof(_Block);Run_Now = (Process)malloc(sizeof(_Block);Run_Now = NULL;InitQueue(PQ);int i, N, Total_Time = 0;/Total_Time为所有进程的执行时间之和printf(请输入计算机中的进程数目:n);scanf(%d, &N);Process *P,

25、 temp;P = (Process*)malloc(N * sizeof(Process);int *wt, *circle_t;wt = (int*)malloc(N * sizeof(int);circle_t = (int*)malloc(N * sizeof(int);for (i = 0;iPB.number = i + 1;Pi-next = NULL;wti = 0;circle_ti = 0;printf(输入第%d个进程的到达时间及剩余执行时间:n, i + 1);scanf(%d %d, &Pi-PB.arrive_time, &Pi-PB.remain_time);fo

26、r (i = 0;iPB.remain_time;printf(n进程按顺序运行依次为:n);i = 0;int k = 0;for (t = 0;t+)if (Run_Now) /如果当前有进程正在执行Run();if (t = Pi-PB.arrive_time) /如果当前时间正好有进程进入if (Pi-PB.remain_time PB.remain_time)temp = Pi;Pi = Run_Now;Run_Now = temp;/则调度它至运行队列中，Run_Now-PB.Tp = t;Run_Now-PB.Tc = t;wtRun_Now-PB.number - 1 += R

27、un_Now-PB.Tc - Run_Now-PB.Tp;printf(%d , Run_Now-PB.number);EnQueue(PQ, Pi);/并将当前运行进程重新插入队列中Pi-PB.Tp = t;k+;i = (i + 1)(N - 1) ? (N - 1) : (i + 1);if (Run_Now-PB.remain_time = 0) /如果当前进程运行结束，Run_Now-PB.To = t;/进程运行结束的时间circle_tRun_Now-PB.number - 1 += t - Run_Now-PB.arrive_time;free(Run_Now);/则将它所占资

28、源释放掉，Run_Now = NULL;/并修改Run_Now为NULLRun_Now = ShortestProcess(PQ)/从就绪队列中调出最短剩余时间进程至队头，if (!Run_Now) /如果队列为空，转为等待状态if (IsEmpty(PQ) & k = N) break;Wait();continue;elseRun_Now-PB.Tc = t;wtRun_Now-PB.number - 1 += Run_Now-PB.Tc - Run_Now-PB.Tp;printf(%d , Run_Now-PB.number);else/如果当前运行进程为空，那么if (t = Pi-

29、PB.arrive_time) /如果正好这时有进程入队k+;EnQueue(PQ, Pi);Run_Now = DeQueue(PQ);/则直接被调入运行队列中Run_Now-PB.Tp = t;Run_Now-PB.Tc = t;printf(%d , Run_Now-PB.number);i = (i + 1)(N - 1) ? (N - 1) : (i + 1);elseWait();continue;printf(n);printf(平均等待时间是:n%fn, (float)sum(wt, N) / N);printf(平均周转时间是:n%fn, (float)sum(circle_

30、t, N) / N);return 0;/#include#includeusing namespace std;class Processpublic:string ProcessName; / 进程名字int Time; / 进程需要时间int leval; / 进程优先级int LeftTime; / 进程运行一段时间后还需要的时间;void Copy(Process proc1, Process proc2); / 把proc2赋值给proc1void Sort(Process pr, int size); / 此排序后按优先级从大到小排列void sort1(Process pr,

31、int size); / 此排序后按需要的cpu时间从小到大排列void Fcfs(Process pr, int num, int Timepice); / 先来先服务算法void TimeTurn(Process process, int num, int Timepice); / 时间片轮转算法void Priority(Process process, int num, int Timepice); / 优先级算法void main()int a;cout endl;cout 选择调度算法： endl;cout 1: FCFS 2: 时间片轮换 3: 优先级调度 4: 最短作业优先 5

32、: 最短剩余时间优先 a;const int Size = 30;Process processSize;int num;int TimePice;cout 输入进程个数: num;cout 输入此进程时间片大小: TimePice;for (int i = 0; i num; i+)string name;int CpuTime;int Leval;cout 输入第 i + 1 个进程的名字、cpu时间和优先级: name;cin CpuTime Leval;processi.ProcessName = name;processi.Time = CpuTime;processi.leval

33、= Leval;cout endl;for (int k = 0;knum;k+)processk.LeftTime = processk.Time;/对进程剩余时间初始化cout ( 说明: 在本程序所列进程信息中，优先级一项是指进程运行后的优先级! );cout endl; cout endl;cout 进程名字 共需占用CPU时间 还需要占用时间 优先级 状态 endl;if (a = 1)Fcfs(process, num, TimePice);else if (a = 2)TimeTurn(process, num, TimePice);else if (a = 3)Sort(pro

34、cess, num);Priority(process, num, TimePice);else / 最短作业算法，先按时间从小到大排序，再调用Fcfs算法即可sort1(process, num);Fcfs(process, num, TimePice);void Copy(Process proc1, Process proc2)proc1.leval = proc2.leval;proc1.ProcessName = proc2.ProcessName;proc1.Time = proc2.Time;void Sort(Process pr, int size) /以进程优先级高低排序/

35、 直接插入排序for (int i = 1;i0 & temp.levalsize / 2;d-)Process temp;temp = prd;prd = prsize - d - 1;prsize - d - 1 = temp; / 此排序后按优先级从大到小排列/* 最短作业优先算法的实现*/void sort1(Process pr, int size) / 以进程时间从低到高排序/ 直接插入排序for (int i = 1;i0 & temp.Time prj - 1.Time)prj = prj - 1;j-;prj = temp;/* 先来先服务算法的实现*/void Fcfs(P

36、rocess process, int num, int Timepice) / process 是输入的进程，num是进程的数目，Timepice是时间片大小while (true)if (num = 0)cout 所有进程都已经执行完毕! endl;exit(1);if (process0.LeftTime = 0)cout 进程 process0.ProcessName 已经执行完毕! endl;for (int i = 0;inum;i+)processi = processi + 1;num-;else if (processnum - 1.LeftTime = 0) cout 进程

37、 processnum - 1.ProcessName 已经执行完毕! endl;num-;elsecout endl; /输出正在运行的进程process0.LeftTime = process0.LeftTime - Timepice;process0.leval = process0.leval - 1;cout process0.ProcessName process0.Time ;cout process0.LeftTime process0.leval 运行;cout endl;for (int s = 1;snum;s+)cout processs.ProcessName pro

38、cesss.Time ;cout processs.LeftTime processs.leval 等待 endl; ; / elsecout endl;system( pause);cout endl; / while /* 时间片轮转调度算法实现*/void TimeTurn(Process process, int num, int Timepice)while (true)if (num = 0)cout 所有进程都已经执行完毕! endl;exit(1);if (process0.LeftTime = 0)cout 进程 process0.ProcessName 已经执行完毕! endl;for (int i = 0;inum;i+)processi = processi + 1;num-;if (processnum - 1.LeftTime = 0)cout 进程 processnum - 1.ProcessName