操作系统期末复习

大纲

操作系统引论
- 为什么要学习操作系统？
- 操作系统目标与作用
- 操作系统的发展过程
- 操作系统的基本特征和主要功能
- 操作系统的结构设计
进程的描述与控制
- 前趋图和程序执行
- 进程的描述
- 进程控制
- 进程通信
- 线程
处理机调度与死锁
- 处理机调度概述
- 调度算法
- 实时调度
- 死锁概述
- 预防死锁
- 避免死锁
- 死锁的检测与解除
进程同步
- 进程同步
- 经典进程同步问题
存储器管理
- 存储器的层次与程序的装入链接
- 连续分配
- 页式管理
- 段式管理
虚拟存储器
- 虚拟存储器概述
- 请求分页管理
- 页面置换算法
- 请求分段管理
输入输出系统
- IO系统的功能、模型和接口
- IO设备和设备控制器
- 中断和中断处理程序
- 设备驱动程序
- 用户层的IO软件
- 缓冲管理
- 磁盘存储器的性能和调度
文件系统
- 文件和文件系统
- 文件的逻辑结构
- 文件目录
- 文件共享与保护
磁盘存储器的管理
- 外存组织方式
- 文件存储空间管理

思维导图

mindmap
  操作系统思维导图
    Chapter01 操作系统引论
      为什么要学习操作系统？
      操作系统目标与作用
      操作系统的发展过程
      操作系统的基本特征和主要功能
      操作系统的结构设计
    Chapter02 进程的描述与控制
      前趋图和程序执行
      进程的描述
      进程控制
      进程通信
      线程
    Chapter03 处理机调度与死锁
      处理机调度概述
      调度算法
      实时调度
      死锁概述
      预防死锁
      避免死锁
      死锁的检测与解除
    Chapter04 进程同步
      进程同步
      经典进程同步问题
    Chapter05 存储器管理
      存储器的层次与程序的装入链接
      连续分配
      页式管理
      段式管理
    Chapter06 虚拟存储器
      虚拟存储器概述
      请求分页管理
      页面置换算法
      请求分段管理
    Chapter07 输入输出系统
      IO系统的功能、模型和接口
      IO设备和设备控制器
      中断和中断处理程序
      设备驱动程序
      用户层的IO软件
      缓冲管理
      磁盘存储器的性能和调度
    Chapter08 文件系统
      文件和文件系统
      文件的逻辑结构
      文件目录
      文件共享与保护
    Chapter09 磁盘存储器的管理
      外存组织方式
      文件存储空间管理

总结

Chapter 1

一言

操作系统的目标是达到 ==方便性（Convenience==）、==有效性（Effectiveness）== 可扩充性（Extensibility 和开放性（Openness）
操作系统是用户和计算机硬件系统之间的接口；是计算机（各种）系统资源的管理者；实现了对计算机资源的抽象，使用户无需理会繁杂的硬件细节。
为了不断提高==计算机资源利用率==、为了方便用户（分时系统的出现）以及硬件的迭代和计算机体系结构的演进（从单批到多批），和新的应用需求被不断挖掘，这些原因是推动OS发展的主要动力
分时系统的特征：多路性、独立性、及时性、交互性、而实时系统在此之上更多了 可靠性（不是说分时就没有，而是实时的可靠性更突出）。

Chapter 2

概念

线程

为了减少程序在并发执行的时空开销，使OS具有更好的并发性，提出线程概念，并把线程作为调度和分派的基本单位。

线程的属性

与进程相比，线程作为==调度和分派的基本单位==，而进程则作为资源拥有的基本单位，所以同一个进程之间的线程切换不会引起进程切换。
一个进程的多个线程之间可以并发执行，具有==并发性==
相较于进程，线程的创建销毁和切换开销比进程远远小的多

线程的状态

和其状态设计和状态转换和进程状态一致

线程控制块（Thread control block， TCB）

线程标识符
寄存器组
线程运行状态
存储区
优先级
堆栈指针
信号屏蔽

线程设计与实现

内核支持线程（KST）
在内核空间实现，具有各种速度的优势和内核级支持，就是对于用户线程切换开销较大。
用户级线程（ULT）
在用户空间实现，不需要内核支持，但是依赖于系统调用，有系统调用的阻塞问题。
ULT 和 KST 的组合方式

进程

进程是程序的一次执行
进程是一个程序及其数据在处理机上顺序执行时产生的活动
进程是程序在一个数据集合上运行的过程。他是系统进行资源分配和调度的一个独立单位

进程的定义

几种经典定义：
1. 进程是程序的一次执行
2. 程是一个程序及其数据在处理机上顺序执行时产生的活动
3. 程是程序在一个数据集合上运行的过程。他是系统进行资源分配和调度的一个独立单位

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的特征

动态性（Concurrence） - 最基本的特征
==动态性==与否，还是看和谁比较，相较于程序，进程由创建而产生，由调度而执行，由撤销而消亡，也就是说进程实体具有生命周期，而程序只是一组有序指令的集合，存放于某种介质上，是==静态的==。
并发性
并发性与否，也是和看和谁比较，相较于程序，由同一个程序创建的多个进程实体可以同时存储在内存中，==且能在一段时间内同时运行==。
独立性
独立性指的是进程实体是一个能==独立运行==、==独立获得资源== 和 ==独立接受调度== 的 ==基本单位==。
异步性
进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进，也就是说其具有==独立性==、==不可预知性==。

进程的状态

就绪（Ready） - 已准备好运行，且已经被分配到除了CPU以外的所有必要资源
执行（Running） - 已获得CPU，正在执行
阻塞（Block） - 因为某种事件导致==暂时无法继续执行==时的状态，此时引起进程调度，OS把CPU分配给其他就绪进程，而令原进程暂停，这种暂停状态成为阻塞状态

进程控制块（Process Control Block PBC）

专门用于管理进程的数据结构，与进程一一对应。
系统利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。
OS中最重要的==记录型数据结构==

PCB的作用

PCB在进程创建时诞生，在进程结束时消亡，PCB记录了对于一个进程最重要的一些==数据（进程管理、进程调度所需要的信息）==，==OS是通过PCB来感知进程存在的==。

当进程因阻塞而暂停时，他需要保存运行时的上下文，从而使再次被调度运行时可以正常恢复CPU现场信息，而有了PCB，OS就可以把CPU现场信息保存在相应被中断进程的PCB中，从而恢复CPU现场，也就是==实现了间断式运行方式==。

在PCB中还具有用于用于实现进程通信的区域或通信队列指针，==用于实现与其他进程的同步与通信==。

PCB携带的信息

进程标识符 - 分为==外部标识符（由字母、数字组成）== 和 ==内部标识符（类似序号）==。
处理机状态信息 - 即处理机上下文，由各种寄存器的内容组成
1. 通用寄存器
2. 指令计数器
3. 程序状态字
4. 用户栈指针
进程调度信息
- 进程状态
- 进程优先级
- Others
进程控制信息 - 程序和数据的地址、进程同步和通信机制，资源清单，连接指针。

PCB的组织方式

线性

方便简单。
链接
![](https://l4p-bucket-1.oss-cn-shenzhen.aliyuncs.com/img/Pasted image 20250627002614.png)

看上去就像是链表一样~~
索引

索引，即映射。

一言

Section01

进程控制即==控制 进程状态 的切换==，一般由OS的内核中的==原语==来实现
OS中允许一个进程创建另一个进程，这使得进程之间具备==树形层次结构==
父子进程的互动应当遵循：子承父业、子死父还、父死子亡
描述 2. 中提到的结构的有向无环图的结构称为==进程图==

Section02

诸如“用户登录、作业调度、提供服务、应用请求”等事件都会引起进程创建
进程创建，先申请空白PCB再分配所需资源，然后初始化PCB，最后把进程丢进（就绪）队列
有三种事件会引起进程终止：正常结束、异常结束和外界干预。其规则可以参考 3.
对共享资源的请求。对某种操作的等待、IO相关等操作都会引起进程阻塞
进程阻塞的关键是要把PCB中的状态由执行改为阻塞，然后保存处理机上下文
进程唤醒的关键就是和阻塞相反
阻塞和唤醒是一对相对的原语，必须配对使用

Section03

为了用户可以==方便快捷==且==安全（隐藏细节）==的==高效传输大量数据==，OS提供了一组实现了高级通信的命令（原语）
进程通信具有四种类型的设计：共享存储器系统、==管道通信系统==、消息传递系统和 C/S系统、
共享存储区是共享存储器系统中的高效设计
管道通信以互斥、同步和确认机制协调通信
消息传递系统类似于计网的报文系统设计，分为直接和间接两种通信方式
C/S 系统是当下主流的通信方式，一般通过 Socket、RPC等技术实现

Chapter 3

前面说到，多道程序环境下内存中存在着多个进程，
而如何协调这些进程，合理的分配CPU资源，是主要问题。

概念

调度

调度的层次

低级调度 - 短程调度 / ==进程调度==
==低级调度==是以进程为对象的调度方式，根据某种调度算法，决定==就绪队列==中哪个进程应该获得处理机资源，在多道批处理、分时和实时OS中都有应用。
中级调度 - 中程调度 / ==内存调度==
是以==提高内存利用率和系统吞吐量==为目的的调度方式，将暂不运行的进程调至外存，让出资源给外存上急需运行的进程，即==对换==功能
高级调度 - 长程调度 / ==作业调度==
==高级调度==是以 作业（Job） 为对象的调度方式，根据某种算法，为处于外存上的==后备队列==中的作业调度（为作业创建进程并调入就绪队列）做出决策，主要用于多道批处理系统中。

调度的方式

分为抢占和非抢占式，==抢占式调度被现代OS广泛采用==

抢占方式的原则
1. 优先权原则 - 优先权高的来抢占
2. 短作业 / 短进程优先原则 - 作业短的来抢占
3. 时间片原则 - 每个进程按时间片分配

调度算法

先来先服务(first-come first-served，FCFS)调度算法
FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。系统按照作业到达的先后次序来进行调度，优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短。
短作业优先(short job first，SJF)的调度算法
　　SJF算法是以作业的长短来计算优先级，作业运行时间越短，其优先级越高。SJF算法可以分别用于作业调度和进程调度。
短作业优先算法的缺点
(1)必须预知作业的运行时间。一般都会偏长估计。
(2)对长作业非常不利，可能使长作业等待时间过长，出现饥饿现象。
(3) 在采用FCFS算法时，人—机无法实现交互。
(4)该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。
优先级调度算法(priority-scheduling algorithm，PSA)
基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法根据该优先级进行调度。如FCFS把作业等待时间看作优先级，等待时间越长优先级越高；SJF把作业运行时间看作优先级，运行时间越短，优先级越高。
高响应比优先调度算法(Highest Response Ratio Next，HRRN)
在批处理系统中，FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而SJF算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。　高响应比优先算法的实现：为每个作业引入一个动态优先级，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。

轮转调度算法
1. 轮转法的基本原理
　　在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。

2. 进程切换时机
　　在RR调度算法中，应在何时进行进程的切换，可分为两种情况：
① 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
② 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

3. 时间片大小的确定
　　在轮转算法中，时间片的大小对系统性能有很大的影响。时间片小，有利于短进程，但调度频繁开销大；时间片大，RR退化为FCFS，无法满足交互需求。时间片较为可取的大小为：略大于一次典型的交互所需时间。

实时调度算法 - 针对实时任务（HRT、SRT）的调度

死锁

引起死锁的原因和处理方案

资源分配图

如何预防死锁

如何避免死锁

死锁避免算法

当进程申请一个有效资源的时候，系统必须确定分配后是安全的，也就是说如果存在一个安全序列，则系统处于==安全状态==。
安全状态

这里的pi 和 pi-1 和pi+1 应该指的是拓扑序。

银行家算法

银行家算法的数据结构

死锁解除

一言

银行家算法的精髓在于，如果存在==安全序列==才允许分配
死锁检测的精髓在于图有环则死锁

Chapter 4

在OS中引入进程后，一方面可以使系统中的多道程序并发执行，这不仅能有效地改善资源利用率，还可显著地提高系统的吞吐量，但另一方面却使系统变得更加复杂。如果不能采取有效的措施，对多个进程的运行进行妥善的管理，必然会因为这些进程对系统资源的无序争夺给系统造成混乱。致使每次处理的结果存在着不确定性，即显现出其不可再现性。

概念

进程间的制约关系以及如何实现

1. 两种形式的制约关系
　　1) 间接相互制约关系
　　2) 直接相互制约关系

2. 临界资源(Critical Resouce)
　　许多硬件资源如打印机、磁带机等，都属于临界资源，诸进程间应采取互斥方式，实现对这种资源的共享。

3. 临界区(critical section)
　　不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)。
　　

==同步机制应遵循的规则==
　　为实现进程互斥地进入自己的临界区，可用软件方法，更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则：
　　(1)空闲让进。
　　(2)忙则等待。
　　(3)有限等待。
　　(4)让权等待。

信号量机制

1. 整型信号量
　　最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。很长时间以来，这两个操作一直被分别称为P、V操作。

2. 记录型信号量
　　在整型信号量机制中的wait操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针list，用于链接上述的所有等待进程。

3. AND型信号量
　　前面所述的进程互斥问题针对的是多个并发进程仅共享一个临界资源的情况。在有些应用场合，是一个进程往往需要获得两个或更多的共享资源后方能执行其任务。假定现有两个进程A和B，它们都要求访问共享数据D和E，当然，共享数据都应作为临界资源。

4. 信号量集
　　在前面所述的记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或减1操作，意味着每次只能对某类临界资源进行一个单位的申请或释放。当一次需要N个单位时，便要进行N次wait(S)操作，这显然是低效的，甚至会增加死锁的概率。此外，在有些情况下，为确保系统的安全性，当所申请的资源数量低于某一下限值时，还必须进行管制，不予以分配。因此，当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。

信号量的应用

1. 利用信号量实现进程互斥
　　为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。

一言：看作是两个小孩在玩一个球的模型即可，wait操作就是小孩在等待传球，signal操作则是传球，只有手上有球才能传球对吧？

2. 利用信号量实现前趋关系
　　还可利用信号量来描述程序或语句之间的前趋关系。设有两个并发执行的进程P1和P2。P1中有语句S1；P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系，只需使进程P1和P2共享一个公用信号量S，并赋予其初值为0，将signal(S)操作放在语句S1后面，而在S2语句前面插入wait(S)操作，即
　　在进程P1中，用S1；signal(S)；
　　在进程P2中，用wait(S)；S2；

一言：看作是一串小孩在排队传球，处于队列后方的小孩不断等待（wait操作），直到他的前一个小孩（前驱）传球给他（signal操作）。（这么一想更复杂的模型估计就是有向无环图了，每个点都有多个前驱）

管程机制

系统中的各种硬件资源和软件资源均可用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。
由上述的定义可知，管程由四部分组成：
① 管程的名称；
② 局部于管程的共享数据结构说明；
③ 对该数据结构进行操作的一组过程；
④ 对局部于管程的共享数据设置初始值的语句。

进程间同步的经典问题

生产者-消费者问题

1. 利用记录型信号量解决生产者-消费者问题
　　假定在生产者和消费者之间的公用缓冲池中具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。

2. 利用AND信号量解决生产者-消费者问题
　　对于生产者-消费者问题，也可利用AND信号量来解决，即用Swait(empty，mutex)来代替wait(empty)和wait(mutex)；用Ssignal(mutex，full)来代替signal(mutex)和signal(full)；用Swait(full，mutex)代替wait(full)和wait(mutex)，以及用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)。

哲学家进餐问题

1. 利用记录型信号量解决哲学家进餐问题
　　经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。

2. 利用AND信号量机制解决哲学家进餐问题
　　在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。

读者-写者问题

1. 利用记录型信号量解决读者-写者问题
　　为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Readcount=0，表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。

2. 利用信号量集机制解决读者-写者问题
　　这里的读者—写者问题，与前面的略有不同，它增加了一个限制，即最多只允许RN个读者同时读。为此，又引入了一个信号量L，并赋予其初值为RN，通过执行wait(L, 1, 1)操作来控制读者的数目，每当有一个读者进入时，就要先执行wait(L, 1, 1)操作，使L的值减1。当有RN个读者进入读后，L便减为0，第RN + 1个读者要进入读时，必然会因wait(L, 1, 1)操作失败而阻塞。

Chapter 5

存储器的层次与程序的装入链接

存储器的层次结构

多层结构的存储器系统
对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。
可执行存储器
在计算机系统的存储层次中，寄存器和主存储器又被称为可执行存储器。对于存放于其中的信息，与存放于辅存中的信息相比较而言，计算机所采用的访问机制是不同的，所需耗费的时间也是不同的。进程可以在很少的时钟周期内使用一条load或store指令对可执行存储器进行访问。但对辅存的访问则需要通过I/O设备实现，因此，在访问中将涉及到中断、设备驱动程序以及物理设备的运行，所需耗费的时间远远高于访问可执行存储器的时间，一般相差3个数量级甚至更多。
主存储器与寄存器
主存储器简称内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据，属于可执行存储器。
寄存器具有与处理机相同的速度，故对寄存器的访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。
高速缓存
高速缓存是现代计算机结构中的一个重要部件，它是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，这样可大幅度地提高程序执行速度。高速缓存容量远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。
磁盘缓存
由于目前磁盘的I/O速度远低于对主存的访问速度，为了缓和两者之间在速度上的不匹配，而设置了磁盘缓存，主要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息。主存也可以看作是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用，反之，数据也必须先存在主存中，才能输出到辅存。

程序的装入和链接

用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：
(1) 编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(Object Module)；
(2) 链接，由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；
(3) 装入，由装入程序(Loader)将装入模块装入内存。

程序的装入

在将一个装入模块装入内存时，可以有如下三种装入方式：

绝对装入方式(Absolute Loading Mode)
当计算机系统很小，且仅能运行单道程序时，完全有可能知道程序将驻留在内存的什么位置。此时可以采用绝对装入方式。用户程序经编译后，将产生绝对地址(即物理地址)的目标代码。
> 特点：程序中所使用的地址与实际内存地址完全相同。
可重定位装入方式(Relocation Loading Mode)
在多道程序环境下，编译程序不可能预知经编译后所得到的目标模块应放在内存的何处。因此，对于用户程序编译所形成的若干个目标模块，它们的起始地址通常都是从0开始的，程序中的其它地址也都是相对于起始地址计算的。装入时，对目标程序中的指令和数据地址的修改过程称为重定位。
动态运行时的装入方式(Dynamic Run-time Loading)
可重定位装入方式可将装入模块装入到内存中任何允许的位置，但该方式并不允许程序运行时在内存中移动位置。
动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是逻辑地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。

程序的链接

静态链接(Static Linking)方式
在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。在将目标模块装配成一个装入模块时，须解决以下两个问题：
(1) 对相对地址进行修改。
(2) 变换外部调用符号。
装入时动态链接(Load-time Dynamic Linking)
指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要修改目标模块中的相对地址。装入时动态链接方式有以下优点：
(1) 便于修改和更新。
(2) 便于实现对目标模块的共享。
运行时动态链接(Run-time Dynamic Linking)
典型的例子是作为错误处理用的目标模块，如果程序在整个运行过程中都不出现错误，则显然就不会用到该模块。如果装入时全部链接，显然低效。
运行时动态链接方式，将对某些模块的链接推迟到程序执行时才进行。亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块，并将之装入内存，将其链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅能加快程序的装入过程，而且可节省大量的内存空间。

连续分配

连续分配存储管理

单一连续分配
在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。

固定分区分配

划分分区的方法
(1)分区大小相等(指所有的内存分区大小相等)。
(2)分区大小不等。
内存分配
　　为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。

动态分区分配
　　动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。主要学习该管理方法的：数据结构、分区分配算法和分区的分配与回收操作。

动态分区分配中的数据结构
①空闲分区表
在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项。
②空闲分区链
在每个分区的起始部分设置一些用于控制分区分配的信息，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链表。
动态分区分配算法
　　为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。
1. 首次适应(first fit，FF)算法
2. 循环首次适应(next fit，NF)算法
3. 最佳适应(best fit，BF)算法
4. 最坏适应(worst fit，WF)算法
5. 快速适应(quick fit)算法
6. 伙伴系统(buddy system)算法
7. 哈希算法

3. 分区分配操作
1)分配内存
　　系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。
2)回收内存
　　当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：
(1) 回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。
—
(2) 回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
—
(3) 回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。
—
(4) 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

基于顺序搜索的动态分区分配算法

首次适应(firstfit，FF)算法
FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败，返回。
循环首次适应(nextfit，NF)算法
为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。

3. 最佳适应(bestfit，BF)算法
所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。

4. 最坏适应(worstfit，WF)算法
由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。

分配算法	优点	缺点
FF	保留高地址大空闲区	低地址产生很大碎片
NF	空闲区分布均匀	缺乏大的空闲区
BF	保留了大的空闲区	产生大量难以利用的碎片
WF	碎片少、查找效率高	可能缺乏大的空闲区

基于索引搜索的动态分区分配算法

快速适应(quickfit)算法
该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。该算法在搜索可分配的空闲分区时分为两步：第一步是根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表；第二步是从链表中取下第一块进行分配即可。优点是不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片，查找效率高。缺点在于为了有效合并分区，在分区归还主存时的算法复杂，系统开销较大。一个分区只属于一个进程。
伙伴系统(buddysystem)
该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，l≤k≤m)。通常2m是整个可分配内存的大小(也就是最大分区的大小)。假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断地划分，将会形成若干个不连续的空闲分区，将这些空闲分区按分区的大小进行分类。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，这样，不同大小的空闲分区形成了k个空闲分区链表。
哈希算法
哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。

动态可重定位分区分配

紧凑——碎片整理
连续分配方式的一个重要特点是，一个系统或用户程序必须被装入一片连续的内存空间中。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲空间。即使这些分散的许多小分区的容量总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。
动态重定位
作业装入内存后的所有地址仍然都是相对(逻辑)地址。而将相对地址转换为绝对(物理)地址的工作被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。
动态重定位分区分配算法
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：增加了紧凑的功能。通常，当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这时便须对内存进行“紧凑”，将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求，则返回分配失败信息。

对换(Swapping)

对换技术也称为交换技术，最早用于麻省理工学院的单用户分时系统CTSS中。由于当时计算机的内存都非常小，为了使该系统能分时运行多个用户程序而引入了对换技术。系统把所有的用户作业存放在磁盘上，每次只能调入一个作业进入内存，当该作业的一个时间片用完时，将它调至外存的后备队列上等待，再从后备队列上将另一个作业调入内存。这就是最早出现的分时系统中所用的对换技术。现在已经很少使用。

多道程序环境下的对换技术

对换的引入
在多道程序环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，却占用了大量的内存空间；另一方面，却又有着许多作业因内存空间不足，而不能进入内存运行。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。
“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便把已具备运行条件的进程或进程所需要的程序和数据换入内存。对换是改善内存利用率的有效措施，它可以直接提高处理机的利用率和系统的吞吐量。

2.对换的类型
在每次对换时，都是将一定数量的程序或数据换入或换出内存。根据每次对换时所对换的数量，可将对换分为如下两类：
(1) 整体对换——中级调度，以整个==进程==为单位。
(2)页面(分段)对换——虚拟存储器，以==页面或段==为单位。

对换空间的管理

对换空间管理的主要目标
在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区两部分：
1)对文件区管理的主要目标
提高文件存储空间的利用率，提高对文件的访问速度。对文件区空间的管理采取离散分配方式。
2)对对换空间管理的主要目标
提高进程换入和换出的速度，提高文件存储空间的利用率。对对换区空间的管理采取连续分配方式，较少考虑外存中的碎片问题。
对换区空闲盘块管理中的数据结构
为了实现对对换区中的空闲盘块的管理，在系统中应配置相应的数据结构，用于记录外存对换区中的空闲盘块的使用情况。其数据结构的形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表的每个表目中，应包含两项：对换区的首址及其大小，分别用盘块号和盘块数表示。
对换空间的分配与回收
由于对换分区的分配采用的是连续分配方式，因而对换空间的分配与回收与动态分区方式时的内存分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法等。具体的分配操作也与内存的分配过程相同。

进程的换出与换入

进程的换出
对换进程在实现进程换出时，是将内存中的某些进程调出至对换区，以便腾出内存空间。换出过程可分为以下两步：
(1)选择被换出的进程 ——阻塞或睡眠进程或最低优先级进程。
(2)进程换出过程。 ——只能换出非共享的程序和数据段。
进程的换入
对换进程将定时执行换入操作，它首先查看PCB集合中所有进程的状态，从中找出“就绪”状态但已换出的进程。当有许多这样的进程时，它将选择其中已换出到磁盘上时间最久(必须大于规定时间，如2 s)的进程作为换入进程，为它申请内存。如果申请成功，可直接将进程从外存调入内存；如果失败，则需先将内存中的某些进程换出，腾出足够的内存空间后，再将进程调入。

连续分配存储管理

单一连续分配

　　在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。

固定分区分配

划分分区的方法
(1)分区大小相等(指所有的内存分区大小相等)。
(2)分区大小不等。
内存分配
　　为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。

动态分区分配

　　动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。主要学习该管理方法的：数据结构、分区分配算法和分区的分配与回收操作。

动态分区分配中的数据结构
①空闲分区表。在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项。
②空闲分区链。在每个分区的起始部分设置一些用于控制分区分配的信息，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链表。
动态分区分配算法

　　为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。
    1. 首次适应(first fit，FF)算法
    2. 循环首次适应(next fit，NF)算法
    3. 最佳适应(best fit，BF)算法
    4. 最坏适应(worst fit，WF)算法
    5. 快速适应(quick fit)算法
    6. 伙伴系统(buddy system)算法
    7. 哈希算法

3. 分区分配操作
1)分配内存
　　系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。

2)回收内存
　　当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：
(1) 回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。

(2) 回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。

(3) 回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。

(4) 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

基于顺序搜索的动态分区分配算法

首次适应(firstfit，FF)算法FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败，返回。
循环首次适应(nextfit，NF)算法
为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。

3. 最佳适应(bestfit，BF)算法
　　所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。

分配算法	优点	缺点
FF	保留高地址大空闲区	低地址产生很大碎片
NF	空闲区分布均匀	缺乏大的空闲区
BF	保留了大的空闲区	产生大量难以利用的碎片
WF	碎片少、查找效率高	可能缺乏大的空闲区

基于索引搜索的动态分区分配算法

快速适应(quickfit)算法
该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。该算法在搜索可分配的空闲分区时分为两步：第一步是根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表；第二步是从链表中取下第一块进行分配即可。优点是不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片，查找效率高。缺点在于为了有效合并分区，在分区归还主存时的算法复杂，系统开销较大。一个分区只属于一个进程。
伙伴系统(buddysystem)
该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，l≤k≤m)。通常2m是整个可分配内存的大小(也就是最大分区的大小)。假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断地划分，将会形成若干个不连续的空闲分区，将这些空闲分区按分区的大小进行分类。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，这样，不同大小的空闲分区形成了k个空闲分区链表。
哈希算法
哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。

动态可重定位分区分配

紧凑——碎片整理
连续分配方式的一个重要特点是，一个系统或用户程序必须被装入一片连续的内存空间中。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲空间。即使这些分散的许多小分区的容量总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。
动态重定位
　　作业装入内存后的所有地址仍然都是相对(逻辑)地址。而将相对地址转换为绝对(物理)地址的工作被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。
动态重定位分区分配算法
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：增加了紧凑的功能。通常，当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这时便须对内存进行“紧凑”，将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求，则返回分配失败信息。

对换(Swapping)

多道程序环境下的对换技术

对换的引入
在多道程序环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，却占用了大量的内存空间；另一方面，却又有着许多作业因内存空间不足，而不能进入内存运行。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。
“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便把已具备运行条件的进程或进程所需要的程序和数据换入内存。对换是改善内存利用率的有效措施，它可以直接提高处理机的利用率和系统的吞吐量。
对换的类型
在每次对换时，都是将一定数量的程序或数据换入或换出内存。根据每次对换时所对换的数量，可将对换分为如下两类：
(1) 整体对换——中级调度，以整个进程为单位。
(2)页面(分段)对换——虚拟存储器，以页面或段为单位。

对换空间的管理

对换空间管理的主要目标
在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区两部分：
1)对文件区管理的主要目标
提高文件存储空间的利用率，提高对文件的访问速度。对文件区空间的管理采取离散分配方式。
2)对对换空间管理的主要目标
提高进程换入和换出的速度，提高文件存储空间的利用率。对对换区空间的管理采取连续分配方式，较少考虑外存中的碎片问题。
对换区空闲盘块管理中的数据结构
为了实现对对换区中的空闲盘块的管理，在系统中应配置相应的数据结构，用于记录外存对换区中的空闲盘块的使用情况。其数据结构的形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表的每个表目中，应包含两项：对换区的首址及其大小，分别用盘块号和盘块数表示。
对换空间的分配与回收
由于对换分区的分配采用的是连续分配方式，因而对换空间的分配与回收与动态分区方式时的内存分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法等。具体的分配操作也与内存的分配过程相同。

进程的换出与换入

进程的换出
对换进程在实现进程换出时，是将内存中的某些进程调出至对换区，以便腾出内存空间。换出过程可分为以下两步：
(1)选择被换出的进程 ——阻塞或睡眠进程或最低优先级进程。
(2)进程换出过程。 ——只能换出非共享的程序和数据段。
进程的换入
对换进程将定时执行换入操作，它首先查看PCB集合中所有进程的状态，从中找出“就绪”状态但已换出的进程。当有许多这样的进程时，它将选择其中已换出到磁盘上时间最久(必须大于规定时间，如2 s)的进程作为换入进程，为它申请内存。如果申请成功，可直接将进程从外存调入内存；如果失败，则需先将内存中的某些进程换出，腾出足够的内存空间后，再将进程调入。

页式管理

分页存储管理方式

1. 页面和物理块
　　(1)页面——按进程逻辑地址分为等长的若干页。
物理块——按内存物理地址分成与页面一致大小的若干存储块。
　　(2)页面大小——1K~8K，太小效率低，太大页内碎片。

2. 地址结构
对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：

3.页表
在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。页表实现从页号到物理块的地址映射。

地址变换机构

基本的地址变换机构进程在运行期间，需要对程序和数据的地址进行变换，即将用户地址空间中的逻辑地址变换为内存空间中的物理地址，由于它执行的频率非常高，每条指令的地址都需要进行变换，因此需要采用硬件来实现。页表功能是由一组专门的寄存器来实现的。一个页表项用一个寄存器。但寄存器成本高，页表一般驻留内存，只设置一个页表寄存器（PTR）指向页表位置。
具有快表的地址变换机构
由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。因此，采用这种方式将使计算机的处理速度降低近1/2。
引入具有并行查寻能力的特殊高速缓冲寄存器（联想寄存器，快表）提升查找速度。速度损失可减少到10%以下。

访问内存的有效时间

从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间，称为内存的有效访问时间(EffectiveAccess Time，EAT)。假设访问一次内存的时间为t，在基本分页存储管理方式中，有效访问时间分为第一次访问内存时间(即查找页表对应的页表项所耗费的时间t)与第二次访问内存时间(即将页表项中的物理块号与页内地址拼接成实际物理地址所耗费的时间t)之和：　EAT = t + t = 2t

在引入快表的分页存储管理方式中，通过快表查询，可以直接得到逻辑页所对应的物理块号，由此拼接形成实际物理地址，减少了一次内存访问，缩短了进程访问内存的有效时间。但是，由于快表的容量限制，不可能将一个进程的整个页表全部装入快表，所以在快表中查找到所需表项存在着命中率的问题。所谓命中率，是指使用快表并在其中成功查找到所需页面的表项的比率。这样，在引入快表的分页存储管理方式中，有效访问时间的计算公式即为：
$$
EAT=а×λ+(t+λ)(1-а)+t=2t+λ—t×а
$$

λ表示查找快表所需要的时间，а表示命中率，t表示访问一次内存所需要的时间。

两级和多级页表

两级页表(Two-Level Page Table)
针对难于找到大的连续的内存空间来存放页表的问题，可利用将页表进行分页的方法，使每个页面的大小与内存物理块的大小相同，并为它们进行编号，即依次为0# 页、1# 页，…，n# 页，然后离散地将各个页面分别存放在不同的物理块中。同样也要为离散分配的页表再建立一张页表，称为外层页表(OuterPage Table)，在每个页表项中记录了页表页面的物理块号。

为了方便实现地址变换，在地址变换机构中，同样需要增设一个外层页表寄存器，用于存放外层页表的始址。

多级页表
对于32位的机器，采用两级页表结构是合适的，但对于64位的机器呢？如果页面大小仍采用4KB即$2^12 $B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项，要占用16 384GB的连续内存空间。
必须采用多级页表，将外层页表再进行分页，再利用第2级的外层页表来映射它们之间的关系。在近两年推出的64位OS中，把可直接寻址的存储器空间减少为45位长度（即245）左右，这样便可利用三级页表结构来实现分页存储管理。

反置页表(Inverted Page Table)

反置页表的引入
在分页系统中，为每个进程配置了一张页表，进程逻辑地址空间中的每一页，在页表中都对应有一个页表项。在现代计算机系统中，通常允许一个进程的逻辑地址空间非常大，因此就需要有许多的页表项，而因此也会占用大量的内存空间。
地址变换
在利用反置页表进行地址变换时，是根据进程标识符和页号，去检索反置页表。如果检索到与之匹配的页表项，则该页表项(中)的序号i便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送内存地址寄存器。若检索了整个反置页表仍未找到匹配的页表项，则表明此页尚未装入内存。对于不具有请求调页功能的存储器管理系统，此时则表示地址出错。对于具有请求调页功能的存储器管理系统，此时应产生请求调页中断，系统将把此页调入内存。

段式管理

分段存储管理

一言：分段存储管理方式的引入，是以用户（进程）的视角看的，段式更符合用户使用的逻辑。

方便编程
用户把自己的作业按照逻辑关系划分为若干个段，每个段都从0开始编址，并有自己的名字和长度。因此，程序员们都迫切地需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，这不仅可以方便程序员编程，也可使程序非常直观，更具可读性。
信息共享
在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。比如，为了共享某个过程、函数或文件。分页系统中的“页”只是存放信息的物理单位(块)，并无完整的逻辑意义，这样，一个可被共享的过程往往可能需要占用数十个页面，这为实现共享增加了困难。段是信息的逻辑单位，因此，可以为该被共享过程建立一个独立的段，这就极大地简化了共享的实现。
信息保护
信息保护同样是以信息的逻辑单位为基础的，而且经常是以一个过程、函数或文件为基本单位进行保护的。分段管理方式能比分页管理更有效和方便地实现对信息的保护功能。
动态增长
在实际应用中，往往存在着一些段，尤其是数据段，在它们的使用过程中，由于数据量的不断增加，而使数据段动态增长，相应地它所需要的存储空间也会动态增加。然而，对于数据段究竟会增长到多大，事先又很难确切地知道。对此，很难采取预先多分配的方法进行解决。
动态链接
为了提高内存的利用率，系统只将真正要运行的目标程序装入内存，也就是说，动态链接在作业运行之前，并不是把所有的目标程序段都链接起来。当程序要运行时，首先将主程序和它立即需要用到的目标程序装入内存，即启动运行。而在程序运行过程中，当需要调用某个目标程序时，才将该段(目标程序)调入内存并进行链接。

分段系统的基本原理

分段
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D及栈段S等，
段表
在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个连续的分区。进程中的各个段，可以离散地装入内存中不同的分区中。为保证程序能正常运行，就必须能从物理内存中找出每个逻辑段所对应的位置。
地址变换机构
为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若S>TL，表示段号太大，是访问越界，于是产生越界中断信号。若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。然后，再检查段内地址d是否超过该段的段长SL。若超过，即d>SL，同样发出越界中断信号。若未越界，则将该段的基址d与段内地址相加，即可得到要访问的内存物理地址。
分页和分段的主要区别
　　(1)页是信息的物理单位。
　　(2)页的大小固定且由系统决定。
　　(3)分页的用户程序地址空间是一维的。

信息共享

分页系统中对程序和数据的共享
　　在分页系统中，虽然也能实现对程序和数据的共享，但远不如分段系统来得方便。
分段系统中程序和数据的共享
　　在分段系统中，由于是以段为基本单位的，不管该段有多大，我们都只需为该段设置一个段表项，因此使实现共享变得非常容易。

段页式存储管理方式

基本原理
段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。作业有三个段：主程序段、子程序段和数据段；页面大小为 4KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成，在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。下图演示了利用段表和页表进行从用户地址空间到物理(内存)空间的映射。

地址变换过程
在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长TL。进行地址变换时，首先利用段号S，将它与段长TL进行比较。若S < TL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。

Chapter 6

虚拟存储器概述

1.常规存储器管理方式的特征
(1) 一次性：作业必须一次性全部装入内存方能开始运行。
(2) 驻留性：作业被装入内存后，运行期一直驻留内容。

2. 局部性原理
程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。
（1）大多数情况下程序是顺序执行的；
（2）函数过程调用深度有限，一般不超过5层；
（3）程序中存在许多循环结构；
（4）程序包括许多对数据结构（如数组）的处理；
—
局限性又表现在下述两个方面：
(1) 时间局限性：典型原因为存在大量的循环操作。
(2) 空间局限性：典型情况便是程序的顺序执行

3. 虚拟存储器的基本工作情况　　
基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在外存磁盘上。
（1）缺页（段）中断请求；
（2）页（段）置换功能。

4. 虚拟存储器的定义
具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

5. 虚拟存储器的特征
与传统的存储器管理方式比较，虚拟存储器具有以下三个重要特征：
(1) 多次性：一个作业中的程序和数据允许被分成多次调入内容允许。
(2) 对换性：经常运行期间，允许将暂不使用的代码和数据换出外存，需要时再将其换入内存。
(3) 虚拟性：指从逻辑上扩充了内存的容量。

6. 虚拟存储器的实现方法

分页请求系统
1)硬件支持
(1) 请求分页的页表机制。
(2) 缺页中断机构。
(3) 地址变换机构。
2)实现请求分页的软件
请求分段系统
1)硬件支持
(1) 请求分段的段表机制。
(2) 缺页中断机构。
(3) 地址变换机构。
2)软件支持