操作系统——内存管理（1）

内存管理的功能及相关概念

内存管理：OS对内存的划分和动态分配。
功能：
- 1.地址转换：程序的逻辑地址与内存中的物理地址不一致，需要相关转换；
- 2.内存空间的扩充：使用虚拟存储的技术或者自动覆盖技术，从逻辑上扩充内存；
- 3.内存保护：各道作业在各自的存储空间内运行，互不干扰。
- 4.（重点）内存空间的分配和回收：让程序员摆脱存储分配的麻烦，提高编程效率；
  - 连续分配管理方式
  - 非连续分配管理方式

1. 程序装入内存和链接

创建进程的第一步就是讲程序和数据装入内存，需要经过：编译、链接、装入三个阶段：

编译：源代码编译成若干个目标模块（若干程序段）。
链接：由链接程序将上一步产生的目标模块，以及所需库函数链接在一起，形成一个完整的装入模块。
- 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开（重点是：以后不拆）；
- 装入时动态链接：目标模块装入内存的同时，进行链接；
- 运行时动态链接：在程序执行过程中需要该目标模块时，才进行链接。优点是便于修改和更新，便于实现对目标模块的共享。
装入：使用装入程序，将装入模块放入内存运行。
- 绝对装入：编译产生的目标代码是绝对地址（可在编译或汇编时给出，也可由程序员赋予）。绝对装入程序按照该地址完成程序的装入（无需对数据和程序的地址进行修改）。只适用于单道程序环境。
- 可重定位装入：在多道程序环境下，目标模块的起始地址一般都是0，所以逻辑地址都是相对于起始地址的。根据内存的当前情况，将装入模块装入内存适当的位置。装入时对目标程序中的指令和数据的修改过程称为重定位。因为地址变换是在装入时一次性完成的，所以称为静态重定位。一旦进入内存后，整个运行期间不能在内存中移动，也不能再申请新的内存空间。
- 动态运行时装入：装入程序把模块装入内存以后，并不立即将模块中的相对地址修改为绝对地址（内存中的都还是相对地址），而是把这种地址转换推迟到程序真正要执行时才进行。需要一个重定位寄存器。特点：可以将程序分配到不连续的存储区中，在程序运行之前只装入部分代码就可以投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

2. 内存保护

保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。
做法是设立基址寄存器（重定位寄存器）和限长寄存器（界地址寄存器）。
- 基址寄存器是用来“加”的，逻辑地址加上该寄存器的值，转换得到物理地址；
- 限长寄存器是用来“比”的，逻辑地址的值与该寄存器的值进行比较。

3. 内存扩充的方法：覆盖和交换

覆盖

程序运行时并非任何时候都要访问程序的各个部分，因此可以把用户空间划分成一个固定区和若干个覆盖区。经常活跃的部分放在固定区，其余部分按照调用关系分段。
首先将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统将其调入覆盖区，覆盖掉原有的段。
特点：虽然打破了之前“必须将进程全部信息转主存才能运行”的限制，但若当前运行程序的代码量大于主存时仍然不能运行（需要使用虚拟内存的技术来解决）。而且不在覆盖区的段会常驻内存。
覆盖技术用在同一个程序或进程中，而且要求给出程序段之间的覆盖结构，对用户和程序员不透明，所以覆盖技术已成历史。

交换

把处于等待状态的程序从内存移到辅存，把内存空间腾出来，即换出；把准备好竞争CPU的程序从辅存移到内存，即换入。比如，将作业挂起的内存调度方法。
交换时注意点：
- 交换需要备份存储；
- 要求进程执行时间比交换时间长，其中交换时间与所交换的内存空间大小成正比；
- 如果换出进程，要求该进程必须处于空闲状态；
- 交换空间通常作为磁盘的一整块，且独立于文件系统，使用可能就很快；
- 交换通常发生在多进程运行且内存吃紧的时候，系统负荷较低时就暂停交换；
- 当前交换技术使用不多，但其延伸技术依然应用在Unix等系统中。

4.1 连续分配管理方式

分为单一连续分配、固定分区分配、动态分区分配三种。
共同特点：进程在主存中都是连续存放的。

单一连续分配

分为系统区和用户区，内存中永远只有一道程序
应用在单道程序，优点：简单、无外部碎片，可采用覆盖技术。缺点：只能用在单用户、单任务的操作系统，有内部碎片，存储器的利用率极低。

固定分区分配

最简单的一种多道程序存储管理方式，将用户内存空间划分为若干个固定大小（可彼此相等或不等）的区域，一个分区只装入一道作业。当有分区是空闲状态时，可以选择合适大小的作业装入分区，如此循环。
为了便于管理，建立一张分区说明表，表项包括各个分区的起始地址、大小和是否已分配。
缺点：程序可能太大而放不进任何一个分区中，用户不得不采用覆盖技术；会产生内部碎片。

动态分区分配

是一种动态划分内存的分区方式，进程在装入内存时，根据进程的大小动态地建立分区，使得分区的大小正好适合进程的需要（没有内部碎片）。
缺点：开始分配时状况较好，但随着时间推移，内存中会出现很多很小的内存碎块（即外部碎片），必须要通过紧凑技术来解决，这种操作需要动态重定向技术来解决，而且相对费时。
如果内存有着多个足够大的内存块，某个进程需要装入内存时，可以选择四种不同的策略进行分配：
- 首次适应：按地址顺序查找，首次找到合适大小的，就给予分配。虽然够简单、够快、够好，但每次要从低地址部分开始寻找，增加了查找的开销。
- 最佳适应：按容量递增形成分区链，找到第一个能满足要求的内存块。虽然“看上去很美”，但性能不好，容易造成更多的外部碎片。
- 最坏适应：按容量递减形成分区链，找到第一个能满足要求的内存块。虽然不容易产生外部碎片，但会导致内存中缺少可用的大的内存块，使性能变差。
- 邻近适应：循环首次适应算法，从上次查找结束的位置开始查找，会在内存的末尾分配空间，分裂成小碎片，比首次适应算法结果差。

4.2 非连续分配管理方式

允许一个程序分散地装入到不相邻的内存分区中。这种方式针对的问题是：内存中有超过需要大小的内存空间，但该空间并不连续，如果采用连续分配的管理方式，仍然无法运行。
按照分区的大小是否固定可以分为分页存储管理方式和分段存储管理方式

	分页	分段
目的	页是信息的物理单位，分页是为实现离散分配方式，以减少内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要	是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好的满足用户的需要
长度	页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，由机器硬件实现，因而在系统中只能有一种大小的页面	段的长度不固定，决定于用户编写的程序，通常由编译程序在对程序进行编译时，根据信息的性质来划分
地址空间	作业地址空间是一维的，即单一的线性地址空间，程序员只需要利用一个记忆符，即可表示一个地址	作业地址空间是二维的，程序员在标识一个地址时，既给出段名，又需给出段内地址
碎片	有内部碎片，无外部碎片	有外部碎片，无内部碎片
共享和动态链表	不容易实现	容易实现

运行时是否要把作业的所有页面都装入内存才能运行分为两种：基本分页和请求分页（请求分页见下一节：操作系统第三章（2））

基本分页存储管理方式

分页：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位（叫：页Page）。同时，每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间（叫，页框Page Frame）。同时，外存中直接叫：块Block。
逻辑地址结构：页号P（12到31位，故总共允许2^20页）和页内偏移量W（0到11位，故每页大小2^12即4KB）。可以定位到某页某处，直接找到字节。
页表：由页表项组成，页表项包含页号P和块号b（块号即物理内存中的块的编号，根据块号b和页内偏移量W可以找到内存中的物理地址）。每个进程对应一张页表，页表存在内存中。页表的作用：实现从页号到物理块号的地址映射。
基本地址变换机构。任务：将逻辑地址（通常十进制表示）转换为内存中的物理地址。需要：一个页表寄存器（PTR），存放页表在内存的始址F（理解：连续页在内存中最开始的地址）和页表长度M（理解：总页数）。
流程：
1. 进程未执行时，始址F和页表长度M放在进程的PCB中；当进程执行时，这两个数据写入PTR中。
2. 明确需求：计算一个逻辑地址A对应的物理地址E（待求）。
3. 计算页号P和页内偏移量W（P=A/L;W=A%L，L是页面大小，A和L都是B为单位）。
4. 比较页号P和页表长度的大小M。如果P>=M，说明页数超了，发生越界中断；没超继续下一步。
5. 计算页号P对应的页表项地址（P页第一个字节的物理地址），页表项地址=页表起始地址F+页号P×页表项长度（页表项长度即每页多少B）。从该页表项的地址可以得到块号b。
6. 计算物理地址E=b×L+W。
以上流程中取一次数据至少要访问两次内存，第一次得到物理地址，第二次根据该地址访问数据。使用块表（某高速缓冲存储器，TLB）进行辅助。流程：CPU给出逻辑地址后，由硬件进行地址转换并将页号与TLB比较，如果找到了，直接一次性存取内存数据；如果没有找到，那就读内存，顺便将该数据存入TLB，方便下一次快查。
两级页表:构建页表的索引页表。顶级页表最多只能有1个页面。
- 解决了：当逻辑地址空间过大时，页表的长度会大大增加的问题。

基本分段存储管理方式

分段：按照用户进程中的自然段划分逻辑空间。比如可以分为主程序、两个子程序、栈和一段数据统共五段组成，每段从0开始编址，并且段内是连续的地址空间。
逻辑地址是由段号S（16到31位）和段内偏移量W（0到15位）两部分组成（一个作业最多2^16段，每段最长64KB）。
段表：逻辑空间与内存空间映射的作用。段表项为：段号+段长+本段在主存的起始地址。
流程：
- 进程中取出段表始址F和段表长度M，放入段表寄存器中。
- 根据逻辑地址A（通常二进制表示）中取出前几位为段号S，后几位为段内偏移量W。
- 比较S和M，如果S>=M，产生越界中断，没有则下一步。
- 计算S的段表项地址=始址F+S×段表项长度。取出段表项，段表项的前几位得到段长C，段内偏移量W如果大于C，产生越界中断，否则继续执行。
- 取出段表项该段的起始地址b，计算物理地址E=b+W。
段的共享是通过两个作业的段表中相应表项只想被共享的段的同一个物理副本来实现的。可修改的代码和数据不能被共享，不能修改的代码可以被共享（即纯代码或可重入代码）。
对比分页。页有固定大小，所以可以通过整除得到段号和段内偏移；但分段方式需要显式地给出段号和段内偏移。

段页式管理方式

段页式：作业的地址空间被分成若干个逻辑段，每段都有自己的段号，然后将每一段分成若干个大小固定的页。
段页式逻辑地址：段号S+页号P+页内偏移量W。
流程：先通过段表查到页表起始地址，然后通过页表查到页帧号，最后形成物理地址。
特点：实际需要三次访问主存，可以使用快表加快查找速度。

碎片问题

只要是固定的分配就会产生内部碎片，其余的都会产生外部碎片。
段页式也要看作固定式的。