【E 内存】2020上海高校程序设计竞赛暨第18届上海大学程序设计联赛夏季赛（同步赛）解题报告

E 内存

题目描述 虚拟存储器作为现代操作系统中存储器管理的一项重要技术，实现了内存扩充功能。但该功能并非是从物理上实际地扩大内存的容量，而是从逻辑上实现对内存容量的扩充,让用户所感觉到的内存容量比实际内存容量大得多。于是便可以让比内存空间更大的程序运行，或者让更多的用户程序并发运行。这样既满足了用户的需要，又改善了系统的性能。当用户看到自己的程序能在系统中正常运行时，他会认为，该系统所具有的内存容量一定比自己的程序大，或者说，用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉，是虚的，故人们把这样的存储器称为虚拟存储器。在页式虚拟存储系统中，虚拟空间被分成大小相等的页，称为逻辑页或虚页。主存空间也被分成同样大小的页，称为物理页或实页。程序要运行必须存在物理内存中，但虚拟内存比实际物理内存空间到大得多，因此只有一部分页面真正存在物理内存之中，其余页面都还存在外存。用户编制程序时使用的地址称为虚地址或逻辑地址，其对应的存储空间称为虚存空间或逻辑地址空间；而计算机物理内存的访问地址则称为实地址或物理地址，其对应的存储空间称为物理存储空间或主存空间。程序进行虚地址到实地址转换的过程称为程序的再定位。当要访问一个逻辑地址时，其对应的页面可能在主存中，也可能不在。如果在，那么就要把虚拟地址转换成为实址，再到物理内存中进行访问。如果不在，就要发出缺页中断。当前计算机的地址为 32 位二进制表示，按字节编址。虚存大小为 2ⁿ 字节，物理内存大小为 2^m 字节，页面大小为 2^p 字节。虚拟空间的的地址称为虚拟地址，虚拟地址分为两个字段:高位字段为虚页号，低位字段为页内地址。实存地址也分为两个字段：高位字段为实页号，低位字段为页内地址。同时页面大小都取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。如下图所示。

再如一个虚拟地址为 00000000000000000000001000111100 ，低 6 位为 111100 为页内地址，高 26 位为 00000000000000000000001000 ， 为页号，即为第 8 页。但根据上述描述，虚拟内存中的第 8 页不在主存中，要访问该地址就会发出缺页中断。TL;DR: 现给出主存各页面中存的对应的虚存页号，当程序提出要访一个逻辑地址时，请确定该地址所对应的物理地址，或发出中断信号。

输入描述 为了表示简洁，在测试数据中的地址都以 8 位大写十六进制数来表示一个 32 位二进制地址。第一行输入 3 个十进制整数 n, m, p (0<p<m≤n≤32,m−p≤14)，分别表示虚拟内存大小为 2ⁿ 字节，物理内存大小为 2^m 字节，每页大小为 2^p 字节。第二行输入 2^m-p 个十进制整数 a₀, a₁, ... a_2^m-p-1，分别代表当前主存第 i 页中存了虚拟内存的第 a_i 页。第三行输入一个十进制整数 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;
}