bzoj1206: [HNOI2005]虚拟内存 | jeffswt: the ac moments

Description

操作系统中一种重要的存储管理技术就是虚拟内存技术. 操作系统中允许进程同时运行, 也就是并行. 每个进程都有其相对独立的数据块 (进程运行的过程中将对其进行读写操作). 理想的情况下, 这些数据块都应该存放在内存中, 这样才能实现高效的读写操作. 但事实上, 内存的容量有限, 每个进程只能把一部分数据放在内存中, 为了解决这个矛盾, 提出了虚拟内存技术. 虚拟内存技术的基本原理是: 对进程而言, 内存空间是无限大的, 进程可以随意地读写数据, 而对操作系统内部而言, 利用外存来模拟扩充的内存空间, 进程要求访问某个内存单元时, 交由操作系统处理, 操作系统首先在内存中查找该单元是否存在, 如果存在, 查找成功, 否则转入外存查找 (一定存在于外存中). 就存储介质的物理性质而言, 内存的访问速度相对于外存要快得多, 因此对于每个进程来说操作系统应该把那些访问次数较多的数据存放在内存中, 而把那些访问次数很少的数据放在外存中. 如何选择内存中暂留的数据是一个很值得研究的问题, 下面介绍一个内存管理中比较常用的算法: 内存中的数据以页为基本存储单位, 进程的读写操作都针对页来进行. 实际内存空间被分割成 n 页, 虚拟内存空间的页数往往要多得多. 某一时刻, 进程需要访问虚存编号为 P 的页, 该算法的执行步骤如下:

首先在内存中查找, 如果该页位于内存中, 查找成功, 转 4, 否则继续下面的操作;
寻找内存中是否存在空页 (即没有装载任何数据页的页面), 若有, 则从外存中读入要查找页, 并将该页送至内存中的空页进行存储, 然后转 4, 否则继续下面的操作;
在内存中寻找一个访问次数最少的页面 (如果存在多个页面的访问次数同时为最少, 则选取最早读入数据进入内存的那个页面), 从外存中读入要查找页, 替换该页.
结束

所谓访问次数是指从当前页面进入内存到该时刻被访问的次数, 如果该页面以前进入过内存并被其它页面替换, 那么前面的访问次数不应计入这个时刻的访问次数中. 你的任务是设计一个程序实现上述算法. 测试数据将会提供 \(m\) 条读写内存的命令, 每条命题提供要求访问的虚拟内存页的编号 \(P\). 你的程序要求能够模拟整个 \(m\) 条命令的全部执行过程, 所有的命令是按照输入的先后执行的, 最开始的时候内存中的 \(n\) 页全为空.

Input

第 \(1\) 行为 \(n \lt 10000\) 和 \(m \lt 1000000\), 分别表示内存页数和读写内存命令条数. 接下来有 \(m\) 行, 其中第 \(i+1\) 行有一个正整数 \(P_i \leq 10^9\), 表示第 \(i\) 条读写内存命令需要访问的虚拟内存页的编号.

Output

仅包含一个正整数, 表示在整个模拟过程中, 在内存中直接查找成功的次数 (即上面的算法只执行步骤 1 的次数).

Sample Input

Sample Output

Explanation

是不是随便拿 STL 水一下就可以过了呢~

其实用各种 set map 维护一发就可以了...... 就是逻辑可能有点混乱, 而且不停申请内存和销毁内存的开销可能有点大 (不过我的程序常数一直就很大对不对).

其实我的程序还是比较好看懂的, 就是各种 access_t 的定义太奇葩 233

话说这样说到底可以提高程序可读性, 降低检索次数 (就是查看这个变量是干嘛的)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <set>

using namespace std;
typedef long long lli;
const int maxn = 10010;

typedef lli vmemaddr_t;
typedef int memaddr_t;
typedef int access_t;
typedef int loadtime_t;
const vmemaddr_t vmem_null = 0;
const memaddr_t mem_null = 0;

class VirtualMemoryManager
{
private:
    // Used to access memory address through virtual memory address
    map<vmemaddr_t, memaddr_t> vmem_to_mem;
    // Used to access virtual memory addresses through access counter
    map<access_t, map<loadtime_t, vmemaddr_t> > cnt_to_vmem;
    // Used to access virtual memory address stored in memory
    vmemaddr_t mem_to_vmem[maxn];
    // Used to store time variables for virtual memory addresses
    map<vmemaddr_t, access_t> vmem_to_cnt;
    map<vmemaddr_t, loadtime_t> vmem_to_tim;
    // Global stati
    set<memaddr_t> empty_mem;
    loadtime_t atomic_time;
    int n;
protected:
    bool cache_hit(vmemaddr_t vma)
    {
        if (vmem_to_mem[vma] > 0)
            return true;
        return false;
    }
    // void unload_memory(memaddr_t ma)
    // {
    //     vmemaddr_t vma = mem_to_vmem[ma];
    //     access_t act = vmem_to_cnt[vma];
    //     loadtime_t ltt = vmem_to_tim[vma];
    //     map<loadtime_t, vmemaddr_t>& lvm = cnt_to_vmem[act];
    //     lvm.erase(lvm.find(ltt));
    //     if (lvm.empty())
    //         cnt_to_vmem.erase(cnt_to_vmem.find(act));
    //     // Unloading indices
    //     mem_to_vmem[ma] = 0;
    //     vmem_to_mem.erase(vmem_to_mem.find(vma));
    //     vmem_to_cnt.erase(vmem_to_cnt.find(vma));
    //     vmem_to_tim.erase(vmem_to_tim.find(vma));
    //     empty_mem.insert(ma);
    //     return ;
    // }
public:
    bool access_memory(vmemaddr_t vma)
    {
        // printf("ACCESSING VMEM ADDRESS 0x%lld...\n", vma);
        // If cache hit, update counter and leave.
        if (this->cache_hit(vma)) {
            access_t act = vmem_to_cnt[vma];
            loadtime_t ltt = vmem_to_tim[vma];
            // printf("  CACHE HIT: ACCESSED %d, INJECTED @ %d\n", act, ltt);
            // Unloading original value.
            map<loadtime_t, vmemaddr_t>& lvm = cnt_to_vmem[act];
            lvm.erase(lvm.find(ltt));
            if (lvm.empty())
                cnt_to_vmem.erase(cnt_to_vmem.find(act));
            // Loading new value.
            act += 1;
            if (cnt_to_vmem.find(act) == cnt_to_vmem.end()) {
                map<loadtime_t, vmemaddr_t> lvm;
                cnt_to_vmem[act] = lvm;
            }
            cnt_to_vmem[act][ltt] = vma;
            // Finished loading. Updating indexes.
            vmem_to_cnt[vma] = act;
            return true;
        }
        // Insert into memory, if doesn't exist.
        // Freeing memory for extra spaces
        if (empty_mem.empty()) {
            // printf("  MEMORY FULL, LOOKING FOR EXCESSIVE SPACE\n", vma);
            map<access_t, map<loadtime_t, vmemaddr_t> >::iterator it1
                = cnt_to_vmem.begin();
            map<loadtime_t, vmemaddr_t>::iterator it2
                = it1->second.begin();
            vmemaddr_t vma = it2->second;
            // Eradicating from structure
            // printf("  DUMPING 0x%lld INTO PAGEFILE... ", vma);
            // this->unload_memory(vma);
            memaddr_t ma = vmem_to_mem[vma];
            access_t act = vmem_to_cnt[vma];
            loadtime_t ltt = vmem_to_tim[vma];
            it1->second.erase(it2);
            if (it1->second.empty())
                cnt_to_vmem.erase(it1);
            // printf("OK\n  REMOVING INDICES... ");
            mem_to_vmem[ma] = 0;
            vmem_to_mem.erase(vmem_to_mem.find(vma));
            vmem_to_cnt.erase(vmem_to_cnt.find(vma));
            vmem_to_tim.erase(vmem_to_tim.find(vma));
            empty_mem.insert(ma);
            // printf("OK\n");
        }
        // Injecting indices
        access_t act = 1;
        loadtime_t ltt = atomic_time;
        // printf("  INJECTING VMEM WITH SETTINGS %d, @ %d\n", act, ltt);
        vmem_to_cnt[vma] = act;
        vmem_to_tim[vma] = ltt;
        // Injecting into free memory
        memaddr_t ma = *empty_mem.begin();
        empty_mem.erase(empty_mem.begin());
        vmem_to_mem[vma] = ma;
        mem_to_vmem[ma] = vma;
        if (cnt_to_vmem.find(act) == cnt_to_vmem.end()) {
            map<loadtime_t, vmemaddr_t> lvm;
            cnt_to_vmem[act] = lvm;
        }
        cnt_to_vmem[act][ltt] = vma;
        // printf("  MEMORY CACHING SUCCEEDED\n");
        return false;
    }
    void increment_atomic_time(void)
    {
        atomic_time += 1;
        return ;
    }
    void init(int n_)
    {
        this->n = n_;
        atomic_time = 1;
        for (int i = 1; i <= n; i++) {
            vmem_to_mem[i] = 0;
            empty_mem.insert(i);
        }
        return ;
    }
} vmm;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    vmm.init(n);
    int res = 0;
    for (int i = 1; i <= m; i++) {
        vmemaddr_t vma;
        scanf("%lld", &vma);
        res += vmm.access_memory(vma);
        vmm.increment_atomic_time();
    }
    printf("%d\n", res);
    return 0;
}