操作系统原理——虚拟存储管理实验

本文最后更新于：2022年5月23日 凌晨

本文章用到的语言：Python

前言

前排提个醒，这个程序我觉得自己写得挺复杂的（因为我懒癌犯了，没有想着优化，也没有想着跟题目走），so大家看看就好。

原理

老样子照搬：

突然发现这次没得搬的我be like： :(

实现

一些一些一些全局变量

1
2
3
4
5
6
7
input_queue = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1, ]  # 输入队列
a_queue = []  # 保存用于打印的结果
b_queue = []  # 同上
c_queue = []  # 同上
interrupt_queue = []  # 中断队列，保存发生中断时候的位置
page_queue = []  # 保存页表类对象的队列
ram_queue = []  # 虚拟内存队列

（小声：其实我会很大程度写出这样的程序是题目要求的输出的问题，真的

一直到最后都没什么用的页表类

1
2
3
4
5
6
class PageList:
    """页表类"""

    def __init__(self, status, quote):
        self.status = status  # 状态
        self.quote = quote  # 引用位

真的没用。真的没用。真的没用。直接往下看吧。我用数组下标完成工作的。

获取输入、打印结果、重置各队列

获取输入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def input_data():
    """获取用户输入来选择算法"""
    while True:
        algorithm = input("请选择一个算法：A、最佳置换；B、先进先出置换；C、最近最少用置换；D、退出")
        if algorithm == 'A':
            opt()
        elif algorithm == 'B':
            fifo()
        elif algorithm == 'C':
            lru()
        else:
            print("程序退出！")
            break
        reset_page()

打印结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def print_result():
    """打印各个队列"""
    global input_queue, a_queue, b_queue, c_queue, interrupt_queue
    for i in input_queue:
        print(f"{i}".center(3), end='')
    print()
    print("".center(60, '-'))
    for i in a_queue:
        print(f"{i}".center(3, '|'), end='')
    print()
    print("".center(60, '-'))
    for i in b_queue:
        print(f"{i}".center(3, '|'), end='')
    print()
    print("".center(60, '-'))
    for i in c_queue:
        print(f"{i}".center(3, '|'), end='')
    print()
    print("".center(60, '-'))
    for i in interrupt_queue:
        print(f"{i}".center(3, '|'), end='')
    print()
    print(f"该算法一共发生了{interrupt_queue.count('+')}页面置换，缺页中断率为{interrupt_queue.count('+')*100/len(input_queue)}%")
    print()
    return

重置各队列：

1
2
3
4
5
6
7
8
9
10
11
def reset_page():
    """重置页表状态"""
    global a_queue, b_queue, c_queue, interrupt_queue, ram_queue
    for page in page_queue:
        page.status = 0
        page.quote = 0
    a_queue = []
    b_queue = []
    c_queue = []
    interrupt_queue = []
    ram_queue = []

最优置换算法

最优是我想了最久的，毕竟其他两个确实不难，这里仔细划分每种情况就清晰多了。
首先是虚拟内存当前是否满的情况，这里要注意在虚拟内存未满的时候产生缺页中断是插入队尾而不是队头（就这个OPT是这样），其实虚拟内存未满的情况下还需要考虑是否产生缺页中断，我这里写的是没有考虑的。
然后是虚拟内存满了后，产生缺页中断和不产生缺页中断的情况。不产生缺页中断就不需要对虚拟内存进行操作了。
产生缺页中断后，我首先找剩下不需要再调用的页面，这部分页面的优先级是最大的，当然这是在有python列表方法的情况下这么写简单，直接找最迟访问也行。如果都还要访问那就找最迟访问的页面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def opt():
    """to do"""
    global input_queue, a_queue, b_queue, c_queue, interrupt_queue, page_queue, ram_queue
    for index in range(len(input_queue)):  # 遍历整个序列
        if len(ram_queue) == 3:
            if input_queue[index] in ram_queue:  # 当前虚拟内存中有该页，不产生缺页中断，也不需要改变虚拟内存中的页表
                a_queue.append(ram_queue[0])  # 保存用于打印的结果
                b_queue.append(ram_queue[1])
                c_queue.append(ram_queue[2])
                interrupt_queue.append(' ')  # 未产生缺页中断，所以塞个' '进去
                continue  # 继续下次循环
            else:  # 虚拟内存满的情况下，调用对应页面置换算法置换页面
                find = 0
                for exchange_index in range(len(ram_queue)):  # 找出需要置换的页面在虚拟内存队列中的下标
                    if ram_queue[exchange_index] not in input_queue[index + 1:]:  # 如果在剩下的序列中都找不到该页，可以直接换出去
                        find = 1  # 标记是否找到了置换页面
                        exchange_page = ram_queue[exchange_index]
                        break
                if find == 0:  # 三个页在剩下的序列中还有访问
                    tmp_queue = input_queue[index + 1:]
                    max_index = 0
                    exchange_page = 0
                    for tmp_index in range(len(ram_queue)):  # 找出最迟访问的页
                        new_index = tmp_queue.index(ram_queue[tmp_index])
                        if max_index < new_index:
                            max_index = new_index
                            exchange_page = ram_queue[tmp_index]
                for tmp_index in range(len(ram_queue)):
                    if exchange_page == ram_queue[tmp_index]:  # 进行页面置换
                        ram_queue[tmp_index] = input_queue[index]
                        break
                a_queue.append(ram_queue[0])  # 保存用于打印的结果
                b_queue.append(ram_queue[1])
                c_queue.append(ram_queue[2])
                interrupt_queue.append('+')  # 产生缺页中断，所以塞个'+'进去
                continue  # 继续下次循环
        elif len(ram_queue) <= 2:  # 虚拟内存队列长度为0、1、2的情况
            ram_queue.append(input_queue[index])
            a_queue.append(ram_queue[0])  # 保存用于打印的结果
            b_queue.append(ram_queue[1] if len(ram_queue) >= 2 else ' ')
            c_queue.append(ram_queue[2] if len(ram_queue) == 3 else ' ')
            interrupt_queue.append('+')  # 产生缺页中断，所以塞个'+'进去
            continue  # 继续下次循环
    print("OPT页面置换算法示意图如下：")
    print_result()
    return

先进先出置换算法

其实就是很简单的队列操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def fifo():
    global input_queue, a_queue, b_queue, c_queue, interrupt_queue, page_queue, ram_queue
    for index in range(len(input_queue)):  # 遍历整个序列
        if len(ram_queue) == 3:
            if input_queue[index] in ram_queue:  # 当前虚拟内存中有该页，不产生缺页中断，也不需要改变虚拟内存中的页表
                a_queue.append(ram_queue[0])  # 保存用于打印的结果
                b_queue.append(ram_queue[1])
                c_queue.append(ram_queue[2])
                interrupt_queue.append(' ')  # 未产生缺页中断，所以塞个' '进去
                continue  # 继续下次循环
            else:  # 虚拟内存满的情况下，调用对应页面置换算法置换页面
                ram_queue.insert(0, input_queue[index])  # 队列头进
                ram_queue.pop()  # 队列尾出
                a_queue.append(ram_queue[0])  # 保存用于打印的结果
                b_queue.append(ram_queue[1])
                c_queue.append(ram_queue[2])
                interrupt_queue.append('+')  # 产生缺页中断，所以塞个'+'进去
                continue  # 继续下次循环
        elif len(ram_queue) <= 2:  # 虚拟内存队列长度为0、1、2的情况
            ram_queue.insert(0, input_queue[index])
            a_queue.append(ram_queue[0])  # 保存用于打印的结果
            b_queue.append(ram_queue[1] if len(ram_queue) >= 2 else ' ')
            c_queue.append(ram_queue[2] if len(ram_queue) == 3 else ' ')
            interrupt_queue.append('+')  # 产生缺页中断，所以塞个'+'进去
            continue  # 继续下次循环
    print("FIFO页面置换算法示意图如下：")
    print_result()
    return

最近最少用置换算法

其实和队列也没多大差，要是当前队列有对应页，就把该页和队头那一页调换位置就好了，产生缺页中断时候的操作和FIFO是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def lru():
    """to do"""
    global input_queue, a_queue, b_queue, c_queue, interrupt_queue, page_queue, ram_queue
    for index in range(len(input_queue)):  # 遍历整个序列
        if len(ram_queue) == 3:
            if input_queue[index] in ram_queue:  # 当前虚拟内存中有该页，不产生缺页中断，也不需要改变虚拟内存中的页表
                ram_queue.remove(input_queue[index])
                ram_queue.insert(0, input_queue[index])
                a_queue.append(ram_queue[0])  # 保存用于打印的结果
                b_queue.append(ram_queue[1])
                c_queue.append(ram_queue[2])
                interrupt_queue.append(' ')  # 未产生缺页中断，所以塞个' '进去
                continue  # 继续下次循环
            else:  # 虚拟内存满的情况下，调用对应页面置换算法置换页面
                ram_queue.pop()
                ram_queue.insert(0, input_queue[index])
                a_queue.append(ram_queue[0])  # 保存用于打印的结果
                b_queue.append(ram_queue[1])
                c_queue.append(ram_queue[2])
                interrupt_queue.append('+')  # 产生缺页中断，所以塞个'+'进去
                continue  # 继续下次循环
        elif len(ram_queue) <= 2:  # 虚拟内存队列长度为0、1、2的情况
            ram_queue.append(input_queue[index])
            a_queue.append(ram_queue[0])  # 保存用于打印的结果
            b_queue.append(ram_queue[1] if len(ram_queue) >= 2 else ' ')
            c_queue.append(ram_queue[2] if len(ram_queue) == 3 else ' ')
            interrupt_queue.append('+')  # 产生缺页中断，所以塞个'+'进去
            continue  # 继续下次循环
    print("LRU页面置换算法示意图如下：")
    print_result()
    return

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == '__main__':
    # 初始化页表，一共有八页
    page_queue.append(PageList(0, 0))
    page_queue.append(PageList(0, 0))
    page_queue.append(PageList(0, 0))
    page_queue.append(PageList(0, 0))
    page_queue.append(PageList(0, 0))
    page_queue.append(PageList(0, 0))
    page_queue.append(PageList(0, 0))
    page_queue.append(PageList(0, 0))

    input_data()

运行结果

没想到吧，我这次放运行结果了！

最优置换

先进先出置换

最近最少用置换

一些一些一些其他垃圾话

其实本来是想优化的，但是由于我太懒了（五一假那能叫懒吗）所以计划取消了！

这里有一只爱丽丝

希望本文章能够帮到您~

Learning Log > 操作系统
#数据结构 #Python #操作系统 #算法
操作系统原理——虚拟存储管理实验
https://map1e-g.github.io/2022/04/29/page-store/
作者
MaP1e-G
发布于
2022年4月29日
许可协议