linux环境下几种内存调度算法模拟

课程设计（大作业）报告课程名称：操作系统设计题目：Linux环境下几种内存调度算法模拟院系：信息技术学院班级：09级计算机科学与技术二班设计者：学号：指导教师：设计时间：2011、12、20——2011、12、28昆明学院昆明学院课程设计（大作业）任务书姓名：院（系）：专业：计算机科学与技术学号：任务起止日期：2011年12月20日——12月28日课程设计题目：Linux环境下几种内存调度算法模拟课程设计要求及任务描述：设计内容：1.理解FIFO、LRU、OPT等常见内存调度算法的原理。2.模拟实现其中任意两种调度算法。3.采用这两种调度算法，对同一访问序列进行命中率计算和输出，并比较结果。注：命中率=1-缺页率。实验环境及工具：1．实验环境：Linux2．文本编辑工具：Vi3．编译器：GCC2工作计划及安排：12月20日~12月22日整理FIFO算法和OPT算法的原理。12月23日~12月24日编写算法代码并调试运行。12月25日~12月26日对调试出的结果进行对比分析，得出初步的结果。12月27日~12月28日整理资料，并填写课程设计报告书。指导教师签字年月日3课程设计（大作业）成绩学号：姓名：指导教师：课程设计题目：linux环境下几种内存调度算法模拟完成情况总结：在本次设计中，首先，对于FIFO和OPT两种内存调度算法的原理和实现方式有了更好的了解，还学到了一个新的词汇—命中率=1–缺页率。其次，通过对两种内存调度算法的模拟实现，对比运行结果发现对于同一访问序列，OPT算法的命中率比FIFO算法更高。再次通过在linux中调试和运行程序，对linux中的使用有了更深的记忆，尤其是在linux中实现文件的共享这一功能，实现这一功能就不用每次都在Vi中重复输入代码，减少了工作量。另外在画流程图时，一定要读懂源代码，才能正确的画出。通过本次课程设计，我对以前学过的一些知识有了更深的记忆和理解，特别是对linux中的各种命令的使用更加熟练。指导教师评语：成绩：填表时间：指导教师签名：4课程设计（大作业）报告一、两种算法的原理分析1．FIFO内存调度算法的原理先进先出先出置换算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择内存中驻留时间最久的页面予以淘汰。（1）、在分配内存页面数（AP）大于进程页面数（PP）时,所有进程需要的页面（PP个页面）按提出要求的先后次序放入内存。（2）在分配内存页面数（AP）大于进程页面数（PP）时,当然是按提出请求的次序将最先的AP个页面放入内存。（3）这时有需要处理新的页面，则将原在内存中的AP个页面中最先进入的调出（称为FIFO）然后放入新页面。（4）以后如果有新页面需要调入，按（3）的规则进行。该算法的实现方式为：把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指向最老页面的替换指针。但是该算法是基于CPU按线性顺序访问地址空间的假设上的。算法实现提示如下：要得到“命中率”，必然应该有一个常量total-instruction记录页面总共使用次数；此外，需要一个变量记录总共换入页面的次数（需要换出页面，总是因为没有命中而产生的）diseffect。利用公式1-ninstructiototaldiseffect_*100%可以得到命中率。1）初始化。设置两个数组page[PP]和pagecontrol[AP]分别表示进程页面数和内存分配页面数，并产生一个随机数序列main[total-instruction](当然这个序列有page[]的下标随机构成)，表示待处理的进程页面顺序，diseffect置零。2）看main[]中是否有下一个元素，有，就由main[]中获取该页面下标，并转到3）；没有，就转到7）。3）如果该page页已在内存中，就转到2）；否则转到4），同时未命中的diseffect加1.4）观察pagecontrol是否占满，如果占满需将使用队列（6）中建立的）中最先进入的（就是队列第一单元）pagecontrol单元“清干净”，同时将对应的page[]单元置为“不在内存中”。5）将该page[]与pagecontrol[]建立关系（可以改变pagecontrol[]的标示位，也可以采用指针连接，总之至少要使对应的pagecontrol单元包含两个信息：一个它被使用了，二是那个page[]单元使用的。Page[]单元包含两个信息：对应的pagecontrol单元号、本page[]单元已在内存中）。6）将用到的pagecontrol置入使用队列（这里的队列当然是一种先进先出的数据结构了，而不是泛指），返回2）。7）显示公式1-ninstructiototaldiseffect_*100%完成。算法特点：所使用的内存页面构成一个队列。2．（其他任选一个算法）OPT内存调度算法的原理前提是在分配的内存页面占满的情况下。最佳置换法是一种理想状况下的算法，它要求遍历所有的CPU待处理的进程页面序列（实际上由于待处理的页面有时取决于先前处理的页面，所以，很多情况下不可能得到完整的待处理页面序列。在这个层面上，才说该算法是理想的），在这些页面中，如果有已经在内存中，而CPU不再处理的，就将其换出。当要调入5一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。算法实现提示如下:1）初始化。设置两个数组page[PP]和pagecontrol[AP]分别表示进程页面数和内存分配的页面数，并产生一个随机数序列main[total_instruction](当然这个序列由page[]的下标随机构成)，表示待处理的进程页面顺序，diseffect置零。2）看main[]中是否有下一个元素，有，就从序列main[]中获取一个CPU待处理的页面号；没有，转到6）。3）如果该页面已经在内存中了，就转到2），否则转到4）。4）看是否有空闲的内存页面，如果有就直接返回该页面指针；如果没有，遍历所有未处理的进程页面序列，如果有位于内存中的页面，而CPU以后不再处理的，首先将其换出，返回页面指针；如果没有这样的页面，找寻到CPU最晚处理到的页面，将其换出，返回该内存页面指针。5）将内存页面和待处理的进程页面建立联系，返回2）。6）输出1-total_instruction/diseffcet*100%,结束。二、两种算法的流程图表示1．FIFO算法的流程图6开始判断指令是否执行完计算页号在队列中查找页号判断是否找到插入队列计算命中率结束初始化队列产生指令队列报错执行指令判断是否越界72．（其他任选一个算法）OPT内存调度算法的流程图开始定义用户进程的内存页面数初始化相关页面控制用数据结构申请调入新页面判断有无空闲页面释放忙页面队列中的很长时间未使用或以后都不使用的页面直接调入新页面按OPT方式调入新页面输出结果判断是否还有未读页面结束空闲页面减少一个否是否是三、两种算法的实现代码1．FIFO内存调度算法的代码#defineTRUE1#defineFLASE0#defineINVALID-1#defineNULL0#definetotal_instruction320#definetotal_vp32#defineclear_period50typedefstruct{intpn,pfn,counter,time;}pl_type;pl_typepl[total_vp];8structpfc_struct{intpn,pfn;structpfc_struct*next;};typedefstructpfc_structpfc_type;pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_instruction];intpage[total_instruction],offset[total_instruction];intinitialize(int);intFIFO(int);intmain(){ints,i,j;srand(10*getpid());s=(float)319*rand()/32767/32767/2+1;for(i=0;itotal_instruction;i+=4){if(s0||s319){printf(wheni==%d,Error,s==%d\n,i,s);exit(0);}a[i]=s;a[i+1]=a[i]+1;a[i+2]=(float)a[i]*rand()/32767/32767/2;a[i+3]=a[i+2]+1;s=(float)(318-a[i+2])*rand()/32767/32767/2+a[i+2]+2;if((a[i+2]318)||(s319))printf(a[%d+2],anumberwhichis:%dands==%d\n,i,a[i+2],s);}for(i=0;itotal_instruction;i++){page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i32;i++){printf(----%2dpageframes---\n,i);FIFO(i);}return0;}9intinitialize(total_pf)inttotal_pf;{inti;diseffect=0;for(i=0;itotal_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID;pl[i].counter=0;pl[i].time=-1;}for(i=0;itotal_pf-1;i++){pfc[i].next=&pfc[i+1];pfc[i].pfn=i;}pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0];return0;}intFIFO(total_pf)inttotal_pf;{inti,j;pfc_type*p;initialize(total_pf);busypf_head=busypf_tail=NULL;for(i=0;itotal_instruction;i++){if(pl[page[i]].pfn==INVALID){diseffect+=1;if(freepf_head==NULL){p=busypf_head-next;pl[busypf_head-pn].pfn=INVALID;freepf_head=busypf_head;freepf_head-next=NULL;busypf_head=p;}p=freepf_head-next;10freepf_head-next=NULL;freepf_head-pn=page[i];pl[page[i]].pfn=freepf_head-pfn;if(busypf_tail==NULL)busypf_head=busypf_tail=freepf_head;else{busypf_tail-next=freepf_head;busypf_tail=freepf_head;}freepf_head=p;}}printf(FIFO:%6.4f\n,1-(float)diseffect/320);return0;}2．（其他任选一个算法）OPT内存调度算法的代码#defineTRUE1#defineFLASE0#defineINVALID-1#defineNULL0#definetotal_instruction320#definetotal_vp32#defineclear_period50typedefstruct{intpn,pfn,counter,time;}pl_type;pl_typepl[total_vp];structpfc_struct{intpn,pfn;structpfc_st