操作系统实验报告虚拟内存.docx

操作系统实验报告虚拟内存.docx

《操作系统实验报告虚拟内存.docx》由会员分享，可在线阅读，更多相关《操作系统实验报告虚拟内存.docx（29页珍藏版）》请在冰点文库上搜索。

操作系统实验报告虚拟内存

北京邮电大学软件学院

2019-2020学年第1学期实验报告

课程名称：

操作系统

实验名称：

虚拟存储器管理

实验完成人：

日期：

2019年12月21日

一、

实验目的

（说明通过本实验希望达到的目的）

1.了解虚拟存储技术的特点；

2.掌握请求页式管理的页面置换算法。

二、实验内容

（说明本实验的内容）

1.通过随机数产生一个指令序列，共320条指令。

其地址按下述原则生成：

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

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

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

具体的实施方法是：

A.在[0，319]的指令地址之间随机选取一起点M；

B.顺序执行一条指令，即执行地址为M+1的指令；

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

D.顺序执行一条指令，其地址为M’+1；

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

F.重复A—E，直到执行320次指令。

2.指令序列变换成页地址流

设：

（1）页面大小为1K；

（2）用户内存容量为4页到32页；（3）用户虚存容量为32K。

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

第0条—第9条指令为第0页（对应虚存地址为[0，9]）；第10条—第19条指令为第1页（对应虚存地址为[10，19]）；……………………第310条—第319条指令为第31页（对应虚存地址为[310，319]）；按以上方式，用户指令可组成32页。

3.计算并输出下述各种算法在不同内存容量下的命中率。

A.先进先出（FIFO）页面置换算法

B.最近最久未使用（LRU）页面置换算法--最近最少使用算法

C.最少使用（LFR）页面置换算法

D.最佳（Optimal）页面置换算法

三、实验环境

（说明本实验需要的环境）

Vscode+ubuntun

四、实验过程描述

本实验需要分几个步骤完成。

本实验所定义的数据结构:

#define I_NUM 320

#define CONST 1000

//页表

typedef struct pagetable {

  int p_num;    //页号

   int access_time[32];//记录访问的时间

  bool status[32];//状态位（是否写入内存） 写入1 未写入0

  int m_num[32];//存入的内存块号

}PageTable;

//队列的结构

typedef struct {

  int count;    //计数

  int front;    //头指针

  int rear;     //尾指针

  int *data;    //数据域

  int size;     //大小

} CirQueue;

int ins[I_NUM];       //指令数组

int visit_times[32]; //每一个页面访问次数的数组

步骤一：

按要求产生指令序列。

这部分按照指导书上做就ok了。

具体实现：

void initIns（）

{

    for （int i = 0; i < I_NUM; i += 4）

    {

        int m = rand（） % I_NUM; //0到319的随机数

        ins[i] = （m + 1） % I_NUM;  //执行地址为m+1的指令

        int m1 = rand（） % （m + 2）; //随机选取一条指令并执行

        ins[i + 1] = m1;

        ins[i + 2] = （m1 + 1） % I_NUM; //执行地址为m1+1的指令

        ins[i + 3] = rand（） % （I_NUM - m1 - 2） + m1 + 2;

    }

}

步骤二：

指令序列变换成页地址流

只需将指令所在的位置整除10即可得到页号。

步骤三：

实现各种算法

首先是FIFO算法。

相关原理：

该算法总是淘汰最新进入内存的页面，即选择在内存中驻留时间最久的页面予

以淘汰。

该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

思路：

先检查内存是否还有空间，如果还有则直接插入，否则调用此算法，将先出队再入队来完成页面置换。

实现:

void FIFO（int f_num, PageTable *pagetable）

{

    int p_fault = 0;

    CirQueue *queue = （CirQueue *）malloc（sizeof（CirQueue））;

    initPage（pagetable, f_num）;

    initQueue（queue, f_num）;

    int i;

    for （int i_num = 0; i_num < 320; i_num++）

    {

        if （!

isHitted（f_num, i_num, pagetable）） //没命中

        {

            p_fault++; //页表内没有查询到当前指令所属的页

            for （i = 0; i < pagetable->p_num; i++）

            {

                if （pagetable->status[i] == 0）

                    break;

            }

            if （i < pagetable->p_num） //内存未满 让新的页进来

            {

                pagetable->status[i] = true;

                pagetable->m_num[i] = ins[i_num] / 10;

                Enqueue（queue, （ins[i_num] / 10））; //同时 此页进队

            }

            else //内存已满 开始置换

            {

                int last_page = Dequeue（queue）; //页号

                for （i = 0; i < pagetable->p_num; i++）

                {

                    if （pagetable->m_num[i] == last_page）

                        break;

                }

                pagetable->m_num[i] = ins[i_num] / 10;

                Enqueue（queue, （ins[i_num] / 10））; //新的页号进队

            }

        }

    }

    double p_fault_r = （double）p_fault / I_NUM;

    printf（"%f\t", 1 - p_fault_r）;

}

其次是LRU算法。

相关原理：

最近最久未使用（LRU）页面置换算法，是根据页面调入内存后的使用情况进行决策的。

由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

思路：

同样先判断内存是否为满。

如果未满则直接插入，否则调用该算法。

该算法需要一个记录访问时间的数组access_time[]，当需要置换时，选择数组中元素最大的元素，将其置换出去，然后将新页面放进来。

每次访问时将未访问的页面的access_time加一。

实现：

//lru算法

void LRU（int f_num, PageTable *pagetable）

{

    int p_fault = 0;

    initPage（pagetable, f_num）;

    int k;

    for （int i_num = 0; i_num < I_NUM; i_num++）

    {

        if （!

isHitted（f_num, i_num, pagetable）） //没命中

        {

            p_fault++;

            //页表内没有查询到当前指令所属的页

            for （k = 0; k < pagetable->p_num; k++）

            {

                if （pagetable->status[k] == false）

                {

                    break;

                }

            }

            if （k < pagetable->p_num）

            {

                //内存未满 让新的页进来

                pagetable->status[k] = true;

                pagetable->m_num[k] = ins[i_num] / 10;

                //所有页的访问次数自增

                incTime（pagetable, f_num）;

            }

            else

            {

                //内存已满 开始置换

                int index = LeastUsed（pagetable, f_num）;

                pagetable->access_time[index] = 0;

                pagetable->m_num[index] = ins[i_num] / 10;

                //所有页的访问时间自增

                incTime（pagetable, f_num）;

            }

        }

    }

    double p_fault_r = （double）p_fault / I_NUM;

    printf（"%f\t", 1 - p_fault_r）;

}

void incTime（PageTable *pagetable, int f_num）

{

    for （int i = 0; i < f_num; i++）

    {

        if （pagetable->status[i] == true）

            pagetable->access_time[i]++;

    }

}

int LeastUsed（PageTable *pagetable, int f_num） //选择现有页面中其 t 值最大的，即用的最少的页

{

    int k = pagetable->access_time[0];

    int max = 0;

    for （int i = 0; i < f_num; i++）

    {

        if （pagetable->access_time[i] > k）

        {

            k = pagetable->access_time[i];

            max = i;

        }

    }

    return max;

}

然后是LFR算法。

相关原理：

在采用该算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录页面被访问的频率。

该置换算法选择在最近使其使用最少的页面作为淘汰页。

思路：

需要一个数组visit_times[]来记录每个页面访问的次数，即为频率。

同样先判断内存是否为满。

如果未满则直接插入，否则调用该算法。

选择频率最低的页面，将其置换出去，然后将新页面放进来。

实现：

//lfr算法

void LFR（int f_num, PageTable *pagetable）

{

    int p_fault = 0;

    initPage（pagetable, f_num）;

    int i;

    for （int i_num = 0; i_num < 320; i_num++）

    {

        if （!

isHitted（f_num, i_num, pagetable）） //没命中

        {

            p_fault++;

            //页表内没有查询到当前指令所属的页

            for （i = 0; i< pagetable->p_num; i++）

            {

                if （pagetable->status[i] == false）

                {

                    break;

                }

            }

            if （i < pagetable->p_num）   //内存未满 让新的页进来

            {

                pagetable->status[i] = true;

                pagetable->m_num[i] = ins[i_num] / 10;

                visit_times[ins[i_num] / 10]++;     //同时 所有页的访问次数自增

            }

            else

            {

                //内存已满 开始置换

                int min_index = 0;

                int min = CONST;

                for （int k = 0; k < 32; k++）

                {

                    if （pagetable->status[k] == true）   //寻找在内存中的被访问次数最少的页面换出

                        if （visit_times[k] < min）

                        {

                            min = visit_times[k];

                            min_index = k;

                        }

                }

                pagetable->m_num[min_index] = ins[i_num] / 10;

                visit_times[ins[i_num] / 10]++;

            }

        }

    }

    double p_fault_r = （double）p_fault / I_NUM;

    printf（"%f\t", 1 - p_fault_r）;

}

最后是OPT算法。

相关原理：

该算法选择的被淘汰页面，将是以后永远不使用的，或许是在最长（未来）时间内不再被访问的页面。

采用该算法，通常可保证获得最低的缺页率。

但由于人们目前

还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间

思路：

由于本模拟实验已经知道将来会有那些序列被放进内存，所以该算法可以实现。

同样先判断内存是否为满。

如果未满则直接插入，否则调用该算法。

该算法需要数组distance[]表示该页到未来最近一次的距离。

需要置换时，选择距离被使用的页面将其置换，然后将新页面置换进来。

实现：

void OPT（int f_num, PageTable *pagetable）

{

    int p_fault = 0;

    initPage（pagetable, f_num）;

    int i;

    for （int i_num = 0; i_num < 320; i_num++）

    {

        if （!

isHitted（f_num, i_num, pagetable）） //没命中

        {

            p_fault++;

            //页表内没有查询到当前指令所属的页

            for （i = 0; i < pagetable->p_num; i++）

            {

                if （pagetable->status[i] == false）

                    break;

            }

            if （i < pagetable->p_num）

            {

                //内存未满 让新的页进来

                pagetable->status[i] = true;

                pagetable->m_num[i] = ins[i_num] / 10;

            }

            else

            {

                //内存已满 开始置换

                //检查当前内存里的页哪个最久会被使用

                int *distance = （int *）malloc（sizeof（int） * f_num）; //暂存距离的数组

                //初始化

                for （i = 0; i < f_num; i++）

                {

                    distance[i] = CONST;

                }

                for （int l = 0; l < f_num; l++）

                {

                    i = pagetable->m_num[l];

                    for （int k = i_num; k < f_num; k++）

                    {

                        if （ins[k] == i）

                        {

                            distance[l] = k - l; 

                            break;

                        }

                    }

                }

                //找出之后最远被使用的

                i = distance[0];

                int max = 0;

                for （int j = 0; j < f_num; j++）

                {

                    if （distance[j] > i）

                    {

                        i = distance[j];

                        max = j;

                    }

                }

                pagetable->m_num[max] = ins[i_num] / 10;

            }

        }

    }

    double p_fault_r = （double）p_fault / I_NUM;

    printf（"%f\t", 1 - p_fault_r）;

}

五、实验结果

运行结果如下：

随着物理内存的增加，命中率逐渐上升。

4种算法的命中率差别不大。

六、附件

6.1附件1：

源代码

Vm.h

#include 

#include 

#include 

#define I_NUM 320

#define CONST 1000

//页表

typedef struct pagetable {

  int p_num;    //页号

   int access_time[32];//记录访问的时间

  bool status[32];//状态位（是否写入内存） 写入1 未写入0

  int m_num[32];//存入的内存块号

}PageTable;

//队列的结构

typedef struct {

  int count;    //计数

  int front;    //头指针

  int rear;     //尾指针

  int *data;    //数据域

  int size;     //大小

} CirQueue;

int ins[I_NUM];       //指令数组

int visit_times[32]; //每一个页面访问次数的数组

void initQueue（CirQueue* queue,int i）;

bool isEmpty（CirQueue* queue）;

bool