补全下面页面淘汰算法

Question

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define N 10
#define MAXN 320      //序列个数
#define MAX MAXN+20  //数组大小
#define MAXP MAXN/10 //最大页数

int inst[MAX]; //指令序列
int page[MAX]; //页地址流
int size=10;      //内存能容纳的页数

int in[MAXP];   //该页是否在内存里 0 1
int pin[MAXP];  //页在内存中的位置为下标 

void welcome()
{
    printf("******************************************\n");
    printf("**     操作系统模拟实验\t\t**\n");
    printf("**        页式储存管理       **\n");
    printf("******************************************\n\n");
}

/*选择操作界面*/
void input_hint()
{
    printf("\n1--构造指令序列     2--设置存储页号(4 to 32)\n");
    printf("3-- FIFO 算法       4--LRU 算法\n");
    printf("5--OPT 算法         0--退出\n");
    printf("*********请输入您的选择:  ");
}

/*通过随机数产生一个**指令序列**，共320条指令*/
void produce_inst()
{
    int m, n,i=0;
    int num = 0;
    srand(time(NULL)); 
    while(num < MAXN)
    {
        //指令编号在320内
        
        m = rand() % MAXN;
        inst[num++] = (m+1)%MAXN;
        if(num == MAXN) break;
        
        //要访问的第二组指令 
        m = (m+2) % MAXN;
        if(m == 0) m = 160;
        n = rand() % m;
        inst[num++] = (n+1)%MAXN;
        if(num == MAXN) break;
        //要访问的第三组指令 
        n = (n+2) % MAXN;
        m = MAXN - n;
        if(m == 0) m = 160;
        m = rand() % m + n;
        inst[num++] = m;
    }
    printf( "指令序列为：\n");
    for(i=0;i<MAXN;i++) 
    {
        if (i % size == 0) putchar('\n');
        printf("%d\t",inst[i]);
        
    }
    printf("\n\n"); 
}

/*将指令序列变换成为页地址流
  共有32个页面 
*/
void turn_page_address()
{
    int i;
    //将指令放入页面中 
    for(i=0; i<MAXN; i++)
        page[i] = inst[i]/10;
    printf( "页地址流为：\n");
        for(i=0;i<MAXN;i++)  
        {
            if (i % size == 0) putchar('\n');
            printf("%d\t",page[i]);            
        }
        printf("\n\n");
}

/*先来先服务置换算法*/
void FIFO_solve()
{
    memset(in, 0, sizeof(in));
    int fault_n = 0;//缺页率
    int ptr, i , j;

    //预调页填满空间 size为内存中的页面数   
    ptr = 0; //下一个要放的位置
    //把size个页面放入内存中 in表示在内存中 
    for(i=0; i<MAXN && ptr<size; i++)
        //访问页面不在内存中 
        if(!in[page[i]])
        {
            pin[ptr++] = page[i]; //页面在内存中的位置ptr 
            in[page[i]] = 1;  //放入内存 
            fault_n++;  //缺页次数 
        }
    printf("内存中的页面序列为：\n");
    for(j=0;j<size;){
        printf("%5d",pin[j]);
        j++;
        if(j % size == 0) putchar('\n');
    }
    //继续执行剩下的指令
    ptr = 0;//队列里最先进来的位置，即下一个要被替换的位置
    printf("缺页序列为：\n");
    j=0;
    for(; i<MAXN; i++)
        if(!in[page[i]])
        {
          **  /*请补全该部分*/**
            
              
        }else{
            //printf("   **%3d**  ",page[i]); 
        }

    printf("\n FIFO算法  访问失败页面数量为:  %d\n", fault_n);
    printf("             缺页率为 :  %.2lf\n", ((float)fault_n)/MAXN);
}

/*最近最久未使用置换算法*/
void LRU_solve()
{
    int ltu[MAXP]; //last_time_use
    int ti = 1;    //模拟时间
    int fault_n = 0; //缺页次数 
    memset(ltu, 0, sizeof(ltu));
    memset(in, 0, sizeof(in));
    memset(pin, -1, sizeof(pin));

    int min, ptr, i, j,k=0;
    //初始将size个页面调入内存 
    //预调页填满空间 size为内存中的页面数   
    ptr = 0; //下一个要放的位置
    //把size个页面放入内存中 in表示在内存中 
    for(i=0; i<MAXN && ptr<size; i++)
        //访问页面不在内存中 
        if(!in[page[i]])
        {
            pin[ptr] = page[i]; //页面在内存中的位置ptr 
            in[page[i]] = 1;  //放入内存 
            fault_n++;  //缺页次数 
            ltu[ptr] = ti++;
            ptr++;
        }
    printf("内存中的页面序列为：\n");
    for(j=0;j<size;){
        printf("%5d",pin[j]);
        j++;
        if(j % size == 0) putchar('\n');
    }
    printf("缺页序列为：\n");
    for(; i<MAXN; i++)
    {  // k=0;
        if(!in[page[i]])
        {            
            //寻找lru
            min=ltu[0]; ptr=0;
            for(j=1; j<size; j++)
            {
                if(ltu[j] < min)
                {
                    min = ltu[j];
                    ptr = j;
                }
            }
       //替换或写入 
            if(pin[ptr] != -1){
                in[pin[ptr]] = 0;  //换出页面 
                in[page[i]] = 1;   //写入页面 
            }
            /*请补全该部分*/
            //缺页调入内存 

        }
        else//已经在内存里则只需更改最近使用时间    
        {
            for(j=0; j<size; j++)
                if(pin[j] == page[i])
                {
                    ltu[j] = ti++;
                    break;
                }
        }        
    }

    printf("\n LRU 算法   访问失败页面数量为:  %d\n", fault_n);
    printf("              缺页率为 :  %.2lf\n", ((float)fault_n/MAXN));
}

/*最佳置换算法*/
void OPT_solve()
{
    int ntu[MAXP];  //next_time_use
    int fault_n = 0;
    int i, j,k = 0;
    memset(in, 0, sizeof(in));
    memset(ntu, -1, sizeof(ntu));

    //预调页填满
    int ptr = 0;
    for(i=0; i<MAXN && ptr<size; i++)
    {
        if(!in[page[i]])
        {
            in[page[i]] = 1;
            pin[ptr] = page[i];
            fault_n++;
            ptr++;
        }
    }

    //初始化ntu数组 下次再使用页面序列 
    ptr = 0;
    for(j=i; j<MAXN && ptr<size; j++)
    {
        if(ntu[page[j]] == -1)
        {
            ntu[page[j]] = j;
            ptr++;
        }
    }

    int max;
    printf("缺页序列为：\n");
    for(; i<MAXN; i++)
    {
        if(!in[page[i]])
        {
            max = 0;ptr = 0;
            for(j=0; j<size; j++)
            {
                if(ntu[pin[j]] == -1)
                {
                    ptr = j;
                    break;
                }
                if(ntu[pin[j]] > max)
                {
                    max = ntu[pin[j]];
                    ptr = j;
                }
            }
            //换页 
            /*请补全该部分*/
        }

        ntu[page[i]] = -1;
        for(j=i+1; j<MAXN; j++)
            if(page[j] == page[i])
            {
                ntu[page[i]] = j;
                break;
            }
    }

    printf("\n OPT 算法, 访问失败页面数量为:  %d\n", fault_n);
    printf("               缺页率为 :  %.2lf\n", ((float)fault_n/MAXN));
}

int main()
{
    srand(time(NULL));
    welcome();

    int choice;
    while(1)
    {
        input_hint();
        scanf("%d", &choice);
        printf("\n");

        if(choice == 0)
        {
            printf("再见!!!\n");
            break;
        }
        if(choice == 1)
        {
            produce_inst();
            turn_page_address();
            printf("新的页面地址序列设置已完成!!!\n");
        }
        else if(choice == 2)
        {
            printf("请输入存储页面大小:  ");
            scanf("%d", &size);
        }
        else if(choice == 3)
            FIFO_solve();
        else if(choice == 4)
            LRU_solve();
        else if(choice == 5)
            OPT_solve();
        else
            printf("输入错误 !!! \n");
    }

    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

首先，我们需要补全FIFO、LRU和OPT算法的部分。我会逐个补充这些算法的缺失部分。

FIFO算法（已排序）

FIFO算法简单地按照页面的访问顺序进行替换，因此我们只需要记录当前的指针ptr，当遇到不在内存中的页面时，将其替换掉pin[ptr]中的页面，并更新ptr到下一个位置。

void FIFO_solve()
{
    ...
    // 继续执行剩下的指令
    ptr = 0; // 队列里最先进来的位置，即下一个要被替换的位置
    printf("缺页序列为：\n");
    j = 0;
    for (; i < MAXN; i++)
    {
        if (!in[page[i]])
        {
            // 替换内存中的页面
            in[pin[ptr]] = 0;
            in[page[i]] = 1;
            pin[ptr] = page[i];
            fault_n++;  // 缺页次数
            printf("%3d -> %3d\n", pin[ptr], page[i]);
        }
        else
        {
            // 已经在内存里则无需处理
            // printf("   **%3d**  ",page[i]); 
        }
        ptr = (ptr + 1) % size;  // 更新替换指针
    }
    ...
}

LRU算法

LRU算法需要维护一个链表，用于跟踪页面的最近使用情况。我们可以使用一个额外的数组ltu来保存每个页面最后一次使用的索引。当需要替换页面时，找到ltu数组中最小值对应的元素，然后替换它。

void LRU_solve()
{
    ...
    int ltu[MAXP]; // last_time_use
    int ti = 1;    // 模拟时间
    ...

    // 初始化lru链表
    for (j = 0; j < size; j++)
        ltu[j] = ti++;

    for (; i < MAXN; i++)
    {
        if (!in[page[i]])
        {
            // 找到lru页面
            min = ti;
            ptr = -1;
            for (j = 0; j < size; j++)
            {
                if (ltu[j] < min && in[pin[j]] == 1)
                {
                    min = ltu[j];
                    ptr = j;
                }
            }

            // 替换或写入
            if (pin[ptr] != -1)
            {
                in[pin[ptr]] = 0;  // 换出页面
                in[page[i]] = 1;   // 写入页面
                ltu[pin[ptr]] = ti++;
                ltu[ptr] = ti++;
                pin[ptr] = page[i];
            }
            else
            {
                in[page[i]] = 1;   // 新页面进入内存
                ltu[pin[size-1]] = ti++;
                pin[size-1] = page[i];
            }

            printf("%3d -> %3d\n", pin[ptr], page[i]);
            fault_n++;  // 缺页次数
        }
        else
        {
            // 页面已在内存中，更新其使用时间
            for (j = 0; j < size; j++)
                if (pin[j] == page[i])
                {
                    ltu[j] = ti++;
                    break;
                }
        }
    }
    ...
}

OPT算法

OPT算法是理论上的最优算法，它需要知道未来的页面需求，这在实际中是不可能的。但在这里，我们可以实现一个近似版本，根据已知的页面需求预测未来可能再次访问的页面。

void OPT_solve()
{
    ...
    int ntu[MAXP];  // next_time_use
    int fault_n = 0;
    int i, j, k = 0;
    ...

    // 预调页填满
    int ptr = 0;
    for (i = 0; i < MAXN && ptr < size; i++)
    {
        if (!in[page[i]])
        {
            in[page[i]] = 1;
            pin[ptr] = page[i];
            fault_n++;
            ptr++;
        }
    }

    // 初始化ntu数组 下次再使用页面序列
    for (j = i; j < MAXN && ptr < size; j++)
    {
        if (ntu[page[j]] == -1)
        {
            ntu[page[j]] = j;
            ptr++;
        }
    }

    int max;
    printf("缺页序列为：\n");
    for (; i < MAXN; i++)
    {
        if (!in[page[i]])
        {
            max = 0; ptr = 0;
            for (j = 0; j < size; j++)
            {
                if (ntu[pin[j]] == -1 || ntu[pin[j]] > i)
                {
                    ptr = j;
                    break;
                }
                if (ntu[pin[j]] > max)
                {
                    max = ntu[pin[j]];
                    ptr = j;
                }
            }
            // 换页
            in[pin[ptr]] = 0;
            in[page[i]] = 1;
            pin[ptr] = page[i];

            ntu[pin[ptr]] = -1;
            ntu[page[i]] = -1;
            for (j = i + 1; j < MAXN; j++)
                if (page[j] == page[i])
                {
                    ntu[page[i]] = j;
                    break;
                }

            printf("%3d -> %3d\n", pin[ptr], page[i]);
            fault_n++;  // 缺页次数
        }
    }

    ...
}

以上就是对三种页面淘汰算法的补全。现在，您可以运行这个程序并测试不同的页面淘汰策略了。注意，对于OPT算法，由于它依赖于未来页面的需求预测，这里的实现只是一个简单的近似，实际效果可能会因为预测不准确而不如其他算法。