操作系统引论

操作系统的目标

• 有效性
  • 提高系统资源利用率
  • 提高系统的吞吐量

操作系统的作用

• OS作为用户与计算机硬件系统之间的接口
• OS作为计算机系统资源的管理者
• OS实现了对计算机资源的抽象

操作系统的发展过程

• 无操作系统的计算机：通过人工打卡的方式编写程序和数据，通过纸带输入机来读取内容。会有如下问题1）人机矛盾：人工操作会浪费CPU时间；2）CPU和I/O设备之间速度不匹配。
  • 脱机输入/输出方式：借助一台外围机，提前输入卡带内容到磁带上。在CPU需要程序和数据的时候，直接从磁带上读取。
• 单道批处理系统：在脱机的方式下把一批数据输入到磁带上，在系统中配置监督程序，在监督程序的控制下使得这批作业一个接一个地连续处理，直到磁带上的作业全部被完成。同时只会运行一个作业。
• 多道批处理系统：用户所提交的作业都存放在外存的一个后备队列上，由作业调度程序按一定的算法从后备队列选择若干个作业调入内存，使他们共享CPU和系统中的各种资源。多道批处理系统会在一个作业等待I/O的时候切换CPU去执行其它作业。
• 分时系统：在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。分时系统的特点是可以及时处理用户的请求并返回响应。分时系统要求所有用户提交的作业都驻扎在内存中，并且将CPU时间划分为很短的时间片，在时间片之间允许切换执行的程序。
• 实时系统：实时系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

并发与并行

• 并发：多个事件在同一时间间隔内发生
• 并行：多个事件在同一时刻发生

进程

进程是指在系统中能独立运行并作为资源分配的基本单位。

线程

线程是独立运行和独立调度的基本单位。

虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。操作系统中利用两种方式实现虚拟技术

• 时分复用技术
  • 虚拟处理机技术：为每道程序建立一个进程，让多道程序并发执行来分时使用一台处理机
  • 虚拟设备技术：一台物理I/O设备虚拟为多台逻辑上的I/O设备，并允许每个用户占用一台逻辑上的I/O设备
• 空分复用技术
  • 虚拟磁盘技术：将一台硬盘虚拟为多台虚拟磁盘，可以安装在不同的逻辑驱动器上
  • 虚拟存储器技术：通过内存分时复用，提高内存的利用率

处理机管理

创建和撤销进程，对诸进程的运行进行协调，实现进程之间的信息交换，以及按照一定的算法把处理机分配给进程。

通常的程序是不能并发执行的，为了是程序能独立运行，需要配置一进程控制块（PCB），而由程序段、相关的数据段和PCB三部分便构成了进程实体。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程一般拥有下面三种基本状态

• 就绪状态：进程已经分配到除CPU外的所有必要资源。通常这样的进程排成一个队列，称为就绪队列。
• 执行状态：进程已经得到CPU，正在执行。
• 阻塞状态：正在执行的进程由于某事件而暂时无法继续执行。

处于就绪状态的进行在分配到处理机之后，就可以开始执行，进入执行状态。如果分配给进程的时间片被用完，则进程暂停执行，变成就绪状态。如果发生某事件而使得进程的执行受阻，则进入阻塞状态。

对于临界资源，多个进程必须互斥地对它进行访问，人们把在进程中访问临界资源的那段代码称为临界区（critical section）。要实现进程互斥进入自己的临界区，需要同步机制来协调各进程间的运行，所有同步机制都应遵循下述四条准则：

• 空闲让进：当没有进程处于临界区，这时候应该允许一个请求进入临界区的进程立即进入自己的临界区，以有效利用临界资源
• 忙则等待：当已有进程进入临界区，其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问
• 有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，避免陷入死等。
• 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。

整形信号量

信号量定义为一个用于表示资源数目的整数量S。除初始化外，仅支持两个标准的原子操作wait(S)和signal(S)。

wait(S): 
    while S <= 0 do no-op
    S := S - 1

signal(S):
    S := S + 1

整形信号量不符合让权等待准则。

记录型信号量

记录型信号量，还维护一个进程链表L，用于保存所有等待的进程。

wait(S):
    S.value := S.value - 1
    if S.value < 0 then block(S.L)

signal(S):
    S.value := S.value + 1
    if S.value <= 0 then wakeup(S.L)

管程（Monitors）

一个管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。

• 管程的名称
• 局部于管程的共享数据结构说明
• 对该数据结构进行操作的一组过程
• 对局部于管程内部的共享数据设置初始值的语句

条件变量

考虑一个进程调用了管程，在管程中被阻塞，等待阻塞的原因解除，在这期间，如果进程不释放管程，则其它进程无法进入管程，被迫长时间等待。

为了解决这个问题，引入了条件变量condition，通常一个进程被阻塞或挂起的条件可以有多个，因此管程中设置了多个条件变量，对这些条件变量的访问，只能发生在管程中。对条件变量的操作仅仅是wait和signal，每个条件变量保存一个链表，用于记录因该条件变量而阻塞的所有进程。

• x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait把自己插入到x条件的等待队列上，并释放管程，直到x条件变化
• x.signal：正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程（如果有多个，任意选择一个，如果没有则继续执行原进程）。

操作系统通过引入线程，来减少程序在并发执行时所付出的时空开销。在引入线程的操作系统中，把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位。

• 调度：线程是调度和分派的基本单位
• 并发性：同一个进程中的不同线程可以并发执行
• 拥有资源：进程中的所有资源都可以供该进程中的所有线程所共享
• 系统开销：创建和销毁进程需要分配和释放进程的资源，开销要大于线程的创建和销毁。同理同一个进程内的线程切换的代价也要小于进程之间切换的代价。

内核支持线程

内核支持线程KST是在内核支持下运行的。优点如下

• 内核能够同时调度同一进程中的多个线程并行执行
• 如果进程中的一个线程被阻塞了，内核可以调度该进程中的其它线程占有处理器运行，也可以运行其它进程中线程。
• 内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小。
• 内核本身也可以采用多线程技术，可以提高系统的执行效率

• 对于用户的线程切换而言，模式切换的开销较大

用户级线程

用户级线程ULT仅存在于用户空间中。用户线程的创建、销毁等都无需系统调用来实现。对于用户级线程的切换，如果发生在同一个进程中，则无需内核的支持，因此切换速度特别快。特殊的是，对于设置了用户级线程的系统，其调度仍然是以进程为单位进行的。在采用轮转调度算法时，各个进程轮流执行一个时间片，而进程中所有线程分用这个时间片。

用户级线程的优点

• 线程切换发生在用户态
• 调度算法可以是进程专用的
• 用户级线程的实现与操作系统平台无关

• 系统调用的阻塞问题：当一个线程陷入I/O等待，则整个进程会陷入I/O等待，其余线程无法被调度
• 一个进程最多只能分配到一个CPU

组合方式

在组合方式下，内核支持多KST线程的建立、调度和管理，同时也允许用户应用程序建立、调度和管理用户级线程。

用户级线程与内核控制线程的连接

• 一对一模型
• 多对一模型
• 多对多模型

处理机调度与死锁

高级调度

高级调度又称为作业调度与长程调度，其主要功能是根据某种算法，把外存上处于后备队列的那些作业调入内存。作业包含通常的程序和数据，以及一份作业说明书，系统根据该说明书对程序的运行进行控制。

低级调度

通常把低级调度称为进程调度或短程调度，它所调度的对象是进程（或内核级线程）。

• 保存处理机的现场信息
• 按某种算法选取进程
• 把处理器分配给进程

• 排队器：将就绪进程按照一定的方式排成一个或多个队列
• 分配器：把进程调度程序选定的进程，从就绪队列中取出，并进行上下文切换，将处理机分配给它
• 上下文切换机制：当对处理机进行切换时，会发生两对上下文切换操作1）先保存当前进程的上下文，并装入分派程序的上下文；2）移出分派程序的上下文，装入新选进程的CPU现场信息；

由于上下文切换会花去很多CPU时间，即使是现代计算机，一次上下文切换大约需要花费几毫秒的时间。为此，现在已有通过硬件（采用两组或更多的寄存器）的方式来减少上下文切换的时间。一组寄存器供处理机在系统态使用，另一组寄存器供应用程序使用。在这种条件下的上下文切换只需要改变指针，使其指向当前寄存器组即可。

进程调度方式

• 非抢占式：一旦处理机分配给某个进程后，不管它要运行多久，都一直让它运行下去，直至进程结束或主动释放处理机，或遇到阻塞，才将处理机分配给其他进程。
• 抢占方式：运行调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机分配给另外一个进程。

抢占式个原则有如下：

• 优先权原则，优先执行优先级比较高得作业
• 短作业有限原则，如果新作业比正在执行得作业明显短得时候，则暂停当前长作业，将处理机分配给新到的短作业
• 时间片原则。各进程按照时间片轮流运行，当一个时间片用完时，便停止该进程的执行而重新进行调度。

中级调度

由于内存有限，我们需要把那些暂时不能运行的进程调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程又重新具备运行条件且内存有空间的情况下，由中级调度来决定把外存上的那些就绪进程重新调入内存，并加入就绪队列等待调度。

通常低级调度运行频率最高，因此为了避免占用过多时间，应该采用简单的算法。而作业调度的周期较长，大约几分钟一次，故允许采用较复杂的算法。中程调度的频率居于其中。

调度队列模型

低级调度队列

常把就绪进程组织成FIFO队列形式，每当OS创建一个新进程，便把它挂在就绪队列的末尾，然后按照时间片轮转的方式运行。

低级+高级调度队列

在批处理系统中，不仅由进程调度，还有作业调度。

在批处理系统中最常使用最高优先权优先调度算法，而最常用额就绪队列形式是优先队列。

对于大型系统，如果只有一个阻塞队列，那么它的长度一定会很长，这将严重影响对阻塞队列的操作效率，因此应该按照阻塞事件设置多个阻塞队列。

低级+中级+高级

在引入中级调度后，可以把进程的就绪状态分为内存就绪和外存就绪，也可以把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。

对于如何选择调度方式和算法，应该基于下面的原则：

面向用户的准则

• 批处理系统的平均带权周转时间短：一个作业的周转时间是指从提交到完成所花费的时间，而带权周转时间是指周转时间和实际被调度的时间的比值
• 分时系统的响应时间快：响应时间是指从用户通过键盘提交一个请求开始，直到系统首次产生响应为止的时间。
• 实时系统的截至时间保证：截至时间是某项任务必须开始执行或完成的最迟时间。
• 优先权准则：无论什么系统，都可遵循优先权原则，以便让某些紧急的作业能得到及时处理。

面向系统的准则

• 系统吞吐量高：吞吐量是指单位时间内系统所完成的作业数
• 处理机利用率好
• 各类资源的平衡利用

选择作业（进程）算法

• 先来先服务算法（FCFS）：每次调度都从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，并为它们分配资源、创建进程，然后放入就绪队列。
  • 优点：利于长作业
  • 缺点：不利于短作业
• 短作业优先调度算法（SJ(P)F）：短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞时再重新调度。
  • 优点：利于短作业
  • 缺点：不利于长作业，并且作业的长短往往来自于估计值，并不准确。
• 高优先权优先调度算法（FPF）：当该算法调度作业时，系统从后备队列中选择若干个优先权最高的作业装入内存，当用于进程调度的则是将处理机分配给就绪队列中优先权最高的进程。
  • 非抢占式优先权算法：系统一旦将处理器分配给就绪队列中优先级最高的进程之后，该进程会一直执行下去，直至完成。除非发生阻塞或主动放弃处理机。
  • 抢占式优先权调度算法：系统把处理机分配给优先权最高的进程，使之执行。但是在执行期间，只要又出现了另外一个优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先级最高的进程。
• 高响应比优先调度算法：高响应比优先调度算法是通过高优先权优先调度算法+动态优先级实现的，一个作业的优先权=(已经等待时间+要求服务时间)/要求服务时间。因此在等待时间相同的情况下会优先调度短作业，但是一个长作业依旧可以通过长时间等待获得调度。

优先级既可以是静态的，也可以是动态的

• 静态优先级：在创建进程的时候确定优先级，并且之后不再改变。静态优先级的优点是简单，缺点是低优先级的作业可能一直无法得到调度。确定进程优先级的依据一般为
  • 进程类型，系统进程一般比用户进程更加优先
  • 进程对资源的需求，资源要求越少，优先级越高
  • 用户要求：根据用户进程的紧迫程度额付费来确定优先级
• 动态优先级：指在创建进程时所赋予的优先级，可以随进程的推进或等待时间增加而改变，以便获得更好的调度性能。一般在等待的时候以某个固定速率提高优先级，而在执行的时候以某个固定速率降低优先级。

基于时间片的轮转调度算法

时间片轮转法：每次调度将CPU分配给进程，并令其执行一个时间片。时间片的大小从几毫秒到几百毫秒，当执行的时间片用完时，由计时器发出时钟中断请求，调度程序根据此信号来停止该进程的执行，并把进程重新放回就绪队列。

选择较小的时间片有利于小作业，但是会导致频繁地发生中断和进程上下文切换，从而增加系统的开销。而采用较大的时间片，会使得每个进程都能在一个时间片内完成，时间片轮转算法变成FCFS算法，无法满足用户的交互需求。一个可取的大小是时间片略大于一次典型的交互所需的时间。

多级反馈队列调度算法

通过设置多个就绪队列，每个队列赋予不同的优先级。第一个队列优先级最高，第二个队列次之。优先权越高的队列中，分配的时间片就越小。

当一个新进程进入内存后，首先将它放在第一队列的末尾，按FCFS原则排队调度。当轮到该进程执行时，如果它能在该时间片内完成，则直接撤离系统，否则将它在时间片结束后放在第二队列的末尾。而对于最后的队列中的无法完成的任务，继续放在这个队列中。

仅当前面的所有队列都为空的时候，该队列中的任务才能被调度。

实时调度

为了保证系统能正常工作，实时调度必须满足实时任务对截止时间的要求。要实现实时调度，我们需要下述信息

• 就绪时间，任务称为就绪状态的起始时间
• 开始截止时间和完成截止时间

一个拥有N个处理机的机器，有m个周期性的硬实时任务，它们的处理时间可以表示为Ci，周期时间表示为Pi。则下面的条件必须满足

m∑i=1CiPi≤N

调度算法根据抢占方式可以分为

• 基于时钟中断的抢占式优先权调度算法：重新调度发生在时钟中断到来时，把处理机分配给新到的高优先权任务。
• 立即抢占的优先权调度算法：一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机重新分配给请求中断的紧迫任务

常用的几种实时调度算法

• 最早截止时间优先算法（EDF）：该算法根据任务的开始截止时间来确定任务的优先级，截止时间越早，优先级越高
• 最低松弛度优先算法（LLF）：松弛度表示作业完成截止时间减去它所需要的处理时间，即可以用来排队的时间。

资源按照是否可以剥夺可以分为

• 可剥夺性资源：一个进程在获得这类资源后，该资源可以被其他进程或系统剥夺。比如CPU和主存。
• 非剥夺性资源：一个进程在获得这类资源后，资源不能被强行回收。比如打印机。

资源按照是否可以重复使用分为

• 临时性资源：由一个进程产生后被另外一个进程使用短暂时间后便失去作用的资源，也称作消耗性资源。
• 永久性资源：资源可以顺序重复使用。如打印机。

产生死锁的必要条件

• 互斥条件：独占资源
• 请求和保持条件：同时持有资源并请求其它资源
• 不剥夺条件：自己持有的资源不会被剥夺
• 环路等待条件：请求构成环路

预防死锁的方式，只要破坏上面任一产生死锁的必要条件

• 摒弃请求和保持条件，所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。
• 摒弃不剥夺条件：当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。
• 摒弃环路等待条件：将所有资源按照类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须按照资源序号递增的次序提出。

系统安全状态

在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全的状态，则将资源分配给进程，否则令线程等待。

所谓安全状态，是指系统能按某种进程顺序(P1,…,Pn)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

只要系统处于安全状态，就可以避免进入死锁状态。

银行家算法

假设有M类资源，N个进程，第i个进程已经分配到的第j类资源的数量为Ai,j，第i个进程需要的第j类资源的上限数量为Li,j。第k类资源可分配数量为Rk。

银行家算法如下：

如果收到来自进程i的请求向量X，其中Xj表示需要j类资源的数目。

1. 如果Ai,j+Xj>Li,j，则认为出错，结束流程。否则进入步骤2。
2. 如果Xj>Rj，则资源不足，进程i需要等待。否则进入步骤3。
3. 系统试探着把资源分配给进程i，并执行安全性检测。如果系统依旧安全，则提交变更，否则回滚分配，并让进程i等待。

死锁的检测

可以构造一幅资源分配图，即如果资源i被进程j所持有，则从资源i到进程j连一条边。如果进程j请求资源i，则从进程j向资源i连一条边。

死锁定理指的是，存在死锁等价于资源分配图不可以被拓扑排序（即有环）。

死锁的解除

死锁的解除有两种方案

对于撤销进程，一般不需要撤销所有死锁的进程，而是选择一些进程进行撤销，目标是让撤销的进程的代价总和最小。

我们可以利用贪心算法，维护一个最小堆，找到从当前不安全状态到安全状态的最小代价。（每次从堆中找到代价最小的状态，通过撤销任一其中进程得到所有后续状态，并加入堆中）。

存储器管理

对于通用计算机，目前的存储层次为

• 可移动存储介质

其中必须的存储器为

• 主存：高速缓存，主存，磁盘缓存
• 辅存：磁盘，可移动存储介质

其中磁盘以上的部分处于操作系统存储管理的管辖范畴，掉电后它们存储的信息会丢失，而磁盘及其下面的层次则不会。

寄存器和主存储器又被称为可执行存储器，它的访问方式与辅存有很大区别，所需的时间也是不同的。对于可执行存储器中的内容可以直接通过机器指令进行访问，而对辅存的访问则需要通过I/O设备来实现。

主存储器的访问速度远低于CPU执行指令的速度，为了缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。寄存器的访问速度最快，能和CPU协调工作，但是价格昂贵，因此容量很小。寄存器的单位一般为字。

高速缓存的容量大于寄存器但是比内存小，访问速度也介于其间。

磁盘缓存也是用于缓解磁盘IO速度与主存访问速度之间的矛盾。

程序加载到内存的过程一般为

• 编译：将程序源码编译为若干目标模块
• 链接：将编译得到的目标模块和它们所需要的库函数链接在一起，形成转入模块
• 装入：将转入模块加载到内存

装入可以分为

• 绝对装入方式：如果在编译时知道程序将来被加载到内存中的位置，则可以使用绝对地址的目标代码。
• 可重定位装入方式：在编译时记录的是相对地址，在装入时根据内存分布将相对地址替换为绝对地址。在装入时对目标程序中的指令和数据的修改过程称为重定位，同时因为地址变换是一次性完成的，以后不再改变，故称为静态重定位。
• 动态运行时装入方式：类似于可重定位装入方式，但是并不立即将相对地址转换为绝对地址，而是把地址转换推迟到程序真正要执行到时才进行。

链接可以分为

• 静态链接：在程序运行之前，把各目标模块以及它们所需要的库函数，链接为一个完整的装配模块，之后不再拆开
• 装入时动态链接：再装入内存时，采用边装入边链接的链接方式
• 运行时动态链接：将对某些目标模块的链接，在程序执行中需要该模块时，才对它进行链接。

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

• 单一连续分配：只适合单用户、单任务的操作系统。把内存分为系统区和用户区两部分，系统区提供给OS使用，用户区则是系统区外的所有内存，留给用户使用。
• 固定分区分配：最简单的一种可以哦那个是运行多道程序的存储管理方式。将内存用户空间划分为若干个固定大小的区域，在每个分区中仅装入一道作业，这样最大作业数等于分区数。
  • 分区大小相等：容易造成浪费
  • 分区大小不等：可以按照需求进行分配
• 动态分区分配：为了实现分区分配，需要用数据结构来维护分区信息。 分区算法有如下
  • 首次适应算法（First Fit）：在所有可分配分区中，分配开始地址最小的分区。优点是可以为高地址保留大量内存，缺点是在低地址会留下很多难以利用的空闲空间碎片。
  • 循环首次适应算法（Next Fit）：每次都从上次分配的分区地址开始寻找，找到第一个能满足要求的空闲分区，并从中划出空间分配给作业。
  • 最佳适应算法（Best Fit）：每次都找满足要求但是最小的空闲分区分配给作业。缺点是会留下很多难以利用的空闲空间碎片。
  • 最坏适应算法（Worst Fit）：每次挑选一个最大空闲区分割给作业使用。优点是剩下的空闲区都相对较大，碎片少，并且查找效率高。缺点是会使存储器缺乏大的空闲分区。
  • 快速适应算法（Quick Fit）：按照空闲分区的容量进行分类，每一类的容量相同。对于其它大小的分区，可以放在特殊的空闲区链表中，每次挑选足够大但是最小的分区进行分配。优点是查找效率高，缺点是在分区归还主存时算法复杂，系统开销较大。

分区分配操作

系统利用某种分配算法，从空闲分区中找到所需大小的分区。设请求分区的大小为u.size，而分配的分区大小为m.size。如果m.size-u.size<=size，其中size是某个事先规定的常量，则说明多余部分太小，不必切割，而是把整个分区分配给请求者。否则从该分区中按请求的大小划分一块内存空间出去，余下的部分则插入到数据结构中。

回收内存

当进程运行完并释放内存时，系统将内存回收到数据结构中，如果前后有相邻的分区，则把这些分区合并为更大的分区。

伙伴系统

固定分区问题在于空间利用率低，动态分区算法则是分配和回收的过程复杂。

伙伴系统规定，无论已分配的或是空闲的分区，它们的大小都是2的幂次。其中21是最小分区的大小。我们将空闲分区按照分区的大小进行分类，对于每一类维护一个双向链表。

当需要分配长度为n的空间时，记i=⌈log2n⌉，根据下面逻辑进行

1. 如果大小为2i的分区链表非空，则弹出链表头返回。否则进入第2步。
2. 找到最小的j，满足j>i且大小为2j的分区链表非空。如果找不到，则内存不足，无法进行分配。否则进入第3步。
3. 弹出大小为2j的分区链表头部分区，并将其均分为两个大小为2j−1的新分区，这两个分区相互为伙伴关系。并回到第1步。

对于回收的逻辑，考虑回收一个大小为2i的分区，只需要把它插回到2i的分区链表中即可。之后如果在数据结构中存在一对伙伴，则合并伙伴为更大的空间，重复这个流程直到没有伙伴存在。

可重定位分区分配

如果可分配空间中有大量的内存碎片，它们的总大小可能很大，但是无法分配出一个中等大小的空间出去。

一种简单的消除内存碎片的方式是将内存中的所有作业进行移动，使它们全都相互邻接，这样原本的碎片会被合并为一个大的分区。由于移动后的程序在内存中的位置发生了变化，因此需要相应地对程序和数据的地址加以修改。

在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令真正要执行时才进行。为了使得地址的转换不会影响到指令的执行速度，必须有硬件地址变换机制的支持，需要在系统中增设一个重定位寄存器，用来存放程序在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而得到的。

而移动作业的时候，只需要修改作业的起始地址即可。

在多道程序环境下，一些占用大量内存的进程进入阻塞状态，会造成内存浪费。

为了解决这一问题，系统中还增设了对换设施，可以把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程需要的程序和数据调入内存。对换是提高内存利用率的有效措施。

如果对换是以进程为单位的，则称为进程对换或整体对换。如果对换是以页或段为单位进行的，则称为页面对换或分段对换，统称为部分对换。

在具有对换功能的OS中，通常用外存分为文件区和对换区。前者用于存放文件，后者用于存放内存换出的进程。一般文件区的目标是提高存储空间利用率，因此采用离散分配的方式；而对换区的目标是提高进程换入和换出的速度，因此采用的是连续分配方式。

对对换区的空间分配和回收算法，与动态分区分配算法是相同的。

每当一个进程由于创建子进程需要更多的内存空间时，但又无足够的内存空间等情况发生时，系统应该将某进程换出来释放内存。具体流程时：系统选择处于阻塞且优先级最低的进程作为换出进程，启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。若过程没有出错，则可以回收该进程所占用的内存空间。在进程换出后，系统应该定时地查看所有进程的状态，从中找出已换出的进程，将其中换出时间最久的进程作为换入进程，将之换入。

分页存储管理方式

可重定位分区分配需要移动作业，成本很高。如果允许一个进程使用多个不连续的分区，则可以避免移动。这种想法产生了离散分配方式，如果离散分配的基本单位时页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存储管理方式。

分页存储管理方式

将一个进程的逻辑地址空间划分为若干个大小相等的片，称为页面。同时把内存空间也划分成与页相同大小的若干个存储块，称为物理块。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。

页面的大小要适中，太大会降低内存利用率，太小会使得页表过大。

为了追踪页和块的对应关系，系统为每个进程建立了一张页表。页表中每一页都会设置存取控制字段，用于决定该页是否支持读写执行操作。

为了将用户地址空间中的逻辑地址转换为内存空间中的物理地址，需要在系统中设置地址变换机制。一般系统通过查询页表来进行转换。而页表一般存在于内存中，在系统中会设置一个页表寄存器PTR，在里面放置页表的地址和页表长度。

当进程需要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址分为页号和页内地址两部分，再以也好去检索页表。查找操作由硬件完成。如果页号非法，则产生地址越界中断。否则找到表项在页表中的位置，得到物理块号。之后将物理块好装入物理地址寄存器，同时将有效地址寄存器中的业内地址送入物理地址寄存器的块内地址字段中。

由于每次进程访问内存，都实际上会先访问内存中的页表，之后再访问物理块，需要执行两次内存访问，将计算机的处理速度降低了一半。为了提高地址变换速度，在地址变换机构中增加了一个具有并行查寻能力的特殊高速缓冲寄存器，称为快表，用来作为页表项的缓存。一般来说缓存的命中率达到90%，因此实际的额外内存访问次数仅为10%。

由于现代的计算机大多支持非常大的逻辑地址空间，在这种情况下，页表会变得非常大。一种可行的方案是采用多级页表。第一级页表项记录的是第二级页表地址，同理第二级页表项记录的是第三级页表的地址。在64位OS中，一般把可直接寻址的存储器空间减少为45位长度，考虑物理块大小为212，那么就可以用三级页表来实现分页存储管理。