bzoj1206 [HNOI2005]虚拟内存

bzoj1206 [HNOI2005]虚拟内存

​​ Description

操作系统中一种重要的存储管理技术就是虚拟内存技术。操作系统中允许进程同时运行，也就是并行。每个进程都有其相对独立的数据块（进程运行的过程中将对其进行读写操作）。理想的情况下，这些数据块都应该存放在内存中，这样才能实现高效的读写操作。但事实上，内存的容量有限，每个进程只能把一部分数据放在内存中，为了解决这个矛盾，提出了虚拟内存技术。虚拟内存技术的基本原理是：对进程而言，内存空间是无限大的，进程可以随意地读写数据，而对操作系统内部而言，利用外存来模拟扩充的内存空间，进程要求访问某个内存单元时，交由操作系统处理，操作系统首先在内存中查找该单元是否存在，如果存在，查找成功，否则转入外存查找（一定存在于外存中）。就存储介质的物理性质而言，内存的访问速度相对于外存要快得多，因此对于每个进程来说操作系统应该把那些访问次数较多的数据存放在内存中，而把那些访问次数很少的数据放在外存中。如何选择内存中暂留的数据是一个很值得研究的问题，下面介绍一个内存管理中比较常用的算法：内存中的数据以页为基本存储单位，进程的读写操作都针对页来进行。实际内存空间被分割成n页，虚拟内存空间的页数往往要多得多。某一时刻，进程需要访问虚存编号为P的页，该算法的执行步骤如下： a. 首先在内存中查找，如果该页位于内存中，查找成功，转d，否则继续下面的操作； b. 寻找内存中是否存在空页（即没有装载任何数据页的页面），若有，则从外存中读入要查找页，并将该页送至内存中的空页进行存储，然后转d，否则继续下面的操作； c. 在内存中寻找一个访问次数最少的页面（如果存在多个页面的访问次数同时为最少，则选取最早读入数据进入内存的那个页面），从外存中读入要查找页，替换该页。 d. 结束所谓访问次数是指从当前页面进入内存到该时刻被访问的次数，如果该页面以前进入过内存并被其它页面替换，那么前面的访问次数不应计入这个时刻的访问次数中。你的任务是设计一个程序实现上述算法。测试数据将会提供m条读写内存的命令，每条命题提供要求访问的虚拟内存页的编号P。你的程序要求能够模拟整个m条命令的全部执行过程，所有的命令是按照输入的先后执行的，最开始的时候内存中的n页全为空。 Input

第1行为n<10000和m<1000000，分别表示内存页数和读写内存命令条数。接下来有m行，其中第i+1行有一个正整数Pi<=10^9，表示第i条读写内存命令需要访问的虚拟内存页的编号。 Output

仅包含一个正整数，表示在整个模拟过程中，在内存中直接查找成功的次数（即上面的算法只执行步骤a的次数）。 Sample Input 3 8 1 1 2 3 4 2 5 4 Sample Output 1 今天早晨起来忽然看到以前一个没有写过的题 改了改 做法呢就是纯模拟 用一个map来离散化 然后priority_queue用来把我访问次数最少的找出来 做了个优化就是如果以前存在那么我就先不去改动 当空间满了需要去弹出的时候我再依次把所有的都更新正确了 然后再决定弹哪个内存

#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。