教材为西安电子科技大学 汤小丹老师 第四版 视频/图片来源：https://www.bilibili.com/video/BV1jv41147h8?p=1 操作系统系列目录： 第一章：操作系统引论 第二章：进程的描述与控制 第三章：处理机调度与死锁 第四章：存储器管理 第五章：虚拟存储器 第六章：输入输出系统 第七章：文件管理

存储器是计算机系统的重要组成部分之一。对存储器加以有效管理，不仅直接影响存储器的利用率，而且对系统性能有重大影响。 存储器管理的主要对象是内存，对外存的管理在文件管理中。

在多道程序环境下，要使程序运行，必须为之先建立进程。创建进程的第一件事是将程序和数据装入内存。 将用户源程序变为可在内存中执行的程序的步骤：

程序经过编译后得到一组目标模块，再利用链接程序将目标模块链接，形成装入模块。根据链接时间的不同，把链接分成三种： 1、静态链接：在程序运行前，将目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开。 2、装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式。 3、运行时动态链接：指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行链接。

将一个装入模块装入内存时，有三种方式：

绝对装入方式 可重定位装入方式 动态运行时装入方式

绝对装入方式 在编译时，如果知道程序驻留在内存的什么位置，那么编译程序将产生绝对地址的目标代码。 装入模块装入内存后，程序中的逻辑地址与实际内存地址完全相同，不须对程序和数据的地址进行修改。 程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员赋予。 只适合于单道程序环境

可重定位装入方式 在多道程序环境下，目标模块的起始地址通常从0开始，程序中的其他地址都是相对于起始地址计算的。因此应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。 注意：在采用可重定位装入方式将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。

动态运行时装入方式 动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。 装入内存后的所有地址都仍是相对地址。 为使地址转换不影响指令的执行速度，应设置一个重定位寄存器。

连续分配方式：指为一个用户程序分配一个连续的内存空间。

一、单一连续分配 二、固定分区分配 三、动态分区分配 四、可重定位分区分配

原理 将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，便可以有多道作业并发执行。 当有一空闲分区时，便可以再从外存的后备作业队列中，选择一个适当大小的作业装入该分区，当该作业结束时，可再从后备作业队列中找出另一作业调入该分区。

划分分区的方法 (1) 分区大小相等 所有的内存分区大小相等，缺乏灵活性 (2) 分区大小不等 把内存区划分成含有多个较小的分区、适量的中等分区及 少量的大分区。

实现 为便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中包括每个分区的起始地址、大小及状态(是否已分配)。 当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。

原理 动态分区分配是根据进程的实际需要，动态地为之分配内存空间。作业装入内存时，把可用内存分出一个连续区域给作业，且分区的大小正好适合作业大小的需要。 分区的大小和个数依装入作业的需要而定。

实现 在实现过程中涉及如下问题：

分区分配中的数据结构 分区分配算法 分区分配及回收操作

为把一个新作业装入内存，需按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。 常用的分配算法：

(1) 首次适应算法（first fit FF） (2) 循环首次适应算法 (3) 最佳适应算法（best fit BF） (4) 最坏适应算法（worst fit WF） (5) 快速适应算法(quick fit QF)

FF算法要求空闲分区表以地址递增的次序排列。在分配内存时，从表首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表中。若从头到尾不存在满足要求的分区，则分配失败。

在分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。   为实现算法，需要： 设置一起始查寻指针、采用循环查找方式  

所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。 要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。 缺点：产生许多难以利用的小空闲区

要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用。 该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。

是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针

分区分配

回收制度

连续分配方式会形成“碎片”，虽然可以通过“紧凑”解决，但开销大。如果允许将一个进程直接分散地装入许多不相邻的分区中，则无需“紧凑”，由此产生离散分配方式。

分类： 分页存储管理方式：离散分配的基本单位是页 分段存储管理方式：离散分配的基本单位是段   基本的分页存储管理方式(或纯分页存储管理方式)：不具备页面对换功能，不具有支持实现虚拟存储器的功能，要求把每个作业全部装入内存后方能运行。

分页式存储管理的原理:

将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页，并为各页加以编号，从0开始。   同时把内存空间分成与页面相同大小的若干个存储块，称为块或页框。   在为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻的物理块中。进程的最后一页经常装不满一块而形成“页内碎片”。

与4.6 请求分页式存储管理的区别

基本分页式存储管理（简单页式存储管理）的原理 系统若能满足一个作业所要求的全部块数，此作业才能被装入内存，否则不为它分配任何内存。   请求分页式存储管理的原理 运行一个作业时，并不要求把该作业的全部程序和数据都装入内存，可以只把目前要执行的几页调入内存的空闲块中，其余的仍保存在外存中，以后根据作业运行的需要再调入内存。

页面大小的选择

由机器的地址结构所决定的，即由硬件所决定 某一种机器只能采用一种大小的页面。 小：内碎片小，内存利用率高，但页面数目多，使页表过长，占大量内存，管理开销大 大：页表短，管理开销小，内碎片大，内存利用率低 页面大小应适中，是2的幂，通常是512B~8KB

地址结构 基本分页式存储管理（简单页式存储管理）的实现

进程的每一页离散地存储在内存的任一存储块中，为方便查找，系统为每一进程建立一张页面映像表，简称页表。 页表实现了从页号到物理块号的地址映射。

为了能将用户地址空间的逻辑地址变换为内存空间的物理地址，在系统中必须设置地址变换机构。

地址变换机构实现从逻辑地址到物理地址的转换，由于页内地址与物理地址是一 一对应的，因此，地址变换机构的任务是借助于页表，将逻辑地址中的页号转换为内存中的物理块号。   原理：

页表的功能可以由一组专门的寄存器来实现，一个页表项用一个寄存器。但寄存器成本高，系统页表可能很大，所以页表大多常驻内存。 在系统中只设置一个页表寄存器PTR，存放着页表在内存中的始址和页表的长度。平时，进程没有执行时，页表的始址和页表长度存放在进程的PCB中，当调度到进程时，才将这两个数据装入到页表寄存器中。

作业表

现代计算机系统都支持非常大的逻辑地址空间(232 ~264)，页表就非常大，需占用较大的地址空间。

例如：一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB 即 212B，则每个进程页表的页表项可达1M (232/212=220)个，若每个页表项占用一个字节，则每个进程的页表就要占据1MB的内存空间，而且要求连续存放。 解决方法： 采用离散方式存储 只将当前所需页表项调入内存

两级页表的实现： 上述方法用离散分配空间解决了大页表无需大片存储空间的问题，但并未减少页表所占的内存空间。 解决方法: 是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。在采用两级页表结构的情况下，对正在运行的进程，必须将其外层页表调入内存，而对页表则只需调入一页或几页。 这就需要在外层页表项中增设一个状态位S，用于表示该页表是否调入内存。

两级页表对32位机器适用，64位呢？ 页面大小为4KB即212B，还剩52位，按物理块大小212位来划分页表，则剩余40位用于外层页号，此时外层页表可能有1024G（240B）个页表项，要占用4096GB的连续存储空间

例1. 设页面大小为1KB，将逻辑地址3BADH划分为页号和页内偏移量两部分。用16进制表示。 例2. 设页面大小为2KB，将逻辑地址3BADH划分为页号和页内偏移量两部分。用16进制表示。

例3. 设页面大小为2KB，作业的页表如下图。求逻辑地址3BADH的物理地址。用16进制表示。

例4：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH转换成内存地址。 复杂做法

引入分段存储管理方式，主要是为了满足用户和程序员的需要  

1）段表 为使程序正常运行，须在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项。 段表结构：段号；段在内存中的起始地址(基址)；段长。 段表可以存放在寄存器中，但更多的是存放在内存中。 段表用于实现从 逻辑段 到 物理内存区 的映射。 2）地址变换机构 在系统中设置段表寄存器，用于存放段表始址和段表长度，以实现从进程的逻辑地址到物理地址的变换。 当段表存放在内存中时，每访问一个数据，都需访问两次内存，降低了计算机的速率。 解决方法：设置联想寄存器，用于保存最近常用的段表项。

分段系统的一个突出优点是易于实现段的共享和保护，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。 分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。

2. 地址变换过程 在段页式系统中，为了实现地址变换，增加一个段表寄存器，用来存放段表始址和段长。