《操作系统》第四次实验——页面置换

一、实验目的及基本要求

设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法；通过页面访问序列随机发生器实现对上述算法的测试及性能比较。

二、页面置换算法知识背景说明

1. 请求分页虚拟内存
   
2. 工作集与缺页率
   （1）工作集
   多数程序都显示出高度的局部性，也就是说，在一个时间段内，一组页面被反复引用。这组被反复引用的页面随着时间的推移，其成员也会发生变化。有时这种变化是剧烈的，有时这种变化则是渐进的。我们把这组页面的集合称为工作集。
   （2）缺页率
   缺页率 = 缺页中断次数/页面访问次数
3. 最佳置换算法
   （1）基本思想
   选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存
   （2）评价
   理想化算法，具有最好性能（对于固定分配页面方式，本法可保证获得最低的缺页率），但实际上却难于实现，故主要用于算法评价参照
4. 先进先出置换算法
   （1）基本思想
   选择最先进入内存即在内存驻留时间最久的页面换出到外存.进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针以指向最老页面
   （2）评价
   简单直观，但不符合进程实际运行规律，性能较差，故实际应用极少
5. 最近最久未使用置换算法LRU
   （1）基本思想
   以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存
   （2）评价
   适用于各种类型的程序，性能较好，但需要较多的硬件支持
6. 改进型Clock置换算法
   （1）基本思想
   从查寻指针当前位置起扫描内存分页循环队列，选择A=0且M=0的第一个页面淘汰；若未找到，转②
   开始第二轮扫描，选择A=0且M=1的第一个页面淘汰，同时将经过的所有页面访问位置0；若不能找到，转①
   （2）评价
   与简单Clock算法相比，可减少磁盘的I/O操作次数，但淘汰页的选择可能经历多次扫描，故实现算法自身的开销增大
7. 页面缓冲算法PBA
   （1）基本思想

• 设立空闲页面链表和已修改页面链表
• 采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是据是否修改分别挂到空闲页面链表或已修改页面链表的末尾
• 空闲页面链表同时用于物理块分配
• 当已修改页面链表达到一定长度如Z个页面时，一起将所有已修改页面写回磁盘，故可显著减少磁盘I/O操作次数

三、课题假设前提说明

1. 模拟的虚拟内存的地址为16位，页面大小为1K
2. 模拟的物理内存有32K
3. 页表用整数数组或结构数组来表示
4. 页面访问序列串是一个整数序列，整数的取值范围为0到N - 1。页面访问序列串中的每个元素p表示对页面p的一次访问

四、页面访问序列随机生成说明

1. 符合局部访问特性的随机生成算法
   （1）确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和1之间的值t；
   （2）生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中；
   （3）生成一个随机数r，0 ≤ r ≤ 1；
   （4）如果r < t，则为p生成一个新值，否则p = (p + 1) mod N；
   （5）如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。

五、性能测评及问题说明

1. 测试不同的页面访问序列及不同的虚拟内存尺寸，并从缺页率、算法开销等方面对各个算法进行比较。
2. （同时请给出在给定页面访问序列的情况下，发生页面置换次数的平均值）

六、实验过程

1. 页面访问序列随机生成器的实现

/*********生成页面访问序列********/
void generate()
{
    srand ( (unsigned) time (NULL)); //用时间做种，每次产生随机数不一样
    p = rand() % 64;
    int m = 8, e = 8;
    int i, j;
    double t;
    t = rand()%10/10.0;
    for (i = 0; i < 4; i++)
    {
        for (j=i*m; j<(i+1)*m;j++)
        {
            access[j] = (p + rand() % e) % 64;
        }
        double r = (rand() % 10) / 10.0;
        if (r < t)
        {
            p = rand() % 64;
        }
        else
        {
            p = (p + 1) % 64;
        }
    }
    printf("生成的页面随机访问序列：\n");
    for(int i=0;i<32;i++)
    {
        printf("%d ", access[i]);
    }
    printf("\n");
}

2. 页面缓冲算法（PBA）
   设立空闲页面链表和已修改页面链表，采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾，空闲页面链表同时用于物理块分配，当已修改页面链表达到一定长度如Z个页面时，一起将所有已修改页面写回磁盘，故可显著减少磁盘I/O操作次数。
   使用链表将装入内存的页块串联起来，节点结构体如下：

typedef struct LNode
{
    int data;
    int flag; //访问位
    int modify; //修改位
    struct LNode *next;
}LNode;
typedef struct Link
{
    int num;//当前链表上的结点数
    LNode *next;
}Link;

主要函数如下：
bool isInNodes(int n);//页面是否已经在链表中
void addToLink(int data, int type);/页面添加到已修改页面链表和空闲链表上
void emptyIdle();//将空闲链表上的所有页面送出内存
void emptyModi();//将已修改页面链表上所有的链表送出内存
void PBA(int n);//PBA算法实现函数
void PBA_ALL();//处理随机生成器生成的页面序列并计算缺页率

void PBA (int n)
{
    if (isInNodes (n))
    {
        printf ("已装入内存\n");
    }
    else
        if (index == size)
        {
            struct LNode *p;
            if ( (p = isinLinks (n)) != NULL)
            {
                nodes = (LNode*) realloc (nodes, (size + 1) * sizeof (LNode));
                nodes[size] .data = p->data;
                nodes[size].flag = p->flag;
                nodes[size].modify = p->modify;
                nodes[size].next = p->next;
                free (p);
                size++;
                index++;
            }
            else
            {
                lost++;//缺页
                if (nodes[n % 3].modify == 1)
                {
                    addToLink (nodes[n % 3].data, 1);
                }
                else
                {
                    addToLink (nodes[n % 3].data, 0);
                }
                nodes[n % 3].data = access[n];
                nodes[n % 3].flag = 1;
                nodes[n % 3].next = NULL;
                if (rand() % 10 < 4)
                {
                    nodes[n % 3].modify = 0;
                }
                else
                {
                    nodes[n % 3].modify = 1;
                }
            }
        }
        else
        {
            nodes[index].data = access[n];
            nodes[index].flag = 1;
            nodes[index].next = NULL;
            if (rand() % 10 < 4)
            {
                nodes[index].modify = 1;
            }
            else
            {
                nodes[index].modify = 0;
            }
            index++;
        }
}

3. 先进先出页面置换算法（FIFO）
   这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序存入一个时间数组，并将其中时间值最大的页面进行淘汰，并替换入新的页面就可以实现。
   如图所示：
   
   使用单向队列，队列结点元素的结构体如下：

typedef struct node
{
    int num;//页号
    node* next;//下一个结点页面
} Node, *pNode;

typedef struct queue
{
    int n;//总的结点数
    pNode front;//队首指针
    pNode rear; //队尾指针
} Queue, *pQueue;

主要函数如下：
void initQueue(pQueue q);//初始化队列
void push(pQueue q, int num);//队列中加入新的页面结点
void pop(pQueue q);//将页面移出内存
void destroy (pQueue q);//销毁队列
bool findInQueue (pQueue q, int num);//查找页面是否已经调入内存
void fifo(pQueue q, int num);//先进先出置换算法实现函数
void FIFO_ALL();//处理随机生成器生成的页面序列并计算缺页率

void fifo(pQueue q, int num)
{
    if (findInQueue (q, num))
    {
        printf ("已装入内存\n");
    }
    else
    {
        if(q->n==size)
        {
            pop(q);
            push(q, num);
            lost++;
        }
        else
        {
            push(q, num);
        }
    }
}

4. 最近最久未使用页面置换算法（LRU）
   当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。
   
   使用数组结构，主要函数如下：
   bool isInMemo(int n);//指定页号是否已经在内存中
   void LRU(int n);//LRU算法实现函数
   void LRU_ALL();//处理随机生成器生成的页面序列并计算缺页率

void LRU(int n)
{
    int i, j;
    if (isInMemo(n))
    {
        printf ("已经装入内存\n");
    }
    else
        if (index == size)
        {
            int max = n, pos = -1, tag;

            for (i = 0; i < size; i++)
            {
                for (j = n - 1; j >= 0; j--)
                {
                    if (access[j] == memo[i])
                    {
                        tag = j;
                        break;
                    }
                }
                if (tag < max)
                {
                    max = tag;
                    pos = i;
                    if (max == 0)
                    {
                        break;
                    }
                }
            }
            memo[pos] = access[n];
            lost++;
        }
        else
        {
            memo[index] = access[n];
            index++;
        }
}

5. 最佳页面置换置换算法（OPT）
   其所选择的被淘汰页面，将是永不使用的，或者是在最长时间内不再被访问的页面。可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法也是无法实现的。但是可利用该算法去评价其它算法。
   
   使用数组结构，主要函数如下：
   bool isInMemo(int n);//指定页号是否已经在内存中
   void OPT(int n);//OPT算法实现函数
   void OPT_ALL();//处理随机生成器生成的页面序列并计算缺页率

void OPT(int n)
{
    int i = 0, j = 0;
    if (isInMemo (n))
    {
        printf ("页面已被调入\n");
    }
    else
        if (index == size)
        {
            lost++;
            int max = 0, pos, tag;
            for (i = 0; i < size; i++)
            {
                tag = -1;
                for (j = n + 1; j < 32; j++)
                {
                    if (access[j] == memo[i])
                    {
                        tag = j;
                        break;
                    }
                }
                if (tag == -1)
                {
                    max = 32;
                    pos = i;
                    break;
                }
                else
                {
                    if (max < tag)
                    {
                        max = tag;
                        pos = i;
                    }
                }
            }
            memo[pos] = access[n];
        }
        else
        {
            memo[index] = access[n];
            index++;
        }
}

七、实验结果

生成随机序列access[32]={63, 58, 58, 60, 60, 63, 58, 63, 26, 28, 29, 31, 31, 27, 30, 28, 27, 31, 31, 31, 27, 34, 32, 33, 28, 31, 30, 30, 33, 28, 34, 34}
PBA算法处理结果及缺页率：


可以看到，32个页面，有13个页面发生了缺页，缺页率为0.406
FIFO算法处理结果及缺页率：


可以看到，32个页面，有18个页面发生了缺页，缺页率为0.563
LRU算法处理结果及缺页率：


可以看到，32个页面，有17个页面发生了缺页，缺页率为0.531
OPT算法处理结果及缺页率：


可以看到，32个页面，有12个页面发生了缺页，缺页率为0.375
利用genenrate()函数再生成几个访问序列，记录得到如下表格的形式表示：
访问序列的长度始终为32，默认初始分配给每种算法的内存空间块数为3

置换算法		PBA	FIFO	LRU	OPT
测试序列1	缺页数	13	18	17	12
	缺页率	0.41	0.56	0.53	0.38
测试序列2	缺页数	18	20	21	17
	缺页率	0.56	0.63	0.66	0.53
测试序列3	缺页数	11	11	12	9
	缺页率	0.34	0.34	0.38	0.28

从上图以及表格可以分析出：
（1） 同一种算法，对于不同的访问序列，其缺页率是不同，会有所变化。
（2） 总的来看，最佳置换算法的缺页率是最低的。剩下的集中算法中，页面缓冲算法的缺页率要低于其他置换算法。先进先出算法和最近最久未使用算法性能相近。
实验完整源码请点击(Github)