OS-存储器管理

存储管理是指存储器资源（主要指内存并涉及外存）的管理。

• 存储器资源的组织（如内存的组织方式）
• 地址变换（逻辑地址与物理地址的对应关系维护）
• 虚拟存储的调度算法

存储管理的功能

1. 主存分配和回收
   分配和回收算法及相应的数据结构。
2. 地址变换
   • 可执行文件生成中的链接技术
   • 程序加载(装入)时的重定位技术
   • 进程运行时硬件和软件的地址变换技术和机构
3. 存储共享和保护
   • 代码和数据共享
   • 地址空间访问权限（读、写、执行）
4. 主存容量扩充(存储器的逻辑组织和物理组织)
   • 由应用程序控制：覆盖；
   • 由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）
   • 提高主存利用率

程序的装入和链接

程序的装入(重定位)(地址映射)

重定位

• 重定位: 程序运行装入主存时，要将程序中的虚拟地址转换为主存中的物理地址，这个转化过程就是重定位。
• 程序成为进程前的准备工作:
  • 编辑：形成源文件(符号地址)
  • 编译：形成目标模块(模块内符号地址解析)
  • 链接：由多个目标模块或程序库生成可执行文件(模块间符号地址解析)
  • 装入：构造PCB，形成进程(使用物理地址)

重定位方法

可重定位装入(静态重定位)

• 内容
  • 编写程序时可以采用相对地址
  • 作业（用户程序）在装入内存时才确定它的物理地址，并且将相对地址转换为物理地址
  • 作业一旦装入就不能移动、改变空间或者被换出主存。
  • 在程序运行之前，由链接装入程序进行的一次重定位。
  • 在程序运行之前已经完成了逻辑地址到物理地址的转换(只要完成链接装入)
• 优点：不需硬件变换机构支持，可以装入有限多道程序
• 缺点：一个程序通常需要占用连续的内存空间，程序装入内存后在运行期间不能移动，不易实现共享。

动态运行时装入(动态重定位)

• 内容
  • 动态重定位是在程序执行的过程中，每当访问指令或数据时，才将要访问的指令或数据的逻辑地址转换成物理地址。
  • 在程序装入时不对地址做任何操作，也就是保留逻辑地址不变。
  • 运行时重定位：可以使程序载入后还可以移动
  • 每个进程有各自的基地址,放在PCB

连续分配方式

分配方式

• 固定分区: 把内存划分为若干个固定大小的连续分区。

  • 分区大小可以相等也可以不同
  • 固定分区可能存在内碎片
  • 系统通过分区说明表对内存进行管理和控制。

• 动态分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。

  • 没有内碎片；有外碎片，如果大小不是任意的，也可能出现内碎片。
  • 内存紧缩：将空闲分区合并，需要移动多个段(复制内容)：

分区分配数据结构

空闲分区表

• 用于为内存中每个尚未分配的分区设置一个表项，每个分区的表项包含分区序号、分区始址及分区大小；

空闲分区链

• 通过前、后向指针将所有的分区链接成一个双向链

分区分配算法

首次适应算法FF

1. 内容
   内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲分区为止。然后按作业大小划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。
2. 优点
   • 优先利用内存中低址部分的空闲分区，在高址部分的空闲分区很少被利用，从而保留了高址部分的大空闲区，为后到的大作业分配大的内存空间创造了条件。
3. 缺点
   • 低址部分不断被划分，形成碎片；
   • 每次查找都从低址部分开始，这增加了查找可用空闲分区的开销。

循环首次适应算法

1. 内容
   • 内存分配时，从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，并从中划出一块与请求的大小相等的内存空间分配给作业
   • 设置一起始查寻指针，并采用循环查找方式。
2. 优点
   • 使内存中的空闲分区分布得更均匀
   • 减少查找空闲分区的开销
3. 缺点
   • 缺乏大的空闲分区

最佳适应算法

1. 内容
   • “最佳”是指每次为作业分配内存时，总把既能满足要求、又是最小的空闲分区分配给作业，避免了“大材小用”。
   • 为了加速寻找，该算法要求将所有的空闲区，按其大小以递增的顺序形成空闲区链。

分区分配和回收操作

动态分区分配内存

• 首先系统要利用某种分配算法，从空闲分区链(表)中找到所需的分区;
• 设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size;
• if(m.size-u.size<=size)
  - // size是事先规定的不再切割的剩余分区的大小
  - 说明多余部分太小,可不再切割，将整个分区分配给请求者;
• else
  - 从该分区中划分出与请求的大小相等的内存空间分配出去，余下的部分仍留在空闲分区链或空闲分区表中。最后，将分配区的首址返回给调用者;

回收内存

内存紧缩

• 内容：将各个占用分区向内存一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合并成为一个空闲分区。
• 这过程涉及到了动态重定位
• 紧缩时机：每个分区释放后，或内存分配找不到满足条件的空闲分区时

可重定位分区分配(增加了内存紧凑)

对换

对换的定义

• 指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存
• 对换是提高内存利用率的有效措施
• 整体对换(进程对换): 对换是以整个进程为单位
• 部分对换(页面对换/分段对换): 对换是以“页”或“段”为单位进行
• 为了实现进程对换，系统必须能实现三方面的功能：
  • 对换空间的管理
  • 进程的换出
  • 进程的换入

对换空间的管理

• 数据结构: 空闲分区表或空闲分区链
• 空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。

外存空间分类
文件区：用于存放文件，由于通常的文件都是较长久地驻留在外存上，故对文件区管理的主要目标是提高文件存储空间的利用率，为此系统采取离散分配方式。
对换区：用于存放从内存换出的进程，由于这些进程在对换区中驻留的时间是短暂的，而对换操作又较频繁，故对对换空间管理的主要目标是提高进程的换入、换出速度，为此所应采取的管理策略是用连续分配方式，较少考虑外存中的碎片问题。

进程的换出与换入

进程的换出

• 每一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出
• 换出过程:
  • 系统首先选择处于阻塞状态且优先级最低的进程作为换出进程;
  • 启动盘块，将该进程的程序和数据传送到磁盘的对换区上;
  • 若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的PCB做相应的修改。

进程的换入

• 系统应定时地查看所有进程的状态;
• 从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入;
• 直至已无可换入的进程或无可换出的进程为止。

离散分配方式

• 思想：将一个进程直接分散地分配到许多不相邻接的分区中，就不必再进行“紧凑”。
• 离散分配种类：
  • 分页存储管理
  • 分段存储管理
  • 段页式存储管理

基本分页存储管理方式

页面和物理块

• 页面:
  • 将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。
• 物理块(页框):
  • 把内存空间分成与页面相同大小的若干个存储块
• 分配时主存块可以不连续; 而页内逻辑地址是连续的
• 分页存储器的逻辑地址: 页号和页内地址(位移量)
  • 假设地址总长度为15位，其中页号占5位，页内地址占10位;那么逻辑地址可有32页，编号为0－31;页内地址占10位，则块的大小为1024个字节。编号为0－1023。
  • 若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得:

  $$P=INT[A/L]$$

  $$d=A mod(L)$$

页表(地址变换机构)

• 作用：实现逻辑地址到物理地址的转换(将逻辑地址中的页号转换为内存中的物理块号)

• 地址转换的公式为：绝对地址＝块号*块长+页内地址
  

• 页表控制寄存器–系统中只有一个

引入快表(TLB)的地址变换机构

• 引入原因：由于页表是存放在内存中的，这使CPU每次要存取一个数据时，都要两次访问内存。
  • 第一次是访问内存中的页表，从中找到该页的物理块号，将此块号与页内偏移量w拼接以形成物理地址
  • 第二次访问内存时，才是从第一步所得地址中获得所需数据(或向此地址中写入数据)
• TLB是一组相联快速存储，是寄存器，类似Cache
• 有效访问时间 = HitR(TLB+MA) + (1-HitR)*(TLB+2MA)*
• 原理：
  • 程序的地址访问存在局部性
  • 空间局部性(程序多体现为循环、顺序结构)
    

两级和多级页表

• 引入原因: 现代的大多数计算机系统，都支持非常大的逻辑地址空间。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。并且为连续的。
• 解决方法：
  • 采用离散分配方式来解决难以找到一块连续的大内存空间的问题；
  • 将当前需要的部分页表项调入内存，其余的页表项驻留在磁盘上，需要时再调入

两级页表

• 将页表也进行分页的办法，使每个页面的大小与内存物理块的大小相同，并为它们进行编号，即依次为0页，1页，…，n页。可以离散地将各个页面分别放在不同的物理块中
• 外层页表：为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)，在每个页表项中记录了页表页面的物理块号。

基本分段存储管理方式

• 引入：为了满足用户和程序员的下述一系列需要：
  • 方便编程：通常采用分段，汇编。。。
  • 信息共享：通常，在实现程序和数据的共享时，都是以信息的逻辑单位为基础的；
    • 比如，共享某个例程和函数。而在分页系统中的每一页都只是存放信息的物理单位，其本身并无完整的意义，因而不便于实现信息共享；然而段却是信息的逻辑单位。
  • 信息保护
  • 动态增长
  • 动态链接

分段

• 内容：
  • 作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。
  • 将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要CPU的硬件支持。
• 优点：
  • 没有内碎片，外碎片可以通过内存紧缩来消除
  • 便于改变进程占用空间的大小

段表

段表实现从逻辑段到物理内存区的映射。

分页和分段的主要区别

相同点

• 都采用离散分配方式；
• 都要通过地址映射机构来实现地址变换

不同点

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

段页式存储管理方式

优点：

• 段页式既具有分段系统便于实现、分段可共享、易于保护、可动态链接等一系列优点；
• 也具有分页系统那样很好地解决内存的外部碎片问题，以及为各个分段可离散地分配内存等问题

基本原理

把用户程序分成若干段，再把每个段分成若干页

• 在段页式系统中，为了获取一条指令或数据，须3次访问内存。
  • 第一次：访问内存中的段表，从中取得页表地址；
  • 第二次：访问内存中的页表，从中取出该页所在的物 理块号，同时和页内地址相加求出物理地址；
  • 第三次：从地址中取出指令或数据；

虚拟存储器的基本概念

• 引入原因：
  • 作业很大：
    其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行；
  • 大量作业要求运行：
    但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。
• 解决方法：
  • 从物理上增加内存容量。
  • 从逻辑上扩充内存容量。这正是虚拟存储技术所要解决的主要问题。

定义

• 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
• 其逻辑容量受限于计算机的地址结构和可用磁盘容量，其运行速度接近于内存速度。

基本原理

• 在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。
• 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。
• 另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序的一部分在内存就可执行。

优点

• 大程序：可在较小的可用内存中执行较大的用户程序；
• 大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)
• 并发：可在内存中容纳更多程序并发执行；
• 易于开发：与覆盖技术比较，不必影响编程时的程序结构

实现方式

• 虚拟存储器的实现，是建立在离散分配的存储管理方式基础上
• 常见方法有：
  • 分页请求系统
  • 分段请求系统

请求分页存储管理方式

页面置换算法

请求分段存储管理方式