操作系统课程设计说明书

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

33、-%d):, max_work-1);scanf( %d, &i);printf(请输入进程 %d 申请的资源:n);for(j=0;jmax_resource;j+)printf(%c:, namej);scanf( %d, &requestj);for (j=0;jneedij)printf(进程 %d 申请的资源大于它需要的资源!分配不合理，不予分配!n, i);ch=n; break;else if(requestjavaliablej)printf(进程 %d 申请的资源大于系统现在可利用的资源!分配错误，不予分配!n);ch=n; break; if(ch=y)resource_a

34、llocation(i);display_resources();safe_algorithm();return ok;/bank_algorithm2.3.5 资源分配函数1. 功能：用于对资源进行分配。2.数据结构：int resource_allocation(int);3.算法实现：/用于对资源进行分配int resource_allocation(int i) int j;for (j=0;jmax_work;j+) avaliablej=avaliablej-requestj;allocationij=allocationij+requestj;needij=needij-requ

35、estj;return ok;/resource_allocation2.3.6 资源修改函数1. 功能：用于修改资源的函数。2.数据结构：iint modify_resources();3.算法实现：/用于修改资源函数int modify_resources()printf(系统目前可用的资源avaliable:n); for(int i=0;imax_resource;i+)printf(%c:%dn, namei, avaliablei);printf(输入系统可用资源avaliable:n);for(i=0;i3;+i)scanf( %d, &avaliablei);printf(经修

36、改后的系统可用资源为:n);for (i=0;imax_resource;i+)printf(%c:%dn, namei, avaliablei);display_resources();safe_algorithm();return ok;/modify_resources2.3.7 资源添加函数1. 功能：用于添加资源的函数。2.数据结构：int add_resources();3.算法实现：/用于添加资源int add_resources() int n,temp;printf(请输入需要添加资源种类的数量:);scanf( %d, &n);temp=max_resource;max_r

37、esource=max_resource+n;for(int i=0;in;i+)printf(名称:);scanf( %c, &nametemp);printf(数量:);scanf( %d, &avaliabletemp+);display_resources();safe_algorithm();return ok;/add_resources2.3.8 资源删除函数1. 功能：用于对资源删除的函数。2.数据结构：int del_resources() ;3.算法实现：/用于删除资源int del_resources()char del_name;int i,temp=1;printf(

38、请输入需要删除的资源名称:);do scanf( %c, &del_name);for(i=0;imax_resource;i+)if(del_name=namei)temp=0;break;if(i=max_resource)printf(该资源名称不存在，请重新输入:); while(temp);for(int j=i;jmax_resource-1;j+)namej=namej+1;avaliablej=avaliablej+1; max_resource=max_resource-1;display_resources();safe_algorithm();return ok;/del

39、_resources2.3.9 作业添加函数1. 功能：用于对作业的添加函数。2.数据结构：int add_process();3.算法实现：/用于添加作业int add_process() int temp=max_work;max_work=max_work+1;printf(请输入该作业的最打需求量max:n);for(int i=0;imax_resource;i+)printf(%c:, namei);scanf( %d, &maxtempi);needtempi=maxtempi-allocationtempi;display_resources();safe_algorithm();return ok;/add_process2.3.10 打印函数1. 功能：用于在屏幕上打印资源矩阵。2.数据结构：int display_resources();3.算法实现：/用于在屏幕上打印资源矩阵int display_resources()int i,j; printf(系统目前可