操作系统（9）---存储管理

一、引入

1.计算机体系结构 

 2.内存层次

 存储管理，也可以称为内存管理，其特点主要有：抽象（拥有逻辑地址空间），保护（每个进程都有独立的地址空间），共享（可以访问相同内存），虚拟化（虚拟存储）。

存储管理主要要解决两个问题： 1.存储空间如何分配？（连续分配，非连续分配）

　　　　　　　　　　　　　　 2.地址如何映射？

地址空间：分为物理地址空间和逻辑地址空间。物理地址空间是硬件（内存）支持的地址空间。逻辑地址空间是在CPU运行的进程看到的地址。

地址检查:

物理地址=基址+偏移量。由内存管理的独立性可知，若进程访问其进程空间以外的地址空间，可能会造成错误，所以地址检查，是查偏移地址是否超出了进程对应的物理地址空间的大小。在段长度寄存器处查偏移地址，检查通过后偏移+段基址寄存器中的基址=物理地址。

二、连续内存分配

连续内存分配：进程分配一块不小于指定大小的连续物理内存区域。

存在问题：1.产生内部碎片（分配给进程的空闲空间其他进程不可使用，造成内存空间浪费）

　　　　　2.产生外部碎片（进程之间的未分配内存空间太小不足以继续分配，造成内存空间浪费）

连续内存分配的三个策略：

• 最先分配

　　　　原理：空闲分区按地址顺序排序，顺着找合适的分区分配，释放时检查是否有临近空闲分区可以合并。

　　　　优点：高地址空间有大块的空闲分区

　　　　问题：有大量内部碎片（如下图样例，1KB的空间有约600B的内部碎片）、分配大块时较慢

• 最佳分配

　　　　原理：空闲分区按大小顺序排序，顺着找合适的分区分配，释放时检查是否有临近空闲分区可以合并。

　　　　优点：可以避免大的空闲分区被拆分，可以减小外部碎片的大小

　　　　问题：外部碎片过小不好再分配，产生很多无用的小碎片（如下图样例，剩了100B不好再分配）、释放分区时较慢

• 最差分配

　　　　原理：空闲分区由大到小排序，分配时选最大的，释放时检查是否有临近空闲分区可以合并，并调整空闲分区顺序。

　　　　优点：避免出现太多的小碎片，中等大小的分配较多时，效果最好。

　　　　问题：容易破坏大的空闲分区，后面难以分配大的分区，释放分区较慢。

碎片整理：通过调整进程占用的分区位置来减少或避免分区碎片

　　1.紧凑，通过移动分配给进程的内存分区，以合并外部碎片，前提是所有程序可动态重定位，开销大。

　　2.分区对换，通过抢占并回收处于等待状态进程的分区，以增大内存可用内存空间。

连续分配总有碎片，如何解决？

　　1.伙伴系统，以2的次幂划分内存空间，尽可能匹配进程所需要的空间大小，分配后剩余空闲分区合并。

　　2.非连续内存分配。

三、非连续内存分配

连续分配的缺点：

• 分配的物理内存必须连续
• 有内部碎片和外部碎片
• 内存分配的动态修改难
• 内存利用率低

非连续分配目标：提高内存利用率和管理灵活性。允许非连续物理地址空间，允许共享代码与数据、支持动态加载和动态链接。

非连续存储就要解决地址映射的问题，逻辑地址和物理地址如何转换？

1.段式存储

  段：访问方式和存储数据等属性相同的一段地址空间。对应连续内存的一个“块”，若干个段组成逻辑地址空间。

地址映射（MMU）：逻辑地址（段号，段偏移），物理地址（段基址，段偏移）

地址检查：地址安全检查需要段的长度（注意，不是进程空间的长度，进程空间被划分成多个段分段存储在内存中，逻辑/物理地址中的偏移是段偏移）。

 段式存储中，物理地址和逻辑地址的映射需要段表。段表包括：段号（可省略，段表每一行对应一个段）、段基址、段长度。

段表的一些概念

• 段表项：段表中的一行，段长度=段表项个数，段长度取决于分了几段
• 段表大小=段长度*段表项大小

段式存储的优/缺点：有效减少了外部碎片，但是段长仍是可变的，无法完美的嵌入内存空间，仍存在外部碎片。

因此，存储管理引入页式存储，进程空间分成一模一样大小的块，内存也分成对应大小的页，进程按页存储，完美占用内存的一页，外部碎片就消除了。

2.页式存储

• 页帧（Frame）：物理地址空间的一页

• 页面（Page）：逻辑地址空间的一页

• 页帧和页面的大小必须相同

地址映射（MMU）：逻辑地址表示（页面号，偏移），物理地址表示（页帧号，偏移），物理地址=页帧号*页面大小+偏移，页内偏移=帧内偏移，逻辑地址同理。

地址检查：检查偏移长度是否不超过页面大小。

页式存储中，物理地址和逻辑地址的映射需要页表。段表包括：页号（可省略，页表每一行对应一个页）、页帧号、标志位。

不是所有页都有对应的帧，物理/逻辑地址的偏移是一样的，但页号位数大小可以不一样，当页号位数P>页帧号位数f，内存不够用，需要虚拟内存，如果没有虚拟内存，会有缺页错误。

标志位的主要作用是：在缺页置换中，标志位可以标志该页是否在内存中，否则在外存中将该页调出来。

页表的一些概念：

• 页表项：页表中的一行，页表项大小是每一行的大小。
• 页表长度：页面个数=页表项个数，页面个数=进程空间大小/页面大小。
• 页表大小=页表长度*页表项大小。

用一个例子来理解：

假设占有64GB内存，每个页面4KB，页表大小？如果每个页面1B呢？

（1）页表长度=页面个数=内存大小/页面大小=64GB/4KB=2^24=16MB，故物理地址由24位页号和12位偏移组成。

         页表项大小（假设页表只有页帧号）=24bit=3B

         页表大小=页表项大小*页表长度=16MB*4B=48MB

（2）若每个页面1B，页表长度=2^36=64GB，页表项大小=36bit，物理地址由36位页号组成，没有偏移，内存存储以字节（1B）为单位。页表大小=64GB*36bit=288GB，页表大小远远超过原本的64GB。

由上可知，逻辑/物理地址的偏移位数，由页面大小决定。页式存储时，页面大小的取值很重要，页面太小，页表太大。

• 页式存储的优点：外部碎片消除。
• 页式存储的缺点：

　　 1.性能慢。需要二次访问内存，第一次查表，第二次访问对应的内存空间。

　　解决办法：快表（TLB），利用硬件实现——缓存，缓存近期访问的页表项。

　　TLB使用关联存储实现，可以快速访问。但是，如果TLB没有命中，要去内存中找对应的页表项并更新TLB，会很慢。

　　每一个进程都有自己的页表，但CPU只有一个TLB。当进程切换的时候，TLB有两种做法：

• • 清空，切换后每次都会未命中，效率很低
  • 共享TLB，效率高，只需要加上一项进程PID即可。

　　 2.页表占用内存。

　　解决方法：

　　（1）页面设置的很大，大了之后出现和段一样的问题，有外部碎片。

　　（2）多级页表。

二级页表：第一级页表存第二级页表项地址，第二级页表存页帧号。　　

用一个例子来理解：

假设有4GB内存，逻辑/物理地址一样（20位页号，12位偏移），进程仅用4MB，一级页表和二级页表（第一级第二级各10bit）分别多大？

一级页表：20位页号，页表长度=2^20，20位页帧号，页表项大小20bit取整算4B，页表大小=2^20*4B=4MB

二级页表：第一级和第二级页表10位页号，第一级页表存第二级页表项，页表长度1=2^10，页表项大小10bit取整算2B，

页表1大小=2^10*2B；

　　　　　第二级页表存页帧号，页表长度2=2^10，已知一共12位偏移，一个页面4KB，进程仅用4KB，刚好需2^10页。物理地址的页号20bit，页表项大小20bit取整算4B，页表2大小=2^10*4B

所以页表总大小为6KB。

综上，多级页表可以有效减小页表的大小，x86系统用的是4级页表。二级页表中，当且仅当“页表项全部都有效”时，二级页表多费空间，二级页表不可用。

3.段页式存储

段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势。 

四、虚拟存储

1.覆盖技术

目标：在较小的可用内存中运行较大的程序。

方法：依据程序逻辑结构，将程序划分为若干功能相对独立的模块；将不会同时执行的模块共享同一块内存区域。

• 必要部分（常用功能）的代码和数据常驻内存
• 可选部分（不常用功能）放在其他程序模块中，只在需要用到时装入内存
• 不存在调用关系的模块可相互覆盖，共用同一块内存区域

问题：

• 增加编程困难，需要陈还需要划分功能模块确定覆盖关系，复杂度高。
• 增加执行时间，不常用功能模块用的时候从外存装入覆盖模块，时间换空间。

例子如下：A要调用B、C，独占20KB，B不调用E、F，共用50KB，C不调用D，共用30KB，一共只需要100K。

2.交换技术

目标：增加正在运行或需要运行的程序内存

方法：将暂时不能运行的程序放到外存，换入/出整个进程的地址空间。

• 交换时机：内存不够或者有可能不够的时候
• 交换区大小：要存放所以进程的内存映像拷贝
• 程序换入的重定位：采用动态地址映射（？）的方法

总结：覆盖发生在运行程序的没有调用关系的模块间，交换以进程为单位，发生在进程间；覆盖要程序员给逻辑覆盖结构，交换不需要。