实验要求

实验目的

存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。

本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

二、实验内容

（1） 通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。

页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。

在本实验中，假定页面大小为1k，用户虚存容量为32k，用户内存容量为4页到32页。

（2） produce_addstream通过随机数产生一个指令序列，共320条指令。

A、 指令的地址按下述原则生成：

1） 50%的指令是顺序执行的

2） 25%的指令是均匀分布在前地址部分

3） 25%的指令是均匀分布在后地址部分

B、 具体的实施方法是：

1） 在[0，319]的指令地址之间随机选取一起点m；

2） 顺序执行一条指令，即执行地址为m+1的指令；

3） 在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；

4） 顺序执行一条指令，地址为m’+1的指令

5） 在后地址[m’+2，319]中随机选取一条指令并执行；

6） 重复上述步骤1）~5），直到执行320次指令

C、 将指令序列变换称为页地址流

在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：

第0条~第9条指令为第0页（对应虚存地址为[0，9]）；

第10条~第19条指令为第1页（对应虚存地址为[10，19]）；

。。。。。。

第310条~第319条指令为第31页（对应虚存地址为[310，319]）；

按以上方式，用户指令可组成32页。

（3） 计算并输出下属算法在不同内存容量下的命中率。

1） 先进先出的算法（FIFO）；

2） 最近最少使用算法（LRU）；

四、运行结果

运行程序：

a、 终端先显示：

Start memory management.

Producing address flow, wait for while, please.

b、 地址流、地址页号流生成后，终端显示：

There are algorithms in the program

1、 Optimization algorithm

2、 Least recently used algorithm

3、 First in first out algorithm

4、 Least frequently used algorithm

Select an algorithm number, please.

用户输入适当淘汰算法的号码，并按回车，若是第一次选择，输出相应的地址页号流。然后输出该算法分别计算的用户内存从2k32k时的命中率，若输入的号码不再14中，则显示：

there is not the algorithm in the program,并重复b。

c、 输出结果后，终端显示 “do you try again with anther algorithm(y/n)”。若键入y则重复b,否则结束。（一般讲四种算法都用过后结束，以便比较）。

五、运行结果讨论

1、 比较各种算法的命中率

2、 分析当用户内存容量增加是对命中率的影响

实验报告

1.实验目的

存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。

本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

2.实验内容与要求

①实验内容

（1） 通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。

页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。

在本实验中，假定页面大小为1k，用户虚存容量为32k，用户内存容量为4页到32页。

（2） produce_addstream通过随机数产生一个指令序列，共320条指令。

A、 指令的地址按下述原则生成：

1） 50%的指令是顺序执行的

2） 25%的指令是均匀分布在前地址部分

3） 25%的指令是均匀分布在后地址部分

B、 具体的实施方法是：

1） 在[0，319]的指令地址之间随机选取一起点m；

2） 顺序执行一条指令，即执行地址为m+1的指令；

3） 在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；

4） 顺序执行一条指令，地址为m’+1的指令

5） 在后地址[m’+2，319]中随机选取一条指令并执行；

6） 重复上述步骤1）~5），直到执行320次指令

C、 将指令序列变换称为页地址流

在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：

第0条~第9条指令为第0页（对应虚存地址为[0，9]）；

第10条~第19条指令为第1页（对应虚存地址为[10，19]）；

。。。。。。

第310条~第319条指令为第31页（对应虚存地址为[310，319]）；

按以上方式，用户指令可组成32页。

（3） 计算并输出下属算法在不同内存容量下的命中率。

1） 先进先出的算法（FIFO）；

2） 最近最少使用算法（LRU）；

②实验要求

运行程序：

a、 终端先显示：

Start memory management.

Producing address flow, wait for while, please.

b、 地址流、地址页号流生成后，终端显示：

There are algorithms in the program

1、 Optimization algorithm

2、 Least recently used algorithm

3、 First in first out algorithm

4、 Least frequently used algorithm

Select an algorithm number, please.

用户输入适当淘汰算法的号码，并按回车，若是第一次选择，输出相应的地址页号流。然后输出该算法分别计算的用户内存从2k32k时的命中率，若输入的号码不再14中，则显示：

there is not the algorithm in the program,并重复b。

c、 输出结果后，终端显示 “do you try again with anther algorithm(y/n)”。若键入y则重复b,否则结束。（一般讲四种算法都用过后结束，以便比较）。法

3.流程图与模块调用

4.实验分析

想要完成操作系统算法，首先要弄清楚操作系统相关的专业术语。弄清各个算法的流程和目的要求。才能模拟出相关算法的过程。

在我的理解中，

为什么要进行页面置换？

在请求分页存储管理系统中，由于使用了虚拟存储管理技术，使得所有的进程页面不是一次性地全部调入内存，而是部分页面装入。

这就有可能出现下面的情况：要访问的页面不在内存，这时系统产生缺页中断。操作系统在处理缺页中断时，要把所需页面从外存调入到内存中。如果这时内存中有空闲块，就可以直接调入该页面；如果这时内存中没有空闲块，就必须先淘汰一个已经在内存中的页面，腾出空间，再把所需的页面装入，即进行页面置换。

先进先出法（FIFO）

算法描述：由于认为最早调入内存的页不再被使用的可能性要大于刚调入内存的页，因此，先进先出法总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。先进先出法把一个进程所有在内存中的页按进入内存的次序排队，淘汰页面总是在队首进行。如果一个页面刚被放入内存，就把它插在队尾。

最近最少使用置换法（LRU）

算法描述：最近最少使用置换法（LRU）是选择在最近一段时间里最久没有使用过的页面予以淘汰。借鉴FIFO算法和OPT算法，以“最近的过去”作为“不久将来”的近似。

5.运行情况

①程序正常运行测试

② 比较各种算法的命中率、分析当用户内存容量增加是对命中率的影响：

利用如下语句，可以直观对比区别：

for i in range(2,33):
    print('memory={} FIFO/LRU命中率：{} / {}'.format(i,FIFO(i),LRU(i)))

由上图可以直观看出：

①当用户内存容量增加对命中率会相应增加；
②对于FIFO与LRU两种算法，在内存容量为20左右时，命中率差不多；
在内存容量小于20时，FIFO算法命中率更高；
在内存容量大于20时，LRU算法命中率更高；

6.实验体会

通过本次实验，我深刻的理解了操作系统中资源的分配方式和存储管理的调度方式。操作系统实验重在理解每一个算法的意图和目的，那么就选择适当的数据结构模拟过程就可以完成相关算法了。

对于FIFO算法，这个算法原理简单，就是先进先出。对于这个结构最好采用的就算队列了，对于python而言，我用的是list集合，每次添加数据的时候添加到第0位置（list的insert(0,num)），而如果移除的时候移除末尾的页数（list的pop()）。在这个过程中，每执行一条指令的时候，如果这个指令对应的地址（指令/10）在list中，那么就命中，否则就是缺页，需要移除尾，在0位置添加元素。

对于LRU算法，这个算法跟FIFO其实还是挺像的，但是有一点区别，最近最少使用。也就是说在一个正常序列的时候如果命中的话，就会把这个地址的页号移动到首位（或者链表首位）。而如果缺页的时候，要把这个链表的末尾位置移除，因为末尾的元素是最近用的最少的（很久前才有的）。对于数据结构，依然选择list。其实这个是典型的堆栈的数据结构，利用python的list的pop()和append()就可以完美完成。

本次实验采用python完成，IDE是pycharm，python的列表list的insert()、pop()、append()方法可以把列表很好的模拟成堆栈或者队列，这些在算法的编写过程中否起到了很大的作用。

【附】实验代码

import random

num = [0 for i in range(0, 325)]  # 生成随机数会有溢出，所以数组长度设置大一点
page = [0 for i in range(0, 320)]


# 按照题目的算法生成随机数
def createRandomNum():
    i = 0
    while i < 320:
        m = random.randint(0, 318)
        num[i] = m + 1  # 顺序执行了一条指令
        m1 = random.randint(0, m + 1)
        i += 1
        num[i] = m1  # 在[0,m+1]之间执行了一条指令
        i += 1
        num[i] = m1 + 1  # 顺序执行了一条指令
        if m1 < 317:
            m2 = random.randint(m1 + 2, 319)
            i += 1
            num[i] = m2  # 在[m1+2,319]之间执行了一条指令

    print('**********生成320个随机数**********')
    str = ''
    for index, i in enumerate(num):
        if index < 320:
            str += '{}	'.format(i)
            if (index + 1) % 20 == 0:
                str += '
'
    print(str)


# 将指令序列变换称为页地址流
def changeAsPage():
    for index, i in enumerate(num):
        if index < 320:
            page[index] = int(i / 10)
    print('**********转化为320个页码数**********')
    str = ''
    for index, i in enumerate(page):
        str += '{}	'.format(i)
        if (index + 1) % 20 == 0:
            str += '
'
    print(str)

# 先进先出法
def FIFO(msize):
    Q = []  # 定义队列
    queYeTimes = 0  # 缺页次数
    for item in page:
        if len(Q) < msize:
            Q.insert(0, item)  # 压入队列
        elif item in Q:
            Q.remove(item)
        else:
            Q.pop()
            Q.insert(0, item)
            queYeTimes += 1
    return (1-queYeTimes/320)

# 最近最少使用置换法
def LRU(msize):
    L = []  # 定义堆栈
    queYeTimes = 0  # 缺页次数
    for item in page:
        if item in L:
            [L[0],L[len(L)-1]]=[L[len(L)-1],L[0]]
        elif len(L)<msize:
            L.append(item)
        else:
            L.append(item)
            del L[0]
            queYeTimes+=1
    return (1 - queYeTimes / 320)


print('Start memory management.
Producing address flow, wait for while, please.
')
print('There are algorithms in the program
1、  Optimization algorithm
2、  Least recently used algorithm
3、   First in first out algorithm
4、    Least frequently used algorithm
Select an algorithm number, please.')
key = int(input())
createRandomNum()
changeAsPage()

i=2
while i<33:
    if key==2:
        print('memory={} LRU命中率：{}'.format(i,LRU(i)))
        flag = input('do you try again with anther algorithm(y / n):')
        if flag=='y':
            key = int(input('input the num:'))
            i+=1
        else:
            break
    elif key == 3:
        print('memory={} FIFO命中率：{}'.format(i,FIFO(i)))
        flag = input('do you try again with anther algorithm(y / n):')
        if flag == 'y':
            key = int(input('input the num:'))
            i += 1
        else:
            break

# for i in range(2,33):
#     print('memory={} FIFO/LRU命中率：{} / {}'.format(i,FIFO(i),LRU(i)))