页面置换算法lfu算法

⑴ 页式管理的请求页式管理中的置换算法

功能：需要调入页面时，选择内存中哪个物理页面被置换。称为replacement policy。
出发点：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。
页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法为在页表中加上锁定标志位(lock bit)。 轮转法(RR,round robin)和先进先出算法(FIFO,first in first out):轮转法循回换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间。FIFO算法总是选择在内存驻留时间最长的一员将其淘汰。
FIFO算法认为先调入内存的页不再被访问的可能性要比其它页大，因而选择最先调入内存的页换出。实现FIFO算法需要把各个已分配页面按分配时间顺序链接起来，组成FIFO队列，并设置一置换指针指向FIFO队列的队首页面。这样，当要进行置换时，只需把置换指针所指的FIFO队列前头的页顺次换出，而把换入的页链接在FIFO队尾即可。
由实验和测试发现FIPO算法和RR算法的内存利用率不高。这是因为，这两种算法都是基于CPU按线性顺序访问地址空间这一假设。事实上，许多时候．CPU不是按线性顺序访问地址空间的。
Belady现象:一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。 最近最久未使用页面置换算法(LRU, Least Recently Used):
选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构如：
(1) 一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。
(2) 每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。
比较常用的近似算法有：
(a) 最不经常使用页面淘汰算法(LFU, Least Frequently Used)
(b) 最近没有使用页面淘汰(NRU, Not Recently Used) 理想型淘汰算法（OPT,Optimal Replacement Algorithm）
该算法淘汰在访问串中将来再也不出现的或是离当前最远的位置上出现的页。它是一种理想化的算法，性能最好，但在实际上难于实现。

⑵ 莫系统空闲分区如下表.哪种算法可满足该作业序列请求为什么

一、进程(作业)调度算法
l 先来先服务调度算法（FCFS）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。

l 短进程（作业）优先调度算法(SPF)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。

l 时间片轮转调度算法 ：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。

l 优先数调度算法 ：它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。

l 响应比高者优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。

l 多级队列调度算法

基本概念：

作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)

作业平均周转时间(T)＝周转时间/作业个数

作业带权周转时间（Wi）＝周转时间/运行时间

响应比＝（等待时间＋运行时间）/运行时间

二、存储器连续分配方式中分区分配算法
n 首次适应分配算法（FF）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。

n 循环首次适应算法：每次分配均从上次分配的位置之后开始查找。

n 最佳适应分配算法(BF)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。

三、页面置换算法
l 最佳置换算法（OPT) ：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

l 先进先出置换算法（FIFO）：选择最先进入内存的页面予以淘汰。

l 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。

l 最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。

四、磁盘调度
n 先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置

n 最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题

n 扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。

n 循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。

⑶ lru/lfu可以称为近似opt算法吗

LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!
LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!
比如,第二种方法的时期T为10分钟,如果每分钟进行一次调页,主存块为3,若所需页面走向为2 1 2 1 2 3 4
注意,当调页面4时会发生缺页中断
若按LRU算法,应换页面1(1页面最久未被使用) 但按LFU算法应换页面3(十分钟内,页面3只使用了一次)
可见LRU关键是看页面最后一次被使用到发生调度的时间长短,
而LFU关键是看一定时间段内页面被使用的频率!

⑷ 操作系统题：页面置换算法 OPT FIFO LRU

fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。

⑸ 请分别给出三种不同的页面置换算法,并简要说明他们的优缺点

[fifo.rar]
-
操作系统中内存页面的先进先出的替换算法fifo
[先进先出页面算法程序.rar]
-
分别实现最佳置换算法(optimal)、先进先出(fifo)页面置换算法和最近最久未使用（LRU）置换算法，并给出各算法缺页次数和缺页率。
[0022.rar]
-
模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断
[Change.rar]
-
用java实现操作系统的页面置换
其中包括
最佳置换算法(Optimal)、先进先出算法（First-in,
First-out）
、最近最久不用的页面置换算法（LeastRecently
Used
Replacement）三种算法的实现
[M_Management.rar]
-
操作系统中内存管理页面置换算法的模拟程序，采用的是LRU置换算法
[detail_of_44b0x_TCPIP.rar]
-
TCPIP
程序包加载到44b0x
的ADS1.2工程文件的说明书。说名了加载过程的细节和如何处理演示程序和代码。演示代码已经上传，大家可以搜索
[.rar]
-
java操作系统页面置换算法：
（1）进先出的算法（fifo）
（2）最近最少使用的算法（LRU）
（3）最佳淘汰算法(OPT)
（4）最少访问页面算法(LFU)
（注：由本人改成改进型Clock算法）
（5）最近最不经常使用算法(NUR)

⑹ 页面置换算法的常见的置换算法

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做， 不仅要查页表，而且当页表改变时（因CPU调度）要 维护这个页表中的时间，还要考虑到时钟值溢出的问题。
2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。
4）Clock置换算法（LRU算法的近似实现）
5）最少使用（LFU）置换算法
在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访 问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。
LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。
6）工作集算法
7）工作集时钟算法
8）老化算法（非常类似LRU的有效算法）
9）NRU(最近未使用）算法
10）第二次机会算法
第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是 0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。
第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个 存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

⑺ 实现虚拟存储器最常用的算法是哪个

页式虚拟存储器的页面置换算法一般有：
最佳置换算法（OPT），先进先出置换算法（FIFO），最近最久未使用置换算法（LRU），Clock置换算法，最少使用置换算法（LFU），页面缓存算法（PBA）等。
先进先出（FIFO）置换算法是最直观的置换算法，由于它可能是性能最差的算法，故实际应用极少。（摘录自汤的教材）

⑻ [求助]LFU页面置换算法

least frequently used (LFU)，要求在页置换时置换引用计数最小的页。
3，2，1
0进入时，缺页。置换最近最小的1。内存：3，2，0
3，2
4进入时，缺页。置换最近最小的0。内存：3，2，4
3，2
1进入时，缺页。置换最近最小的4。内存：3，2，1
0进入时，缺页。置换最近最小的1。内存：3，2，0
4进入时，缺页。置换最近最小的0。内存：3，2，4

⑼ 采用近期最少使用（LFU）算法仿真请求分页系统（C语言实现）

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