虚拟存储

利用大容量外存来扩充内存，产生一个比有限的实际内存空间大的多的、逻辑的虚拟内存空间，简称虚存。
原理：程序部分装入内存便可运行，其他部分需要运行时再装入内存。

页式存储

将内存分成大小相等的许多区，每个区称为一个”物理页面“。
页面:将程序中的逻辑地址(也可称为虚拟地址)也进行分页，页的大小和物理页面大小一致。

逻辑地址

由虚拟页号和页内地址组成. 逻辑地址最少位数(二进制位) = 虚拟页号位数 + 页内地址位数

逻辑地址组成排列

虚拟地址从"0"开始(页号为"0"，页内地址也为"0")，当编址到2ⁿ-1时，第0页的页内地址的各位均为"1"，即占满一个页面。下一个地址为2ⁿ，这时页号部分就为"1"，而页内地址部分又恢复到"0"，表示进入了第一页，再继续顺序编址，此时页内地址0~(2ⁿ-1)时属于第一页

表格表示
一个物理页面

如下图所示

逻辑地址计算

假定地址用m个二进制表示，其中页内地址部分占用n个二进制，则最大程序可运行有多少页面

解题
由逻辑地址的组成部分可知，逻辑地址 = 虚拟页号 + 页内地址，也就是求页面(就是逻辑地址)。那么一块的长度为2ⁿ(因为要化成二进制，也就是2ⁿ， n就是位数), 也就是有2ⁿ字节，由逻辑地址的组成可知，页号就占了m - n 位，那么页面就为2(^m-n)

例题

设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，试问逻辑地址至少应为多少位()?  单选题
A. 4            B.11                   C. 15                      D.16  

解题
和上面的逻辑地址计算一样：逻辑地址位数 = 页号位数 + 页内地址位数
那么由逻辑地址的排列可知：16页为页号，化为二进制位2⁴，每页2048字节，化为二进制2¹¹，那么逻辑地址 = 页号 + 页内地址 = 15

物理内存的分配与回收

位示图

内存分配表由一张”位示图“组成，横轴位字号，竖轴为位号

假设内存的可分配区域被分成256个物理页面，则可用字长位32位的8个字作为”位示图“，在位示图中增加一个字节记录当前剩余的总空闲物理页面数，如图,初始化时系统在位示图中把操作系统占用物理页面所对应的位置设成1，其余位置均为0，剩余空闲物理页面数为可分配的空闲物理页面总数

内存分配与回收

分配

在位示图中找出空闲物理页面数，如果能满足，则分配，并把相应位置为1，计算物理页面号(块号)。

$$ 物理页面号=字号×字长＋位号 $$

回收

当归还物理页面时，计算归还页面在位示图中对应的位置，将1改为0。位号也可叫偏移量

例题

使用8个字(字长32位)组成的位示图来管理页式主存空间的分配与回收，“O”表示空闲，“1”表示占用。假定将位示图中字号为4，位号为5的空闲块分配出去，则该块的块号是()      单选
A. 100              B. 101                   C. 132                       D. 133

解题
由上面的公式可知：物理页面号 = 字号 * 字长 + 位号，那么 4 * 32 + 5 = 133

虚拟页式存储地址转换过程

页式存储管理的转换过程

页表

记录装入内存的逻辑页面与物理页面的对应关系
是硬件进行地址转换的依据

硬件支持

页表始址寄存器和页表长度寄存器;
分别用来存储正在运行程序的页表在内存的起始地址和页表的长度由程序拥有的页面数而定

地址转换过程

• (1）在执行检索前,先将页号与页表长度进行比较,若页号大于或等于页表长度,则地址越界.
• (2）若未出现越界错误,则将页表始址与页号和页表项长度的乘积相加,则找到该表项在页表中的位置,找到该页的物理页号. 看下面十进制计算公式
• (3）将有效地址的页内地址送入物理地址寄存器的块内地址字段中.

十进制计算

$$ 物理地址=物理页面号(也就是块号)∗块长+页内地址 $$
页内地址就是位移量

二进制/十六进制计算

物理页面号作为绝对地址的高位地址，页内地址作为它的地址部分。
如：逻辑地址5F6AH转为二进制位：0101 1111 0110 1010，页号位前面几位，页内地址后几位 可查看例题2

例题1

在一个页式存储管理系统中，页表内容如下图所示，若页的大小为4K，则地址转换机构将逻辑地址0转换成的物理地址为()。
A. 8192                 B. 4096                     C.2048                             D.1024

解题
由题目和图片可知，页的大小为4K，即4096，0对应的块号为2：那么2*4096 + 0 = 8192

例题2

逻辑地址(物理页面号)长度为16位，页面大小为4096字节，逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少?

解题
即把逻辑地址2F6AH转为二进制(因为是地址不是位)：0010 1111 0110 1010，物理页号为高位地址，16为转成位数2的4次方，那么就取前面的4位，为页号，页号为2对应的块号为11，则11的十六进制为B，则对应的物理地址(1011 1111 0110 1010 把前面4位为替换成块号的二进制)十六进制(因为题目逻辑地址是十六进制，结果也要是十六进制，最后H与0x一样表示为十六进制)BF6AH。和上一题不一样，逻辑地址为十进制，这一题为十六进制，所以采用十六进制计算

计算类型

十进制计算

逻辑地址为十进制，如：已知逻辑地址（例：[0,250]）求物理地址，那么可采用上面的公式：物理地址=物理页面号(也就是块号)∗块长+页内地址

例题

若在一分页存储管理系统中,某作业的页表如下所示。已知页面大小为1024字节,试将逻辑地址[0,100],[1,179],[2,785]和[3,1010],页内地址单位字节,转化为相应的物理地址。

解题：
由题可知：页面大小1024字节，逻辑地址为[0, 100]，而逻辑地址由虚拟页号 + 页内地址，
公式：物理地址 = 物理页号 * 块长 + 页内地址
那么计算可得：
[0, 100]的物理地址为：3 * 1024 + 100 = 3172
[1, 179]的物理地址为：5 * 1024 + 179 = 5299
[2, 785]的物理地址为：6 * 1024 + 785 = 6929
[3, 1010]的物理地址为：2 * 1024 + 1010 = 3058

十六进制/二进制计算

已知逻辑地址（十六进制、二进制等非十进制）求物理地址

例题

某虚拟存储器的用户空间共32个页面，每页1KB，主存16KB
问：(1)逻辑地址的有效位是______位；
    (2)物理地址需要______位；
    (3)假定某时刻系统为用户的第0,1,2,3页分别分配的物理块号为5,10,4,7，试将逻辑地址0A5CH和093CH变换为物理地址。

列表

解题

(1)
逻辑地址的有效位和上面一题一样：逻辑地址位数 = 虚拟页号位数 + 页内地址位数
 32页面转为：2⁵，每页1KB为：2¹⁰。那么5 + 10 = 15。15就是逻辑地址的有效位为15

(2)
物理地址就是内存总数：每页1KB为：2¹⁰。主存16KB为：2⁴。那么物理地址需要：10 + 4 = 14位

(3)
解题步骤

• 十六进制转为二进制
  0A5CH化为二进制为：1010 0101 1100。

• 找出页号和页内地址
  每页为2¹⁰，那么页内地址从右往左数10位以内就是页内地址，剩下的五位数(对应题目的32页->2⁵)就是页号(不足补零黑色表示，绿色表示页号，红色表示页内地址)：$\color{0}$ $\color{000 10}$ $\color{10 0101 1100}$，

• 将页号替换进去
  页号0010转化位十进制：2，那么2对应的块号为：4。化为二进制：0100，那么换进去：$\color{0}$ $\color{00100}$ $\color{1001011100}$(记得补码)。结果为：125CH

• 093CH也是上面步骤

OA5CH   页号：00010十进制为：2 对应的块号为4 化为二进制：0100
$\color{0}$ $\color{000 10}$ $\color{10 0101 1100}$
$\color{0}$ $\color{001 00}$ $\color{10 0101 1100}$
结果为：125CH

093CH   页号：0010十进制为：2 对应的块号为4 化为二进制：0100
$\color{0}$ $\color{000 10}$ $\color{01 0011 1100}$
$\color{0}$ $\color{001 00}$ $\color{01 0011 1100}$
结果为：113CH

例题1

若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。

解题
逻辑地址十进制公式：物理地址 = 物理页面号 * 块长 + 页内地址
1011：页号 = 1011/1024 = 0 位号 = 1011 % 1024 = 1011 物理地址 = 2 * 1024 + 1011 = 3059
2148: 页号 = 2148 / 1024 = 2 位号 = 2148 % 1024 = 100 物理地址 = 1 * 1024 + 100 = 1124
4000：页号 = 4000 / 1024 = 3 位号 = 4000 % 1024 = 928 物理地址 = 6 * 1024 + 928 = 7072
5012: 页号 = 5012 / 1024 = 4 位号 = 5012 % 1024 = 916 物理地址超出

例题2

某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下:

则逻辑地址0A5C(H)所对应的物理地址是什么?要求:写出主要计算过程。

解题

步骤：0A5C(H)化成二进制：101001011100 已知共32页面，则页号2⁵位 每页1KB，页内地址2¹⁰，那补码后，取前面五个位：000010，化为十进制为：2，那么所对应块号为：11，化为二进制：1011，并将其替换，然后转化为十六进制
补码后：$\color{000010}$ $\color{1001011100}$
替换后：$\color{001011}$ $\color{1001011100}$
则0A5C(H)对应的物理地址为：2E5C(H)

参考

• Sly_ame-操作系统-第四章存储器管理 计算题：已知逻辑地址求物理地址
• Cuzblind-《操作系统》——分页存储管理方式逻辑地址到物理地址的转换