虚拟存储页算法

① 什么是虚拟存储器请求式分页存储管理常用的页面置换算法有哪些试比较他们的性能。

虚拟存储器(Virtual Memory)：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。
最佳置换算法（OPT）（理想置换算法）
先进先出置换算法（FIFO）：
最近最久未使用（LRU）算法
Clock置换算法（LRU算法的近似实现）
最少使用（LFU）置换算法

② 目前大多数虚拟存储系统采用什么算法

大多数虚拟存储系统采用OPT（优化）淘汰算法。根据相关信息展示，常用的虚拟存储系统由主存、辅存两级存储器组成，其中辅存是大容量的磁表面存储器，其采用OPT（优化）淘汰算法。

③ 虚拟存储方式都有哪些

目前虚拟存储的发展尚无统一标准，从虚拟化存储的拓扑结构来讲主要有两种方式：即对称式与非对称式。对称式虚拟存储技术是指虚拟存储控制设备与存储软件系统、交换设备集成为一个整体，内嵌在网络数据传输路径中；非对称式虚拟存储技术是指虚拟存储控制设备独立于数据传输路径之外。从虚拟化存储的实现原理来讲也有两种方式；即数据块虚拟与虚拟文件系统。具体如下： 图1对称式虚拟存储解决方案的示意图
在图1所示的对称式虚拟存储结构图中，存储控制设备 High Speed Traffic Directors（HSTD）与存储池子系统Storage Pool集成在一起，组成SAN Appliance。可以看到在该方案中存储控制设备HSTD在主机与存储池数据交换的过程中起到核心作用。该方案的虚拟存储过程是这样的：由HSTD内嵌的存储管理系统将存储池中的物理硬盘虚拟为逻辑存储单元（LUN），并进行端口映射（指定某一个LUN能被哪些端口所见），主机端将各可见的存储单元映射为操作系统可识别的盘符。当主机向SAN Appliance写入数据时，用户只需要将数据写入位置指定为自己映射的盘符（LUN），数据经过HSTD的高速并行端口，先写入高速缓存，HSTD中的存储管理系统自动完成目标位置由LUN到物理硬盘的转换，在此过程中用户见到的只是虚拟逻辑单元，而不关心每个LUN的具体物理组织结构。该方案具有以下主要特点：
（1）采用大容量高速缓存，显着提高数据传输速度。
缓存是存储系统中广泛采用的位于主机与存储设备之间的I/O路径上的中间介质。当主机从存储设备中读取数据时，会把与当前数据存储位置相连的数据读到缓存中，并把多次调用的数据保留在缓存中；当主机读数据时，在很大几率上能够从缓存中找到所需要的数据。直接从缓存上读出。而从缓存读取数据时的速度只受到电信号传播速度的影响（等于光速），因此大大高于从硬盘读数据时盘片机械转动的速度。当主机向存储设备写入数据时，先把数据写入缓存中，待主机端写入动作停止，再从缓存中将数据写入硬盘，同样高于直接写入硬盘的速度
（2）多端口并行技术，消除了I/O瓶颈。
传统的FC存储设备中控制端口与逻辑盘之间是固定关系，访问一块硬盘只能通过控制它的控制器端口。在对称式虚拟存储设备中，SAN Appliance的存储端口与LUN的关系是虚拟的，也就是说多台主机可以通过多个存储端口（最多8个）并发访问同一个L

④ 虚拟页式存储系统

二维数组在内存中表现为连续的数据，100行 150列数据，则有15000个数据，存放在100个页面中，因此，缺页中断为100次

⑤ lru的算法是什么

lru的算法是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

对于虚拟页式存储，内外存信息的替换是以页面为单位进行的——当需要一个放在外存的页面时，把它调入内存，同时为了保持原有空间的大小，还要把一个内种调动越少，进程执行的效率也就越高。

硬件支持

LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。

寄存器

为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为：

R = Rn-1 Rn-2 Rn-3…R2 R1 R0。

⑥ 储存管理中,分页式虚拟储存管理的页面淘汰算法有

储存管理中，分页式虚拟储存管理的页面淘汰算法有先进先出法，最近最少使用页面先淘汰，最优淘汰算法。最优淘汰算法(OPT)：系统预测作业今后要访问的页面，淘汰页是将来不被访问的页面或者在最长时间后才被访问的页面。它保证有最少的缺页率，但它实现困难，只能通过理论分析用来衡量其它算法的优劣。

⑦ Windows98/XP的虚拟存储器采用的页面调度算法是什么

1 随机算法
用软件或硬件随机数产生器确定替换的页面。
2 先进先出
先调入主存的页面先替换。
3 近期最少使用算法
替换最长时间不用的页面。
4 最优算法
替换最长时间以后才使用的页面。这是理想化的算法，只能作为衡量其他各种算法优劣的标准。

⑧ 计算机组成原理——虚拟存储器

（1）程序员在比实际主存大得多的逻辑地址空间中编写程序

（2）程序执行时，把当前需要的程序段和数据块掉入主存，其他暂不使用的放在磁盘上

（3）执行指令时，通过硬件将逻辑地址转化为物理地址。虚拟地址高位为虚页号，低位为页内偏移地址

（4）当程序发生数据访问或程序访问失效(缺页时)，由操作系统把信息从磁盘调入主存中

    （1）基本思想：

        内存被分成固定长度且长度较小的存储块（页框，实页，物理页）

        每个进程也被划分为固定长度的程序块（页，虚页，逻辑页）

        通过页表，实现逻辑地址想物理地址的转化

    （2）逻辑地址

        程序中指令所使用的地址（进程所在地址空间）

    （3）物理地址

        存放指令或数据的实际内存地址

（1）与“cache-主存”层次相比，页大小远比cache的行大小要大（windows中的页位4k）

（2）采用全相联映射方式：磁盘中的任意一个页能用射到内存中的任意一个页

    因为缺页导致中断时，操作系统从磁盘拿数据通常要耗费几百万个时钟周期。增大页大小，可以减少缺页中断

（3）为什么让软件处理“缺页”

    因为访问磁盘需要好粉几百万个时钟周期，硬件即使能立刻把地址打给磁盘，磁盘也不能立即响应

（4）为什么地址转换用硬件实现

    硬件实现地址转换可以加快指令的执行速度

（5）为什么页写会策略采用write back

    避免频繁的慢速磁盘访问

页表的首地址放在基址寄存器。采用基址寻址方式

每个页表项前面有一个虚页号：从0开始递增的序号。页表项又分为几个结构：

（1）装入位：该页是否在内存中

（2）修改位：该也在内存中是否被修改

（3）替换控制位：用于clock算法

（4）其他

（5）实页号（8进制）

（1）一次磁盘引用需要访问几次主存？2次，一次查页表，一次查物理地址。于是，把经常查的页表放到cache中。这种在cache页表项组成的页表称为TLB（Translation Lookside Buffer）

（2）TLB的页表结构：tag + 主存中的页表项

当采用全相连映射时，tag为页表项前面的虚页号。需要把tag和虚页号一一比较

当采用组相联映射时，tag被分为tag+index，虚页号的高位为tag，虚页号的低位为index，做组内索引(属于组内第几行)

    1.段式存储是根据程序逻辑，给程序分段。使得每段大小不同。这种虚拟地址划分方法适合程序设计

    2.段式存储的虚拟地址由段号和段内偏移地址组成。段式虚拟存储器到物理地址的映射通过段表实现

    3.段式虚拟存储会造成空页

    1.段页式虚拟存储，先把程序按照逻辑分成段，再把每段分成固定大小的页。

    2.程序对主存的调入调出是按照页面进行的；但他有可以根据段实现共享和保护

    3.缺点是段页式虚拟地址转换成物理地址需要查询2个表：段表和页表。段表找到相应页表的位置，页表找到想也页的位置

    4.段页式细腻地址的结构可以为以下形式：

            程序地址： 用户号(进程pid) | 段号 | 页号 | 页内偏移地址

（1）某计算机的cache块工16块，采用二路组相联映射方式，每个主存块大小为32字节，按照字节编制。则主存129号单元的主存块硬装如刀cache的组号是：（C）A、0      B、2      C、4      D、6

解：二路组相联，所以每组2块，共有16/2=8组，所以组号占3位。

      每块32字节，所以块内地址占5位。

      129转化为二进制：1000 0001：前3位为组号，100：=4

（2）假设用若干个2K4位的芯片组成一个8K8位的存储器，则地址0B1FH所在芯片的最小地址为：

解：用2片组成一行，共4行，所以片选地址占2位。片内地址有2k=211，所以占11位

      0B1FH：000|0 1|011 0001 1111 这三段为前缀，片选地址，片内地址。

      该片芯片的最小地址是片内地址全0：000|0 1|000 0000 0000 = 0800H

（3）某计算机的主存地址空间大小为256MB，按字节编址，指令cache和数据cache分离，均有8个cache行，每行大小为64B，数据cache采用直接映射方式，现有两个程序A，B对数组int a[256][256]进行遍历，程序A按行遍历，程序B按列遍历。假定int类型数据用32位补码表示，数组a按行优先方式存储，其地址为320（十进制）。

问：(1) 若不考虑cache一致性维护和替换算法所需的控制位，则数据cache的总容量占多少？

      (2) 数组元素a[0][31]和a[1][1]各自所在主存块对应的cache行号分别为多少（cache从0行开始）？

      (3)程序A和B的数据访问命中率各自为多少？哪个程序的执行时间更短？

解：(1) 因为cache的总容量是cache每行的数据存储大小+tag位+数据是否有效位+其他一致性控制位。

          主存地址空间256MB，占28位。直接映射方式，8行，行号占3位。每行64B，所以块内地址占6位，因此，tag占28-3-6=19位

          每行有一个数据有效位。因此，cache共（19+1+648）8 = 532字节

      (2) 因为int类型占32位，所以一个int占4B。a[0][31] = 320 + 314 = 444 a1 = 320 + 4(256+1) = 1348。

          块内地址占6位，直接映射下行号占3位，因此444 = 110 | 111100，所以行号为6

          1348 = 10 | 101 | 000100，所以行号为5

      (3) 因为1行cache占64B，每个int数占4B，所以一行有16个数。第一个数会因cache缺失而不命中，然后调入cache。，使得后面的15个int访问全部命中。所以命中率为1516 对于程序B，每次调入16个数，小于数组每行的128个元素，因此每次都不会命中，命中率为0