一、覆盖与交换

• 覆盖与交换技术是在多道程序环境下用于扩充内存的两种方法。

1、覆盖

• 这种技术主要用于早期计算机中，早期计算机主存容量远比现在的要小，主存虽然仅存放一道用户程序，但存储空间放不下用户进程的现象经常发生，而覆盖技术就可以解决这种矛盾。

1.1、思想

• 覆盖技术的思想：由于程序运行时并非任何时候都要访问程序及数据的各个部分，因此可以将用户空间分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区，其余部分按调用关系分段；将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要的时候调入覆盖区，覆盖覆盖区原有的段。

1.2、特点

• 打破了必须将一个进程的全部信息装入主存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行，此外，内存能够更新的只有覆盖区的段，不在覆盖区的段会常驻内存。

2、交换

• 交换，也称作对换。

2.1、思想

• 交换技术的思想：将处于等待状态或在 CPU 调度原则下被剥夺运行权力的程序从内存移到辅存以腾出内存空间，此过程称为换出；把准备好竞争处理机的程序从辅存移到内存，此过程称为换入。理想情况下，内存管理器的交换过程速度足够快，总有进程在内存中可以执行。

2.2、注意问题

• 交换技术，需要注意以下几方面的问题：
  · 交换需要备份存储，通常是快速磁盘——必须足够大，并提供对这些内存映像的直接访问。
  · 为有效使用 CPU，需使每个进程的执行时间比交换时间长，而影响交换时间的主要是转移时间。转移时间与所交换的内存空间成正比。
  · 若换出进程，则必须确保该进程完全处于空闲状态。
  · 交换空间通常作为磁盘的一整块，且独立于文件系统。
  · 交换通常有许多进程运行且内存空间吃紧时开始启动，而在系统负荷降低时就暂停。
  · 普通的交换使用不同，但交换策略的某些变体在许多系统中，如 UNIX 系统中仍发挥作用。

3、覆盖和交换的区别

• 交换技术主要在不同进程或作业之间进行，而覆盖则用于同一个程序或进程中。由于覆盖技术要求给出程序段之间的覆盖结构，使得其对用户和程序员不透明，所以对于主存无法存放用户程序矛盾，现代操作系统是通过虚拟内存技术来解决的，覆盖技术则已成为历史；而交换技术在现代操作系统中仍具有较强生命力。

二、内存分配

• 内存分配管理可以大致分为连续分配管理方式和非连续分配管理方式两种。
• 所谓连续分配管理方式，是指为一个用户程序分配一个连续的内存空间；而非连续分配管理方式则允许将一个程序分散地装入不相邻地内存分区。

1、连续分配

• 在连续分配管理方式中，主要包括单一连续分配、固定分区分配和动态分区分配。

1.1、单一连续分配

• 将内存划分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；用户区为用户提供的、除系统区外的内存空间。由于内存中永远只有一道程序，因此不会出现访问越界干扰其他程序的情况，故而无需进行内存保护。
• 优点：简单、无外部碎片，可采用覆盖技术，无需额外技术支持。
• 缺点：只能用于单用户、单任务的操作系统中，有内部碎片，存储器利用率极低。

1.2、固定分区分配

• 最简单的一种多道程序存储管理方式。
• 将用户内存空间划分为若干固定大小的内存区，每个分区只装入一道作业；每当有空闲分区，便从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。
• 进行分区是有两种方法：分区大小相等和分区大小不等。前者用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性；后者将内存划分为多个较小的分区、适量的中等分区和少量大分区。如下图：
  

1.2.1、内存分配

• 为便于内存分配，将分区按大小排队，并建立分区说明表，表项由分区的起始地址、大小及状态构成。每当有用户程序要装入时，检索分区说明表，寻找合适的分区并将其对应分区的状态设置为“已分配”，若没有合适的分区，则拒绝为用户程序分配内存。分区说明表和存储空间分配情况如下图：
  

1.2.2、存在的问题

• 此种分区方式主要存在如下两个问题：
  ① 程序可能太大放不进任何一个分区，此时用户不得不用覆盖技术使用内存空间。
  ② 主存利用率低，当程序小于固定分区时，也占用一个完整的分区，这样分区内部存在空间浪费，此种现象称为内部碎片。
• 此种分区方式下，不能实现多进程共享一个主存区。固定分区很少用于现在的通用操作系统，但在某些用于控制多个相同对象的控制系统中仍在发挥着一定的作用。

1.3、动态分区

• 也成为可变分区分配，是一种动态规划内存的分区方法。
• 该方法中，不预先划分内存，而是在进程装入内存时，根据进程大小动态地建立分区，并使分区大小正适合进程的需要。故而，系统分区的大小和数目是可变的。

1.3.1、存在的问题

• 动态分区分配方法存在的一个问题就是，随着时间的推移，内存中会出现越来越多的小内存块，也就是所谓的外部碎片——指所有分区外的存储空间会变成越来越多的碎片，与上面固定分区中提及的内部碎片相反；外部碎片的出现，会导致内存利用率降低。
• 解决外部碎片可通过紧凑（Compaction）技术来解决，也就是操作系统不时地对进程进行移动和整理，需要动态重定位寄存器的支持，并且相对费时。

1.3.2、分区分配算法

• 在为进程分配内存分区时，需要依据一定的策略，常用的算法有首次适应算法、最佳适应算法、最坏适应算法和邻近适应算法。

1）首次适应：

• First fit 算法，空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。
• 最简单、最好和最快的算法，但是会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，增加了查找的开销。

2）最佳适应

• Best fit 算法，空闲分区按容量递增的方式形成分区链，找到第一个能满足要求的空闲分区。
• 每次的最佳分配都会留下很小的难以利用的内存块，产生更多的外部碎片，导致性能下降。

3）最坏适应

• Worst fit，又称为最大适应（Largest Fit）算法，空闲分区以容量递减得次序链接，找到第一个能满足要求得空闲分区，即挑出最大的空闲分区。
• 该算法选择最大可用块，似乎不容易产生碎片，但会很快导致没有可用的大内存块，因此性能也非常差。

4）邻近适应

• Next fit，又称为循环首次适应算法，由首次适应算法演变而来，区别在于，分配内存时从上次查找结束的位置开始继续查找。
• 该算法试图解决首次适应算法的不足，但是常常导致在内存的末尾分配空间分裂成小碎片，反而比首次适应算法的结果要差。

1.4、三种连续分配管理方式的比较

• 这三种内存管理方式的共同特点就是：用户进程在主存中是连续存放的。

2、非连续分配管理方式

• 由于非连续分配管理方式中，将作业要求的内存空间分散地分配在内存的各个区域，因此需要额外的空间存储分散区域的索引，从而存储密度会比连续分配管理方式的低。
• 非连续分配管理方式依据分区大小是否固定分为分页存储管理方式和分段存储管理方式。分页存储管理方式中，又- 根据运行作业时是否要把所有页面都装入内存才能运行，分为基本分页存储管理和请求分页存储管理。

2.1、基本分页存储管理

• 将主存空间划分为大小相等且固定的块，块相对较小，作为主存基本单位，进程以块为单位进行划分，进程在执行时以块为单位逐个申请块空间。
• 相对于固定分区技术，分页管理不会产生外部碎片，块的大小相对分区要小很多，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，是内部碎片—相对进程来说很小；每个进程平均只产生半个块大小的内部碎片，这种碎片称为页内碎片。

2.1.1、相关基本概念

1）页面及其大小

• 进程中的块称为页（Page），内存中的块称为页框（Page Frame，或页帧），外存也以同样的单位进行划分，直接称块（Block）。进程申请空间时，为每个页面分配主存中的可用页框，也即页和页框一一对应。出于方便地址转换，页面大小为 2 的整数幂，通常为 512B~8 KB。页面太小会使进程页数过多导致页表过长，占用内存、增加硬件地址转换的开销，从而降低页面换入/换出效率；页面太长，会使页内碎片增大，降低内存利用率；故而页面大小要适中，在空间效率和时间效率之间权衡。

2）地址结构

• 分页地址的地址结构如下：
  
• 由页号和位移量两部分构成；位移量所对应的低12位为页内地址，也即每页大小为 4KB；剩下的高20位为页号，也即是地址空间最多允许有 1M 页。

3）页表

• 系统为每个进程建立一张页面映像表，称为页表。页表记录页面在内存中对应的物理块号，一般存于内存中；从页表的内容可以知道，也表示用于寻找进程的每个页面在内存中对应的物理块。
• 每个页表项由页号和物理内存中块号组成；页表项的块号与地址的位移量构成物理地址。
  
• 配置页表后，进程执行时，通过页表就可以找到每页在内存中的物理块号，也即是页号到物理块号的地址映射。

2.1.2、基本地址变换机构

• 地址变换机构借助页表将逻辑地址转换成内存中的物理地址。
  
• 系统通常设有页表寄存器（Page-Table Register，PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的起始地址和长度存放在进程的 PCB 中，进程执行时，将页表始地址和长度存入页表寄存器。
• 若页面大小 L，逻辑地址 A 到物理地址 E 的变换过程（数据都是十进制）：
  ① 计算页号 P=A/L 和页内偏移量 W=A%L。
  ② 比较页号 P 和页表长度 M，若 P>=M 则发生越界中断，否则继续执行。
  ③ 页表中页号 P 对应页表项地址 = 页表始地址 F + 页号 P * 页表项长度，取出该页表项内容 b，即为物理块号。
  注意：页表长度指一共有多少页，页表项长度指页地址占据多大存储空间。
  ④ 计算 E=b*L+W，得到物理地址 E 去访问内存。
• 以上整个过程由硬件自动完成。页式管理只需给出一个整数就能确定对应得物理地址，由于页面大小是固定的。因此，页式管理中的地址空间是一维的。

1）如何确定页表项大小

• 某计算机 32 位逻辑地址空间、字节编址单位、一页 4KB，页表项需要多大？
• 地址空间共有 4GB/4KB = 1M 页，故需要 20 位才能保证表示范围能容纳所有页面，又因为以字节作为编制单位，所以页表项大小要大于 3B，可选择更大的页表项让一个页面能够正好容下整数个页表项，进而方便存储，如 4B，一页正好可装下 1K 个页表项。

2）页式管理存在的问题

① 每次访存都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则会降低访存速度。
② 每个进程引入页表，用于存储映射机制，页表不能太大，否则降低内存利用率。

2.1.3、带 TLB 的地址变换机构

• 为提高访存速度（页表全存在内存中，取一个数据或一条指令至少要访问两次内存：访问页表和取数据或取指令），在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器——快表，也叫相联存储器（Translation Look aside Buffer，TLB），存放当前访问的若干页表项，加速地址变换过程；与此相对，主存中的页表称为慢表。
  
• 此时地址变换过程：
  ①CPU 给出逻辑地址，由硬件进行地址转换，将页号送入高速缓寄存器，将此页号与快表中的所有页号比较。
  ② 若找到匹配的页号，则直接从高速缓存寄存器中取出对应的页框号，与页内偏移量组成物理地址；这样，一次访存就可以取出数据。
  ③ 若没有找到匹配的页号，则访问主存中的页表，读出页表项后，将其存入快表，便以后面可能的再次访问；调入新的页表项时，若快表已满，则需要按照一定的算法对旧的快表项进行替换。

2.1.4、两级页表（Two-Level Page Table）

• 目前大多数计算机都是 64 位的，也就是说其逻辑地址空间达到 2^64，此种环境下，页表变得非常大，需要占用相当大的内存空间，而且还是要连续的。为解决这个问题，可采用措施：
  1）采用离散分配方式来解决难以找到一块连续的大内存空间的问题；
  2）只将当前需要的部分页表项调入内存，其余页表项驻留在磁盘上，需要时再调入。
• 对于第一种措施的具体做法就是：将页表再分页并离散地存储在不同的物理块中，并为离散分配地页表再建立一张页表，称为外层页表（Outer Page Table），外层页表地页表项记录了页表页面地物理块号。外层页表又称作一级页表，内层页表也就是二级页表。此时逻辑地址结构如下：
  
• 外层页号又叫做一级页号，外层页内地址又叫做二级页号，页内地址就是页内偏移。映射过程如下图：
  
• 为了地址变换实现的方便，在地址变换机构中同样需要增设一个外层页表寄存器存放外层页表的始址，并利用逻辑地址中的外层页号作为外层页表的索引，从中找到指定页表分页的始址，再利用二级页号（外层页内地址）作为指定分页的索引找到指定的页表项，其中就含有该页在内存中的物理块号，用该块号与页内地址构成物理地址。
  
• 由上也可以看出，建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺序查找页表项。不过，如上做法还未解决用较少地内存空间去存放大页表地问题。为此，需要进一步的措施。在采用两级页表的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对页表只需调入一页或几页；为了确定某页是否已经调入内存，还应在外层页表中增设一个状态位 S，1 表示已经调入，0 表示未调入；进程运行时，地址变换机构根据逻辑地址中的外部页号，去查找外层页表，若所找到的页表项状态位为 0，则产生中断信号，请求操作系统将该页表分页调入内存。
• 两级页表对 32 位计算机是合适的，而对 64 位则不够；近年来的 64位OS 中，都是将直接寻址的存储器空间减少为 45 位长度左右，然后再用三级页表实现分页存储管理。

2.2、基本分段存储管理

• 分页管理方式是从计算机角度考虑设计的，目的在于提高内存的利用率，以提升计算机的性能，分页通过硬件实现，对用户完全透明。分段管理方式则是考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。
  
  

2.2.1、分段

• 在段式存储管理方式下，作业或进程的地址空间被划分为若干段，每段定义了一组逻辑信息；一般按照进程的自然段来划分，例如进程由一个主程序、两个子程序、栈和一段数据组成，那么便可以划分为主程序段MAIN、子程序段X、子程序段Y、栈段S和数据段D。虽然每个段都有段名，但是为方便通常用段号替代段名，每段从 0 开始编址，并采用一段连续的地址空间；段长由段的逻辑信息决定，故而各段段长并不一致，同理整个进程或作业有多少段也是动态的。
  整个作业的逻辑地址由段号和段内地址组成：
  
• 如图示例，段号 16 位，段内地址也就是段内偏移量也是 16 位，所以一个作业最多有 2^16=65,536 段，而每段的最大段长为 64KB。
• 页式存储管理方式下，逻辑地址的页号和页内偏移量对用户和程序员透明，而段式存储管理方式下，段号和段内偏移量必须由用户提供，高级程序设计语言中，这个工作由编译程序完成，编译程序能自动根据源程序的情况而产生若干段。

2.2.2、段表

• 像页式存储管理方式有页表那样，段式存储管理下，系统也为每个进程建立一张段映射表，即段表。段表项为进程一个段在内存中的起始地址（基址）和段长。段表内容如下：
  
• 段表可以存在一组寄存器中，这样有利于提高地址转换过程；但通常是存放在内存中。段表实现从逻辑段到物理内存区的映射。
  

2.2.3、地址变换机构

• 为实现进程的逻辑地址到物理地址的变换功能，在系统设置了段表寄存器，用于存放段表始地址F和段表长度M。逻辑地址A到物理地址E的变换过程如下：
  
  ① 从逻辑地址 A 取出段号 S，段内偏移量 W。
  ② 比较段号 S 和段表长度 M，若 S>=M，产生越界中断，否则继续执行。
  ③ 段表中段号为营的段表项始地址=段表始址F+段号S*段表项长度，取出对应段表项的段长C。若段内偏移量>=C，则发生越界中断，否则继续执行。
  ④ 取出段表项中该段的始址b，计算E=b+W 形成物理地址，然后根据物理地址去访存。

2.2.4、段的共享与保护

• 段的共享通过两个作业的段表中相应表项指向共享的段的同一个物理副本来实现。当一个作业正从共享段读取数据时，必须防止另一个作业修改此共享段的数据。不能修改的代码称为纯代码或可重入代码，这不属于临界资源，这样的代码和不能修改的数据可以共享，而可以修改的代码和数据不能共享。
• 与分页管理类似，分段管理的保护方法主要有：
  ① 存取控制保护
  ② 地址越界保护
• 所谓越界保护是将段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度，则产生越界中断；再将段表项中的段长和逻辑地址中的段内偏移量进行比较，若段内偏移量大于段长，也会产生越界中断。分页管理中的地址越界只需判断页号是否越界，而页内偏移量是不可能越界的。
• 段式管理不能通过给出一个整数便确定对应的物理地址，由于每段的长度不固定，无法通过整数除法得出段号，无法通过求余得出页内偏移量，所以段号和段内偏移量一定要显示给出，因此分段管理的地址空间是二维的。

2.3、分页和分段的区别

• 分段和分页系统有许多相似之处：都采用离散分配方式，都通过地址映射机构实现地址变换；但也有着概念上的区别，主要如下：
  1）页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外部碎片，提高内存利用率；或者说，分页仅仅是由于系统管理的需要而不是用户的需要，段是信息的逻辑单位，含有一组相对完整的信息；分段的目的为了更好地满足用户的需要。
  2）页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能一种大小的页面；而段长却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
  3）分页的作业地址空间是一维，即单一的线性地址空间，程序员只需利用一个记忆符，就可表示一个地址；而分段的作业地址空间是二维的，程序员在标识一个地址时，既需要给出段名，又需给出段内地址。

2.4、段页式管理方式

• 页式存储管理能有效提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享；将两种存储管理方式综合起来形成段页式存储管理方式。

2.4.1、基本原理

• 在段页式系统中，作业的地址空间首先被划分为若干逻辑段，每段有自己的段号，然后将每个段分成若干大小固定的页。内存管理方式和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。段页式系统中，作业的逻辑地址分为段号、页号和页内偏移量（页内地址）：
  
• 同样的，段页式系统中，也有一种用于逻辑地址到物理地址映射的表。系统为每个进程建立一个段表，每个分段有一张页表。段表项中至少包括段号、页表长度和页表始址，页表项中至少包括页号和块号。
  
• 而为了地址转换的实现，系统中应当设置有段表寄存器，其中存放段表始地址和段表长度，段表寄存器的作用是在段表或页表中寻址和判断是否越界。
  
• 一个进程中段表只有一个，而页表可以有多个。
• 进行地址变换时，首先通过段表查到页表始地址，然后通过页表找到页帧号，最后形成物理地址。如上图所示，进行一次访问实际需要三次访问主存，因此同样可以使用快表来加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。段页式管理的地址空间也是二维的。

上一篇
下一篇

---

内存概述

什么是内存：
内存是用于存放数据的硬件，程序执行前需要先放到内存中才能被CPU处理。

存储单元
将内存分为一个一个的小区间，每个区间就是一个存储单元。

内存地址
给内存的存储单元编地址，有两种：

• 按字节编址：每个存储单元的大小为1字节（8位）
• 按字编址：字长为16位的计算机，每个存储单元的大小为1个字（16位）

逻辑地址和物理地址

• 逻辑地址：编译生成的指令中是逻辑地址，是相对地址。
• 物理地址：是数据实际存放在内存当中的地址，是绝对地址。

---

进程运行的基本原理

进程执行的流程：

装入方式

• 绝对装入： 在编译时，如果直到程序将放到内存中的哪个位置，编译时将产生绝对地址的目标代码，装入程序按照装入模块中的地址，将程序和数据装入内存。
  缺点：只适合单道程序环境。
• 静态重定位： 编译、链接后的装入模块的地址都是从0开始，指令中也是逻辑地址。在装入时对地址进行重定位，将逻辑地址变换为物理地址。
  缺点：内存必须有足够的空间才能装入该进程，且运行期间不能移动。
• 动态重定位： 使用重定位寄存器，当该进程被调度运行时，才会获取寄存器中的信息，将逻辑地址转换为物理地址。
  优点：运行期间也可移动。

链接方式

• 静态链接： 在程序运行前，将个目标模块链接成一个完整的装入模块，之后不可拆分。
• 装入时动态链接： 将各目标模块装入内存时，边装入边链接。
• 运行时动态链接： 在程序执行中需要该目标模块时，才对它进行链接。

---

内存管理*

内存管理的主要内容：

• 地址转换： 对应三种装入方式
• 存储保护： 保证各进程在自己的内存空间内运行，不会越界访问，两种方式：
  1.设置上下限寄存器
  2.重定位寄存器+界地址寄存器
• 内存空间的扩充（虚拟）
• 内存空间的分配与回收

---

内存空间的扩充

• 覆盖技术：将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存（固定区，覆盖区）。
• 交换技术：内存空间紧张时，系统会将内存中某些进程暂时换出外存，外存中已具备运行条件的进程换入内存（中级调度）。
• 虚拟存储技术：后文

注：磁盘空间分为文件区和对换区，文件区采用离散分配方式，对换区采用连续分配方式。

---

内存空间的分配与回收

两种类型分配方式：

• 连续分配管理：用户进程分配的必须是一个连续的内存空间
• 非连续分配管理

---

连续分配管理

• 单一连续分配：
  内存分为系统区和用户区，内存中只能有一道用户程序。
• 固定分区分配：
  用户区划分为若干个固定大小的分区（分区大小相等/不相等），每个分区可装入一道作业。
  需要建立分区说明表：分区大小、起始地址、状态
• 动态分区分配：
  在进程装入内存时，根据进程的大小动态地建立分区。
  需要建立空闲分区表或空闲分区链：
  

内部碎片： 分配给某个进程的内存区域中，有些部分没用上。
外部碎片： 内存中的某些空闲分区由于太小而难以利用。我们一般通过紧凑技术来解决外部碎片。

动态分区分配算法
当多个空闲分区都满足进程大小需求时，需要选择分区，因此有以下四中分配算法：

• 首次适应算法
  空闲分区以地址递增的次序排列，顺序查找到第一个能满足的空闲分区。
• 最佳适应算法
  空闲分区以容量递增的次序排列，顺序查找到第一个能满足的空闲分区。
• 最坏适应算法
  空闲分区以容量递减的次序排列，顺序查找到第一个能满足的空闲分区。
• 邻近适应算法
  空闲分区以地址递增的次序排列，从上次查找结束的位置开始查找，找到第一个满足要求的空闲分区。

---

非连续分配管理*

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

三种管理方式：

• 基本分页存储管理
• 基本分段存储管理
• 段页式存储管理

---

基本分页存储管理

基本思想
把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。

基本概念

1. 内存空间中每个分区被称为页框（页帧/内存块/物理块），每个页框有一个编号（从0开始），被称为页框号（内存块号/页帧号/物理块号）。
2. 用户进程的地址空间划分为与页框大小相等的一个个区域，被称为页（面），也有一个编号，即页号。
3. 操作系统以页框为单位为各个进程分配内存空间，即页面与页框一一对应。

那如何知道进程的每个页面在内存中存放的位置，就要为每个进程建立一张页表，如下：

如何得到物理地址

1. 算出逻辑地址对应的页号
2. 要知道该页号对应页面在内存中的起始地址
3. 要算出路基地址在页面内的“偏移量”
4. 物理地址 = 页面始址 + 页内偏移量

上面是我们的实现逻辑地址到物理地址转换的原理，而实际上是由基本地址变换机构（用于实现逻辑地址到物理地址转换的一组硬件机构）来实现的。
通常会在系统中设置一个页表寄存器，存放页表在内存中的起始地址 F 和页表长度 M，进程未执行时，F 和 M 放在进程控制块 PCB 中。

优化

1. 快表
   在基本地址变换机构中，每个逻辑地址都要查询内存中的页表，而快表（联想寄存器）是一种访问速度比内存快的高速缓冲存储器，用来存放当前访问的若干页表项，以加快地址变换的过程。
2. 二级页表
   页表一般连续存放且没必要整个页表常驻内存，因此可以使用二级页表，即在原本页表的基础上，加一个页目录表，如下：
   

---

基本分段存储管理

基本思想
按照程序自身的逻辑关系划分为若干段，每个段都有一个段名且从0开始编址；每段在内存中占据连续空间，各段之间可以不相邻。

分段系统的逻辑地址由段号（段名）和段内地址（偏移量）组成，同样需要为每个进程建立一张段映射表，即段表：

分段与分页对比

• 页是信息的物理单位，是系统的行为，对用户不可见
• 段时信息的逻辑单位，是用户编程是决定，对用户是可见的
• 分页的逻辑地址是一维的，而分段的逻辑地址是二维的
• 分段比分页更容易实现信息的共享和包含

---

段页式管理方式

先来看下分页管理和分段管理的特点：

	优点	缺点
分页管理	内存利用率高，不会产生外部碎片	不易实现信息的共享和保护
分段管理	方便实现信息共享和保护	段太长，不易分配连续空间，且会产生外部碎片

段页式管理 = 分段 + 分页
进程先分段，再将各段分为大小相等的页面
内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存，如下：

同时会存在段表和页表：

• 段表：每段对应一个段表项，各段表项长度相同，由段号、页表长度、页表地址组成。
• 页表：每页对应一个页表项，各页表项长度相同，由页号、页面存放的内存块号组成。

---

虚拟内存

传统存储管理的缺点：

• 一次性，即作业必须一次性全部装入内存后才能开始运行。
• 驻留性，即一旦作业被装入内存，就会一直驻留在内存中，直到作业运行结束。

虚拟内存技术
允许一个作业分多次调入内存，虚拟内存的实现需要建立在离散分配的内存管理方式基础上，对应三种非连续分配：

请求调页：访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存。
页面置换：内存空间不够时，由操作系统将内存中暂时用不到的信息换出到外存。

---

请求分页

页表机制
请求页表项增加了四个字段：

缺页中断机构
每当要访问的页面不在内存时，便会产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。

缺页的进程会阻塞，调页完成后才唤醒。

内存中有空闲块就直接给该进程分配一个空闲块，如果没有则由页面置换算法淘汰一个页面。

缺页中断是因为当前指令想要访问的目标页面未调入内存，因此属于内中断。

地址变换机构
区别与基本分页：

• 检查页面是否在内存中
• 若不在内存中，需要请求调页
• 若内存空间不够，还需换出页面
• 页面调入内存后，需要修改相应页表项

---

页面置换算法

页面的换入、换出需要磁盘I/O，会有较大的开销，因此算法应该追求更少的缺页率。

最佳置换算法 OPT
每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面。

因为系统需要知道以后会出现的页面，所以是无法实现的。

---

先进先出置换算法 FIFO
每次选择淘汰的页面是最早进入内存的页面。

只有 FIFO 算法会产生 Belady 异常。
Belady 异常：为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

FIFO 算法实现简单，但是性能差。

---

最近最久未使用置换算法 LRU
每次淘汰的页面是最近最久未使用的页面。
实现：页表增加访问字段，记录每个页面自上次被访问依赖所经历的时间 t，每次选择现有页面中 t 值最大的。
最接近 OPT 性能的算法，但是需要专门的硬件支持，算法开销大。

---

时钟置换算法 CLOCK
性能和开销均衡的算法，又称为最近未用算法（NRU）。

实现：

• 每个页面设置一个访问位（1/0），再将内存中的页面通过链接指针链接成一个循环队列。
• 当某页被访问时，访问位为 1。
• 当淘汰某个页面时，只需检查页的访问位，如果是 0，则换出；如果是 1，置 0，暂不换出并检查下一个。
• 若第一轮扫描所有页面是 1，则都置 0 后会进行第二轮扫描。

---

改进型的时钟置换算法
上面的时钟置换算法其实少考虑了一种情况，就是页面是否被修改过。

所以需要检查访问位和修改位，用(访问位,修改位)表示，过程如下：

• 第一轮，淘汰 (0,0)，即未被使用和修改的页面
• 第二轮，淘汰 (0,1)，即未被使用的页面，并将扫描过的页面访问位置 0
• 第三轮，淘汰 (0,0)，即未被修改的页面
• 第四轮，淘汰 (0,1)，即最早进入队列的页面

---

页面分配策略

驻留集：指请求分页存储管理中给进程分配的内存块的集合。
工作集：指再某段时间间隔里，进程实际访问页面的集合。
驻留集一般小于进程的总大小，驻留集大小一般不能小于工作集大小。

固定分配： 操作系统为每个进程分配一组固定的物理块，即驻留集大小不变。

可变分配： 先为每个进程分配一定数目的物理块，在进程运行期间根据情况做适当的调整，即驻留集大小可变

局部置换： 发生缺页时只能选进程自己的物理块进行置换。

全局置换： 可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

所以根据以上四种，可以有一下组合：

• 固定分配局部置换
  发生缺页只能从自己的进程在内存中的页面选出一页换出。
• 可变分配全局置换
  只要缺页就给分配新物理块（空闲块/未锁定页面的内存块），缺页率会增加。
• 可变分配局部置换
  根据发生缺页的频率来动态地增加或减少进程的物理块。

预调页策略： 在进程运行前，调入若干个可能访问到的页面，主要用于进程的首次调入。

请求调页策略： 进程在运行期间发现缺页时才将所缺页面调入内存。

抖动（颠簸）现象：
刚刚换出的页面马上又要换入内存，刚刚换入的页面又要换出外存，这种频繁的页面调度行为称为抖动或颠簸，产生颠簸的主要原因是进程频繁访问的页面数目高于可用的物理块数。