4.1 存储器的层次结构
存储器的多层结构
最高层：CPU寄存器：寄存器
中间层：主存（内存）：高速缓存、主存储器、磁盘缓存
最底层：辅存：固定磁盘，可移动存储介质
可执行存储器
寄存器、主存（掉电信息丢失）——属于操作系统存储管理负责分配、回收，以及提供存储层次间数据移动的管理机制。
存储器管理的目的
主存的分配和管理：当用户需要内存时,系统为之分配相应的存储空间；不需要时，及时回收，以供其它用户使用。
提高主存储器的利用率：不仅能使多道程序动态地共享主存，提高主存利用率，最好还能共享主存中某个区域的信息。
“扩充”主存容量：为用户提供比主存物理空间大得多的地址空间，以至使用户感觉他的作业是在这样一个大的存储器中运行。
存储保护：确保多道程序都在各自分配到存储区域内操作，互不干扰，防止一道程序破坏其它作业或系统文件的信息。
一些基本概念
逻辑地址（相对地址，虚地址） ：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。不能用逻辑地址在内存中读取信息。
物理地址（绝对地址，实地址）：内存中存储单元的地址，可直接寻址。
地址空间
- 程序用来访问信息所用地址单元的集合
- 逻辑（相对）地址的集合
- 由编译程序生成
存储空间
- 主存中物理单元的集合
- 物理（绝对）地址的集合
- 由装配程序等生成
定位（存储分配）：为具体的程序和数据等分配存储单元或存储区工作。
映射：把逻辑地址转换为相应的物理地址的过程。
4.2 程序的装入和链接
对用户程序的处理步骤
用户程序要在系统中运行，必须先将其装入内存，然后再将其转变为一个可执行程序，通常都要经过以下几个步骤：
①编译：由编译程序对用户源程序编译，形成若干个目标模块。
②链接：由链接程序将一组目标模块及其所需库函数链接，形成一个完整的装入模块。
③装入：由装入程序将装入模块装入内存。
程序的装入
程序的装入（地址的变换）
绝对装入方式
编译程序产生绝对地址的目标代码，即代码的逻辑地址和物理地址相同。
装入程序按照装入模块中的地址，将程序和数据装入内存，不进行地址的修改。
只适用于单道程序环境。
可重定位装入方式
目标模块的起始地址从0开始，程序中其他地址相对于起始地址计算，装入程序根据内存的当前情况，将装入模块装入内存的适当位置。
重定位：在装入时对目标程序中指令和数据地址的修改过程。或者说：把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射（虚拟地址到内存地址映射）。
- 地址变换在装入时一次完成，以后不再改变，故称为静态重定位。
优点：无需增加硬件地址变换机构；实现简单；适用于多道程序环境。
缺点：不允许程序运行时在内存中移动位置；程序在存储空间中只能连续分配；多个用户难以共享存于内存中的同一程序。
动态运行时装入方式
装入程序把装入模块装入内存后，不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。
- 装入内存后的所有地址都仍是相对地址。
- 允许程序在内存中移动。
- 需要重定位寄存器的支持。
- 动态重定位。
优点：可对内存进行非连续分配；提供了实现虚存的基础；有利于程序段的共享。
程序的链接
静态链接方式
在程序运行之前，先将各目标模块以及所需的库函数，链接成一个完整的装配模块。
在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：
- 对相对地址进行修改。
- 变换外部调用符号。
装入时动态链接
采用边装入边链接的方式。
优点：便于修改和更新；便于实现对目标模块的共享。
缺点：程序每次要运行的模块可能不相同，但无法知道本次要运行哪些模块，故只能将所有可能要运行的模块都全部装入内存并链接。
运行时动态链接
对某些目标模块的链接，在程序执行中需要该模块时，才对它进行的链接。
优点：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。
4.3 连续分配存储管理方式
1 单一连续分配
最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中（单道程序环境下）。
内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间， 提供给用户使用。
优点：管理简单，不要求专用的硬件支持；为防止破坏OS ，设置界限寄存器；易于实现。
缺点：存储器利用率低；信息不共享；CPU 利用率低，周转时间长。
2 固定分区分配
运行多道程序的存储管理方式。
内存用户被划分为若干个固定大小的区域，每个分区中只装入一道作业。
内存利用率低。
允许几道作业并发。
划分分区的方法：分区大小相等；分区大小不等。
内存分配
分区使用表：各表项包括每个分区的起始地址，大小和状态。
用户程序需要装入时，内存分配程序检索该表，找出一个能满足要求尚未分配的分区，分配给该程序，并将其表项中的状态置为“已分配”。
若未找到大小足够的分区，则拒绝为用户程序分配内存。
3 动态分区分配 ★
（可变分区分配）
按作业的实际大小来划分分区，且分区个数也是随机的,实现多个作业对内存的共享，进一步提高内存资源利用率。
分区分配中的数据结构
空闲分区表，一个空闲分区占一个表目，表目包括：分区序号、分区始址、分区大小。
空闲分区链。
基于顺序搜索的动态分配分区算法
基于顺序搜索（依次搜索空闲分区链上的空闲分区，寻找一个其大小满足要求的分区）。
① 首次适应（FF, first fit）算法
把主存中所有空闲区按其物理地址递增的次序排列。在为作业分配存储空间时，从低址空闲区开始查找,直到找到第一个能满足要求的空闲区后，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲链中。
- 优先利用内存中低址部分的空闲分区，保留了高址部分的大空闲区。
- 低址部分不断被分割，形成很多难以利用的碎片。
② 循环首次适应（NF, next fit）算法
该算法是首次适应算法的变形，在为作业分配存储空间时，是从上次所分配的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的空闲区，从中划出一块与请求的大小相等的 一块存储区分配给作业。若到最后一个空闲区的大小仍不能满足要求时，应再从第一个空闲区开始查找。
需设置查询指针，用于指示下一次起始查寻的空闲分区，采用循环查找方式。
- 使空闲分区分布均匀，但是缺乏大的空闲区。
③ 最佳适应（BF, best fit）算法
“最佳”的含义是指每次为作业分配主存时，总是把既能满足要求，又是最小的空闲区分配给作业，以免由于“大材小用”而浪费主存。
为了加速查找，该算法要求将所有的空闲区按其大小递增次序排列；第一个找到能满足要求的空闲区一定是最佳的；每次分割的剩余部分都是最小的，因此在存储器中会留下很多难以利用的小碎片。
④ 最坏适应（WF, worst fit）算法
与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。
分区分配操作
分配内存
系统利用某种分配算法，从空闲分区表（链）中找到所需大小的分区。
分配流程见下图：
回收内存
系统根据回收区的首地址，从空闲区链中找到插入点后，会有四种情况出现：
- （1）回收区前是空闲分区
- （2）回收区后是空闲分区
- （3）回收区前、后都是空闲分区
- （4）回收区前、后都不是空闲分区
基于索引搜索的动态分区分配算法
快速适应(quick fit)算法
该算法又称为分类搜索法
将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表
系统中存在多个空闲分区链表
在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。
伙伴系统(buddy system)算法
分区大小均为2的k次幂(k为整数)
系统开始运行时，整个内存区是一个大小为2m的空闲分区，运行中不断划分
将空闲分区按分区的大小进行分类
具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表
不同大小的空闲分区形成了k个空闲分区链表。
大小为2k，地址为x的内存块，其伙伴块的地址则用buddyk(x)表示，其通式为:
4 动态可重定位分配
碎片问题
经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为“碎片”或“零头”。
碎片：因为内存中出现不相邻的小分区，而形成的不能被利用的小分区。
碎片问题的解决——“拼接”或“紧凑”
紧凑：移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区。
动态重定位的实现
每次“紧凑”后必须对移动了的程序或数据进行重定位。
地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，称为动态重定位。
硬件地址变换机构的支持——重定位寄存器。
内存地址＝相对地址＋重定位寄存器中的地址。
移动程序时只需修改重定位寄存器中的地址。
动态重定位分区分配算法
与动态分区分配算法基本相同，增加了紧凑的功能。见下图。
4.4 对换
多道程序环境下的对换技术
对换的引入
所谓“对换”， 是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。
OS必须实现三方面的功能：对换空间的管理、进程的换出、进程的换入。
对换的类型
整体对换/进程对换：中级调度
部分对换/页面对换/分段对换：虚拟存储器
对换空间的管理
对换区空间采用连续分配方式。
采用空闲分区表或空闲分区链。
对换空间的分配与回收，与动态分区方式时的内存分配与回收方法雷同。
进程的换入与换出
换出过程
选择处于阻塞状态且优先级最低的进程作为换出进程，换出后收回内存空间，修改进程的PCB相关信息
换入过程
找出“就绪”状态并已经换出的进程，将其中换出时间最久的进程作为换入进程，将其换入，直到已无可换入的进程和无可换出的进程。
4.5 分页存储管理方式 ★
离散存储管理方式
连续分配方式的缺点：形成许多“碎片”；“紧凑”开销大。
离散分配方式：无须“紧凑”，将一个用户程序离散地分配到内存中的多个不相连接的区域中。
- 分页存储管理方式－离散的基本单位是“页”
- 分段存储管理方式－离散的基本单位是“段”
- 段页式存储管理方式
在分页存储管理方式中，如果不具备页面对换功能，就是基本分页存储管理方式，即不支持虚拟存储器的功能。
分页存储管理方式
页面和物理块
页（页面）：把每个作业(进程)逻辑地址空间划分成若干大小相等的片.第0页、第1页。
(物理)块或页框(frame)：把内存空间分成与页面相同大小的若干个存储块。 0＃块、1＃块。 页内碎片：由于进程的最后一页经常装不满一块而形成了不可利用的碎片。
页面大小
太小，可使内存碎片减小，有利于提高内存利用率；会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率。
较大，可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。
页面的大小应选择得适中，且页面大小应是2的幂，通常为512 B~8 KB。
地址结构
对某特定机器，其地址结构是一定的。地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：
页表（页面映象表）
页表的作用是实现从页号到物理块号的地址映射。
由页号和块号组成，指出逻辑地址中页号与主存中物理块号的对应关系。
页号：作业地址空间的页序号。
块号：内存空间的页面序号。
地址变换机构
借助于页表，实现从逻辑地址到物理地址的转换。
基本的地址变换机构
页表驻留在内存中。
进程未执行时，页表的始址和页表长度存放在PCB中。
进程执行时，页表的始址和页表长度装入页表寄存器。
具有快表的地址变换机构
页表驻留在内存中的缺点：每存取一个数据都要两次访问内存。
联想寄存器（快表）：存放当前访问的若干个页表项。
具有快表的地址变换机构见下图。
二级页表
CPU具有32位地址时 ,使用2^32逻辑地址空间的分页系统,规定页面4KB时,每个进程页表的表项有1M(2^20)个,若表项占用1个字节,则每个进程需要占用1MB连续内存空间存放页表。
解决办法：把将页表进行分页,分成一张张小页表(称为页表页) ,小页表的大小与页框相同，为进行索引查找,应该为这些小页表建一张页目录表。
为离散分配的页表再建一张页表，称为：外层页表或页目录表。
逻辑地址结构可描述如下：
具有两级页表的地址变换机构：
二级页表地址变换需三次访问主存：一次访问页目录、一次访问页表页、一次访问指令或数据，访问时间加了两倍。
4.6 分段存储管理方式
引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要：
- 方便编程
- 信息共享
- 信息保护
- 动态增长
- 动态链接
分段系统的基本原理
每个段定义了一组逻辑信息，主程序段，子程序段，数据段等。
用段号代替段名。
两维逻辑地址：段号＋段内地址。
许多编译程序支持分段方式，自动根据源程序的情况产生若干个段。
利用段表实现地址映射：
地址变换机构
①在系统中设置段表寄存器，用于存放段表始址和段表长度。
②逻辑地址中的段号S与段表长度TL比较。
③若S>TL，段号太大，访问越界，产生越界中断信号。
④若S<TL，未越界，根据段表始址和该段段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。
⑤检查比较段内地址d和该段的段长SL。
⑥若d>SL，发出越界中断信号。
⑦若d<SL，未越界，段基址+段内地址=要访问的内存物理地址。
分页系统和分段系统的区别
(1) 页是信息的物理单位，由于系统管理的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
(2) 页的大小固定且由系统决定，而段的长度却不固定，它由其完成的功能决定。
(3) 分页的作业地址空间是一维的而分段的作业地址空间则是二维的，程序员在标识一个地址时，需给出段名和段内地址。
(4) 由于段是信息的逻辑单位，因此便于存贮保护和信息的共享，页的保护和共享受到限制。
信息共享
可重入码：又称为“纯代码”，是一种允许多个进程同时访问的代码。可重入代码是一种不允许任何进程对它进行修改的代码。
分段系统中，实现代码的共享比在分页系统中容易。
段页式存储管理方式
引入
分页和分段管理方式各有其优缺点，分页系统能有效提高内存的利用率，而分段则能更好地满足用户的需要，因此可以将两者结合成一种新的存储管理方式系统称为“段页式系统”。
原理
段页式存储管理系统，作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每段分成若干个大小相等的页。对于内存空间也分成大小相等的页，内存的分配以页为单位。
