# 存储管理

# 存储管理的需求和作用

内存被分为操作系统使用的内存和用户运行程序使用的内存

# 存储管理的需求

# 地址重定位

1. 程序员无需知道程序在执行时的内存位置
2. 程序执行过程中，可能被交换到磁盘，并在之后重新被交换回内存不同位置
3. 代码中内存访问需要被转换为物理内存地址

# 内存保护

1. 在未被允许的前提下，一个进程不能访问另一个进程的内存
2. 地址保护检查无法在编译和链接时刻进行
3. 地址保护必须在程序执行时由硬件实现
4. 操作系统无法预期一个程序将要访问的所有内存地址

# 内存共享

1. 允许多个进程访问同一块内存
   • 多个进程执行同一个程序，让每个进程都拥有一份程序代码的拷贝将浪费内存空间
   • 协作进程之间共享数据
2. 内存管理系统应允许对内存区域的受控共享访问

# 地址转换与存储保护

源程序需要进行编译、链接、装入才能装入主存运行

• 静态链接

  • 在链接时对所有外部引用进行转换，即给装入器的所有引用均已转换为逻辑地址空间中的相对地址
    

• 动态链接

  • 链接时对某些外部模块的引用不进行解析，延迟到装入或运行时
    

装入方式分类

1. 基于绝对地址的装入 (编译时绑定)
2. 基于地址重定位的装入
   • 静态重定位 -- 装入时绑定
   • 动态重定位 -- 运行时绑定

# 连续空间存储管理

# 固定分区存储管理

1. 将主存分为大小相同的分区
2. 将主存分成数目固定不变的，但大小不同的分区

分区分配算法

1. 分区大小相同
2. 分区大小不同
   • 将适合进程的最小分区分配给该进程，而不管该分区是否被占用
   • 将当前未被占用的适合进程最小分区分配给进程

优点：

• 实现简单

缺点：

• 大作业无法装入
• 一个程序无论多小，都将占用整个分区，大于程序大小的部分称为内部碎片。

# 可变分区存储管理

按照进程的需求为其分配恰好的内存空间

优点：

• 按需分配，提高主存利用率

缺点：

• 随着内存的不断分配、回收，最终主存中会出现许多分散的小空闲区，这通常被称为外部碎片

# 可变分区存储管理分配方法

• 最先适应分配算法：从低地址开始顺序查找未分配区表或链表，直至找到第一个能满足要求的空闲区
• 下次适应分配算法：从未分配区的上次扫描结束处顺序查找未分配区表或链表，直至找到第一个能满足长度要求的空闲区为止
• 最优适应分配算法：扫描整个未分配区表或链表，从空闲区挑选一个能满足用户进程要求的最小分区进行分配
• 最坏适应分配算法：扫描整个未分配区表或链表，挑选一个最大的空闲区分割给作业使用
• 快速适应分配算法：为经常用到的长度的空闲区设立单独的空闲区链表

# 连续内存分配的地址转换和存储保护

地址转换：

• 物理地址 = 基址寄存器值 + 逻辑地址值

存储保护：

• 方法一：逻辑地址是否小于限长寄存器的值？
• 方法二：物理地址是否小于界限寄存器的值？

# 主存不足的存储管理技术

• 移动技术
  将已在主存中的分区进行移动，使得分散的空闲区汇集成更大的空闲区，以满足新进程的内存请求
• 对换技术
  当内存空间不足时，将某个处于阻塞态的进程移出主存，腾出空间给其它进程使用；同时将磁盘中的某个进程换入主存，让其投入运行
• 覆盖技术
  覆盖是指程序执行过程中程序的不同模块在内存中相互替代，以达到小内存执行大程序的目的

# 分页存储管理

# 分页式存储管理原理

分页存储管理允许逻辑上连续的地址空间映射到物理内存中不连续的空间中

• 将物理内存分为固定大小的块，称为页框 (frame), 通常为 2 的幂次，如 512 字节
• 将逻辑地址空间划分为和页框相同大小的块，称为页面 (page)
• 为了跟踪进程的页与物理内存中页框之间的映射关系，每个进程都有一个相应的页表。
• 页表的每一项记录了逻辑页号与物理页框号之间的映射关系
• 系统设置页表基址寄存器，用于存放当前运行进程的页表起始地址

• 页号 - 用作查找页表的下标，页表中对应的位置存放了每个页面在物理内存中的首地址.
• 页内偏移 - 与页面在物理内存中的首地址结合，产生物理地址
• 物理地址 = 页框号 × 页面大小 + 页内偏移

页表通常存放在内存中

页表基址寄存器指向页表首地址

页表长度寄存器给出页表大小

每次取数据 / 指令需要两次内存访问，一次访问页表，一次访问数据 / 指令

为解决两次内存访问，可以使用快表 TLB 解决，存放进程最近访问的部分页表项。

# 分页存储空间的分配和去配

• 使用位图记录页框的分配情况，每位与一个页框相对应
• 0/1 表示对应块为空闲还是占用

# 分页存储的存储保护

有效位

• 页表中每一项后附加一位，用以标识该页是否属于进程的逻辑地址空间。
• 如果访问的地址对应的页表项标识为 invalid, 则产生异常。

页表长度寄存器

• 一些系统提供了页表长度寄存器，指出页表的长度
• 每个逻辑地址都与该值比较，如果逻辑地址的页号超过了页表长度寄存器的值，则产生异常。

# 分页存储的存储共享

• 数据页共享
  • 允许不同进程对共享数据页采用不同的页号
• 代码页共享
  • 要求不同的进程为共享代码页在逻辑空间中指定同样的页号

# 多级页表

现代计算机的逻辑地址空间很大，采用分页存储管理时，页表相当大

32 位逻辑地址空间，页面 4KB，则页表为$2^{20}$ 项，若每个页表项占用 4 字节，则每个页表需要占用 4MB 的连续存储空间

因此可以将页表进行分页，形成多级页表，从而允许页表存放在不连续的空间内

# 二级页表

$p_1$ 用于查找一级页表，$p_2$ 用于查找二级页表

# Hash 页表

在地址空间大于 32 位时，通常采用哈希页表的方式
进程的逻辑页号通过哈希函数映射到一个哈希表中的值

# 反置页表

• 反置页表为所有进程维护一张页表，每个物理内存的页框在页表中包含一项。
• 每个页表项包含占用该页框的进程号以及对应的逻辑页号。
• 降低了存储页表的开销，但增加了访存的查询时间。

# 分段存储管理

满足程序员编程和使用需求，将内存看作大小不同的段。

• 地址由两部分组成：段号和段内偏移

# 段表

用于将二维的逻辑空间地址映射到一维的物理地址
段表中的每一个表项包含：

• 段号
• 段起始地址
• 段长度

# 分页和分段区别

信息组织：

• 分段是信息的逻辑单位由源程序的逻辑结构及含义所决定，是用户可见的
• 分页是信息的物理单位与源程序的逻辑结构无关，是用户不可见的

长度：

• 分段的长度由用户根据需要来决定，每个分段在内存中是连续存放的，体现了连续存储空间管理的思想，段起始地址可以是任何地址；
• 页长由系统的硬件确定，页面只能从页大小的整数倍地址开始。