组成结构与操作系统

最近在进行计算机组成结构与操作系统的回顾，部分知识点纪录在此。

位级表示

原码 反码 补码

无符号数就是纯二进制表示，而有符号数有多种表示方法：原码、反码和补码，现大多使用补码。正是因为有符号数有多种表示方法，C++中如果对一个有符号数赋予超出表示范围的值，其结果是未定义的，因为不知道如何解释这个值。

原码和反码都是需要考虑符号的，而且0有正0和负0之分，因此不方便计算也不统一。反码英文是one’s complement，即1的补码，也就是取反，而补码的英文是two’s complement，但不是2的补码，而是2^w^的补码，其中w是该数二进制表示的位数，也就是说一个负数-x，它的补码表示是2^w^ - x，计算方法简记为取反加一。以-1的补码为例，也就是求正数1对2^w^的补码：

  1 0 0 0 0
-   0 0 0 1
-------------
  0 1 1 1 1

而取反加一也刚好是这个结果，所以一般教的计算方法都是取反加一。

二进制与十进制的转换

  1. 正整数转二进制：

    除二取余，倒序排列

  2. 小数转二进制

    对小数点后的数乘以2，取结果的整数部分，以此类推，直到小数部分为0或精度足够

  3. 二进制转十进制

    位上的值与对应权值（基数为2）相乘并累加

强制类型转换

浮点数与整数直接类型转换

旧C++、C语言中：(type)val

现代C++中：static_cast\(val)

（以下知识在深入理解计算机系统中有涉及）

整数存储在通用寄存器中，浮点数存储在xmm寄存器（是ymm寄存器的低16字节）中。它们之间的强制类型转换有对应的机器指令。

浮点数转成整数是直接截断，向0舍入；而整数转成浮点数便是根据IEEE的浮点数位表示标准进行转换。

用指针进行类型转换

旧C++、C语言中：(type*)&val

现代C++中：reinterpret_cast\(&val)

不是直接对值的类型转换，那样也许会改变底层的位表示。而是不改变底层的位表示，而是用另一种类型的方法去解释底层的位表示：例子

进程与线程

进程

在进程模型中，计算机上所有可运行的软件，包括操作系统，都称为进程。

进程是一个正在执行的程序的实例，包括程序计数器、寄存器等程序运行需要的资源。

进程与程序的关系

具体区别 :

程序是一堆代码和数据，可作为目标文件存在磁盘中，也可以作为段存在于地址空间中；而进程是执行中的程序的一个实例，它包含着一个程序运行所需要的一切资源（即程序运行在进程的上下文中）。

例子：

我正在根据参考答案用红笔修改做过的作业，这里参考答案就是程序，红笔和我做过的作业就是相关的资源，我就是CPU，那么进程就是我阅读参考答案，比照我写的答案，用红笔进行修改的这一系列动作的总和。

而如果现在面试官打电话叫我面试，那我就记录下我改到的位置（保存进程当前状态），然后接电话根据我以前学习的知识回答面试官的问题。这里处理机就是从一个进程切换到了一个高优先级的进程，每个进程都拥有各自的程序（参考答案和我学习过的知识）。面试完后，我又回来继续改作业，从刚才改到的位置继续下去。

值得注意的是：一个程序运行两遍，算作两个进程。比如我们可以运行两次自己写的代码，其中用getpid获得当前进程的pid，我们会发现每次运行输出的pid不同。

进程的创建

unix系统中只有一个系统调用可以用来创建新进程：fork，创建出来的子进程通常还会接着执行execve来修改其内存映像并运行一个新程序。之所以要安排两步来建立进程，是为了在fork之后但在execve之前允许该子进程修改其文件描述符，这样可以完成输入输出的重定向。

具体原因其实还是历史遗留，当时fork和execve刚设计时还没有进程和线程的概念，execve就是会直接把shell的内存修改以执行新的程序，但这样要每次重新加载shell，于是fork就出现了，复制一份shell的内存映像、文件描述符等，用execve执行新任务而对shell本身没有影响。[1]

如：

ps aux > 1.txt

shell会先fork出一个自身的进程，然后将文件描述符1从标准输出改为输出到1.txt，再使用execve执行ps这个命令，ps直接输出即可，结果就是输出到1.txt中了。

进程的层次结构

在unix中，进程和他的所有子进程以及后裔共同组成一个进程组。

init进程会出现在启动映像中，当它开始运行时，读入一个说明终端数量的文件，接着为每个终端创建一个新的进程。这些进城等待用户登录，登录成功后，登录进程就会执行shell准备接受命令，接受的这些命令又会启动更多的进程。这样，所有进程都属于以init为根的一棵进程树。

进程的状态

进程有三个状态：

  1. 运行态（占用cpu）
  2. 就绪态（可运行，但是由于其他进程占用cpu而暂时停止）
  3. 阻塞态（不能运行，等待某些事件发生才可运行，如等待用户输入）

unix中当一个进程从管道或其他设备读取数据时，如果暂时没有有效的输入，进程会被自动阻塞（为什么会暂时没有有效输入？这是由命令的执行时间以及分配到的cpu时间决定的）。

进程的实现

操作系统维护一个表格，即进程表，每个进程占据一个表项（有些地方称这些表项为进程控制块），该表项包含程序计数器、寄存器、堆栈指针、文件描述符、用户和调度信息等，这些信息可以保证该进程能在状态切换或中断后能再次启动，像什么也没发生一样。

多道程序设计模型

采用多道程序设计可以提高CPU的利用率。

我们使用概率的角度来看CPU的利用率。假设一个进程等待IO操作的时间与其停留在内存中的时间的比为p，那么当内存中同时有n个进程时，所有n个进程都在等待IO（即CPU空转）的概率是p^n^，CPU的利用率=1-p^n^。n称为多道程序设计的道数。

线程

进程与线程的关系

进程是资源分配的最小单位，而线程是资源调度的最小单位。[2]

进程有一致但独立的地址空间，而线程共享一个地址空间。

线程是轻量级的进程，其创建与上下文切换都比进程快得多。

为什么需要多线程

主要原因：许多应用中同时存在着多种活动，其中某些活动随着时间的推移会被阻塞。通过将这些应用程序分解为可以和所有准并行运行的多个线程，程序设计、用户体验和性能会变得更好。

  1. 多个线程拥有共享同一地址空间和所有可用数据的能力
  2. 线程比进程更轻量级，创建一个线程比创建一个进程要快10~100倍
  3. 如果存在大量的计算和大量的IO处理，多线程允许这些活动彼此重叠进行，从而加快执行速度

例子：

一个字处理程序，需要与用户交互，当用户修改后还需要重新格式化文件。如果是单线程程序，用户修改后，程序马上去格式化，如果是大文件，则时间较长无法响应用户的其他需求。但如果我们程序有两个线程，一个线程与用户交互，另一个在后台格式化处理。当用户修改后，交互的线程通知后台线程进行格式化处理，期间交互线程仍可以响应用户的一些简单命令，也许当用户请求查看格式化好的文件时已经格式化好了，用户的体验也就更好。我们还可以再添加一个线程用于文件的备份，该线程周期性地保存文件内容。

线程模型

每个线程都有自己的堆栈，因为通常每个线程都会各自调用不同的过程，从而有一个不同的执行历史。

在多线程的情况下，进程通常会从当前的单个线程开始，这个线程有能力创建新的线程，新线程自动在创建线程的地址空间运行。通常线程没有层次关系，所有线程都是平等的（有时候会具有父子关系）。

POSIX线程

在unix中，有一个通用的线程包pthread，以下是其中常用的函数调用：

pthread_create创建新线程
pthread_exit结束调用的线程
pthread_join等待一个特定线程退出
pthread_yield让出cpu来运行另一线程

用户级线程与内核级线程

用户级线程

将线程包放在用户空间中，内核对线程包一无所知。从内核角度看，就是按正常的单线程进程管理。在用户控件管理线程，每个进程都需要有一张线程表，用来跟踪与记录各线程的属性，如程序计数器，堆栈指针等，以便后续线程状态切换的复原。

用户级线程的切换可以在几条指令内完成，比内核级至少快一个数量级。

用户级线程的一个问题是实现阻塞系统调用，如果线程实际进行会阻塞的系统调用，则所有线程会停止（因为用户级线程是进程内线程调度）。因此，有许多方法被提出，如使用非阻塞的系统调用，或阻塞前通知替换等。

还有一个问题就是，由于在一个单独的进程内部是没有时钟中断（因为时钟中断是硬中断，进入内核态后因为系统按单线程进程管理，所以对内部的线程是无法处理的）的，所以用户级线程包中一旦一个线程开始执行，那么该进程中其他线程就不能运行，除非第一个线程主动放弃CPU或运行结束。

内核级线程

每个进程不再有线程表，相反，内核中有用来记录系统中所有线程的线程表。当某个线程希望创建或撤销一个线程时，它进行一个系统调用，这个系统调用是通过更新线程表来完成的。

所有阻塞线程的调用都以系统调用的形式实现，不需要任何新的非阻塞系统调用，缺点就是系统调用的代价比较大。

进程的通信

有三个问题：

  1. 信息传递
  2. 互斥
  3. 同步

第一个问题对线程来说比较容易，因为它们共享同一个地址空间，但另外两个问题和对应的解决方法同样适用于线程。

互斥问题

竞争条件：多个进程读写共享数据，其最后的结果取决于进程运行的精确时序。

互斥（mutual exclusion）：以某种手段确保当一个进程在读写一个共享数据时，其他进程不能做同样的操作。

临界区：对共享内存进行访问的程序片段。

如果能使两个进程不可能同时处在临界区，那么就能避免竞争条件。

典型问题：生产者-消费者问题（仔细阅读，有错误实例、伪代码与解析）

使用信号量与互斥量的C代码

信号量

用于解决进程同步或互斥问题而引入的整型变量。

对于生产者-消费者问题而言，信号量mutex用于互斥，fill和empty用于同步。

互斥量

如果不需要信号量的计数能力，有时候可以使用信号量的简化版本，即互斥量（其实就是二进制信号量）。对于生产者-消费者问题，这只能用于解决缓冲区大小为1的情况。

管程

任意时刻管程中只会有一个活跃进程，这一特性使得管程能有效地完成互斥，这是编译器的任务。由于无需考虑互斥问题，我们只需关心如何让进程在无法继续时阻塞，方法仍然是上述的条件变量。

管程是编程语言的组成部分，java中便有管程，但是c和c++没有，因此这里不做过多的探讨。

消息传递

是系统调用，而不属于具体语言。

通常会在并行程序设计系统中使用消息传递，这里不做过多的探讨。

调度

何时调度

  1. 创建新进程后，需要决定先运行父进程还是子进程
  2. 一个进程退出时，一般会选择一个就绪的进程，如果没有，则运行系统提供的一个空闲进程。
  3. 一个进程被阻塞后，需要选择另一个进程运行
  4. IO中断发生时，一般这时候某些被阻塞的进程就会称为可运行的就绪进程了。

如果硬件时钟提供周期性的中断，可以在每k个时钟中断时做出调度决策。

根据如何处理时钟中断，可将调度算法分为两类：抢占式与非抢占式。

非抢占式调度算法调度一个进程，然后让该进程运行直至被阻塞或自动释放CPU，它不会被强制挂起，因此在时钟中断时不会发生进程调度，在处理完时钟中断后，如果没有更高优先级的进程到达，被中断的进程会继续运行。

而抢占式调度算法会让进程运行某个固定时段的最大值，到时间后如果该进程还在运行则将其挂起，挑选另一个进程运行。要进行抢占式调度，就需要在该时段的末端发生时钟中断，以便把CPU控制返回给调度程序。

当然，如果没有可用的时钟，则只能使用非抢占式算法。

调度算法的分类

在不同的系统中，调度程序的优化目标是不同的。通常分为三种系统环境：

  1. 批处理
  2. 交互式（分时）
  3. 实时（这里不探讨该系统的调度算法，不常用）

三种系统的介绍以及各自常用的调度算法

三种系统的区别

批处理系统中，不会有用户在一旁等待快捷响应，因此非抢占式算法或每个进程都有长时间周期的抢占式算法都可以，这样减少了进程切换从而改善了性能。

交互式系统中，为了用户的体验抢占是必需的。

调度算法的目标和指标

  • 所有系统（目标）：
    • 公平：给每个进程公平的CPU份额
    • 策略强制执行：保证规定的策略被执行
    • 平衡：保持系统所有部分都忙碌
  • 批处理系统：
    • 吞吐量：每小时完成的作业数
    • 周转时间：从提交作业到完成作业的平均时间
    • CPU利用率（不是个好的指标）
  • 交互式系统
    • 响应时间：快速响应请求
    • 均衡性：满足用户的期望

具体的调度算法

批处理系统中

  1. 先来先服务：对短作业不友好
  2. 最短作业优先：在所有作业都可同时运行的情况下，最短作业优先算法是最优的
  3. 最短剩余时间优先：是最短作业优先的抢占式版本
  4. 最高响应比优先：1+等待时间 / 运行时间

1，2非抢占式，3抢占式

交互式系统中

  1. 轮转调度：
  2. 优先级调度
  3. 多级队列
  4. 最短进程优先
  5. 彩票调度
  6. 保证调度（每个进程公平，一般来说是均分）
  7. 公平分享调度（每个用户公平，一般来说是均分）

线程调度

当若干进程都有多个线程时，就存在两个层次的并行：进程和线程。这样的调度取决于是用户级线程还是内核级线程。

若是用户级线程，由于内核并不知道线程的存在，所以内核和以前一样操作，选取一个进程A，给予时间片控制，A中的线程调度程序选择运行那个线程由于进程内不存在时钟中断，所以该线程可以任意运行多少时间。从实用角度考虑，一般调度算法使用的是轮转调度和优先级调度。

若是内核调度，则内核选择特定的线程运行，给其赋予一个时间片，时间片结束后挂起该线程。

两者的差别主要在于性能，用户级线程切换只需要少量指令，而内核级线程却需要完整的上下文切换（因为它不考虑属于哪个进程，也就没有共同的地址空间了），修改内存映像，这导致若干的延迟。

文件系统

文件的存储实现

扇区是对硬盘而言，块是对文件系统而言。文件系统不是一个扇 区一个扇区的来读数据，太慢了，所以有了block（块）的概念，它是一个块一个块的读取的，block才是文件存取的最小单位。一般是4KB一块。

1. 连续分配

是最简单的分配方案，即将每个文件连续存储在磁盘上。

这一方法有两大优势：

  1. 实现简单，记录每个文件的磁盘块只需要记住第一块的磁盘地址和文件块数即可
  2. 读操作性能好，只需要找到初始位置，不需要再寻道、旋转等，连续读即可。

但是随着时间的推移，文件的不断添加与释放会使磁盘产生很多碎片，后期要想存储一个新文件很难找到位置。

但是这一方法也不是没有用处，比如DVD这种一次性写的介质，就很适合使用连续分配这一方法。

2. 链表分配

为每个文件构造磁盘块链表。每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。

这一方法可以充分利用磁盘块，无需担心因为碎片而浪费空间。而且同样只需要存放第一块的磁盘地址，就可以访问到其他块。

另一方面，链式存储的随机访问相当缓慢，尤其这还是磁盘IO访问。而且，由于指针占去了一些字节，所以要完整读出文件内容，就需要获取各个块的数据部分然后拼接起来，这其中会涉及复制而引发额外的开销。

3. 用内存中的表进行链表分配

如果取出每个磁盘块中的指针字段，将他们放在内存的表中，就可以解决上述的两个问题。

每个表项存储着下一磁盘块的块号，顺着这一链就可以找到该文件的所有磁盘块。内存中这样的一个表格称为文件分配表（File Allocation Table, FAT），现在各个版本Windows仍然支持这一管理方式。

但这一方法有一个缺点就是必须把整个表都放在内存中，对于比较大的磁盘来说，表会十分大，占用很多内存，这是不实际的。

4. i节点

给每个文件都赋予一个称为i节点（index-node）的数据结构，其中列出了文件属性与文件块的磁盘地址。

这种机制有很大的优势，因为只有当对应文件打开时，其i节点才会在内存中，这通常比FAT所占据的空间要小。

目录的存储实现

打开文件时，操作系统利用给出的路径名找到相应的目录项，目录项提供了查找文件磁盘块需要的信息，这因系统而异，可能是磁盘块的初始地址、第一个块的编号或者是i节点号。总之，目录系统 的主要功能就是把文件名映射为定位文件数据所需的信息。

对于使用i节点的系统，文件属性是存放在i节点中而不是目录项中的，这样目录项会更短，只有文件名和i节点号。

现代操作系统都支持可变长度的长文件名，这是如何实现的呢？

我们可以使目录项本身是固定长度的，而将文件名放置在目录后面的堆中（目录项中的指针指向堆中的文件名）。这一当一个文件目录项被移走后，另一个文件的目录项总可以适合这个空隙。

内存管理

页面置换算法

最近未使用

大部分支持虚拟内存的计算机中，系统为每个页面都设置了两个状态位，页面被读取设置R位，被修改设置M位。

利用R位和M位可以将页面分为4类

  • 第0类：没有访问，没有修改
  • 第1类：没有访问，已被修改
  • 第2类：已被访问，没有修改
  • 第3类：已被访问，且被修改

NRU（Not Recently Used）算法是当启动一个进程时，将所有页面的两个位由操作系统置为0，R位被时钟中断定期清零，以区分最近没有被访问的页面和被访问的页面（其实就是降低各个类的编号）。

看起来第1类是不可能出现的，其实第3类如果被时钟中断R位清零就得到了第1类。

缺页中断时，该算法会随机地从编号最小的页面中挑选一个淘汰。

先进先出

操作系统维护一个页面链表，最新进入的页面在表尾，最早的在表头，缺页中断时就淘汰表头页面，并把新页调入的页面插入表尾。

第二次机会

FIFO可能会把经常使用的算法置换出去，为了避免这一问题，可以检查最老页面的R位，如果是0，则立刻置换，如果是1，则将R位清零，并将该页面放到链表的尾端，装入时间就像刚装入一样，这就是给了第二次的机会。

时钟

第二次机会是比较合理的置换算法，但是经常要在链表中移动页面，降低了效率。

我们可以把所有的页面放入一个环形链表，指针指向最老的页面。

每当发生缺页中断，检查指针所指页面的R位是否为0，是则淘汰，并将新的页面插入该位置，然后把指针向前移动一位；否则清除R位，并把指针向前移动一位。

最近最少使用

LRU（Least Recently Used）算法：在发生缺页中断时，置换未使用时间最长的页面。

一种实现是在内存维护一个所有页面的链表，将最近最多使用的放在表头，最近最少使用的放在表尾，每次使用到的页面如果在链表中，就把它取出并放到表头。不过这个实现一方面很耗时。

一种硬件实现是使用一个计数器，每次执行指令自增1，每个页表项中提供一位来容纳这个值，每次访问时就把计数器的值存到访问的页表项中。淘汰页面时选择最小的即可。虽然很符合“最近最少使用”的含义，缺点是消耗了很多存储空间；另外，计数器的溢出也是个问题。

硬件的实现较为复杂，但我们可以用软件近似实现。一种软件实现被称为NFU(Not Frequently Used，最不常用)，每个页面使用一个计数器，每次时钟中断时，将页面的R位（是否被引用，0或1）加到计数器上。缺页中断时置换计数器值最小的。这种实现的坏处是它“从不忘记任何事情”，简单地说就是在之前计数器值比较高的页面，即使不再访问，仍然会保持这个值；而别的页面在后续始终无法超过。

对NFU做一个小修改，就可以很好的模拟LRU：将R位增加前先计数器右移、R位增加到计数器左边的最高位而不是右边的最低位。修改后的算法称为老化(aging)算法。其蕴含的特征是：越高位越新，最近的使用权重最大；早期的使用记录会随着右移而舍弃。

老化算法就不需要担心溢出问题，但同样由于计数器位数有限（比如8位），会限制对以往页面的记录。比如如果两个页面的计数器都是0，那我们只能随机选择一个，但其实有可能其中一个页面在9个时钟前是被访问了的，但我们看不到这些。 在实践中，如果时钟是20ms，那么8位其实是够用的，毕竟一个页面160ms没有被访问说明它很可能不那么重要。

分页系统的设计

共享页面

在Unix中，在进行fork系统调用后，父子进程共享程序文本和数据。在分页系统中，通常是让这些进程分别拥有自己的页表，但是都指向同一个页面集合。这样在fork后就不需要进行页面复制，然后这些页面都设为只读。

只要两个进程都只读数据，这种情况就可以一直保持下去。但只要有一个进程更改一点数据，就会触发只读保护，引发操作系统陷阱，生成一个该页的副本，这一每个进程都拥有自己的专用副本，两个副本都可读写了。

这一策略意味着那些从不会执行写操作的页面是不需要复制的，只有要修改的会复制，这种方法称为写时复制，减少复制而提高了性能。

共享库

静态链接会链接调用的库中使用的函数，加载到可执行文件中去，当程序被装入内存执行时，所有函数都已经准备就绪了。但当我们静态链接上百个包含这些库的程序时，很容易浪费大量的磁盘空间，装载这些程序时也会浪费大量的内存空间。

这就是引入共享库的原因，当一个程序与共享库链接时，链接器没有加载被调用的函数到可执行文件中，而是加载了一小段存根，到时共享库和程序一起加载到内存中，如果其他程序已经加载了某个共享库，就没必要再加载他了。

而且除了可以使可执行文件更小、节省内存空间外，共享库的函数如果被更新，也不需要重新编译调用了这个函数的程序。

内存映射文件

（是共享内存通信方式的实现原理）

共享库实际上是一种更为通用的机制——内存映射文件的特例。这种机制的思想是：进程可以发起系统调用，将一个文件映射到虚拟内存空间中，当进程退出映射时，改动的页面会被写回到磁盘文件。

如果多个进程同同时映射了同一文件，那么它们就可以通过共享内存来通信，一个进程写后，一个进程就可以立刻读到，这个机制提供了高带宽通道。

分段分页机制

x86的实现

将一个地址解析为（选择子，偏移地址）的二元组。

为了向后兼容，保护模式还是采用“段基址+段偏移”的寻址方式，但是由于要提供诸多的保护限制，段寄存器是放不下的，因此出现了两个在虚拟内存中十分重要的两个表：LDT（局部描述符表）和GDT（全局描述符表），每个程序都有自己的LDT，而一个计算机上所有程序共享一个GDT。LDT描述每个程序的段，包括代码段、堆栈段等，而GDT描述整个系统的段。全局描述符中含有一个个的表项，称为段描述符，描述了段基址、段界限、内存段类型属性等。

实模式中段寄存器放的是段基址，而保护模式下放的是选择子，高位可以作为全局描述符的索引，取出对应的描述符，若合法访问（如不越界、权限合法等），则可取出对应的段基址。

若禁止分页，则由段基址和偏移得出的地址就被解释为物理地址进行读写操作，即得到的是纯分段的方案。

若允许分页，则解释为虚拟地址，并通过页表映射为物理地址进行访问。

磁盘管理

磁盘臂调度算法

先来先服务

按请求顺序完成请求，一般来说寻道时间会很长

最短寻道优先

下一次总是处理与磁头最近的请求以使得寻道时间最小化。

这样响应时间确实是最优的，但是很容易使得磁盘臂停留在磁盘的中部区域，而两端的极端地区的请求等待时间很长，即 获得最小响应时间的目标与公平性存在冲突。

电梯算法

保持一个方向移动，知道在那个方向上没有请求为止，然后改变方向。

软件会维护一个二进制位表示方向UP和DOWN。

死锁

资源

需要排他性使用的对象称为资源，可以是硬件设备（如打印机）或是一组信息（数据库中加锁的记录）。

可抢占和不可抢占

可抢占资源可以从拥有它的进程中抢占而不会产生副作用。典型例子就是存储器，进程A占用内存，请求了打印机，然后开始使用打印机，但当它还没使用完由于时间片用完了而被换出，此时进程B占据内存也请求打印机，进程B会被阻塞。此时A占用了打印机，请求存储器；B占用了存储器，请求打印机。若两个资源都是不可抢占的，那么就死锁了。幸好存储器是可抢占的，B阻塞后，操作系统会把B换出内存，将A换入内存从而实现抢占，这样A继续完成打印任务。这个过程不会产生死锁。

因此总的来说，死锁与不可抢占资源有关，而有关可抢占资源的潜在死锁一般都可以通过对进程的资源重新分配而解决。

死锁简介

规范定义：如果一个进程集合中每个进程都在等待只能由该集合中其他进程才能引发的事件，那么该进程集合是死锁的。

在大多数情况下，所谓等待的事件就是其他进程占有的资源。此时，由于所有进场都不能运行，则它们都不能释放资源，也不能被唤醒。这种死锁称为资源死锁。

资源死锁的条件

四个必要条件：

  1. 互斥条件：每个资源只能分给一个进程，不然它就是可用的。
  2. 占有和等待条件：已经占有了资源，又请求别的资源。
  3. 不可抢占条件：已经分给一个进程的资源不能被强制性被抢占，只能由它显式释放。
  4. 环路等待条件：死锁发生时，系统一定有多个进程组成的环路，其中每个进程都在等待下一进程占有的资源。

死锁发生时，上述四个条件一定同时满足。

死锁建模

资源分配图

建立有向图，圆形表示进程，方形表示资源。

从资源节点到进程节点的有向边代表该资源已被该进程占用，从进程节点到资源节点的有向边代表当前进程正在请求该资源，且被阻塞。

资源分配图可以作为分析工具，每次请求释放后都检查图中是否包括环路。如果有环路说明死锁，否则没有死锁。

处理死锁的策略

  1. 忽略该问题。
  2. 检测死锁并恢复。
  3. 仔细对资源进行分配，动态避免死锁。
  4. 通过破坏引起死锁的四个必要条件之一，防止死锁的发生。

鸵鸟算法

鸵鸟算法：把头埋在沙子里，假装没有问题发生。如果死锁发生频率较低， 如五年一次，而每个月都会发生系统的硬件故障等，那么大多数工程师就不会花费精力去防止死锁。

死锁检测和恢复

死锁检测

每种类型一个资源的死锁检测

若节点数较少，我们可以直接观察资源分配图找出死锁的进程。

我们也可以使用一个具体的算法来排查，即依次将资源分配图中的每一个节点当做根节点，进行深度优先搜索，若有环，则存在死锁。

每种类型多个资源的死锁检测

资源分配图中一种资源是一个方形节点，若一种资源有多个实体，那么上一个方法就不管用了，因为有环进程也不一定会阻塞。

这时我们通常使用一种基于矩阵的算法检测死锁。

E是现有资源向量，A是可用资源向量。C代表当前分配矩阵，R代表请求矩阵。C的行是进程，列是资源，$C{ij}$代表进程i所持有的资源j的数量，同理$R{ij}$代表进程i所需要的资源j的数量。我们可以发现这四种数据间有一个恒等式：

即已分配的资源j的数量加起来再和其可供使用的资源数相加，结果就是该类资源的总数。

每个进程最初都是没有标记的，算法开始对进程标记，被标记说明该进程可执行，最终没被标记的进程即是死锁进程。

具体算法流程如下：

  1. 寻找一个没有标记的进程$P_i$，这一进程R矩阵的第i行必须小于等于A
  2. 如果找到了，则标记它（运行），然后将C矩阵的第i行加到A中（运行结束后交还资源），并转到第1步
  3. 如果没有这样的进程，算法终止

虽然算法运行过程不确定（因为进程运行顺序不确定），但是最终的结果都是相同的。

从死锁中恢复

  1. 抢占。将某一资源强制性从一个进程中取走给另一个进程使用，接着又送回。
  2. 回滚。周期性对进程进行检查点检查。检查点检查就是将进程的当前状态写入一个文件以备以后重启，其中状态包括了内存映像和资源状态等。一旦检测到死锁，就回滚到之前的检查点，重新分配资源。
  3. 杀死进程。最直接和最简单的方法就是杀死一个或若干个环中的进程。

死锁避免

安全状态

如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够是每个进程运行完毕，则该状态是安全的。

注意：不安全状态并不是死锁。如果一个不安全状态中某个进程请求其他资源前，先自己释放了一些资源，那么还是有可能最终所有进程运行完毕的。所以，安全状态和不安全状态的区别只是从安全状态出发，系统能够保证所有进程都能完成，而从不安全状态出发，就没有这样的保证。

银行家算法

判断对当前请求的满足是否会导致进入不安全状态，如果是则拒绝该请求；如果满足后仍然安全，则予以分配。

检测一个状态是否安全的算法与上述的死锁检测算法几乎一致。同样如果若干进程都符合条件，那么选择哪一个开始都没有关系，因为可用资源都只会增加，或者至少不变，而不会因此而变少。

死锁预防

破坏四个必要条件之一即可。

条件处理方式
互斥使用假脱机技术（spooling）
占有和等待在执行前就请求全部资源（那也就可以使用银行家算法了），或者在请求资源前先暂时释放当前占用的资源，然后再请求刚才占有和需要的资源
不可抢占抢占资源
环路等待给资源编号，只允许请求比当前占用资源编号更高的资源

参考

  1. 为什么Linux下要把创建进程分为fork()和exec()(一系列函数)两个函数来处理? ↩
  2. 操作系统中到底是谁分配的资源? ↩