操作系统课程设计说明书.doc

《操作系统课程设计说明书.doc》由会员分享，可在线阅读，更多相关《操作系统课程设计说明书.doc（57页珍藏版）》请在三一文库上搜索。

1、评分标准优秀：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，程序完全实现设计要求，独立完成；良好：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；程序完全实现设计要求，独立完成，但存在少量错误；中等：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确；及格：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确；不及格：没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。没有独立完成，抄袭或雷同。成绩评定为： 。 指导教师： 年 月 日目 录课题一：进程调度算法的模拟011.1 设计目的011.2 任务及要求011.3 算法及数据结构0

2、21.3.1算法的总体思想021.3.2 头文件、控制块结构、全局变量及函数申明部分021.3.3进程创建算法函数031.3.4先来先服务调度算法函数051.3.5最短作业优先调度算法函数061.3.6优先级的分时调度算法函数071.3.7查找优先级最大的进程函数081.3.8轮转调度算法函数091.3.9主函数101.3 实验结果及分析121.4.1 实验结果121.4.2 结果分析17课题二：系统动态分配资源的模拟182.1设计目的182.2任务及要求182.3算法及数据结构182.3.1算法的总体思想182.3.2 头文件、全局变量及函数申明部分202.3.3 资源分配的安全性算法212

3、.3.4 银行家算法222.3.5 资源分配函数232.3.6 资源修改函数242.3.7 资源添加函数242.3.8 资源删除函数252.3.9 作业添加函数262.3.10 打印函数272.3.11 主函数282.4实验结果及分析302.4.1实验结果302.4.2 结果分析34课题三：磁盘调度算法的模拟353.1设计目的353.2任务及要求353.3算法及数据结构353.3.1算法的总体思想353.3.2头文件、常量及函数申明部分363.3.3 调用库函数的快速排序函数373.3.4 当前磁道寻找函数373.3.5 磁盘磁道初始化模块383.3.6 FCFS模块403.3.7 SSTF模

4、块413.3.8 SCAN模块433.3.9 C-SCAN模块453.3.10 主函数483.4实验结果及分析493.4.1实验结果493.4.2结果分析52山东科技大学学生课程设计（操作系统）课题一：进程调度算法的模拟1.1设计目的在计算机操作系统中，进程调度处理从队列中选择哪个进程并为之分配CPU的问题。有几种常见的进程调度算法，如：先到先服务调度（FCFS），最短作业优先调度（SJF），优先权调度，轮转法调度（RR）。为了加深对这些算法的认识和掌握，以及进而在计算机上实现算法的全过程模拟。故做此课题以实现之。1.2任务及要求编程序模拟进程调度算法中的先到先服务调度（FCFS）、最短作业优

5、先调度（SJF）、优先权调度和轮转法调度（RR），要求能体现算法的全过程。1用语言来实现对n个进程采用不同调度算法的进程调度。2每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程优先数ID，其中0为闲逛进程，用户进程的标识数为1，2，3。（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，优先数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。（4）进程总共需要运行时间Alltime，利用随机函数产生。（5）进程状态，0：就绪态；1：运行态；2：阻塞态。（6）队列指针next，用来

6、将多个进程控制块PCB链接为队列。3优先数改变的原则（1）进程在就绪队列中每呆一个时间片，优先数增加1。（2）进程每运行一个时间片，优先数减3。4在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后，所有的进程控制块PCB链接成就绪队列。1.3算法及数据结构1.3.1算法的总体思想（流程）1. 先到先服务调度（FCFS）先到先服务调度算法（FCFS）是最简单的调度算法。采用这种方案，先请求CPU的进程被首先分配到CPU。2. 最短作业优先调度（SJF）最短作业优先调度（SJF）算法是将每个进程与其下一个CPU区间段相关联。当CPU为可用时，它会赋给具有最短后续CPU区间的进程

7、。如果两个进程具有相同长度的CPU区间，那么可以使用FCFS调度来处理。3. 优先权调度在优先权调度算法中，每个进程都有一个优先权与其关联，具有最高优先权的进程会被分配到CPU。具有相同优先权的进程按FCFS顺序调度。4. 轮转法调度（RR）轮转法（RR）调度算法是专门为分时系统而设计的。它类似于FCFS调度，但增加了抢占以在进程间切换。定义一个较小的时间单元，称为时间量或时间片。就绪队列作为循环队列处理。CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片间隔的CPU。1.3.2 头文件、控制块结构、全局变量及函数申明部分/*-头文件包含-*/#include#include#incl

8、ude#include#include/*-状态码定义-*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/*-进程控制块结构定义-*/typedef struct PCB int ID; /进程号,用于标示不同的进程 int PRI; /进程优先级 int CPUTime; /进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4 int ALLTime; /进程运行完成所需要的总时间int Status; /用于表示进程状态，0：就绪态

9、；1：运行态；2：阻塞态Datatype;typedef struct NodeDatatype data; /数据域struct Node *next; /指针域SLNode;/*-全局变量的定义-*/int Progress_Num; /用来存放进程数SLNode *head=(SLNode *)malloc(sizeof(SLNode); /开辟头节点SLNode *head1=(SLNode *)malloc(sizeof(SLNode); /开辟头节点SLNode *head2=(SLNode *)malloc(sizeof(SLNode); /开辟头节点/*-功能函数声明-*/vo

10、id Create_Process(int); /进程创建算法函数void FCFS_Scheduling(); /先来先服务算法函数void SJF_Scheduling(); /最短作业优先调度算法函数void Action_Scheduling(SLNode); /优先级的分时调度算法函数void Search_Max_PRI(int); /查找优先级最大的进程算法函数void RR_Scheduling(int); /轮转调度算法函数1.3.3进程创建算法函数1. 功能：根据用户输入的进程数创建符合条件的进程。2.数据结构：void Create_Process(int); 3.算法实

11、现：/进程创建算法函数void Create_Process(int n)int i=1;srand(int)time(0); head-next=NULL; SLNode *q=head;printf(进程分配情况如下：n);printf(*n);printf( 优先数 优先级 CPUTime AllTime Status n); while(idata.ID=i;p-data.CPUTime=0;p-data.Status=0;p-data.PRI=rand()%20+1;p-data.ALLTime=rand()%12+1;printf(%8d%10d%10d%10d%10d%n,p-d

12、ata.ID,p-data.PRI, p-data.CPUTime,p-data.ALLTime,p-data.Status);p-next=NULL;q-next=p;q=q-next;i+;SLNode *p0=head1;head1-next=NULL;for(q=head-next;q!=NULL;q=q-next)SLNode *r=(SLNode *)malloc(sizeof(SLNode);r-data.ID=q-data.ID;r-data.CPUTime=q-data.CPUTime;r-data.Status=q-data.Status;r-data.PRI=q-data

13、.PRI; r-data.ALLTime=q-data.ALLTime;p0-next=r;r-next=NULL;p0=p0-next;SLNode *p1=head2;head2-next=NULL;for(q=head-next;q!=NULL;q=q-next)SLNode *k=(SLNode *)malloc(sizeof(SLNode);k-data.ID=q-data.ID;k-data.CPUTime=q-data.CPUTime;k-data.Status=q-data.Status;k-data.PRI=q-data.PRI; k-data.ALLTime=q-data.

14、ALLTime;p1-next=k;k-next=NULL;p1=p1-next;/Create_Process1.3.4先来先服务调度算法函数1. 功能：用先来先服务调度（FCFS）算法对系统进程进行调度。2.数据结构：void FCFS_Scheduling();3.算法实现：/先来先服务算法函数void FCFS_Scheduling()SLNode *p=head-next;while(p!=NULL)printf(正在执行 p%2d 进程 ,p-data.ID);for(int i=0;idata.ALLTime);printf(n进程 p%2d 执行完成!nn,p-data.ID)

15、;p=p-next;printf(n);printf(所有进程都执行完成。nn);/FCFS_Scheduling1.3.5最短作业优先调度算法函数1. 功能：用最短作业优先调度（SJF）算法对系统进程进行调度。2.数据结构：void SJF_Scheduling();3.算法实现：/最短作业优先调度算法函数void SJF_Scheduling()SLNode *p;SLNode *min_p;while(head2-next!=NULL)min_p=head2-next;for(p=head2-next;p!=NULL;p=p-next)if(min_p-data.ALLTimep-dat

16、a.ALLTime)min_p=p;printf(正在执行区间长度最短的 %2d 进程 ,min_p-data.ID);for(int i=0;idata.ALLTime);printf(n进程 p%2d 执行完成!nn,min_p-data.ID);for(p=head2;p!=NULL;p=p-next)if(p-next=min_p)p-next=p-next-next;free(min_p);printf(n);printf(所有进程都执行完成!nn);/SJF_Scheduling1.3.6 优先级的分时调度算法函数1. 功能：用优先级的分时调度算法对系统进程进行调度。2.数据结构：

17、void Action_Scheduling(SLNode);3.算法实现：/优先级的分时调度算法函数void Action_Scheduling(SLNode *p)SLNode *q=head-next;while(q!=NULL)printf(n正在执行一个时间片的 p2%d 进程 ,p-data.ID);for(int i=0;idata.PRI=q-data.PRI+1;elseq-data.PRI=q-data.PRI-3;if(q-data.ALLTime4)q-data.ALLTime-=4;elseq-data.ALLTime=0;q-data.Status=1;q=q-ne

18、xt;/Action_Scheduling1.3.7 查找优先级最大的进程函数1. 功能：用于查找优先级最大的进程的函数。2.数据结构：void Search_Max_PRI(int m);3.算法实现：/查找优先级最大的进程函数void Search_Max_PRI(int)SLNode *p=head-next;SLNode *q=head-next;SLNode *q0=head;while(q!=NULL)if(q-data.ALLTime=0)printf(n进程 p2%d 已执行完成!n,q-data.ID);Progress_Num-; q0-next=q0-next-next;

19、 free(q); q=q0-next; else if(q-data.PRIp-data.PRI) p=q;q0=q0-next; q=q-next;if(Progress_Num0)Action_Scheduling(p);/Search_Max_PRI1.3.8 轮转调度算法函数1. 功能：用轮转法调度（RR）算法对系统进程进行调度。2.数据结构：void RR_Scheduling(int);3.算法实现：/轮转调度算法void RR_Scheduling(int m)SLNode *p;while(head1-next!=NULL)p=head1-next;SLNode *prep=

20、head1;SLNode *q;while(p!=NULL)printf(n正在进行一个时间片的 P%2d 进程,p-data.ID);for(int i=0;inext!=NULL;q=q-next)if(q-next=p)p-data.ALLTime-=4;p-data.CPUTime+=4;if(p-data.ALLTimedata.ID);prep-next=prep-next-next;free(p);p=prep-next;elseprep=prep-next;p=p-next;printf(n进入下一次轮转!);printf(所有进程都执行完成!nn);/RR_Schedulin

21、g1.3.9 主函数1. 功能：主函数。2.数据结构：int main();3.算法实现：/*-主函数模块-*/int main()printf(*-*n);printf(| *系统进程调度算法的模拟* |n);printf(*-*n);printf(请输入系统进程数：);scanf(%d,&Progress_Num);int Choose=-1;if(Progress_Num=0) printf(此时没有就绪进程。n);elseCreate_Process(Progress_Num);printf(n-*系统进程初始化完毕，下面开始进程调度算法模拟!*-nn);while(1)printf(

22、*-*n);printf(| *进程调度算法模拟开始* |n);printf(| 1、先来先服务调度 2、最短作业优先调度 |n);printf(| 3、优先权分时调度 4、轮转法调度 0、退出 |n);printf(*-*n);printf(n请输入您想执行的算法序号:);scanf( %d, &Choose);switch (Choose)case 0:return ERROR;case 1:printf(n-*先来先服务调度算法模拟开始*-nn);FCFS_Scheduling();break;case 2:printf(n-*最短作业优先调度算法模拟开始*-nn);SJF_Schedu

23、ling();break;case 3:printf(n-*优先权的分时调度算法模拟开始*-nn);while(head-next!=NULL)Search_Max_PRI(Progress_Num);printf(所有进程都执行完成!nn);break;case 4:printf(n-*轮转法调度算法模拟开始*-nn);RR_Scheduling(Progress_Num);break;default :printf(您输入的选择有误!请重新输入!n);break;return OK;/main1.4实验结果及分析1.4.1 实验结果系统进程初始化：先来先服务调度模拟：最短作业优先调度：优先

24、权分时调度：轮转法调度：程序结束：1.4.2 结果分析这个课题的主要算法是对CPU进程调度的模拟。其主要调度方法有：先到先服务调度（FCFS），最短作业优先调度（SJF），优先权调度，轮转法调度（RR）。实验过程中，开始由于直接模拟导致结果立刻出来，无法观察到执行的过程，随后在程序中加入了Sleep函数就能看到模拟的执行过程。经过多次的调试和改正，还是得到了和理论上一样的实验结果（如2.4.1中所示）。课题二：系统动态分配资源的模拟2.1设计目的在计算机操作系统中，最有代表的避免死锁的算法，是银行家算法。这种算法如此命名是因为这一算发可用于银行系统，以确保银行绝不会分配其现金以至使他不能满足其

25、所有客户的需求。此课题只目的就是为了加深对该算法的认识和掌握，进而在计算机上实现算法的全过程模拟。2.2任务及要求编程序模拟银行家算法，要求能体现算法的全过程。2.3算法及数据结构2.3.1算法的总体思想（流程）1. 银行家算法中的数据结构Available：这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Max：这是的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。Allocation：这也是一个的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。Need

26、：这也是一个的矩阵，用以表示每一个进程尚需的各类资源数。上述三个矩阵间存在下述关系：。2. 安全性算法确定计算机系统是否处于安全状态的算法分为以下几步：1. 设和分别是长度为m和n的向量。按如下方式进行初始化，且对于。2. 查找这样的i使其满足 如果没有这样的i存在，那么就转到第4步。3. 返回到第2部。4. 如果对所有的i，Finishi=ture，那么系统处于安全状态。这个算法可能需要数量级的操作以确定状态是否安全。3. 银行家算法设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Pj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：1. 如果

27、Requestij=Needi，j，便转向步骤2;否则认为出错，因为它所需要的资源数已超出它所宣布的最大值。2. 如果Requestij=Availablei，j， 便转向步骤3；否则，表示尚无足够资源， Pi须等待。3. 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值:Availablej:= Availablej- Requestij；Allocationi，j:= Allocationi，j+ Requestij；Needi，j:=Needi，j-Requestij；系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分

28、配;否则，将本次的试探分配作废，恢复原来的资源分配状态。2.3.2 头文件、全局变量及函数申明部分/*-头文件包含-*/#include /*-状态码定义-*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/*-全局变量的定义-*/int Max_Resource=0; /用来定义资源的最大数char Name100=0; /用来存放资源的名称int Avaliable100=0; /用来存放系统的可用资源数int Max_Work=0; /用来定义

29、作业的最大数int Max100100=0; /用来存放各进程所需各类资源的最大需求int Allocation100100=0; /用来存放各个进程系统已分配资源int Need100100=0; /用来存放各个进程还需要资源int Request100=0; /用来存放进程的请求资源向量int Work100=0; /用来存放系统可提供资源int Temp100=0; /用来存放资源分配的安全序列/*-功能函数声明-*/int Safe_Algorithm(); /资源分配的安全性算法int Bank_Algorithm(); /用银行家算法对申请资源对进行判定int Resource_A

30、llocation(int); /用于对资源进行分配的函数int Modify_Resources(); /用于修改资源的函数int Add_Resources(); /用于添加资源的函数int Del_Resources(); /用于删除资源的函数int Add_Process(); /用于添加作业的函数int Display_Resources(); /用于在屏幕打印出资源矩阵2.3.3 资源分配的安全性算法1. 功能：资源分配的安全性算法。2.数据结构：int Safe_Algorithm();3.算法实现：/资源分配的安全性算法int Safe_Algorithm()int i,j,k

31、=0,m,apply,temp=0,Finish100=0;for(i=0;i3;+i)Worki=Avaliablei;for(i=0;iMax_Work;i+) apply=0;for(j=0;jMax_Resource;j+)if (Finishi=FALSE&Needij=Workj) apply+;if(apply=Max_Resource)for(m=0;mMax_Resource;m+)Workm=Workm+Allocationim;Finishi=TRUE;Tempk=i;i-; k+;temp+;for(i=0;iMax_Work;i+)if(Finishi=FALSE)p

32、rintf(系统不安全!n);return INFEASIBLE;printf(系统是安全的!n);printf(分配的序列:n);for(i=0;iMax_Work;i+)printf(%d, Tempi);if(i);printf(n);return ERROR;/Safe_Algorithm2.3.4 银行家算法1. 功能：用银行家算法对申请资源对进行判定。2.数据结构：int Bank_Algorithm(); 3.算法实现：/用银行家算法对申请资源对进行判定int Bank_Algorithm()char ch=y;int i=0,j=0;printf(请输入要求分配的资源进程号(0-%d):, Max_Work-1);scanf( %d, &i);printf(请输入进程 %d 申请的资源:n);for(j=0;jMax_Resource;j+)printf(%c:, Namej);scanf( %d, &Requestj);for