操作系统课程设计报告

1、操作系统原理及应用课程设计报告进程调度算法模拟 学院（系）： 计算机科学与工程学院 班 级： 学号 学生姓名： 许鸿兴 同组人员： 许鸿兴 时间： 从 2016年 12 月27日 到 2017 年01月03日目录1、课程设计的目的12、课程设计的内容及要求13、设计原理14、设计说明25、具体实现56、软件运行环境及限制97、结果输出及分析98、心得体会129、参考文献1310、源程序131、课程设计的目的本课程设计是学生学习完操作系统原理及应用课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。

2、2、课程设计的内容及要求进程调度算法模拟：先来先服务、短作业优先、时间片轮转、基于静态优先级的调度、基于高响应比优先的动态优先级调度算法实现。能够输出调度情况，并计算周转时间和平均周转时间。要求使用链表，进程个数由用户提供，按照进程的实际个数生成PCB，程序能够让用户选择使用哪种调度算法，能够在Linux环境运行并验证结果。程序要考虑用户界面的友好性和使用方便性。进程基本信息可从文件读入，也可手动输入。3、设计原理（1）先来先服务调度算法（FCFS）。当在作业调度中采用FCFS算法时，系统将按照作业到达的先后次序来进行调度。即相当于只考虑作业的等待时间，而忽视了作业的运行时间，从后备作业队列中

3、选择一个最先进入该队列的进程，为之分配处理机，使之投入运行，该进程一直运行到完成或者发生某件事而阻塞后，进程调度程序才就爱那个处理机分配给其他进程。（2）短作业优先调度算法（SJF）。SJF算法是以作业的长短来计算优先级，作业越短，优先级越高。作业的长短是以作业的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把段作业优先算法用于作业调度时，它将从外村的作业后备队列中选择若干个估计运行时间按最短的作业，优先将它们调入内存运行。（3）时间片轮转调度算法（RR）。RR算法采取了非常公平的处理机分配方式，即让就绪队列上的每一个进程每次仅运行一个时间片。如果就绪队列上有n个进程，则每次大

4、约都可获得1/n的处理机时间。在RR算法中，有两种情况发生进程的切换：若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，在调度就绪队列中的进程运行，并启动一个新的时间片。在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列。在RR算法中，时间片的大小对系统性能的影响很大。一个较为可取的时间片大小是略大于一次典型的交互所需的时间，是大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间。（4）基于静态优先级的调度算法（PSA）。PSA算法是基于作业的紧迫程度，由外部赋予作业相应的优先级。调度算法是基于该优

5、先级进行调度的。这样就可以保证紧迫性作业优先运行。PSA算法可作为作业调度算法，也可作为进程调度算法。当该算法用于作业调度时，系统是从后备队列中选择若干个优先级最高的作业装入内存。（5）基于高响应比优先的动态优先级调度算法（HRRN）。为每个作业引入一个动态优先级，即优先级是可以改变的，令它随等待时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然会获得处理机。由于等待时间与服务时间之和就是系统对该作业的响应时间，故优先级的变化规律为：优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间。由上式可以看出：如果作业的等待时间相等，则要求服务时间越

6、短，其优先权越高，因而类似SJF算法，有利于短作业。当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而类似FCFS算法。对于长作业的优先权，可以随等待时间的增加而增高，当其等待时间足够长时，也可获得处理机。因此该算法实现了较好的折中。但在使用该算法时，每次进行调度之前，都需要先做响应比的计算，会增加系统的开销。4、设计说明（1）系统整体结构。系统主要分为三个部分：获取进程信息部分、调度算法部分、输出部分。程序流程：输入进程个数->选择获取进程信息方式->选择调度算法->继续选择。程序流程图如图4.1所示。图4.1 程序流程图（2）获取进程信息系统首先定义一个进程控制

7、块结构体Node。包含进程名Name、优先级Piority（数值越小优先级越高）、到达时间Arrive_Time、服务时间Service_Time、开始时间Start_Time、结束时间Finish_Time、周转时间Around_Time、还需要的轮转时间Need_Around_Time以及指向下一个结点指针Next。在void Create_Process(Node *H)函数中，根据主函数传进来的头指针H以及全局变量进程个数Pro_Num根据选择的获取进程信息的方法，使用尾插法创建长度为Pro_Num的进程链表，其中头结点H不保存进程信息。若选择的是手动输入进程信息，则使用for循环，一

8、个一个输入进程的信息。若选择从文件获取进程的信息，则也是for循环，使用fscanf将文件逐行读出，每行包括进程的进程名、优先级、到达时间、服务时间。（3）输出部分函数void OutPutProcess(Node *H)用于按格式输出进程信息以及计算并输出平均周转时间。（4）先来先服务调度算法（FCFS）。在先来先服务调度算法中，首先定义一个空链表的头指针First和尾指针Tail，以及用于保留键值更小的节点的前驱节点的指针p_min和用于存储最小到达时间的节点min。然后使用选择排序的方法，将原进程链表中到达时间最小的结点依次放到First链表的链尾，直到取完原链表中的结点。然后再将Fir

9、st连接到H->Next，即此时H为已将到达时间从小到大排序好的链表。（5）短作业优先调度算法（SJF）。原理同先来先服务调度算法，在短作业优先调度算法中，首先定义一个空链表的头指针First和尾指针Tail，以及用于保留键值更小的节点的前驱节点的指针p_min和用于存储最小到达时间的节点min。然后使用选择排序的方法，将原进程链表中相同条件下作业时间最短或者不同条件下最先到达的结点依次放到First链表的链尾，直到取完原链表中的结点。然后再将First连接到H->Next，即此时H为已满足短作业优先的链表。（6）时间片轮转调度算法（RR）。时间片轮转调度算法中用到的变量主要有用户

10、输入的轮转时间Round_Time、记录当前时间Time、新到达进程数NewArrive以及用于存放当前就绪队列中的进程的循环链表First。在当前时间=总的服务时间Total_Time之前，应不断地获取在Time之前到达但未移动到运行队列的进程数量，然后判断并在循环链表中插入新结点。然后判断当前进程Q剩余的服务时间是否小于等于轮转时间，若是，则结束Q，并将其从队列中删除；若否，则计算相应数据并继续循环。（7）基于静态优先级的调度算法（PSA）。原理同先来先服务调度算法，在静态优先级调度算法中，首先定义一个空链表的头指针First和尾指针Tail，以及用于保留键值更小的节点的前驱节点的指针p_

11、min和用于存储最小到达时间的节点min。然后使用选择排序的方法，将原进程链表中相同条件下优先级最高或者不同条件下最先到达的结点依次放到First链表的链尾，直到取完原链表中的结点。然后再将First连接到H->Next，即此时H为已满足静态优先级调度的链表。（8）基于高响应比优先的动态优先级调度算法（HRRN）。原理同先来先服务调度算法，在高响应比优先的动态优先级调度算法中，首先定义一个空链表的头指针First和尾指针Tail，以及用于保留键值更小的节点的前驱节点的指针p_min和用于存储最小到达时间的节点min。然后使用选择排序的方法，将原进程链表中相同条件下优先权最高或者不同条件下

12、最先到达的结点依次放到First链表的链尾，直到取完原链表中的结点。然后再将First连接到H->Next，即此时H为已满足高响应比优先的动态优先级调度的链表。5、具体实现（1） 主函数的功能说明。在主函数中，创建头结点H，初始化为空链表。并输入进程的个数，然后调用Create_Process(H);函数，创建链表。为了避免调用其他调度算法后影响程序的结果，为五个调度算法赋予了五个原始创建的进程链表，即H1H5。然后调用Menu函数，输出菜单，在根据选择的选项，调用相应的调度算法。（2） 先来先服务调度算法（FCFS）。在此调度算法中，最主要的是使用选择排序进行到达时间的排序。使用whi

13、le循环，遍历链表中的每个结点，在while循环内，再使用for循环，找出比当前结点到达时间小的结点，然后交换并记录下其前驱结点，程序片段如下：for(P=H->Next,min=H->Next;P->Next!=NULL;P=P->Next)/循环遍历链表中的节点，找出此时最小的节点if(P->Next->Arrive_Time<min->Arrive_Time)/找到一个比当前min小的节点p_min=P;/保存p->next的前驱节点pmin=P->Next;/保存键值更小的节点然后判断有序链表是否为空，若为空，则将找出的最小到

14、达时间的进程的结点作为First链表的头结点，然后将其到达时间作为开始时间、完成时间=开始时间+服务时间、周转时间=完成时间-到达时间，同时尾指针后移。若有序链表First不为空链表，则将找到的当前最小的到达时间的进程的结点作为有序链表的尾节点，然后判断若其到达时间<=前一个进程的完成时间，则将前一个进程的完成时间作为其开始时间，若其到达时间>前一个进程的完成时间，则将爱其到达时间作为其开始时间，同样地在计算其完成时间和周转时间，同时尾指针后移。if(min=H->Next) H->Next=H->Next->Next;else p_min->Next

15、=min->Next; 用于判断如果找到的最小节点就是第一个节点，则让H指向原H->next,即第二个节点。如果不是第一个节点，则将前次最小节点的next指向当前min的next。（3） 短作业优先调度算法（SJF）。同先来先服务算法，只是判断的条件不同。增设一个用于记录前一个进程的完成时间的变量Pre_Finish_Time，初始化为0。然后判断满足一下四个条件之一则满足min->Next和P->Next交换的条件：min->Next到达时间<=前一个进程完成时间且P->Next到达时间<=前一个进程完成时间且min->Next服务时间&

16、gt;P->Next服务时间。min->Next到达时间>前一个进程完成时间且P->Next到达时间<=前一个进程完成时间。min->Next到达时间>前一个进程完成时间且P->Next到达时间>前一个进程完成时间且min->Next到达时间>P->Next到达时间。min->Next到达时间>前一个进程完成时间且P->Next到达时间>前一个进程完成时间且min->Next到达时间=P->Next到达时间且min->Next服务时间>P->Next服务时间。（4） 时

17、间片轮转调度算法（RR）。在时间片轮转调度算法中，int GetCount(Node *H,int Time)函数用于获取在Time之前到达但未移动到运行队列的进程数量，并返回进程数Count。Node *SearchEnd(Node *H)函数用于查找循环队列的尾节点的前一个节点，并返回前一个结点的指针。void Move(Node *HeadF,Node *HeadT,int Num)用于将H1后的Num个节点移动到循环队列H2中。在调度过程中，需要定义一个循环链表，用于存放当前就绪队列中的进程。然后再不断地获取在Time之前到达但未移动到运行队列的进程数量，然后判断并在循环链表中插入新结

18、点，代码片段如下：NewArrive=GetCount(H,Time); if(NewArrive>0)Move(H,First,NewArrive); 若就绪队列中没有进程，则Time+：if(First=First->Next)Time+;若有一个进程，则取出作为当前进程：else if(First=Q)P=Q;Q=Q->Next;否则，输出其信息。若当前进程Q的剩余服务时间<=轮转时间，则当前时间Time+=Q的服务时间，Q的完成时间=当前时间，Q的轮转时间=Q的完成时间-Q的到达时间，总的轮转时间+=Q的轮转时间，并将Q从队列删除:if(Q->Servic

19、e_Time<=Round_Time)/服务时间<=轮转时间Time+=Q->Service_Time;/当前时间+=服务时间Q->Finish_Time=Time;/结束时间=当前时间printf("时 刻:%dn",Time);printf("结束 进程:%sn",Q->Name);Q->Around_Time=Q->Finish_Time-Q->Start_Time;/周转时间=结束时间=到达时间ALL_Turn_Around_Time+=Q->Around_Time;/所有进程周转时间之和+=

20、每个进程的周转时间printf("周转 时间:%dnn",Q->Around_Time);temp=Q;Q=Q->Next;P->Next=Q;free(temp);/将已经结束的进程从队列删除若当前进程Q的剩余服务时间>轮转时间，则当前时间Time+=Q的轮转时间，并将Q的服务时间-=轮转时间，再往下循环：else/服务时间>轮转时间Time+=Round_Time;/当前时间+=轮转时间printf("第%d次运行结束时间:%dnn",Q->Run_Time+1,Time);Q->Service_Time-=

21、Round_Time;/服务时间-=轮转时间Q->Run_Time+;/运行次数+P=Q;Q=Q->Next;（5） 基于静态优先级的调度算法（PSA）。同先来先服务算法，只是判断的条件不同。增设一个用于记录前一个进程的完成时间的变量Pre_Finish_Time，初始化为0。然后判断满足一下四个条件之一则满足min->Next和P->Next交换的条件（其中优先数越高，优先级越小）：min->Next到达时间<=前一个进程完成时间且P->Next到达时间<=前一个进程完成时间且min->Next优先级>P->Next优先级。m

22、in->Next到达时间>前一个进程完成时间且P->Next到达时间<=前一个进程完成时间。min->Next到达时间>前一个进程完成时间且P->Next到达时间>前一个进程完成时间且min->Next到达时间>P->Next到达时间。min->Next到达时间>前一个进程完成时间且P->Next到达时间>前一个进程完成时间且min->Next到达时间=P->Next到达时间且min->Next优先级>P->Next优先级。（6） 基于高响应比优先的动态优先级调度算法（HRR

23、N）。同先来先服务算法，只是判断的条件不同。增设一个用于记录前一个进程的完成时间的变量Pre_Finish_Time，初始化为0。然后每次进行交换前进行优先权的计算，再判断满足一下四个条件之一则满足min->Next和P->Next交换的条件：min->Next到达时间<=前一个进程完成时间且P->Next到达时间<=前一个进程完成时间且min->Next优先权>P->Next优先权。min->Next到达时间>前一个进程完成时间且P->Next到达时间<=前一个进程完成时间。min->Next到达时间>

24、前一个进程完成时间且P->Next到达时间>前一个进程完成时间且min->Next到达时间>P->Next到达时间。min->Next到达时间>前一个进程完成时间且P->Next到达时间>前一个进程完成时间且min->Next到达时间=P->Next到达时间且min->Next优先权<P->Next优先权。6、软件运行环境及限制在Linux环境下C语言编程。7、结果输出及分析文件内容为：图7.1 文件内容（1）FCFS：图7.2先来先服务（2）SJF:图7.3短作业优先（3）RR：图7.4时间片轮转（4）PSA

25、：图7.5基于静态优先级的调度（5）HRRN：图7.6基于高响应比优先的动态优先级调度8、心得体会本次课程设计的内容主要是对进程调度的掌握和使用，以及对链表的操作外加一个选择排序的使用。通过这次课程设计，加深了我对进程概念及进程调度的理解；熟悉并掌握了进程调度算法。使得理论知识得到的实践，也使我的编程能力得到了进一步提高。虽然在设计中遇到了一些问题，但在查阅资料后都解决了。9、参考文献1汤小丹，梁红兵计算机操作系统（第四版）2014年 陕西 西安电子科技大学出版社1陈媛，何波，卢玲，涂飞算法与数据结构（第二版）2011年 北京 清华大学出版社10、源程序#include<stdio.h&

26、gt;#include<stdlib.h>#include<string.h>int Pro_Num;/进程个数int Total_Time;/所有进程运行的总时间typedef struct Node/进程控制块结构体char Name10;/进程名int Piority;/优先级 数值越小优先级越高int Arrive_Time;/到达时间int Service_Time;/服务时间int Start_Time;/开始时间int Finish_Time;/结束时间int Around_Time;/周转时间int Run_Time;/运行次数struct Node *

27、Next;/指向下一个结点Node;void Create_Process(Node *H)/尾插法创建进程链表int i,Select;Node *P=H;printf("1.手动输入进程的信息n");printf("2.从文件读取进程的信息n");printf("输入选择:");scanf("%d",&Select);if(Select=1)/手动输入进程信息for(i=0;i<Pro_Num;i+)P->Next=(Node *)malloc(sizeof(Node);printf(&qu

28、ot;n输入第%d个进程的信息:",i+1);printf("n进 程 名:");scanf("%s",&P->Next->Name);printf("优 先 级:");scanf("%d",&P->Next->Piority);printf("到达时间:");scanf("%d",&P->Next->Arrive_Time);printf("服务时间:");scanf("%d

29、",&P->Next->Service_Time);P->Next->Run_Time=0;/初始化运行次数为0Total_Time+=P->Next->Service_Time;/计算总运行时间P=P->Next;P->Next=NULL;/链表尾节点置空else if(Select=2)/从文件读入进程信息FILE *fp=fopen("Process_Scheduling.dat","r");/打开文字文件只读if(fp=NULL)printf("打开文件失败!n"

30、;);exit(0);for(i=0;i<Pro_Num;i+)P->Next=(Node *)malloc(sizeof(Node);fscanf(fp,"%s %d %d %d",P->Next->Name,&P->Next->Piority,&P->Next->Arrive_Time,&P->Next->Service_Time);P->Next->Run_Time=0;/初始化运行次数为0Total_Time+=P->Next->Service_Time;/计

31、算总运行时间P=P->Next;P->Next=NULL;/链表尾节点置空fclose(fp);elseprintf("输入有误!n");exit(0);void OutPutProcess(Node *H)/输出进程Node *Q=H->Next;int ALL_Turn_Around_Time=0;/执行完所有进程周转时间只和printf("进 程 名 优 先 级 到达时间 服务时间 开始时间 完成时间 周转时间n");while(Q)printf("%s%10d%10d%10d%10d%10d%10dn",Q-

32、>Name,Q->Piority,Q->Arrive_Time,Q->Service_Time,Q->Start_Time,Q->Finish_Time,Q->Around_Time);ALL_Turn_Around_Time+=Q->Around_Time;/执行完所有进程所用时间Q=Q->Next;printf("n平均周转时间为:%fn",(float)ALL_Turn_Around_Time/Pro_Num);printf("*n");/*先来先服务*void FCFS(Node *H)Nod

33、e *First=NULL;/排列后有序链的表头指针Node *Tail=NULL;/排列后有序链的表尾指针Node *p_min;/保留键值更小的节点的前驱节点的指针Node *min;/存储最小到达时间节点Node *P;/当前比较的节点while(H->Next!=NULL)/在链表中找到达时间最小的节点for(P=H->Next,min=H->Next;P->Next!=NULL;P=P->Next)/循环遍历链表中的节点，找出此时最小的节点if(P->Next->Arrive_Time<min->Arrive_Time)/找到一个

34、比当前min小的节点p_min=P;/保存p->next的前驱节点pmin=P->Next;/保存键值更小的节点if(First=NULL)/如果有序链表目前还是一个空链表First=min;/第一次找到键值最小的节点First->Start_Time=First->Arrive_Time;/开始时间等于到达时间First->Finish_Time=First->Start_Time+First->Service_Time;/完成时间=开始时间+服务时间First->Around_Time=First->Finish_Time-First-

35、>Arrive_Time;/周转时间=完成时间-到达时间Tail=min;/尾指针指向最后一个节点else/有序链表中已经有节点Tail->Next=min;/把刚找到的最小节点放到最后if(Tail->Next->Arrive_Time<=Tail->Finish_Time)/下一个进程的到达时间<=前一个进程的完成时间Tail->Next->Start_Time=Tail->Finish_Time;/开始时间=前一个进程的完成时间else/下一个进程的到达时间>=前一个进程的完成时间Tail->Next->Sta

36、rt_Time=Tail->Next->Arrive_Time;/开始时间=到达时间Tail->Next->Finish_Time=Tail->Next->Start_Time+Tail->Next->Service_Time;/完成时间=开始时间+服务时间Tail->Next->Around_Time=Tail->Next->Finish_Time-Tail->Next->Arrive_Time;/周转时间=完成时间-到达时间Tail=min;/尾指针也要指向它if(min=H->Next)/如果找到的

37、最小节点就是第一个节点H->Next=H->Next->Next;/让H指向原H->next,即第二个节点else/如果不是第一个节点p_min->Next=min->Next;/前次最小节点的next指向当前min的next,让min离开原链表if(First!=NULL)/循环结束得到有序链表FirstTail->Next=NULL;/链表的最后一个节点的next指向NULLH->Next=First;/*短作业优先(非抢占式)*void SJF(Node *H)Node *First;/排列后有序链的表头指针Node *Tail=NULL;

38、/排列后有序链的表尾指针Node *p_min;/保留键值更小的节点的前驱节点的指针Node *min;/存储最小到达时间节点Node *P;/当前比较的节点int Pre_Finish_Time=0;/前一个进程的完成时间First=NULL;while(H->Next!=NULL)/在链表中找到达时间最小的节点for(P=H->Next,min=H->Next;P->Next!=NULL;P=P->Next)/循环遍历链表中的节点，找出此时最小的节点/1.当前进程到达时间<=Pre_Finish_Time 且 被比较进程到达时间<=Pre_Fini

39、sh_Time 且 当前进程服务时间>被比较进程服务时间/2.当前进程到达时间>Pre_Finish_Time 且 被比较进程到达时间<=Pre_Finish_Time/3.当前进程到达时间>Pre_Finish_Time 且 被比较进程到达时间>Pre_Finish_Time 且 当前进程到达时间>被比较进程到达时间/4.当前进程到达时间>Pre_Finish_Time 且 被比较进程到达时间>Pre_Finish_Time 且 当前进程到达时间=被比较进程到达时间 且 当前进程服务时间>被比较进程服务时间if(min->Arriv

40、e_Time<=Pre_Finish_Time && P->Next->Arrive_Time<=Pre_Finish_Time && min->Service_Time>P->Next->Service_Time)|(min->Arrive_Time>Pre_Finish_Time && P->Next->Arrive_Time<=Pre_Finish_Time)|(min->Arrive_Time>Pre_Finish_Time && P

41、->Next->Arrive_Time>Pre_Finish_Time && min->Arrive_Time>P->Next->Arrive_Time)|(min->Arrive_Time>Pre_Finish_Time && P->Next->Arrive_Time>Pre_Finish_Time && min->Arrive_Time=P->Next->Arrive_Time && min->Service_Time>P-&

42、gt;Next->Service_Time)p_min=P;/保存p->next的前驱节点pmin=P->Next;/保存键值更小的节点if(First=NULL)/如果有序链表目前还是一个空链表First=min;/第一次找到键值最小的节点First->Start_Time=First->Arrive_Time;/开始时间等于到达时间First->Finish_Time=First->Start_Time+First->Service_Time;/完成时间=开始时间+服务时间First->Around_Time=First->Fin

43、ish_Time-First->Arrive_Time;/周转时间=完成时间-到达时间Pre_Finish_Time=First->Finish_Time;/前一个进程的完成时间Tail=min;/尾指针指向最后一个节点else/有序链表中已经有节点Tail->Next=min;/把刚找到的最小节点放到最后if(Tail->Next->Arrive_Time<=Tail->Finish_Time)/下一个进程的到达时间<=前一个进程的完成时间Tail->Next->Start_Time=Tail->Finish_Time;/开始

44、时间=前一个进程的完成时间else/下一个进程的到达时间>=前一个进程的完成时间Tail->Next->Start_Time=Tail->Next->Arrive_Time;/开始时间=到达时间Tail->Next->Finish_Time=Tail->Next->Start_Time+Tail->Next->Service_Time;/完成时间=开始时间+服务时间Tail->Next->Around_Time=Tail->Next->Finish_Time-Tail->Next->Arriv

45、e_Time;/周转时间=完成时间-到达时间Pre_Finish_Time=Tail->Next->Finish_Time;/前一个进程的完成时间Tail=min;/尾指针也要指向它if(min=H->Next)/如果找到的最小节点就是第一个节点H->Next=H->Next->Next;/让H指向原H->next,即第二个节点else/如果不是第一个节点p_min->Next=min->Next;/前次最小节点的next指向当前min的next,让min离开原链表if(First!=NULL)/循环结束得到有序链表FirstTail-&g

46、t;Next=NULL;/链表的最后一个节点的next指向NULLH->Next=First;/*时间片轮转*int GetCount(Node *H,int Time)/获取在Time之前到达但未移动到运行队列的进程数量int Count=0;/进程数Node *Q=H->Next;while(Q&&Q->Arrive_Time<=Time)Q=Q->Next;Count+;return Count;Node *SearchEnd(Node *H)/查找循环队列的尾节点的前一个节点Node *P=H;Node *Q=H->Next;whil

47、e(Q->Next!=H)/如果不是头节点，返回尾节点的前一个节点，如果只有头节点，则直接返回P=Q;Q=Q->Next;return P;void Move(Node *H,Node *First,int Num)/将H后的Num个节点移动到循环队列First中Node *P=H;Node *Q=H->Next;Node *S=Q;/记录要移动的第一个节点while(Num>1)Q=Q->Next;Num-;P->Next=Q->Next;/以上完成从原队列中取出相关节点,S,Q分别为第一个和最后一个节点 P=SearchEnd(First);/P为

48、循环队列的尾节点的前一个节点Q->Next=P->Next;/连接到循环队列的链尾P->Next=S;/循环链表的链尾的下一个节点为头节点void RR(Node *H)/轮转调度Node *P,*Q,*temp;int Round_Time;/轮转时间int Time=0;/记录当前时间int NewArrive;/新到达进程数int ALL_Turn_Around_Time=0;/执行完所有进程周转时间只和Node *First=(Node *)malloc(sizeof(Node);First->Next=First;/循环链表，存放当前就绪队列中的进程P=Fir

49、st;Q=P->Next;/当前应当运行的进程printf("输入轮转时间:");scanf("%d",&Round_Time);printf("n");if(Round_Time<=0)printf("输入的轮转时间有误!n");exit(0);FCFS(H);while(Time<=Total_Time)NewArrive=GetCount(H,Time);/获取在Time之前到达但未移动到运行队列的进程数量if(NewArrive>0)Move(H,First,NewArriv

50、e);/将H后的NewArrive个节点移动到First队列中if(First=First->Next)/就绪队列中没有进程Time+;/自增的最小单位为1，自增后再获取在Time+1之前到达但未移动到运行队列的进程数量else if(First=Q)/就绪队列只有一个进程P=Q;/把Q放到就绪队列 Q=Q->Next;elseprintf("时 刻:%dn",Time);printf("运行 进程:%sn",Q->Name);printf("第几次运行:%dn",Q->Run_Time+1);printf(&

51、quot;到达 时间:%dn",Q->Arrive_Time);if(Q->Run_Time=0)/第一次运行，则开始时间=当前时间Q->Start_Time=Time;if(Q->Service_Time<=Round_Time)/服务时间<=轮转时间Time+=Q->Service_Time;/当前时间+=服务时间Q->Finish_Time=Time;/结束时间=当前时间printf("进程 时刻:%dn",Time);Q->Around_Time=Q->Finish_Time-Q->Arri

52、ve_Time;/周转时间=结束时间=到达时间ALL_Turn_Around_Time+=Q->Around_Time;/所有进程周转时间之和+=每个进程的周转时间printf("周转 时间:%dnn",Q->Around_Time);temp=Q;/将已经结束的进程从就绪队列删除Q=Q->Next;/指针后移P->Next=Q;/将删除掉的结点的下一个结点接到该结点的上一个结点的后边free(temp);else/服务时间>轮转时间Time+=Round_Time;/当前时间+=轮转时间printf("第%d次运行结束时间:%dnn

53、",Q->Run_Time+1,Time);Q->Service_Time-=Round_Time;/服务时间-=轮转时间Q->Run_Time+;/运行次数+P=Q;/放回就绪队列Q=Q->Next;/指针后移printf("平均周转时间:%fn",(float)ALL_Turn_Around_Time/Pro_Num);/*基于静态优先级的调度*void PSA(Node *H)Node *First=NULL;/排列后有序链的表头指针Node *Tail=NULL;/排列后有序链的表尾指针Node *p_min;/保留键值更小的节点的

54、前驱节点的指针Node *min;/存储最小到达时间节点Node *P;/当前比较的节点int Pre_Finish_Time=0;/前一个进程的完成时间while(H->Next!=NULL)/在链表中找到达时间最小的节点for(P=H->Next,min=H->Next;P->Next!=NULL;P=P->Next)/循环遍历链表中的节点，找出此时最小的节点/1.当前进程到达时间<=Pre_Finish_Time 且 被比较进程到达时间<=Pre_Finish_Time 且 当前进程优先级>被比较进程优先级/2.当前进程到达时间>Pr

55、e_Finish_Time 且 被比较进程到达时间<=Pre_Finish_Time/3.当前进程到达时间>Pre_Finish_Time 且 被比较进程到达时间>Pre_Finish_Time 且 当前进程优先级>被比较进程优先级/4.当前进程到达时间>Pre_Finish_Time 且 被比较进程到达时间>Pre_Finish_Time 且 当前进程到达时间=被比较进程到达时间 且 当前进程优先级>被比较进程优先级if(min->Arrive_Time<=Pre_Finish_Time && P->Next->

56、;Arrive_Time<=Pre_Finish_Time && min->Piority>P->Next->Piority)|(min->Arrive_Time>Pre_Finish_Time && P->Next->Arrive_Time<=Pre_Finish_Time)|(min->Arrive_Time>Pre_Finish_Time && P->Next->Arrive_Time>Pre_Finish_Time && min-&g

57、t;Piority>P->Next->Piority)|(min->Arrive_Time>Pre_Finish_Time && P->Next->Arrive_Time>Pre_Finish_Time && min->Arrive_Time=P->Next->Arrive_Time && min->Piority>P->Next->Piority)p_min=P;/保存p->next的前驱节点pmin=P->Next;/保存键值更小的节点if(First=NULL)/如果有序链表目前还是一个空链表First=min;/第一次找到键值最小的节点First->Start_Time=First->Arrive_Time;/开始时间等于到达时间First->Fin