《操作系统》课程设计报告

1、河海大学文天学院操作系统课程设计报告专业：计算机科学与技术 班级： 五 班 学号： 姓名： 时间： 2010/12/24 课程设计文档实验一 进程调度一、实验目的通过一个简单的进程调度模拟程序的实现，加深对进程调度算法，进程切换的理解。 二、实验内容采用动态优先数的方法，编写一进程调度程序模拟程序。模拟程序只进行相应的调度模拟操作，不需要实际程序。三、实验流程图 四、算法思想1、创建进程对象，成员属性有：进程名，进程所需运行时间、进程的优先级和状态2、使用arraylist来存放模拟的进程（arraylist是动态数组，不用去考虑容量问题，可以很好的解决不知道数量的进程数，同时可以不使用链表）

2、。3、对创建的进程进行排序，按照优先级的顺序进行相应的排序。排序成功后进行模拟进程的运行，每运行一次进程，将该进程的优先级减少一个单位，运行时间减一个单位，依次循环，直至所有的进程的运行完成，运行时间变为0。注意：优先级和运行所需要的时间变为0时就不可以再减！五、算法实现#include #include #include #include /定义pcb结构体typedef struct pcb char name4; /进程名 int runtime; /进程要求运行时间 int priority; /进程优先数 char state; /进程状态r代表就绪，e代表结束 struct pcb

3、 *next;*pronode,pro;typedef struct pronode front; pronode rear; plinkqueue;/初始化进程队列void initpqueue(plinkqueue *q) int i; pronode p,q; system(cls); q-rear=q-front=null; /构造一个空队列 /构造进程队列 printf(n请输入5个进程名、运行时间和优先数：n); for(i=1;iname); printf(n运行时间:); scanf(%d,&p-runtime); printf(n优先数:); scanf(%d,&p-prio

4、rity); p-state=r; if(q-front=null) /队列为空 q-front=q-rear=p; p-next=null; else if(p-priorityq-front-priority) /队列非空，新进程优先数最大，插入队首 p-next=q-front; q-front=p; else q=q-front; while(q-next) if(q-priority=p-priority)&(q-next-prioritypriority) p-next=q-next; /插入 q-next=p; break; q=q-next; if(!q-next) q-rea

5、r-next=p; q-rear=p; p-next=null; /当前待插如进程优先数最小，插入进程尾 /initpqueue(plinkqueue *q)/程序实现void dequeue(plinkqueue *q) /队首进程运行完成后退出队列并释放节点 pronode p; p=q-front; q-front=p-next; free(p);/dequeue(plinkqueue *q)/*队首的进程占用cpu,运行一个固定时间段后调整队列，要求runtime=0的进程时退出队列，否则按优先数从大到小的顺序插入至后续ready进程队列中*/ void run(plinkqueue

6、*q) pronode p,temp;int t=0;while(q-front) /进程运行至队列空 printf(nn-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-n); printf(时刻%d到%d,t,t+1); p=q-front; printf(进程%s正在运行n,p-name); getchar(); p=q-front; p-runtime-; p-priority-; t+;temp=q-front; if(p-runtime=0)printf(n进程%s已经运行完毕，退出队列,p-name); p-

7、state=e; getchar(); dequeue(q); if(q-front=null) printf(所有进程已经运行完毕!); getchar(); return; else /使队列保持优先数递减次序,并打印就绪队列情况 while(temp-next) if(temp-priority=p-priority)&(temp-next-prioritypriority) q-front=q-front-next; p-next=temp-next; temp-next=p; /插入到两进程间 break; temp=temp-next; if(!temp-next) q-front

8、=q-front-next; p-next=null; temp-next=p; q-rear=p; /插入队列尾 temp=q-front; printf(n时刻%d进程运行情况:n,t); /队列中进程运行状态打印 printf(n进程名t要求运行时间tt优先数tt状态n); do printf(%stt%dtt,temp-name,temp-runtime); printf(%d,temp-priority); printf(tt%cn,temp-state); temp=temp-next;while(temp!=null); getchar();/run(plinkqueue *q)

9、void main() plinkqueue pqueue; printf(/-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-n); printf(* *n); printf(* 动态优先数进程调度 *n); printf(* *n); printf(-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-/n); getchar(); initpqueue(&pqueue); printf(优先数进程调度过程如下:n); run(&pqueue);六、总

10、结 这个实验主要是为了实验进程管理中的进程调度，运用的算法和整个的调度思想都是比较简单的，但是却体现了进程调度的重要性，操作系统的四大特征都是基于进程而形成的，所以我们可以从进程的角度来研究操作系统，进程调度是操作系统中一个极其重要的组成部分，进程调度算法就是为了实现进程调度，在进程调度算法中引入了最高优先权调度算法，一般经常用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可以用于实时系统中。按照优先级的顺序进行排序是该实验的重要部分，排好了序列了才能进行其他操作，该实验加深了我们对进程调度算法和进程切换的学习，加深了对进程调度算法的熟悉和操作实验二 存储管理一、实验

11、目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计 , 了解虚拟存储技术的特点 , 掌握请求页式存储管理的页面置换算法。二、实验内容虚拟存储器的工作原理以及虚拟页式存储管理中的页面置换算法三、算法思想1、使用随机数产生的函数，产生320个随机数，要求随机数的大小在1100之间，在 0,319 的指令地址之间随机选取一起点 m;顺序执行一条指令;在前地址0,m+1中随机选取一条指令并执行 , 该指令的地址为 m; 顺序执行一条指令 , 其地址为 m+1;在后地址 m+2,319 中随机选取一条指令并执行

12、;重复上述步骤, 直到执行 320 次指令。2、采用先进先出的算法 (fifo)；3、最近最久未使用算法 (lru);四、算法实现/ test_1.cpp : 定义控制台应用程序的入口点。/* *此程序为页面调度程序，用于模拟虚存与主存之间的页面置换 *并同时采用fifo,lru,opt,lft,nur几种算法 *并比较在不同算法下及不同的主存页面状态下，主存的命中率的高低 * */#include stdlib.h#include stdio.h#include time.h#define true 1#define false 0#define invalid -1/*页面失效符*/#de

13、fine 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; /*页面结构数组;建立虚存页面空间*/* *此程序有两种结构，一种是页面结构，用于页面的实际转换 *即将某一页面的实际参数作改变 *另一种是页面控制结

14、构，用于控制页面的调度 */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,*bus

15、ypf_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 用户进程的内

16、存页面数 */ 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=tot

17、al_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,

18、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;/*忙页面头指向下一个*/

19、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

20、=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的页中选出时间最小的

21、,将之替换出去 */ 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

22、_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增大，以确保

23、不被最先置换*/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) /*无空闲

24、页面*/ 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.

25、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;

26、 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 to

27、tal_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_head=null) /*无空闲页面*/ for(j=0;jtotal_vp;j+)if(plj.pfn!=invalid)dis

28、tj=32767;/将所有主存内的页面的disk标志为最大值 else distj=0;/不在主存内的则其disk标志为0 plj.counter=0; d=1; for (j=i+1;jtotal_instruction;j+)/找出余下指令所在页面以后会被访问到的次数 if (plpagej.pfn!=invalid)/前提是这些页面现在已在主存中 distpagej=d;/不是j,而是pagej d+; max=-1; for (j=0;jtotal_vp;j+) /找出在主存中哪个页面在以后的被访问到的次数最小 if(maxnext=null; plmaxpage.pfn=invalid; plpagei.pfn=pagei;/将当前页面调入内存中去,即将其pfn值标注为非invalid else/有空闲页面时,将当前页面调入,并将freepf_head指向下一个 plpagei.pfn=freepf_head-pfn;freepf_head=freepf_head-next;