OS复习笔记ch7-2

页式管理

学过计组的同学都了解一点页式管理，就是将内存划分成较小的、大小固定的、等大的块。现在OS引入了进程的概念，那么为了匹配内存的分块，同样把进程也划分成同样大小的块。

这里区分两个概念

• The chunks of a process are called pages→进程划分的块称为页
• The chunks of memory are called frames/ page frames→内存划分的块叫做页框(物理页面、页帧)
  从语义去分析页和页框的区别和联系，把进程加载到内存，相当于把页放到页框中

在组原的课程当中我们知道逻辑地址包括页号和页内偏移量，有以下两个基本公式：

• 页号=逻辑地址/页面大小
• 偏移量=逻辑地址%页面大小
  看一下这个例子
  
  按照我们之前的分区和分页的概念，假设用户空间大小是2700B，访问地址是十进制的1502。按照分区的思想如图a所示访问，按照分页思想如图b所示。

一般来说，页面大小都是2的整数次幂，可以直接通过位运算得到结果。比如，页大小是1K = 2^10，那么偏移量 = 逻辑地址%页面大小 ，也就是逻辑地址后10位，前面的6位就是页号。

下标从0开始，所以page1是从上往下数第二个页面，即从1024开始到2047结束，然后偏移量offset=478是针对于1024的基地址的相对位移。

最后我们可以看到，图b在最下面有一段内部碎片，就是page2中不会使用到的区域，但是为了分页必须要分配。

分页的特点

• 没有外碎片，每个内碎片不超过页大小
• 一个程序不必连续存放（支持虚拟存储）
• 便于改变程序占用空间的大小
• 简单分页，程序全部装入内存
• 不易实现共享
• 不便于动态连接

页表

为了便于管理进程，操作系统为每个进程维护一张页表，包含进程的每个页面所对应的页框位置(号)，即逻辑地址和物理地址的映射关系。

如图所示，OS给A、C、D进程分配了页框，其中A是连续的0-3，而C是连续的7-10，D比较特殊是4-6+11-12，空闲13-14。由于会出现像D这种分配的页框不连续的情况，所以就必须使用页表专门记录。

接下来说一下，地址映射关系和存储保护机制

如图所示，页表开始地址b放在页表始址寄存器，类似于基址寄存器。页表长度l放在页表长度寄存器，防止地址越界。
根据图示，地址映射关系可以按以下步骤描述：
第一步：比较运算

• 将逻辑地址对应的页号p与 l 进行比较（比较条件为 P >= l），这决定了数据流向哪个分支，如果为真则地址越界抛出异常，反之进行下一步。

第二步：加法运算

• 页表始址 b 和页号 p 通过b+p*页表项长度查询页表，得到的结果p'就是所在页框的物理起始地址。

第三步：输出映射

• 在右侧分支，p' 和 d 直接结合作为输出，得到真实的物理地址。
  注：之所以p=l也被视为是地址越界，因为我们的下标默认都是从0开始，所以页号最大是l-1，等于l也是非法的，实际写过代码的同学会比较熟悉。

段式管理

类似进程的管理，我们的程序在逻辑上也可以分开，也就是我们常说的分段管理，比如代码段、数据段等。段式管理中一般段长可变，但是有最大段长。
段式地址有两个部分构成，和页式管理类似

• a segment number 段号
• an offset 段内偏移量
  
  回到我们之前看的这个例子，如图c采用段式存储，每一个段长度不一，偏移量指的是相对于每个段的起始地址。

接下来我们了解一下段式存储的内存划分和分配：

• 内存划分：内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定
• 内存分配：以段为单位分配内存，每一个段在内存中占据连续空间，但各段之间可以不连续存放

分析：

• 没有内碎片，外碎片可以通过内存压缩来消除
• 一个程序不必连续存放（支持虚拟存储）
• 便于改变进程占用空间的大小
• 便于存储保护、共享
• 简单分段，进程全部装入内存

注：有关存储保护和共享方面，本文最后一个标题会详细介绍

段表

与页式管理类似，段式管理也有段表，不过由于每个段的长度不同，所以段表长度寄存器的值不是唯一的。

• 进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(base address)和段长度
• 系统段表：系统内所有占用段,包含始值、段长等
• 空闲段表：内存中所有空闲段，可以结合到系统段表中
  段式管理内存的分配算法：首次适配、下次适配、最佳适配等，即动态分区。

具体流程如下：

• 输入逻辑地址：逻辑地址部分由段号 S 和段内地址 d 组成。
• 地址越界检查：通过段号S和C_l的比较，判断地址越界，方法同页式管理
• 查找段表：通过Cb+S*段表项长度查找段号找到对应的段基地址 b 和段长 l。
• 地址越界检查：将 d 与 l 比较，确保 d 小于l，即段内偏移小于段长。
• 计算物理地址：如果 d 在范围内，计算物理地址 b + d。
  注：由于段长是不固定的，所以在计算得到物理地址之前会进行第二次检查地址越界

页式管理和段式管理的比较

• 分页是出于系统管理的需要，分段是出于用户应用的需要。
  一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。
• 页大小是系统固定的，而段大小则通常不固定。
• 逻辑地址表示：
  分页是一维的，各个模块在链接时必须组织成同一个地址空间；
  分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。
  通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。

注：这里的一维和二维是根据程序员编程的角度分析，由于页的大小是固定的，所以给出一个逻辑地址OS就可以直接对应到物理地址，但是段的大小不一，就必须给定段名和段内地址，类似于基址变址寻址。

段页式管理

段页式管理就是结合页式管理和段式管理

如图所示，我们知道分页管理不能按照逻辑模块实现信息共享和保护，而分段管理又会像动态分区一样容易出现外碎片，虽然压缩紧凑可以解决这个问题，但是非常耗时且麻烦。于是就有人提出了段页式管理，综合了分段管理的逻辑模块和分页管理的无外碎片的优点。

如图所示，段页式管理的地址结构基于段式管理，将原先的段内地址改成了页号和页内偏移量。由于段页式管理的段的大小对于用户可见，对于OS不可知，所以是二维的地址结构。

其中，段表中存放了段号、页表长度、页表存放块号，一般段号都是隐藏的，而页表长度代替了原先的段表长度，页表存放块号也代替了原先的段基地址，通过该物理块号可以到页表中去查询实际物理块地址，可以通过图中箭头指向看到数据流向。

综上，我们可以图示得到段页式管理的地址访问步骤：

1. 由逻辑地址得到段号、页号、页内偏移量
2. 段号与段表寄存器中的段长度比较，检查是否越界
3. 由段表始址、段号找到对应段表项
4. 根据段表中记录的页表长度，检查页号是否越界
5. 由段表中的页表地址、页号得到查询页表，找到相应页表项
6. 由页面存放的内存块号、页内偏移量得到最终的物理地址
7. 访问目标单元

由于段长是不固定的，所以第四步需要根据段表中的页表长度检查页号是否越界。形式上，段页式管理就是将段式管理的段表长度改成页表长度，段基地址改成使用一级页表间接查询得到。

存储保护和共享

我们前面提到的段式管理有利于存储保护和共享，主要是基于以下两点：

• 段表中的基址和长度可实现范围保护
• 多个进程访问同一段

然后我们拓展讲一下存储保护类型和共享方式，了解一下即可。
存储保护类型

• 界限保护（上/下界寄存器或基址寄存器/限长寄存器）
• 访问方式保护
• 环保护：处理器状态分为多个环(ring)，分别具有不同的存储访问特权级别(privilege)，通常是级别高的在内环，编号小（如0环）；
  • 程序可访问同环或更低级别环的数据；
  • 可调用同环或更高级别环的服务（系统调用）。

存储共享方式

• 通过引用计数(reference count)来描述存储区的共享，引用计数表示共享它的进程的数目；具体的存储共享方式有两种
  • 共享段：被连接或被释放一次则对引用计数加1或减1，计数减至0则可将该共享段删除，目的在于进程间的信息交流。
  • 共享页面：在物理页面表中有引用计数。只能共享不被修改的页面。这对用户应用是透明的，完全由操作系统控制，目的在于减少系统内的物理页面总数。
    • 可用于装入同一个程序而创建的几个进程，或是父进程通过fork()创建子进程；
    • 写时复制(copy on write)：如果一个进程要改写共享页面，则先把该页面复制一份，让该进程访问复制后的页面，而让其他进程访问复制前的页面。（Unix类型OS）

写时复制是Unix类OS的一个很重要的特点，子进程创建的时候不是完全继承父进程的地址空间，只有在真正需要写的时候才复制一份进行修改。