用户态到内核态的切换发生了什么
1.读取tr寄存器，访问TSS段
TSS段保存内核栈信息
2.从TSS段中的sp0获取进程内核栈的栈顶指针
sp：堆栈指针(Stack Pointer)寄存器，用它只可访问栈顶。
3.在内核栈中保存当前cs,ss,eip,esp寄存器的值（地址）
cs 为代码段寄存器
ss 为栈段寄存器，一般作为栈使用
eip:用来存储CPU要读取指令的地址，CPU通过EIP寄存器读取即将要执行的指令
esp:用户栈栈顶指针
4.把内核代码选择符写入CS寄存器，内核栈指针写入ESP寄存器，把内核入口点的线性地址写入EIP寄存器
此时，CPU已经切换到内核态，根据EIP中的值开始执行内核入口点的第一条指令。
https://blog.csdn.net/Agoni_xiao/article/details/79034290
1.设备发出中断信号
2.硬件保存现场
3.根据中断码查表
4.把中断处理程序的入口地址推送到相应的寄存器
5.执行中断处理程序
https://www.cnblogs.com/shengge/archive/2011/08/29/2158748.html
1.进程的堆栈
内核在创建进程的时候，在创建task_struct的同事，会为进程创建相应的堆栈。每个进程会有两个栈，一个用户栈，存在于用户空间，一个内核栈，存在于内核空间。当进程在用户空间运行时，cpu堆栈指针寄存器里面的内容是用户堆栈地址，使用用户栈；当进程在内核空间时，cpu堆栈指针寄存器里面的内容是内核栈空间地址，使用内核栈。
2.进程用户栈和内核栈的切换
当进程因为中断或者系统调用而陷入内核态之行时，进程所使用的堆栈也要从用户栈转到内核栈。
进程陷入内核态后，先把用户态堆栈的地址保存在内核栈之中，然后设置堆栈指针寄存器的内容为内核栈的地址，这样就完成了用户栈向内核栈的转换；当进程从内核态恢复到用户态之行时，在内核态之行的最后将保存在内核栈里面的用户栈的地址恢复到堆栈指针寄存器即可。这样就实现了内核栈和用户栈的互转。
那么，我们知道从内核转到用户态时用户栈的地址是在陷入内核的时候保存在内核栈里面的，但是在陷入内核的时候，我们是如何知道内核栈的地址的呢？
关键在进程从用户态转到内核态的时候，进程的内核栈总是空的。这是因为，当进程在用户态运行时，使用的是用户栈，当进程陷入到内核态时，内核栈保存进程在内核态运行的相关信息，但是一旦进程返回到用户态后，内核栈中保存的信息无效，会全部恢复，因此每次进程从用户态陷入内核的时候得到的内核栈都是空的。所以在进程陷入内核的时候，直接把内核栈的栈顶地址给堆栈指针寄存器就可以了。
中断分类
外中断
由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
异常
由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。
陷入
在用户程序中使用系统调用。
异常：异常是由当前正在执行的进程产生。异常包括很多方面，有出错（fault），有陷入（trap），也有可编程异常（programmable exception）。
出错（fault）和陷入（trap）最重要的一点区别是他们发生时所保存的EIP值的不同。出错（fault）保存的EIP指向触发异常的那条指令；而陷入（trap）保存的EIP指向触发异常的那条指令的下一条指令。因此，当从异常返回时，出错（fault）会重新执行那条指令；而陷入（trap）就不会重新执行。这一点实际上也是相当重要的，比如我们熟悉的缺页异常（page fault），由于是fault，所以当缺页异常处理完成之后，还会去尝试重新执行那条触发异常的指令（那时多半情况是不再缺页）。陷入的最主要的应用是在调试中，被调试的进程遇到你设置的断点，会停下来等待你的处理，等到你让其重新执行了，它当然不会再去执行已经执行过的断点指令。
软中断和硬中断
硬中断：
中断：
中断指当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。
硬中断
硬件中断是一个异步信号, 表明需要注意, 或需要改变在执行一个同步事件.
硬件中断是由与系统相连的外设(比如网卡 硬盘 键盘等)自动产生的. 每个设备或设备集都有他自己的IRQ(中断请求), 基于IRQ, CPU可以将相应的请求分发到相应的硬件驱动上(注: 硬件驱动通常是内核中的一个子程序, 而不是一个独立的进程). 比如当网卡受到一个数据包的时候, 就会发出一个中断.
处理中断的驱动是需要运行在CPU上的, 因此, 当中断产生时, CPU会暂时停止当前程序的程序转而执行中断请求. 一个中断只能中断一颗CPU(也有一种特殊情况, 就是在大型主机上是有硬件通道的, 它可以在没有主CPU的支持下, 同时处理多个中断).
硬件中断可以直接中断CPU. 它会引起内核中相关代码被触发. 对于那些需要花费时间去处理的进程, 中断代码本身也可以被其他的硬件中断中断.
对于时钟中断, 内核调度代码会将当前正在运行的代码挂起, 从而让其他代码来运行. 它的存在时为了让调度代码(或称为调度器)可以调度多任务.
软中断
软中断的处理类似于硬中断. 但是软中断仅仅由当前运行的进程产生.
通常软中断是对一些I/O的请求.
软中断仅与内核相联系, 而内核主要负责对需要运行的任何其他进程进行调度.
软中断不会直接中断CPU, 也只有当前正在运行的代码(或进程)才会产生软中断. 软中断是一种需要内核为正在运行的进程去做一些事情(通常为I/O)的请求.
有一个特殊的软中断是Yield调用, 它的作用是请求内核调度器去查看是否有一些其他的进程可以运行.
硬件中断和软中断的区别
硬件中断是由外设引发的, 软中断是执行中断指令产生的.
硬件中断的中断号是由中断控制器提供的, 软中断的中断号由指令直接指出, 无需使用中断控制器.
硬件中断是可屏蔽的, 软中断不可屏蔽.（硬中断是外设引发的，通过设置状态寄存器的IF位可以屏蔽硬中断。而软中断是由指令调用的，因此不可屏蔽）
硬件中断处理程序要确保它能快速地完成任务, 这样程序执行时才不会等待较长时间, 称为上半部.
软中断处理硬中断未完成的工作, 是一种推后执行的机制, 属于下半部.
————————————————
进程和线程的区别：
进程拥有两个基本的属性：资源的拥有者和独立调度单位。
进程是资源分配和独立运行的基本单位，每一个进程都完成一个特定的任务。
线程的引入进一步提高了程序并发执行的程度，从而进一步提高了资源的利用率和系统的吞吐量。引入线程目的是减少并发执行时的时空开销。因为进程的创建、撤销、切换较费时空，它既是调度单位，又是资源拥有者。线程是系统独立调度和分派的基本单位，基本上不拥有系统资源，只需要少量的资源(指令指针IP，寄存器，栈)，但可以共享其所属进程所拥有的全部资源。
一个进程可以创建一个或多个线程；一个线程可以创建一个或多个线程；一个进程可以创建一个或多个进程；但是线程不可以创建进程。
进程与线程的比较：
（1）引入线程后，线程是处理机(CPU)=调度的基本单位，进程是资源分配的基本单位，而不再是一个可执行的实体。在同一进程中线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时。将会引起进程的切换。
（2）引入线程后，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行。多个线程会争夺处理机，在不同的状态之间进行转换。线程也是一个动态的概念，也有一个从创建到消亡的生命过程，具有动态性。
（3）进程是资源分配的单位，一般线程自己不拥有系统资源，但可以访问其隶属进程的资源。同一进程中的所有线程都具有相同的地址空间（进程的地址空间）。
（4）同进程的不同线程间的独立性要比不同进程间的独立性低得多。多个线程共享进程的内存地址空间和资源。
（5）创建、撤销一个新线程系统开销小。两个线程间的切换系统开销小。
（6）同进程的不同线程可以分配到多个处理机上执行，加快了进程的完成。
线程共享的资源包括：
（1） 进程代码段
（2） 进程的公有数据（利用这些数据，线程很容易实现相互之间的通讯）
（3） 进程的所拥有资源。
线程独立的资源包括：
（1）线程ID：每个线程都有自己唯一的ID，用于区分不同的线程。
（2）寄存器组的值：当线程切换时，必须将原有的线程的寄存器集合的状态保存，以便重新切换时得以恢复。
（3）线程的堆栈：堆栈是保证线程独立运行所必须的。
（4）错误返回码：由于同一个进程中有很多个线程同时运行，可能某个线程进行系统调用后设置了error值，而在该线程还没有处理这个错误，另外一个线程就在此时被调度器投入运行，这样错误值就有可能被修改。所以，不同的线程应该拥有自己的错误返回码变量。
（5）线程优先级：线程调度的次序（并不是优先级大的一定会先执行，优先级大只是最先执行的机会大）。
区别：
Ⅰ 拥有资源
进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
Ⅱ 调度
线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
Ⅲ 系统开销
由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
Ⅳ 通信方面
线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。
进程状态的切换
就绪状态（ready）：等待被调度
运行状态（running）
阻塞状态（waiting）：等待资源
只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 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. 实时系统
实时系统要求一个请求在一个确定时间内得到响应。（比如CD播放器的计算机要求短时间内将流转换为音乐，正确的但迟到的应答比没有更糟糕。）
分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。
经典同步问题
生产者消费者问题：
两个信号量empty和full,一个锁mutex
empty+full保持在N，N就是任务总数。
mutex用于对队列拿/取进行保护。
对于生产者来说，当它准备放入时，首先对empty进行down,如果失败说明无空位，只有等待消费者那边up了才能进行。
当成功后，首先对队列进行放入，放入后对full进行up，这个代表多了一个产品可以消费。
对于消费者来说，当他准备消费的时候，首先对full进行down,如果失败说明无产品，只有等待生产者up了才能进行。
当成功后，首先对队列进行拿，拿后对empty进行up，这个代表多了一个产品空位。
注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。
读者-写者问题
一个count统计临界区里的读者数量
一个data_mutex用于对数据区加锁，一个count_mutex用于对count加锁
对于读者：
首先对count加锁，因为count也是公共资源。
然后判断count的大小，如果为1说明为第一个读者，这代表里面没有其他读者，尝试对data_mutex加锁，如果有写者在里面，则阻塞在此处，其他的读者进来时由于count未释放，也被阻塞。
如果没有写者，则进入，并对data_mutex加锁，此后只要有一个读者在里面，写者就无法进入。
当结束读时，对count判断，如果为0，说明最后一个读者要出去了，这个时候释放data_mutex，让写者可以进入。
对于写者：
只要判断data_mutex的状态就可以了，加锁时阻塞，不加锁时进入并开写。
哲学家进餐问题
N个信号量，每个哲学家一个。N个信号量均初始化为0.
mutex用于保护哲学家改变状态和尝试拿筷子
test是尝试拿起左右的筷子，如果左右都不为EATING，则可以拿起，否则函数返回，并在下面的down阻塞住，直到左边的哲学家通过test(RIGHT)再重新使这个被阻塞的哲学家尝试在拿一次筷子（因为左边的哲学家已经放下来了）
test尝试拿起筷子，但条件是自己为Hungry且左右均不为EATING时才能拿起。如果没有拿起，则不会对这个哲学家的信号量进行up,此时信号量仍然为0，出来后被down阻塞住。此时这个哲学家的尝试拿起筷子的过程已经结束了。如果旁边的哲学家吃完了，在put筷子的过程中会test(LEFT)和 test(RIGHT)，这相当于让左边（也就是前面未拿起筷子的哲学家再拿一次筷子，因为旁边的哲学家阻塞住了，它的拿筷子过程已经结束了，现在是通过这个放筷子的过程来让左边的哲学家拿筷子。）拿筷子，如果能拿起，则up，相当于让原来阻塞的哲学家拿起了筷子，且唤醒，此时这个阻塞的哲学家信号量为0.
put_two是用于放下筷子，首先改变当前哲学家的状态，即代表放下了左右的筷子，然后test(LEFT)和test(RIGHT)让左右两边的哲学家重新尝试试着拿起筷子，比如test(LEFT)，此时left这个哲学家应该是在down处阻塞了，test(left)让他重新试着拿筷子，如果拿起来，进入if，唤醒他；如果不能，test(LEFT)不作任何工作而返回，左边哲学家继续阻塞
进程通信
进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。
1. 管道
#include <unistd.h>
int pipe(int fd[2]);
它具有以下限制：
1)它是半双工的，具有固定的读端和写端
2)它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）
3)它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中
管道是用环形队列实现的，数据从写端流入从读端流出，这样就实现了进程间通信。
先创建管道，然后再fork后即可在父子进程间创建管道。如果需要父向子写，则关闭父的读和子的写；如果子向父写，则关闭子的读和父的写。
2. FIFO
也称为命名管道，去除了管道只能在父子进程中使用的限制。
#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);
1)FIFO可以在无关的进程之间交换数据
2)FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
当以只读open一个FIFO时，会阻塞到出现某个进程以写而open这个FIFO为止，同样，以只写open一个FIFO将阻塞到某个进程以只读打开他为止。如果FIFO设置了O_NONBLOCK，则只读OPEN立即返回，如果没有进程为读而打开FIFO，则只写OPEN将返回-1，也就是说只有对一个FIFO同时存在读和写的进程时，才能在进程间进行通信。
FIFO的通信方式类似于在进程中使用文件类传输数据，只不过FIFO类型的文件同时具有管道的特性，在数据读出时，FIFO中同时清除了数据。
类似于管道，若写一个尚无进程为读而打开的FIFO，将产生信号SIGPIPE，若某个FIFO的最后一个写进程关闭了该FIFO，则将为该FIFO的读进程将产生一个文件结束标志。
3. 消息队列
相比于 FIFO，消息队列具有以下优点：
消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭（相当于一个文件）时可能产生的困难；
避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法（是异步的，而FIFO当写端没写会陷入阻塞）；
读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。
4. 信号量
它是一个计数器，用于为多个进程提供对共享数据对象的访问。
5. 共享存储
允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。
需要使用信号量用来同步对共享存储的访问。
多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。
6. 套接字
与其它通信机制不同的是，它可用于不同机器间的进程通信。
进程同步
进程同步的四种方法
1、临界区（Critical Section）:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
优点：保证在某一时刻只有一个线程能访问数据的简便办法
缺点：虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。
2、互斥量（Mutex）:为协调共同对一个共享资源的单独访问而设计的。
互斥量跟临界区很相似，比临界区复杂，互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权限。
优点：使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。
缺点：
①互斥量是可以命名的，也就是说它可以跨越进程使用，所以创建互斥量需要的资源更多，所以如果只为了在进程内部使用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。
②通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号量对象可以说是一种资源计数器。
3、信号量（Semaphore）:为控制一个具有有限数量用户资源而设计。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。互斥量是信号量的一种特殊情况，当信号量的最大资源数=1就是互斥量了。
优点：适用于对Socket（套接字）程序中线程的同步。（例如，网络上的HTTP服务器要对同一时间内访问同一页面的用户数加以限制，只有不大于设定的最大用户数目的线程能够进行访问，而其他的访问企图则被挂起，只有在有用户退出对此页面的访问后才有可能进入。）
缺点：
①信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点；
②信号量机制功能强大，但使用时对信号量的操作分散， 而且难以控制，读写和维护都很困难，加重了程序员的编码负担；
③核心操作P-V分散在各用户程序的代码中，不易控制和管理，一旦错误，后果严重，且不易发现和纠正。
4、事件（Event）: 用来通知线程有一些事件已发生，从而启动后继任务的开始。
优点：事件对象通过通知操作的方式来保持线程的同步，并且可以实现不同进程中的线程同步操作。
总结：
①临界区不是内核对象，只能用于进程内部的线程同步，是用户方式的同步。互斥、信号量是内核对象可以用于不同进程之间的线程同步（跨进程同步）。
②互斥其实是信号量的一种特殊形式。互斥可以保证在某一时刻只有一个线程可以拥有临界资源。信号量可以保证在某一时刻有指定数目的线程可以拥有临界资源。
----------------------------------
死锁
必要条件
互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
占有和等待：已经得到了某个资源的进程可以再请求新的资源。
不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
处理方法
主要有以下四种方法：
鸵鸟策略
死锁检测与死锁恢复
死锁预防
死锁避免
鸵鸟策略
把头埋在沙子里，假装根本没发生问题。
因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。
当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。
大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。
死锁检测与死锁恢复
不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。
死锁检测
1. 每种类型一个资源的死锁检测
上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。
图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
检测有向图是否存在环：
1).DFS:
从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环
2).拓扑排序：
方法是重复寻找一个入度为0的顶点，将该顶点从图中删除（即放进一个队列里存着，这个队列的顺序就是最后的拓扑排序，具体见程序），并将该结点及其所有的出边从图中删除（即该结点指向的结点的入度减1），最终若图中全为入度为1的点，则这些点至少组成一个回路。
2. 每种类型多个资源的死锁检测
上图中，有三个进程四个资源，每个数据代表的含义如下：
E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量
进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。
算法总结如下：
每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。（标记代表不会死锁）
1. 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
2. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1（相当于释放了已占用的资源）。
3. 如果没有这样一个进程，算法终止。
死锁恢复
利用抢占恢复
利用回滚恢复
通过杀死进程恢复
死锁预防
在程序运行之前预防发生死锁（与死锁的避免的区别在于程序运行的时间）
1. 破坏互斥条件
例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
2. 破坏占有和等待条件
一种实现方式是规定所有进程在开始执行前请求所需要的全部资源（这样在运行时不会去请求其他的资源，因为所有所需资源已得到）。
3. 破坏不可抢占条件
即当进程新的资源未得到满足时，释放已占有的资源，从而破坏不可剥夺的条件
4. 破坏环路等待
给资源统一编号，进程只能按编号顺序来请求资源。
死锁避免
在程序运行时避免发生死锁。
与死锁预防的区别在于这个是运行时进行的。
与死锁的检测的区别是，死锁的检测是在死锁已经发生后，检测了并通过抢占或杀死或回滚的方式恢复，而避免是在分配资源时，如果会进入死锁则拒绝分配。
1.单个资源的银行家算法
一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。
2.多个资源的银行家算法
图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4个资源分别还剩下 1/0/2/0。
检查一个状态是否安全的算法如下：
查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行（全都大于A），那么系统将会发生死锁，状态是不安全的。
假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
重复以上两步，直到所有进程都标记为终止，则状态是安全的。
如果一个状态不是安全的，需要拒绝进入这个状态。
内存管理
虚拟内存
虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令（中断中的异常）。
从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序（不用全部加载进内存）。
分页系统地址映射
内存管理单元（MMU）管理着地址空间和物理内存的转换（硬件来做映射），其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。
一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。
下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1
表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 （110 000000000100）。
这里的110 1是根据0010定位到的页表中的内容，也就是说先看虚拟地址前4位，为0010，定位到页表2，也就是第三项，页表中该项内容为110 1，前三位与后12位拼接，最后一个1表示是否在内存中。
这里是16位系统，可以寻址到64K的内存，然后分成16个页，平均一页4K大小。
页面置换算法在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。
1. 最佳
所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。
是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。
与LRU的区别在于，它是未来最久不会被访问的，但它现在的位置可能不是像LRU的链表尾，可能这个页面上一秒刚被访问过，但它在未来都不会被访问。而在LRU里这个页面是不可能被淘汰的。
2. 最近最久未使用（LRU, Least Recently Used）
为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
3. 最近未使用
NRU, Not Recently Used
每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：
第一类：R=0，M=0
第二类：R=0，M=1
第三类：R=1，M=0（优于R=0,M=1）
第四类：R=1，M=1
第二类看似不可能，一个页面不可能被修改了却未被访问，但它可以通过第四类的R位被定时清0得到。
当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。
NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
4. 先进先出
FIFO, First In First Out
选择换出的页面是最先进入的页面（也就是最老的页面）。
该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。
5. 第二次机会算法（改进FIFO）
FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
6. 时钟
Clock
第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。
当指向的页面R=0，则换出去，并将指针前移。如果R=1，则置R=0，同时指针前移。
分段
虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。
下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现（因为只有分页，当当前页满时会往相邻的页上写）。
分段的做法是把每个表对应一个段（一个表对应一个段），一个段构成一个独立的地址空间（一个独立的地址空间指从地址从0开始）,下图就是不同的段，每个段的逻辑意义不同。有共享与保护。
每个段的长度可以不同，并且可以动态增长。
段是二维的，首先给出段名（每个段都是独立的地址空间），然后给出段内偏移。
而页是一维的，给出地址就可以找出位置。
分段的问题在于外部碎片，比如一个10大小的段，现在这个段不用了，换了1个7K的段，则有3K的段成为碎片，除非刚好可以有一个3K的段可以用。
而采用分页系统不会产生外部碎片（但内部碎片一定会有）
段页式
程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
-----------------------------------------------------------
分页与分段的比较
对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
地址空间的维度：分页是一维地址空间，分段是二维的。
大小是否可以改变：页的大小不可变，段的大小可以动态改变。
出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
分页和分段的区别
1.目的
页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页是出于系统管理的需要而不是用户需要。
段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了更好地满足用户的需要。
2.长度
页的大小固定而且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面。
段的长度不固定，决定于用户所编写的程序，通常由编译程序在对程序进行编译时，根据信息的性质来划分。
3.地址空间
页的地址空间是一维的，即单一的线形地址空间，程序员只要利用一个记忆符就可以表示一个地址。
作业地址空间是二维的，程序员在标识一个地址时，既需要给出段名，又需给出段内地址（相当于一个进程有多个地址空间，用段名来定位在哪个地址空间，用偏移定位到对应的位置）。
4.碎片
分页有内部碎片无外部碎片
分段有外部碎片无内部碎片
5.绝对地址
处理器使用页号和偏移量计算绝对地址
处理器使用段号和偏移量计算绝对地址
6.管理方式
对于分页，操作系统必须为每个进程维护一个页表，以说明每个页对应的的页框。当进程运行时，它的所有页都必须在内存中（只是单纯把空间分成固定大小的页而没有使用虚拟技术），除非使用覆盖技术或虚拟技术，另外操作系统需要维护一个空闲页框列表。
对于分段，操作系统必须为每个进程维护一个段表，以说明每个段的加载地址和长度。当进程运行时，它的所有段都必须在内存中，除非使用覆盖技术或虚拟技术，另外操作系统需要维护一个内存中的空闲的空洞列表。
特别的，当使用虚拟技术是，把一页或一段写入内存时可能需要把一页或几个段写入磁盘。
7.共享和动态链接
分页不容易实现，分段容易实现
链接
预处理阶段：处理以 # 开头的预处理命令；
编译阶段：翻译成汇编文件；
汇编阶段：将汇编文件翻译成可重定位目标文件；
链接阶段：将可重定位目标文件和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。
静态链接
静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：
符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。
重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。
目标文件
可执行目标文件：可以直接在内存中执行；
可重定位目标文件：可与其它可重定位目标文件在链接阶段合并，创建一个可执行目标文件；
共享目标文件：这是一种特殊的可重定位目标文件，可以在运行时被动态加载进内存并链接；
动态链接
静态库有以下两个问题：
当静态库更新时那么整个程序都要重新进行链接；
对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。
共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。它具有以下特点：
在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；
在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。
