目录
页面置换算法是虚拟内存管理中的重要技术，当内存空间不足时，操作系统需要选择合适的页进行换出，以腾出空间。commonly used 的页面置换算法包括最佳页面置换算法、先进先出页面置换算法、最近最久未使用置换算法和 clock 页面置换算法等。
最佳页面置换算法和先进先出页面置换算法
最佳页面置换算法（OPT）
最佳页面置换算法（Optimal Page Replacement Algorithm，简称OPT）是一种理论上最优的页面置换策略。它选择被淘汰的页面将是以后永不使用，或者是在最长时间内不再被访问的页面，从而保证最低的缺页率。
OPT的基本思想
- 目标：最小化缺页率。
- 过程：每次发生缺页中断时，从内存中的页面中挑出一个在未来最长时间内不再被访问的页面进行替换。
- 优点：理论上提供了最低的缺页率，作为衡量其他页面置换算法的基准。
实现方式及局限性
由于OPT算法需要知道进程未来的页面访问模式，这在实际操作中是不可行的，因此OPT算法仅作为理论参考，无法在实际系统中实现。
伪代码示例:
function optimalPageReplacement(pageTable, futureRequests) {
longestTime = -1;
pageToReplace = null;
for each page in pageTable {
time = findNextUseTime(page, futureRequests);
if time > longestTime {
longestTime = time;
pageToReplace = page;
}
}
return pageToReplace;
}
function findNextUseTime(page, futureRequests) {
for i = 0 to length of futureRequests - 1 {
if futureRequests[i] == page {
return i;
}
}
return Infinity;
}
function handlePageFault_OPT(pageTable, newPage, futureRequests) {
pageToReplace = optimalPageReplacement(pageTable, futureRequests);
evictPage(pageToReplace);
loadPage(newPage, pageToReplace.frame);
}
先进先出页面置换算法（FIFO）
先进先出页面置换算法（FIFO）是一种简单的页面置换算法，每次选择淘汰的页面是最早进入内存的页面。该算法实现简单，只需把调入内存的页面根据先后次序排列成队列。以下是对FIFO算法的详细描述及其优缺点：
工作原理
- 队列结构：使用一个队列来记录页面进入内存的顺序。
- 页面调入：当一个新的页面需要调入内存时，将其加入队列的尾部。
- 页面置换：当内存已满且需要调入新的页面时，移除队列头部的页面（即最早进入内存的页面），然后将新的页面加入队列的尾部。
示例
假设内存可以容纳3个页面，页面访问序列为：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
- 初始状态：内存为空。
- 访问页面7：内存：[7]，队列：[7]
- 访问页面0：内存：[7, 0]，队列：[7, 0]
- 访问页面1：内存：[7, 0, 1]，队列：[7, 0, 1]
- 访问页面2：页面置换，移除页面7，内存：[0, 1, 2]，队列：[0, 1, 2]
- 访问页面0：页面已在内存中，无需置换。
- 访问页面3：页面置换，移除页面0，内存：[1, 2, 3]，队列：[1, 2, 3]
- 访问页面0：页面置换，移除页面1，内存：[2, 3, 0]，队列：[2, 3, 0]
- 访问页面4：页面置换，移除页面2，内存：[3, 0, 4]，队列：[3, 0, 4]
- 访问页面2：页面置换，移除页面3，内存：[0, 4, 2]，队列：[0, 4, 2]
- 访问页面3：页面置换，移除页面0，内存：[4, 2, 3]，队列：[4, 2, 3]
- 访问页面0：页面置换，移除页面4，内存：[2, 3, 0]，队列：[2, 3, 0]
- 访问页面3：页面已在内存中，无需置换。
- 访问页面2：页面已在内存中，无需置换。
优点
- 实现简单：FIFO算法的实现非常简单，只需维护一个队列即可。
- 开销低：由于不需要复杂的计算和比较，FIFO算法的开销较低。
缺点
- 不适应实际运行规律：FIFO算法不考虑页面的访问频率和时间局部性，可能会导致经常被访问的页面也被淘汰，从而增加缺页中断的次数。
- Belady现象：在某些情况下，增加内存的页面数反而会增加缺页中断的次数，这种现象被称为Belady现象。
代码示例
以下是一个使用FIFO页面置换算法的简化示例代码：
from collections import deque
def fifo_page_replacement(pages, capacity):
memory = set()
queue = deque()
page_faults = 0
for page in pages:
if page not in memory:
if len(memory) == capacity:
oldest_page = queue.popleft()
memory.remove(oldest_page)
memory.add(page)
queue.append(page)
page_faults += 1
print(f"Memory: {list(memory)}, Queue: {list(queue)}")
return page_faults
# 示例页面访问序列和内存容量
pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
capacity = 3
faults = fifo_page_replacement(pages, capacity)
print(f"Total page faults: {faults}")
最近最久未使用置换算法和最少使用页面置换算法
最近最久未使用置换算法（LRU）
最近最久未使用置换算法（LRU）是一种页面置换算法，用于在内存管理中确定需要淘汰的页面。LRU算法的核心思想是淘汰最近最久未被使用的页面。具体步骤如下：
-
访问字段：为每个页面设置一个访问字段，记录该页面自上次被访问以来的时间。可以将此字段理解为一个时间戳或者计数器，每次访问该页面时更新其值。
-
页面访问：当一个页面被访问时，更新该页面的访问字段，以表示该页面最近被使用了。
-
页面淘汰：当需要为新页面腾出空间时，LRU算法选择访问字段值最大的页面进行淘汰，即选择最近最久未被使用的页面。这个页面被认为是最不可能在不久的将来被再次访问的，因此是最合适的淘汰目标。
优缺点分析
优点
-
性能较好：LRU算法利用页面的访问历史来进行页面置换，因此在很多实际应用中性能较好。它能够较好地模拟程序的局部性原理，即程序在一段时间内访问的页面往往集中在某些特定区域。
-
简单直观：LRU的思想简单，容易理解。它基于最近最久未使用的策略，符合直觉。
缺点
-
实现复杂：LRU算法需要为每个页面维护一个访问字段，这在实现上较为复杂。每次访问页面时都需要更新访问字段，这增加了系统的开销。
-
硬件支持：实现LRU算法通常需要额外的硬件支持，例如寄存器和栈，以记录和更新页面的使用时间。这增加了硬件设计的复杂度。
-
开销大：维护和更新访问字段需要额外的存储和计算资源。这对系统的性能有一定影响，尤其是在页面频繁访问的情况下。
实现方式
硬件实现
一种硬件实现LRU的方法是使用栈结构。每当一个页面被访问时，将其移到栈顶。当需要淘汰页面时，直接选择栈底的页面，因为它是最近最久未被访问的页面。这种方法需要特定的硬件支持，例如快速的栈操作。
软件实现
在软件实现中，可以使用链表或数组来维护页面的访问时间。例如，可以使用一个链表，每次页面访问时将其移到链表头部，当需要淘汰页面时选择链表尾部的页面。另一种方法是使用一个数组，记录每个页面的时间戳，每次访问页面时更新其时间戳，当需要淘汰页面时选择时间戳最小的页面。
示例
假设内存中有三个页面框架，访问序列为：1, 2, 3, 1, 4, 2, 5。
-
访问页面1：内存中没有页面1，将其加载到内存中。
- 内存状态：[1]
-
访问页面2：内存中没有页面2，将其加载到内存中。
- 内存状态：[1, 2]
-
访问页面3：内存中没有页面3，将其加载到内存中。
- 内存状态：[1, 2, 3]
-
访问页面1：页面1已经在内存中，更新其访问时间。
- 内存状态：[1, 2, 3]
-
访问页面4：内存中没有页面4，选择最近最久未使用的页面进行淘汰（页面2），将页面4加载到内存中。
- 内存状态：[1, 4, 3]
-
访问页面2：内存中没有页面2，选择最近最久未使用的页面进行淘汰（页面3），将页面2加载到内存中。
- 内存状态：[1, 4, 2]
-
访问页面5：内存中没有页面5，选择最近最久未使用的页面进行淘汰（页面1），将页面5加载到内存中。
- 内存状态：[5, 4, 2]
通过以上例子可以看到，LRU算法在每次页面访问时都需要更新访问时间，并在需要淘汰页面时选择最久未使用的页面进行替换。
最少使用页面置换算法（LFU）
最少使用页面置换算法（LFU, Least Frequently Used）选择在最近时期使用最少的页面进行淘汰。LFU算法通过为每个页面设置一个计数器，记录该页被访问的频率，当需要置换页面时，选择访问频率最小的页面。这个算法本质上是一个top-K问题，可以通过优先队列（如二项堆或最小堆）来高效实现。
LFU算法的基本思想
- 目标：选择最近时期使用频率最少的页面进行置换。
- 过程：每次访问页面时，增加其计数器值；当需要淘汰页面时，选择计数器值最小的页面进行置换。
实现方式
使用优先队列（如二项堆或最小堆）来实现高效选择频率最小的元素。
-
数据结构：
- 计数器：记录每个页面的访问次数。
- 优先队列（最小堆）：用于快速查找和移除计数器值最小的页面。
-
操作步骤：
- 页面访问：每次访问页面时，更新其计数器值，并调整优先队列。
- 缺页处理：当发生缺页中断时，从优先队列中移除计数器值最小的页面，并将新页面加入内存和优先队列。
LFU 算法的伪代码
伪代码示例:
initialize minHeap as empty priority queue;
initialize pageTable as empty dictionary;
function accessPage(pageId) {
if pageId is in pageTable:
pageTable[pageId].accessCount += 1;
minHeap.update(pageTable[pageId]);
else:
handlePageFault(pageId);
}
function handlePageFault(pageId) {
if memory is full:
victimPage = minHeap.extractMin();
evictPage(victimPage.id);
pageTable.remove(victimPage.id);
newPage = loadPage(pageId);
pageTable[pageId] = newPage;
minHeap.insert(newPage);
}
function evictPage(pageId) {
// Evict the page from memory
}
function loadPage(pageId) {
page = Page(pageId);
page.accessCount = 1;
// Load the page into memory
return page;
}
LFU 算法的特点
-
优点：
- 减少频繁访问页面的置换：通过记录访问频率，避免将经常访问的页面置换出去，从而减少缺页中断。
- 适合特定访问模式：对于访问频率较稳定的应用，LFU 能够较好地优化页面置换。
-
缺点：
- 计数器溢出：需要处理计数器可能溢出的情况，可以在一定时间间隔内重置或衰减计数器值。
- 复杂性：维护计数器和二项堆的开销较大，尤其在频繁访问和置换页面时。
- 不适应某些访问模式：对于访问模式变化频繁的应用，LFU 的效果可能不如 LRU。
Clock 页面置换算法
Clock 页面置换算法是一种性能和开销较均衡的页面置换算法，也被称为最近未用（Not Recently Used, NRU）算法。Clock 算法通过维护一个循环队列和访问位来决定页面置换的策略。以下是对Clock算法的详细描述及其优缺点：
工作原理
- 循环队列：将内存中的页面通过链接指针链接成一个循环队列，类似于时钟的指针。
- 访问位（Reference Bit）：为每个页面设置一个访问位，初始值为0。当页面被访问时，将其访问位置设为1。
- 页面置换：
- 当需要淘汰页面时，从时钟指针所指的页面开始扫描，选择访问位为0的页面进行换出。
- 如果扫描一圈后发现所有页的访问位均为1，则将访问位依次置为0，并进行第二轮扫描。
改进措施
- 考虑页面修改位：引入修改位（Dirty Bit），优先淘汰没有被修改的页面，避免写回磁盘的I/O操作。
- 增加访问位数目：通过增加访问位的数目，可以更精细地记录页面的使用历史，从而提高置换决策的准确性。
示例
假设内存可以容纳3个页面，页面访问序列为：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
- 初始状态：内存为空，时钟指针指向第一个槽位。
- 访问页面7：调入内存，访问位设为1，内存：[7]，访问位：[1]，指针指向下一个槽位。
- 访问页面0：调入内存，访问位设为1，内存：[7, 0]，访问位：[1, 1]，指针指向下一个槽位。
- 访问页面1：调入内存，访问位设为1，内存：[7, 0, 1]，访问位：[1, 1, 1]，指针指向第一个槽位。
- 访问页面2：指针指向的页面访问位为1，将其设为0并移动指针，内存：[7, 0, 1]，访问位：[0, 1, 1]，指针指向下一个槽位。
- 继续访问页面2：指针指向的页面访问位为1，将其设为0并移动指针，内存：[7, 0, 1]，访问位：[0, 0, 1]，指针指向下一个槽位。
- 继续访问页面2：指针指向的页面访问位为1，将其设为0并移动指针，内存：[7, 0, 1]，访问位：[0, 0, 0]，指针指向第一个槽位。
- 继续访问页面2：指针指向的页面访问位为0，淘汰该页面并调入页面2，内存：[2, 0, 1]，访问位：[1, 0, 0]，指针指向下一个槽位。
以此类推，按照上述流程继续处理后续的页面访问。
代码示例
以下是一个使用Clock页面置换算法的简化示例代码：
class Page:
def __init__(self, number):
self.number = number
self.reference_bit = 0
def clock_page_replacement(pages, capacity):
memory = []
pointer = 0
page_faults = 0
for page_number in pages:
found_in_memory = False
for page in memory:
if page.number == page_number:
page.reference_bit = 1
found_in_memory = True
break
if not found_in_memory:
if len(memory) < capacity:
memory.append(Page(page_number))
else:
while memory[pointer].reference_bit == 1:
memory[pointer].reference_bit = 0
pointer = (pointer + 1) % capacity
memory[pointer] = Page(page_number)
pointer = (pointer + 1) % capacity
page_faults += 1
print(f"Memory: {[page.number for page in memory]}, Pointer: {pointer}")
return page_faults
# 示例页面访问序列和内存容量
pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
capacity = 3
faults = clock_page_replacement(pages, capacity)
print(f"Total page faults: {faults}")代码解释
- Page类：表示一个内存页面，包含页面号和访问位。
- clock_page_replacement函数：实现Clock页面置换算法。
- memory：表示当前在内存中的页面列表。
- pointer：指向当前时钟指针的位置。
- page_faults：记录缺页次数。
- for循环：遍历页面访问序列。
- found_in_memory：检查页面是否已在内存中。
- 内存未满时，直接将页面调入内存。
- 内存已满时，循环检查页面的访问位，找到访问位为0的页面进行置换。
页面缓冲算法（PBA）
页面缓冲算法（Page Buffering Algorithm，PBA）是Linux系统中常用的一种页面置换算法。当需要置换页面时，PBA采用FIFO（先进先出）策略，从所有已分配页面中选择最先进入的页面进行淘汰。
工作原理
-
FIFO页面选择：当需要淘汰某个页面时，PBA会选择在物理内存中存在时间最长的页面，即最早进入内存的页面。这种选择策略简单且易于实现。
-
链表管理：PBA将淘汰的页面放入两个链表之一：
- 空闲链表：如果页面未被修改，则直接放入空闲链表中，表示该页面可以立刻被回收和重新利用。
- 已修改页面链表：如果页面已被修改（即脏页面），则放入已修改页面链表中，以便稍后将其写回到磁盘。
这种链表管理方式有助于区分未修改和已修改的页面，从而优化页面回收和写回的过程。
-
模拟固定数量空闲物理块：通过将淘汰的页面放入空闲链表，PBA模拟了一定数量的空闲物理块的存在。这种模拟使得页面置换过程变得更加灵活和高效。
优缺点分析
优点
-
实现简单：PBA采用FIFO策略选择淘汰页面，同时利用链表管理页面状态，算法结构简单，易于实现和维护。
-
管理灵活：通过将页面分为未修改和已修改两类，并分别管理，有助于优化页面回收和写回过程，提高系统的整体性能。
缺点
-
频繁缺页中断：由于PBA采用FIFO策略，选择最早进入内存的页面淘汰，可能会导致频繁的缺页中断，尤其是在访问模式呈现一定局部性时，这种缺点尤为明显。
-
不考虑访问历史：PBA不考虑页面的访问历史和频率，只根据页面进入内存的时间进行选择，可能会淘汰掉仍被频繁访问的重要页面，导致性能下降。
示例
假设内存中有三个页面框架，访问序列为：A, B, C, A, D, B, E。
-
访问页面A：内存中没有页面A，将其加载到内存中。
- 内存状态：[A]
-
访问页面B：内存中没有页面B，将其加载到内存中。
- 内存状态：[A, B]
-
访问页面C：内存中没有页面C，将其加载到内存中。
- 内存状态：[A, B, C]
-
访问页面A：页面A已经在内存中，继续访问。
- 内存状态：[A, B, C]
-
访问页面D：内存中没有页面D，采用FIFO策略，选择最早进入的页面A进行淘汰。
- 内存状态：[D, B, C]
-
访问页面B：页面B已经在内存中，继续访问。
- 内存状态：[D, B, C]
-
访问页面E：内存中没有页面E，采用FIFO策略，选择最早进入的页面B进行淘汰。
- 内存状态：[D, E, C]
请求分页系统的内存有效访问时间
在请求分页系统中，为了计算内存的有效访问时间（Effective Memory Access Time, EMAT），需要考虑访问页表和内存的时间。通过引入块表（block table）可以减少页表的搜索时间，从而提高系统的整体性能。
有效访问时间的计算公式
有效访问时间的计算公式为：
EMAT=查找块表时间+查找页表时间+访问内存时间
其中：
- 查找块表时间：时间依赖于块表的结构和哈希函数的性能。
- 查找页表时间：时间依赖于页表项的数量以及页表查找的效率。
- 访问内存时间：访问物理内存需要的时间，通常是一个固定值。
如何减少查找时间
-
块表的设计和哈希函数：
- 块表（Block Table）是用于快速定位页表项的辅助数据结构，通过适当的哈希函数可以显著减少查找时间。
- 哈希函数的设计要确保散列均匀，减少冲突，从而提高查找效率。
-
多级页表：
- 多级页表将页表分层，减少每层页表的大小，从而提高查找效率。
- 每一级的查找时间相加构成总的页表查找时间。
-
TLB（Translation Lookaside Buffer）：
- TLB 是一种高速缓存，用于存储最近使用的页表项，能够大大减少查找时间。
- TLB 命中率越高，查找页表时间越少。
示例计算
假设一个系统的各项时间参数如下：
- 查找块表时间：10ns
- 查找一级页表时间：20ns
- 查找二级页表时间：15ns
- 访问内存时间：100ns
若系统采用两级页表和块表，且没有TLB，那么其有效访问时间为：
EMAT=查找块表时间查找+一级页表时间+查找二级页表时间+访问内存时间
代入具体数值：
EMAT=10ns+20ns+15ns+100ns+145ns
优化策略
-
优化哈希函数：
- 选择适当的哈希函数，确保哈希冲突最小化，提升块表查找效率。
-
增加TLB命中率：
- 增加TLB缓存的大小和优化TLB替换策略，提升命中率，大幅减少查找页表时间。
-
减少页表级数：
- 尽可能减少页表级数，例如采用多级页表时，设计合理的页表大小和分层方式，降低每级页表的查找时间。
-
内存访问的并行化：
- 采用并行化技术，使得在查找页表的同时预取数据，减少总的内存访问时间。
通过这些措施可以有效地减少查找时间，优化内存访问效率，进一步提高系统性能。
结语
页面置换算法是虚拟内存管理中的重要技术，commonly used 的算法包括 OPT、FIFO、LRU、LFU 和 Clock 算法等。最佳页面置换算法虽然理论上最优，但无法实现。FIFO 算法实现简单，但性能差。LRU 和 Clock 算法性能较好，但实现困难且开销大。页面缓冲算法适用于 Linux 系统，模拟了固定数量的空闲物理块。了解 commonly used 的页面置换算法，有助于我们选择合适的算法，提高虚拟内存的管理效率。
标签：置换,访问,算法,内存,page,页面 From： https://blog.csdn.net/JAZJD/article/details/139567652