北邮操作系统第二次实验

1、文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.北京邮电大学操作系统实验实验报告班号： 14姓名：oneseven学号：实验日期 ：实验名称 ：操作系统实验一、实验目的通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。 掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验内容1.实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。实验准备用随机函数仿真进程进行内存申请， 并且以较为随机的次序进行释放。 对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满

2、足。2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1) 最佳置换算法（ Optimal ）2) 先进先出法（ Fisrt In First Out ）3) 最近最久未使用（ Least Recently Used ）4) 最不经常使用法（ Least Frequently Used ）其中，命中率页面失效次数页地址流长度。试对上述算法的性能加以较各： 页面个数和命中率间的关系； 同样情况下的命中率比较。实验准备本实验中主要的流程：首先用 srand( ) 和 rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。实验可

3、先从一个具体的例子出发。(1)通过随机数产生一个指令序列，共2048 条指令。指令的地址按下述原则生成：A ： 50%的指令是顺序执行的B： 25%的指令是均匀分布在前地址部分C： 25%的指令是均匀分布在后地址部分具体的实施方法是：A ：在 0， 1023的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1 的指令C：在前地址 0,m+1 中随机选取一条指令并执行，该指令的地址为mD：顺序执行一条指令，其地址为m +1E：在后地址 m +2， 2047中随机选取一条指令并执行F：重复步骤A -E，直到 2048 次指令(2)将指令序列变换为页地址流设：页面大小为4K ；用户

4、内存容量4页到 32 页；用户虚存容量为32K 。在用户虚存中，按每K 存放 64 条指令排列虚存地址，即2048 条指令在虚存中的存放方式为：第 0 条 -第 63 条指令为第0 页（对应虚存地址为0， 63 ）第 64 条 -第 127 条指令为第1 页（对应虚存地址为64， 127）第 1984 条 -第 2047 条指令为第31 页（对应虚存地址为1984 ， 2047）按以上方式，用户指令可组成32 页。1文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.以此为基础，给出较为一般的情形：仿真内存容量和虚存容量参数变化时的情形。3. 实现内存的slab 分配器：其基本

5、思想是：一次向内核获取整数页，slab 根据数据结构的大小进行划分为一个个小的数据结构， 当需要时直接从该链表上摘取一个返回应用程序，当应用程序释放时，而非真正释放，只需要该空间放回到链表中，当分散的一页多块又聚集一页时，又会拼成一页，同时判断 slab 空闲的页数，如果空闲页超过一定的页数，就会向系统释放一定的页数。一个 slab 分配器只能管理一个指定大小的数据结构分配。三、项目要求及分析3.1 实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。假设系统的可利用内存空间容量为 2m 个字 (地址从 0 到 2m-1)，则在开始运行时， 整个内存区是一个大小为 2m 的空闲块

6、，在运行了一段时间之后，被分隔成若干占用块和空闲块。为了在分配时查找方便起见，我们将所有大小相同的空闲块建于一张子表中。每个子表是一个双重链表，这样的链表可能有 m+1 个，将这 m+1 个表头指针用向量结构组织成一个表，这就是伙伴系统中的可利用空间表，如图所示：分配算法：当用户提出大小为 n 的内存请求时，首先在可利用表上寻找结点大小与表，若此子表非空， 则将子表中任意一个结点分配之即可；若此子表为空，的非空子表中去查找， 直至找到一个空闲块， 则将其中一部分分配给用户，入相应的子表中。n 相匹配的子则需从结点更大而将剩余部分插若 2k-1 < n k2-1，又第 k+1 个子表不空，

7、则只要删除此链表中第一个结点并分配给用户即可； 若 2k- 2k- 12k-1的子表为空， 则需从结点大小为2k的< n 2-1，此时由于结点大小为子表中取出一块，将其中一半分配给用户，剩余的一半作为一个新结点插入在结点大小为k-1的子表中，若2k-i -1k -ik的子表均为空，2< n 2-1(i 为小于是的整数 )，并且所有结点小于 2则同样需从结点大小为2k 的子表中取出一块， 将其中2k-i 的一小部分分配给用户， 剩余部分分割成若干个结点分别插入在结点大小为2k-1 、 2k-2、 、 2k-i 的子表中。回收算法：在用户释放不再使用的占用块时，系统需将这新的空闲块插入

8、到可利用空间表中去。这里，同样有一个地址相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑互为“伙伴 ”的两个空闲块的归并。何谓 “伙伴 ”?如前所述，在分配时经常需要将一个大的空闲块分裂成两个大小相等的存储区，这两个由同一大块分裂出来的小块就称之“互为伙伴 ”。例如：假设 p 为大小为 pow(2,k)的空闲块的初始地址，且p MOD pow(2,k+1)=0，则初始地址为 p 和 p+pow(2,k) 的两个空闲块互为伙伴。在伙伴系统中回收空闲块时， 只当其伙伴为空闲块时才归并成大块。也就是说，若有两个空闲块， 即使大小相同且地址相邻， 但不是由同一大块分裂出来的，也不归并在一起。由此，

9、在回收空闲块时，应首先判别其伙伴是否为空闲块，若否，则只要将释放的空闲块简单插入在相应子表中即可；若是，则需在相应子表中找到其伙伴并删除之，然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中去。3. 2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去， 就要按某种策略来废弃某个页面， 将其所占据的物理页释放出来，供新页面使用。2文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.页面替换算

10、法主要用于如下几个地方：(1) 虚拟存储器中，主存页面（或程序段）的替换。(2) Cache 中的块替换。(3) 虚拟存储器的快慢表中，快表的替换。(4) 虚拟存储器中，用户基地址寄存器的替换。在虚拟存储器中常用的页面替换算法有如下几种：(1) 最优替换算法，即OPT 算法（ OPTimal replacement algorithm ）。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然，这种假设不总是正确的。 最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换

11、算法的命中率一定是最高的，它就是最优替换算法。要实现 OPT 算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT 算法只是一种理想化的算法，然而，它也是一种很有用的算法。实际上， 经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下，哪一种页面替换算法的命中率与 OPT 算法最接近，那么，它就是一种比较好的页面替换算法。(2) 先进先出算法，即 FIFO 算法（ First -In First -Out algorithm ）。这种算法选择最先调入主存储器的页面作为被替换的页面。

12、 它的优点是比较容易实现， 能够利用主存储器中页面调度情况的历史信息， 但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用的页面。(3) 最久没有使用算法，即 LRU 算法（ Least Recently Used algorithm ）。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的" 多 "与 "少 "简化成判断 " 有 "与 " 无 "，因此，实现起来比较容易。(4) 近期最少使用算法，即 LFU 算法（ Least Frequently Used

13、algorithm ）。这种算法选择近期最少访问的页面作为被替换的页面。 显然，这是一种非常合理的算法， 因为到目前为止最少使用的页面， 很可能也是将来最少访问的页面。 该算法既充分利用了主存中页面调度情况的历史信息， 又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时， 要从所有计数器中找出一个计数值最大的计数器。因此， 通常采用如下一种相对比较简单的方法。3.3 实现内存的 slab 分配器slab 描述符和空闲对象管理部分成为 slab 的管理部分，也可以称为slab 头slab

14、的头可以放在 slab 自身，也可以放在slab 之外。如果slab 头放在了 slab之外，那么用户申请 obj 时，需要首先访问slab 头， slab 头提供未使用free obj 的指针然后再访问这个 free obj 的地址。完成这项工作需要访问 2 个页块。 会带来效率上的损失。slab 头始终位于 slab也存在问题， 比如一个页面只有4K ，objsize = 2K ，那么 slab 头在 slab上，就意味着，这个4K 的页面只能够 分配一个 obj。造成了内存的浪费。如果 页数太少，存放的 obj个数少，那么增加管理开销，同时内存使用率低，如果页数太多对伙伴内存系统不好，所

15、以需要一定的策略妥协。这个妥协过程是有calculate_slab_order这个函数来实现的。从 0 阶（即一页） 到 kmalloc 的最高阶 KMALLOC_MAX_ORDER，挨个尝试，由 cache_estimate这个函数计算如果选用order阶，那么能分配多少个obj （ num），剩余空间是多少（ remainder ）。所谓剩余空间，就是除去 slab 头（如果有的话） ，除去 obj*num ，剩下的边角料空间是多少。 需要分成两种情况去计算，分成两种情况的原因，很快就能看到3文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.A) slab头不在 slab

16、 上，即 flag &CFLGS_OFF_SLAB = 1的时候这种情况比较简单，由于管理数据完全不在slab上，size_t slab_size = PAGE_SIZE << gfporder;nr_objs = slab_size / buffer_size;B)slab 头在 slab上，这种情况稍复杂， 原因是 slab头里面有个除了固定大小的slab描述符， 还有个空闲对象管理数组，这个数组的大小取决于obj 的个数。但 obj 的个数又取决于 slab头大小。换句话， slab 头的大小取决于obj 的个数， obj的个数取决于slab头的大小，四、具体实现4.

17、1 实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。程序：#include <stdio.h>#include <stdlib.h>#include <time.h>#define MIN_MOMORY_SIZE 2/ 随机产生的最小内存空间#define WORKTIME 1500/系统工作时间#define MAX_REQ_SIZE 6/申请空闲内存分配的最大容量：256M#define MIN_DUE 30/ 使用内存块的最短时间#define MAX_DUE 90/使用内存块的最长时间#define OCCUPY_INTERV AL

18、 60/ 每次分配的最大间隔#define USED 1/内存块被使用#define UNUSED 0/ 内存块未被使用/内存块链表结点结构typedef struct buddy_node int flag;/标记空间是否被使用int base;/ 本块儿内存的基地址int occupy;/ 实际使用空间大小int fragment;/碎片大小int duetime;/使用时间struct buddy_node *nextPtr;/指向下一个结点 Buddy, *BuddyPtr;IndexTable tableINDEX_SIZE;/使用哈希表管理伙伴系统int ready = 0;/ 需

19、要分配内存的时刻int availSpace;/ 可分配空间大小int totalFragment = 0;/总碎片大小/函数：添加结点（形参为内存块结点的信息）void insert_node (int i, int inbase, int f, int occ, int frag, int d)BuddyPtr newnodePtr = NULL, prePtr = NULL, curPtr = NULL; newnodePtr = (BuddyPtr) malloc (sizeof (Buddy);/ 分配结点 newnodePtr->base = inbase;newnodePt

20、r->flag = f;newnodePtr->occupy = occ;4文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.newnodePtr->fragment = frag;newnodePtr->duetime = d;newnodePtr->nextPtr = NULL;if (tablei.headPtr = NULL)tablei.headPtr = newnodePtr;else curPtr = tablei.headPtr;prePtr = NULL;/ 按地址顺序插入内存块while (curPtr &&

21、curPtr->base < inbase) prePtr = curPtr;curPtr = curPtr ->nextPtr;if (prePtr = NULL) /插在最前newnodePtr->nextPtr = curPtr;tablei.headPtr = newnodePtr;else if (curPtr = NULL) / 插在最后prePtr->nextPtr = newnodePtr;else / 插在中间prePtr->nextPtr = newnodePtr;newnodePtr->nextPtr = curPtr;/函数：删

22、除结点int delete_node (int i, BuddyPtr delPtr)BuddyPtr prePtr = NULL, curPtr = NULL;int basehold = delPtr ->base;curPtr = tablei.headPtr;while (curPtr != delPtr) /寻找要删除的结点的位置prePtr = curPtr;curPtr = curPtr ->nextPtr;if (prePtr = NULL)/要删除的结点在最前tablei.headPtr = curPtr ->nextPtr;else/ 要删除的结点不在链表

23、的最前prePtr->nextPtr = curPtr ->nextPtr;free (curPtr);/释放结点return basehold;/ 返回删除的内存块结点的基地址/函数：伙伴系统的分配算法5文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.void buddy_allocate (int time_slice)int i, j, size, due;int state = 0; /分配状态： 0 为未分配， 1 为已分配 int inbase, basehold;BuddyPtr curPtr = NULL;if (ready = time_sli

24、ce) /到达分配内存的时刻printf ("Time %d:", time_slice);size = 1 + rand () % MAX_REQ_SIZE;/ 申请使用内存的大小due = MIN_DUE + rand ()%(MAX_DUE- MIN_DUE);/申请使用内存的时间if (availSpace > size) / 在可分配空间大于申请空间时分配/依次寻找可分配的内存块for (i = 0; (i < INDEX_SIZE) && (state = 0); i +) /找到一个不小于申请大小的块索引if (tablei.nod

25、esize >= size && tablei.headPtr) curPtr = tablei.headPtr;/遍历相应的循环链表中while (curPtr && (state = 0) / 找到空闲块if (curPtr - >flag = UNUSED) /空闲块的大小小于申请大小的2 倍，分配if (tablei.nodesize / size = 1) / 在分配的内存块上设置信息curPtr ->flag = USED;curPtr ->occupy = size;curPtr ->fragment = tablei

26、.nodesize- size;curPtr ->duetime = due + ready;/ 修改可系统分配空间和碎片大小availSpace - = tablei.nodesize;totalFragment += curPtr ->fragment;state = 1;/ 标记已分配break;/空闲块的大小刚大于申请大小的2 倍else basehold = delete_node (i, curPtr);/ 删除较大的空闲块并保留其基地址inbase = basehold + tablei.nodesize;j = i;/ 分割空闲块do j -;inbase -= t

27、ablej.nodesize;/ 设置要添加内存块结点的基地址6文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.insert_node (j, inbase, UNUSED, 0, 0, 0);/添加较小的空闲块printf ("A block cut takes placen"); while (tablej.nodesize / size > 1); / 分配insert_node(j,basehold,USED,size,tablej.nodesize - size, due + ready);/ 修改可系统分配空间和碎片大小availSpa

28、ce - = tablej.nodesize;totalFragment += tablej.nodesize- size;state = 1;/ 标记已分配/ 块被占用，查看下一结点elsecurPtr = curPtr ->nextPtr;printf("Allocated%d,Fragment%d,Due%dn",size,totalFragment,ready+due);else if (availSpace < size) && (availSpace + totalFragment) >= size)printf ("

29、Allocation failed because of fragment!n");elseprintf ("Allocation failed because of no enough unused space!n");ready += (1 + rand() % OCCUPY_INTERVAL);/下次需要分配内存的时刻/函数：伙伴系统的回收算法void buddy_retrieve (int time_slice)int i, basehold, dif;int f = 0;int Modnext=0;BuddyPtr curPtr = NULL, tode

30、lPtr = NULL;/依次查找，并回收需要回收的块for (i = 0; i < INDEX_SIZE; i +) if (tablei.headPtr) curPtr = tablei.headPtr;while (curPtr) if (curPtr ->flag = USED) && (curPtr->duetime = time_slice) /需要回收/修改可系统分配空间和碎片大小7文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.availSpace += tablei.nodesize;totalFragment -= cu

31、rPtr ->fragment;/回收为空闲块curPtr->flag = UNUSED;curPtr->occupy = 0;curPtr->fragment = 0;curPtr->duetime = 0;printf ("Time %d:Retrieve %d,Fragment %dn", time_slice, tablei.nodesize, totalFragment);curPtr = curPtr ->nextPtr;/合并空闲块for (i = 0; i < INDEX_SIZE; i +) if (tablei.

32、headPtr) curPtr = tablei.headPtr;while (curPtr && curPtr->nextPtr) /将地址连续且都为空闲的块合并后加入下一级的链表中if (curPtr ->flag = UNUSED && (curPtr->nextPtr) ->flag = UNUSED)dif = (curPtr ->nextPtr) - >base - curPtr->base;Modnext = (int)(curPtr ->nextPtr ->base)%(2*tablei.no

33、desize); if (dif = tablei.nodesize)&&(Modnext=0) / 删除两个结点todelPtr = curPtr;curPtr = curPtr ->nextPtr;basehold = delete_node (i, todelPtr);todelPtr = curPtr;curPtr = curPtr ->nextPtr;delete_node (i, todelPtr);insert_node (i+1, basehold, UNUSED, 0, 0, 0);/添加合并后的结点printf ("Two blocks

34、 mergen");elsecurPtr = curPtr ->nextPtr;elsecurPtr = curPtr ->nextPtr;8文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持./函数：伙伴系统的处理过程void buddy_system (void)int time_slice = 0;/在每个时间片内使用分配算法和回收算法for (; time_slice < WORKTIME; time_slice +) buddy_allocate (time_slice);/分配算法buddy_retrieve (time_slice);/

35、 回收算法int main(int argc, char *argv)int memory_size;ini_index ();/ 初始化哈希索引表srand (time (NULL);/ 设置随机数种子/随机产生需要管理的内存大小：512M 1Gmemory_size = MIN_MOMORY_SIZE + rand() % MIN_MOMORY_SIZE; printf ("The size of memory is:%dn", memory_size);int_system (memory_size);/ 初始化伙伴系统buddy_system ();/伙伴系统的处理

36、过程printf ("Time %d:System execution stops and the spaces are all freed.n", WORKTIME);free_system ();/ 释放所有结点system("pause");return 0;42.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。程序：#include<stdio.h>#include<stdlib.h>#include<unistd.h>#define TRUE 1#define FALSE 0#define IN

37、V ALID -1#define NUL 0#define total_instruction 320/指令流长#define total_vp 32/ 虚页长#define clear_period 50/ 清零周期typedef structint pn;/页号int pfn;/ 面号int counter;/ 一个周期内访问该页面的次数9文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.int time;/ time 为访问时间pl_type;pl_type pltotal_vp;/ 页面结构数组struct pfc_struct/页面控制结构int pn,pfn;st

38、ruct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail; int diseffect,atotal_instruction;int pagetotal_instruction,offsettotal_instruction;/*Name: void Lprintf(void)Achieve:格式控制*/void Lprintf(void)int i,j;printf("|");for(i = 1;i

39、<=6;i+)for(j = 1;j<=9;j+)printf(" -");if(i!=6)printf("+");printf("|n");/*Name:voidinitialize(int total_pf)Achieve: 初始化相关数据结构*/voidinitialize(int total_pf)int i;diseffect=0;for(i=0;i<total_vp;i+)pli.pn=i;pli.pfn=INVALID;/置页面控制结构中的页号，页面为空pli.counter=0;pli.time=-1

40、; / 页面控制结构中的访问次数为0，时间为 -1for(i=1;i<total_pf;i+)pfci -1 .next=&pfci;pfci-1.pfn=i -1;/ 建立 pfci -1 和 pfci 之间的连接10文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.pfctotal_pf -1.next=NUL;pfctotal_pf-1.pfn=total_pf -1;freepf_head=&pfc0;/ 页面队列的头指针为pfc0/*Name:void FIFO(int total_pf)Achieve: 先进先出法（ Fisrt In Fir

41、st Out ）*/void FIFO(int total_pf)int i,j;pfc_type *p;/ 中间变量initialize(total_pf); / 初始化相关页面控制用数据结构busypf_head=busypf_tail=NULL; /忙页面队列头，队列尾链接for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID)/页面失效diseffect+=1;/ 失效次数if(freepf_head=NULL)/无空闲页面p=busypf_head->next;plbusypf_head ->pn.pfn=INV

42、ALID;freepf_head=busypf_head;/ 释放忙页面队列的第一个页面freepf_head->next=NULL;/ 表明还是缺页 */busypf_head=p;p=freepf_head ->next;freepf_head->pn=pagei;plpagei.pfn=freepf_head ->pfn;freepf_head->next=NULL; / 使 busy 的尾为 nullif(busypf_tail=NULL)busypf_tail=busypf_head=freepf_head;elsebusypf_tail ->ne

43、xt=freepf_head;busypf_tail=freepf_head;freepf_head=p;printf("%6.3f",1 -(float)diseffect/320);11文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持./*Name:void LRU (int total_pf)Achieve:最近最久未使用（Least Recently Used ）*/void LRU (int total_pf)int min,minj,i,j,present_time; /minj为最小值下标initialize(total_pf);presen

44、t_time=0;for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID)/ 页面失效diseffect+;if(freepf_head=NULL)/无空闲页面min=32767;/ 设置最大值for(j=0;j<total_vp;j+) /找出 time 的最小值if(min>plj.time&&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn;/ 空出一个单元plminj.pfn=INVALID;plminj.time=

45、0;freepf_head->next=NULL;plpagei.pfn=freepf_head ->pfn; / 有空闲页面 ,改为有效plpagei.time=present_time;freepf_head=freepf_head ->next; / 减少一个free 页面elseplpagei.time=present_time;/ 命中则增加该单元的访问次数 present_time+;printf("%6.3f",1 -(float)diseffect/320);/*12文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.Nam

46、e:void OPT(int total_pf)Achieve: 最佳置换算法（Optimal ）*/void OPT(int total_pf)int i,j, max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID)/* 页面失效 */diseffect+;if(freepf_head=NULL)/* 无空闲页面 */for(j=0;j<total_vp;j+)if(plj.pfn!=INVALID)dist

47、j=32767;elsedistj=0;for(j=0;j<total_vp;j+)if(plj.pfn!=INVALID)&&(distj=32767)distj=j;max=0;for(j=0;j<total_vp;j+)if(max<distj)max=distj;maxpage=j;freepf_head=&pfcplmaxpage.pfn;freepf_head- >next=NULL;plmaxpage.pfn=INV ALID;plpagei.pfn=freepf_head ->pfn;freepf_head=freepf_h

48、ead ->next;13文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.printf("%6.3f",1 -(float)diseffect/320);/*Name: vodi LFU(int total_pf)Achieve: 最不经常使用法（Least Frequently Used ）*/void LFU(int total_pf)int i,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID)/ 页面失效diseffect+;if(freepf_head=NULL)/无空闲页面min=32767