【操作系统】分页存储管理方式

布满荆棘的人生 2022-07-14 14:18 854阅读 0赞

# 离散分配方式 #

连续分配存储管理方式产生的问题：

*  要求连续的存储区
 *  碎片问题

变连续分配为离散分配，允许将作业离散放到多个不相邻接的分区中。

*  分页式存储管理：离散分配的基本单位是页
 *  分段式存储管理：离散分配的基本单位是段
 *  段页式存储管理：离散分配的基本单位是段、页

# 页面和物理块 #

空间划分

*  将一个用户进程的地址空间（逻辑空间）划分成若干个大小相等的区域，称为页或页面，各页从 0 开始编号。
 *  内存空间也分成若干个与页大小相等的区域，称为块（物理块）或页框（frame） ，同样从 0 开始编号。

内存分配

*  在为进程分配内存时以块为单位，将进程中若干页装入到多个不相邻的块中，最后一页常装不满一块而出现页内碎片。

# 地址结构 #

![图示][SouthEast]

已知逻辑地址求页号和页内地址

给定一个逻辑地址空间中的地址为 A，页面的大小为L，则页号 P 和页内地址 d（从 0 开始编号）可按下式求得：

![图示][SouthEast 1]

其中，INT 是整除函数，mod 是取余函数。

例：系统的页面大小为 1 KB，设 A = 2170 B，则由上式可以求得 P = 2，d = 122。

# 页表 #

为了便于在内存找到进程的每个页面所对应块，分页系统中为每个进程配置一张页表，进程逻辑地址空间中的每一页，在页表中都对应有一个页表项。

页表存放在内存中，属于进程的现场信息。  
用途：1.记录进程的内存分配情况 2.实现进程运行时的动态重定位。  
访问一个数据需访问内存 2 次 (页表一次，内存一次)。  
页表的基址及长度由页表寄存器给出。  
![图示][SouthEast 2]

![图示][SouthEast 3]

# 页面大小 #

若页面较小

*  减少页内碎片和总的内存碎片，有利于提高内存利用率。
 *  每个进程页面数增多，使页表长度增加，占用内存较大。
 *  页面换进换出速度将降低。

若页面较大

*  每个进程页面数减少，页表长度减少，占用内存较小。
 *  页面换进换出速度将提高。
 *  增加页内碎片，不利于提高内存利用率。

# 基本分页存储管理方式 #

在分页存储管理方式中，如果不具备页面对换功能，不支持虚拟存储器功能，这种存储管理方式称为纯分页或基本分页存储管理方式。

在调度作业运行时，必须将它的所有页面一次调入内存，但逻辑上连续的各个页所对应的内存块可以不连续。

特殊的固定分区 + 离散分配

# 地址变换机构 #

地址变换机构

*  将用户地址空间中的逻辑地址变换为内存空间中的物理地址。
 *  实现逻辑地址向物理地址的转换（页号 ⇒ 块号）
 *  地址变换借助页表来完成。

地址变换机构种类

*  基本的地址变换机构
 *  具有快表的地址变换机构

# 基本地址变换机构 #

地址变换借助页表来完成，页表驻留内存。

为了提高地址变换的速度，系统中设置一个页表寄存器PTR (Page-Table Register)。

每个进程对应一页表，其信息（如长度、始址）放在PCB 中，执行时将其装入页表寄存器。

在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。

# 基本地址变换机构 #

当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址（相对地址）分为页号和页内地址两部分。

将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间，产生地址越界中断。

将页表始址与页号和页表项长度的乘积相加，得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。

将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。

![图示][SouthEast 4]

*  逻辑地址: 把相对地址分为页号和页内地址两部分。
 *  越界中断: 页号与页表长度做比较。
 *  页表定位：页表始址 + 页号 × 页表项长度。\{查询页表：读出块号。
 *  物理地址：块号 + 块内地址。 （块内地址 = 页内地址）

![图示][SouthEast 5]

# 地址变换例题 #

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

![图示][SouthEast 6]

设页号为 P，页内位移为 W，逻辑地址为 A，内存地址为 M，页面大小为 L，则  
P = int ( A / L )  
W = A mod L  
对于逻辑地址 1011  
P=int(1011/1024)=0  
W=1011 mod 1024=1011  
A=1011=(0,1011)  
查页表第 0 页在第 2 块，所以物理地址为 M=1024\*2+1011= 3059。

![图示][SouthEast 7]

对于逻辑地址为 2148  
P= int (2148/1024)=2  
W=2148 mod 1024=100  
A=2148=(2,100)  
查页表第 2 页在第 1 块，所以物理地  
址为 M=1024\*1+100=1124。  
对于逻辑地址 5012  
P= int ( 5012/1024)=4  
W=5012 mod 1024=916  
页号超过页表长度，该逻辑地址非法。

例：存储器的用户空间共有 32 个页面，每页 1KB，内存16KB。假定某时刻系统为用户的第 0、1、2、3 页分别分配的物理块号为 5、10、4、7，试将逻辑地址 0A5C 和093C 变换为物理地址。

![图示][SouthEast 8]

# 具有快表的地址变换机构 #

基本的地址变换机构存在的问题

*  地址变换速度低（两次访问内存）

具有快表的地址变换机构

*  目的：为提高地址变换速度。
 *  快表：又称为联想寄存器、联想存储器 (AssociativeMemory) 、IBM-TLB (Translation Lookaside Buffer)。
 *  快表是一种特殊的高速缓冲存储器（Cache） ，内容是页表中的一部分或全部内容。
 *  CPU 产生逻辑地址的页号，首先在快表中寻找，若命中就找出其对应的物理块；若未命中，再到页表中找其对应的物理块，并将之复制到快表。若快表中内容满，则按某种算法淘汰某些页。

![图示][SouthEast 9]

![图示][SouthEast 10]

![图示][SouthEast 11]

# 访问内存的有效时间 #

有效访问时间(Effective Access Time ,EAT) 是指从给定逻辑地址，经过地址变换，到在内存中找到对应物理地址单元并取出数据所用的总时间。

基本地址变换机构

![图示][SouthEast 12]

具有快表的地址变换机构

![图示][SouthEast 13]

例：有一页式系统，其页表存放在内存中。（1）如果对内存的一次存取需要 100ns，试问实现一次页面访问的存取时间是多少？（2）如果有快表，对快表的一次存取需要20ns, 平均命中率为 85%，试问此时的存取时间为多少？

页表放内存中，则实现一次页面访问需 2 次访问内存。  
所以实现一次页面访问的存取时间为：100ns\*2=200ns

系统有快表，则实现一次页面访问的存取时间为：  
0.85\*(20ns+100ns)+(1-0.85)\*(20ns+2\*100ns)=135ns

# 多级页表 #

若逻辑地址空间很大 (2^32 ∼2^64 ) ，则划分的页比较多，页表就很大，占用的存储空间大（要求连续） ，实现较困难。

例如，对于 32 位逻辑地址空间的分页系统，如果规定页面大小为 4 KB 即 2^12 B，则在每个进程页表就由高达2^20 页组成。设每个页表项占用一个字节，每个进程仅仅页表就要占用 1 MB 的内存空间。

解决问题的方法

*  动态调入页表: 只将当前需用的部分页表项调入内存，其余的需用时再调入。
 *  多级页表

## 两级页表 ##

将页表再进行分页，离散地将各个页表页面存放在不同的物理块中，同时也再建立一张外部页表用以记录页表页面对应的物理块号。

正在运行的进程，必须把外部页表调入内存，而动态调入内部页表。只将当前所需的一些内层页表装入内存，其余部分根据需要再陆续调入。

![图示][SouthEast 14]

![图示][SouthEast 15]

![图示][SouthEast 16]

将外层页表再进行分页，也将各外层页表页面离散地存放在不同的物理块中，再利用第 2 级的外层页表来记录它们之间的对应的关系。

![图示][SouthEast 17]

# 反置页表 #

![图示][SouthEast 18]

解决问题的方法

*  动态调入页表
 *  多级页表
 *  反置页表（Inverted page tables ）

一般页表的表项是按页号进行排序，页表项中的内容是物理块号。

反置页表是为每一个物理块设置一个页表项并按物理块号排序，其中的内容是页号 P 及隶属进程标志符 pid。

利用反置页表进行地址变换

*  用进程标志符和页号去检索反置页表。
 *  如果检索完整个页表未找到与之匹配的页表项，表明此页此时尚未调入内存，对于具有请求调页功能的存储器系统产生请求调页中断，若无此功能则表示地址出错。
 *  如果检索到与之匹配的表项，则表项的序号 i 便是该页的物理块号，将该块号与页内地址一起构成物理地址。

![图示][SouthEast 19]

*  反置页表可以有效地减少页表占用的内存，但反置页表中只包含已经调入内存的页面，未包含那些未调入内存的各个进程的页面，因此必须为每个进程建立一个外部页表 (External Page Table)。发现页面不在内存时才访问外部页表。
 *  外部页表存放各页在外存中的物理位置。通过外部页表可将所需要的页面调入内存。
 *  反置页表中是为每一个物理块设置一个页表项，通常页表项的数目也很大，通常又利用 Hash 表来检索。

# 页的共享与保护 #

页的共享：各进程把需要共享的数据/程序的相应页指向相同物理块。

![图示][SouthEast 20]

页的保护

页式存储管理系统提供了两种方式：

*  地址越界保护
 *  在页表中设置保护位（定义操作权限：只读，读写，执行等）

共享带来的问题

若共享数据与不共享数据划在同一块中，则：

*  有些不共享的数据也被共享，不易保密。
 *  计算共享数据的页内位移较困难。

实现数据共享的最好方法：分段存储管理。

[SouthEast]: /images/20220714/5305dbe2d12e4c0fbacfa8974419598f.png
[SouthEast 1]: /images/20220714/602f59e128b647a8bd4987724672ab40.png
[SouthEast 2]: /images/20220714/7ee81abeceba4670b8b81d6be3f9fe91.png
[SouthEast 3]: /images/20220714/09d6aba966704923ae4da0a95c37ca1f.png
[SouthEast 4]: /images/20220714/7d2cdd3f9ec14b158e8e0181d1239447.png
[SouthEast 5]: /images/20220714/0f7baba26f8a4f0697c1b2d94852616b.png
[SouthEast 6]: /images/20220714/9f951cb97ff34b7098286cdb844cf181.png
[SouthEast 7]: /images/20220714/7f5d5d62910642639aab77550767bc58.png
[SouthEast 8]: /images/20220714/223a97084f2747508eb94e4ba6610b72.png
[SouthEast 9]: /images/20220714/5c984cb963894f90b8f5e39fe79c9a31.png
[SouthEast 10]: /images/20220714/6ec54de3ee2942dc85420ee3f3a5f210.png
[SouthEast 11]: /images/20220714/ddb07aecb40548af953015321b4cdc7a.png
[SouthEast 12]: /images/20220714/88e6e372c42f4d62acc2ebfcf1a0e524.png
[SouthEast 13]: /images/20220714/7c46cf3182274d318948bf03517a6ba5.png
[SouthEast 14]: /images/20220714/80aa1d3cc26e469d931a53f0c3219e49.png
[SouthEast 15]: /images/20220714/30e3058eedd5488b9c718f3968f024ed.png
[SouthEast 16]: /images/20220714/b355f90c14a44b20aed4bf2240c737a4.png
[SouthEast 17]: /images/20220714/908e2540714b40d3831fa842d6ae0f59.png
[SouthEast 18]: /images/20220714/d504a03cc2884c199fb6bb9dd31fc752.png
[SouthEast 19]: /images/20220714/2397fa2c09f649f4855a8b3310f761ac.png
[SouthEast 20]: /images/20220714/f06140a8448f4cecb48566525ece96d1.png