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

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分配给一个进程，那

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

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

5、-Come ， First-Served scheduling)最 简 单 的 CPU 调 度 算 法 是 先 到 先服 务算 法 （ First-Come ， First-Served scheduling ）：先请求 CPU的进程先分配到 CPU。FCFS策略可以用 FIFO 队列来容易实现。当一个进程进入就绪队列，其 PCB链接到队列的尾部。当 CPU空闲时， CPU分配给位于队列头的进程，接着运行进程从队列中删除。FCFS策略的代码编写简单且容易理解， 不过采用 FCFS策略的平均等待时间通常比较长。当进程 CPU区间时间变化很大，平均等待时间会变化很大。算法原理 ：假设有 n 个进程

6、分别在T1, , ,Tn 时刻到达系统，它们需要的服务时间分别为S1, ,Sn 。分别采用先来先服务 FCFS调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计 n 个进程的平均周转时间和平均带权周转时间。程序要求如下 ：1）进程个数 n；每个进程的到达时间T1, , ,Tn 和服务时间 S1, , ,Sn 。2 ）要求采用先来先服务 FCFS调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程 B 开始运行”等等；4）输出：要求输出计算出来的每

7、个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。实现简要过程 ：1）变量初始化；2）接收用户输入n，T1, , ,Tn，S1, , ,Sn；3）按照选择算法进行进程调度，计算进程的完成时间、周转时间和带权周转时间；4）按格式输出调度结果。测试结果 ：案例分析 ：进程区间时间P124P23P33如果按照 P1P2P3顺序到达， Gantt 图如下：0P1P2P3242730平均等待时间：（ 0+24+27）3=17平均周转时间：（ 24+27+30 ）3=27如果按照 P2P3P1 顺序到达，平均等待时间：（0+3+6）3=3平均周转时间：（3+6+30） 3=13另外

8、考虑在动态情况下的性能，假设有一个CPU 约束进程和许多I/O 约束进程，CPU 约束进程会移回到就绪队列并被分配到CPU 。再次所有 I/O 进程会在就绪队列中等待 CPU 进程的完成。由于所有其他进程都等待一个大进程释放CPU ，这称之为护航效果（ convoy effect ）。与让较短进程最先执行相比，这样会导致CPU 和设备使用率变的很低。FCFS 调度算法是非抢占的。对于分时系统（每个用户需要定时的等待一定的 CPU 时间）是特别麻烦。允许一个进程保持 CPU 时间过长是个严重错误。4.2优先级调度 (priority scheduling algorithm)算法：每个进程有一个

9、进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W（Wait ）、运行 R（ Run）、或完成 F （Finish ）三种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。 用已占用 CPU 时间加 1 来表示。如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用 CPU时间还未达所需

10、要的运行时间，也就是进程还需要继续运行， 此时应将进程的优先数减 1（即降低一级） ，然后把它插入就绪队列等待 CPU。每进行一次调度程序都打印一次运行进程、 就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。SJF 算法可作为通用的优先级调度算法的一个特例。 每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到 CPU。具有相同优先级的进程按 FCFS顺序调度。SJF，其优先级（ p）为下一个 CPU区间的倒数。 CPU区间越大，则优先级越小，反之亦然。优先级通常是固定区间的数字，如，但是数字大小与优先级的高低没有定论。测试结果 ：案例分析 ：（假

11、设数字越小优先级越高）进程区间时间优先级P1103P211P324P415P552画出 Gantt 图：0P2P5P 1P3 P416161819平均等待时间：（ 0+1+6+16+18）5=8.2平均周转时间：（ 1+6+16+18+19 ） 5=12优先级可通过内部或外部方式来定义。内部定义优先级使用一些测量数据以计算进程优先级。外部优先级是通过操作系统之外的准则来定义，如进程重要性等。优先级调度可以是抢占的或非抢占的。优先级调 度算法 的一个 重要问 题是无 限阻塞 （ indefiniteblocking ）或饥饿（starvation ）。可以运行但缺乏 CPU 的进程可认为是阻塞的

12、，它在等待级调度算法会使某个有低优先级无穷等待 CPU 。CPU 。优先低优先级进程务求等待问题的解决之一是老化（加在系统中等待很长时间的进程的优先级。aging ）。老化是一种技术，以逐渐增4.3时间片轮转调度算法 (round-robin,RR)专门为分时系统设计。它类似于 FCFS调度，但是增加了抢占以切换进程。定义一个较小的时间单元，称为时间片（ time quantum ，or time slice ）。将就绪队列作为循环队列。 CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片段的 CPU。系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进

13、程， 并令其执行一个时间片。 时间片的大小从几 ms到几百 ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后 , 它被移到队列的末尾。RR策略的平均等待时间通常较长测试结果 ：案例分析 ：（使用 4ms时间片）进程区间时间P124P23P33画出 Gantt 图：P

14、1P2P3P1P1P1P1P1047101418222630平均等待时间： 0+4+7+（ 10-4 ） 3=5.66平均周转时间：（ 7+10+30 ）3=15.67如果就绪，那么每个进程会得到 1n 的 CPU 时间，其长度不超过 q 时间单元。每个进程必须等待 CPU 时间不会超过 (n- 1) q 个时间单元，直到它的下一个时间片为止。RR 算法的性能很大程度上依赖于时间片的大小。 在极端情况下， 如果时间片非常大，那么 RR 算法与 FCFS 算法一样。如果时间片很小，那么 RR 算法称为处理器共享， n 个进程对于用户都有它自己的处理器，速度为真正处理器速度的1/n 。小的时间片会

15、增加上下文切换的次数，因此，希望时间片比上下文切换时间长，事实上，绝大多数现代操作系统，上下文切换的时间仅占时间片的一小部分。周转时间也依赖于时间片的大小。4.4 最短作业优先调度 (shortest-job-first scheduling,SJF)将每个进程与下一个 CPU区间段相关联。当 CPU为空闲时，它会赋给具有最短 CPU 区间的进程。如果两个进程具有同样长度，那么可以使用 FCFS调度来处理。注意，一个更为适当地表示是最短下一个 CPU区间的算法，这是因为调度检查进程的下一个 CPU 区间的长度，而不是其总长度。这种策略是下一次选择所需处理时间最短的进程。是非抢占策略，目的也是为

16、减少FCFS策略对长进程的偏向。测试结果 ：案例分析 ：进程区间时间P16P28P37P43画出 Gantt 图：P4P1P3P20391624SJF 平均等待时间：（0+3+9+16） 4=7SJF 平均周转时间：（3+9+16+24 ）4=13FCFS 平均等待时间：（0+6+14+21 ） 4=10.25FCFS 平均周转时间：（6+14+21+24 ）4=16.25SJF算法的平均等待时间最小。SJF算法的真正困难是如何知道下一个CPU 区间的长度。对于批处理系统的长期（作业）调度，可以将用户提交作业时间所制定的进程时间极限作为长度。SJF 调度经常用于长期调度。它不能在短期CPU 调

17、度层次上加以实现。 我们可以预测下一个认为下一个CPU 区间的长度与以前的相似。因此通过计算下一个度的近似值，能选择具有最短预测CPU 区间的进程来运行。下一个CPU 区间。CPU 区间长CPU 区间通常可预测为以前CPU 去剪的测量长度的指数平均（exponential average）。4.5最 短 剩 余 时 间 优 先 调 度 （ shortest-remaining-time-firstscheduling ）SJF算法可能是抢占的或非抢占的。抢占 SJF 算法可抢占当前运行的进程，而非抢占的 SJF 算法会允许当前的进程先完成其 CPU区间。抢占 SJF 调度有时称为最短剩余时间优

18、先调度。这种策略下调度器总是选择预期剩余时间最短的进程。是抢占策略。测试结果 ：案例分析 ：进程到达时间区间时间P108P214P329P435画出 Gantt图：P1P2P4P1P3015101726平均等待时间： 0+0+(5-3)+(17-2)4=6.5平均周转时间： （17-0 ）+（5-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

19、;/ 进程剩余执行时间int arrive_time;/ 进程到达时间int Tp;/ 进入就绪队列的时间int Tc;/ 进入执行队列的时间int To;/ 进程执行结束的时间int number;/ 进程编号Process_Block;/ 定义进程模块typedef struct _QueueProcess_Block PB;struct _Queue *next;_Block, *Process;/ 定义一个进程模块队列中结点typedef structProcess head;/ 队列头指针Process end;/ 队列尾指针Process_Queue;/ 进程队列Process_Q

20、ueuePQ;/ 定义一个全局队列变量intt;/ 全局时间ProcessRun_Now;/ 当前正在运行的进程，作为全局变量void InitQueue(Process_Queue PQ)PQ.head-next = NULL;PQ.end-next = PQ.head;/* 初始化队列 */int IsEmpty(Process_Queue PQ)if (PQ.end-next = PQ.head)return 1;/ 队列空的条件为头指针指向尾指针并且尾指针指向头指针elsereturn 0;/* 判定队列是否为空队列*/void EnQueue(Process_Queue PQ, Pr

21、ocess 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 temp = PQ.head-next;PQ.head-next = temp-next;if (PQ.end-next = temp)PQ.end-next = PQ.head;return temp;/* 出列操作 */Proce

22、ss 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 = Run_Now;/ 那么最短进程初始化为当前正在执行的进程，min_time = Run_Now-PB.remain_time;else/ 如果当前没有进程执行，shortest = PQ.head-next; /则最短进程初

23、始化为队列中第一个进程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;/ 及其前驱temp = temp-next;if (shortest = PQ.end-next)/如果最短剩余时间进程是队列中最后一个进程，PQ.end-next = prev;/ 则需要修改尾指针指向其前驱prev-nex

24、t = 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;for (i = 0;in;i+)sum += arrayi;return sum;int main()PQ.head = (Process)malloc(sizeof(_Block);PQ.end = (P

25、rocess)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, temp;P = (Process*)malloc(N * sizeof(Process);int *wt, *circle_t;wt = (int*)malloc(N * sizeof(int);circl

26、e_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);for (i = 0;iPB.remain_time;printf(n进程按顺序运行依次为:n);i = 0;int k = 0;for (t = 0;t+)if (Run_Now) / 如果当前有进程正在执行R

27、un();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 += Run_Now-PB.Tc -Run_Now-PB.Tp;printf(%d , Run_Now-PB.number);EnQueue(PQ, Pi);/ 并将当前运行进程重新插入队列中Pi-PB.Tp =

28、 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);/ 则将它所占资源释放掉，Run_Now = NULL;/ 并修改 Run_Now为NULLRun_Now = ShortestProcess(PQ)/从就绪队列中调出最短剩余时间进程至队头，if (!Run_Now)

29、 /如果队列为空，转为等待状态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-PB.arrive_time) / 如果正好这时有进程入队k+;EnQueue(PQ, Pi);Run_Now = DeQueue(PQ);/ 则直接被调入运行队列中Run_Now-PB.Tp =

30、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_t, N) / N);return 0;/#include#includeusing namespace std;class Processpublic:string ProcessName

31、; /进程名字int Time; /进程需要时间int leval; /进程优先级int LeftTime; /进程运行一段时间后还需要的时间;void Copy(Process proc1, Process proc2); /把 proc2 赋值给 proc1void Sort(Process pr, int size); /此排序后按优先级从大到小排列void sort1(Process pr, int size); /此排序后按需要的cpu时间从小到大排列void Fcfs(Process pr, int num, int Timepice); /先来先服务算法void TimeTurn

32、(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:最短剩余时间优先 a;const int Size = 30;ProcessprocessSize;int num;int TimePice;cout 输入进程个数 : num;cout 输入此进程时间片大小:

33、TimePice;for (int i = 0; i num; i+)string name;int CpuTime;int Leval;cout 输入第 name; i + 1 CpuTime Leval;processi.ProcessName = name;processi.Time = CpuTime;processi.leval = Leval;cout endl;for (int k = 0;knum;k+)processk.LeftTime = processk.Time;/对进程剩余时间初始化cout (说明 :在本程序所列进程信息中，优先级一项是指进程运行后的优先级 ! );

34、cout endl;cout endl;cout 进程名字共需占用CPU时间还需要占用时间优先级状态 endl;Fcfs(process, num, TimePice);else if (a = 2)TimeTurn(process, num, TimePice);else if (a = 3)Sort(process, num);Priority(process, num, TimePice);else /最短作业算法，先按时间从小到大排序，再调用Fcfs算法即可sort1(process, num);Fcfs(process, num, TimePice);void Copy(Proces

35、s proc1, Process proc2)proc1.leval = proc2.leval;proc1.ProcessName = proc2.ProcessName;proc1.Time = proc2.Time;void Sort(Process pr, int size) /以进程优先级高低排序/ 直接插入排序for (int i = 1;i0 & temp.levalsize / 2;d-)Process temp;temp = prd;prd = prsize - d - 1;prsize - d - 1 = temp; /此排序后按优先级从大到小排列/*最短作业优先算法的实现

36、*/void sort1(Process pr, int size) /以进程时间从低到高排序/ 直接插入排序for (int i = 1;i0 & temp.Time prj - 1.Time)prj = prj - 1;j-;prj = temp;/*先来先服务算法的实现*/void Fcfs(Process process, int num, int Timepice) / process是输入的进程， num是进程的数目， Timepice 是时间片大小 while (true)if (num = 0)cout 所有进程都已经执行完毕! endl;exit(1);if (process

37、0.LeftTime = 0)cout 进程 process0.ProcessName 已经执行完毕 ! endl;for (int i = 0;inum;i+)processi = processi + 1;num-;else if (processnum - 1.LeftTime = 0)cout 进程 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 processs.Time ;cout processs.LeftTime proc