操作系统

操作系统的概念、功能

操作系统的四个特征

操作系统的特征包含并发、共享、虚拟、异步

并发和并行
并发指两个或者多个时间在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。并行指两个获多个事件在同一时刻同时发生。
共享
共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用，分为 互斥共享方式和 同时共享堂方式
虚拟
虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体是实际存在的，而逻辑上对应物是用户感受到的。
虚拟技术包含空分复用技术（如虚拟存储技术）和时分复用（虚拟处理器）技术
异步
异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

操作系统的运行机制

两种指令

特权指令
指令影响重大，只允许操作系统的内核来使用
非特权指令
例如加法指令、减法指令等

两种运行状态

cpu有两种状态，内核态和用户态

内核态（管态）
CPU处于内核态时，说明此时运行的内核程序，此时可以执行特权指令
用户态（用户态）
CPU处于用户态的时候，说明此时运行的是应用程序，此时只能执行非特权指令。
程序状态寄存器
CPU中有一个寄存器叫程序状态寄存器（PSW），其中有个二进制位，1表示内核态，0表示用户态（也可以反过来）

内核态和用户态之间的切换

内核态和用户态之间是通过 “中断机制”来切换状态的。
内核态->用户态：执行一条特权指令–修改PSW的标志位位“用户态”，这个动作意味着操作系统将主动让出CPU使用权
用户态->内核态：由“中断”引发，硬件自动完成变态的过程，触发中断信号意味着操作系统将强行多为CPU的使用权

中断和异常

中断的类型

内中断（也称为异常）
与当前执行的指令有关，中断信号来源于CPU内部。CPU在执行执行时会检查是否有异常发生。
- 非法特权指令（终止 abort）。一个用户程序中插入了特权指令，当CPU拿到特权指令时，发现当前时用户态却想要执行一个特权指令，就会触发一个中断信号。CPU会拒绝执行这条特权指令并会变成内核态来处理这个中断。
- 非法非特权指令(终止 abort)。如果非特权指令中有非法的指令，也会触发中断，比如除数是0. 简单来说，若当前执行的指令是非法的，则会引发一个中断信号。
- 陷入(陷阱)指令（trap）（访管指令）。有时候应用程序像请求操作系统内核的服务，此时就会执行一条特殊的指令–陷入指令，该指令会引发一个内部中断信号。执行陷入指令，意味这应用程序主动地将CPU控制权还给操作系统内核，“系统调用”就是通过陷入指令完成的。
- 故障（fault）。由错误条件引起的，可能被内核程序修复。内核程序修复故障后会把CPU使用权还给应用程序，让它继续执行下去。如：缺页故障。
外中断（也成为中断，侠义的中断） 每个指令周期末尾，CPU都会检查是否有外中断信号需要处理。
与当前执行的指令无关，中断信号来源于CPU外部。
- 时钟中断–由始终不见发来的中断信号。
- I/0中断–由输入/输出设备发来的中断信号。

中断机制的基本原理

不同的中断信号，需要用不同的中断处理程序来处理。当CPU检测到中断信号后，会根据中断信号的类型去查询 中断向量表，以此来找到相应的中断处理程序在内存中的存放位置。

系统调用的过程

操作系统的体系结构

操作系统引导

虚拟机

进程

进程的概念

进程是动态的，是程序的一次执行过程，同一个程序多次执行会有对应多个进程。例如，登录3个QQ号。
为了区分和管理不用的进程，进程被创建时，操作系统会为该进程分配一个唯一的、不重复的身份证号–PID(Process ID, 进程ID)
此外，操作系统还会记录给进程分配了哪些资源，如分配了多少内存，正在使用哪些I/O设备；还会记录进程的运行情况，如CPU使用时间，磁盘使用情况、网络流量使用情况等等。
这些信息都被保存在一个数据结构PCB(Process Control Block)中，即进程控制块

进程的组成

进程的特征

动态性
进程时程序的一次执行过程，是动态的产生、变化喝消亡的
并发性
内存中多个进程实体，各进程可并发执行
独立性
进程是能独立运行、独立获得资源、独立接受调度的基本单位
异步性
各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题
结构性
每个进程都会配置一个PCB，结构上看，进程由程序段、数据段、PCB组成

进程的状态与转换

1. 创建态
进正在被创建时是创建太，在这个阶段操作系统会为进程分配资源、初始化PCB
2. 就绪态
当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行。
3. 运行态
当CPU空闲时，操作系统会选择一个就绪态的进程（可能会有多个就绪态的进程在等待被执行），让他上处理机运行。进程正在CPU上运行，那么这个进程处于“运行态”
4. 阻塞态（等待态）
在进程处于运行态时，可能会 请求等待某个事件的发生 （如等待某种系统资源的分配，或者等待其他进程的相应。）在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让他进入“阻塞态”。当CPU空闲时，又会选择另一个“就绪态”进程上CPU运行
当该事件发生了，或者资源可以被分配到刚到才进入阻塞态的进程了，操作系统就会让阻塞态的进程变成就绪态。
5. 终止态（结束态）
一个进程可以执行exit系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成后，该进程就彻底消失了。

进程的组织方式

链接方式
索引方式

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

进程通信

进程间通信是指两个进程之间产生数据交互。各进程拥有的内存地址空间相互独立，一般不可以相互访问。

进程通信的方式

共享存储
申请一个共享存储区，不同的进程可以访问共享存储区的数据。同时要注意解决冲突问题，例如写冲突可能会导数据覆盖问题。为保证安全，各个进程对共享空间的访问应该是 互斥的。这种基于存储区的共享是速度的。
还有一种共享方式是 基于数据结构的共享，共享空间里面只能放一个特定长度的数据结构，这种共享方式速度慢、限制多。
消息传递
进程间的数据交换以 **格式化的笑死(Message)**为单位。进程通过操作系统提供的 “发送消息、接收消息”两个原语进行数据交换。

格式化的消息包含 消息头和消息体。

消息传递有 直接通信和间接通信两种方式，直接通信消息发送进程要指明接受进程的 ID。间接通信时通过 **“信箱”**间接的通信。
- 直接通信
- 间接通信
管道通信
“管道”时一个特殊的共享文件，又名pipe文件。在内存中开辟一个大小固定的内存缓冲区。和共享存储的区别是共享存储区域内，数据的位置是不定的，接受消息的进程是可以随意选择要接受那个位置的数据。而管道通信是采用先入先出的机制。本质上是一个循环队列。

管道只能采用 半双工通信，某一时段内只能实现单向的传输。如果要实现 双向同时通信，则需要设置两个管道。各进程要互斥地访问管道。

线程

线程是CPU的调度的基本单位。线程的引入，增加了并发程度

线程的属性

TCB 线程控制块

引入线程后带来的改变：

进程是资源分配的基本单位，线程变为调度的基本单位
各线程间也能并发，提高了并发度
如果是同一进程内的进程切换，因为不需要切换进程环境，系统开销小
引入线程后，并发带来的系统开销减小

线程的实现方式

用户级线程
用户级线程是再用户级别实现逻辑上的多线程，在操作系统中，操作系统看到的仍是一个进程。这种实现方式是线程的切换是在用户态，开销小。缺点是当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个进程不可在多核处理及上运行
内核级线程
内核级线程的管理工作是由操作系统内核完成。内核级线程就是从操作系统内核视角能看到的线程。操作系统会为每个内核级线程建立TCB。优点是当一个线程被阻塞后，别的线程还可以继续执行。多线程可在多核处理及上并行执行。缺点是一个用户进程会占用多个内核级线程，线程切换需要变态，因此线程管理成本高，开销大。
多线程模型
多对多模型：n个用户级线程映射到m个内核级线程(n>=m)。每个用户进程对应m个内核级线程。克服了多对一模型并发度不高的缺点，又克服了一对一模型中开销太大的缺点。

调度

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。就需要确定 某种规则来决定处理这些任务的顺序，这就是调度。

调度的三个层次

高级调度（作业调度）
作业是指一个具体的任务。例如用户让操作系统启动一个程序。
按一定的原则从外存的作业后被队列中挑选一个作业调入内存，并创建进程。**每个作业只调入一次，调出一次。**作业调入时会建立PCB，调出时才撤销PCB。
低级调度（进程调度/处理机调度）
按照某种策略从就绪队列中选取一个进程，将处理机分配给它。进程调度频率很高。
中级调度
内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时在重新调入内存。暂停调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列。
中级调度（内存调度）就是按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出、调入内存。因此中级调度发生的频率比高级调度要高

进程调度的时机和方式

进程调度的时机

需要进行进程调度与切换的情况：

主动放弃处理机	被动放弃处理机
进程正常终止	分给进程的时间片用完
运行过程中发生异常而终止	有更紧急的事需要处理（如I/O中断）
进程主动请求阻塞（如等待I/0）	有更高优先级的进程进入就绪队列

有些时候是不能进行进程的调度与切换的：

处理中断的过程中
进程在操作系统内核程序临界区中
在原子操作的过程中

进程调度的方式
- 非抢占式。只允许进程主动放弃处理机。
- 抢占式。允许进程被动放弃处理机。

调度算法

调度算法的指标

调度算法

先来先服务（FCFS）

算法思想	算法规则	用于作业/进程调度	是否可抢占	优缺点	是否会导致饥饿
公平角度考虑	按照作业进程到达的先后顺序进行服务	用于作作业调度时，哪个作业先到达后被队列；用于进程调度，哪个进程先到达就绪队列	非抢占式	优点：公平、算法实现简单缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。对长作业有利，对短作业不利	不会

短作业优先（SJF）

算法思想	算法规则	用于作业/进程调度	是否可抢占	优缺点	是否会导致饥饿
追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间	最短的作业/进程优先得到服务（指要求服务时间最短）	都可以	非抢占式/也有抢占式版本-最短剩余时间优先算法	优点：“最短的”平均等待时间、平均周转时间缺点：不公平，对短作业有利，长作业不利。可能会出现饥饿现象。	会

高响应比优先（HRRN）

算法思想	算法规则	用于作业/进程调度	是否可抢占	优缺点	是否会导致饥饿
综合考虑作业/进程的等待时间和要求服务的时间	在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务响应比=等待时间+要求服务时间/要求服务时间	都可以	非抢占式	综合考虑了等待时间和运行时间 1.等待时间相同，要求服务时间短的优先 2.要求服务时间相同时，等待时间长的优先 3.可以避免长作业饥饿问题	不会

以上算法适合早期的批处理系统，交互性很糟糕，没有考虑任务的紧急程度等。

以下是实时操作系统常用的交互式调度算法

时间片轮转调度算法（RR）

算法思想	算法规则	用于作业/进程调度	是否可抢占	优缺点	是否会导致饥饿
公平地、轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到响应	按照个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理及，将进程重新放到就绪队列队尾重新排队	都可以	抢占式	优点：公平，响应快缺点：有一定的开销；不区分任务的紧急程度。	不会

优先级调度算法

算法思想	算法规则	用于作业/进程调度	是否可抢占	优缺点	是否会导致饥饿
应用场景需要根据人物的紧急程度来决定处理顺序	每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程	都可以，甚至还会用于I/O调度	抢占式、非抢占式都有	优点：可以灵活地调整对各种作业/进程的偏好程度缺点：如果一直有高优先级的，可能会导致低优先级饥饿	会

如何合理的设置各进程的优先级：

系统进程 > 用户进程
前台进程 > 后台进程
偏好 I/O 型进程

多级反馈队列调度算法

算法思想	算法规则	用于作业/进程调度	是否可抢占	优缺点	是否会导致饥饿
对以上算法的折中权衡	1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大 2.新进程到达时先进入第1级队列，按FCFS原则排毒等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾 3. 只有第k级为空时，才会为k+1级队友的进程分配时间片	用于进程调度	抢占式	优点：集合前面调度算法的有点，避免缺点缺点：可能会导致饥饿	会

进程同步与进程互斥

进程互斥的软件实现方法

单标志法
算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予，违反空闲让进原则
双标志先检查
算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如 “flag[0] = ture” 意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设置为true，之后开始访问临界区。违反忙则等待原则
双标志后检查
算法思想：双标志先检查法的改版。前一个算法的问题是先“检查” 后 “上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，利用先“上锁” 后 “检查”的方法，来避免上述问题。违反了“空闲让进”和“有限等待”的原则，因各进程都长期无法访问临界资源而产生“饥饿”的现象
Peterson算法
结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试谦让。没有遵循让权等待原则。

进程互斥的硬件实现方法

中断屏蔽法
利用“开/关中断指令”实现，在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况。
优点：简单、高效
缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态）
TestAndSet(TS指令/TSL指令)
Swap指令（XCHG指令）

互斥锁

一个进程再进入临界区时应获得锁，再退出临界区时释放锁。每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁时可用的，调用acquire()函数会成功，且锁不可再用。当一个金策韩国你试图获取不可用的锁时，会被阻塞，直到锁被释放。

互斥锁的主要缺点是忙等待，当有一个进程再临界区时，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以再一个处理器上等待，不影响其他线程的执行。
需要连续循环忙等待的互斥锁，都可以成为自旋锁。

信号量机制

用户进程可以通过使用操作系统提供的 一对原语 来对 信号量进行操作，从而很方便的实现了进程互斥和进程同步。

信号量其实就是一个变量，可以用一个信号量来 表示系统中某种资源的数量

一对原语： wait(S)原语和signal(s)原语。
wait、signal原语常简称为P、V操作。

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
存在忙等问题。

记录型信号量

信号量机制实现进程互斥、进程同步

实现进程互斥
对不同的临界资源需要设置不同的互斥信号量
- 分析并发进程的关键果冻，划定临界区
- 设置互斥信号量mutex（表示进入临界区的名额），初始值为1
- 在进入去P(mutex)——申请资源
- 在退出区V(mutex)——释放资源

实现进程同步
- 分析什么地方需要实现“同步关系”，及必须保证有顺序的执行
- 设置同步信号量S，初试为0
- 在“前操作”之后执行V(S)
- 在“后操作”之前执行P(S)

生产者-消费者问题

实现互斥的P操作一定要在实现同步的P操作之后。 V操作的顺序可以交换

管程

为什么要引入管程
信号量机制存在问题，编写程序困难、易出错。为了让程序员在写程序时不需要在关注复杂的PV操作，引入管程。管程就是一种高级同步机制。
定义和基本特征
管程是一种特殊的软件模块，由这些部分组成：
- 局部于管程的共享数据结构说明
- 对该数据进行操作的一组过程（函数）
- 对局部与管程的共享数据设置初始值的语句
- 管程有一个名字
  管程的基本特征：
- 局部与管程的数据只能被局部于管程的过程所访问
- 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程

死锁

什么是死锁
各进程相互等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
死锁产生的必要条件
- 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的。
- 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
- 请求和保持的条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
- 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
什么时候会发生死锁
- 对系统资源的竞争。个金策韩国你对不可剥夺的资源的竞争可能引起死锁
- 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。
- 信号量的使用不当也会造成死锁。

死锁的处理策略

预防死锁

破坏互斥条件
把只能互斥使用的资源改造为允许共享使用。但并不是所有的资源都可以被改造成共享资源。
破坏不剥夺条件
破坏请求和保持条件
破坏循环等待条件

避免死锁

安全序列
安全序列是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。安全序列可能有多个。
如果分配资源后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态。

安全状态一定不会死锁，不安全状态可能发生死锁。
因此可以在分配资源之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。
银行家算法

死锁的检测和解除

死锁的检测

用某种数据结构来保存资源的请求和分配信息
如果能消除所有的边，就是可简化的，不会发生死；如果不能消除所有边，那么此时就是发生了死锁

死锁的解除

内存

什么是内存
内存用来存放数据。缓和CPU与硬盘之间的速度矛盾。内存中按地址分成了一个一个的存储单元。
内存的逻辑地址和物理地址
逻辑地址即相对地址，假设我们一个程序编译后的指令装入内存的时候是连续的。如果我们的指令0想把x变量的值“10”存入内存的79地址，用逻辑地址的话，假如我们的指令0的的地址是100，那么10应该存放在地址179，而不是地址79。
而物理地址就是以内存的地址0为起始地址的绝对地址。
如何将指令中的逻辑地址转换为物理地址
- 绝对装入
  在编译时，如果知道程序将存放到内存中的那个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。例如，如果知道装入模块要从地址为100的地方开始存放，写入10的地址时79，那么我们就直接可以把79改成179。但是绝对装入只适用于单道程序环境，灵活性很差。
- 可重定位装入（静态重定位）
  编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。在装入时对地址进行“重定位”，将逻辑地址转变为物理地址（地址变换实在装入时一次完成的）。这要求一个作业装入内存时，必须为其分配要求的全部连续内存空间，如果没有足够的内昆，就不能装入作业。作业一旦装入后，在运行期间就不能再引动，也不能再申请内存空间。
- 动态运行时装入（动态重定位）
  编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟道程序真正要执行时才进行。因此装入内存后所有的地址依然时逻辑地址。这种方式需要一个重定位寄存器的支持。重定位寄存器存放装入模块存放的起始位置。

内存管理

内存空间的分配与回收
内存空间的扩充（实现虚拟性）
地址转换
存储保护
保证各进程在自己的内存空间内运行，不会越界访问
两种方式：
- 设置上下限寄存器
- 利用重定位寄存器、界地址寄存器进行判断

覆盖技术

覆盖技术的思想：将程序分为多个段（多个模块）。常用段常驻内存，不常用的段在需要时调入内存。
内存中分为一个“固定区”和若干个“覆盖区”

固定区放常驻段，调入后就不再调出，除非运行结束
不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存
这种技术的缺点是必须由程序员声明覆盖结构，对用户不透明，增加了用户编程负担。

交换技术

设计思想：内存空间紧张时，系统将内存中某些进程暂时患处外存，把外存中某些已经具备运行条件的进程换入内存。

连续分配管理方式

连续分配：为用户进程分配一个连续的内存空间
内部碎片：分配给某进程的内存区域中，有些部分没有用上。例如分配了20MB,单进程只用了19MB。就有1MB的内部碎片。
外部碎片：是指内存中的某些空闲分区由于太小而难以利用。

单一连续分配
- 在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据。用户区用于存放用户进程相关数据。
- 内存中只能有一道用户程序，用户程序独占整个用户空间。
固定分区分配
- 将整个用户空间划分为若干个固定大小的分区，在每个分区之只装入一道作业。
- 分为分区大小相等（适用于用一台计算机控制多个相同对象的场合）和分区大小不相等（增加了灵活性）两种
- 使用分区说明表来实现分区的分配与挥手。每个表象包括对应分区的 大小、起始地址、状态（是否已分配）
动态分区分配
- 又称为可变分区分配。根据进程的大小动态地建立分区，并使分区地大小正好适合进程的需要。动态分区没有内部碎片，但是有外部碎片。
- 使用 空闲分区表 或 空闲分区链 数据结构记录内存使用情况
- 当一个作业装入内存时，按照动态分区分配算法进行装入。
- 如果使用空间分区表，装入一个作业后，要修改表项的分区大小、起始地址。如果某个作业、进程刚好占用一个分区，则把这个分区表象从表中删除。如果一个进程结束了，退出内存，则把它占用的内存空间加入内存表，如果分区前后有相邻的分区，则合并他们。

动态分配算法

首次适应法
- 思想：每次都从低地址开始查找，找到第一个满足大小的空闲分区
- 实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链或空闲分区表，找到大小能满足要求的第一个空闲分区。
最佳适应法
- 思想：尽可能留下大片的空闲区，优先使用更小的空闲区
- 实现：空闲分区按照 容量递增次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。每次分配后，要重新排列空闲分区链表或者空闲分区表，保证是按 容量递增次序排列的。
- 缺点：会产生很多外部碎片，开销大，因为需要对数据结构进行重新排序
最坏适应法
- 思想：与最佳适应法相反，在每次分配时优先使用最大的连续空闲区。
- 实现：和最佳适应法一样，只是空闲分区是按照 容量递减次序链接的
邻近适应法
- 思想：基础思想和首次适应算法一样，但首次适应算法会导致低地址产生很多小的空闲分区，而每次分配查找时，都要经过这些分区，增加了查找的开销。邻近适应算法是从上次查找结束的位置开始检索，增加了效率，减少了开销。
- 实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时 从上次查找结束的位置开始查找空闲分区链或空闲分区表，找到大小能满足要求的一个空闲分区。