操作系统课程设计编程内容

1、实验一 进程调度一、实验目的通过一个简单的进程调度模拟程序的实现， 加深对进程调度算法， 进程切换 的理解。二、实验容采用动态优先数的方法， 编写一进程调度程序模拟程序。 模拟程序只进行相 应的调度模拟操作，不需要实际程序。 提示 ：(1) 假定系统有五个进程，每一个进程用一个进程控制块 PCB来代表，进程 控制块的格式为：进程名指针 要求运行时间 优先数 状态 其中，进程名作为进程的标识，假设五个进程的进程名分别为 P1， P2， P3， P4， P5。指针按优先数的大小把五个进程连成队列， 用指针指出下一个进程的进程控 制块的首地址，最后一个进程中的指针为“ 0”。 要求运行时间假设进程需

2、要运行的单位时间数。优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。 状态可假设有两种状态， “就绪”状态和“结束”状态。 五个进程的初始状 态都为“就绪”，用“R'表示，当一个进程运行结束后，它的状态为“结束”， 用“ E”表示。(2) 在每次运行你所设计的处理器调度程序之前， 为每个进程任意确定它的 “优先数”和“要求运行时间”。(3) 为了调度方便， 把五个进程按给定的优先数从大到小连成队列。 用一单 元指出队首进程，用指针指出队列的连接情况。(4) 处理器调度总是选队首进程运行。 采用动态改变优先数的办法， 进程每 运行一次优先数就减“ 1”。由于本实习是模拟处理器

3、调度，所以，对被选中的 进程并不实际的启动运行，而是执行：优先数 -1要求运行时间 -1来模拟进程的一次运行。提醒注意的是： 在实际的系统中， 当一个进程被选中运行时， 必须恢复进程 的现场，让它占有处理器运行， 直到出现等待事件或运行结束。 在这里省去了这 些工作。(5) 进程运行一次后， 若要求运行时间 ?0，则再将它加入队列 (按优先数大 小插入，且置队首标志)；若要求运行时间 =0，则把它的状态修改成“结束” (E)， 且退出队列。(6) 若“就绪”状态的进程队列不为空，则重复上面( 4)和( 5)的步骤，直到所有进程都成为“结束”状态。(7) 在所设计的程序中应有显示或打印语句，能显

4、示或打印每次被选中进程 的进程名以及运行一次后进程队列的变化。(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态 变化过程。三：实验流程图退出四、实验代码#include <stdio.h>#include <stdlib.h> #include <string.h>#include <ctype.h>/* 进程控制块数据结构 */ typedef struct nodechar name10;/* int prio; /* int count; /*进程名

5、 */ 进程优先级 */ 进程运行时间 */char state; /*进程的状态：'R':运行:W :等待,'F':结束*/struct node *next;/* 指向下一个进程的指针 */为就绪PCB;PCB *finish,*ready,*tail,*run;/*指向三个队列的队首的指针， tail队列的队尾指针 */int N;/* 定义进程的数目 */* 函数功能： 将进程就绪队列中第一个放进就绪队列 函数原型： void firstin(void)函数参数： void函数返回值： void */ void firstin(void) if(read

6、y!=NULL)run=ready; ready=ready->next; run->state='R'run->next=NULL;elserun=NULL;/* 函数功能：输出所有进程信息的函数 函数原型： void prt(char algo) 函数参数： char a :a='p' 为优先级， ='r' 为时间片轮转 函数返回值： void*/void prt(char algo)PCB *p;printf(" name count priority state n"); p=ready;while(

7、p!=NULL) printf("%-10s,%-10d,%-10d,%-5cn",p->name,p->prio,p->state); p=p->next;p=finish;while(p!=NULL) printf("%-10s,%-10d,%-10d,%-5cn",p->name,p->prio,p->state);p=p->next;getchar();/* 函数功能：优先级法调度将进程插入到就绪队列算法 函数原型： void insert1(PCB *q)函数参数： PCB *q 待插入的队列进程

8、控制块 优先级越高，插入越靠前函数返回值： void*/void insert1(PCB *q)PCB *p,*s,*r; /*p,r 用来控制就绪队列滚动， S 指向插入的队列 */ int b; /*b 作为插入控制标志的 */ s=q;p=ready;r=p;b=1;if(s->prio>=ready->prio)s->next=ready;ready=s;elsewhile(p!=NULL)&&b)if(p->prio>=s->prio)r=p;p=p->next;elseb=0; s->next=p; r->

9、next=s;/* 函数功能：采用优先级进程调度法时，进程初始化函数 函数原型： void pcreate_task(char algo) 函数参数： char algo: 函数返回值： void*/ void pcreate_task(char algo)PCB *p;int i,time;char na10; ready=NULL; finish=NULL; run=NULL;for(i=0;i<N;i+) p=(PCB*)malloc(sizeof(PCB); printf("Enter the name of processn"); scanf("%

10、s",na);printf("Enter the time of processn"); scanf("%d",&time);strcpy(p->name,na); p->count=time; p->state='W' p->prio=time;if(ready=NULL)ready=p;ready->next=NULL; elseinsert1(p);printf("Output the waiting processes informationn"); prt(al

11、go);firstin();/* 函数功能：采用优先级进程调度法时，进程调度函数 函数原型： void priority(char algo)函数参数： char a: 进程调度类别标志： 'P' 优先级 'R' 时间片轮转 函数返回值： void*/priority(char algo) while(run!=NULL)run->count-=1; run->prio-=1; if(run->count=0) run->next=finish;finish=run;run->state='E' run=NULL;f

12、irstin();else if(ready!=NULL)&&(run->prio<ready->prio) run->state='W' insert1(run); run=NULL;firstin(); prt(algo);return(0);/*main 函数 */int main()char algo;algo='P'printf("Please enter the number of processes N:n");scanf("%d",&N); pcreate_t

13、ask(algo); priority(algo); return(0);实验二 存储管理一、实验目的存储管理的主要功能之一是合理地分配空间。 请求页式管理是一种常用的虚 拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计 , 了解虚 拟存储技术的特点 , 掌握请求页式存储管理的页面置换算法。二、实验容通过随机数产生一个指令序列 ,共 320条指令。指令的地址按下述原则生成 50% 的指令是顺序执行的； 25% 的指令是均匀分布在前地址部分； 25% 的指令是均匀分布在后地址部分。具体的实施方法是 : 在 0,319 的指令地址之间随机选取一起点 m; 顺序执行一条指令

14、; 在前地址0,m+1中随机选取一条指令并执行，该指令的地址为 m' 顺序执行一条指令，其地址为m+1; 在后地址m+2,319中随机选取一条指令并执行； 重复上述步骤 , 直到执行 320 次指令。(1) 将指令序列变换成为页地址流设：页面大小为 1K; 用户存容量为 4 页到 32 页 ; 用户虚存容量为 32K 。在用户虚存中 , 按每 K 存放 10 条指令排列虚存地址 , 即 320 条指令 在虚存中的存放方式为 :第 0 条 第 9 条指令为第 0 页 ( 对应虚存地址为 0,9);第 10 条 第 19 条指令为第 1 页 ( 对应虚存地址为 10,19 ) ;第 310

15、 条 第 319 条指令为第 31 页 ( 对应虚存地址为 310,319) 按以上方式 , 用户指令可组成 32 页。(2) 计算并输出下述各种算法在不同存容量下的命中率。 先进先出的算法 (FIFO) ； 最近最久未使用算法 (LRU);命中率=1 -页面失效次数/页地址流长度在本实验中 , 页地址流长度为 320, 页面失效次数为每次访问相应指令时 该指令所对应的页不在存的次数。三、随机数产生办法关于随机数产生办法 ,Linux 或 UNIX 系统提供函数 srand( ) 和 rand( ), 分别进行初 始化和产生随机数。例如 :srand () ;语句可初始化一个随机数 ;ao=1

16、0 * rand( ) / 32767 * 319 + 1; a1= 10 * rand( ) / 32767 * ao;III语句可用来产生 a0 与 a1 中的随机数。四，实验代码 /* *此程序为页面调度程序，用于模拟虚存与主存之间的页面置换 * 并同时采用 FIFO,LRU,OPT,LFT,NUR 几种算法 *并比较在不同算法下及不同的主存页面状态下，主存的命中率的高低 */#include "stdlib.h"#include "stdio.h"#include "time.h"#define TRUE 1/*页面失效#de

17、fine FALSE 0#define INVALID -1/*指令流长 */*虚页长 */*清零周期 */#define null 0#define total_instruction 320#define total_vp 32#define clear_period 50typedef struct/* 页面结构 */int pn,pfn,counter,time;pl_type;/*-pn 为页面队列号 ,pfn 为页面控制结构中的页号， counter 为访问次数 -*/pl_type pltotal_vp;/* 页面结构数组 ;建立虚存页面空间 */*此程序有两种结构，一种是页面结

18、构，用于页面的实际转换*即将某一页面的实际参数作改变*另一种是页面控制结构，用于控制页面的调度struct pfc_struct/* 页面控制结构 ;主存中的页面调度结构 */int pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;/*-p272 c 语言书 ;用于将定义语句 struct pfc_struct 改成 pfc_type-*/ /*-pfctotal_vp 为用户进程虚页控制结构； freepf_head 闲页面头指针； *-busypf_head 忙页面头指针； busypf_tail 忙页面尾

19、指针 */pfc_type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;int diseffect,atotal_instruction;/* 定义页面缺失次数 diseffect 和指令序列表 a*/int pagetotal_instruction,offsettotal_instruction;/* 定义每条指令分别在哪一 页 pagei 以及在此页中的偏移量 offseti*/void initialize();void FIFO();void LRU();void OPT();void LFU();void NUR();voi

20、d initialize(int total_pf)/* 初始化相关数据 ;total_pf 用户进程的存页面数 */ int i;diseffect=0;for (i=0;i<total_vp;i+)/* 虚存页面设初值 */ pli.pn=i; pli.pfn=INV ALID; pli.counter=0; pli.time=-1;/* 页面控制结构中的访问次数为0，时间为 -1*/for (i=1;i<total_pf;i+) /* 主存页面设初值 */ pfci-1.next=&pfci;pfci-1.pfn=i-1;/*建立 pfci-1和 pfci之间的 */

21、pfctotal_pf-1.next=NULL; pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/* 空页面队列的头指针为 pfc0*/void FIFO(int total_pf) /*FIFO(First In First Out) ALGORITHM*/ /* 该算法中 freepf_head 用于指示主存页面中空闲页面的头位置 ,而并没 有创建新的队列*同样,busypf_head及busypf_tail也没有创建新的队列，而是用于指示主 存结构中忙页面的头尾* 而且由于是纯算法 ,所以并没有考虑页面自己消掉的可能性 ,而纯粹由

22、调度结构控制*因此,当页面满后 ,只有命中不命中目标 ,只有当释放页面时 ,会暂时性地 产生一个 free 页面*/ int i,j;pfc_type *p,*t;initialize(total_pf);/*利用子程序初始化相关页面控制用数据结构 */busypf_head=busypf_tail=NULL;/*忙页面队列头，队列尾 */for (i=0;i<total_instruction;i+)/*通过查看虚存中页面的pfn是否为INVALID来判断该页面是否在主存中* 若则应存在一个值 */if (plpagei.pfn=INV ALID)/*页面失效 */diseffect+

23、;/* 失效次数 */if (freepf_head=NULL)/*无空闲页面 */p=busypf_head->next;plbusypf_head->pn.pfn=INVALID;/*将释放出的页面的 pfn 改为 INVALID*/ freepf_head=busypf_head;/*释放忙页面队列中的第一个页面 */freepf_head->next=NULL;/*因为只有一个空闲页面 ,所以 next 必为 NULL*/busypf_head=p;p=freepf_head->next;/* 按 FIFO 方式调新页面入存页面 */freepf_head-&g

24、t;next=NULL;/*当前空闲页面将被占用，因此其next必为NULL*/freepf_head->pn=pagei;/* 这里的freepf_head指的是当前将被占用的页面*/plpagei.pfn=freepf_head->pfn;/*仅仅是存放一个值而已,用以区分页面不在主存中的INVALID*/if (busypf_tail=NULL) busypf_head=busypf_tail=freepf_head;/* 当主存页面为 空的情况下 ,处理尾部 */elsebusypf_tail->next=freepf_head;busypf_tail=freepf_

25、head;freepf_head=p;/*空闲页面指向下一个 */ printf("FIFO:%6.4f-",1-(float)diseffect/320);void LRU(int total_pf)/*LRU(Last RecentlyUsed) ALGORITHM */*此处LRU算法并未用到pfc队列* 而是用是否为 INVALID 来判断该页面是否被载入存*若未被载入存,则被载入，同时在有空闲页面的情况下将freepf_head指 向下一个*若没有空闲页面 ,则在 plpagei.pfn!=INV ALID 的页中选出时间最小 的 ,将之替换出去*/ int mi

26、n,minj,i,j,present_time;initialize(total_pf);present_time=0;for (i=0;i<total_instruction;i+)/*页面失效 */* 失效次数 */*无空闲页面 */if (plpagei.pfn=INV ALID) diseffect+;if (freepf_head=NULL) min=32767;/*找出主存中时间最小的页面 */for(j=0;j<total_vp;j+) if(plj.pfn!=INV ALID&&min>plj.time)/在 pl 中的页面凡是标注有值的均是在

27、主存中的页面！ ！ min=plj.time;minj=j;/！错/*freepf_head=&pfcpfcminj.pfn;*/误！ minj 取值会大于 total_pfplminj.pfn=INV ALID;plminj.time=-1;plpagei.pfn=pagei;elseplpagei.pfn=pagei;页面被载入存freepf_head=freepf_head->next;/freepf_head 指向下一个elseplpagei.time=present_time;中的页面的 time 增大，以确保不被最先置换 */present_time+; printf

28、("LRU:%6.4f-",1-(float)diseffect/320);/标志此/*页面有效则将命/为了表示void NUR(int total_pf) 用算法 ALGORITHM */ int i,j,dp,cont_flag,old_dp; pfc_type *t;/*NUR 最近不经常使initialize(total_pf);dp=0;for (i=0;i<total_instruction;i+)if (plpagei.pfn=INV ALID) diseffect+;if (freepf_head=NULL) cont_flag=TRUE; old_d

29、p=dp; while (cont_flag) if(pldp.counter=0&&pldp.pfn!=INV/* 页面失效 */*失效次数 */* 无空闲页面 */ALID)cont_flag=FALSE;else dp+; if(dp=total_vp) dp=0; if(dp=old_dp)for(j=0;j<total_vp;j+) plj.counter=0; freepf_head=&pfcpldp.pfn; pldp.pfn=INV ALID; freepf_head->next=NULL;plpagei.pfn=freepf_head-&g

30、t;pfn; freepf_head=freepf_head->next;elseplpagei.counter=1;if(i%clear_period=0)for(j=0;j<total_vp;j+) plj.counter=0; printf("NRU:%6.4f",1-(float)diseffect/320);void LFU(int total_pf) Used) ALGORITHM */ int i,j,min,minpage;pfc_type *t;/*LFU(Leat Frequentlyinitialize(total_pf);for (i=0

31、;i<total_instruction;i+)/*页面失效 */*失效次数 */* 无空闲页面 */ALID)if (plpagei.pfn=INV ALID) diseffect+;if (freepf_head=NULL) min=32767; for(j=0;j<total_vp;j+)if(min>plj.counter&&plj.pfn!=INV min=plj.counter;minpage=j;plj.counter=0; freepf_head=&pfcpfcminpage.pfn; plminpage.pfn=INV ALID; f

32、reepf_head->next=NULL;plpagei.pfn=freepf_head->pfn; freepf_head=freepf_head->next;elseprintf("LFU:%6.4f-",1-(float)diseffect/320);void OPT(int total_pf) /*OPT(Optimal Replacement) ALGORITHM*/ int i,j,max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf);据结构 */for (i=0;i<total_instruction;i+)if (plpagei.pfn=INV ALID) diseffect+;if (freepf_head=NULL) for(j=0;j<total_vp;j+)if(plj.pfn!=INV ALID) distj=32767;else