E 内存

题目描述 虚拟存储器作为现代操作系统中存储器管理的一项重要技术,实现了内存扩充功能。但该功能并非是从物理上实际地扩大内存的容量,而是从逻辑上实现对内存容量的扩充,让用户所感觉到的内存容量比实际内存容量大得多。于是便可以让比内存空间更大的程序运行,或者让更多的用户程序并发运行。这样既满足了用户的需要,又改善了系统的性能。当用户看到自己的程序能在系统中正常运行时,他会认为,该系统所具有的内存容量一定比自己的程序大,或者说,用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉,是虚的,故人们把这样的存储器称为虚拟存储器。在页式虚拟存储系统中,虚拟空间被分成大小相等的页,称为逻辑页或虚页。主存空间也被分成同样大小的页,称为物理页或实页。程序要运行必须存在物理内存中,但虚拟内存比实际物理内存空间到大得多,因此只有一部分页面真正存在物理内存之中,其余页面都还存在外存。用户编制程序时使用的地址称为虚地址或逻辑地址,其对应的存储空间称为虚存空间或逻辑地址空间;而计算机物理内存的访问地址则称为实地址或物理地址,其对应的存储空间称为物理存储空间或主存空间。程序进行虚地址到实地址转换的过程称为程序的再定位。当要访问一个逻辑地址时,其对应的页面可能在主存中,也可能不在。如果在,那么就要把虚拟地址转换成为实址,再到物理内存中进行访问。如果不在,就要发出缺页中断。当前计算机的地址为 32 位二进制表示,按字节编址。虚存大小为 2n 字节,物理内存大小为 2m 字节,页面大小为 2p 字节。虚拟空间的的地址称为虚拟地址,虚拟地址分为两个字段:高位字段为虚页号,低位字段为页内地址。实存地址也分为两个字段:高位字段为实页号,低位字段为页内地址。同时页面大小都取2的整数幂个字节。例如 n=10 ,m=8 ,p=6 ,当前物理内存中有 256 字节,每页大小 64 字节,共有4页,虚拟内存大小为 1024 字节,共有 16 页,物理内存第 [0,1,2,3] 页中对应存了虚拟内存的第 [1,11,14,7] 页。如一个虚拟地址为 00000000000000000000000111010100 ,低 6 位为 010100 为页内地址,高 26 位为 00000000000000000000000111 , 为页号,即为第 7 页。根据上述描述,虚拟内存中的第 7 页存放在主存中的第 3 页,要访问的数据存在主存第 3 页,页内地址为 010100的地方。故物理地址为 00000000000000000000000011010100。如下图所示。
E.png
再如一个虚拟地址为 00000000000000000000001000111100 ,低 6 位为 111100 为页内地址,高 26 位为 00000000000000000000001000 , 为页号,即为第 8 页。但根据上述描述,虚拟内存中的第 8 页不在主存中,要访问该地址就会发出缺页中断。TL;DR: 现给出主存各页面中存的对应的虚存页号,当程序提出要访一个逻辑地址时,请确定该地址所对应的物理地址,或发出中断信号。

输入描述 为了表示简洁,在测试数据中的地址都以 8 位大写十六进制数来表示一个 32 位二进制地址。第一行输入 3 个十进制整数 n, m, p (0<p<m≤n≤32,m−p≤14),分别表示虚拟内存大小为 2n 字节,物理内存大小为 2m 字节,每页大小为 2p 字节。第二行输入 2m-p 个十进制整数 a0, a1, ... a2m-p-1,分别代表当前主存第 i 页中存了虚拟内存的第 ai 页。第三行输入一个十进制整数 q (1≤q≤2333) ,代表询问的数量。接下来 q 行,每行输入一个 8 位十六进制数代表程序要访问的虚拟地址。

输出描述 对于每次询问,在一行输出一个十六进制数代表所对应的物理地址,或输出 interrupt! 代表发出缺页中断。

思路
一个标准的模拟题,没有动脑筋的地方,关键点在于位运算。具体看代码吧。

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}

const int MAXN=1000002;
long long n,m,p,zc[20000],Q,ans;

int main()
{
    read(n);
    read(m);
    read(p);
    long long tmpsx=pow(2ll,m-p);
    for (long long i=0;i<tmpsx;++i)
        scanf("%lld",&zc[i]);
    for (read(Q);Q;--Q)
    {
        ans=-1;
        long long xndz,xn2=0;
        scanf("%llX",&xndz);
        for (int i=0;i<p;++i)
        {
            xn2|=(xndz&1)<<i;
            xndz>>=1;
        }
        if(xndz>pow(2ll,n-p) || xn2>pow(2ll,m))
        {
            printf("interrupt!\n");
            continue;
        }
        for (long long i=0;i<tmpsx;++i)
            if(zc[i]==xndz)
            {
                ans=(i<<p)+xn2;
                break;
            }
        if(ans==-1) printf("interrupt!\n");
        else printf("%08llX\n",ans);
    }
    
    return 0;
}
©著作权归作者所有

发表评论

正在加载 Emoji