进程同步、互斥 - 思维导图

进程

概念

程序是静态的

进程是动态的

是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程的组成

进程实体（进程映像）

进程控制块PCB

给操作系统用，常驻内存

进程存在的唯一标志

内容

进程描述信息

进程标识符PID

用户标识符UID

进程控制和管理信息

进程当前状态：就绪态/阻塞态/运行态……

进程优先级

代码运行入口地址

程序的外存地址

进入内存时间

信号量使用

CPU、磁盘、网络流量使用情况统计……

资源分配清单

正在使用哪些文件

文件描述符

正在使用哪些内存区域

数据段指针

堆栈段指针

文件描述符

正在使用哪些I/O设备

键盘、鼠标

处理机相关信息（CPU上下文）

主要指CPU各寄存器的值（用于实现进程切换）

将各个进程组织起来的方式

链接方式

索引方式

程序段

程序的代码（指令序列）

数据段

运行过程中产生的各种数据（如：程序中定义的变量）

进程自己使用

特征

动态性

最基本的特征

进程是程序的一次执行过程

并发性

独立性

独立运行、独立获得资源、独立接收调度的基本单位

异步性

执行速度的不可预知，结果的不可再现性

结构性

程序段、数据段、PCB

进程的状态与转换

状态

运行态

占有CPU，并在CPU上运行

就绪态

已具备运行条件，但没有空闲CPU

阻塞态

因等待某一时间而暂时不能运行

三种基本状态

创建态

操作系统为进程分配资源、初始化PCB

终止态

OS回收进程所拥有的的资源、撤销PCB

进程PCB中会有一个变量state来表示进程的当前状态

状态间的转换

就绪态——>运行态

进程被调度

运行态——>就绪态

时间片到，被高优先级抢占CPU

运行态——>阻塞态

等待资源分配（主动行为）

阻塞态——>就绪态

资源分配到位（被动行为）

创建态——>就绪态

运行态——>终止态

进程的组织方式（各个进程PCB的组织方式）

链接方式

按照进程状态将PCB分为多个队列

操作系统持有指向各个队列的指针

索引方式

根据进程状态的不同，建立几张索引表

操作系统持有指向各个索引表的指针

进程控制

基本概念

什么是进程控制

如何实现进程控制

用原语实现

原语的执行具有原子性，期间不允许被中断

“关/开中断指令”

两个特权指令

进程的创建

创建原语

申请空白PCB

为新进程分配所需资源

初始化PCB

将PCB插入就绪队列

引起进程创建的时间

用户登录

分时系统中，用户登录成功

作业调度

多道批处理系统中，有新作业放入内存

提供服务

用户向操作系统提出某些请求时

应用请求

用户进程主动请求创建一个子进程

进程的终止

终止（撤销）原语

从PCB集合中找到终止进程的PCB

若进程正在运行，立即剥夺CPU，将CPU分配给其它进程

终止其所有子进程

进程间的关系是树形结构

将该进程拥有的所有资源归还给父进程或操作系统

删除PCB

引起进程终止的事件

正常结束

异常结束

外界干预

级联终止

进程的阻塞

阻塞原语

找到要阻塞的进程对应的PCB

保护进程运行现场，PCB状态信息置为”阻塞态“

将PCB插入相应事件的等待队列

引起进程阻塞的事件

等待系统分配某种资源

等待相互合作的其他进程完成工作

进程的唤醒

唤醒原语

在事件等待队列找到PCB

将PCB从等待队列中移除，设置进程为就绪态

将PCB插入就绪队列，等待被调度

引起进程唤醒的事件

等待的事件发生

进程的切换

切换原语

将运行环境信息存入PCB

PCB移入相应队列

选择另一个进程执行，并更新其PCB

根据PCB恢复新进程所需的运行环境

引起进程切换的事件

当前进程时间片到

有更高优先级的进程到达

当前进程主动阻塞

当前进程终止

进程的通信

什么是进程间通信

两个进程之间产生数据交互

各进程拥有的内存地址空间是独立的

共享存储

基于数据结构的共享

低级

基于存储区的共享

高级通信

不由操作系统控制

消息传递

直接通信

指明接收进程的ID

间接通信

通过信箱间接地通信

数据交换以格式化的信息为单位

发送信息/接收信息两个原语

管道通信

管道是一种特殊的共享文件 pip文件

在内存中开辟一个大小固定的内存缓冲区

半双工通信；双向同时通信，需要设置两个管道

当管道写满时，写进程将阻塞；当管道读空时，读进程将阻塞

管道中的数据一旦被读出，就消失

一个管道允许多个写进程，一个读进程

允许有多个读进程，多个写进程，但系统会让各个读进程轮流从管道读数据（Linux）

两个进程按生产者-消费者方式进行通信

管道可克服使用文件进行通信的两个问题

限制管道的大小

读进程也可能工作得比写进程快

可被子进程继承

管道机制提供三方面的协调能力

互斥

由操作系统实现

同步

确定对方的存在

真题解答

信号

用于通知进程发生了某个特定事件的机制

信号是如何发送的？

内核——>进程

进程——>进程

信号的两种处理方式

执行默认的信号处理程序

执行进程定义的信号处理程序

进程控制相关的原语

更新PCB中的进程

进程状态标志

剥夺CPU前，保存运行环境

运行前恢复运行环境

将PCB插入合适的队列

分配/回收资源

线程、多线程模型

基本概念

轻量级进程

一个基本的CPU执行单元

组成

线程ID

程序计数器

寄存器集合

堆栈

基本状态

与进程的比较

引入线程可以增加并发度

进程只是除CPU之外的系统资源的分配单元

线程作为处理机（调度）的分配单元

同一进程内的线程切换，不需要切换进程环境，系统开销小

线程的属性

处理机调度的单位

多CPU计算机中，各个线程可占用不同的CPU

每个线程都有一个线程ID、线程控制块TCB

有就绪、阻塞、运行三种基本状态

线程几乎不拥有系统资源

同一进程的不同线程间共享进程的资源

同一进程中的线程间通信无需操作系统干涉

切换不同进程间的线程，需要切换进程，系统开销大

线程的实现方式

用户级线程ULT

线程管理工作由应用程序负责

线程切换在用户态下完成

优点：系统开销小，效率高

缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不能在多核处理机上并行运行（操作系统（OS）不知道这些线程的存在）。

内核级线程KLT

操作系统管理

切换在核心态下完成

优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

缺点：线程管理的成本高，开销大

多线程模型

多对一模型

优缺点类似于用户级进程

多个用户级进程映射到一个内核级进程

一对一模型

当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。

缺点：线程管理的成本高，开销大

多对多模型

内核级进程时处理机分配的单位

线程的状态与转换

状态

就绪态

阻塞

运行

线程的组织与控制

TCB

TID线程标识符

PC

其它寄存器

堆栈指针

线程切换时要保存/恢复

线程运行状态

优先级

处理机调度

基本概念

三个层次

高级调度（作业调度）

挑选一个作业调入内存，每个作业只调入一次，调出一次

中级调度（内存调度）

内存不够时，将某些进程的数据调出外存（挂起状态）。可能被多次调出、调入内存。发生频率比高级调度高。

低级调度（进程调度）

按照某种策略从就绪队列中选取一个进程，将处理机分配给他

最基本的一种调度，频率很高

三层调度的联系、对比

补充知识

进程的”挂起态“

与阻塞态不同，将进程映像调到外存了，阻塞态仍在内存

七状态模型

加入”就绪挂起“和”阻塞挂起“

进程调度

时机

什么时候需要进程调度？

当前运行的进程主动放弃处理机

进程正常终止

运行过程中发生异常而终止

进程主动请求阻塞（如等待I/O）

被动放弃

时间片用完

更紧急的事需要处理（I/O中断）

有更高优先级的进程进入就绪队列

什么时候不能进行进程调度？

在处理中断的过程中

进程在操作系统内核程序临界区中

普通临界区可以

在原子操作过程中

切换与过程

“狭义的调度”与“切换”的区别

狭义的进程调度：从就绪队列中选中一个要运行的进程（可以是刚刚被暂停执行的进程）

进程切换：另一个进程占用处理机的过程

进程切换的过程需要做什么？

进程调度、切换有代价，并不是越频繁、并发度越高

对原来运行进程各种数据的保存

对新的进程各种数据的恢复

方式

非剥夺调度方式（非抢占式）

早期的批处理系统

剥夺调度方式（抢占式）

分时操作系统，实时

调度器/调度程序（scheduler）

调度时机

非抢占

运行进程阻塞或退出

抢占式

k个时钟中断

对象

支持内核级线程的操作系统

内核线程

不支持内核级线程的操作系统

进程

闲逛进程

没有其它就绪进程时，运行闲逛进程

特性

优先级最低

可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）

能耗低

调度算法

调度算法的评价指标

要理解并且会计算

CPU利用率

忙碌时间/总时间

系统吞吐量

单位时间内完成作业的数量

总共完成了多少道作业/总共花了多少时间

周转时间

周转时间、平均周转时间

作业完成时间-作业提交时间

带权时间、平均带权时间

作业周转时间/作业实际运行时间

等待时间

处于等待处理机状态时间之和

响应时间

从用户提交请求到首次产生响应所用的时间

调度算法

先来先服务FCFS

算法思想

公平

算法规则

按照作业/进程到达的先后顺序进行服务

用于作业/进程调度

作业调度，后备队列

进程调度，就绪队列

是否可抢占

非抢占式的算法

优缺点

优点：公平，实现简单

缺点：带权周转时间大，对短作业不友好

是否会导致饥饿

不会

短作业优先SJF

追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间

最短的作业/进程优先得到服务

SJF和SPF是非抢占式的算法

所有进程几乎同时到达时，平均等待时间、平均周转时间最少

并非绝对

抢占式的版本

最短剩余时间优先算法SRTN

优点：平均等待时间、平均周转时间最少

缺点：不公平。对长作业不利。不一定真能做到短作业优先

会产生饥饿

高响应比优先HRRN

综合考虑作业/进程的等待时间和要求服务时间

响应比=（等待时间+要求服务时间）/要求服务时间

非抢占式算法

综合优点

不会导致饥饿

时间片轮转RR

公平、轮流

轮流、时间片轮转

可抢占，时钟装置发出时钟中断

优点；公平、响应快，适用于分时操作系统

缺点：进程切换开销大；不区分任务的紧急程度

不会导致饥饿

优先级调度

调度时优先选择优先级最高的进程

系统进程优先级高于用户进程

前台进程优先级高于后台进程

操作系统偏好I/O型进程

I/O设备和CPU可以并行工作

抢占式、非抢占式都有

优点：优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活调整优先级

缺点：可能导致饥饿

多级反馈队列调度

对其他调度算法的折中权衡

规则

设置多级就绪队列，时间片随优先级降低而增大

新进程到达时进入优先级最高的队列（FCFS原则分配）；用完时间片后，放入下一优先级队列的队尾

只有高优先级的队列为空，才会为低优先级的队列分配时间片

抢占式；被抢占的进程放回原队列队尾

优点：相对公平；快速响应；短进程友好；不必预估运行时间；可灵活调整对各类进程的偏好程度（可以选择放回的队列）

会导致饥饿

适用于交互式系统

多级队列调度

按进程类型设置多个队列

采取固定优先级或按时间片划分

各队列可采用不同的调度策略

主题

进程同步、互斥

进程同步

为了解决异步问题

有些进程需要相互配合，遵循一定的先后顺序

进程互斥

两种资源共享方式

互斥共享

临界资源：一个时间段内只允许一个进程访问该资源

临界区：进程中访问临界资源的代码进入区和退出区：负责实现互斥的代码段

同时共享

对临界资源的互斥访问

四个部分

进入区：负责实现互斥的代码段

检查是否可以进入临界区，若可以，则设置正在访问临界区的标志

临界区：进程中访问临界资源的代码

退出区：解除正在访问临界资源的标志

清除正在访问临界区的标志

剩余区

访问原则

空闲让进

临界区空闲，则允许一个进程访问

忙则等待

正在被访问，则其它要访问的进程等待

有限等待

在有限时间内等待访问临界区

让权等待

进不了临界区的进程，释放处理机，防止忙等

软件实现

单标志法

turn变量表示当前拥有访问临界区权限的进程号，由另一个进程赋予

在进入区只做检查不做上锁

在退出区把临界区的使用权转交给另一个进程

可以实现“同一时刻最多只允许一个进程访问临界区”

问题：违背“空闲让进”

某个进程拥有权限但一直不使用，则权限在无法授予其它进程

双标志先检查

设置一个布尔数组，标记各进程想进入临界区的意愿

先检查布尔数组，再上锁

问题：违背“忙则等待”

进入区的检查和上锁可能不是连续的，两个操作中间被打断则可能导致另一个进程检查到未上锁状态，导致多个进程同时访问

双标志后检查

先上锁，再检查布尔数组

问题：违背了“空闲让进”和“有限等待”

双方都上锁了，但是双方都无法进入访问，导致产生饥饿现象

Peterson算法

结合双标志和单标志

先表示自己想访问；谦让（将turn标记为另一进程）；如果无其他人想访问，则进入临界区；如果有，则等待。

最后一个等待

问题：未遵循让权等待的原则

没有权限时，一直处于忙等待占用处理机

硬件实现

中断屏蔽方法

利用“开/关中断指令”实现

优点：简单、高效

缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程；限制了CPU交替执行程序的能力

硬件指令方法

Swap指令（Exchange/XCHG)

TestAndSet(TS)/TSL

为每个临界资源设置一个共享变量记录资源的两种状态将加锁并检查作为一整个原子操作

优点：实现简单；适用于多处理机环境；支持系统中有多个临界区，只需为每个临界区设立一个布尔变量

缺点：不满足“让权等待”原则；随机选择性会导致“饥饿”现象

这个原子性是在总线/内存控制器级别保证的，确保了即使在多个CPU同时访问同一内存位置时，锁的获取操作也是互斥的

互斥锁/自旋锁

acquire()获得锁；release()释放锁

原子操作，采用硬件机制实现

需要连续循环忙等——>自旋锁

特性

需忙等，进程时间片用完才下处理机

优点：等待期间不用切换进程上下文

常用于多处理器系统，上锁的时间段，等待代价很低

不太适用于单处理机系统

信号量机制

信号量是一个变量，表示系统中某种资源的数量

wait(S)和signal(S)原语

整型信号量

整数型的变量，表示系统中某种资源的数量

对信号量只能进行初始化、wait操作、signal操作

不遵循“让权等待”原则

记录型信号量

用记录型数据结构表示信号量

S.value表示某种资源数，S.L指向等待该资源的队列

P操作，先S.value--

若S.value <0 说明资源数不足，调用block原语进行自我阻塞

V操作，先S.value++

若S.value <=0 说明仍有进程等待使用该资源，调用wakeup原语将S.L中的第一个进程唤醒

用记录型信号量实现系统资源的“申请”和“释放”

用记录型信号量实现进程互斥、进程同步

实现进程互斥

分析问题，确定临界区

互斥信号量mutex，初始值为1

临界区之前对信号量执行P操作

申请资源

临界区之后对信号量执行V操作

释放资源

注意

不同临界资源需要设置不同的互斥信号量

P(S) V(S)必须同步出现

多个资源问题，更改互斥信号量的初始值

实现进程同步

分析问题，找到需要实现的前后关系

同步信号量S，初始值为0

在‘前操作’之后，执行V操作

在‘后操作’之前，执行P操作

实现前驱关系

分析问题，画出前驱图，每一对前驱关系都是一个进程同步问题

为每一对前驱关系各设置一个同步信号量，初始值为0

在每个‘前操作’之后，执行V操作

在每个‘后操作’之前，执行P操作

经典同步问题

生产者-消费者问题

生产者、消费者共享一个初始值为空、大小为n的缓冲区

缓冲区没满时，生产区才能把产品放入缓冲区，否则必须等待

缓冲区不空时，消费者才能从中取出产品，否则必须等待

缓冲区是临界资源，各进程必须互斥地访问

多生产者-多消费者问题

吸烟者问题

可生产多种产品的单生产者-多消费者问题

读者-写者问题

要求

允许多个读者可以同时对文件执行读操作

只允许一个写者往文件中写信息

任一写者在完成写操作之前不允许其它读者或写者工作

写者执行写操作前，应让已有的读者和写者全部退出

实现方法

变量count记录当前读者数量

如果没有一个实现“写优先”的信号量，则程序为“读优先”

会导致写进程饿死

哲学家进餐问题

哲学家饥饿时一根一根地拿起左、右两根筷子。如果筷子已在他人手上，则需等待。哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

管程

为什么引入管程

信号量机制编写程序困难、易出错

管程的定义和基本特征

特殊的软件模块

局部于管程的共享数据结构说明

对该数据结构进行操作的一组过程

对局部于管程的共享数据设置初始值的语句

管程有一个名字

基本特征

局部于管程的数据只能被局部于管程的过程所访问

一个进程只有通过调用管程内的过程才能进入管程访问共享数据

每次仅允许一个进程在管程内执行某个内部进程

拓展1：用管程解决生产者消费者问题

各进程必须互斥访问管程的特性是由编译器实现的

可在管程中设置条件变量及等待/唤醒操作以解决同步问题

拓展2：Java中类似于管程的机制

死锁

概念

什么是死锁

在并发环境下，各进程因竞争资源而造成的一种相互等待对方手里的资源，导致各进程都阻塞

死锁、饥饿、死循环的区别

死锁：至少是两个进程一起死锁，死锁进程处于阻塞态

饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞、可能就绪

死循环：可能只有一个进程发生死循环，死循环的进程可上处理机

死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的

死锁产生的必要条件

互斥条件

对必须互斥使用的资源的争抢

不剥夺条件

进程保持的资源只能主动释放，不可强行剥夺

请求和保持条件

保持某些资源不放的同时，请求别的资源

循环等待条件

存在一种进程资源的循环等待链

循环等待未必死锁，死锁一定有循环等待

什么时候会发生死锁

对不可剥夺资源的不合理分配

死锁的处理策略

预防死锁

破坏死锁产生的四个必要条件

避免死锁

避免进入不安全状态（银行家算法）

死锁的检测和解除

允许死锁发生，系统负责检测出死锁并解决

处理

不允许死锁发生

静态策略：预防死锁

破坏互斥条件

破坏不剥夺条件

请求新的资源得不到满足，则立即释放保持的所有资源

由操作系统协助，强行剥夺被其他进程占有的资源

缺点

实现复杂

释放已获得的资源可能造成前一阶段工作的失效

反复地申请和释放资源会增加系统开销，降低系统吞吐率

可能会导致饥饿

破坏请求和保持条件

静态分配方法，一次性申请完它所需地全部资源

每个进程只能同时申请或拥有一个资源

缺点：资源利用率低，可能导致某些进程饥饿

破坏循环等待条件

顺序资源分配法，进程按编号递增地顺序请求资源

缺点：不方便增加新设备；使用资源地顺序可能和编号递增顺序不一样，造成资源浪费；用户编程麻烦

动态策略：避免死锁

什么是安全序列

系统按照这种序列分配资源，则每个进程都能顺利完成

只要能找出一个安全序列，系统就是安全状态

什么是系统的不安全序列，与死锁有何联系

处于安全状态，就一定不会发生死锁

死锁时一定处于不安全状态

处于不安全状态不一定死锁

如何避免系统进入不安全状态——银行家算法

在分配前先预判这次分配是否会导致系统进入不安全状态

安全性算法

每一轮检查从较小编号开始

检查是否存在安全序列

系统中有n个进程，m中资源

还有多少可用资源Available

最大需求矩阵Max

分配矩阵Allocation

各进程最多还需要多少各类资源矩阵Need

一维数组Request

表示进程此次申请的各种资源数

步骤

检查此次申请是否超过Max

检查剩余可用资源是否可以满足这次申请

分配

用安全性算法检查系统状态

允许死锁发生

死锁的检测和解除

死锁的检测

资源分配图

结点

进程结点

圆形

资源结点

矩形

边

进程结点——>资源结点：表示进程想申请几个资源

资源结点——>进程结点：表示已经为进程分配了几个资源

死锁检测算法

依次消除与不阻塞进程相连的边

不能消除所有边，发生死锁

死锁的解除

资源剥夺法

挂起某些死锁进程，并抢占它的资源

撤销进程法

强制撤销部分，甚至全部死锁进程

进程回退法

让一个或多个进程回退到足以回避死锁的地步