操作系统页面置换算法
- 格式:pdf
- 大小:226.08 KB
- 文档页数:11
操作系统-页面置换算法操作系统页面置换算法在操作系统中,页面置换算法是一项至关重要的技术,它主要用于管理内存中的页面,当内存空间不足时,决定哪些页面应该被替换出去,为新的页面腾出空间。
这一过程对于系统的性能和效率有着直接的影响。
想象一下,内存就像是一个有限大小的书架,而页面就像是一本本书。
当书架已经满了,但我们还想放入新的书时,就必须要把一些书拿出来,为新书腾出位置。
页面置换算法就是决定拿哪本书出来的规则。
常见的页面置换算法有多种,下面我们来详细了解一下。
首先是先进先出(FIFO)算法。
它的原理就像排队一样,先进入内存的页面先被替换出去。
这种算法实现起来比较简单,但可能会出现一种叫做“Belady 异常”的现象,即增加分配给进程的物理块数量时,反而可能会导致缺页率增加。
这是因为可能先进入的页面是经常被使用的,而后面进来的是不常使用的,这样就容易造成错误的替换。
接下来是最近最久未使用(LRU)算法。
它的思路是把最近一段时间内最久没有被使用的页面替换出去。
这种算法的性能通常比较好,因为它更能反映页面的实际使用情况。
但它的实现相对复杂,需要额外的硬件支持或者通过软件来模拟实现。
然后是最近未使用(NRU)算法。
这个算法会把页面分为四类:未被访问且未被修改、未被访问但已被修改、已被访问但未被修改、已被访问且已被修改。
然后根据这些分类来选择替换的页面。
它的优点是实现相对简单,但可能不如 LRU 算法那么精确。
还有一种叫做时钟(Clock)算法,也称为第二次机会算法。
它把所有的页面组成一个环形链表,通过一个指针来遍历。
当需要替换页面时,如果页面的访问位是 0 ,则直接替换;如果是 1 ,则将其访问位置为 0 ,然后指针继续移动,直到找到访问位为 0 的页面。
除了以上这些,还有最优(OPT)算法。
这是一种理想的算法,它会选择未来最长时间内不会被使用的页面进行替换。
但由于它需要预先知道未来的页面访问情况,所以在实际中是无法实现的,通常只是用来作为评估其他算法性能的标准。
操作系统页⾯置换算法(opt,lru,fifo,clock )实现选择调出页⾯的算法就称为页⾯置换算法。
好的页⾯置换算法应有较低的页⾯更换频率,也就是说,应将以后不会再访问或者以后较长时间内不会再访问的页⾯先调出。
常见的置换算法有以下四种(以下来⾃操作系统课本)。
1. 最佳置换算法(OPT)最佳(Optimal, OPT)置换算法所选择的被淘汰页⾯将是以后永不使⽤的,或者是在最长时间内不再被访问的页⾯,这样可以保证获得最低的缺页率。
但由于⼈们⽬前⽆法预知进程在内存下的若千页⾯中哪个是未来最长时间内不再被访问的,因⽽该算法⽆法实现。
最佳置换算法可以⽤来评价其他算法。
假定系统为某进程分配了三个物理块,并考虑有以下页⾯号引⽤串: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1进程运⾏时,先将7, 0, 1三个页⾯依次装⼊内存。
进程要访问页⾯2时,产⽣缺页中断,根据最佳置换算法,选择第18次访问才需调⼊的页⾯7予以淘汰。
然后,访问页⾯0时,因为已在内存中所以不必产⽣缺页中断。
访问页⾯3时⼜会根据最佳置换算法将页⾯1淘汰……依此类推,如图3-26所⽰。
从图中可以看出⾤⽤最佳置换算法时的情况。
可以看到,发⽣缺页中断的次数为9,页⾯置换的次数为6。
图3-26 利⽤最佳置换算法时的置换图2. 先进先出(FIFO)页⾯置换算法优先淘汰最早进⼊内存的页⾯,亦即在内存中驻留时间最久的页⾯。
该算法实现简单,只需把调⼊内存的页⾯根据先后次序链接成队列,设置⼀个指针总指向最早的页⾯。
但该算法与进程实际运⾏时的规律不适应,因为在进程中,有的页⾯经常被访问。
图3-27 利⽤FIFO 置换算法时的置换图这⾥仍⽤上⾯的实例,⾤⽤FIFO 算法进⾏页⾯置换。
进程访问页⾯2时,把最早进⼊内存的页⾯7换出。
然后访问页⾯3时,再把2, 0, 1中最先进⼊内存的页换出。
LRU 页面置换算法1. 简介LRU(Least Recently Used)页面置换算法是一种常用的操作系统内存管理算法,用于在内存不足时决定哪些页面应该被置换出去以腾出空间给新的页面。
LRU算法基于一个简单的原则:最近最少使用的页面应该被置换。
在计算机系统中,内存是有限的资源,而运行程序所需的内存可能超过可用内存大小。
当系统发现没有足够的空闲内存来加载新页面时,就需要选择一些已经在内存中的页面进行替换。
LRU算法就是为了解决这个问题而设计的。
2. 原理LRU算法基于一个简单的思想:如果一个页面最近被访问过,那么它将来可能会再次被访问。
相反,如果一个页面很久没有被访问过,那么它将来可能不会再次被访问。
根据这个思想,LRU算法将最近最少使用的页面置换出去。
具体实现上,可以使用一个数据结构来记录每个页面最近一次被访问的时间戳。
当需要替换一页时,选择时间戳最早(即最久未访问)的页面进行替换即可。
3. 实现方式LRU算法的实现可以基于多种数据结构,下面介绍两种常见的实现方式。
3.1 使用链表一种简单的实现方式是使用一个双向链表来记录页面的访问顺序。
链表头部表示最近访问过的页面,链表尾部表示最久未被访问过的页面。
每当一个页面被访问时,将其从原位置移动到链表头部。
当需要替换一页时,选择链表尾部的页面进行替换。
这种实现方式的时间复杂度为O(1),但空间复杂度较高,为O(n),其中n为内存中可用页面数。
class Node:def __init__(self, key, value):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity):self.capacity = capacityself.cache = {}self.head = Node(0, 0)self.tail = Node(0, 0)self.head.next = self.tailself.tail.prev = self.headdef get(self, key):if key in self.cache:node = self.cache[key]self._remove(node)self._add(node)return node.valueelse:return -1def put(self, key, value):if key in self.cache:node = self.cache[key]node.value = valueself._remove(node)self._add(node)else:if len(self.cache) >= self.capacity:del self.cache[self.tail.prev.key] self._remove(self.tail.prev)node = Node(key, value)self.cache[key] = nodeself._add(node)def _remove(self, node):prev = node.prevnext = node.nextprev.next = nextnext.prev = prevdef _add(self, node):head_next = self.head.nextself.head.next = nodenode.prev = self.headnode.next = head_nexthead_next.prev = node3.2 使用哈希表和双向链表另一种实现方式是使用一个哈希表和一个双向链表。
操作系统课程设计报告书一、设计目的学习计算机软件技术,特别是计算机操作系统技术,除了需要刻苦努力外,还需要掌握软件和操作系统的原理与设计技巧。
本设计木的是通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。
二、设计任务1、通过随机数产生一个指令序列,共320条指令。
指令的地址按下述原则生成:50%的指令是顺序执行的;25%的指令是均匀分布在前地址部分;25%的指令是均匀分布在地址部分。
2、将指令序列换成为页地址流。
3、计算并输出下述各种算法在不同内存容量下的命中率。
(1)先进先出的算法(FIFO);(2)最近最少使用算法(LRU);(3)最近最不经常使用算法(NUR);三、设计内容与步骤分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片,称为页面或页。
1、调页策略1)何时调入页面2)请求调页策略2、从何处调入页面(1) 系统拥有足够的对换区空间,这时可以全部从对换区调入所需页面,以提高调页速度。
为此,在进程运行前,便须将与该进程有关的文件,从文件区拷贝到对换区。
(2) 系统缺少足够的对换区空间,这时凡是不会被修改的文件,都直接从文件区调入;而当换出这些页面时,由于它们未被修改而不必再将它们换出时,以后需要时,再从对换区调入。
(3) UNIX方式。
由于与进程有关的文件都放在文件区,故凡是未运行过的页面,都从文件区调入。
而对于曾经运行过但又被换出的页面,由于被放在对换区,因此在下次时,应从对换区调入。
由于UNIX系统允许页面共享,因此,某进程所请求的页面有可能已被其它进程调入内存,此时也就无须再从对换区调入。
3、页面调入过程四、页面置换算法在进程运行过程中,若其所要访问的页面不在内存而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的对换区中。
但应将哪个页面调出,须根据一定的算法来确定。
常见的页面置换算法1.概述页面置换算法是操作系统中用于管理内存的一种算法,其目的是确保可用内存的最大化并实现对内存的高效使用。
在操作系统中,当进程所需的内存空间超出了可用的物理内存空间时,操作系统就需要从主存中选择一些页面腾出空间来装载进程所需的页面。
这就需要使用页面置换算法。
2.常见的页面置换算法2.1最优页面置换算法(OPT)最优页面置换算法是一种理论上的置换算法。
它的核心思想是通过计算进程未来访问各个页面的时间和距离,来推断出离当前时间最久的页面。
这种算法的优点是能够保证页面置换的最优性,但是它需要预先知道进程未来所有的页面调度情况,这在实际应用中是不可行的。
2.2先进先出(FIFO)置换算法先进先出置换算法是一种很简单的置换算法,它选取主存中驻留时间最长的页面作为替换目标。
优点是实现简单,但是缺点是可能会引发置换震荡问题。
2.3最近最久未使用算法(LRU)最近最久未使用算法是一种比较常用的页面置换算法,其核心思想是将驻留时间久且最近一次使用时间早的页面视为需要置换的页面。
相对于FIFO算法,LRU算法能够保证更高的页面命中率和更小的置换次数。
2.4时钟置换算法(Clock)时钟置换算法是一种改进型的FIFO算法。
该算法使用一个环形队列来存储主存中的页面位置信息。
当需要置换页面时,指针先指向队列首位置,遍历队列并且在第一遍扫描时,将页框的访问位ACC设置为0。
第一遍扫描结束后,如果有页面的ACC位为0,就将其替换出去。
如果找不到未访问页面,指针再回到队列首位置,以此类推,直到找到为止。
3.总结以上所述的几种页面置换算法是操作系统中常见的算法。
它们各有优点和缺点,在实际应用中,需要根据实际情况进行选择。
在选择算法后,还需要对其进行适当的调整,以满足实际需求。
opt置换算法什么是OPT置换算法?OPT置换算法是一种页面置换算法,用于解决操作系统中的页面置换问题。
该算法会根据未来最长时间内不会被使用的页面进行替换,以达到最优化的效果。
如何实现OPT置换算法?1. 确定缓存大小首先,需要确定缓存的大小。
缓存大小应该足够大,以便能够容纳系统中经常使用的页面。
2. 缓存初始化然后,需要将缓存初始化为空。
这意味着所有页面都没有被加载到内存中。
3. 页面请求当一个新的页面请求进入系统时,需要检查该页面是否已经在缓存中。
如果是,则不需要进行任何操作。
如果不是,则需要将该页面加载到缓存中。
4. 缺页处理当所有的缓存空间都被占满时,如果有新的页面请求进来,则需要进行缺页处理。
这时候就需要使用OPT算法来决定哪个页面应该被替换出去。
5. 实现OPT算法实现OPT算法可以分为以下几个步骤:(1)找到未来最长时间内不会被使用的页面。
(2)将该页面从缓存中移除,并将新请求的页面添加到其中。
6. 重复执行步骤3-5重复执行上述步骤,直到所有的页面请求都被处理完毕。
OPT算法的优缺点优点:1. 最优化:OPT算法可以保证在所有页面置换算法中得到最优解。
2. 简单易懂:OPT算法的实现方法相对简单,易于理解和实现。
缺点:1. 确定未来最长时间内不会被使用的页面是一个难题,需要进行一定的预测和分析。
2. 实际应用受限:由于需要对未来进行预测,因此在实际应用中受到一定的限制。
3. 空间复杂度高:OPT算法需要维护一个队列来存储未来时间内不会被使用的页面,因此空间复杂度较高。
结论总体而言,OPT置换算法是一种非常优秀的页面置换算法。
虽然它存在一些缺点,但是它可以保证在所有页面置换算法中得到最优解。
在实际应用中,我们可以根据具体情况选择合适的页面置换算法。
页面置换算法实验报告一、实验目的本次实验的目的是通过模拟页面置换算法的过程,了解不同算法的优缺点,掌握算法的实现方法,以及对算法的性能进行评估。
二、实验原理页面置换算法是操作系统中的一个重要概念,它是为了解决内存不足的问题而产生的。
当系统中的进程需要使用内存时,如果内存已经被占满,就需要将一些页面从内存中置换出去,以便为新的页面腾出空间。
页面置换算法就是用来决定哪些页面应该被置换出去的算法。
常见的页面置换算法有以下几种:1. 最佳置换算法(OPT)最佳置换算法是一种理论上的最优算法,它总是选择最长时间内不会被访问的页面进行置换。
但是,由于无法预测未来的页面访问情况,因此最佳置换算法无法在实际中使用。
2. 先进先出置换算法(FIFO)先进先出置换算法是一种简单的置换算法,它总是选择最先进入内存的页面进行置换。
但是,这种算法容易出现“抖动”现象,即频繁地将页面置换出去,然后再将其置换回来。
3. 最近最久未使用置换算法(LRU)最近最久未使用置换算法是一种比较常用的置换算法,它总是选择最长时间未被访问的页面进行置换。
这种算法可以避免“抖动”现象,但是实现起来比较复杂。
4. 时钟置换算法(Clock)时钟置换算法是一种改进的FIFO算法,它通过维护一个环形链表来实现页面置换。
当需要置换页面时,算法会从当前位置开始扫描链表,如果找到一个未被访问的页面,则将其置换出去。
如果扫描一圈后都没有找到未被访问的页面,则将当前位置的页面置换出去。
三、实验过程本次实验使用Python语言编写了一个页面置换算法模拟程序,可以模拟上述四种算法的过程,并输出算法的性能指标。
程序的主要流程如下:1. 读取输入文件,获取页面访问序列和内存大小等参数。
2. 根据选择的算法,初始化相应的数据结构。
3. 遍历页面访问序列,模拟页面置换的过程。
4. 输出算法的性能指标,包括缺页率、页面置换次数等。
下面分别介绍四种算法的实现方法。
1. 最佳置换算法(OPT)最佳置换算法需要预测未来的页面访问情况,因此需要遍历整个页面访问序列,找到最长时间内不会被访问的页面。
操作系统——模拟页⾯置换算法(FIFO——先⼊先出、LRU——最近最少使⽤、LFU——最近。
操作系统——模拟页⾯置换算法(FIFO——先⼊先出、LRU——最近最少使⽤、LFU——最近最不常使⽤),计算置换率(包含程序框图)导语:1. FIFO页⾯置换算法:最简单的页⾯置换算法。
这种算法的基本思想是:当需要淘汰⼀个页⾯时,总是选择驻留主存时间最长的页⾯进⾏淘汰,即先进⼊主存的页⾯先淘汰。
(看时间)2. LRU页⾯置换算法:最近最少使⽤,简单来说就是将数据块中,每次使⽤过的数据放在数据块的最前端,然后将存在的时间最长的,也就是数据块的末端的数据置换掉。
(看时间)3. LFU页⾯置换算法:近期最少使⽤算法,选择近期最少访问的页⾯作为被替换的页⾯,如果⼀个数据在最近⼀段时间内使⽤次数很少,那么在将来⼀段时间内被使⽤的可能性也很⼩。
(看次数)4. 置换率与与缺页率不同。
置换率⽤置换次数算,缺页率⽤缺页中断次数算。
FIFO页⾯置换算法:Linux效果图(采⽤UOS + VScode + g++)程序框图C++代码(FIFO):#include<iostream>using namespace std;static int mnum;//物理块数static int pnum;//页⾯⾛向static int count=0;//页⾯置换次数static int *analogblock;//模拟物理块static int *block;//物理块static int *process;//随机页⾯访问序列int judge(int a[],int n,int x) //判断数组中是否已有x,若有返回其下标值,没有则返回-1 {int i;for (i=0;i<n;i++)if(x==a[i])return i;return -1;}void replace(int y,int mnum,int x)//⽤于物理块页⾯置换,y是⽤来置换的页⾯,x是被置换的页⾯ {int i;for (i=0;i<mnum;i++)if(x==block[i])block[i]=y;}int main() {int i;int maxanalogblock=-1;//模仿队列的定义int x;cout<<"请输⼊页框⼤⼩物理块数:\n";cin>>mnum;if(mnum>999999) {cout<<"输⼊超出控制⼤⼩!"<<endl;return 0;}cout<<"⾃动⽣成的内存块需求序列个数:\n";cin>>pnum;if(pnum>999999) {cout<<"输⼊超出控制⼤⼩!"<<endl;return 0;}analogblock=new int[mnum];block=new int[mnum];process=new int[pnum];for (i=0;i<mnum;i++) analogblock[i]=-1;for (i=0;i<mnum;i++) block[i]=-1;///////////////////////随机产⽣页⾯⾛向序列cout<<"产⽣随机序列如下:\n";srand( (unsigned)time( NULL ) );//以time函数值(即当前时间)作为种⼦数,保证两次产⽣序列的随机性for (i=0; i<pnum; i++) {process[i] = rand()%10;cout<<process[i]<<" ";}cout<<endl;//////////////////////cout<<"先进先出(FIFO)页⾯置换算法,结果: \n\n";//////////////////////for (x=0;x<pnum;x++) //⾃动读数 {//读⼀个序列号,输出当前数组元素cout<<"真实物理块情况:";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况:";for (i=0;i<mnum;i++) {if(analogblock[i]!=-1)cout<<analogblock[i]<<" ";}//////////////////////////maxanalogblock++;//读数后maxanalogblock⾃动+1if(maxanalogblock<mnum) //若在物理块范围内 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {analogblock[maxanalogblock]=process[x];//新元素从尾部插⼊block[maxanalogblock]=process[x];//新元素从尾部插⼊cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 缺页中断调⼊页⾯"<<process[x]<<endl;} else //若数组中存在待插⼊元素 {maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock值cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 已存在直接访问"<<endl;}} else //超过物理块数的元素 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {//队列法插⼊(尾部元素出,新元素从头部⼊)cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 缺页中断页⾯"<<process[x]<<"置换出页⾯"<<analogblock[0]<<endl; replace(process[x],mnum,analogblock[0]);//置换物理块中页⾯for (i=0;i<mnum-1;i++)LRU 页⾯置换算法:Linux 效果图(采⽤UOS + VScode + g++)程序框图C++代码(LRU): analogblock[i]=analogblock[i+1];analogblock[mnum-1]=process[x];//////////////////maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock 值count++;} else //若数组中存在待插⼊元素 {maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock 值cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 已存在 直接访问"<<endl;}}}//读⼀个序列号,输出当前数组元素cout<<"真实物理块情况:";for (i=0;i<mnum;i++) {if(block[i]!=-1) cout<<block[i]<<" ";}cout<<"模拟物理块情况:";for (i=0;i<mnum;i++) {if(analogblock[i]!=-1)cout<<analogblock[i]<<" ";}cout<<endl<<"页⾯换算次数为:"<<count<<endl;cout<<"置换率为:"<<(float)count/pnum<<endl;return 0;}//g++ test71.cpp -o test71 -lpthread&&./test71#include<iostream>using namespace std;static int mnum;//物理块数static int pnum;//页⾯⾛向static int count=0;//页⾯置换次数static int *analogblock;//模拟物理块static int *block;//物理块static int *process;//随机页⾯访问序列int judge(int a[],int n,int x) //判断数组中是否已有x ,若有返回其下标值,没有则返回-1 {int i;for (i=0;i<n;i++)if(x==a[i])return i;return -1;}void replace(int y,int mnum,int x)//⽤于物理块页⾯置换,y是⽤来置换的页⾯,x是被置换的页⾯ { int i;for (i=0;i<mnum;i++)if(x==block[i])block[i]=y;}void move(int a[],int n,int i) //移动下标为i的元素到尾部 {int j;int m=a[i];for (j=i;j<n-1;j++)a[j]=a[j+1];a[n-1]=m;}int main() {int i;int maxanalogblock=-1;//模仿栈的定义int x;cout<<"请输⼊页框⼤⼩物理块数:\n";cin>>mnum;if(mnum>999999) {cout<<"输⼊超出控制⼤⼩!"<<endl;return 0;}cout<<"⾃动⽣成的内存块需求序列个数:\n";cin>>pnum;if(pnum>999999) {cout<<"输⼊超出控制⼤⼩!"<<endl;return 0;}analogblock=new int[mnum];block=new int[mnum];process=new int[pnum];for (i=0;i<mnum;i++) analogblock[i]=-1;///////////////////////随机产⽣页⾯⾛向序列cout<<"产⽣随机序列如下:\n";srand( (unsigned)time( NULL ) );//以time函数值(即当前时间)作为种⼦数,保证两次产⽣序列的随机性for (i=0; i<pnum; i++) {process[i] = rand()%10;cout<<process[i]<<" ";}cout<<endl;//////////////////////cout<<"最近最少使⽤(LRU)页⾯置换算法,结果: \n\n";//////////////////////for (x=0;x<pnum;x++) //⾃动读数 {//读⼀个序列号,输出当前数组元素cout<<"真实物理块情况:";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况:";for (i=0;i<mnum;i++) {if(analogblock[i]!=-1)cout<<analogblock[i]<<" ";}//////////////////////////maxanalogblock++;//读数后maxanalogblock⾃动+1LFU 页⾯置换算法:Linux 效果图(采⽤UOS + VScode + g++)程序框图 if(maxanalogblock<mnum) //若在物理块范围内 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {analogblock[maxanalogblock]=process[x];//新元素从尾部插⼊block[maxanalogblock]=process[x];//新元素从尾部插⼊cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 缺页中断 调⼊页⾯"<<process[x]<<endl;} else //若数组中存在待插⼊元素 {move(analogblock,maxanalogblock,judge(analogblock,mnum,process[x]));//移动下标为i 的元素到尾部maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock 值cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 已存在 直接访问"<<endl;}} else //超过物理块数的元素 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {//栈法插⼊(第⼀个元素出,后⾯元素前移,新元素从尾部⼊)cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 缺页中断 页⾯"<<process[x]<<"置换出页⾯"<<analogblock[0]<<endl; replace(process[x],mnum,analogblock[0]);//物理块中页⾯置换for (i=0;i<mnum-1;i++)analogblock[i]=analogblock[i+1];analogblock[mnum-1]=process[x];//////////////////maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock 值count++;} else //若数组中存在待插⼊元素 {move(analogblock,mnum,judge(analogblock,mnum,process[x]));//移动下标为i 的元素到尾部maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock 值cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 已存在 直接访问"<<endl;}}}//读⼀个序列号,输出当前数组元素cout<<"真实物理块情况:";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况:";for (i=0;i<mnum;i++) {if(analogblock[i]!=-1)cout<<analogblock[i]<<" ";}cout<<endl<<"页⾯换算次数为:"<<count<<endl;cout<<"置换率为:"<<(float)count/pnum<<endl;return 0;}//g++ test72.cpp -o test72 -lpthread&&./test72C++代码(LFU):#include<iostream>using namespace std;static int mnum;//物理块数static int pnum;//页⾯⾛向static int count=0;//页⾯置换次数static int **analogblock;//模拟物理块static int *block;//物理块static int *process;//随机页⾯访问序列int judge(int *a[],int n,int x) //判断数组中是否已有x,若有返回其下标值,没有则返回-1 {int i;for (i=0;i<n;i++)if(x==a[i][0])return i;return -1;}void replace(int y,int mnum,int x)//⽤于物理块页⾯置换,y是⽤来置换的页⾯,x是被置换的页⾯ { int i;for (i=0;i<mnum;i++)if(x==block[i])block[i]=y;}void move(int *a[],int n,int i) //移动下标为i的元素,⽐较访问次数次多少进⾏前进 {int j;int m=a[i][0];int m2=a[i][1];for (j=i;j<n-1;j++) {if(m2>=a[j+1][1]) {a[j][0]=a[j+1][0];a[j][1]=a[j+1][1];a[j+1][0]=m;a[j+1][1]=m2;}}}int main() {int i;int maxanalogblock=-1;//模仿栈的定义int x;//动态数组初始化cout<<"请输⼊页框⼤⼩物理块数:\n";cin>>mnum;if(mnum>999999) {cout<<"输⼊超出控制⼤⼩!"<<endl;return 0;}cout<<"⾃动⽣成的内存块需求序列个数:\n";cin>>pnum;if(pnum>999999) {cout<<"输⼊超出控制⼤⼩!"<<endl;return 0;}analogblock=(int**) (new int[mnum]);block=new int[mnum];process=new int[pnum];for (i=0;i<mnum;i++) analogblock[i]=(int*) new int[2];//⽤于保存页⾯号和访问次数for (i = 0; i < mnum; i++) {analogblock[i][0]=-1;analogblock[i][1]=0;}///////////////////////随机产⽣页⾯⾛向序列cout<<"产⽣随机序列如下:\n";srand( (unsigned)time( NULL ) );//以time函数值(即当前时间)作为种⼦数,保证两次产⽣序列的随机性for (i=0; i<pnum; i++) {process[i] = rand()%10;cout<<process[i]<<" ";}cout<<endl;//////////////////////cout<<"最近最不常使⽤(LFU)页⾯置换算法,结果: \n\n";//////////////////////for (x=0;x<pnum;x++) //⾃动读数 {//读⼀个序列号,输出当前数组元素cout<<"真实物理块情况:";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况:";for (i=0;i<mnum;i++) {if(analogblock[i][0]!=-1)cout<<analogblock[i][0]<<" ";//<<"访问次数"<<analogblock[i][1]<<" "}//////////////////////////maxanalogblock++;//读数后maxanalogblock⾃动+1if(maxanalogblock<mnum) //若在物理块范围内 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {analogblock[0][0]=process[x];//新元素从头部插⼊analogblock[0][1]=1;block[maxanalogblock]=process[x];//新元素从尾部插⼊move(analogblock,mnum,0);//移动下标为i的元素到相同访问次数页⾯的顶部cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 缺页中断调⼊页⾯"<<process[x]<<endl;} else //若数组中存在待插⼊元素 {// move(analogblock,maxanalogblock,judge(analogblock,mnum,process[x]));//移动下标为i的元素到尾部analogblock[judge(analogblock,mnum,process[x])][1]++;move(analogblock,mnum,judge(analogblock,mnum,process[x]));//移动下标为i的元素到相同访问次数页⾯的顶部maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock值cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 已存在直接访问"<<endl;}} else //超过物理块数的元素 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {//栈法插⼊(新元素从头部⼊,替换掉头部)cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 缺页中断页⾯"<<process[x]<<"置换出页⾯"<<analogblock[0][0]<<endl; replace(process[x],mnum,analogblock[0][0]);//物理块中页⾯置换analogblock[0][0]=process[x];analogblock[0][1]=1;move(analogblock,mnum,0);//移动下标为i的元素相同访问次数页⾯的顶部//////////////////maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock值count++;} else //若数组中存在待插⼊元素 {analogblock[judge(analogblock,mnum,process[x])][1]++;move(analogblock,mnum,judge(analogblock,mnum,process[x]));//移动下标为i的元素到相同访问次数页⾯的顶部maxanalogblock--;//因为没有插⼊新元素,回滚maxanalogblock值cout<<" 第"<<x+1<<"次访问,页⾯"<<process[x]<<" 已存在直接访问"<<endl; }}}//读⼀个序列号,输出当前数组元素cout<<"真实物理块情况:";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况:";for (i=0;i<mnum;i++) {if(analogblock[i][0]!=-1)cout<<analogblock[i][0]<<" ";}cout<<endl<<"页⾯换算次数为:"<<count<<endl;cout<<"置换率为:"<<(float)count/pnum<<endl;return 0;}//g++ test73.cpp -o test73 -lpthread&&./test73。
页面置换算法实验报告背景页面置换算法是计算机操作系统中的一个重要概念,它用于解决操作系统需要共享有限的物理内存资源给多个进程使用的问题。
在操作系统中,每个进程都有自己的虚拟地址空间,但实际的物理内存资源是有限的。
当物理内存不足时,操作系统需要根据一定的策略将一部分进程暂时从内存中移出,以便为其他进程让出空间,而后再从外存中将其重新加载到内存中。
这个过程就是页面置换。
页面置换算法有很多种,比如最优页面置换算法(Optimal)、先进先出页面置换算法(FIFO)、最近最久未使用页面置换算法(LRU)等等。
不同的算法对于系统性能、响应时间等指标有着不同的影响,因此在实际应用中需要选择合适的算法来平衡各种需求。
本实验旨在通过模拟页面置换算法,并对不同算法进行性能分析,以便了解各种算法的优缺点,为实际系统的选择提供依据。
分析在实验中,我们选择了三种常用的页面置换算法,分别是FIFO、LRU和Optimal。
下面对这三种算法进行详细的分析和说明。
先进先出页面置换算法(FIFO)FIFO算法是最简单和最直观的页面置换算法。
它按照页面进入内存的顺序来选择被淘汰的页面。
当内存不足时,选择最早进入内存的页面进行置换,即将其从内存中移出。
FIFO算法不需要进行进一步的页面访问计算,只需要维护一个页面进入内存的队列即可,因此实现起来比较简单。
然而,由于FIFO算法没有考虑页面的访问频率和重要性,所以可能会导致被频繁访问的页面被淘汰出内存,从而影响系统的性能。
最近最久未使用页面置换算法(LRU)LRU算法是一种基于”最近使用原则”的页面置换算法。
它根据页面最近被访问的时间来选择被淘汰的页面。
当内存不足时,选择最长时间未被访问的页面进行置换,即将其从内存中移出。
LRU算法需要维护一个页面访问时间的记录,以便在需要置换时能够快速找到最近最久未使用的页面。
相比于FIFO算法,LRU算法更加合理地利用了页面的访问情况,但实现起来相对复杂一些。
四种页面置换算法一、实验原理:在存运行过程中,若其所要访问的页面不在存而需要把他们调入存,但存已经没有空闲空间时,为了保证该进程能正常运行,系统必须从存中调出一页程序或数据送磁盘的对换区中。
但应将那个页面调出,需根据一定的算法来确定。
通常,把选择换出页面的算法成为页面置换算法。
置换算法的好坏,将直接影响到系统的性能。
一个好的页面置换算法,应具有较低的页面更换频率。
从理论上讲,应将那些以后不再会访问的页面置换出,或者把那些在较长时间不会在访问的页面调出。
目前存在着许多种置换算法(如FIFO,OPT,LRU),他们都试图更接近理论上的目标。
二、实验目的1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。
2.掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想,并至少用三种算法来模拟实现。
3.通过对几种置换算法页面的比较,来对比他们的优缺点,并通过比较更换频率来对比它们的效率。
三、实验分析在进程运行过程中,若其所访问的页面不存在存而需要把它们调入存,但存已无空闲时,为了保证该进程能够正常运行,系统必须从存中调出一页程序或数据送磁盘的对换区中。
但应调出哪个页面,需根据一定的算法来确定,算法的好坏,直接影响到系统的性能。
四、运行结果五、代码#include"stdafx.h"#define M 3 //物理页数#define N 20 //需要调入的页数typedef struct page {int num;int time;int temp;}Page; //物理页项,包括调入的页号和时间Page pp[M]; //M个物理页int queue1[20], queue2[20], queue3[20]; //记录置换的页int K = 0, S = 0, T = 0; //置换页数组的标识int pos = 0;//记录存在最长时间项int changenum = 0;int A[N];//初始化存页表项及存储存情况的空间void INIT(){int i;for (i = 0; i<M; i++){pp[i].num = -1;pp[i].time = 0;pp[i].temp = 0;} }//取得存中存在时间最久的位置int GetMax(){int max = -1;int i;for (i = 0; i<M; i++){if (pp[i].time > max){max = pp[i].time;pos = i;}}return pos;}//检查最长时间不使用页面int longestTime(int mxatimep,int temp) {int i;int max = -1;for (i = 0; i<M; i++){pp[i].temp = 0;}for (i = temp; i<N; i++){if (pp[0].temp == 1 && pp[1].temp == 1 && pp[2].temp == 1){ break;}if (pp[0].num != A[i]){pp[0].time++;if (pp[0].temp >= 1){pp[0].time--;}}else{pp[0].temp++;}if (pp[1].num != A[i]){pp[1].time++;if (pp[1].temp >= 1){pp[1].time--;}}else{pp[1].temp++;}if (pp[2].num != A[i]){pp[2].time++;if (pp[2].temp >= 1){pp[2].time--;}else{pp[2].temp++;}}for (i = 0; i<M; i++){if (pp[i].time>max){max = pp[i].time;pos = i;}}return pos;}//检查某页是否在存int Equation(int fold){int i;for (i = 0; i<M; i++){if (pp[i].num == fold)return i;}return -1;}//检查物理存是否已满,-1表满,其他不满int Check(){int i;for (i = 0; i<M; i++){if (pp[i].num == -1)return i;}return -1;}void FIFO(int fold,int temp){int i;int a, b, c;a = Equation(fold);//页已存在if (a != -1){}//页不存在else{b = Check();//存还有空闲if (b != -1){pp[b].num = fold;//存已满,需要置换else {c = GetMax();pp[c].num = fold;pp[c].time = 0;changenum++;}queue1[K++] = fold;}for (i = 0; i<M; i++){if (pp[i].num != -1){pp[i].time++;}}}void OPT(int fold,int temp){int a, b, c;a = Equation(fold);if (a == -1){//页不在存b = Check();//存还有空闲if (b != -1){pp[b].num = fold;}//存已满,需要置换else{c = longestTime(fold,temp);pp[c].num = fold;pp[c].time = 0;changenum++;}queue3[T++] = fold;}}void LRU(int fold,int temp){int i;int a, b;int p;a = Equation(fold);if (a != -1)//页已在存{//把此项移动到链表最后一项if (a == 2)//此项已经在最后,不需要做任何改动{}else{p = Equation(-1);if (p == -1)//链表是满的{for (; a<2; a++)pp[a].num = pp[a + 1].num;pp[2].num = fold;}else if (p <= 3)//链表不满{for (; a<p - 1; a++)pp[a].num = pp[a + 1].num;pp[a].num = fold;}}}else{b = Check();if (b != -1)//不满pp[b].num = fold;else{for (i = 0; i<2; i++)pp[i].num = pp[i + 1].num;pp[2].num = fold;changenum++;}queue2[S++] = fold;}}int_tmain(int argc, _TCHAR* argv[]){int B[N];int i;INIT();changenum = 0;printf("请依次输入%d个页面号:\n", N);for (i = 0; i<N; i++){scanf_s("%d", &A[i]);}//OPTprintf("\n");printf("1.最佳置换算法(Opt)\n");INIT();changenum = 0;for (i = 0; i<N; i++){B[i] = A[i];}for (i = 0; i<N; i++){OPT(B[i], i);}printf("\n");printf("OPT算法,调入页面顺序为:");for (i = 0; i<T; i++)printf("%3d", queue3[i]);printf("\n页面置换次数为:%6d\n缺页率:%16.2f\n\n", changenum, (float)changenum / N); //FIFOprintf("2.先进先出页面置换算法(FIFO)\n");INIT();changenum = 0;for (i = 0; i<N; i++){B[i] = A[i];}for (i = 0; i<N; i++){FIFO(B[i], i);}printf("FIFO算法,调入页面顺序为:");for (i = 0; i<K; i++)printf("%3d", queue1[i]);printf("\n页面置换次数为:%6d\n缺页率:%16.2f\n\n", changenum, (float)changenum / N);//LRUprintf("3.最近最久未使用算法(LRU)\n");INIT();changenum = 0;for (i = 0; i<N; i++){B[i] = A[i];}for (i = 0; i<N; i++){LRU(B[i], i);}printf("LRU算法,调入页面顺序为:");for (i = 0; i<S; i++)printf("%3d", queue2[i]);printf("\n页面置换次数为:%6d\n缺页率:%16.2f\n\n", changenum, (float)changenum / N);printf("\n");printf("四种算法已全部执行完毕!\n");return 0;}。
操作系统-1-存储管理之LFU页⾯置换算法(leetcode460)LFU缓存题⽬:请你为最不经常使⽤(LFU)缓存算法设计并实现数据结构。
它应该⽀持以下操作:get 和 put。
get(key) - 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。
put(key, value) - 如果键不存在,请设置或插⼊值。
当缓存达到其容量时,则应该在插⼊新项之前,使最不经常使⽤的项⽆效。
在此问题中,当存在平局(即两个或更多个键具有相同使⽤频率)时,应该去除最近最少使⽤的键。
「项的使⽤次数」就是⾃插⼊该项以来对其调⽤ get 和 put 函数的次数之和。
使⽤次数会在对应项被移除后置为 0 。
⽰例: LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4代码:1class LFUCache {23public LFUCache(int capacity) {45 }67public int get(int key) {89 }1011public void put(int key, int value) {1213 }14 }1516/**17 * Your LFUCache object will be instantiated and called as such:18 * LFUCache obj = new LFUCache(capacity);19 * int param_1 = obj.get(key);20 * obj.put(key,value);21*/LFU页⾯置换算法(最不经常使⽤算法) 原理: 选择到当前时间为⽌被访问次数最少的页⾯被置换; 每页设置访问计数器,每当页⾯被访问时,该页⾯的访问计数器加1; 发⽣缺页中断时,淘汰计数值最⼩的页⾯,并将所有计数清零; 如图:图中的页⾯为三页,依次向存储中加⼊432143543215这些数字。
【操作系统】页⾯置换算法(最佳置换算法)(C语⾔实现)【操作系统】页⾯置换算法(最佳置换算法)(C语⾔实现)(编码⽔平较菜,写博客也只是为了个⼈知识的总结和督促⾃⼰学习,如果有错误,希望可以指出)1.页⾯置换算法:在地址映射过程中,若在页⾯中发现所要访问的页⾯不在内存中,则产⽣缺页中断。
当发⽣缺页中断时,如果操作系统内存中没有空闲页⾯,则操作系统必须在内存选择⼀个页⾯将其移出内存,以便为即将调⼊的页⾯让出空间。
⽽⽤来选择淘汰哪⼀页的规则叫做页⾯置换算法。
⼀个好的页⾯置换算法,应具有较低的页⾯更换频率。
从理论上讲,应该保留最近重复访问的页⾯,将以后都不再访问或者很长时间内不再访问的页⾯调出。
----百度百科2.具体的页⾯置换算法:2.1 最佳置换算法:⼀个进程在内存的若⼲个页⾯中,哪⼀个页⾯是未来最长时间内不再被访问的,那么如果发⽣缺页中断时,就将该页⾯换出,以便存放后⾯调⼊内存中的页⾯。
1.这是计算机操作系统(第四版)中的⼀个例⼦。
系统⾸先为进程分配了三个物理块。
上⾯⼀排数字是作业号。
在转满三个物理块后,要访问2号作业,2号作业不在内存,所以会发⽣缺页中断,然后系统需要将2号作业调⼊内存,但是此时物理块已经装满。
2.依据最佳置换算法,会将7号页换出(0号页在2号页后第1个就会被访问,1号页在2号页后第10个会被访问,7号页在2号页后第14个会被访问,7号页在已经装⼊内存的作业中是未来最长时间不会被访问的,所以换出7号页)。
3.后⾯依次类推。
2.2 先进先出算法:如果发⽣缺页中断,需要换出⼀个页⾯的时候,总是选择最早进⼊内存的页⾯,即选择在内存中驻留时间最久的页⾯进⾏换出。
有点不清楚。
就是每次发⽣缺页就将最早进⼊内存的页⾯换出,然后将刚调⼊的页⾯换⼊该物理块。
2.3 最近最久未使⽤(LRU)置换算法:LRU算法是缺页中断发⽣时选择最久未使⽤的页⾯进⾏换出。
这个算法其实也很好判断。
分享⼀个⼩技巧。
内存分配了k个物理块,发⽣缺页中断将要往内存调⼊某个页⾯的时候,在该页⾯往前⾯数K个物理块最前⾯的那个就会是要换出的,因为该页⾯最长时间未被使⽤过。
操作系统之页⾯置换算法(最佳置换OPT,先进先出FIFO,最近最久未使⽤LRU)最近学习操作系统时,实验要求实现常见的三种页⾯置换算法,博主按照书上要求试着编写,实现了案例,并记录在博客随记中,以便后续⾃⼰复习并也给需要的同学分享参考⼀下!⽔平有限,若有错,请悄悄告诉博主!博主好⽴即改正。
最佳置换算法(optimal replacement,OPT)是从内存中选择今后不再访问的页⾯或者在最长⼀段时间后才需要访问的页⾯进⾏淘汰。
如下例⼦:根据页⾯⾛向依次处理,得到最终的置换结果如下图表,整个页⾯缺页次数为7,缺页率为7/12=58%。
1 #include <iostream>2 #include <stdio.h>3 #include <stdlib.h>4#define N 125#define B 36using namespace std;78int pageArr[N]={1,2,3,4,1,2,5,1,2,3,4,5};//页⾯⾛向9int block[B]={0};//物理块3个,其数值是页号10 typedef struct FLAG {11int flags[B];12int counts;13 } FLAG;1415void opt(int pageArr[],int block[]);16int inBlock(int which);17int findFar(int next);18void Replace(int index,int value);19void disPlay();2021int main(void){22 cout << "begin:" <<endl;23 opt(pageArr,block);24 cout << "end!" <<endl;25return0;26 }2728void opt(int pageArr[],int block[]){29int getIndex;30for(int i=0;i<N;i++){31if(i<3){//前3页号#短缺#进队列32 block[i]=pageArr[i];33 printf("缺页:(null)-->%d\n",pageArr[i]);34 }35else {36if(i==3){37 disPlay();3839 }40if(inBlock(pageArr[i])!=-1){//下⼀个页⾯if在物理块中返回index并跳过,反-141 disPlay();4243continue;44 }45 getIndex=findFar(i+1);//从下⼀个页号,找到最远出现的页⾯,替换的下标46if(getIndex==-1){47 cout<<"error,not replace obj!"<<'\t';48 }49else{50 Replace(getIndex,pageArr[i]);//由下标找到上⼀组替换⽬标,⽤第⼆参数替换51 disPlay();5253 }54 }55 }56return;57 }5859//替换block中的物理块60void Replace(int index,int value){61 printf("缺页:%d--被替换为-->%d\n",block[index],value);62 block[index]=value;63return;64 }656667//找到最远出现的页⾯68int findFar(int next){69int index=-1;//error,默认返回不存在的索引70 FLAG myflag;71 myflag.flags[0]=0;72 myflag.flags[1]=0;73 myflag.flags[2]=0;74 myflag.counts=0;75int stop = N-next;76while(stop--){77 index=inBlock(pageArr[next++]);78if(index!=-1){79 myflag.flags[index]=1;80 myflag.counts++;83break;84 }85 }86for(index=0;index<B;index++){87if(myflag.flags[index]==0)88break;89 }90return index;91 }929394//下⼀个页⾯if在物理块中返回index,反-195int inBlock(int which){96//int i=0;97//while(i<B)98// if(block[i++]==which)99// return i-1;100for(int i=0;i<B;i++){101if(block[i]==which)102return i;103 }104return -1;105 }106107//打印⼀元组108void disPlay(){109int i=0;110while(i<B){111 printf("%d\t",block[i++]);112 }113 printf("\n");114return;115 }上⾯是博主使⽤C++(基本是C语法)编写的代码,运⾏结果如下://////////////////////////////////////////////////////////////////////////begin:缺页:(null)-->1缺页:(null)-->2缺页:(null)-->31 2 3缺页:3--被替换为-->41 2 41 2 41 2 4缺页:4--被替换为-->51 2 51 2 51 2 5缺页:1--被替换为-->33 2 5缺页:3--被替换为-->44 2 54 2 5end!//////////////////////////////////////////////////////////////////////////先进先出算法:先进先出置换算法(first in first out,FIFO)是淘汰最先进⼊内存的页⾯,即选择在内存中驻留时间最长的页⾯进⾏淘汰的算法。