CACHE页面置换算法LRU的C语言实现

通过一道题目学习下cache的LRU算法。c语言实现。

LRU算法是最久未使用替换算法，就是假设刚刚用到的数据，将来用到几率也非常大。每次淘汰cache中最久没有使用的元素。

题目：

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

所以，目标就是要设计一个cache系统（数据结构+接口函数），要求保证最近使用的数据不能被移除出cache，也就是每次添加一个cache项的时候，把最旧的cache项移除出去。假设cache只有4这么大，现在有很多元素1,2,2,4,2,5,3

cache income:1

1

cache income:2

2 1

cache income:1

1 2

cache income:4

4 1 2

cache income:2

2 4 1

cache income:5

5 2 4 1

cache income:3

3 5 2 4

实现：

哈希表+双向链表+LRU（Least Recent Used）算法。

当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部；如果不存在，则新建一个节点，放到链表头部；若缓存满了，则把链表最后一个节点删除即可，即set(key, value)。

在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项，即get(key) 。

为什么要用双向链表作为cache的结构？因为双向链表在删除节点时，复杂度为O（1）。而单项链表在删除节点时，不知道前驱节点情况下，需要遍历链表，也有解决办法，双向链表更加灵活。

为什么要将cache节点同时映射到Hashmap？因为是cache嘛，需要快速访问以便知道是否命中，通过拉链法解决冲突。

所以，cache以双向链表的形式存在（实现LRU，节点越靠前说明越新），同时每个节点又

被映射到了hash表上。

cache

hash table

NULL

所以上面的例子中，元素1它的key是1，value也是1。

#define HASH_TABLE_SIZE 4

#define CACHE_SIZE 4

struct Node //cache node

{

int key;

int value;

Node* pre; //cache的双向链表

Node* next; //

Node* nexthash; //hash表的链，可以解决冲突

};

Node* hashTable[HASH_TABLE_SIZE]; //hash table data strcutrue

int cache_lenth;

Node* cacheHead;

Node* cacheTail;

void cache_init()

{

cacheHead = NULL;

cacheTail = NULL;

cache_lenth = 0;

}

//lookup a key in the hash table

Node* hash_table_lookup(int key)

{

unsigned int pos = key % HASH_TABLE_SIZE; //hash funtion if(hashTable[pos])

{

Node* pHead = hashTable[pos];

while(pHead)

{

if(key == pHead->key)

return pHead;

pHead = pHead->nexthash;

}

}

return NULL;

}

//insert Node into hash table

void hash_table_insert(Node *cur)

{

unsigned int pos = cur->key % HASH_TABLE_SIZE;

Node* pHead = hashTable[pos];

if(NULL == pHead)

{

pHead=cur;

}

else

{

while(pHead->nexthash)

{

pHead = pHead->nexthash;

}

pHead->nexthash=cur;

}

cur->nexthash = NULL;

}

//remove key-value from the hash table

void hash_table_remove(int key)

{

unsigned int pos = key % HASH_TABLE_SIZE;

if(hashTable[pos])

{

Node* pHead = hashTable[pos];

Node* pLast = NULL;

Node* pRemove = NULL;

while(pHead)

{

if(key == pHead->key)

{

pRemove = pHead;

break;

}

pLast = pHead;

pHead = pHead->nexthash;

}

if(pRemove)

{

if(pLast)

pLast->nexthash = pRemove->nexthash;

else

hashTable[pos] = NULL;

}

}

}

void pushFront(Node *cur) //双向链表删除节点,并将节点移动链表头部，O(1) {

if(cache_lenth == 1)

return;

if(cur == cacheHead)

return;

if(cur==cacheTail)

{

cacheTail = cur->pre;

}

cur->pre->next = cur->next; //删除节点

if(cur->next!=NULL)

cur->next->pre = cur->pre;

cur->next = cacheHead; //移到链表头部

cur->pre = NULL;

cacheHead->pre = cur;

cacheHead = cur;

}

int get(key)

{

if(cacheHead==NULL)

return -1;

Node *p=hash_table_lookup(key);

if(NULL==p)//如果在Cache中不存在该key，则返回-1

{

return -1;

}

else

{

pushFront(p); //将节点p置于链表头部

}

return cacheHead->value;

}

void set(int key, int value)

{

if(cacheHead==NULL) //如果链表为空，直接放在链表头部

{

cacheHead = (Node *)malloc(sizeof(Node));

cacheHead->key = key;

cacheHead->value = value;

cacheHead->pre = NULL;

cacheHead->next = NULL;

hash_table_insert(cacheHead);

cacheTail = cacheHead;

cache_lenth++;

}

else //否则，在map中查找

{

Node *p=hash_table_lookup(key);

if(NULL==p)////没有命中

{

if(cache_lenth == CACHE_SIZE) //cache满了

{

Node * p =cacheTail;

hash_table_remove(cacheTail->key);

pushFront(p);

p->value=value;

p->key=key;

hash_table_insert(p);

}

else

{

Node * p = (Node *)malloc(sizeof(Node));

p->key = key;

p->value = value;

p->next = cacheHead;

p->pre = NULL;

cacheHead->pre = p;

cacheHead = p;

hash_table_insert(cacheHead);

cache_lenth++;

}

}

else

{

pushFront(p);

}

}

}

void main()

{

cache_init();

if(-1==get(1)) set(1,1);//没有命中

if(-1==get(2)) set(2,2);

if(-1==get(1)) set(1,1);

if(-1==get(4)) set(4,4);

if(-1==get(2)) set(2,2);

if(-1==get(5)) set(5,5);

if(-1==get(3)) set(3,3);

Node *p=cacheHead;

while(p)

{

printf(“%d ”,p->value);

p=p->next;

}

getchar();

}

页面置换算法模拟程序-附代码

目录 1．问题的提出 (2) 1.1关于页面置换算法模拟程序问题的产生 (2) 1.2任务分析 (2) 2．需求分析 (2) 3．方案设计 (3) 4．总体设计 (4) 4.1程序N-S图 (4) 4.2主要的函数 (4) 4.3主要流程图及代码 (5) 4.3.1 FIFO（先进先出） (5) 4.3.2 LRU（最近最久未使用） (6) 4.3.3 OPT（最佳置换算法） (8) 4.4实现结果 (11) 5．程序测试 (14) 5.1设计测试数据 (14) 5.2测试结果及分析 (15) 摘要 随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要

提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果. 本课程设计是学生学习完《操作系统教程》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。 关键词：编制页面置换算法模拟程序、打印页面、FIFO页面算法、LRU页面置换算法、OPT页面置换算法。

操作系统课程设计-页面置换算法C语言

操作系统课程设计-页面置换算法C语言

5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三、设计要求 1、编写算法，实现页面置换算法FIFO、LRU； 2、针对内存地址引用串，运行页面置换算法进行页面置换； 3、算法所需的各种参数由输入产生（手工输入或者随机数产生）； 4、输出内存驻留的页面集合，页错误次数以及页错误率； 四．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、设计说明 1、采用数组页面的页号 2、FIFO算法，选择在内存中驻留时间最久的页 面予以淘汰； 分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。3、LRU算法，根据页面调入内存后的使用情况 进行决策； 同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。 选择置换算法，先输入所有页面号，为系统分

《操作系统》实验五页面置换算法模拟

实验五. 请求页式存储管理的模拟 [实验内容]: 熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法----最近最久未使用算法（LRU），要求在每次产生置换时显示页面分配状态和缺页率。 [实验要求]： 1、运行给出的实验程序，查看执行情况，进而分析算法的执行过程，在理解FIFO页面置换算法和最近最久未使 用算法（LRU）置换算法后，给出最佳置换算法的模拟程序实现，并集成到参考程序中。 2、执行2个页面置换模拟程序，分析缺页率的情况。最好页框数和访问序列长度可调节，在使用同一组访问序 列数据的情况下，改变页框数并执行2个页面置换模拟程序，查看缺页率的变化。 3、在每次产生置换时要求显示分配状态和缺页率。程序的地址访问序列通过随机数产生，要求具有足够的长度。 最好页框数和访问序列长度可调节。 实验的执行结果如下图所示（左下图为FIFO执行结果，右下图为LRU执行结果）：

程序源代码： #include #include "windows.h" #include #include #include #include #include #include void initialize(); //初始化相关数据结构 void createps(); //随机生成访问序列 void displayinfo(); //显示当前状态及缺页情况 void fifo(); //先进先出算法 int findpage(); //查找页面是否在内存 void lru(); //最近最久未使用算法 int invalidcount = 0; // 缺页次数 int vpoint; //页面访问指针 int pageframe[10]; // 分配的页框 int pagehistory[10]; //记录页框中数据的访问历史 int rpoint; //页面替换指针 int inpflag; //缺页标志，0为不缺页，1为缺页 struct PageInfo //页面信息结构 { int serial[100]; // 模拟的最大访问页面数，实际控制在20以上 int flag; // 标志位，0表示无页面访问数据 int diseffect; // 缺页次数 int total_pf; // 分配的页框数 int total_pn; // 访问页面序列长度 } pf_info; //////////////////////////////////////////////////////////////////////// //初始化相关数据结构 void initialize() { int i,pf; inpflag=0; //缺页标志，0为不缺页，1为缺页 pf_info.diseffect =0; // 缺页次数 pf_info.flag =0; // 标志位，0表示无页面访问数据 printf("\n请输入要分配的页框数："); // 自定义分配的页框数 scanf("%d",&pf); pf_info.total_pf =pf; for(i=0;i<100;i++) // 清空页面序列 { pf_info.serial[i]=-1; }

虚拟存储器管理 页面置换算法模拟实验

淮海工学院计算机工程学院实验报告书 课程名：《操作系统原理A 》 题目：虚拟存储器管理 页面置换算法模拟实验 班级：软件*** 学号：20**1228** 姓名：****

一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内， 此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问 一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前

页面置换算法实验报告

一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、简单时钟(钟表)算法（CLOCK） 命中率＝１－页面失效次数／页地址流(序列)长度 三、实验原理 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。 当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。 当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 四、算法描述 本实验的程序设计基本上按照实验内容进行。即使用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，319]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’ D：顺序执行一条指令，其地址为m’+1

实验四页面置换算法代码

实验四页面置换算法模拟（2）一．题目要求： 设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再 被访问的页面换出。 2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留 时间最久的页面予以淘汰。 3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的： 1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。

三．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。

(流程图)页面置换算法课程设计

操作系统课程设计报告题目：页面置换算法模拟程序 学院名称: 专业班级： 学生姓名： 指导教师： 成绩：

目录 一、设计目的 (3) 二、设计题目 (3) 2.1设计内容 (3) 2.2设计要求 (3) 三、设计过程 (4) 3.1 FIFO（先进先出） (4) 3.2 LRU（最近最久未使用） (5) 3.3 OPT（最佳置换算法） (6) 3.4 随机数发生器 (7) 四、完整代码 (7) 五、运行结果演示 (13) 六、设计心得 (16) 七、参考文献 (16)

操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。 本课程设计是学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。 二、设计题目：页面置换算法模拟程序 2.1设计内容 编制页面置换算法的模拟程序。 2.2设计要求 1).用随机数方法产生页面走向，页面走向长度为L(15<=L<=20),L由控制台输入。 2).根据页面走向，分别采用Optinal、FIFO、LRU算法进行页面置换，统计缺页率。 3).假定可用内存块为m(3<=m<=5)，m由控制台输入，初始时，作业页面都不在内存。 4).要求写出一份详细的设计报告。课程设计报告内容包括：设计目的、设计内容、设计原理、算法实现、流程图、源程序、运行示例及结果分析、心得体会、参考资料等。

操作系统-LRU页面置换算法模拟

广东海洋大学学生实验报告书（学生用表） 实验名称LRI?页而之后算法模拟课程名称操作系统课程号_______________ 学院（系）_______________________ 专业__________________ 班级 ____________________ 学生姓名_______ 学号 _________ 实验地点_________________ 实验日期 ________________ LRU页面置换算法模拟 一.实验目的 （1）掌握页式管理基本原理 （2）掌握LRU页而宜换算法 二.实验内容 （1）按照最近最久未使用页而置换算法（LRU）设计页而置换模拟程序。 （2）对于给左的页面访问序列，输出其访问过程中的页而置换序列，并记录缺页次数。 （3）输出内容参考 三.相关数据结构 （1）页表结构数组 （2）页而访问序列数组：保存进程执行过程中的页而访问序列* （3）寄存器数组：每个物理块对应一个16bit的寄存器。 （4）物理块分配表（bool数组）：标识每个物理块是否已经分配

四.实现流程

（1）主线程：实现页面访问过程中的物理块分配和页而置换（假设每间隔80ms访问一个页面）。 （2）寄存器周期性移位线程：周期性（每隔100ms）将所有寄存器右移一位。 （3）主线程参考流程图： 绅水丿 详细代码： import java.io.BufferedReader； import java.io.InputStreamReader； public class LRU { int blockCount; int seriaCount；

页面置换算法代码实现(完整版)

实验原理： 在内存运行过程中，若其所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将那个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法成为页面置换算法。置换算法的好坏，将直接影响到系统的性能。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会在访问的页面调出。目前存在着许多种置换算法（如FIFO，OPT，LRU），他们都试图更接近理论上的目标。 实验目的： 1．熟悉FIFO，OPT和LRU算法 2．比较三种算法的性能优劣 实验内容： 写出FIFO，OPT和LRU算法的程序代码，并比较它们的算法性能。 实验步骤： 代码如下： #include #define M 4 //物理页数 #define N 20 //需要调入的页数 typedef struct page { int num; int time; }Page; //物理页项，包括调入的页号和时间 Page mm[M]; //4个物理页

int queue1[20],queue2[20],queue3[20]; //记录置换的页int K=0,S=0,T=0; //置换页数组的标识 int pos=0;//记录存在最长时间项 //初始化内存页表项及存储内存情况的空间 void INIT(){ int i; for(i=0;i max){ max=mm[i].time ; pos=i; } } return pos; } //检查最长时间不使用页面 int longesttime(int fold)

存储管理---------常用页面置换算法模拟实验

实验七存储管理---------常用页面置换算法模拟实验 实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 实验内容 设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、最不经常使用算法（LFU） 5、最近未使用算法（NUR） 命中率＝１－页面失效次数／页地址流长度 实验准备 本实验的程序设计基本上按照实验内容进行。即首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，319]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’ D：顺序执行一条指令，其地址为m’+1 E：在后地址[m’+2，319]中随机选取一条指令并执行 F：重复步骤A-E，直到320次指令 （2）将指令序列变换为页地址流 设：页面大小为1K； 用户内存容量4页到32页； 用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0 条-第9 条指令为第0页（对应虚存地址为[0，9]） 第10条-第19条指令为第1页（对应虚存地址为[10，19]） ……………………………… 第310条-第319条指令为第31页（对应虚存地址为[310，319]） 按以上方式，用户指令可组成32页。 实验指导 一、虚拟存储系统 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以

第7次 常用页面置换算法模拟实验

操作系统课程实验报告

断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出（FIFO）法。 2、算法流程图 3、步骤说明 （1）初始化 void init(){//初始化 int i; for (i = 0; i < page_frame_number; i++){ page_table[i].page_id = -1; page_table[i].load_time = -1; page_table[i].last_visit_time = -1; } } （2）选择算法，输入插入页面号。进入判断函数 int judge(){//判断页框是否满，或者页框里面是否已存在页面 int i;

for (i = 0; i < page_frame_number; i++){ if (page_table[i].page_id == -1 || page_table[i].page_id == page_id) return i; } return -2; } 之后根据返回数的不同决定了不同类型 返回-2则说明页框满且页框里面没有存在要插入的页面。 返回-1则说明页框未满 返回其它数则说明页框里存在相同的页面 （3）//当没有空页框，并且页面本身也没有存在，则执行一下代码 qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp);//按照装入时间从小到大排序 page_table[0].page_id = page_id; page_table[0].load_time = counter; page_table[0].last_visit_time = counter; page_interrupt_number++; 将页框号为0的页面置换成最新插入的页面。 int cmp(const void *p, const void *q){//按照装入时间从小到大排序 int c = (*(struct Page_table*)p).load_time - (*(struct Page_table*)q).load_time; if (c > 0) return 1; else return -1; } 排序函数，将页面按装入时间从小到大排序 （4）//如果页面未满，则将页面替换在空页框里 if (page_table[j].page_id == -1){ page_table[j].page_id = page_id; page_table[j].load_time = counter; page_table[j].last_visit_time = counter; page_interrupt_number++; 则将页面替换在页框号最小的空页框里 （5）//如果页面本身存在页框中，则执行一下代码 page_table[j].last_visit_time = counter; 则更新页面的最近访问时间 （6）qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp3);//按照装入时间从小到大排序 print(2); 打印出页表详细信息 printf("页表信息：\n页号页框号装入时间最近访问时间\n"); for (j = 0; j < page_frame_number; j++){ printf("%4d%8d%7d%7d\n", page_table[j].page_id, j, page_table[j].load_time,

页面置换算法作业

页面置换算法的演示 一．实验要求： 设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再 被访问的页面换出。 2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留 时间最久的页面予以淘汰。 3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的： 1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。

(LRU)置换算法-操作系统

实验报告三 ——内存页面置换算法的设计 姓名：田玉祥 班级：计算机科学与技术专业一班 一、实验内容 ·实现最近最久未使用（LRU）置换算法 二、实验目的 ?LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其 一部分调入内存便可运行，还支持请求调页的存储管理方式。 ?本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面 置换算法。 三、实验题目 1. 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页 面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。

?例如: 分配给该进程的页块数为3，一个20位长的页面访问序列为:12560,36536,56042,70435， 则缺页次数和缺页率按下图给出: 假定分配给该进程的页块数为3，页面访问序列长度为20。本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。

程序实现想法： 用一个数组a[n]来存放所有需要访问的页，用一个数组b[3]来存放页表，用数组c[3]来存放页表每一页的权值，就是最近最少使用的度，度越高则使用率越小，用n次循环，每次a[i]进行判断时先判断有没有空格，再判断a[i]是否已经在页表中，此时注意要将权值归1，若都没有这些情况，则用函数int MAX(int a,int b,int c) 找到权值最大的，进行替换，并将其他页的权值加1. 实验代码： //LRU算法，最近最少使用的页替换算法 #include #include using namespace std ; int MAX(int a,int b,int c) //赋值之后的权值中找到权值最大的，返回它的下标也就是最近最少使用的 { int max = a ; if(max

操作系统页面置换算法模拟实验

淮海工学院计算机科学系实验报告书 课程名：《操作系统原理A 》 题目：虚拟存储器管理 页面置换算法模拟实验 班级： 学号： 姓名：

一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内， 此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问 一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前

操作系统常用页面置换算法课程设计

摘要 在lｉnｕｘ中,为了提高内存利用率,提供了内外存进程对换机制,内存空间的分配和回收均以页为单位进行，一个进程只需要将其一部分调入内存便可运行；当操作系统发生缺页中断时，必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。因而引入一种用来选择淘汰哪一页的算法——页面置换算法。页面置换算法是操作系统中虚拟存储管理的一个重要部分。页面置换算法在具有层次结构存储器的计算机中,为用户提供一个比主存储器容量大得多的可随机访问的地。常见的页面置换算法有先来先服务算法(FIFO)，最近最久未使用算法(LＲＵ)和最佳适应算法(OＰT）。 关键字:操作系统；FIFＯ；LＲＵ；OPT；Linux

目录 1 绪论?１ 1．1设计任务 (1) １.2设计思想?1 1.3设计特点?1 1．４基础知识 (2) １．4.1 先进先出置换算法(FIFO)?2 1.4.2最近最久未使用算法（LRU) (3) １.4.３最佳置换算法(OPT) (3) 2 各模块伪代码算法?4 2.1伪代码概念?4 2.２伪代码算法 (4) 2.2.１主函数伪代码算法.............................................. 错误!未定义书签。 ２.２.2延迟时间函数伪代码算法?6 2.2．3 FＩFO算法的伪代码?７ ２.2.4LRU算法的伪代码 (7) 10 2．2.5 OPＴ算法的伪代码? 3 函数调用关系图................................................................................................... １2 3．1函数声明?１2 3.1.１主要算法函数...................................................... 错误!未定义书签。

页面置换算法实验(内含完整代码)

实验二存储管理 一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、简单时钟(钟表)算法（CLOCK） 命中率＝１－页面失效次数／页地址流(序列)长度 三、实验原理简述 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。 当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。 当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 四、算法描述 本实验的程序设计基本上按照实验内容进行。即使用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，319]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令

(完整版)页面置换算法C语言

页面置换算法的演示 一．题目要求： 设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再 被访问的页面换出。 2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留 时间最久的页面予以淘汰。 3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的： 1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。

考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 四．设计思想： 选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：OPT基本思想： 是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。 【特别声明】 若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。 FIFO基本思想： 是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。 LRU基本思想： 是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。 五．流程图： 如下页所示

C++模拟LRU页面置换算法

实验五C++模拟LRU页面置换算法 一、实验目的：用c++模拟LRU页面置换算法 二、实验内容：随机一访问串和驻留集的大小，通过模拟程序显示淘汰的页号并统计命中率。示例： 输入访问串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 驻留集大小：3 算法的实现：由于LRU算法淘汰的是上次使用距离t时刻最远的页，故需记录这个距离。 计数器：可使用计数器，给每一个页帧增设一个计数器。每访问一页，就把对应页帧的计数器清零，其余页帧的计数器加1.因此，计数器值为最大的页即上次访问距当前最远的页。 7 0 1 2 0 3 0 4 2 3 0 3 2 0/7 1/7 2/7 0/2 1/2 2/2 3/2 0/4 1/4 2/4 0/0 1/0 2/0 0/0 1/0 2/0 0/0 1/0 0/0 1/0 2/0 0/3 1/3 0/31/3 0/1 1/1 2/1 0/3 1/3 2/3 0/2 1/2 2/2 3/2 0/2 缺缺缺缺命缺命缺缺缺缺命命 红色表示：每个页帧对应的计数器值 通过模拟程序输出淘汰的页号分别为：7 1 2 3 0 4 命中率为：4/13

四、代码： #include using namespace std; struct node { char data; int time; }; void init(char str[],int n,struct node zhuliuji[],int m) { for(int i = 0;i>str[i]; } } void addtime(struct node zhuliuji[],int m) { for(int i=0;i

虚拟内存页面置换算法实验报告

软件学院 上机实验报告 课程名称：操作系统原理 实验项目：虚拟内存页面置换算法实验室：地狱018 姓名：死神学号： 专业班级：实验时间：2015/12/13

一、实验目的及要求 通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。结合Linux的内层的分析方法查看内存的分配过程及linux kernel的内存管理机制 二、实验性质 设计性 三、实验学时 4学时 四、实验环境 实验环境1.实验环境：C与C++程序设计学习与实验系统 2.知识准备： （1）使用Linux的基本命令； （2）了解Linux vmstat、free、top等命令查看linux系统的内存分配 情况； （3）掌握虚拟内存页面置换算法FIFO等基本算法理论。 五、实验内容及步骤 假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。

步骤 通过已知最小物理块数、页面个数、页面访问序列、及采用置换方式可以得出页面置换的缺页次数和缺页率，及每次缺页时物理块中存储。 1．输入的形式 int PageOrder[MaxNumber];//页面序列 int PageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数 2. 输出的形式 double LackPageRate//缺页率 缺页个数 每次缺页时物理块中存储 程序所能达到的功能 模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。 程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 int PageOrder[MaxNumber];//页面序列 int PageCount[MaxNumber]={0};//计算内存内数据离下一次出现的距离 int PageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数 double LackPageRate=0; bool found=false;