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

评分标准优秀：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，程序完全实现设计要求，独立完成；良好：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；程序完全实现设计要求，独立完成，但存在少量错误；中等：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确；及格：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确；不及格：没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。没有独立完成，抄袭或雷同。成绩评定为： 。 指导教师： 年 月 日目 录课题一：进程调度算法的模拟011.1 设计目的011.2 任务及要求011.3 算法及数据结构021.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.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模块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）、最短作业优先调度（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，用来将多个进程控制块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区间的进程。如果两个进程具有相同长度的CPU区间，那么可以使用FCFS调度来处理。3. 优先权调度在优先权调度算法中，每个进程都有一个优先权与其关联，具有最高优先权的进程会被分配到CPU。具有相同优先权的进程按FCFS顺序调度。4. 轮转法调度（RR）轮转法（RR）调度算法是专门为分时系统而设计的。它类似于FCFS调度，但增加了抢占以在进程间切换。定义一个较小的时间单元，称为时间量或时间片。就绪队列作为循环队列处理。CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片间隔的CPU。1.3.2 头文件、控制块结构、全局变量及函数申明部分/*-头文件包含-*/#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<time.h>#include<windows.h>/*-状态码定义-*/#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：就绪态；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); /开辟头节点/*-功能函数声明-*/void 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.算法实现：/进程创建算法函数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(i<=n) SLNode *p=(SLNode *)malloc(sizeof(SLNode); p->data.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->data.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.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.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;i<20;i+)printf("");Sleep(50*p->data.ALLTime);printf("n进程 p%2d 执行完成!nn",p->data.ID);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.ALLTime>p->data.ALLTime)min_p=p;printf("正在执行区间长度最短的 %2d 进程 ",min_p->data.ID);for(int i=0;i<20;i+)printf("");Sleep(50*min_p->data.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.数据结构：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;i<20;i+)printf("");Sleep(30);if(q!=p)q->data.PRI=q->data.PRI+1;elseq->data.PRI=q->data.PRI-3;if(q->data.ALLTime>4)q->data.ALLTime-=4;elseq->data.ALLTime=0;q->data.Status=1;q=q->next;/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; free(q); q=q0->next; else if(q->data.PRI>p->data.PRI) p=q;q0=q0->next; q=q->next;if(Progress_Num>0)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=head1;SLNode *q;while(p!=NULL)printf("n正在进行一个时间片的 P%2d 进程",p->data.ID);for(int i=0;i<20;i+)printf("");Sleep(30);for(q=head1;q->next!=NULL;q=q->next)if(q->next=p)p->data.ALLTime-=4;p->data.CPUTime+=4;if(p->data.ALLTime<=0)printf("n进程%d已执行完成!n",p->data.ID);prep->next=prep->next->next;free(p);p=prep->next;elseprep=prep->next;p=p->next;printf("n进入下一次轮转!");printf("所有进程都执行完成!nn");/RR_Scheduling1.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("*-*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_Scheduling();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 实验结果系统进程初始化：先来先服务调度模拟：最短作业优先调度：优先权分时调度：轮转法调度：程序结束：1.4.2 结果分析这个课题的主要算法是对CPU进程调度的模拟。其主要调度方法有：先到先服务调度（FCFS），最短作业优先调度（SJF），优先权调度，轮转法调度（RR）。实验过程中，开始由于直接模拟导致结果立刻出来，无法观察到执行的过程，随后在程序中加入了Sleep函数就能看到模拟的执行过程。经过多次的调试和改正，还是得到了和理论上一样的实验结果（如2.4.1中所示）。课题二：系统动态分配资源的模拟2.1设计目的在计算机操作系统中，最有代表的避免死锁的算法，是银行家算法。这种算法如此命名是因为这一算发可用于银行系统，以确保银行绝不会分配其现金以至使他不能满足其所有客户的需求。此课题只目的就是为了加深对该算法的认识和掌握，进而在计算机上实现算法的全过程模拟。2.2任务及要求编程序模拟银行家算法，要求能体现算法的全过程。2.3算法及数据结构2.3.1算法的总体思想（流程）1. 银行家算法中的数据结构Available：这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Max：这是的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。Allocation：这也是一个的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。Need：这也是一个的矩阵，用以表示每一个进程尚需的各类资源数。上述三个矩阵间存在下述关系：。2. 安全性算法确定计算机系统是否处于安全状态的算法分为以下几步：1. 设和分别是长度为m和n的向量。按如下方式进行初始化，且对于。2. 查找这样的i使其满足 如果没有这样的i存在，那么就转到第4步。3. 返回到第2部。4. 如果对所有的i，Finishi=ture，那么系统处于安全状态。这个算法可能需要数量级的操作以确定状态是否安全。3. 银行家算法设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Pj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：1. 如果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，以完成本次分配;否则，将本次的试探分配作废，恢复原来的资源分配状态。2.3.2 头文件、全局变量及函数申明部分/*-头文件包含-*/#include <stdio.h>/*-状态码定义-*/#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; /用来定义作业的最大数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_Allocation(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=0,m,apply,temp=0,Finish100=0;for(i=0;i<3;+i)Worki=Avaliablei;for(i=0;i<Max_Work;i+) apply=0;for(j=0;j<Max_Resource;j+)if (Finishi=FALSE&&Needij<=Workj) apply+;if(apply=Max_Resource)for(m=0;m<Max_Resource;m+)Workm=Workm+Allocationim;Finishi=TRUE;Tempk=i;i-; k+;temp+;for(i=0;i<Max_Work;i+)if(Finishi=FALSE)printf("系统不安全!n");return INFEASIBLE;printf("系统是安全的!n");printf("分配的序列:n");for(i=0;i<Max_Work;i+)printf("%d", Tempi);if(i<Max_Work-1)printf("->");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;j<Max_Resource;j+)printf("%c:", Namej);scanf(" %d", &Requestj);for