操作系统基础

shilongshen included in Java学习笔记

2020-11-27 994 words 5 minutes

Contents

什么是操作系统

操作系统所处的位置：

底层是硬件，包括芯片，电路板，硬盘，键盘等

硬件的上层是软件，软件又分为用户态和内核态

其中操作系统运行在内核态中，处于软件的最基础部分，操作系统具有对所有硬件的完全访问权，可以执行机器能够运行的任何指令。

用户态的最低层次称为用户接口程序（用户与之交互的程序，基于文本的称为shell，基于图形界面的称为GUI），用户接口程序允许用户运行其他程序，例如web应用,电子邮件，音乐播放器。

文本模式登录后所取得的程序被称为壳（shell），这是因为这只程序负责最外面跟使用者（我们）打交道，所以被戏称为“壳”

在Linux中的shell为bash

操作系统本质上是一个运行在计算机的软件，用于管理计算机硬件和软件资源（操作系统是一个运行在内核态的软件）
操作系统屏蔽了硬件的复杂性
操作系统运行与裸机之上，为其他软件提供基础的运行环境

操作系统具有两种功能：

向应用程序提供抽象;例如将硬盘抽象为文件，使用该抽象，程序可以创建，读写文件，而不用直接和硬件打交道。
管理计算机资源;在相互竞争的程序间有序的控制对处理器、存储器以及其他I/O接口的分配。

什么是系统调用

如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。

线程中发生函数调用时, 就会在线程栈中分配函数调用栈, 而虚拟内存分配, 文件操作, 网络读写等很多功能都是由操作系统来实现的, 再向用户程序暴露接口, 所以线程免不了要调用操作系统提供的系统服务, 即系统调用.

Linux 的系统调用主要有以下这些：

Task	Commands
进程控制	fork(); exit(); wait();
进程通信	pipe(); shmget(); mmap();
文件操作	open(); read(); write();
设备操作	ioctl(); read(); write();
信息维护	getpid(); alarm(); sleep();
安全	chmod(); umask(); chown();

例：

如果一个进程正在用户态运行一个用户程序，并且需要一个系统服务，比如从一个文件读数据，那么它就必须执行一个陷阱或系统调用指令，将控制转移到操作系统。操作系统通过参数检查找出所需要的调用进程。然后，它执行系统调用，并将控制返回给系统调用后面跟随的指令。

1.什么是系统调用？

系统调用是操作系统（OS）提供给用户编程时的一些公共子程序，一般为函数或方法

2.为什么要使用系统调用？

OS为了安全的管理计算机软硬件资源，不允许程序员直接操作系统资源，例如I/O，进程，内存，文件

但是用户可以通过系统调用向OS请求相关资源的服务，比如I/O额请求和释放；设备启动；文件的创建，读写，删除；进程的创建，阻塞，唤醒等

总结：系统调用就是程序员给操作系统发送请求服务的方法或函数

好比，你去餐馆吃饭，你只需要向服务员点菜（系统调用），服务员就会处理你的请求，而不是你自己去做菜。

3.如何进行系统调用，操作系统如何响应？

程序员在代码中首先传递系统调用参数，然后由陷入（trap）指令负责将用户态转换为核心态，并将返回地址压栈备用，然后 CPU 执行相应的内核服务程序，最后返回用户态。

根据进程访问资源的特点，我们可以把进程在系统上的运行分为两个级别：

用户态(user mode) : 用户态运行的进程可以直接读取用户程序的数据。

内核态(kernel mode):可以简单的理解内核态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。

说了用户态和系统态之后，那么什么是系统调用呢？

我们运行的程序基本都是运行在用户态，如果我们调用操作系统提供的内核态级别的子功能咋办呢？那就需要系统调用了！

也就是说在我们运行的用户程序中，凡是与内核态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

这些系统调用按功能大致可分为如下几类：

设备管理。完成设备的请求或释放，以及设备启动等功能。

文件管理。完成文件的读、写、创建及删除等功能。

进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。

进程通信。完成进程之间的消息传递或信号传递等功能。

内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

1.进程和线程

什么是进程？（在并发总结中已经提及）

什么是线程？（在并发总结中已经提及）

进程和线程的区别（在并发总结中已经提及）

进程的状态实际上与线程的状态是一致的，包括了就绪（Ready）,运行（Running）和阻塞（blocked）//（在并发总结中已经提及）

线程和进程的区别

简单的理解：

进程是系统中的一个应用，进程不会相互影响。进程是程序运行的基本单位，系统运行一个程序就是一个进程从创建到灭亡的过程
一个进程中可以包含多个线程，一个线程开辟一个栈空间，假设有10个线程，就会开辟10个栈空间。但是不同线程之间是共享方法区和堆的。
- 栈是线程私用的，生命周期和线程相同，栈描述的是Java方法执行的线程内存模型：每个方法执行的时候都会同步创建一个栈帧用于存储局部变量表/操作数栈，动态连接。方法出口等信息。
- 堆是所有线程共享的区域。这在JVM启动时创建，此内存唯一的目的就是存放对象实例
- 方法区是所有线程共享的区域，用于存储已被JVM加载的类型信息，常量，静态常量，即时编译后的代码缓存片段。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


这里要引入一个概念：除了CPU以外所有的执行环境，主要是寄存器的一些内容，就构成了进程的上下文环境。进程的上下文是进程执行的环境。当这个程序执行完了，或者分配给他的CPU时间片用完了，那它就要被切换出去，等待下一次CPU的临幸。在被切换出去做的主要工作就是保存程序上下文，因为这个是下次他被CPU临幸的运行环境，必须保存
---


进程的颗粒度太大，每次的执行都要进行进程上下文的切换。如果我们把进程比喻为一个运行在电脑上的软件，那么一个软件的执行不可能是一条逻辑执行的，必定有多个分支和多个程序段，就好比要实现程序A，实际分成 a，b，c等多个块组合而成。那么这里具体的执行就可能变成：

程序A得到CPU -> CPU加载上下文，开始执行程序A的a小段，然后执行A的b小段，然后再执行A的c小段，最后CPU保存A的上下文。

这里a，b，c的执行是共享了A进程的上下文，CPU在执行的时候仅仅切换线程的上下文，而没有进行进程上下文切换的。进程的上下文切换的时间开销是远远大于线程上下文时间的开销。这样就让CPU的有效使用率得到提高。这里的a，b，c就是线程，也就是说线程是共享了进程的上下文环境的更为细小的CPU时间段。线程主要共享的是进程的地址空间。

作者：zhonyong
链接：https://www.zhihu.com/question/25532384/answer/81152571
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

小结：进程和线程都是一个时间段的描述，是CPU工作时间段的描述，不过是颗粒大小不同。参考

进程的实现

为了实现进程模型，操作系统维护这一张表格，即进程表（PCB）。每个进程占用一个进程表项（或称为进程控制块）。该表项中包括了进程的状态的重要信息，包括程序计数器，堆栈指针，内存分配状况，所打开文件的状态，账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态必须保存的信息，从而保证该进程随后能再次启动，就像从未被中断一样。

注意：进程表是在操作系统中的（在内核态中）

再一次明确：进程切换的效率是比较低的

在切换进程时，首先用户态必须切换到内核态；然后保存当前进程的状态，包括在进程表中存储寄存器值以便以后重新加载。在许多系统中，内存映像也必须保存；接着，通过运行调度算法选定一个新进程；之后，应该将新进程的内存映像重新载入MMU（内存管理单元）中；最后，新进程开始运行。除此之外，进程切换还要使得整个内存高速缓存失效，强迫缓存从内存中动态重新载入两次（进入内核一次，出内核一次）。

进程是由内核管理和调度的，所以进程的切换只能发生在内核态。

所以，进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。

通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后恢复到 CPU 中，这使得这个进程可以继续执行，如下图所示：

为什么需要线程

主要原因：在一个进程中可能会同时发生多个活动。其中某一些活动随着时间的推移会被阻塞。通过将进程分解为多个线程，程序设计模式会变得简单
线程比进程更加的轻量化，所以线程比进程更容易创建和销毁。

进程和线程的区别

Ⅰ 拥有资源

进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

Ⅱ 调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

Ⅲ 系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

Ⅳ 通信方面

线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

注意：一个进程中的所有线程都有完全一样的地址空间，这意味着他们也共享同样的全局变量（共享公共内存）。除了共享内存地址外，所有线程还共享同一个打开的文件集，子进程、定时器以及相关信号等。

一个进程总是由某个用户拥有，该用户创建多个线程是为了他们之间的相互合作而不是竞争。

而不同进程可能由不同用户拥有，不同进程间可能存在敌对关系。

线程的分类

线程可以分为用户级线程和内核级线程，其调度算法与可以是进程的调用算法中的一种。

两者间的差异在于性能。

用户级线程的线程进行切换时只需要少量的机器指令，而内核级线程的线程进行切换时需要完整的上下文切换（修改内存映像，清理高速缓存等内容）
用户级线程可以使用专门为应用程序定制的线程调度算法

进程和程序的区别

举个例子：

有一位科学家在为他的女儿制作生日蛋糕。他有做蛋糕的食谱，厨房里有所需的原料。在这个比喻中，做蛋糕的食谱就是程序（即用适当形式描述的算法），科学家就是CPU，而做蛋糕的各种原料就是输入数据。进程就是科学家阅读食谱，取来各种原料以及烘制蛋糕等一系列动作的总和。

这里的关键思想是：一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。

小结：进程和线程有什么区别和联系

进程是正在执行程序的实例，是资源调度的最小单位，一个程序中可以包含多个进程，例如多次打开同一个程序

而线程是CPU调度和分配的最小单位，实际上可以将线程看成是更小的进程，一个进程中可以包含多个线程，这些线程共享进程中的资源，包括地址空间，打开的文件，全局变量。

打个比方：

我们有一个打印机程序，当我们运行这个程序时就会创建一个进程。当然我们可以同时打开多个打印机程序，这样就创建了多个进程。

在打印机进程中又包含了多个线程，比如其中一个线程需要读取输入的文件，一个线程需要读取的文件进行渲染，一个文件需要将渲染后的文件输出。进程中的线程通过协作来高效的完成任务。

进程表

每一个进程都占用一个进程表项，这个表项存储着进程的重要信息，包括了寄存器，程序计数器，堆栈内存分配状况，以及在进程中又运行态转换为就绪态或阻塞态必须保留的信息，以便在下次再次启动进程时，就像重未中断。

进程的上下文切换：对于单处理器来说，任何时刻都只能处理一个进程，当操作系统要将控制权由一个进程切换到另一个进程时，就会进行上下文切换。即保留当前进程的上下文，恢复新进程的上下文，然后将控制权交给新进程。

进程同步

讨论三个问题：

一个进程如何把信息传递给另一个
确保两个或更多的进程在关键活动中不会出现交叉
正确的顺序

竞争条件

有两个或多个进程读写同一共享数据，这两个进程可能会相互覆盖。取决于进程的访问次序，可能会导致共享数据被破坏。这称为竞争条件或竞态条件（ race condition ）（线程也有相似的概念）

临界区

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

互斥：多个进程在同一时刻只能有一个能进入临界区

忙等待互斥

实现互斥的几个方法（在这些方案中，当一个进程进入临界区更新共享内存时，其他进程不会进入临界区）

屏蔽中断
锁变量：设置一个共享（锁）变量，但是但是由于锁也是共享变量，所以会出现竞态
严格轮换法：

参考

设置一个变量turn,只有当turn=0时进程0才能够进入临界区，只有当turn=1时进程1才能够进入临界区

假设此时turn=0，进程0进入临界区，此时进程1因为turn不等于1则进行等待。

当进程0执行退出临界区，就将turn设为1，这时进程1就可以进入临界区了。

但是这个方法存在的一个缺点是：如果当进程0退出临界区，将turn设为1，然后执行非临界区的操作；这时进程1也在执行非临界区的操作，并没有将turn设为0；当进程0结束非临界区的操作后由于turn不为0，所以没有办法执行临界区的操作，需要等待。

因此在一个进程比另一个进程慢的情况下，并不适合用严格轮换法。
Peterson解法

假设有两个进程：进程0和进程1，有一个数组interested，长度为2，初始化为false。

假设进程0先进入，执行语句
1 2 3

int other=1-process -->1-0=1 interested[0]=true --> 数组interested的第一位被设为true turn=0 -->turn=0
这时进程1进入执行语句
1 2 3

int other=1-process -->1-1=0 interested[0]=true --> 数组interested的第二位被设为true turn=0 -->turn=1
在进入while语句之前，各个变量的值为
1 2 3

turn=1 other=0 intersted[]=[true,true]
所以
1

while(turn==1&&intersted[0]=true)
这时因为turn==1，进程0跳出while循环，进入临界区；而进程1进行等待；直到进程0退出临界区，令intersted[0]=false，进程1进入临界区
TSL指令

睡眠与唤醒

生产者消费者问题

问题描述：两个进程共享一个内存缓存区，其中一个进程负责向缓冲区中生产数据，一个进程负责向缓冲区中消费数据。如果当缓冲区存放满了，生产者就要进行睡眠，直到消费者进行消费，缓冲区中有空闲位置。如果当缓冲区为空时，消费者就要进入睡眠，直到生产者生产，缓冲区不为空。

存在问题：

使用一个整型变量count记录缓冲区中的数据个数，如果count==N,则使生产者睡眠，否则生产一个数据，count+1,如果count==1,则唤醒消费者进行消费。

同理，如果count==0,消费者睡眠，否则消费者消费一个数据，count-1，如果count==N-1,则唤醒生产者进行消费。

但是如果数据的个数为0，且消费者执行if(count==0)时，切换到生产者，此时生产者进行生产，count==1，唤醒消费者。但是实际上消费者此时并未睡眠，所以这个唤醒信号会丢失。当消费者运行时，发现count==0，所以进入睡眠，此时切换到生产者进程，count=2。从此count永远不会等于1，所以消费者永远不会被唤醒，所以生产者迟早会将缓冲区填满，这时生产者和消费者都进入睡眠。

问题的实质是唤醒信号和唤醒操作是分离的，如果发生唤醒信号丢失，唤醒操作就不会执行

信号量

信号量是一个整型变量，可以对其进行down和up操作，也就是常见的P , V 操作。

down：如果信号量大于0，执行减1操作，并继续操作；如果信号量等于0，进程睡眠，等待信号量大于0。
up：对信号量进行加1操作，唤醒睡眠的进程让其进行down操作。up操作与唤醒进程的绑定的

down和up被设置为原子操作，一旦一个信号量开始操作，则在该操作完成或阻塞之前，其他进程均不可以访问该信号量。

原子操作：指一组相关联的操作要么不间断的执行，要么不执行。

假设进程1相对共享变量进行操作，此时信号量为1，则进行down操作，此时信号量为0；如果这个时候进程2也向对共享变量进行操作，对信号量执行down操作，但是此时信号量为0，所以会使进程2睡眠，down操作也一并暂停。当进程1结束共享变量的访问后，对信号量执行up操作，信号量为1。此时进程2唤醒，就可以进行访问了。

使用信号量来解决生产者消费者问题

互斥量

互斥量是一个处于两态之一的变量：解锁和加锁。

如果一个进程需要访问临界区，他将调用互斥量。如果该互斥量是解锁的，该进程则可以自由进入临界区

如果该互斥量是加锁的，调用进程将会阻塞，直到临界区中的进程完成。

如果有多个进程阻塞，则会随机选择选择一个进程并允许他获得锁。

管程

管程有一个重要的特性：即任何时刻管程中只能有一个活跃进程，这一特性使得管程能够高效的完成互斥。

管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞(使得进程进入等待队列)，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程（将等待队列中的进程放入锁池中）。

信息传递

屏障

避免锁

进程同步和进程通信间的区别

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；
进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

进程通信

管道

管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。

它具有以下限制：

只支持半双工通信（单向交替传输）；
只能在父子进程或者兄弟进程中使用。

FIFO

也称为命名管道，去除了管道只能在父子进程中使用的限制。

1
2
3


#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

消息队列

相比于 FIFO，消息队列具有以下优点：

消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

信号量

它是一个计数器，用于为多个进程提供对共享数据对象的访问。

共享存储

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。

需要使用信号量用来同步对共享存储的访问。

多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。

套接字

与其它通信机制不同的是，它可用于不同机器间的进程通信。

调度

如果有多个进程或线程同时竞争CPU,那么就必须选择下一个要运行的进程或线程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序所使用的算法称为调度算法。

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

1. 批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.1 先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

1.2 短作业优先 shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

1.3 最短剩余时间优先 shortest remaining time next（SRTN）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

2. 交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

2.1 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
而如果时间片过长，那么实时性就不能得到保证。

2.2 优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

2.3 多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

3. 实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

2. 内存管理

分层存储体系：

若干兆(MB) 快速，昂贵且易失的高速缓存（catch）->高速缓存的管理主要有硬件来完成
数千兆(GB) 速度和价格适中且同样易失的内存 ->内存的管理由编程人员来完成,本章介绍的内容
几兆兆(TB) 低速，廉价，非易失的磁盘存储
DVD，USB等可移动存储装置

操作系统中管理分层存储体系的部分称为存储管理器，它的任务是有效的管理内存，即记录哪些内存是正在使用的，哪些是空闲的；在进程需要时为其分配内存，在进程使用完后释放内存。

操作系统的内存管理主要是做什么？

操作系统的内存管理主要负责内存的分配与回收（malloc 函数：申请内存，free 函数：释放内存），另外地址转换也就是将逻辑地址转换成相应的物理地址等功能也是操作系统内存管理做的事情。

内存管理机制:

无存储器抽象

早期的计算机都没有存储器抽象。每一个程序都是直接访问物理内存。当一个程序执行如下指令:

1

MOV REGISTER,100

计算机会将位置为100的物理内存中的内容移到REGISTER中，因此那时呈现给编程人员的存储器模型就是简单的物理内存：从0到某个上限的地址集合，每一个地址对应一个可容纳一定数目而进行之·二进制位的存储单元，通常时8个。

在这种情况下，想要在内存中运行两个时不可能的。如果第一个程序在2000的位置写入一个新的值，将会擦除第二个程序存放在相同位置上的所有内容，这是行不通的。

存储器的抽象：地址空间

什么是地址空间

将物理地址直接暴露给进程会带来很多问题：

用户程序可以很容易的破坏操作系统
想要同时运行多个程序是很困难的

想要是多个程序运行于内存中并且不相互影响，需要解决两个问题：保护和重定位

地址空间为程序创造了一个抽象的内存。就是一个标识符

地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间（除了在一些特殊情况下需要共享它们的地址空间外）

比较难的是给每一个进程一个独有的地址空间，例如使得一个程序中的地址28对应的物理地址与另一个程序中的地址28对应的物理地址不同。

基址寄存器和界限寄存器是一种之前常用的方法：

基址寄存器和界限寄存器

基址寄存器和界限寄存器提供为每一个进程提供了一个独立的地址空间

当一个进程运行时，程序的起始物理地址装载到基址寄存器中，程序的长度装载到界限寄存器中。

每一次进程访问内存，取一条指令，读或写一个数据字，CPU硬件会在把地址发送给内存总线之前，自动把基址值（当前程序的起始物理地址）加到进程发出的地址值上。同时，它检查程序提供的地址是否大于或等于界限寄存器里的值（当前程序的长度），如果访问地址超出了界限，就会产生错误并终止访问。

使用基址寄存器和界限寄存器重定向的缺点：每一次重定向都需要进行比较和加法运算，而加法运算可能会产生进位，所以速度会慢。

交换技术

基址寄存器和界限寄存器的方法相当于将所有进程存在内存中。但是将所有进程存在内存中需要巨大的内存，若果内存不够，就做不到这一点。因此这一方法几乎不再使用了。

有两种处理内存超载的技术：

交换技术，把一个进程完整的调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，所以当它们不运行时不会占用内存（其中有一些进程会周期性的被唤醒以完成工作，然后就会又进入休眠状态）。
虚拟内存， ->接下来将介绍

注意一个问题：当进程被创建或换入时应该为它分配多大的内存?

如果进程的创建时其大小是不变的，则操作系统按照准确的大小进行内存分配即可。
如果进程的数据段是增长的，一种可用的分配策略为：当创建进程时为其分配一些额外的内存。当进程被换出到磁盘时，应该只交换进程实际上使用内存中的内容，因为将额外的内存交换出去是一种浪费。

空闲内存管理

在动态分配内存的时候（在创建进程和将进程换出时，内存应该如何变化），操作系统必须对其进行管理。一般有两种跟踪内存使用情况的方式：

位图
空闲区链表

使用位图的存储管理

将内存划分为小到几个字或大到几千字节的分配单元。每个单元对应于位图中的一位，0表示空闲，1表示占用。

优点：利用一块固定大小的内存（用于存储位图）就能对内存使用情况进行记录

缺点：在决定把一个占用k个存储单元的进程调入内存时，存储管理器必须搜索位图，在位图中找出k个连续0的串。这是十分耗时的。

使用链表进行管理

维护一个记录已分配内存段和空闲内存段的链表。其中链表中的一个结点或包括一个进程，或包括两个进程间的一块空闲区

链表的每个结点包含以下内容：空闲区(H)或进程(P)的指示标记，起始地址，长度和指向下一个结点的指针。

优点：当进程被换出时，链表的更新是非常方便的。

当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以用来为创建的线程（或从磁盘中换入的线程）分配内存。

首次适配法
下次适配法
最佳适配法
最差适配法
快速适配法

虚拟内存

解决程序大于内存的问题

基本思想：每个程序拥有自己的地址空间，这个空间被分割为多块，每一块被称为一页或页面。每一页有连续的地址范围。这些页被映射到物理内存中，但是并不是所有页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

注意：上述表述的可以理解为：虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存中，也就是一个程序不需要全部调用内存就可以运行。（如果调用到了不在物理空间中的内存地址，操作系统就将其装入物理内存中重新执行），这使得有限的内存运行大程序成为可能。

分页

由程序产生的地址称为虚拟地址，他们构成了一个虚拟地址空间。虚拟地址空间按照固定大小划分为被称为页面的若干单元。在物理内存中对应的单元被称为页框。页面和页框的大小通常是一致的。

例子：

当程序试图访问地址0时，例如执行了一下这条指令：

MOV REG ,0

将虚拟地址0送入MMU。MMU看到虚拟地址落在页面0（0-4095），根据其映射结果，这一页面对应的是页框2（8192-12287），因此MMU把地址变换为8192，并把地址8192送到总线上。内存对MMU一无所知，它只看到一个读或写地址8192的请求并执行它。MMU从而有效的将所有0-4095的虚拟内存地址映射到了8192-12287的物理地址。

假设有64K的虚拟地址空间和32K的物理内存地址，页面和页框的大小为4K，那么一共有16个页面和8个页框。因此只有8个页面被映射到了物理内存地址中。还有8个页面没有被映射到物理内存地址，如何为解决这一问题？

在实际的硬件中，用一个标记位“在/不在”来记录页面在内存中的实际存在情况。

当程序访问当了一个未被映射的页面，MMU会注意到该页面没有被映射（通过标记位来识别），于是CPU陷入到操作系统中，这个陷阱称为页面中断或缺页错误。操作系统找到一个很少使用的页框并将它的内容写到磁盘中（如果它不在磁盘上）。随后把需要访问的页面读到刚才回收的页框中，修改映射关系，然后重新启动引起陷阱的指令。

MMU的内部结构：

虚拟地址到物理地址的映射可以概括如下：虚拟地址被分为虚拟页号和偏移量。

虚拟页号可用于页表的索引，以便找到虚拟页面对应的页表项。由页表项可以找到页框项（如果有的话）。然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成送往内存的物理地址。

页表的目的是把虚拟页面映射为页框。

需要强调的是：虚拟内存本质上用来创造一个新的抽象概念-地址空间，这个概念是对物理地址的抽象，类似于进程是对CPU 的抽象。虚拟内存的实现，是将虚拟地址空间分解为页，并将每一页映射到物理内存的某个页框或者解除映射。

快表和多级页表

页表：将页面映射成页框，即虚拟地址映射成物理地址

需要解决的问题：

虚拟地址转换为物理地址的速度要快
虚拟地址空间大，页表也会有很大的问题

快表

为了使虚拟地址转换为物理地址的速度要快，操作系统在页表方案上引入了快表。

根据虚拟地址中的页号查询快表
如果该页号在快表中，直接从快表中读取相应的物理地址
如果该页号不在快表中，就访问内存中的页表，再从页表得到物理地址，同时将页表中的该映射表添加到快表中
当快表填满时，又要登记新页，就按照一定的淘汰策略淘汰掉快表中的一个页

多级页表

页面转换算法

回顾：缺页中断-当程序访问当了一个未被映射的页面，MMU会注意到该页面没有被映射（通过标记位来识别），于是CPU陷入到操作系统中，这个陷阱称为页面中断或缺页错误。操作系统找到一个<u>很少使用的页框并将它的内容写到磁盘中</u>（如果它不在磁盘上）。随后把需要访问的页面读到刚才回收的页框中，<u>修改映射关系</u>，然后重新启动引起陷阱的指令。

在程序运行过程中，如果要访问的页面不在内存（访问到了一个未被映射的页面）中，就发生缺页中断从而将该页调入内存中。

页面置换：

当发生缺页中断时，操作系统就必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。

对于换出内存的页面存在两种情况：

如果换出的页面在内存驻留期间已经被修改过了，就必须将它写回磁盘以更新该页面在磁盘上的副本
如果该页面没有被修改过，那么他在磁盘上的副本已经是最新的，不需要回写。直接用调入的页面覆盖被淘汰的页面就可以了。

注意：页面置换是发生在缺页中断的情况下的。当访问到了一个未被映射的页面才会发生缺页中断。

当发生缺页中断时，虽然可以随机的选择一个页面来置换，但是如果每次都选择不常使用的页面会提升系统的性能。

页面置换算法:

页面置换算法就是在发生缺页中断的时候如何选择页面的算法。

选择页面也就是选择了页框，因为这个页面本来是可以映射到页框的

最优页面置换算法

原理：在缺页中断发生时，有些页面在内存中，其中一个页面（包含紧接着的下一条指令的那个页面）将很快被访问，其他页面则可能要到10,100或1000条指令才会被访问，每个页面都可以用在该页面首次被访问前所要被访问的指令数作为标记。最优页面置换算法规定应该置换标记最大的页面。

这种算法的缺点是无法实现，因为我们在发生缺页中断时无法得知每个页面首次被访问的指令数。

最近未使用页面置换算法（NRU）

每个页面都有两个状态位，R与M，当页面被访问时，R被置为1，当页面被修改时，M被置为1.其中R会被定时清零，比如每个20ms被清零。可以根据R和M分为将页面分为4个状态：
- R=0，M=0 ，没有被访问，没有被修改
- R=0，M=1 ，没有被访问，被修改
- R=1，M=0 ，被访问，没有被修改
- R=1，M=1 ，被访问，被修改

当发生缺页中断时，NRU算法随机地从类编号最小的非空类（R=0，M=1）中挑选一个页面将它换出。

NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。

先入先出置换算法（FIFO）

原理：由操作系统维护一个所有当前在内存中的所有页面的链表，最新进入的页面放在链表尾部，最早进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加入表尾。

很少使用纯粹的先入先出置换算法。

第二次机会页面置换算法

FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法进行修改。

检查最老页面的R位。如果R位为0，那么这个页面既老又没被使用，可以立刻置换掉；如果R为1，就将其 R位清零，并把该页面放到链表的尾部，修改它的装入时间使得它就像刚装入一样，然后继续搜索。

时钟页面置换算法

尽管第二次机会算法比较合理，但是经常需要在链表中移动页面，既降低了效率，又不是很有必要。

一个更好的方法是将所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。

原理：当发生缺页中断时，算法首先检查表针指向的页面，如果R为0，则将其页面进行淘汰，并把一个新页面插入此处，然后将表针向前移一位；如果R为1，则将表针向前移一位，重复这一过程真到找到了R为0 的页面。

最近最少使用页面算法（LRU）

原理：在缺页中断发生时，置换未使用时间最长的页面。

虽然LRU在理论上是可行的，但是代价很高。为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是在每次访问内存时都必须要更新整个链表。

最优页面置换算法：将最长时间不再被访问的页面置换出去 –>无法实现，因为无法知道需要预知将来的状态

最近最少使用页面置换算法(LRU)：将未使用时间最长的页面置换出去

最近未使用页面置换算法(NRU)：随机在未被访问但是已被修改的页面中挑选一个将其置换

先进先出页面置换算法(FIFO)：将最先进入内存的页面置换出去

分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。目前我们讨论的虚拟内存都是一维的，虚拟地址从0到最大地址。在许多问题中，有多个独立的地址空间要比只有一个地址空间要好。

分页：一个进程有一个地址空间

分段：将地址空间分成多段

下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现（一个表与另一个表发生碰撞）。

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。要在这种分段的存储器中指示一个地址，程序需要提供两部分地址，一个段号，一个段内地址。

每个段是一个逻辑实体，比一个过程或一个数组，所以不同的段可以有不同种类的保护。比如一个过程段只允许执行，不允许读写；一个数组可以被读写但是不能被执行。

分段也有助于在几个进程中共享过程和数据。比如可以将图形库放在一个单独的段中由各个进程共享，而不需要在每个进程的地址空间中都保存一份。

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

先将内存分成若干段，每个段再分成若干页。

分页机制和分段机制的异同

共同点：

都是为了提高内存的利用率，减少内存碎片
页和段都是离散存储，所以都是离散分配内存的。但是每个页和段中的地址空间是连续的

不同点：

页的大小是固定的，由操作系统决定；段的大小是不固定的，是动态增长的，每个段拥有一个独立的地址空间
分页是为了得到更大的线性地址空间而不用购买更大的存储器；分段是为了将程序和数据可以被划分为逻辑独立的地址空间，比如一个段可以是一个数组或者是一个堆栈，这样更加有利于共享和保护。

分页就是在不用购买存储器的前提下解决内存太小的问题；而分段也是用于解决内存太小的问题，它是在分页的基础上将程序的地址空间划分多个拥有独立地址空间的段，每个段都是一个逻辑实体，这样更加有利保护和共享。

对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
地址空间的维度：分页是一维地址空间，分段是二维的。
大小是否可以改变：页的大小不可变，段的大小可以动态改变。
出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

3. 输入/输出

I/O硬件原理

I/O设备

I/O设备可以大致分为两类：块设备和字符设备

块设备：将信息存储在固定大小的块中，每个块有自己的地址。所有的传输以一个或多个完整的（连续的）块为单位。块设备的基本特征是每个块都能独立于其他块进行读写。硬盘，光盘和USB盘是常见的块设备。
字符设备：以字符为单位发送和接收一个字符流，而不考虑任何块结构。打印机、网络接口、鼠标，以及大多数与磁盘不同的设备都可以看做字符设备。

设备管理器

I/O设备由机械部分和电子部分组成。电子部分称为设备控制器或适配器，常以主板上的芯片的形式出现。

设备控制器的任务是把串行的位流转换为字节流，并进行必要的错误校正工作。

内存映射I/O

CPU与设备管理器进行通信的方式

每个控制器有几个寄存器用来与CPU进行通信。通过读写这些寄存器，操作系统可以了解设备的状态或控制设备。

除了控制寄存器外，许多设备还有一个操作系统可以读写的数据缓冲区。

CPU如何与设备的控制寄存器和缓冲区进行通信？

方法1：每个控制寄存器被分配一个I/O端口号

直接存储器存储（DMA）

方法2：

重温中断

I/O软件原理

I/O软件的目标

设备独立性。应该能够编写出这样的程序：它能够访问任意I/O设备而无需事先指定设备。
错误处理
同步和异步传输
缓冲

I/O可以通过三种不同的方式来实现，1.程序控制I/O，2.中断驱动I/O，3.使用DMA的I/O

程序控制I/O

基本思路：在程序（设备驱动程序）中通过不断地检测I/O设备的当前状态，来控制I/O操作的完成。具体来说，在进行I/O操作之前，要循环地检测设备是否就绪；在I/O操作进行之中，要循环地检测设备是否已完成。从硬件来说，控制I/O的所有工作均由CPU来完成。

也称为繁忙等待方式（busy waiting)或轮询方式（polling)。

缺点：在进行I/O操作时，一直占用CPU时间。

中断驱动I/O

循环检测的控制方法占用了太多的CPU时间，可能会造成CPU时间的浪费。例如：假设打印机的打印速度为100字符/秒，在循环检测方式下，当一个字符被写入到打印机的数据寄存器中后，CPU需要等待10毫秒才能写入下一个字符。

一种解决的办法：中断驱动的控制方式。

1
2
3
4
5
6


1 //系统调用函数print
2 copy_from_user(buffer,p,count);//p:内核缓冲区
3 enable_interrupts()；
4 while(*printer_status_reg!=READY)；
5 *printer_data_register=p[0];
6 scheduler()；

在执行系统调用函数print时进程是否切换？没有切换，A仍为运行状态，但执行的代码是操作系统代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


 1 //中断处理程序
 2 if(count==0)
 3 {
 4   unblock_user();
 5 }
 6 else
 7 {
 8   *printer_data_register=p[++i];
 9   count--；
10 }
11 acknowledge_intereupt()；
12 return_from_interrupt()；

中断驱动方式的基本思路是：用户进程通过系统调用函数来发起I/O操作，并在发起后阻塞该进程，调度其他的进程使用CPU。在I/O操作完成时，设备向CPU发出中断，然后在中断处理程序中做进一步的处理。在中断驱动方式下，数据的每次读写还是通过CPU来完成，但是当I/O设备在进行数据处理时，CPU不必等待，可以继续执行其他的进程。

使用DMA的I/O

适合大规模数据传输！

I/O读操作的典型过程：

-CPU向设备控制器发出命令，启动读操作；

-设备控制器控制I/O设备完成此次读操作，并将数据保存在设备控制器内部的寄存器或缓冲区中，然后中断CPU；

I/O软件层次

盘

磁盘结构

盘面（Platter）：一个磁盘有多个盘面
磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道
扇区(Track Sector)：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理存储单位，目前主要有512bytes和4K两种大小
磁头（Head）：与盘面非常接近，能够将判别上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）
制动手臂（Actuator arm）:用于在磁道中移动磁头
主轴（Spindle）：使得整个盘面转动。

下面将分别介绍

磁道（Track）如下图，数据存储在磁道上

扇区：

如何确定数据存储在硬盘上的哪一个位置，实现快速读写数据（这么多文件存在磁盘上该如何快速的找到需要读写的数据呢？）

有两种方式：

分区表

在写数据时，再将数据存储到磁道后，会将分区表中记录数据存储位置对应的扇区和簇，这能够大致的定位数据的位置

在读数据时，首先在查找分区表，找到数据对应的存储位置并进行读取（通过移动磁头）。

cache

通过精确的映射到数据存储的位置

磁盘调度算法

读写一个磁盘块需要多长时间，取决与以下三点：

寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
旋转时间（主轴转动盘面，使得磁头移动到适当的扇面上）
实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使得磁盘的姘居寻道时间最短。

1.先来先服务

FCFS，First Come First Served

磁盘的驱动程序每次接收一个请求并按照接收顺序完成请求。

优点：公平和简单

缺点：因为未对寻道做任何优化，使平均寻道时间可能较长。

2.最短寻道时间优先

SSTF，Shortest Seek Time First

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

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

3.电梯算法

SCAN

电梯总是保持一个方法运行，直到该方向没有请求为止，然后改变运行方向。

电梯算法（扫描算法）和电梯的运行过程类似，总是按照一个方向来进行磁盘调度，知道该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决SSTF的界问题。

4. 死锁

资源

简单的来说，资源就是随着时间的推移，必须能够获取、使用以及释放的任何东西。

可抢占资源和不可抢占资源

可抢占资源：可以从拥有它的进程中抢占而不会产生任何的副作用，存储器就是一类可抢占资源
不可抢占资源：在不引起相关计算失败的情况下，无法将它从占有它的进程处抢占过来。

死锁与不可抢占资源有关。

有关可抢占资源的潜在死锁通常可以通过在进程之间重新分配资源而化解。

使用一个资源需要的事件顺序可以抽象为：

请求资源
使用资源
释放资源

资源获取

一种允许用户管理资源的可能方法是为每一个资源配置一个信号量。

现在考虑两个进程和两个资源的情况：当进程A获取了资源1，进程B获取了资源2，每个进程如果都想要请求另一个资源就会被阻塞，那么，每个进程都无法继续运行。这种情况就是死锁。

死锁简介

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

每个进程都在等待其他进程占用的资源，就造成了死锁

在大多数情况下，每个进程所等待的事件是释放进程集合中其他进程所占用的资源。这种资源称为资源死锁，是最常见类型的死锁，但是不是唯一的类型。

资源是事件的一种，还有其他类型的事件。

资源死锁的条件

资源死锁的四个必要条件：

互斥条件：每个资源要么就是分配给了一个进程（要有只能有一个，不能有多个），要么就是可用的
占有和等待条件：已经得到某个资源的进程可以再请求得到另外的资源
不可抢占条件：已经分配给一个进程的资源不能够强制性的抢占，只能够由占有它的进程显式的释放
环路等待条件：死锁发生时，一定有两个或两个以上的进程组成一条环路，该环路中的每个进程都在等待这下一个进程所占有的资源。

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

简单来说就是，一个资源只能分给一个进程，且资源分配后不能够强行抢夺，一个进程可以不仅仅拥有一个资源，死锁发生时至少有两个进程在互相等待着对方占有的资源。

死锁建模

资源分配图：在有向图中，用圆形表示进程，用方形表示资源。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

资源分配图可以作为一种分析工具。如果其中有环路就说明有死锁，反之则没有死锁。

有四种处理死锁的策略：

忽略该问题。如果也许你忽略它，它就会忽略你。（？）
检测死锁并恢复。让死锁发生，检测它们是否发生，一旦发生死锁，采取行动解决问题
仔细对资源进行分配，动态避免死锁发生
通过破坏引起死锁的四个必要条件之一，防止死锁的发生

下面将分别讨论这四种方法。

鸵鸟算法

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测和死锁恢复

在使用这种技术时，系统并不试图阻止死锁的发生，而是允许死锁发生，当检测到死锁发生后，采用措施进行恢复。

以下将考察检测死锁的几种方法以及恢复死锁的几种方法。

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

最简单的情况，即每种资源类型只有一个资源。这样的系统可能有扫描仪、打印机，但是每种设备都不超过一个，即排除了同时有两台打印机的情况。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

如果从任何给定的结点出发的弧都被穷举了，那么就回溯到前面的节点。如果回溯到根并且不能够再深入下去，那么从当前节点出发的子图就不包含任何环。如果所有节点都是如此，那么整个图就不存在环，也就是说系统不存在死锁。

该算法对节点次序是任意的，例如我们选择R-A-B-C-S…作为访问次序。

从R开始，R->A->S, S节点没有出发的弧，所以是一条死路，所以回溯到A，回溯到R。

再选A，这次检索页很快结束了

再选B，B->T->E->V->G->U->D，然后随机选择，例如选择了S, S节点没有出发的弧，所以是一条死路,回溯到D，然后选择T，此时为：B->T->E->V->G->U->D->T。在这一节点上发现了环，算法结束。

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

上图中，有三个进程四个资源，每个数据代表的含义如下：

E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
如果没有这样一个进程，算法终止。

从死锁中恢复

假设死锁检测算法成功检测到了死锁，下一步需要一些方法是系统重新正常工作。以下将讨论各种从死锁中恢复的方法

利用抢占恢复

将不通知原进程的情况下将某一个资源强行的（使用人工方法）方法取走，并给另一个进程使用，然后再将该资源还给原来的进程。

利用回滚恢复

当了解死锁有可能发生时，就可以周期性的对进程进行检查点检查。

一旦检测到死锁，就很容易发现需要哪些资源。为了进行恢复，要从一个较早的检查点上开始，这样拥有所需要资源的进程会回滚到一个时间点，在此时间点之前该进程获得了一些其他资源。在该检查点之后所做的所有工作都丢失了。

通知杀死进程恢复

杀死一个或若干个进程。

杀死环中的一个进程
杀死环外的一个进程以释放该进程的资源

死锁避免

安全状态和不安全状态

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

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态是安全的。

安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

死锁预防

死锁避免从本质上来说是不可能的，因为它需要获知未来的请求，而这些请求是不可知的。

那么实际系统是如何避免死锁的，我们可以从死锁的四个必要条件出发。

破坏互斥条件

例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。

如果资源不被一个进程所独占，那么死锁肯定不会发生。允许两个进程同时使用打印机会造成混乱，通过采用假脱机打印机技术可以允许若干个进程同时产生输出。该模型唯一真正请求使用物理打印机的进程是打印机守护进程，由于守护进程绝不会请求别的资源，所以不会因打印机而产生死锁。

破坏占有并等待条件

禁止已经持有资源的进程在等待其他资源便可以消除死锁。

一种实现方法是规定所有进程在开始执行前请求所需的全部资源。如果所需的全部资源可用，那么就将他们分配给这个进程，于是该进程肯定能够运行结束。如果有一个或多个资源正在被使用，那么就不进行分配，进程等待。

这种方法的一个直接问题是很多进程直到运行时才知道它需要多少资源。实际上如果进程知道它需要多少资源，就可以使用银行家算法，另一个问题时这种方法的资源利用率不是最高的。

另一种方法是当一个进程请求资源时，先暂停释放其当前占用的所有资源，然后再尝试一次获得所需的全部资源。

破坏不可抢占资源

一些资源可以通过虚拟化的方式来避免发生这样的情况。假脱机打印机项磁盘输出，并且只允许打印机守护进程访问真正的物理打印机。

破坏环路等待条件

消除环路等待有几种方法

一种是保证每一个进程在任意时刻只能占用一个资源，如果要请求另外一个资源，它必须先释放第一个资源。

另一种方法是将所有资源进行统一编号，进程可以在任意时刻提出资源请求，但是所有请求必须按照资源编号的顺序（升序）提出。

其他问题

通信死锁

资源死锁是竞争性同步问题。进程在执行过程中如果与竞争的进程无交叉，便会顺利执行。进程将资源死锁，是为了防止交替访问资源而产生不一致的资源状态。交替访问加锁的资源将会可能产生死锁。

资源死锁是一种最普遍的类型，但不是唯一的一种。另一种死锁发生在通信过程中，即两个或两个以上的进程利用发送信息来通信时。一种普遍的情形是进程A向进程B发送请求信息，然后阻塞直至B回复。假设请求信息丢失，A将阻塞以等待回复，而B会阻塞等待一个向其发送命令的请求，因此发生死锁。我们把上面这种情况称为通信死锁，通信死锁是协同死锁的异常情况。

用于中断通信死锁的技术称为超时；在大多数网络通信系统中，只要一个信息被发送到一个特定的地方，并等待其返回一个特定的回复，发送者就同时启动计时器。若计时器在回复到达前计时就停止了，则信息的发送者可以认定信息已经丢失了，并重新发送。

活锁

在某些情况下，当进程意识到它不能够获取所需要的下一个锁时，就会尝试礼貌的释放已经获得的锁，然后等待1ms，在尝试一次。

从理论上来说，这是用来检测并预防死锁的号方法。但是，如果另一个进程在相同的时刻做了相同的操作，那么就像两个人在一条路上相遇并同时给对方让路，相同的步调将导致双方都无法前进。这种情况可以称之为活锁

参考

https://github.com/CyC2018/CS-Notes

现代操作系统（第4版）