非连续分配管理方式之基本分页存储管理

连续分配：为用户进程分配的必须是一个连续的内存空间。
非连续分配：为用户进程分配的可以是一些分散的内存空间。

基本分页存储管理的思想∶把进程分页，各个页面可离散地放到各个的内存块中。

1.分页存储

1.内存空间分区

• 将内存空间分为一个个大小相等的分区（比如:每个分区4KB），
• 每个分区就是一个“页框”(页框=页帧=内存块=物理块=物理页面）。
• 每个页框有一个编号，即“页框号”(页框号=页帧号=内存块号=物理块号=物理页号)，
• 页框号从0开始。

2.进程的逻辑地址空间

• 将进程的逻辑地址空间也分为与页框大小相等的一个个部分，
• 每个部分称为一个“页”或“页面”。
• 每个页面也有一个编号即“页号”，
• 页号也是从0开始。

操作系统以页框为单位为各个进程分配内存空间。
进程的每个页面分别放入一个页框中。
也就是说，进程的页面与内存的页框有一一对应的关系。
各个页面不必连续存放，可以放到不相邻的各个页框中。

2.数据结构：页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。
注:页表通常存在PCB（进程控制块）中。

1.每个页表项占多少字节

Eg:假设某系统物理内存大小为4GB，
页面大小为4KB，则每个页表项至少应该为多少字节?

页表项连续存在，因此页号可以隐含的，不占用存储空间（类比数组）
由于页号是隐含的，因此每个页表项占3B，存储整个页表至少需要$3\ast (n+1)B$

注意:

• 页表记录的只是内存块号，而不是内存块的起始地址.
• J号内存块的起始地址=J*内存块大小

2.实现地址的转换

将进程地址空间分页之后，操作系统该如何实现逻辑地址到物理地址的转换?

1.特点:

虽然进程的各个页面是离散存放的，但是页面内部是连续存放的。

2.如果要访问逻辑地址A，则

①确定逻辑地址A对应的“页号”P
②找到P号页面在内存中的起始地址（需要查页表)
③确定逻辑地址A的“页内偏移量”W

3.逻辑地址的计算

逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W

4.例题

在某计算机系统中，页面大小是50B。
某进程逻辑地址空间大小为200B，则逻辑地址110对应的页号、页内偏移量是多少?

• 页号=逻辑地址/页面长度（取除法的整数部分)
• 页内偏移量=逻辑地址%页面长度（取除法的余数部分）
• 页号=110/ 50=2
• 页内偏移量=110%50= 10
• 逻辑地址可以拆分为(页号，页内偏移量)
• 通过页号查询页表，可知页面在内存中的起始地址
• 页面在内存中的起始地址+页内偏移量=实际的物理地址

在计算机内部,地址是用二进制表示的:如果页面大小刚好是2的整数幂，
则计算机硬件可以很快速的把逻辑地址拆分成（(页号，页内偏移量)

结论:
如果每个页面大小为$2^{k}B$，用二进制数表示逻辑地址,
则末尾K位即为页内偏移量，其余部分就是页号。

5.页面大小刚好是2的整数幂的好处

• ①逻辑地址的拆分更加迅速：如果每个页面大小为$2^k\ast B$，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为2的整数幂，计算机硬件就可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法运算，从而提升了运行速度。
• ②物理地址的计算更加迅速：根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。

3.逻辑地址结构

分页存储管理的逻辑地址结构如下所示：

地址结构包含两个部分：前一部分为页号，后一部分为页内偏移量W。
在上图所示的例于中，地址长度为32位，其中0-11位为“页内偏移量”，或称“页内地址”;
12~31位为“页号”。

• 如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是$2^k$个内存单元
• 如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有$2^M$个页面