第二章进程的描述与控制思维导图模板

1.前趋图和程序控制

1.前趋图

直接前驱，前驱

描述执行顺序，即可顺序也可并发

2.程序的顺序执行

可再现性

3.程序并发执行

不可再现

2.进程的描述

1.进程的定义

进程实体=程序段+相关数据段+PCB

2.进程的特征

3.三种基本状态

4.三种基本状态的转换

5.创建状态和终止状态

1、创建过程
2、终止步骤

6.挂起操作和激活操作

7.数据结构

操作系统中

PCB的作用

(1) 作为独立运行基本单位的标志。
(2) 能实现间断性运行方式。
(3) 提供进程管理所需要的信息。
(4) 提供进程调度所需要的信息。
(5) 实现与其它进程的同步与通信。

PCB中的信息

1) 进程标识符

(1) 外部标识符。
(2) 内部标识符。

2) 处理机状态

通用寄存器
指令计数器
程序状态字PSW
用户栈指针

3) 进程调度信息

进程状态
进程优先级
进程调度所需的其他信息
事件(阻塞原因）

4) 进程控制信息

程序和数据的地址
进程通信和同步机制
资源清单
链接指针

PCB的组织方式

线性方式

链接队列

索引方式

8、典型问题

1、进程的定义及组成，
程序和进程的区别

2、状态转换图

3、PCB的作用

4、PCB包含的内容

3.进程的控制
（对系统中的全部进程实施有效的
管理，负责进程状态的改变。
进程控制一般是由OS的内核中的原语来实现的。
）

1、OS内核

OS内核的定义

处理机的执行状态
（防止关键数据遭破坏）

系统态（管态）

用户态（目态）
（应用程序）

功能

支撑功能

(1) 中断处理。

是内核最基本的功能，是整个OS赖以活动的基础

(2) 时钟管理。

最基本功能

(3) 原语操作。

原语定义

有若干指令组成的，用于完成一定功能的一个过程，
执行过程中不允许被中断。在系统态执行，常驻内存。

原语与一般过程的区别

原子操作

原子操作的定义

要么全做，要么全不做

资源管理功能

(1) 进程管理。
(2) 存储器管理
(3) 设备管理。

1、进程的创建
（原语create）

1、进程的层次结构

父进程
子进程

进程图
（描述进程间关系的
一棵有向树）

2、引起创建进程的事件

(1) 用户登录。
(2) 作业调度。
(3) 提供服务。
(4) 应用请求。

3、创建步骤

(1) 申请空白PCB
(2) 为新进程分配其运行所需的资源

(3) 初始化进程控制块(PCB)。

初始化标识信息
初始化处理机状态信息
初始化处理机控制信息

(4) 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。

2、进程的终止

引起终止的事件

1）正常结束：

2）异常结束：

3）外界干预

操作员或操作系统干预
父进程请求
父进程中止

终止过程

3、进程的阻塞与唤醒

1. 引起进程阻塞和唤醒的事件

1) 请求系统服务
2) 启动某种操作
3) 新数据尚未到达
4) 无新工作可做

2. 进程阻塞过程

3. 进程唤醒过程

4、进程的挂起与激活

1. 进程的挂起

2. 进程的激活

5、出现过的原语

挂起 suspend

激活 active

阻塞 block

唤醒 wakeup

创建 create

4.进程同步
（进程同步的主要任务：使并发执行的诸进程之间能有效地
共享资源和相互合作，从而使程序的执行具有可再现性。）

1、基本概念

1. 两种形式的制约关系

1、共享资源（CPU\打印机）
2、输入进程和计算进程(一个用户作业涉及一组并发进程（输入、计算和输出进程）)

2. 临界资源—互斥访问

1、临界资源的定义

2、例子
生产者—消费者问题：

类型
（3个）

该问题的同步和互斥表现在哪些地方

实现代码

幻灯片48

3. 临界区
（访问共享数据的代码）

定义

并发执行的进程访问临界资源的
那段必须互斥执行的程序。

幻灯片51

访问过程

4. 同步机制应遵循的规则
（作用：协调各进程间的运行）

临界区外运行的进程不得阻塞其他进程进入。
任何两个进程不能同时处于其临界区。
不得使进程无限期等待在临界区之外。（饿死）
不能进入自己临界区时，应立即释放

2、硬件同步机制（了解）
（读写由一条指令完成
保证读写不被打断）

1. 关中断
（互斥）

实现过程

先测试锁的状态，
测试和关锁操作必须连续，不允许分开
测试锁之前关闭中断，因为有中断就又调度，有调度就又进程

优缺点

2、Test-and-Set
（测试并建立）

3、Swap

子主题

3、信号量(Semaphores)机制

简介

发展历程

1. 整型信号量
（忙等）

P:请求系统分配一个单位的资源
V:释放一个单位的资源

2. 记录型信号量

结构

PV操作

S的取值

3. AND型信号量
（对某类资源只能进行
一个单位的申请/释放）

思想

在wait中加入AND条件，又称AND同步或同时wait操作：

PV

4. 信号量集

引入的原因

几种特殊情况

4、信号量的应用

1. 利用信号量实现进程互斥

设S(mutex）为实现进程Pl、P2互斥的信号量，
由于每次只允许一个进程进入临界区，
所以S的初值应为1（即可用资源数为1)。
只需把临界区置于P(S)和V(S)之间，
即可实现两进程对临界资源的互斥访问。
其算法如下：

PV必须成对出现

互斥的实现是不同进程对同一信号量进行P、V操作，
一个进程在成功地对信号量执行了 P操作后进入临界区，
并在退出临界区后，由该进程本身对该信号量执行V操作,
表示当前没有进程进入临界区，可以让其他进程进入。

2、利用信号量实现同步

设S为实现进程P1、P2同步的公共信号量，初值为0。
进程P2中的语句y要使用进程P1中语句x的运行结果，
所以只有当语句x执行完成之后语句y才可以执行。
其实现进程同步的算法如下：

PV

互斥

同步

3. 利用信号量实现前趋关系

其中S1, S2, S3, …, S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。例如，为保证S1 -> S2、 S1 -> S3的前驱关系，应分别设置信号量a1、a2。同样，为了保证 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,应设置信号量bl、b2、c、d、e。

4、分析进程同步和互斥问题的方法步骤

https://www.cnblogs.com/duan-decode/p/9641071.html

总结

例题

定义一信号量S，初始值为20。S>0 S的值表示可继续进入售票厅的人数 S=0 表示售票厅中已有20名顾客 S<0 |S|的值为等待进入售票厅中的人数

x=5，y=12，z=9 x=5，y=3,z=4 x=5，y=7，z=9

http://www.cnblogs.com/littlecurl/p/PVoperation.html

5、管程机制（了解）
（新的进程同步工具）

1、基本信息

1.引入的原因

2、引入的目的

3、基本思想

将共享变量及对共享变量能够进行的所有操作集中在一个模块中。
（把信号量及其操作原语“封装”在一个对象内部）

4．管程的定义

5.管程的组成

6、管程示意图

7、管程与进程的区别

2. 条件变量

5.经典进程的同步问题

1、生产者—消费者问题

1、问题描述

每种类型中的同步问题和互斥问题分别是什么
互斥：生产者进程将产品放入一个缓冲区中；消费者可以从一个缓冲区取走产品去消费。
同步：当一个缓冲区为空时不允许消费者去取走产品，当一个缓冲区满时也不允许生产者去存入产品。
https://blog.csdn.net/woailuo453786790/article/details/51436799

2、涉及的基本概念

3、问题分析

生产者流程

消费者流程

4、解决方法

利用记录型信号量解决
（掌握）

https://blog.csdn.net/glinsha/article/details/6514781

http://www.cnblogs.com/MissXu/p/5483666.html

利用AND信号量解决
（了解）

利用管程解决
（不讲）

5、延伸问题

生产者和消费者里面都有两个P,两个V操作，
那么两个P操作可否调换顺序呢？V操作呢？
http://blog.jobbole.com/86709/

6、经典习题

https://blog.csdn.net/fuziwang/article/details/79767527

2、哲学家进餐问题
http://blog.jobbole.com/86709/

问题描述

约束条件

分析

解决方法
https://blog.csdn.net/u014304293/article/details/46004677

利用AND信号量解决

3、读者——写者问题（不讲）
http://blog.jobbole.com/86709/

问题描述

问题分析

解决方法

利用记录型信号量解决

利用AND信号量解决

用信号量解决同步互斥问题的
基本规律和一般步骤

需强调的几个问题

两种形式的制约关系

临界区和临界资源

同步机制应遵循的规则

空闲让进

6.进程通信
（进程之间的信息交换）

进程通信类型

低级进程通信

原因

效率低

对用户不透明

高级通信

共享存储器系统

基于共享数据结构的通信方式
（少量数据，低级）

基于共享存储区的通信方式
（大量数据，高级）

管道通信系统
（共享文件）

互斥

同步

确定对方是否存在

消息传递系统

实现方式

分类

直接通信方式

间接通信方式

客户机-服务器系统
（实现方法分三类）

套接字
（包括两类）

发展历史

类型

基于文件型
（类似于管道）

基于网络型

远程过程调用
（远程方法调用）

实现方式

主要步骤

消息传递通信的实现方式

直接消息传递系统

直接通信原语

消息格式

进程同步方式
(三种可能性）

发送接收进程阻塞

发送进程不阻塞，接收进程阻塞

发送接收均不阻塞

通信链路
（两种方式）

显式命令

系统原语

信箱通信
（间接）

直接消息传递系统实例
（发送进程利用Send原语，
将消息直接发送给接收进程；
接受进程则利用Receive原语接收消息。）

消息缓冲队列通信机制中的数据结构

(1)消息缓冲区

(2)PCB中有关通信的数据项

发送原语

接收原语

典型问题

消息缓冲队列通信机制应具有哪几方面的内容

比较直接通信方式和间接通信方式

7.线程的基本概念

基本概念

引入的原因

操作系统将进程独立性的两个属性分别赋予了两个不同实体:
拥有资源所有权的仍称为进程，而调度的单位称为线程，或轻量级进程。

线程的特点

线程状态

引入线程的好处

进程与线程的比较

多线程OS中的进程属性

8.线程的实现
（了解）

9.考研真题

选择

填空

简答