操作系统课程设计

要求

目的任务

基于Linux操作系统环境，设计页面替换算法，实现OPT、FIFO、LRU、Clock、改进Clock算法。理解各页面替换算法的原理及实现方法。

设计内容

（1）编程实现OPT算法、FIFO算法、LRU算法、简单时钟算法和改进时钟算法;

（2）编程实现页面访问序列的随机化机制，包括设置每个页面的读写访问方式，以满足改进时钟算法的要求。

（3）在进程执行和访问每一页的过程中，每一次对一页的访问都应显示输出当时进程页表的内容(包括页号、物理块号、状态位、读写访问方法等字段)和当前页访问操作(如该页已经在内存中或触发缺页中断);

（4）所有算法都应该基于相同的条件，包括:

系统采用“固定分配，局部替换”策略;

进程逻辑地址空间的大小相同;

分配给进程的物理块数目相同。

相同页面访问序列(整数序列，整数区间[0,N));

（5）进行多次测试，统计分析和比较算法的性能(如缺页率，缺页次数)

设计工作要求

（1）在实验报告中详细阐明实验目标、实验步骤、实验步骤的具体原理、关键核心代码、实验结果演示及说明和上机实践总结等。

（2）以完整的作业包的形式提交原始代码、可运行程序、课程设计报告。程序清单要求格式规范，注意加注释。报告压缩包命名：学号-姓名；

（3）提交截止日期：2024年12月31日。

设计过程

整体设计

根据要求，大概需要做一个输入一串进程涉及的页面序列之后，就能自动模拟生成整个进程的执行过程。

每次进行到一个新的页面，都要决定：当前是否缺页？如果缺页的话换哪页？当前内存中有哪些页面？

执行完后要统计出缺页数量、缺页率和替换次数这些指标，并要有直观的显示便于评价，来满足第5条任务。至于主存块的分配，我打算直接在确定了进程主存空间大小后随机指定相同数量的块号，毕竟这不是这次课设的重点，我要把精力放在军事上面。

界面设计

主界面的最终设计如下：

可以看出其中已经实现了要求中说的所有功能。为了尽量做得完整，还有两个子页面，分别是使用方法和显示分析图，这两个不需要什么设计，只需显示写死的内容即可：

使用方法页面

分析图页面

算法设计

共性说明

在所有的页面替换算法中，有很多变量与逻辑等是相同的，在此做统一说明，之后只细说最最核心的算法设计。

为了方便后续集成，我把所有的算法都封装成类（以OPT为例）：

class OPT(object):
    MissingPageFlag = True  # 是否缺页
    MissingPageCount = 0  # 缺页次数
    TotalPages = 0  # 序列中总的页面数
    theMostUnusedPage = 0  # inputSequence[theMostUnusedPage]是最久不用的页面
    forReplacement = 0  # 要被置换的位置是pagesInMainMemory[forReplacement]
    wint = True
    def __init__(self, inputSequence, memoryBlockNumber):
        self.memoryBlockNumber = memoryBlockNumber
        self.inputSequence = inputSequence
        self.pageSequenceTable = []
        self.pagesInMainMemory = []
        self.outputSequence = ""
        self.mutex = True
        self.err = False
    def getinfo(self):
        # 预处理函数
        try:
            self.pageSequenceTable = self.inputSequence.split(' ')
            # 空格隔开输入序列
            self.memoryBlockNumber = int(self.memoryBlockNumber)
            self.TotalPages = len(self.pageSequenceTable)
            if self.memoryBlockNumber < 1:
                raise ValueError
            self.outputSequence += f'Memory block allocated: {randomBlock.randomBlock(self.memoryBlockNumber)}\n'  # 分配主存块号
            for j in range(len(self.pageSequenceTable)):
                self.pageSequenceTable[j] = int(self.pageSequenceTable[j])
        except TypeError and ValueError:
            self.err = True
    def compute:
        # 这里写具体逻辑
        return self.outputSequence, int(self.MissingPageCount), float(
            self.MissingPageCount / self.TotalPages * 100), int(self.MissingPageCount - self.memoryBlockNumber) 
        # 返回四个值，分别是一个字符串，表示整个处理过程；缺页次数、缺页率、置换次数

在之后在外部调用时，只需用这些参数来初始化这个类：

inputSeq = "1 2 3 4 5 6 7 8 9 3 4 7 5 4 6 7"
OPTr0, OPTr1, OPTr2, OPTr3 = target = OPT(inputSeq, 5).compute()

这样就能获得特定算法输出的四个结果。

在输出时，把所有的过程输出都先放在一个字符串outputSequence内最后整体追加在输出区，例如：

self.outputSequence += str(
    'The number of missing pages is %d, the missing page rate is %f%%, and the number of page replacements is %d\n\n' % (
    self.MissingPageCount, self.MissingPageCount / self.TotalPages * 100,
    self.MissingPageCount - self.memoryBlockNumber))

OPT

OPT，Optimal Page Replacement，最佳页面替换算法，是一种基于全局信息做出决策的页面替换算法，每次选择未来最长时间不再被访问的页面进行替换，可以达到最低的缺页率。

把所有页面依次放入空间，若有空空间则直接放入，没有空空间则“向未来看”，寻找已经存入的页面哪一个最久没有被使用，将他替换。不断重复上面的步骤，直到完成所有页面的替换。

也就是说只有三种情况：

1、不缺页，跳过

2、缺页但无需替换

if self.pageSequenceTable[i] not in self.pagesInMainMemory:
    self.MissingPageFlag = True
    if len(self.pagesInMainMemory) < self.memoryBlockNumber:
        self.pagesInMainMemory[len(self.pagesInMainMemory)::] = [
            self.pageSequenceTable[i]]

此时只需把这一页加到内存，也就是在pagesInMainMemory后边加上一个页号。

3、缺页且需要替换

for t in range(self.memoryBlockNumber):  # 剩余页面列表中没有出现的序号优先替换
    if self.pagesInMainMemory[t] not in self.pageSequenceTable[i:self.TotalPages]:
        self.forReplacement = t
        self.wint = False
        break  # 如果没有再也不出现的，就换最后一个

替换最后一个页面的代码（可以保证最后有得换）：

for t in range(self.memoryBlockNumber):  # 寻找剩余页面列表中最后出现的序号并替换
    self.mutex = True
    for y in range(i, len(self.pageSequenceTable)):
        if self.pagesInMainMemory[t] == self.pageSequenceTable[y]:
            self.mutex = False
            if y > self.theMostUnusedPage:
                self.theMostUnusedPage = y
                self.forReplacement = t
                break  # 找到首次出现的序列号就结束循环
            else:
                break  # 若没有则继续下个循环
        if not self.mutex:
            break

每一轮循环都输出一次缺页信息：

if self.MissingPageFlag is True:
    self.outputSequence += str("Page is missing" + str(self.pagesInMainMemory) + '\n')
else:
    self.outputSequence += str("No pages missing" + str(self.pagesInMainMemory) + '\n')

FIFO

FIFO，First In First Out，先入先出算法，是最简单的页面替换策略，它按照页面进入内存的顺序来决定替换哪个页面。即优先淘汰最早进入内存的页面，不论这些页面之后是否被频繁访问。但是FIFO可能会导致“Belady异常”，即随着分配给进程的物理块数增加，缺页次数反而增加。

这应该是这5种算法里最好实现的，构造一个队列即可：

如果没满，就在尾部追加：

self.pagesInMainMemory[len(self.pagesInMainMemory)::] = [self.pageSequenceTable[i]]

如果到了，就加在头部并把后边的后移一位剩下的删了：

self.pagesInMainMemory[0:len(self.pagesInMainMemory) - 1:] = self.pagesInMainMemory[1:len(self.pagesInMainMemory):]
self.pagesInMainMemory[len(self.pagesInMainMemory) - 1] = self.pageSequenceTable[i]

同样是每一次大循环结束就输出一轮信息，之后的算法都是如此。

LRU

LRU，Least Recently Used，最近最少使用算法，如果一个数据最近被访问过，那么将来被访问的可能性也较大。因此，它选择最近最长时间未被访问的页面进行替换。LRU的性能和效率接近OPT，但是对于频繁访问的页面更新开销较大。

怎么表示“最长时间未被访问”呢？也按队列来，只是这次每一轮访问之后队内顺序会有调整，把被访问的一页放到队头，无论是否缺页。

缺页：

if len(pagesInMainMemory) < self.memoryBlockNumber:
    pagesInMainMemory[len(pagesInMainMemory)::] = [i]
else:
    pagesInMainMemory[0:self.memoryBlockNumber - 1:] = pagesInMainMemory[1:self.memoryBlockNumber:]  # 队列整体后移
    pagesInMainMemory[self.memoryBlockNumber - 1::] = [i]  # 添加新元素
MissingPageCount += 1

不缺页：

pageMissingFlag = False
pagesInMainMemory[pagesInMainMemory.index(i):len(pagesInMainMemory) - 1:] = pagesInMainMemory[pagesInMainMemory.index(i) + 1::]
# 把新页加到队头
pagesInMainMemory[len(pagesInMainMemory) - 1::] = [i]

CLOCK

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，NotRecently Used） 简单的CLOCK 算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。

当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。

如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）

简单理解其实就是，每一页有两次机会，你第一轮没被访问没关系，只是访问位先变成0，只有下一轮开扫的时候你前边没0了，才会被换掉。

在每一轮大循环中，都要检查访问位，如果不缺页就全部置1，下一轮众生平等：

if i in pagesInMainMemory:
    use_bit[pagesInMainMemory.index(i)] = 1
    self.outputSequence += str("No pages missing" + str(pagesInMainMemory) + '\n')

如果缺页了，就先扫一轮按要求设置访问位：

while use_bit[pointer] == 1:  # 如果访问位为1，跳过此页
    use_bit[pointer] = 0  # 重置访问位
    pointer = (pointer + 1) % self.memoryBlockNumber

由于是循环队列，所以移动修改指针时要取余。

之后替换，此时会替换指针指的位置。而指针指在哪呢？它会停在最后一个访问位为1的下一位，也就是第一个0那里，很完美。

pagesInMainMemory[pointer] = i
use_bit[pointer] = 1
pointer = (pointer + 1) % self.memoryBlockNumber
MissingPageCount += 1

Enhanced CLOCK

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。

修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。 为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过。

每一页的修改位固定。

替换规则是：

第一轮找0,0，有就淘汰没就下一轮；

第二轮找0,1，扫到的访问位置0；

第三轮第四轮和前两轮差不多，只是不再修改任何位。

开始时都初始化为0，修改位让用户输入：

use_bit = [0] * self.memoryBlockNumber
modify_bit = [0] * self.memoryBlockNumber

如果不缺页，不用动

idx_in_yeBiao = pagesInMainMemory.index(i)
use_bit[idx_in_yeBiao] = 1
modify_bit[idx_in_yeBiao] = mod_bits_list[idx]
outputSequence += str(f"No pages missing: {pagesInMainMemory} | Use bits: {use_bit} | Mod bits: {modify_bit}\n")

缺页，开启扫描：

优先找全0位：

if use_bit[pointer] == 0 and modify_bit[pointer] == 0:
    pagesInMainMemory[pointer] = i
    use_bit[pointer] = 1  # 设置访问位
    modify_bit[pointer] = mod_bits_list[idx]  # 设置修改位
    pointer = (pointer + 1) % self.memoryBlockNumber
    replaced = True

找不到全0找01：

pagesInMainMemory[pointer] = i
use_bit[pointer] = 1  # 设置访问位
modify_bit[pointer] = mod_bits_list[idx]  # 更新修改位
pointer = (pointer + 1) % self.memoryBlockNumber
replaced = True

全1，和01一样重置访问位：

use_bit[pointer] = 0
pointer = (pointer + 1) % self.memoryBlockNumber

算法集成

Thanks to my object-oriented design，在槽函数中只需从界面获取数据并初始化一个类即可，以改进型CLOCK为例：

def enhancedClockProcess(self):
    print(self.getFromSequenceInput())
    seq = self.getFromSequenceInput()
    modi = self.getFromModifyBits()
    memblock = self.getFromMemoryNumberInput()
    r0, r1, r2, r3 = EnhancedCLOCK(seq, memblock, modi).compute()
    self.writeOnResult(r0)

在画图时，只需把15个数据传入画图模块画出柱状图即可：

data = {
    'Page Missing': [OPTr1, FIFOr1, LRUr1, CLOCKr1, EnCLOCKr1],
    'Misssing Rate': [OPTr2, FIFOr2, LRUr2, CLOCKr2, EnCLOCKr2],
    'Replacements': [OPTr3, FIFOr3, LRUr3, CLOCKr3, EnCLOCKr3]
}

测试

在测试时我遇到点小问题，就是没法生成合适的数据。chatgpt生成的访问序列悬殊太大，让它生成100个1-10之间的页面和修改位，给6块主存，缺页率直接来到100%：

我懒得自己写概率模型去生成，所以干脆多给点空间，尽量让缺页率合理一点：

毕竟要写实验报告，确定算法没写错的话报告里得有一张稍微不那么离谱的图。

经过调整，用一段长度为5000,1-11范围内生成的数据得到如下性能排序：

打包

打包还是用pyinstaller，但是要在linux下编译，我前几天刚把虚拟机删了，我是不可能为了这么个破事把那玩意下载一遍的，所以我决定直接咸鱼找一个代打包算了（

总结与思考

算法简介如下：

对性能预测与实验结果基本符合。

个人总结

其实如果时间足够，应该在真实系统环境下去模拟，做几个真正的页出来让系统去执行。但是最近实在没时间，我本来打算一天内结束这件事，但到我写完这篇文章已经有两整天了。

总之完成得不错，秉承着能用gpt就用gpt的原则，我其实只需要调优并debug就好了……

最后为实验报告写个官方心得体会：

在本次操作系统实验中，我通过编写一个页面替换算法的模拟程序，深入理解了不同页面替换算法（如OPT、FIFO、LRU、CLOCK、Enhanced CLOCK）在实际运行中的表现差异。通过实验，我不仅掌握了这些算法的具体实现过程，还对它们的优缺点有了更直观的认识。

通过绘制性能比较图，我能够清楚地观察到各个算法在缺页次数、缺页率、以及页面替换次数等方面的表现差异。比如，OPT算法理论上表现最优，但由于实际系统中难以实现，FIFO和LRU则作为常用替代算法。而CLOCK和Enhanced CLOCK在性能上有所折中，在一定程度上优化了算法效率。

实验加深了我对页面置换策略在操作系统内存管理中的重要性的理解，也让我意识到，不同算法在不同场景中的适用性并不相同，具体的选择需要权衡效率和实现复杂性。

结束！