进程管理
进程与线程
进程
进程是资源分配的基本单位。
线程
线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程资源。
区别
拥有资源
进程是资源分配的基本单元，但线程不拥有资源，线程可以访问隶属于进程的资源。
调度
线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
系统开销
由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等，所付出的开销远大于创建或撤销线程时的开销。在进行进程切换时，涉及当前执行进程CPU环境的保存及新调度进程CPU环境的设置，而线程切换时只需要保存和设置少量寄存器内容，开销很小。
通信方面
线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助IPC。
进程状态的切换
- created：创建
- ready：就绪状态
- running：运行状态
- waiting：阻塞状态
- terminated：终止状态
只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法获得CPU时间，转为运行状态；运行状态的进程，用完CPU时间片之后转为就绪状态，等待CPU调度。
阻塞状态是缺少需要资源从而由运行状态转换而来，但该资源不包括CPU时间。
进程调度算法
不同环境的调度算法目标并不同，因此需要针对不同环境来讨论调度算法。
批处理系统
批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间。
先来先服务(First-come first-serverd, FCFS)
非抢占式的调度算法，按照请求的顺序进行调度。
有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完才能执行，而长作业需要执行很长时间，造成了短作业等待时间过长。
短作业优先(shortest job first, SJF)
非抢占式的调度算法，按估计运算时间最短的顺序进行调度。
长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
最短剩余时间优先(shortest remaining time next, SRTN)
最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前线程，运行新的进程。否则新的进程等待。
交互式系统
交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。
时间片轮转
将所有就绪进程按FCFS的原则排成一个队列，每次调度时，把CPU时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把CPU时间片分配给队首的进程。
时间片轮转算法的效率和时间片的大小有很大关系：
- 因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
- 而如果时间片过长，那么实时性就不能得到保证。
优先级调度
为每个进程分配一个优先级，按优先级进行调度。
为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
多级反馈队列
一个进程需要执行100个时间片，如果采用时间片轮转调度算法，那么需要交换100次。
多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如1，2，4，8。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换7次。
每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进行进程在排队，才能调度当前队列上的进程。
可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。
实时系统
实时系统要求一个请求在一个确定的时间内得到响应。
进程同步
临界区
对临界资源进行访问的那段代码称为临界区。
为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。
同步互斥
- 同步：多个进程因为合作产生直接制约关系，使得进程有一定的先后执行关系。
- 互斥：多个进程在同一时刻只有一个进程能进入临界区。
信号量
信号量(Semaphore)是一个整型变量，可以对其执行down和up操作，也就是常见的P和V操作。
- down：如果信号量大于0，执行-1操作；如果信号量等于0，进程睡眠，等待信号量大于0；
- up：对信号量执行+1操作，唤醒睡眠的进程让其完成down操作。
down和up操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。
如果信号量取值只能为0或者1，那么就成为了互斥量(Mutex)，0表示临界区已经加锁，1表示临界区解锁。
管程
管程在功能上和信号量及PV操作类似，属于一种进程同步互斥工具。但是具有与信号量及PV操作不同的属性。
管程有一个重要的特性：在一时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其他进程永远不能使用管程。
管程引入了条件变量以及相关的操作：wait()和signal()来实现同步操作。对条件变量执行wait()操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal()操作用于唤醒被阻塞的进程。
进程通信
进程同步与进程通信很容易混淆，它们的区别在于：
- 进程同步：控制多个进程按一定顺序执行；
- 进程通信：进程间传输信息。
进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。
管道
管道是通过调用pipe函数创建的。
它的限制：
- 只支持半双工通信(单向交替传输)；
- 只能在父子进程或兄弟进程中使用。
FIFO
也称为命名管道，去除了管道只能在父子进程中使用的限制。
FIFO常用于客户-服务器应用程序中，FIFO用作汇聚点，在客户进程和服务器进程之间传递数据。
消息队列
相比于FIFO，消息队列具有以下优点：
- 消息队列可以独立于读写进程存在，从而避免了FIFO中同步管道的打开和关闭时可能产生的困难；
- 避免了FIFO的同步阻塞问题，不需要进程自己提供同步方法；
- 读进程可以根据消息类型有选择地接收消息，而不像FIFO那样只能默认地接收。
信号量
它是一个计数器，用于为多个进程提供对共享数据对象的访问。
共享存储
允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种IPC。
需要使用信号量用来同步对共享存储的访问。
多个进程可以将同一个文件映射到它们的地址存储空间从而实现共享内存。另外XSL共享内存不是使用文件，而是使用内存的匿名段。
套接字
与其他通信机制不同的是，它可用于不同机器间的进程通信。
死锁
必要条件
- 互斥：每个资源要么已经分配给了一个进程，要么就是可用的
- 占有和等待：已经得到了某个资源的进程可以再请求新的资源
- 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显示地释放。
- 环路等待：有两个或两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
处理方法
鸵鸟策略
把头埋在沙子里，假装根本没有发生问题。
因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。
当发生死锁时不会对用户造成多大影响，或者发生死锁的概率很低，可以采用鸵鸟策略。
大多数操作系统，处理死锁问题的办法仅仅是忽略它。
死锁检测与死锁恢复
不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。
每种类型一个资源的死锁检测
资源指向进程表示资源已经分配给该进程，进程指向资源表示进程请求获取该资源。
若满足了环路等待条件，因此会发生死锁。
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
每种类型多个资源的死锁检测
$E=(4,2,3,1),A=(2,1,0,0),$
- E向量：资源总量
- A向量：资源剩余量
- C矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
- R矩阵：每个进程请求的资源数量
进程$P_1$和$P_2$所请求的资源都得不到满足，只有进程$P_3$执行，之后释放$P_3$所拥有的资源，此时$A=(2,2,2,0)$。$P_2$可以执行，执行后释放$P_2$拥有的资源，$A=(4,2,2,1)$。$P_1$也可以执行。所有进程都可以顺利执行，没有死锁。
算法总结如下：
每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。
- (1)寻找一个没有标记的进程$P_i$，它所请求的资源小于等于$A$。
- (2)如果找到了这样一个进程，那么将$C$矩阵的第$i$行向量加到$A$中，标记该进程，并转回(1)
- (3)如果没有这样一个进程，算法终止。
死锁恢复
- 利用抢占恢复
- 利用回滚恢复
- 通过杀死进程恢复
死锁预防
在程序运行之前预防发生死锁。
- 破坏互斥条件
- 破坏占有和等待条件：一种实现方式是规定所有进程在开始执行前请求所有需要的全部资源
- 破坏不可抢占条件
- 破坏环路等待：给资源统一编号，进程只能按编号顺序来请求资源
死锁避免
在程序运行时避免发生死锁。
安全状态
定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。
单个资源的银行家算法
算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。
多个资源的银行家算法
