操作系统备忘录--存储器管理

内容：课件整理

• 存储器的层级结构
• 程序的装入和链接
• 连续分配存储
• 分页存储管理方式
• 分段存储管理方式

1. 存储器的层级结构

• 主存储器
• 寄存器
• 高速缓存
• 磁盘缓存

2. 从程序(外存)视角——程序的装入和链接

使用内存的时机与方法

3. 装入

• 绝对装入方式(Absolute Loading Mode)
  • 绝对地址
  • 装入到事先指定的内存地址，只适用于单道程序系统
• 可重定位装入方式(Relocation Loading Mode)
  • 相对地址
  • 程序装入时对目标程序中指令和数据的修改过程称为重定位。
• 动态运行时装入方式 (Dynamic Run-time Loading)
  • 相对地址
  • 在程序运行期间进行重定位，即在CPU访问存储单元时才进行程序相对地址到物理地址之间的映射
  • 几个进程可以共享程序的单个副本。

4. 链接

程序编译后得到一组目标模块，链接程序将这组目标模块链接后形成装入模块

• **静态链接方式(Static Linking) **
• **装入时动态链接(Loadtime Dynamic Linking) **
  • 装入内存时再链接
  • 便于实现对目标模块的共享
  • 便于修改和更新
• **运行时动态链接(Run-time Dynamic Linking) **
  • 将对某些模块的链接推迟到执行时才执行

5. 从主存视角——连续分配存储

6. 单一连续分配

• 简单容易实现，但浪费存储资源
• 只能用于单用户、单任务的操作系统中

7. 固定分区分配

• 将内存用户区划分为若干个固定大小的区域，每个区域装入一道作业
  • 为实现分区的保护，系统硬件需设置基址和界限寄存器

8. 动态分区分配

• 根据进程的实际需要，动态地为其分配合适大小的内存空间

描述空闲分区和已分配的分区

• 空闲分区表

  分区序号	起始地址(K)	长度(K)
  1	20	12

• 空闲分区链

  • 所有空闲分区链成双向链表

分配算法

• 顺序搜索分区分配算法
  • 首次适应算法
    • 从链表第一个分区控制块开始线性搜索，找到一个分区长度大于等于请求容量的空闲区，即进行分配
  • 循环首次适应算法
    • 分配内存时，不是从链首搜索，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到满足要求的空闲分区
  • 最佳适应算法
    • 从空闲分区中找到能满足要求容量的最小分区
  • 最坏适应算法
    • 从最大空闲分区中裁取块分配；然后为该分区剩下的存储空间建立空闲分区控制块，插入可用表中
• 索引搜索分区分配算法
  • 快速适应算法
  • 伙伴系统
  • 哈希算法

回收内存

• 分区合并

9. 两种视角的结合——动态重定位分区分配

程序以相对地址方式装入，在指令执行时再变换为物理地址

核心：引入中间层

• 动态：地址变换是在程序执行期间发生

• 重定位：地址变换

  • 重定位寄存器

• 碎片：系统中小的空闲分区的总和大于要装入的作业，但因不连续而无法使用

• 紧凑：作业移动，把分散的小分区拼接成大分区

  

实现

• 分段
• 分页

10. 对换

阻塞进程占用内存，浪费资源

• 把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。

11. 分页存储管理方式

12. 页面

（页）页面

• 将一个进程的逻辑地址空间分成若干个大小相等的片
  • 为各页加以编号，从0开始， 如第0页、第1页等

（物理）块、页框

• 把内存空间分成与页面相同大小的若干个存储块
• 在为进程分配内存时，将进程中的若干个页以块为单位分别装入到多个可以不相邻接的物理块中。

页面碎片

• 进程的最后一页经常装不满一块而形成了不可利用的碎片

页面大小的影响

• 页面小
  • 内存碎片减小， 有利于提高内存利用率，但使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率
• 页面大
  • 减少页表，提高页面换进换出的速度；但使页内碎片增大
• 通常为512 B~8 KB

12.1. 地址结构

若有一个逻辑地址空间中的地址$A$，页面大小$L$

• 页号：$P=[\frac{A}{L}]$

• 页内地址：$d=AmodL$

  例如
  已知：页面大小1kb，逻辑空间地址2170b
  则：页号2，页内地址122

13. 页表

• 页面映射表

页表寄存器

• 页表在内存中的开始地址和长度

页号与块号

• $逻辑地址\Leftrightarrow 物理地址$

  

14. 地址变换机构

基本地址变换机构

• 逻辑地址（页号地址）：$页号+页内地址$

• 检查页号是否越界

• 通过页表寄存器得到页表位置

• 查页表，$页号\Rightarrow 块号$

• 物理地址：$物理块号×页面大小 ＋ 页内地址$

  

具有快表的地址变换机构

• 第一次访问页表计算出物理地址，第二次直接访问物理地址

  

15. 两级和多级页表

• 引入
  • 逻辑地址空间大导致页表非常大，要占用相当大的内存空间，并且，要求是连续的
• 解释办法
  • 采用离散分配方式来解决难以找到一块连续的大内存空间的问题
  • 只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入

15.1. 两级页表

• 为离散分配的页表建立页表，称为外层页表

  

16. 反置页表

17. 分段存储管理方式

• for programmer
• 信息共享

18. 分段

• 把程序按内容或过程分成段，长度不固定

19. 段表

• 段映射表

  

20. 地址变换机构

• 段表寄存器

  

• 快表

21. 分页与分段的比较

• 页是信息的物理单位，分页是由于系统管理的需要；段则是信息的逻辑单位，分段式由于用户的需要
• 页的大小固定且由系统决定；而段的长度却不固定， 决定于用户所编写的程序
• 分页的作业地址空间是一维的，即单一的线性地址空间，程序只需利用一个记忆符，即可表示一个地址； 而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名， 又需给出段内地址

22. 段页式存储管理方式

以分段技术管理用户的逻辑地址空间， 以分页技术管理实际使用的主存空间， 兼并分段分页的优点