一、进程

1.1 多道程序设计

允许多个程序同时进入内存并运行，提高CPU的利用率，目的是提高系统效率

a图内存中有四个程序，串行执行，因为这里只有一个程序计数器。

当有了多道程序技术之后就得到了b图，每个程序各自独立的占用一个逻辑程序计数器，达到并发执行效果

从c图中可以看到多个程序是轮流执行的

1.2 并发环境与并发程序

并发环境指一段时间间隔内，单处理器上有两个或两个以上的程序同时处于开始运行但尚未结束的状态，并且次序不是事先确定的。在并发环境下执行的程序就是并发程序。

1.3 定义

进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位

• 进程是程序的一次执行过程，一个程序执行多次那是不同的进程
• 是正在运行的程序的抽象，或者说是对CPU的一个抽象
• 将一个CPU变换成多个虚拟的CPU
• 系统资源以进程为单位分配，如内存、文件等，操作系统为每个独立的进程分配了独立的地址空间
• 操作系统将CPU调度给需要的进程，即将CPU的控制权交给某个进程就称为调度

###特征

• 结构性：由数据段、程序段、PCB构成
• 动态性：可以被动态地创建、执行、撤销
• 并发性：同一时间内有多个进程在运行
• 独立性：独立运行以及获得OS资源的基本单位
• 异步性：异步执行
  ###组成
  ①程序
  描述进程要完成的功能
  ②数据集合
  程序在执行时所需要的数据和工作区。
  ③程序控制块PCB
  包含进程的描述信息和控制信息。它是进程存在的唯一标志。1.4 进程控制块-PCB
• 又称进程描述符或进程属性
• 操作用于管理控制进程的一个专门的数据结构
• 记录进程的各种属性，描述进程的动态变化过程
• **PCB**是系统感知进程存在的唯一标志：进程与PCB一一对应
• 进程表：所有进程的PCB集合。
  进程表的大小往往固定，这也决定了一个操作系统最多支持多少个进程，有时我们称为系统支持的并发度1.4.1 PCB中需要保存的信息
• 1、进程描述信息
  • 进程标识符（process id），这个标识是唯一的，通常是一个整数
  • 进程名，通常基于可执行文件名，这是不唯一的
  • 用户标识符（user id）
  • 进程组关系
• 2、进程控制信息
  • 当前状态
  • 优先级
  • 代码执行入口地址
  • 程序的磁盘地址
  • 运行统计信息（执行时间、页面调度）
  • 进程间同步和通信
  • 进程的队列指针
  • 进程的消息队列指针
• 3、所拥有的资源和使用情况

*   虚拟地址空间的使用状况
*   打开的文件列表4、CPU线程信息undefined这是当CPU不运行的时候操作系统需要把一些重要的信息记录下来

*   寄存器值（通用寄存器、程序计数器`PC`、程序状态字`PSW`、栈指针）
*   指向该进程页表的指针

1.4.2 换个角度看PCB的内容

**说明：**从上图中可以看到第一列是和进程管理相关的字段，第二列是存储管理的字段，第三列是文件管理的字段。

二、进程状态及状态转换(重点)

2.1 进程的三种基本状态

• 运行态：占用CPU，并在CPU上运行
• 就绪态：已经具备运行条件，但由于没有空闲CPU，而暂时不能运行
• 等待态：因等待某一事件而暂时不能运行，如等待读盘结果。又称为阻塞态、封锁态、睡眠态。其转换过程如下：

2.2 进程的其他状态

• 创建态

*   已完成创建一个进程所必要的工作，如`PID、PCB`
*   但尚未同意执行该进程，因为资源有限终止态

*   终止执行后，进程进入该状态
*   可完成一些数据统计工作
*   资源回收挂起态

*   用于调节负载
*   进程不占用内存空间，其进程映像交换到磁盘上

2.3 五状态模型

2.4 七状态模型

![](//upload-images.jianshu.io/upload_images/1925650-0c3172fd8b1a3825.png?imageMogr2/auto-orient/strip|imageView2/2/w/70

2.5 Linux状态转换示意图

**说明：**这里使用fork()创建一个进程。浅度睡眠和深度睡眠不同在于前者在睡眠时会接收信号，而后者则不会。正在运行的程序可能因为调试断点可能出现一个暂停的状态。

三、进程队列

• 操作系统为每一类进程建立一个或多个队列
• 队列元素为PCB
• 伴随进程状态的改变，其PCB从一个队列进入另一个队列undefined
  **说明：**真实情况下，就绪态也是排多个队列。而等待态由于各自产生的原因（事件）不同而排不同的队列。

3.1 五状态进程模型的队列模型

四、进程控制

进程控制操作完成进程各状态之间的转换，由具有特定功能的原语（其实就是程序，只是这些程序不许与被中断）完成。关于进程控制的原语如下：

• 进程创建原语
• 进程撤销原语
• 阻塞原语
• 唤醒原语
• 激活原语
• 改变进程优先级

**原语：**完成某种特定功能的一段程序，具有不可分割性或不可中断性，即原语的执行必须是连续的，在执行过程中不允许被中断。又称原子操作。

4.1 进程的创建

• 给新进程分配一个唯一标识以及进程控制块（没有被使用的）
• 为进程分配独立地址空间
• 初始化进程控制块：设置默认值（如状态为New…）
• 设置相应地队列指针。如：把新进程加到就绪队列链表中
• 主要操作是UNIX中：fork/exec，Windows中：CreateProcess

4.2 进程的撤销

也就是结束进程，主要完成的工作：

• 回收进程所占用的资源，如关闭打开的文件、断开网络连接、回收分配的内存等
• 撤销该进程的PCB
• 在UNIX中使用：exit，Windows中：TerminateProcess

4.3 进程阻塞

处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其他进程发送消息。当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。在UNIX中我们使用wait，在Windows中使用WaitForSingleObject。

4.4 UNIX的几个进程控制操作

• fork() 通过复制调用进程来建立新的进程，是最基本的进程建立过程。也就是通过复制父进程来创建子进程。
• exec() 包括一些列系统调用，它们都是通过用一段新的程序代码覆盖原来的地址空间，实现进程代码的转换
• wait() 提供初级进程同步操作，能使一个进程等待另一个进程的结束
• exit() 用来终止一个进程的运行

**UNIX中fork()**实现：

• 为子进程分配一个空闲的进程描述符，即PCB，在UNIX中又叫proc结构
• 分配给子进程唯一标识pid
• 以一次一页的方式复制父进程的地址空间，这是一个无用功，因为创建子进程就是为了让子进程完成与父进程不同的工作，所以父进程的很多内容其实子进程是不需要的。于是在Linux中采用了写复制技术COW加快创建进程。
• 从父进程处共享资源，如打开的文件和当前工作目录等
• 将子进程的状态设置为就绪，插入到就绪队列
• 对子进程返回标识符0
• 向父进程返回子进程的pidundefined五、深入理解进程概念

5.1 进程的分类

• 1、系统进程/用户进程undefined这里系统进程的优先级要高
• 2、前台进程/后台进程undefined用户一般只和前台进程交互。
• 3、CPU密集型进程/IO密集型进程

5.2 进程层次结构

• **UNIX**中是一个进程家族树的概念：init为根进程。于是如果某一个进程结束了，那么其子孙进程都必须结束。
• **Windows**中的所有进程的地位都是相同的。

5.3 进程和程序的区别

• 进程更能准确刻画并发，而程序不能
• 程序是静态的，进程是动态的
• 进程有生命周期的，有诞生有消亡，是短暂的；而程序是相对长久的
• 一个程序可对应多个进程
• 进程具有创建其他进程的功能

5.4 进程的地址空间

操作系统为每个进程分配了一个地址空间。这里我们看一个例子：

这个程序我们从命令行中输入数据，比如：

myval 7

myval 8

此时我们会发现虽然进程不同，但是打印出来的地址确实一样的。这里我们从进程地址空间来分析：

**说明：**上面的两个进程都有这样一个地址空间，也就是说这两个进程是在不同的地址空间上的相同的位置，所以虽然地址是一样的，但是实际上在实际内存中的地址是不一样的。

5.5 进程映像

对进程执行活动全过程的静态描述（快照）。由进程地址空间内容、硬件寄存器内容及与该进程相关的内核数据结构、内核栈组成

• 与用户相关：进程地址空间（代码段、数据段、堆和栈、共享栈等）
• 与寄存器相关：程序计数器、指令寄存器、程序状态寄存器、栈指针、通用寄存器等的值
• 与内核相关：
  • 静态部分：PCB及各种资源数据结构
  • 动态部分：内核栈（不同进程在进入内核后使用不同的内核栈）

5.6 上下文切换

• 将CPU硬件状态从一个进程换到另一个进程的过程称为上下文切换，其实就是运行环境的切换。
• 进程运行时，其硬件状态保存在CPU上的寄存器中。寄存器有：程序计数器、程序状态寄存器、栈指针、通用寄存器、其他控制寄存器的值
• 进程不运行时，这些寄存器的值保存在进程控制块中；当操作系统要运行一个新的进程时，将进程控制块中相关值送到对应的寄存器中。

六、线程

6.1 线程的引入

引入理由

• 应用的需要
• 开销的考虑
• 性能的考虑

6.1.1 应用的需要

我们看一个例子，一个web服务器的工作方式

• 从客户端接收网页请求
• 从磁盘上检索相关的网页，读入内存（此时进程是停止的，直到读取完毕）
• 将网页返回给对应的客户端

可以看到每次从磁盘读取的时候进程都是暂停的，这样会导致性能低下

那如何提高服务器的工作效率？通常情况下是使用网页缓存

在

没有线程情况下的两种解决方案

• 一个服务进程undefined这种情况下也是一种顺序编程，虽然采用了缓存机制，但是性能同样不高。而如果设置多个进程，这多个进程之间又是相互独立的，有独立的地址空间，所以不能共享信息
• 有限状态机undefined这种方式编程模型复杂，采用非阻塞的I/O

多线程的解决方式

**说明：**这是一个多线程的web服务器的工作方式，首先读取客户端的请求，之后由分派线程将各个任务分派给工作线程，这里还是采用了网页缓存

于是我们可以看到一个web服务器的实现有三种方式：

6.1.2 开销的考虑

6.1.3 性能的考虑

如果有多个处理器的话，一个进程就会有多个线程同时在执行了，这样可以极大的提高运行性能

6.2 线程的基本概念

线程的属性

• 有标识符ID
• 有状态及状态转换-->需要提供一些操作
• 不运行时需要保存的上下文（程序计数器等寄存器）
• 有自己的栈和栈指针
• 共享所在进程的地址空间和其他资源
• 创建、撤销另一个线程（程序开始是以一个单线程方式运行的）

6.3 线程机制的实现

一般有三种实现机制

• 用户级线程
• 核心级线程
• 混合（两者结合）方法6.3.1 用户级线程
  说明：线程是由运行时系统管理的，在内核中只有进程表。典型例子就是UNIXundefinedPOSIX线程库–PTHREAD

• 优点
  • 线程切换快
  • 调度算法是应用程序特定的
  • 用户级线程可运行在任何操作系统上（只需要实现线程库）
• 缺点
  • 内核只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上
  • 大多数系统调用是阻塞的，因此，由于内核阻塞进程，故进程中所有线程也被阻塞。（可以在调用之前判断进行解决，如果是阻塞线程，那么就换其他线程）6.3.2 核心级线程6.3.3 混合模型
• 线程创建在用户空间完成
• 线程调度等在核心态完成
• 例子如Solaris操作系统
  ##6.4 线程状态(Java)
  0)新建：创建后尚未启动的线程处于这种状态。
  1)运行：包括了 OS 中 Running 和 Ready 状态，也就是处于此状态的线程可能正在运行，也可能正在等待 cpu 为它分配执行时间
  2)无限期等待:处于这种状态的线程不会被分配 cpu 执行时间,要等待其他线程显示唤醒。以下方法会让线程进入无限期等待 ：
• 没有设置 timeout 的 object.wait()
• 没有设置 timeout 参数的 Thread.join()
• LockSupport.park()

3)有限期的等待：处于这种状态的线程也不会被分配 cpu 执行时间，不过无需等待被其他线程显示唤醒，而是在一定时间后，他们会由 OS 自动唤醒 1.设置了 timeout 的 object.wait() 方法 2. 设置了 timeout 参数的 Thread.join() 3.LockSupport.parkNanos()

4.LockSupport.parkUnit()

4） 阻塞:与"等待"的区别：

• 阻塞态在等待获取一个排它锁，这个事件将在另外一个线程放弃这个锁的时候发生
• 等待状态在等待一段时间或者唤醒动作。
  5)结束：已终止线程的线程状态，线程已经结束执行。 进程的通信类型
• 共享存储器、管道、客户机-服务器系统（socket）
• 直接通信、间接通信（信箱）

管程(Monitors，也称为监视器)(重点)

基本概念

一种程序结构，结构内的多个子程序（对象 “对象 (计算机科学)”)或模块 “模块 (程序设计)”)）形成的多个工作线程 “工作 (信息学)”)互斥访问共享资源。

这些共享资源一般是硬件设备或一群变量。

管程实现了在一个时间点，最多只有一个线程在执行管程的某个子程序。与那些通过修改数据结构实现互斥访问的并发程序设计相比，管程实现很大程度上简化了程序设计。

管程提供了一种机制，线程可以临时放弃互斥访问，等待某些条件得到满足后，重新获得执行权恢复它的互斥访问。

一、死锁的基本概念

• 临界资源
  指每次只允许一个进程访问的资源，分硬件临界资源、软件临界资源。
• 临界区
  每个进程中访问临界资源的那段程序叫做临界区。
  进程对临界区的访问必须互斥，每次只允许一个进程进去临界区，其他进程等待。

临界区管理的基本原则(重点)

①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。

②任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。

③进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。

④如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

1.1 死锁的定义(重点)

• 一组进程中，每个进程都无限等待被该组进程中另一进程所占用的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。
• 如果发生死锁，会浪费大量系统资源，甚至导致系统崩溃
• 注意：

参与死锁的所有进程都在等待资源

参与死锁的进程是当前系统中所有进程的子集

1.2 死锁的产生原因

资源数量有限、锁和信号量错误使用。

• 资源的使用方式

“申请-分配-使用-释放”模式

• 可重用资源：可被多个进程多次使用，又可分为可抢占资源与不可抢占资源，如处理器、I/O部件、内存、文件、数据库、信号量等可抢占资源。
• 可消耗资源：只可使用一次、可创建和销毁的资源。如信号、中断、消息等。

1.3 活锁和饥饿

说明：

• 如图，这里有两个进程都需要使用资源1和资源2，有这样一种情况，比如这两个进程都上cpu执行，但是进程A执行到第二句的时候需要使用资源2，而进程B执行到第二句的时候需要资源1，但是此时恰好都不能获得各自的资源，这样就进入忙等待（进入轮询看资源是否可用），这就是活锁，也就是先加锁再轮询，这样导致两个进程既无进展也没有阻塞。这和死锁的概念的区别在于死锁的时候进程不能进入cpu去执行。
• 饥饿：资源分配策略决定
  

1.4 产生死锁的必要条件

• 互斥使用（资源独占）：一个资源每次只能给一个进程使用
• 占有且等待（请求和保持，部分分配）：进程在申请新的资源的同时保持对原有资源的占有。
• 不可抢占（不可剥夺）：资源申请者不能强行的从资源占有着手中多去资源，资源只能由占有着自愿释放
• 循环等待

存在一个进程等待队列`｛P1，P2，......，Pn｝`，其中`P1`等待`P2`占有的资源，`P2`等待`P3`占有的资源，......，`Pn`等待`P1`占有的资源，形成一个进程等待环路。

二、资源分配图（RAG：Resource Allocation Graph）

用有向图描述系统资源和进程的状态

2.1 资源分配图画法说明

• 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。
• 资源类：用方框表示。资源实例：用方框中的黑圆点表示。进程：用圆圈中加进程名表示。
  
• 分配边：资源实例–>进程；申请边：进程–>资源类

2.2 死锁定理

• 如果资源分配图中没有环路，则系统中没有死锁；如果图中存在还礼则系统中可能存在死锁。
• 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。例如：
  

2.3 资源分配图化简

化简步骤：

• 1、找一个非孤立、且只有分配边的进程结点，去掉分配边，将其变为孤立结点
• 2、再把相应的资源分配给一个等待该资源的进程，即将该进程的申请边变为分配边。
• 3、重复上述步骤直到找不到资源分配结点。完成之后如果所有结点都变为孤立结点则表示系统中没有死锁，否则系统存在死锁。

三、死锁预防

3.1 解决死锁的方法

• 不考虑此问题（鸵鸟算法）
• 不让死锁发生

*   死锁预防。这是一种静态策略：即设计合理的资源分配算法，不让死锁发生
*   死锁避免。这是一种动态策略：以不让死锁发生为目标，跟踪并评估资源分配过程，根据评估结构决策是否分配

• 让死锁发生

死锁检测和解除

3.2 死锁预防（Deadlock Prevention）(重点)

• 定义：在设计系统时，通过确定资源分配算法，排除发生死锁的可能性
• 具体做法：防止产生死锁的四个必要条件中任何一个条件的发生

3.2.1 破坏“互斥使用/资源独占”条件

• 资源转换技术：把独占资源变为共享资源
• SPooling技术的引入，解决不允许任何进程直接占有打印机的问题。设计一个“守护进程/线程”负责管理打印机，进程需要打印时， 将请求发给该daemon，由它完成打印任务。

3.2.2 破坏“占有且等待”条件

• 实现方案1：要求每个进程在运行前必须一次性申请它所有求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。当然，这种方案的资源利用率较低，容易出现“饥饿”现象。
• 实现方案2：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。

3.2.3 破坏“不可抢占”条件

• 实现方案

当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源（两个进程优先级不同）

• 局限性：
  该方法实现起来比较复杂，要付出很大的代价。
  • 反复地申请和释放资源
  • 进程的执行被无限地推迟

只适用于状态易于保存和恢复的对主存资源和处理器资源的分配适用于资源。如cpu和内存等。

3.2.4 破坏“循环等待”条件

• 通过定义资源类型的线性顺序实现
• 实施方案：资源有序分配法
  把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。我们一般根据资源使用的频繁性来进行编号。例如解决哲学家就餐问题。
• 为什么资源有序分配法不会产生死锁？
  起始就是进程申请的资源编号必须是递增的，比如进程P1申请了资源1、3、9，而进程P2需要资源1、2、5，那么进程P2在申请时必须按照1、2、5的顺序来申请，这样就破坏了环路条件，因为在申请到资源1之前，后面的资源是申请不到的。

存在下述严重问题：

限制了新类型设备的增加。

造成对资源的浪费。

必然会限制用户简单、自主地编程。

四、死锁避免

• 定义：在系统运行过程中，对进程发出的每一个系统能满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统发生死锁或可能发生死锁（不是安全状态），则不予分配，否则（安全状态）予以分配。
• 安全状态：如果系统中存在一个所有进程构成的安全序列P1，P2，......，Pn，则称系统处于安全状态。安全状态表示系统一定没有发生死锁。
• 安全序列
  一个进程序列｛P1，P2，......，Pn｝是安全的，如果对于每个进程Pi(1<= i <= n)：它以后还需要的资源数量不超过系统当前剩余资源量与所有进程Pj(j < i)当前占有资源量只和。
• 不安全状态：系统中不存在一个安全序列。一定会导致死锁。五、死锁避免算法：银行家算法这是Dijkstra在1965年提出的，是仿照银行发放贷款时采取的控制方式而设计的一种死锁避免算法。
• 应用条件
  1、在固定数量的进程***享数量固定的资源。
  2、每个进程预先指定完成工作所需的最大资源数量。
  3、进程不能申请比系统中可用资源总数还多的资源。
  4、进程等待资源的时间是有限的。
  5、如果系统满足了进程对资源的最大需求，那么，进程应该在有限的时间内使用资源，然后归还给系统。
  
  当进程Pi提出资源申请时，系统执行下列步骤：

（1）若Request[i] <= Need[i]，转（2）；否则，报错返回。

（2）若Request[i] <= Available，转（3）；否则，报错返回。

（3）假设系统分配了资源，则有：

Available = Available - Request[i];

Allocation[i] = Allocation[i] + Request[i];

Need[i] = Need[i] = Request[i]

`</pre>

若系统新状态是安全的，则分配完成；若系统新状态是不安全的，则恢复原来状态，进程等待。

为了进行安全性检查，定义了数据结构：

安全性检查的步骤：

（1）`Work = Available； Finish = false；`

（2）寻找满足条件的`i`：

如果不存在，则转（4）

（3）

`Work = Work + Allocationi ;

转（2）

（4）若对所有i，Finish[i] == true，则系统处于安全状态，否则，系统处于不安全状态。

六、死锁检测与解除

• 死锁检测

允许死锁发生，但是操作系统会不断监视系统进展情况，判断死锁是否真的发生。一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。

• 检测时机

1、当进程由于资源请求不满足而等待时检测死锁。这里缺点是系统开销较大。

2、定时检测

3、系统资源利用率下降时检测死锁

6.1 一个简单的死锁检测算法

6.2 死锁的解除

发生死锁后重要的是以最小的代价恢复系统的运行。方法如下：

• 撤销所有死锁进程，代价较大。
• 进程回退再启动，代价也较大
• 按照某种原则逐一死锁进程，直到不发生死锁
• 按照某种原则逐一抢占资源（资源被抢占的进程必须回退到之前的对应状态），直到不发生死锁 。