操作系统典型算法

一. 进程

1. 作业/ 进程调度算法 （重点是CPU 的调度）

作业调度 和 进程调度 实际上并不完全一样，但是下文重点记录算法，对此两概念不做明确区分

相关概念: CPU利用率/ 系统吞入量/ 周转时间/ 等待时间/ 响应时间

• CPU 利用率
  CPU 利用率 = CPU 有效时间 / (CPU 有效工作时间 + CPU 空闲等待时间)

• 系统吞吐量
  单位时间内系统所完成的作业数

• 周转时间
  从作业被提交给系统开始，到作业完成为止的这段时间间隔

• 等待时间
  进程处于等待处理机状态的时间之和

• 响应时间
  从用户提交请求到系统首次产生响应所用的时间

1. 先来先服务(FCFS)

该算法既适用于作业调度、又适用于进程调度。顾名思义，在该算法中，使用一个“队列”来辅助调度，先进入队列者先行获得自愿并执行，直到阻塞或运行结束才“让位”。 该进程对“长作业”有利而对“短作业”不利；对CPU 繁忙型作业有利而对IO 密集型作业不利。

2. 短作业优先 (Short Job First)

顾名思义，短作业优先算法优先执行短作业，也因此会使得长作业经常得不到执行，即所谓的“饥饿”现象。另外，该算法未考虑作业紧迫程度，并且对于作业的长短也仅是一个模糊的说法（由用户指定，并非实际的长短） SJF调度算法的平均等待时间、平均周转周期时间最少

3. 高响应比

给出响应比的定义公式：响应比 = (等待时间 + 要求服务时间 ) / 要求服务时间
该算法充分考虑到了“短作业优先”和“长作业饥饿”的问题：

1. 作业等待时间相同时，要求服务时间越短响应比越高，越优先调度，是 SJF
2. 要求服务时间相同时，等待时间越长响应比越高，越优先调度，是 FCFS
3. 对于长作业，虽然由于“要求服务时间”长的缘故会降低优先级，但是随着等待时间的延长，调度优先级也会提高，因此解决了“饥饿”现象。

4. 时间片轮转

主要适用于分时系统，系统维护一个“队列”，按照FCFS 的原则从队列中取出一个进程并执行，但是仅能执行一个固定的时间片，一旦时间片用完便强制回收资源并将其放回队列尾。
在该算法中，时间片的选择对算法效率影响很大：过短则系统开销过多的浪费在进程切换上；过长则沦为FCFS算法。
因此，时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力

5. 优先级

该算法即可用于作业调度、又可用于进程调度。顾名思义，系统会维护一个优先级最大堆，每次都从堆的顶部取作业或取进程用于执行。
另外，优先级调度也分多种实现：

1. 非剥夺式优先级调度
2. 剥夺式优先级调度
3. 静态优先级
4. 动态优先级

对于优先级的划分，通常有：

1. 系统进程 > 用户进程
2. 交互型进程（前台）> 非交互型进程( 后台)
3. IO 型进程 > 计算型进程

6. 多级反馈队列

多级反馈队列算法是时间片轮转调度算法和优先级调度算法的综合与发展。
在该算法中，系统划分多个优先级不同的队列，优先级越高的队列其对应时间片越短。

对于一个进程的调度原则为：初始时，一个新进程会进入到优先级最高的队列尾，若它能在这一级对应的时间片内结束任务，则完成；否则将会被剥夺并放入次一级的队列中，依次类推，直到其能完成任务。

另外，对于级间的调度原则，完全按照优先级调度，即只当高一级队列为空时才调度低一级队列；若有新任务加入高一级队列则剥夺当前低优先级任务的资源，转而执行高优先级任务。

这种算法的具有很多优势，例如：可以兼顾多种系统目标、也可以不事先估计进程的执行时间。

2. 临界区互斥的实现方法

原则: 空闲让进, 忙则等待, 有限等待, 让权等待

比较原始的几种软件实现算法参见这篇博文

硬件实现参考这篇博文

1. 单标记法

该算法设置一个公用整数变量 turn ，用于指示被允许进入临界区的进程编号。该算法只确保每次只允许一个进程进入临界区，但两个进程必须交替进入临界区。 PS：这个算法极其傻逼，让人完全不知道是为何存在 附代码：

// Process 0
while(turn != 0);
// critical section;
turn = 1;
// remainder section;

// Process 1
while(turn != 1);
// critical section;
turn = 0;
// remainder section;

2. 双标记先检查法

该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。为此，设置了一个数据flag[i]，如第i个元素值为FALSE，表示Pi进程未进入临界区，值为TRUE，表示Pi进程进入临界区。

// Pi 进程
while(flag[j]); // ①
flag[i]=TRUE; // ③
critical section;
flag[i] = FALSE;
remainder section;
// Pj 进程
while(flag[i]); // ② 进入区
flag[j] =TRUE; // ④ 进入区
critical section; // 临界区
flag[j] = FALSE; // 退出区
remainder section; // 剩余区

优点：不用交替进入，可连续使用；缺点：Pi 和 Pj 可能同时进入临界区。按序列①②③④ 执行时，会同时进入临界区（违背“忙则等待”)。即在检查对方flag之后和切换自己flag之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。

3. 双标记后检查法

算法二是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。为此，算法三釆用先设置自己标志为TRUE后，再检测对方状态标志，若对方标志为TURE，则进程等待；否则进入临界区。

// Pi进程
flag[i] =TRUE;
while(flag[j]);
critical section;
flag[i] =FLASE;
remainder section;
// Pj进程
flag[j] =TRUE; // 进入区
while(flag[i]); // 进入区
critical section; // 临界区
flag [j] =FLASE; // 退出区
remainder section; // 剩余区

当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象

4 Peterson's Algorithm

为了防止两个进程为进入临界区而无限期等待，又设置变量turn，指示不允许进入临界区的进程编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入。这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区，只允许一个进程进入临界区。

// Pi进程
flag[i]=TURE; turn=j;
while(flag[j]&&turn==j);
critical section;
flag[i]=FLASE;
remainder section;
// Pj进程
flag[j] =TRUE;turn=i; // 进入区
while(flag[i]&&turn==i); // 进入区
critical section; // 临界区
flag[j]=FLASE; // 退出区
remainder section; // 剩余区

本算法的基本思想是算法一和算法三的结合。利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象。

5. 中断屏蔽法 (硬件实现)

当一个进程正在使用处理机执行它的临界区代码时，禁止一切中断发生（关中断），在执行完后再开中断。 缺点：效率低，若一个进程关中断后不再开中断，则系统可能因此终止。

6. 原子操作(TestAndSet/ Swap) 指令 (硬件实现)

这些原子指令是由硬件提供的, 并非操作系统内部的"原语". 参考Wikipedia

TestAndSet 指令(tsl) 的功能是 "检查并设置" , 具体而言就是"TSL對某個記憶體位置寫入1(set) 並返回其舊值(旧值). ", 由计算机硬件保证这条指令在执行时不会被打断. 可以看出, 这条指令可以用来实现"互斥锁".

Swap 指令用于交换两个字的内容 , 也可用来实现互斥锁.

考察下述汇编码:

enter_region:        ; A "jump to" tag; function entry point.

  tsl reg, flag      ; Test and Set Lock; flag is the
                     ; shared variable; it is copied
                     ; into the register reg and flag
                     ; then atomically set to 1.

  cmp reg, #0        ; Was flag zero on entry_region?

  jnz enter_region   ; Jump to enter_region if
                     ; reg is non-zero; i.e.,
                     ; flag was non-zero on entry.

  ret                ; 在这里返回到调用程序中(进入临界区)
                     ; Exit; i.e., flag was zero on
                     ; entry. If we get here, tsl
                     ; will have set it non-zero; thus,
                     ; we have claimed the resource
                     ; associated with flag.

leave_region:        ; 这里是"离开临界区"函数, 并非上一个函数的"延续"
  move flag, #0      ; store 0 in flag
  ret                ; return to caller

从上述汇编码中可以看出, tsl 指令实际上有两个步骤:

1. 将变量值保存到寄存器
2. 将变量值"置1", 此时该变量值可能和上述寄存器中的值不一样.

而我们可见的 C函数 test_and_set 返回的是上述"寄存器"的值.

由上述汇编码 tsl 指令实现互斥锁 的过程可以看出, tsl 指令有一个"交换"的过程, 因此也可以使用 swap 指令来实现"互斥锁".

swap 指令实现的"互斥锁" 可以参考此博客

可以看出, swap 指令将"两个变量的值互换" (tsl 指令将某个变量的值和某个特定的寄存器互换), 因此可以利用一个变量 key 和一个变量 lock 来实现互斥锁.

7. 信号量 (號誌: (台语))

信号量可以看成是一个"互斥锁的增强版本". 信号量自身具有原子操作的特性, 同时信号量机制提供了一个 队列 用于实现进程休眠与唤醒.

在这篇博客²中讲了"整型信号量"和"记录型信号量"的区别, 百度百科里也有提到三类信号量 . 可以看出 并不是所有的信号量 都会维护一个 等待队列. 在博客 ² 中有如下表述:

在整型信号量中，只要S <= 0，就会不断测试，看何时有资源可用。也因此，进程会一直等，不遵循让权等待的原则。

更好的做法是，像我们在进程调度中学到的，加一个就绪队列。也即，引入：记录型信号量。

记录型信号量 我们常说这个算法是一种进程同步机制，而不说是互斥机制。 是因为，使用PV的思路进行进程的互斥访问，非常简单，只需要设置一个mutex,取值仅仅为0或者1即可。而同步的话就复杂一些，采用用到这个记录型信号量。

链表L表示的是就绪队列，因此核心仍是PV，只不过如何对待进程，记录型信号量的做法更加完善。解决了让进程忙等的现象。

可以比较充分的说明了 队列 在 信号量 机制中起到的作用, 有了队列, 信号量机制便可以实现"让权等待"的效果.

3. 死锁避免算法

死锁避免算法主要记录"银行家算法", 见下文

二. 内存

1. 连续内存管理方案

1. 动态分区分配方案中的分配算法

引用内容来自此博文

动态分区分配是根据进程的实际需要，动态的为之分配内存的空间。总体是按照算法规则找到分配的空闲分区，然后从该分区中再按照作业的大小划出一块内存空间分给作业，该分区余下的空闲分区当做一个新的空闲分区留在空闲链中。

在这里提到的 动态分区方案 是一种 将内存等分的划分为多个区域 的内存利用方案. 也因此, 在分配内存时, 应当找出一个合适的分区用于此次分配.

1. 首次适应算法 (First Fit)

首次适应算法，要求空闲分区链以地址递增的次序链接，在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止，然后再按照作业的大小，从该分区中划出一块内存空间分给请求者，余下的空闲分区仍停留在空闲链中。

2. 最佳适应算法(实际上效果最差) (Best Fit)

为了加速查找，该算法需要将所有的空闲区按其大小从小到大进行排序后，当有作业要分配的时候，查找满足其内存需求，同时又是最小的空闲块，然后分配给作业。

但是, 因为每次都是找到"最合适"的, 也就意味这每次分配后该分区剩余的内存空间也是"最小"的, 这样便会产生"最碎"的内存碎片. 所以效果并不是很好.

3. 最坏适应算法 (Worst Fit)

最差适应算法中，该算法需要将所有的空闲区按其大小从大到小进行排序，分配时直接从空闲区链的第一个空闲分区中分配（不能满足需要则不分配）。非常显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。

这种分配方法初看起来不太合理，但他也有非常强的直观吸引力：在大空闲区中放入程式后，剩下的空闲区常常也非常大，于是还能装下一个较大的新程式。

4. 临近适应算法

从上一次分配的地址开始查找符合要求的块，所查找到的第一个满足要求的空闲块就分配给进程。

2. 非连续内存管理方案 (页式内存管理方式)

虚拟内存的置换算法(任意相邻高级和低级存储设备之间都可能适用)

1. 最佳置换(OPT)

2. 先进先出(FIFO)

3. 最近最久未使用(LRU)

   1. 寄存器实现

   2. 栈实现

4. 时钟(CLOCK) (实际是LRU算法的一种高效改进型实现)

5. 二次机会法

6. 最少使用(LFU)

三. I/O

1. 分配算法(避免死锁)

死锁产生的条件?

1. 互斥条件
2. 不剥夺条件
3. 请求并保持条件
4. 循环等待条件

解决死锁有哪几个方面?

1. 死锁预防
   通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或多个，以防止死锁的发生

2. 避免死锁
   在资源动态分配时，通过某些方法防止系统进入不安全状态。

3. 死锁的检测及清除
   系统具有专门的检测措施来检测死锁，通过剥夺接触死锁。

常用算法：
一、分配时检查(系统安全状态)
在分配资源前，系统首先计算该资源分配的安全性，若安全则将资源分配给进程；否则让进程等待。 所谓安全状态，是指系统能按某种进程推进顺序为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。
说人话就是系统预先为某个资源计算分配顺序，按照这个顺序将该资源先后分配给各进程将不会造成死锁。

银行家算法

银行家算法是最著名的死锁避免算法。算法思想是：当进程首次申请资源时，要测试该进程对资源的最大需求量，若系统现存的资源可以满足它的最大需求量则按照当前申请量分配资源；否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程已占用资源数与本次申请的资源数之和是否超过该进程对资源的最大需求量，若超过则拒绝分配资源，若未超过则在测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则推迟分配。

算法实现

1) 用到的数据结构

• 可用资源矩阵 Avaliable
  该数组的每一个元素表示对应的资源可用数
• 最大需求矩阵 Max
  定义系统中 n 个进程中的每一个进程对 m 类资源的最大需求。简单来说，一行代表一个进程，一列代表一类资源。
• 分配矩阵 Allocation
  定义系统中每类资源当前已分配给每个进程的资源数，同上述一致，一行代表一个进程、一列代表一类资源
• 需求矩阵 Need
  表示每个进程尚需的各类资源数，同上述一致，一行代表一个进程、一列代表一类资源

上述三个矩阵间具有如下关系

• 进程请求矩阵 Request
  定义进程此次请求的资源情况，每一个元素代表对某一类资源的请求数。

2) 算法明细

进程发出请求 Request

1. 若 Request_i[j] \leq Need[i, j] ，则继续；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值
2. 若 Request_i[j] \leq Available[j] ，则继续；否则表示尚无足够资源，进程需等待
3. 此时假设可将资源分配给该进程，同时执行下述计算：

4. 执行安全性检查程序，检查此次资源分配后是否处于安全状态，若安全正式分配资源；否则，进程等待

安全性检查子算法来源于此博文

安全性检查算法: 通过找一个安全序列，判断系统目前是否安全：

1. 另设置两个矩阵，并给它们赋初值：

   • 工作矩阵 Work
     它是一个含有 m 个分量的一维数组，它表示系统目前可提供给进程继续运行使用的各类资源(空闲的)数目， 在开始执行安全性检查算法时，赋初值 Work = Available
   • 完成向量 Finish
     它是一个含有 n 个分量的一维逻辑型数组，它表示系统目前是否有足够的资源分配给系统目前的 n 个进程，使之运行直到完成。 当系统目前有足够资源分配给进程 i 时， 令 Finish_i = 1；算法开始时先给 Finish 赋初值，For\ one\ process\ i, Finish[i] = 0

2. 从进程集合中找一个同时能满足下述两条件的进程 i

   1. Finish[i] = 0
   2. Need[i, j] ≤ Work[j] 若能找到，执行步骤(3)；否则，执行步骤(4)；
3. 由于当进程 i 获得资源后，可顺利执行，直至完成；完成后可释放出分配给它的资源，故可以执行运算：

再次回到步骤 2

4. 若对于所有的进程, 都有 Finish[i] = true ，进入了进程推进序列，这个序列就是安全序列，这表示系统目前处于安全状态；否则， 说明有若干个进程无法进入推进序列， 系统处于不安全状态。 (经过逐一计算后，如果是由于不满足步骤 2 的条件①而结束循环，则找到了一个安全序列；如果是由于不满足步骤 2 的条件②而结束循环，则没有找到安全序列；

以下是本文 安全检查算法 的原文:

1. 初始时安全序列为空

2. 从 Need 矩阵中找出符合下面条件的行：

   1. 该行对应的进程不在安全序列中;

   2. 这行小于等于 Available 矩阵

   若找到则将进程号加入安全序列；否则执行(4)

3. 假设此时进程执行完毕，其将释放自身持有的资源，因此执行运算： Available = Available + Allocation[i] ，返回 (2) 继续测试 (此处应当是存在这么一种关系: Allocationn[i] = Max[i] )

4. 若此时安全序列中已有所有进程，则系统处于安全状态；否则系统处于不安全状态。

下述例题来源

考虑这样一个系统，有5个进程 P0~P4，3种资源类型A、B、C。资源类型A有10个实例，资源类型B有5个实例，资源类型C有7个实例。假定在时刻T0，系统状态如下：

即

矩阵 Need 的内容定义成 Max - Allocation：

可认为系统现在处于安全状态，因为存在一个安全序列 [P1,P3,P4,P2,P0] 。

现在假定进程 P1 再请求1个 A 类资源和两个 C 类资源，这样 Request_1 = [1,0,2]。为了确定这个请求是否可以立即允许，首先检测 Request_1 <= Available\ (i.e. [1,0,2] \le [3,3,2]) ，其值为真。接着假定这个请求被满足，会产生如下新状态：

必须确定这个状态是否安全。为此，执行安全算法，并找到顺序满足安全要求。因此，可以立即允许进程P1的这个请求。

然而，可以发现当系统处于这一状态时，是不能允许 P4 的请求 [3, 3, 0] 的，因为没有那么多资源可用。也不能允许 P0 的请求 [0, 2, 0]；虽然有资源可用，但是这会导致系统处于不安全状态。

二、死锁检测方法

资源分配图

如果一个图中没有环路（也称回路），则系统中不存在死锁；若有环路，系统*可能*存在死锁。即可说，环路是死锁的必要条件，但不是充分条件。

使用资源分配图可以来判定是否出现死锁现象：

方法步骤

1. 先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞（“不阻塞”即：系统有足够的空闲资源分配给它）的
2. 把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来
3. 看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。
4. 最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。 如果一个图可完全简化，则不会产生死锁；如果一个图不可完全简化（即：图中还有“边”存在），则会产生死锁。这就是“死锁定理”。

资源分配图的实例来自于此