页面置换算法课程设计（一个程序的页面走向，FIFO和LRU页面置换算法）

本文目录

• 一个程序的页面走向，FIFO和LRU页面置换算法
• 最佳页面置换算法的算法描述
• c语言编写页面置换算法
• 页面置换算法之LRU算法
• 操作系统课程设计，用C#实现内存页面的置换实现算法间比较
• 页面置换算法
• 页面置换算法的实验

一个程序的页面走向，FIFO和LRU页面置换算法

#include"stdio.h"
#include"stdlib.h"
#include"time.h"
void FIFO(void);
void LRU(void);
char a;
int m=4,n=12,i,y={1,2,3,4,1,2,5,1,2,3,4,5}; /*m为物理块数，n为要访问的页面数*/
typedef struct page{
int num;
int time;
}Page;
Page x;
int GetMax(page *x) /*求出那个物理块中的页面呆的时间最长，返回物理块号*/
{
int i;
int max=-1;
int tag=0;
for(i=0;i《m;i++)
{
if(x.time》max)
{ max=x.time;
tag=i;
}
}
return tag;
}
void Xunhuan()
{
printf("Please select 1:FIFO算法\n 2:LRU算法\n");
scanf("%s",&a);
printf("物理块数：4\n");
//scanf("%d",&m);
for(i=0;i《m;i++) /*将空的物理块中数据置为-1*/
{
x.num=-1;
}
printf("所要访问的页面数：12\n");
//scanf("%d",&n);
//srand(time(NULL));
printf("所要访问的页面号序列为：");
for(i=0;i《n;i++)
printf("%d ",y);
printf("\n");
printf("页面置换步骤如下：\n");
switch(a)
{
case ’1’:FIFO();break;
case ’2’:LRU(); break;
}
}
void main()
{
char a;
Xunhuan();
while(1)
{
printf("Continue or Exit:C/Anykey:\n");
scanf("%s",&a);
if(a==’c’||a==’C’)
Xunhuan();
else break;
}
exit(0);
}
void FIFO(void)
{
int i,j,u;
for(i=0;i《m;i++)
x.time=0;
x;
x.time=1;
printf(" %d \n",x.num);
for(i=1;i《n;i++)
{ u=0;
for(j=0;j《m;j++)
if(x)
{
u=1;
break;
}
if(u!=1&&x.num!=-1)
{
j=GetMax(x);
x;
x.time=0;
}
if(u!=1&&x.num==-1)
{
for(j=0;j《m;j++)
{
if(x.num==-1)
{x;
break;}
}
}
for(j=0;j《m;j++)
if(x.num!=-1)
x.time++;

for(j=0;j《m;j++)
if(x.num==-1)
printf("%2c ",32);
else
printf("%2d ",x.num);
printf("\n");
}
}
void LRU()
{
int i,j,u;
for(i=0;i《m;i++)
x.time=0;
x;
x.time=1;
printf(" %d \n",x.num);
for(i=1;i《n;i++)
{ u=0;
for(j=0;j《m;j++)
if(x) /*物理块中存在相同页面*/
{
x.time=0; /*将相同的物理块的time置为0*/
u=1;
break;
}
if(u!=1&&x.num!=-1) /*物理块中无相同页面且物理块已填满*/
{
j=GetMax(x);
x;
x.time=0; /*将刚替换的页面所在的物理块time置为0*/
}
if(u!=1&&x.num==-1) /*物理块中无相同页面且物理块未填满*/
{
for(j=0;j《m;j++)
{
if(x.num==-1)
{x;
break;}
}
}
for(j=0;j《m;j++)
if(x.num!=-1)
x.time++; /*每执行完一次time加1*/

for(j=0;j《m;j++)
if(x.num==-1)
printf("%2c ",32);
else
printf("%2d ",x.num);
printf("\n"); /*格式化输出*/
}
}

最佳页面置换算法的算法描述

当产生缺页中断时，利用相应的淘汰页面的算法选择需要淘汰的页面。
页面置换算法在淘汰页面时的算法：
输入：页面号引用串P1,P2...Pn；
输出：淘汰页面Pt
实现：
1、如果页框中的某个页面P以后永不使用，则该页面为淘汰页面Pt。
2、如果每个P都会再次被访问，那么其中最长未来时间内不再被访问的页面为淘汰页面Pt。

c语言编写页面置换算法

用C语言编写OPT、FIFO、LRU，LFU四种置换算法。熟悉内存分页管理策略。了解页面置换的算法。掌握一般常用的调度算法。根据方案使算法得以模拟实现。锻炼知识的运用能力和实践能力。

可以先写一个结构体，包括编号和使用次数2个内容。然后动态生成一个数组，数组元素就是结构体。然后另外写2个函数。一个计算中断次数一个进行页面置换。在检测是否中断的时候，可以循环遍历上面动态生成的数组。

你这个问题拿到百度上是不可能有人回答你的，而且像这种操作系统的问题，步骤这么多是要收费的。去csdn求助试试。

计算机系统设计以及应用程序编写是C语言应用的两大领域。同时，C语言的普适较强，在许多计算机操作系统中都能够得到适用，且效率显著。C语言拥有经过了漫长发展历史的完整的理论体系，在编程语言中具有举足轻重的地位。

O(t+p+s)memmove：O(t-p)memcpy：O(s)最终复杂度O(t*p+2(t+s))-O(n^2)。可以看出热点在strstr函数。如果将其通过kmp或类似的匹配算法优化成O(n)的，那么复杂度可以直接降为O(n)。

C语言7种提高效率超赞方法位运算替代乘除位运算是C语言中的最小数据单元，移位运算或位处理基本上是每个MCU或者处理器的指令集中直接支持的，所以C代码编译成汇编以后基本上简单的几条汇编指令即可完成运算。

页面置换算法之LRU算法

三种常见的页面置换算法:FIFO、LFU、LRU
参考：
缓存算法（页面置换算法）-FIFO、LFU、LRU

LRU（Least Recently Used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是： 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小 。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

假设 序列为 4 3 4 2 3 1 4 2
物理块有3个 则
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
之后 4调入内存 4 1 3（原理同上）
最后 2调入内存 2 4 1

如果让我们设计一个LRU Cache的数据结构，它应该支持两个操作：

一种是采用数组来存储每个数据项，再对每个key关联一个时间戳，在cache中维护一个最大时间戳，其设计要点如下：

另一种是采用hashmap+双向链表的数据结构，其设计要点如下：

对比上一节的两种设计思路，不难发现，设计1需要为每个key维护一个时间戳，而且set和get操作的时间复杂度都是O(n)。显而易见，随着数据量的增大，set和get操作的速度越来越慢。而设计2通过采用hashmap+双向链表，set和get操作的时间复杂度只需O(1)，下面给出设计2的具体实现。

运行结果为：

参考：
LRU Cache
LRU原理和Redis实现——一个今日头条的面试题

操作系统课程设计，用C#实现内存页面的置换实现算法间比较

页面置换算法
一．题目要求：
通过实现页面置换算法的FIFO和LRU两种算法，理解进程运行时系统是怎样选择换出页面的，对于两种不同的算法各自的优缺点是哪些。
要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。
2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的：
1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 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个不同页面一起装入内存，后面步骤与前一算法类似。
选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换： 六．设计思想：
OPT基本思想：
是用一维数组page记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。
FIFO基本思想：
是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。
LRU基本思想：
是用一维数组page标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。 七．流程图：
如下页所示
六．运行结果： 1. 按任意键进行初始化：
2. 载入数据：
3. 进入置换算法选择界面：
4.运算中延迟操作：
5.三种算法演示结果：

页面置换算法

  上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
   本文内容

  算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
  举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

  ....按照此算法依次执行，最后的结果如下

  结果图

  注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
  最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。

  算法思想：每次选择 淘汰的页面是最早进入内存的页面。
  该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
  分配三个内存块的情况：

  分配四个内存块的情况：

  当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
   只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。

  算法思想： 每次淘汰的页面是最近最久未使用的页面。
  实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。

  举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
  这里先直接给出答案

  结果图

  最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
   简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过 两轮扫描 ）。

  这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。

  简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
  因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
  改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
  为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
   算法规则 ：将所有可能被置换的页面排成一个循环队列

  由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。

  假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图

  如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。

  某一时刻页面状态如下

  如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
  然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。

  某一时刻页面状态如下

  第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
  然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图

  某一时刻页面状态如下

  具体的扫描过程和上面相同，这里只给出最后的结果，如下图

  所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
  (1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
  (2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
  (3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
  (4) 第四优先级淘汰的是 最近访问且修改 的页面。

页面置换算法的实验

#include《stdlib.h》
#include《iostream.h》
#include《time.h》
#include《stdio.h》
#define total_instruction 200 /*指令流长*/
#define M 16 /*实际页数*/
#define N 4 //可用页面数
struct Pro
{
int num,time;
};
int a;
int page;
void Input(Pro p)
{
int m,i,m1,m2;
srand( (unsigned int )time(NULL));
m=rand( )%160; //
for(i=0;i《total_instruction;) /*产生指令队列*/
{
if(m《0||m》159)
{
printf("When i==%d,Error,m==%d\n",i,m);
exit(0);
}
a=m; /*任选一指令访问点m*/
a+1;
a+2; /*顺序执行两条指令*/
int m1=rand( )%m; /*执行前地址指令m1 */
a=m1;
a=m1+1;
a=m1 + 2;/*顺序执行两条指令*/

// s=(158-a+2;
m2 = rand()%(157-m1)+m1+3;
a=m2;
if( (m2+2) 》 159 )
{
a = m2+1;
i +=8;
}
else
{
a = m2+1;
a = m2+2;
i = i+9;
}
m = rand()%m2;

}
for (i=0;i《total_instruction;i++) /*将指令序列变换成页地址流*/
{
p/10;
p.time = 0;
}
}
void print(Pro *page1)//打印当前的页面
{
Pro *page=new Pro;
page=page1;
for(int i=0;i《N;i++)
cout《《page.num《《" ";
cout《《endl;
}
int Search(int e,Pro *page1 )
{
Pro *page=new Pro;
page=page1;
for(int i=0;i《N;i++)if(e==page.num)return i;
return -1;
}
int Max(Pro *page1)
{
Pro *page=new Pro;
page=page1;
int e=page.time,i=0;
while(i《N)//找出离现在时间最长的页面
{
if(e《page.time;
i++;
}
for( i=0;i《N;i++)if(e==page.time)return i;

return -1;
}
int Compfu(Pro *page1,int i,int t,Pro p)
{
Pro *page=new Pro;
page=page1;

int count=0;
for(int j=i;j《M;j++)
{
if(page.num )break;
else count++;
}
return count;

}
int main()
{
Pro p;
Pro *page=new Pro;
char c;
int t=0;
float n=0;
Input(p);

do{
for(int i=0;i《N;i++)//初试化页面基本情况
{
page.num=0;
page.time=2-i;
}

i=0;
cout《《"f:FIFO页面置换"《《endl;
cout《《"l:LRU页面置换"《《endl;
cout《《"o:OPT页面置换"《《endl;
cout《《"按其它键结束"《《endl;
cin》》c;

if(c==’f’)//FIFO页面置换
{
n=0;
cout《《"页面置换情况: "《《endl;
while( i《 total_instruction)
{
if(Search(p.num,page)》=0)
i++;//找到相同的页面
else
{
if(t==N)t=0;
else
{
n++;//
page.num;
print(page);
t++;
}
}
}
cout《《"缺页次数："《《n《《" 缺页率："《《n/total_instruction《《endl;

}
if(c==’l’)//LRU页面置换
{
n=0;
cout《《"页面置换情况: "《《endl;
while(i《total_instruction)
{
int k;
k=t=Search(p.num,page);
if(t》=0)

page.time=0;

else
{
n++;
t=Max(page);

page.num;
page.time=0;
}
if(t==0){page.time++;}
if(t==1){page.time++;}
if(t==2){page.time++;}
if(k==-1) print(page);
i++;
}
cout《《"缺页次数："《《n《《" 缺页率："《《n/total_instruction《《endl;
}
if(c==’o’)//OPT页面置换
{
n=0;
while(i《total_instruction)
{
if(Search(p.num,page)》=0)i++;
else
{
int temp=0,cn;
for(t=0;t《N;t++)
{
if(temp《Compfu(page,i,t,p))
{
temp=Compfu(page,i,t,p);
cn=t;
}
}
page;
n++;
print(page);
i++;
}
}
cout《《"缺页次数："《《n《《" 缺页率："《《n/total_instruction《《endl;
}

}while(c==’f’||c==’l’||c==’o’);
return 0;
}