一道数据结构习题

题目要求：设存储器中有m个物理块（块号为1…m）。一个进程分为n个大小相等的页面（页面号为1…n），执行进程时要对访问各个页面，每个物理块存储一个页面，当n>m时，有时当前要访问的页面不在物理块中，则若有空闲物理块时，当前要访问的页面放入空闲物理块中，否则要淘汰物理块中的某一个页面进行置换。
赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，给定页面号引用序列，若没有空闲物理块时，选择现有物理块中的页面中其t值最大的页面予以淘汰进行置换。

8 个解决方案

#1

这个问题用什么算法比较好呢？

#2

去看看操作系统中的页面置换算法

#3

若m=4,n=17

1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4
的结果应该是怎样的？

是这样的吗？
1,1,1,1,1,1,1,1,1,1,1,5,5,5,5,5,5
,0,0,0,0,0,0,0,0,0,0,0,4,4,4,4,4
, , , ,2,2,2,2,2,8,8,8,8,3,3,3,3
, , , , ,4,4,4,4,4,7,7,7,7,2,2,2

#4

晕，数据结构关系到操作系统了，，还没有学，看来任重道远呀，，

#5

哪位能具体解释下，是不是LRU算法？

#6

参考“计算机系统结构”

#7

或者操作系统

#8

经多人指点后写出的，不知道有没有错误，
在TC下运行是正常的。
#include <stdio.h>
#include <stdlib.h>
#define M 4   /*M个物理块*/
#define N 17  /*N个页面*/
typedef struct
{
    int page;   /*记录页面号*/
    int time;  /*记录调入内存时间*/
}Block;
Block b[M];
int t[M][N];
void Init(Block *b,int t[M][N])
{
    int i,j;
    for(i=0;i<M;i++)
    {
        b[i].page=-1;
        b[i].time=M-1-i;
    }
    for(i=0;i<M;i++)
        for(j=0;j<N;j++)
            t[i][j]=-1;

}
int GetMax(Block *b)
{
    int i;
    int max=-1;
    int tag=0;
    for(i=0;i<M;i++)
    {
        if(b[i].time>max)
        {
            max=b[i].time;
            tag=i;
        }
    }
    return tag;
}
int Equation(int hit,Block *b)
{
    int i;
    for(i=0;i<M;i++)
    {
        if (hit==b[i].page)
            return i;
    }
    return -1;
}
void Lru(int hit,Block *b)
{
    int i,val;
    val=Equation(hit,b);
    if(val>=0)
    {
        b[val].time=0;
        for(i=0;i<M;i++)
            if(i!=val)
                b[i].time++;
    }
    else
    {
        val=GetMax(b);
        b[val].page=hit;
        b[val].time=0;
        for(i=0;i<M;i++)
            if(i!=val)
                b[i].time++;
    }
}
int main(void)
{
    int a[N]={1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4};
    int i,j;
    printf("%d blocks,%d pages.\n",M,N);
    printf("Pages:\n");
    for(i=0;i<N;i++)
        printf("%3d",a[i]);
    Init(b,t);
    for(i=0;i<N;i++)
    {
        Lru(a[i],b);
        t[0][i]=a[i];
        for(j=0;j<M;j++)
            t[j][i]=b[j].page;
    }
    printf("\nThe result is:\n");
    for(i=0;i<M;i++)
    {
        for(j=0;j<N;j++)
        {
            if(t[i][j]==-1)
                printf("%3c",0x20);
            else printf("%3d",t[i][j]);
        }
        printf("\n");
    }
    system("pause");
    return 0;
}

#1