成也进程，败也进程，不为成败，只为进程。

进程的描述与控制

前驱图

每个结点可用来表示一个进程或进程段，乃至一条语句，结点间的有向边则表示两个结点间存在偏序或前趋关系。

例如上图P1与P2之间有前趋关系，所以P1与P2只能顺序执行。再如P2与P3之间没有前趋关系，所以P2与P3可以并发执行。

说白了就是有向无环图，可以利用拓扑排序进行执行。

进程概述

简单理解，进程就是程序段+数据段+PCB。

由来

由于多道程序环境下，程序的执行属于并发执行，此时它们将失去封闭性，并且具有间断性，以及运行结果不可在现性的特征。由此决定了程序是不能参与并发执行的，否则，程序的运行便失去了意义。为了能使程序并发执行，并且对并发执行的程序加以描述和控制，人们引入了进程。

为使每个并发执行程序（含数据）都能独立运行，在操作系统中加入一个专门的数据结构——进程控制块（Process Control Block，PCB）

系统利用PCB描述进程的基本情况和活动过程。一般情况下，我们把进程实体简称为进程，所谓创建进程就是创建进程实体中的PCB；撤销进程就是撤销进程的PCB。

定义

进程是程序的一次执行。
进程是一个程序及其数据在处理机尚顺序执行是所发生的活动。
进程是具有独立功能的程序在一个数据集合上执行的过程，它是系统执行资源分配和调度的一个独立单位。

特征

动态性：进程是进程实体的执行过程，由创建而生，调度而执行，撤销而亡。进程实体具有生命周期，而程序仅是一组有序命令的集合，存在于某种介质之上，因而是静态的。
并发性：多个进程实体同存于内存之中，且能在一段时间同时运行。程序没有PCB，因而不能并发。
独立性：进程实体是一个能独立运行，独立获得资源，独立接受调度的基本单位。而程序没有PCB，固不能执行以上操作。
异步性：进程是按异步方式运行的，即按各自独立的、不可预知的速度推进，因而结果不可再现。为此，OS中引入进程的概念，并配置相应的同步机制。

状态及转换

三基态：

就绪状态：进程已处于准备好运行的状态，只差CPU，在就绪队列等待调度。
执行状态：进程已获得CPU，并立即执行。
阻塞状态：正在运行的进程由于发生某种事件（I/O请求，申请缓冲区失败等）暂时无法继续执行，而让受阻进程处于暂停状态。进入阻塞队列。阻塞时进程自身的主动行为。

创建与终止状态：

创建状态：申请空白PCB，并向PCB填写控制和管理进程的信息，然后分配资源，最后转入就绪队列中。
终止状态：等待操作系统善后处理，然后PCB清零，返还系统。

挂起状态：

当操作作用于某个进程时，该进程处于静止状态。

引入

终端用户需要。例如运行时改bug。
父进程请求。
符合调节需要。
操作系统需要。例如检查运行情况。

PCB

PCB中的信息

进程描述符：进程标识符用于唯一标识进程。
处理机状态：进程切换时保留现场以及现场恢复。
进程调度信息：进程状态及相关进程调度信息。
进程控制信息：用于进程控制所需信息。

进程控制

进程控制一般由OS原语实现。

操作系统内核

支撑功能
- 中断处理。
- 始终处理。
- 原语操作。原语由若干指令组成，用于完成一定功能的过程。原子操作，一个操作中所有行动要么全做，要么不做。
资源管理功能
- 进程管理。
- 存储器管理。
- 设备管理。

进程的创建与终止

创建原语：Creat

终止原语：Holt

进程的阻塞与唤醒

阻塞原语：block

唤醒原语：wakeup

进程的挂起与激活

挂起原语：suspend

激活原语：active

进程同步

硬件同步机制

关中断
利用Test-and-Set指令实现互斥
利用Swap指令实现进程互斥

信号量

整型信号量
记录型信号量
AND型信号量
信号量集

管程

信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难。因此后来又提出了一种集中式同步进程——管程。其基本思想是将共享变量和对它们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰，便于维护和修改，易于保证正确性。

经典进程同步问题

生产者-消费者问题

读者-写者问题

哲学家进餐问题

进程间通信

共享存储器系统
管道（pipe）通信系统
消息传递系统
- 消息传递的实际功能以一对原语的形式提供：
  - send(destination,message)
  - receive(source,message)
  这是进程间进程消息传递所需要的最小操作集。
  
  一个进程以消息的形式给另一个指定的目标进程发送消息；
  
  进程通过执行receive原语接收消息，receive原语中指明发送消息的源进程和消息。
客户机-服务机系统
- 套接字socket

线程

作为调度和分派的基本单位。

每个线程有一个线程控制块TCB。

处理机调度与死锁

处理机调度

无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。

处理机调度层次

高级、中级和低级调度作业从提交开始直到完成，往往要经历下述三级调度：

高级调度：(High-Level Scheduling)又称为作业调度，它决定把外存上后备作业调入内存运行；

低级调度：(Low-Level Scheduling)又称为进程调度，它决定把就绪队列的某进程获得CPU；

中级调度：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换。把不能正常运行的进程调至外存等待。

处理机调度算法

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

批处理系统

周转时间Ti = 完成时间 - 到达时间

平均周转时间T = 1/n( T1 + …… + Ti + …… + Tn )

带权周转时间为周转时间/运行时间（越小越好）

分时系统

响应时间快，均衡性好。

实时系统

考虑截至时间，提高可预测性。

作业与作业调度

作业（Job）

程序的集合+数据的集合+作业说明书+JCB。

三个状态：后备状态，运行状态，收容状态。

三个阶段：收容阶段（创建JCB），运行阶段，完成阶段（回收JCB）。

任务

接纳多少作业
接纳哪些作业

作业调度算法

先来先服务算法（first-come first-served，FCFS）

系统按照作业到达的优先顺序调度。

不利于短作业。

短作业优先算法（short job first，SJF）

系统以作业长短为优先级。

不利于长作业，容易出现进程饥饿现象。

优先级调度算法（priority-scheduling algorithm，PSA）

根据作业紧迫程度，由外界赋予优先级。

高响应比有限调度算法（Highest Rseponse Ratio Next，HRRN）

动态优先级，根据长短赋初值，根据等待时间加权。作业越短，初值越大，等待时间越长，加权越大。

Rp = 响应时间/要求服务时间

进程调度

方式

剥夺方式

当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。

非剥夺方式

分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。

任务

保存处理机现场信息。
按某种算法选取进程。
把处理器分配给进程。

进程调度算法

进程调度也称为低级调度，它所调度的对象为进程（或者内核级线程），而进程调度算法主要有以下几种：

基于时间片的轮转调度算法

它的原理通俗来讲就是队列中每一个进程都获得了一定的执行时间，从几ms到几百ms，当一个执行时间结束，计时器会发出一个信号，此时正在执行的进程将被中断，同时此进程将被放在队列的末尾，然后执行这时候的队列的队首进程，因此队列中每一个进程都将获得一定时间执行。

先来先服务调度算法（FCFS）

先来先服务调度算法是一种最简单的调度算法，可用于作业调度，也可用于进程调度。

短作业优先调度算法（SJ(P)F）

短作业（进程）优先调度算法是指短作业或者短进程的优先调度算法，它们分别作用于作业调度和进程调度，它是先来先服务调度算法的一种优化版本。

高优先权优先调度算法

为了解决在短作业优先调度算法中进程的紧迫程度问题，我们引入高优先权优先调度算法，高优先权调度算法的方法也很简单，就是在队列中选取优先权最高的进程装入内存，该算法又分为以下两类：

①非抢占式优先权算法
如果系统已经分配好一个优先权最高的进程，它会一直被执行，直到结束或者因为某事件放弃执行，此时系统才会选择另外一个优先权最高的进程，这种调度算法主要被用于批处理系统中。

②抢占式优先权算法
系统在队列中把一个优先权最高的进程执行，但如果在执行中又出现一个优先权更高的进程，此时当前进程被停止，换入另外一个优先权更高的进程，这种调度算法主要被用于要求比较严格的实时系统，以及对性能要求较高的批处理和分时系统中。

优先权的类型：

优先权的类型被分为静态优先权和动态优先权。

静态优先权就是给定某个整形数字来表示进程的优先级，数字越小表示优先级越高，数字越大，进程优先级越低。

动态优先权随着进程的创建而被创建，可以随着进程的推进或者等待时间而变化。

多队列调度算法

进程就绪队列由一个拆成多个，不同类型进程分配不同就绪队列，不同就绪队列采用不同算法。一个就绪队列可以设置不同优先级，不同就绪队列本身也可设优先级。

系统根据不同的用户选用不同的调度策略。

多级反馈队列调度算法

设置多个就绪队列，每个队列的优先级逐渐降低，同时每个队列的执行时间也各不相同，优先级越高的队列，执行时间越短，优先级越低的队列，执行时间越长。
当一个进程进入内存后，首先进入第一个队列的末尾，按照先来先服务的调度算法进行调度，如果在第一个队列的执行时间内未执行完成，此时把此进程放入第二个队列的末尾，按照之前的方法进行执行，直到在某一个队列的队首执行完成。

当第一个队列全部执行完成，此时系统才会执行第二个队列，但是如果此时又有新的进程进入，此时执行完毕这个时间段，立刻把此进程分配给新的作业。

根据公平原则的调度算法

公平分配每个进程相同的处理机时间，或按进程比例公平分配用户相同的处理机时间。

死锁

锁与信号量

锁强调于资源，信号量强调于执行次序。

资源分类

重用性资源与消耗性资源

可抢占性资源与不可抢占资源

死锁起因

源于多个进程对资源的争夺，不仅对不可抢占资源金进行争夺时容易产生死锁，而且对消耗性资源抢夺也会产生死锁。还有就是进程推进不当引起死锁。

死锁产生必要条件

互斥条件（不能破坏该条件）
请求与保持条件
不可抢占条件
循环等待条件

处理死锁的方法

以下四种方法从上往下防范程度逐渐减弱，但资源利用率与并发程度逐渐提高。

预防死锁

破坏”请求保持条件“

一次性分配所有需要的资源。
用到时再调用资源，用完即释放资源。

破坏”不可抢占条件“

调用资源时如果资源被占用，则必须释放已有所有资源，用时再调用。

破坏”循环等待条件“

先给进程编号并排序，再按照顺序分配资源。

避免死锁

银行家算法

银行家算法的数据结构
可利用资源向量（Available）：系统还可以分配的资源

最大需求矩阵（Max）：进程的最大资源需要

分配矩阵（Alloction）：进程已经获得的资源

需求矩阵（Need）：进程还需要获得的资源

银行家算法

假设 P1 进程提出请求 K 个资源

如果 K <= Need，就继续步骤；否则出错，因为请求资源 K 不能超过还需要获得的资源

如果 K <= Available，就继续步骤；否则出错，因为请求资源 K 不能超过系统还可以分配的资源

Available系统试探分配资源，并修改下列数据

Available = Available - K；表示分配给 P1 K 个资源后，还剩多少系统可分配资源

Allocation = Allocation + K；表示 P1 已经获得的资源

Need = Need - K；表示进程 P1 还需要获得的资源

此时系统执行安全性算法，计算进程是否处于安全性状态

PS：此时是执行的试探分配，为的是检查进程是否处于安全状态，不处于则试探分配作废

安全性算法

安全性算法是银行家算法在第五步执行的子算法，用于检查进程的安全状态

两个向量

工作向量（Work）：系统提供给进程的各类资源数目

Finish：表示系统是否有足够的资源分配给进程，这是一个布尔值。初始化为 false。

算法描述

在进程集合中找到下述条件的进程

Finish[ i ] = false;

Need <= Work

进程执行完毕

Work = Work + Allocation

Finish [ i ] = true

返回继续执行 1 ，寻找其他的进程分配资源

若所有的 Finish 为 true 则安全

检测死锁

资源分配图。

解除死锁

杀死进程。