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

.实验一 进程调度一、实验目的通过一个简单的进程调度模拟程序的实现，加深对进程调度算法，进程切换的理解。 二、实验内容采用动态优先数的方法，编写一进程调度程序模拟程序。模拟程序只进行相应的调度模拟操作，不需要实际程序。 提示：(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：进程名指针要求运行时间优先数状态其中，进程名作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。指针按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。要求运行时间假设进程需要运行的单位时间数。优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。(4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实习是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：优先数-1要求运行时间-1来模拟进程的一次运行。提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。(5) 进程运行一次后，若要求运行时间?0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。(6) 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。三：实验流程图输入进程名及属性按优先级排列进程放入就绪队列调用首进程运行优先数减一，要求运行时间要求运行时间0要求运行时间=0修改进程状态为空，输出各进程状态就绪队列为空就绪队列不为空退出四、实验代码#include #include #include #include /*进程控制块数据结构*/typedef struct node char name10;/*进程名*/ int prio; /*进程优先级*/ int count; /*进程运行时间*/ 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(ready!=NULL) run=ready; ready=ready-next; run-state=R; run-next=NULL; else run=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(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 待插入的队列进程控制块 优先级越高，插入越靠前 函数返回值：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; else while(p!=NULL)&b) if(p-prio=s-prio) r=p; p=p-next; else b=0; s-next=p; r-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;iname,na); p-count=time; p-state=W; p-prio=time; if(ready=NULL) ready=p; ready-next=NULL; else insert1(p); printf(Output the waiting processes informationn); prt(algo); 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; firstin(); else if(ready!=NULL)&(run-prioprio) 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_task(algo); priority(algo); return(0); 实验二 存储管理一、实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计 , 了解虚拟存储技术的特点 , 掌握请求页式存储管理的页面置换算法。二、实验内容通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成 : 50% 的指令是顺序执行的； 25% 的指令是均匀分布在前地址部分； 25% 的指令是均匀分布在后地址部分。具体的实施方法是 :在 0,319 的指令地址之间随机选取一起点 m;顺序执行一条指令;在前地址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 条 第 319 条指令为第 31 页 ( 对应虚存地址为 310,319) 。按以上方式 , 用户指令可组成 32 页。(2) 计算并输出下述各种算法在不同内存容量下的命中率。 先进先出的算法 (FIFO)； 最近最久未使用算法 (LRU);命中率 = 1 - 页面失效次数页地址流长度在本实验中 , 页地址流长度为 320, 页面失效次数为每次访问相应指令时 , 该指令所对应的页不在内存的次数。三、随机数产生办法关于随机数产生办法 ,Linux 或 UNIX 系统提供函数 srand( ) 和 rand( ), 分别进行初 始化和产生随机数。例如 :srand （）; 语句可初始化一个随机数 ; ao=10 * rand( ) / 32767 * 319 + 1;a1= 10 * rand( ) / 32767 * ao;语句可用来产生 a0 与 a1 中的随机数。四，实验代码/* *此程序为页面调度程序，用于模拟虚存与主存之间的页面置换 *并同时采用FIFO,LRU,OPT,LFT,NUR几种算法 *并比较在不同算法下及不同的主存页面状态下，主存的命中率的高低 * */#include stdlib.h#include stdio.h#include time.h#define TRUE 1#define FALSE 0#define INVALID -1/*页面失效符*/#define null 0#define total_instruction 320 /*指令流长*/#define total_vp 32 /*虚页长*/#define clear_period 50 /*清零周期*/typedef struct /*页面结构*/int pn,pfn,counter,time;pl_type;/*-pn为页面队列号,pfn为页面控制结构中的页号，counter为访问次数-*/pl_type pltotal_vp; /*页面结构数组;建立虚存页面空间*/* *此程序有两种结构，一种是页面结构，用于页面的实际转换 *即将某一页面的实际参数作改变 *另一种是页面控制结构，用于控制页面的调度 */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 忙页面尾指针*/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();void initialize(int total_pf) /*初始化相关数据;total_pf 用户进程的内存页面数 */ int i; diseffect=0; for (i=0;itotal_vp;i+)/*虚存页面设初值*/ pli.pn=i; pli.pfn=INVALID;/*置页面控制结构中的页号，页面为空*/ pli.counter=0; pli.time=-1; /*页面控制结构中的访问次数为0，时间为-1*/ for (i=1;itotal_pf;i+)/*主存页面设初值*/ pfci-1.next=&pfci; pfci-1.pfn=i-1;/*建立pfci-1和pfci之间的链接*/ 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也没有创建新的队列,而是用于指示主存结构中忙页面的头尾*而且由于是纯算法,所以并没有考虑页面自己消掉的可能性,而纯粹由调度结构控制*因此,当页面满后,只有命中不命中目标,只有当释放页面时,会暂时性地产生一个free页面*/ int i,j; pfc_type *p,*t;initialize(total_pf); /*利用子程序初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/ for (i=0;inext;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-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_head;freepf_head=p;/*空闲页面指向下一个*/ printf(FIFO:%6.4f-,1-(float)diseffect/320);void LRU(int total_pf) /*LRU(Last Recently Used) ALGORITHM */*此处LRU算法并未用到pfc队列 *而是用是否为INVALID来判断该页面是否被载入内存 *若未被载入内存,则被载入,同时在有空闲页面的情况下将freepf_head指向下一个 *若没有空闲页面,则在plpagei.pfn!=INVALID的页中选出时间最小的,将之替换出去 */ int min,minj,i,j,present_time; initialize(total_pf); present_time=0; for (i=0;itotal_instruction;i+) if (plpagei.pfn=INVALID) /*页面失效*/ diseffect+; /*失效次数*/ if (freepf_head=NULL) /*无空闲页面*/ min=32767;/*找出主存中时间最小的页面*/ for(j=0;jplj.time)/在pl中的页面凡是标注有值的均是在主存中的页面！ min=plj.time; minj=j; /*freepf_head=&pfcpfcminj.pfn;*/！错误！minj取值会大于total_pf plminj.pfn=INVALID; plminj.time=-1; plpagei.pfn=pagei;/为了表示命中,换入的页面的pfn值应不为INVALID else/有空闲页面时,首先将新页面填入,然后freepf_head指向下一个 plpagei.pfn=pagei;/标志此页面被载入内存 freepf_head=freepf_head-next;/freepf_head指向下一个 elseplpagei.time=present_time;/*页面有效则将命中的页面的time增大，以确保不被最先置换*/present_time+; printf(LRU:%6.4f-,1-(float)diseffect/320);void NUR(int total_pf) /*NUR最近不经常使用算法 ALGORITHM */ int i,j,dp,cont_flag,old_dp; pfc_type *t; initialize(total_pf); dp=0; for (i=0;itotal_instruction;i+) if (plpagei.pfn=INVALID) /*页面失效*/ diseffect+; /*失效次数*/ if (freepf_head=NULL) /*无空闲页面*/ cont_flag=TRUE; old_dp=dp; while (cont_flag) if(pldp.counter=0&pldp.pfn!=INVALID) cont_flag=FALSE; else dp+; if(dp=total_vp) dp=0; if(dp=old_dp) for(j=0;jnext=NULL; plpagei.pfn=freepf_head-pfn; freepf_head=freepf_head-next; else plpagei.counter=1; if(i%clear_period=0) for(j=0;jtotal_vp;j+) plj.counter=0; printf(NRU:%6.4f,1-(float)diseffect/320);void LFU(int total_pf) /*LFU(Leat Frequently Used) ALGORITHM */ int i,j,min,minpage; pfc_type *t; initialize(total_pf); for (i=0;itotal_instruction;i+) if (plpagei.pfn=INVALID) /*页面失效*/ diseffect+; /*失效次数*/ if (freepf_head=NULL) /*无空闲页面*/ min=32767; for(j=0;jplj.counter&plj.pfn!=INVALID) min=plj.counter; minpage=j; plj.counter=0; freepf_head=&pfcpfcminpage.pfn; plminpage.pfn=INVALID; freepf_head-next=NULL; plpagei.pfn=freepf_head-pfn; freepf_head=freepf_head-next; else plpagei.counter+; printf(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;itotal_instruction;i+) if (plpagei.pfn=INVALID) /*页面失效*/ diseffect+; /*失效次数*/ if (freepf_he