第二章 进程管理 2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 管程机制 2.6 进程通信

Presentation on theme: "第二章 进程管理 2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 管程机制 2.6 进程通信"— Presentation transcript:

1 第二章 进程管理 2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 管程机制 2.6 进程通信
第二章 进程管理 2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 管程机制 2.6 进程通信 2.7 线程的基本概念

2 2.1 进程的基本概念 一、程序的顺序执行及其特征 二、程序的并发执行及其特征 三、进程的描述 四、进程控制块 进程的引入
2.1 进程的基本概念 一、程序的顺序执行及其特征 二、程序的并发执行及其特征 三、进程的描述 进程的引入 进程的定义及基本特征 进程的状态及其转换关系 四、进程控制块

3 二、程序顺序执行及其特征 一个程序由若干程序段组成，这些程序段的执行必须是顺序的；同时程序与程序之间也必须顺序执行。 例： 特征：
1. 顺序性： 2. 封闭性：程序的执行结果不受外界因素的干扰。 3. 可再现性：只要程序执行时的环境和初始条件相同，其执行结果必然相同。 C1 P1 I1 I2 C2 P2 I为输入操作； C为计算操作； P为打印操作。 程序 程序2 重点介绍操作系统承上启下的作用

4 三、程序并发执行及其特征 多个程序同时在系统中运行，这些程序的执行在时间上 是重叠的，即前一程序的执行尚未结束，后一程序的执行已 经开始。
例： 程序与程序之间、程序段与程序段之间均可并发执行。 C1 P1 I1 I2 C2 P2 程序段之间顺序执行； 程序之间并发执行。 重点介绍操作系统承上启下的作用

5 特征： 2. 失去封闭性：某程序执行时，必然受到参与并发执行的其它程序的影响。
1. 间断性：程序执行有“执行--暂停--执行”的活动规律。 2. 失去封闭性：某程序执行时，必然受到参与并发执行的其它程序的影响。 3. 不可再现性 ：计算结果与并发程序执行速度有关。即同一程序，使用相同输入、在相同环境下运行，却可能获得完全不同的结果。 重点介绍操作系统承上启下的作用

6 分析：1）并发：A、B交替占用CPU执行；2）异步性
不可再现性的例子： 两个并发执行的程序A和B，如下所示： A：N:=N+1； B：print（N）； N:=0； 分析：1）并发：A、B交替占用CPU执行；2）异步性 导致： CPU交替执行A、B的语句时顺序可能不同！ 设某次循环前，N的值为8 CPU执 行顺序 2) print(N); N:=0; N:=N+1; 3) print(N); N:=N+1; N:=0; 1) N:=N+1; print(N); N:=0; 重点介绍操作系统承上启下的作用 打印结果： N的值：

7 四、 进程的描述 1、进程的引入 多道程序环境下，必须引入进程的例子： 编译程序C编译源程序1，执行到a时因某种原因无法继续，
四、 进程的描述 1、进程的引入 多道程序环境下，必须引入进程的例子： 编译程序C编译源程序1，执行到a时因某种原因无法继续， 致使CPU空闲，此时转去编译源程序2，执行到b。 begin b: a: end 编译程序C 源程序1 数据部分 源代码1 目标代码1 源程序2 源代码2 目标代码2

8 问题1：谁占用CPU执行？源程序1和2以什么身份出现？ 问题2：程序计数器PC中记录的是a 还是 b？
答案1：占用CPU执行的是编译程序C 。 源程序1和2是编译程序C的数据对象。 答案2：说不清程序计数器PC中记录的是a 还是 b。 引入进程后： 答案1：占用CPU执行的是分别是进程1和进程2。 源程序1和2分别是进程1和进程2的数据对象。 答案2：进程1占用CPU执行时，PC中记录的是a； 进程2占用CPU执行时，PC中记录的是 b。

9 引入进程： 进程2 进程1 begin ------- b:------- a:------- end 编译程序C 源程序1 源程序2
数据部分 源代码1 目标代码1 源程序2 源代码2 目标代码2

10 2、进程的定义与特征 定义： 进程：可并发执行的程序在一个数据集合上的运行过程，它 是系统进行资源分配和调度的一个独立单位。
一个进程的物理实体包括： 程序部分 数据部分 进程控制块PCB 特征： 1. 动态性 异步性 2. 并发性 结构特征 3. 独立性

11 3、进程与程序的区别 1、进程是动态的，程序是静态的：程序是有序代码的集 合；进程是程序的执行。通常进程不可在计算机之间
迁移；而程序通常对应着文件、静态和可以复制。 2、进程是暂时的，程序的永久的：进程是一个状态变化 的过程，程序可长久保存。 3、进程与程序的组成不同：进程的组成包括程序、数据 和进程控制块（即进程状态信息）。 4、进程与程序的对应关系：通过多次执行，一个程序可 对应多个进程；通过调用关系，一个进程可包括多个 程序。

12 程序与进程的对应关系 1：一个程序对应多个进程(多次执行) 源程序1 编译程序C 源程序2 begin ------- b:-------
进程2 进程1 begin b: a: end 编译程序C 源程序1 数据部分 源代码1 目标代码1 源程序2 源代码2 目标代码2

13 程序与进程的对应关系2： 一个进程可以包括多个程序(通过调用) 进程1（用户态） 进程1（核心态） 用 Main( ) 户 ----- 栈
------ open( ) Open( ) return 系统调用 进程1（用户态） 用 户 栈 进程1（核心态） 核 心

14 3、进程的状态 基本状态： 1.就绪状态（ready）：进程等待分配CPU。 系统中同时处于就绪状态的进程会排成就绪队列。
2.执行状态（running）：进程正占用CPU执行其程序中的指令。 在单处理机系统中，任何时刻至多只有一个进程处于执行状态。 3.阻塞状态（blocked）：进程在等待某个事件的发生，故也 称为等待状态（waiting）。 处于阻塞状态的进程会按等待原因进入不同的阻塞队列。 4.新状态（new）：进程正被创建。 5.终止状态（terminated）：进程已经结束执行。

15 基本状态间的转换： 进程的状态是在不断变换的。 新状态 终止状态 接收 退出 进程调度 就绪状态 执行状态 中断 I/O或事件发生
阻塞状态 新状态 终止状态 接收 进程调度 退出 中断 等待I/O或事件 I/O或事件发生

16 2.1 进程的基本概念 五、进程控制块PCB （Process Control Block） PCB中的信息 关于PCB：
2.1 进程的基本概念 五、进程控制块PCB （Process Control Block） 关于PCB： 定义：存放进程的管理和控 制信息的数据结构，是OS 感知进程存在的唯一标志。 创建进程时，为其建立 PCB，并伴随进程运行的全 过程，直到进程撤消而回收。 不同OS，PCB大小不同，包含信息不同。 PCB中的信息 进程标识符 进程状态 进程优先级 进程队列指针 执行程序和数据的内存开始地址 程序计数器 CPU寄存器 CPU现场保护区 进程通信 家族联系 占有资源清单 栈指针 I/O状态信息 打开文件表

17 2.1 进程的基本概念 五、进程控制块PCB（Process Control Block） 说明：
2.1 进程的基本概念 五、进程控制块PCB（Process Control Block） 说明： PCB只能由OS访问，不允许用户进程访问。 一个系统中的PCB数目是一定的，它规定了该系统可同时拥有的最大进程数目。 每个PCB是系统PCB表中的一个表目。 PCB表常驻内存，存放于OS中专门开辟的PCB区。

18 2.2 进程控制 一、进程的创建 二、进程的终止 三、进程的阻塞与唤醒 四、进程的挂起与激活

19 2.2 进程控制 进程是动态的，有它的开始和结束。在它的生命周期中，在 几种不同的状态之间转换。
2.2 进程控制 进程是动态的，有它的开始和结束。在它的生命周期中，在 几种不同的状态之间转换。 OS提供一些程序段实现这些转换。这些程序段必须用机器 语言书写，且在执行中不可被中断。 原语（Primitive）：指用机器语言书写的、在执行中不可被 中断的程序段。 原语属于OS内核（Kernal）。 完成进程控制的原语有：创建(Create)、终止(Termination)、 阻塞(Blocked)、唤醒(Wakeup)、挂起（Suspend)、激活（Active)等。 回顾后图，解释并行和并发的区别。

20 2.2 进程控制 一、进程的创建（Creation） 说明：
2.2 进程控制 一、进程的创建（Creation） 导致创建新进程的事件： 1.批处理系统中，接收了一个新作业。 2.分时系统中，用户登录。 3.运行中的用户程序提出某种服务请求。 4.基于应用进程自身的需要。 OS作为创建者 应用进程作为创建者 说明： 1）一个应用进程在其执行期间，通过执行创建进程系统调用命令（例如fork），可以创建几个新进程。 2）而最终进程的创建，是由进程创建原语create( )实现的。 简单解释方式的不同

21 2.2 进程控制 一、进程的创建（Creation）
2.2 进程控制 一、进程的创建（Creation） 3）创建者是父进程，被创建的新进程是子进程。子进程可以创建子子进程，如此轮流下去，构成一棵进程家族树。 4）父、子进程的执行有两种可能性： -- 父进程和子进程并发执行； -- 父进程等待，直到子进程结束。 简单解释方式的不同

22 2.2 进程控制 Create（）工作流程： 入口 填写PCB的相关项 将PCB链入就绪队列 返回 出错 申请内存空间 装入程序和数据
2.2 进程控制 Create（）工作流程： 入口 填写PCB的相关项 将PCB链入就绪队列 返回 出错 申请内存空间 装入程序和数据 申请空白PCB 分配其它资源 申请到 申请不到 简单解释方式的不同

23 2.2 进程控制 二、进程的终止（ Termination ） 当最后一条语句运行结束时，一个进程终止。此时它使
2.2 进程控制 二、进程的终止（ Termination ） 当最后一条语句运行结束时，一个进程终止。此时它使 用相应的系统调用命令（如exit）请求OS将其撤消。 在许多系统中，若一个进程终止，则其子孙进程也必须 同时被终止。 终止原语的主要操作包括： 1）按照被终止进程的标识符找到其PCB； 2）将其运行的结果信息返给其父进程； 3）将其所占资源或归还系统，或还给其父进程； 4）将其PCB置为空； 5）若被终止进程处于执行状态，则引发进程调度； 6）若被终止进程有子孙进程，则将其子孙进程同时终止。 简单解释方式的不同

24 2.2 进程控制 三、进程的阻塞（blocked）和唤醒（wakeup） 执行状态进程遇到下列典型事件时，调用blocked（）原语
2.2 进程控制 三、进程的阻塞（blocked）和唤醒（wakeup） 执行状态进程遇到下列典型事件时，调用blocked（）原语 将自己阻塞： 1.没有申请到资源； 启动了I/O操作； 3.运行所需数据尚未到达。 当阻塞进程所等待的事件发生时，就会被唤醒。 阻塞过程： 1）进程状态置为阻塞状态，并移入相应的阻塞队列； 2）引发进程调度。 唤醒过程： 进程状态置为就绪状态，并移入就绪队列。 简单解释方式的不同

25 2.2 进程控制 总结： 进程控制原语与进程状态转换的对应： 新状态 终止状态 create termination 进程调度 就绪状态
2.2 进程控制 总结： 进程控制原语与进程状态转换的对应： 执行状态 就绪状态 阻塞状态 新状态 终止状态 create 进程调度 termination 中断 blocked wakeup

26 2.2 进程控制 四、进程的挂起（suspend）和激活（active） 进程遇到下列典型事件时，调用suspend（）原语将自己挂起：
2.2 进程控制 四、进程的挂起（suspend）和激活（active） 进程遇到下列典型事件时，调用suspend（）原语将自己挂起： 1.终端用户的请求； 父进程请求； 3.负荷调节的需要； 操作系统的需要 。 当发生激活进程的事件时，就会被激活。 挂起过程： 1）检查被挂起进程的状态，并改成对应的状态； 2）把该进程的PCB复制到某指定的内存区域； 3）若挂起的进程正在执行，则引发进程调度。 激活过程： 将进程从外存调入内存，检查该进程的现行状态，并改成对应的状态；

27  2.2 进程控制 UNIX系统实例：1-进程家族树 1.系统初启后，由系统核 心程序建立init进程。init
2.2 进程控制 UNIX系统实例：1-进程家族树 init login shell  终端2 cp 终端1 终端0 1.系统初启后，由系统核 心程序建立init进程。init 进程读取文件/etc/ttys，该 文件告诉系统共有几个终 端并提供每个终端的说明。 init进程将为每个终端生成 一个子进程，然后将自己 挂起直到有子进程结束。 2.每个子进程等待用户登记（login）使用系统，接着执行shell命令解释程序。 3.上图系统中有三个终端。运行在终端0上的子进程仍在等待用户登录；在终 端1上的子进程已成功登录了用户，正运行shell等待命令输入；在终端2上的 子进程也成功登录了用户，该用户正运行cp程序，cp是shell的子进程，shell 则 等待该进程结束。cp结束后，shell再接收输入，创建新进程执行新输入命令。 简单解释方式的不同

28 2.2 进程控制 UNIX系统实例：2-相关系统调用 1. fork系统调用： 功能：建立子进程
2.2 进程控制 UNIX系统实例：2-相关系统调用 1. fork系统调用： 功能：建立子进程 返回值：fork对子进程返回0，对父进程返回子进程的标识符。 具体描述：子进程是父进程的一个副本，这就允许父进程可以很容易地 与子进程通信。父子进程都从fork后的那条指令继续执行。 2. exec系统调用： 输入参数：新程序名， 功能：以指定程序覆盖当前进程的程序代码。 3. wait系统调用： 输入参数：进程号 功能：等待指定进程结束。 简单解释方式的不同

29 2.2 进程控制 UNIX系统实例：3-shell的内部部分代码  显示命令提示符 等待用户输入命令行
2.2 进程控制 UNIX系统实例：3-shell的内部部分代码  显示命令提示符 等待用户输入命令行 对命令行分析和解释，得到要运行的程序（例如cp）及其运行参数 if ((pid=fork( ))<0 ){ /*fork失败*/ } else if ( pid>0 ) { /*父进程代码，典型地如：*/ wait ( pid ); /*等待该子进程结束*/ 显示下一个命令提示符 else { /*子进程代码，典型地如：*/ exec(cp, ); 简单解释方式的不同

30 2.3 进程同步 一、进程同步的基本概念 二、信号量机制

31 2.3 进程同步 进程同步的任务： 使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。
参照下页说明：硬件中起指挥作用的是CPU，而CPU的所有动作是软件执行的结果。软、硬件间的关系。

32 多道程序环境下，诸进程之间的关系： 相互独立 彼此有关 进程同步 每个进程既不影响系统中其它进程的执行，也不被其它进程影响。 具体表现为：
1）进程之间由于共享资源而产生的间接制约关系。 2）进程之间由于相互合作而产生的直接制约关系。 进程同步 解决1）的方法是：保证诸进程互斥访问临界资源。 解决2）的方法是：协调相互合作的诸进程的执行次序。 ---狭义的同步 参照下页说明：硬件中起指挥作用的是CPU，而CPU的所有动作是软件执行的结果。软、硬件间的关系。

33 一、 进程同步的基本概念 1、临界资源 2、临界区 重点介绍操作系统承上启下的作用

34 一、 进程同步的基本概念 1、临界资源 临界资源：一段时间内只允许一个进程访问的资源。 要求：共享临界资源的诸进程必须互斥访问临界资源。
一、 进程同步的基本概念 1、临界资源 临界资源：一段时间内只允许一个进程访问的资源。 要求：共享临界资源的诸进程必须互斥访问临界资源。 原因： 例：生产者--消费者问题（P48） 生产者（producer）  放产品； counter:=counter+1; 消费者（consumer）  取产品； counter:=counter-1;

35 一、 进程同步的基本概念 1、临界资源 生产者 消费者 由于生产者和消费者并发运行，且共享变量 counter ，造成： 机器语言形式为：
一、 进程同步的基本概念 1、临界资源 机器语言形式为： 生产者 counter:=counter+1;----CS  1 register1:=counter; 2 register1:= register1+1; 3 counter:= register1; 消费者 counter:=counter-1;----CS  4 register2:=counter; 5 register2:= register2-1; 6 counter:= register2; 由于生产者和消费者并发运行，且共享变量 counter ，造成： 重点介绍操作系统承上启下的作用 可能性 CPU执行顺序 counter的值 （初值为5） A 123456 5 正确 B 456123 C 124536 4 不正确 D 451236 6 不是A、B 

36 一、 进程同步的基本概念 1、临界资源 结论： counter是临界资源，生产者和消费者应互斥访问。
一、 进程同步的基本概念 1、临界资源 结论： counter是临界资源，生产者和消费者应互斥访问。 即：虽然生产者、消费者并发执行，但在执行counter的加1、减1的语句时，只能顺序进行。 即：只能按可能性中A或B的顺序进行，绝不能交替进行。 临界资源实例： 硬件中的打印机、磁带机等，软件中的变量、队列、缓冲区等。 重点介绍操作系统承上启下的作用

37 一、 进程同步的基本概念 2、临界区 临界区（CS）：每个进程中访问临界资源的那段代码。
一、 进程同步的基本概念 2、临界区 临界区（CS）：每个进程中访问临界资源的那段代码。 要求：为实现对临界资源的互斥访问，应保证诸进程互斥进入各自的临界区。（两个互斥是一致的） 模型： 准则：1.空闲让进 忙则等待 有限等待 让权等待 repeat entry section 进入区：检查是否可以进入临界区 critical section 临界区：对临界资源进行操作 exit section 退出区：释放临界资源以供其它进程使用 remainder section 剩余区： until false 重点介绍操作系统承上启下的作用

38 1、记录型信号量机制 2、AND型信号量集机制 1965年，荷兰科学家Dijkstra在THE系统上提出。
二、信号量机制 1、记录型信号量机制 2、AND型信号量集机制 1965年，荷兰科学家Dijkstra在THE系统上提出。 一个信号量S是一个整型量，除对其初始化外，它只能 由两个原子操作P和V来访问。 P和V的名称来源于荷兰文proberen（测试）和verhogen （增量），它们的执行具有不可中断性。 本书中将P、V操作称做 wait 和 signal 操作。

39 二、信号量机制 1、记录型信号量机制 定义： 信号量：type semaphore=record
value:integer; /*信号量的值 L:list of process; /*信号量等待队列的队首指针 end P(s): s.value:=s.value-1; if s.value<0 then blocked(s.L); V(s): s.value:=s.value+1; if s.value0 then wakeup(s.L);

40 关于记录型信号量机制的几点说明 1、S.value为正时表示资源的个数；S.value为负时表示等待进程的个数
2、 P操作分配资源； V操作释放资源。

41 二、信号量机制 1、记录型信号量机制 实现进程互斥： 模型：一个临界资源一个互斥信号量mutex（初值=1）
需互斥访问该临界 P(mutex);----进入区 资源的每个进程中 CS; V(mutex);----退出区 实例：三个进程执行中要共享变量count。 分析：count属于临界资源，对其应互斥访问。 提问：1.mutex的取值范围？ 2.进程被唤醒后，执行哪条语句？ 取值范围：[-2，1] P操作下一条语句

42 二、信号量机制 1、记录型信号量机制 count:=count+2; var mutex:semaphore:=1; begin
parbegin process1:begin repeat P(mutex); count:=count+1; V(mutex); until false; end process2:begin 1 count:=count+2; V(mutex); until false; end process3:begin repeat P(mutex); count:=count-1; parend 2

43 二、信号量机制 1、记录型信号量机制 模型：一类资源一个公用信号量s（初值=0..n） 请求资源的进程中：P(s);
实现进程同步： 模型：一类资源一个公用信号量s（初值=0..n） 请求资源的进程中：P(s); 释放资源的进程中：V(s); 实例：进程A和B合作。 A B   取数据；  计算数据； 送数据；

44 二、信号量机制 1、记录型信号量机制 var s:semaphore:=0; 执行时两种可能性： 1. 在进程B还没有送数据之前，进程
parbegin processA:begin  P(s); 取数据； 计算数据; end processB:begin 送数据； V(s); parend 执行时两种可能性： 1. 在进程B还没有送数据之前，进程 A先执行了P(s)，结果会怎样？ 2. 进程B的V(s)操作已经完成，进程A 才执行了P(s)，结果会怎样？ 1.进程A执行P(s)，会使自己进入阻 塞状态，直至进程B送数据后执行 V(s) ，才能将它唤醒。 2. 若进程B的V(s)操作已经完成，进 程A才执行了P(s)，则进程A不会 阻塞。它可以顺利地取到数据，完 成下面的操作。

45 二、信号量机制 1、记录型信号量机制 一、前趋图 有向无循环图DAG，包括： 定义： 结点：可表示一个语句、程序段或进程；
包括 初始结点：无前趋 终止结点：无后继 有向边：两结点间的前趋关系； pipj：pi必须在pj开始执行之前完成 pi为pj的直接前趋， pj为pi的直接后继。 注：前趋图中必须不存在循环！ 参照下页说明：硬件中起指挥作用的是CPU，而CPU的所有动作是软件执行的结果。软、硬件间的关系。

46 ={(p1,p2),(p1,p3),(p2,p4),(p3,p5),(p4,p5)}
s1 s2 s3 正确例子： P={p1,p2,p3,p4,p5} ={(p1,p2),(p1,p3),(p2,p4),(p3,p5),(p4,p5)} 错误例子： s2s3, s3s2

47 描述进程前趋关系： 实例： a b c d e Var a,b,c,d,e:semaphore:=0,0,0,0,0; begin
parbegin process p1: begin  ; V(a); V(b); end; process p2: begin P(a);  ; V(c); end; process p3: begin P(b);  ; V(d); end; process p4: begin P(c); P(d);  ; V(e); end; process p5: begin P(e);  ; end; parend end p1 p2 p3 p4 p5 e a b c d

48 二、信号量机制 1、记录型信号量机制 描述进程前趋关系： 模型： 与进程同步类似；不同点： 1.信号量s的初值=0；
2.若等信号，则在开始处执行P(s)； 3.若发信号，则在最后处执行V(s)；

49 二、信号量机制 1、记录型信号量机制 物理含义： 信号量的值s.value：
表示系统中某类可用资源的数目。s.value0，表示还有此类资源可供分配；s.value0，表示资源已分配完毕， 其绝对值表示s.L链表中阻塞进程的数目。 P(s)：请求一个单位的资源。 V(s)：释放一个单位的资源。 注：对一个信号量的P、V操作必是成对出现的，有可能集中在一个进程中，也有可能分布在不同进程中。

50 二、信号量机制 2、AND型信号量集机制 定义： swait (s1,s2, ,sn )
if s11 and  and sn 1 then for i:=1 to n do si:=si-1; endfor else place the process in the waiting queue associated with the first si found with si 1,and set the PC of this process to the beginning of swait operation. endif; ssignal (s1,s2, ,sn ) for i:=1 to n do si:=si+1; remove all the process waiting in the queue associated with si into the ready queue. endfor;

51 二、信号量机制 2、AND型信号量集机制 与记录型信号量的区别： 1. 一次同时对多个信号量进行判定；
2. 所处阻塞队列是第一个不满足条件的信号量的阻塞队列； 3. 阻塞后其程序计数器被拨回到swait开始位置； 4. ssignal时，将全部信号量阻塞队列中的全部阻塞进程唤醒。 基本思想： 资源一次性分配（要么全分配，要么一个也不分配）， 进程用完后再一起释放。

52 2.4 经典进程同步问题 一、生产者--消费者问题 二、读者--写者问题 三、哲学家就餐问题

53 2.4 经典进程同步问题 一、生产者--消费者问题
2.4 经典进程同步问题 一、生产者--消费者问题 问题描述： 一群生产者进程在生产消息，并将此消息提供给消费者进程去消费。为使生产者进程和消费者进程能并发执行，在它们之间设置了一个具有个n缓冲区的缓冲池，生产者进程可以将它所生产的消息放入一个缓冲区中，消费者进程可以从一个缓冲区中取得一个消息消费。规定：不允许消费者进程到一个空缓冲区中取消息，也不允许生产者进程向一个已装有消息且尚未被取走消息的缓冲区中投放消息。 简单解释方式的不同 一组生产者 一组消费者   1 n-1 in 顺序放 顺序取 out

54 2.4 经典进程同步问题 一、生产者--消费者问题
2.4 经典进程同步问题 一、生产者--消费者问题 利用记录型信号量解决 1.基本工作：生产者：生产消息；放消息。 消费者：取消息；消费消息。 2.互斥：临界资源（缓冲池）一个互斥信号量mutex（初值=1） 3.同步：生产者：放 有空缓冲区：放 无空缓冲区：阻塞 消费者：取 有满缓冲区：取 无满缓冲区：阻塞 唤醒 简单解释方式的不同 设两个公用信号量 empty：空缓冲区的数目（初值=n） full： 满缓冲区的数目（初值=0）

55 Var mutex, empty, full:semaphore:=1, n, 0;
buffer:array[0..n-1] of item; in, out:integer:=0, 0; begin parbegin producer: repeat until false; end consumer: begin repeat until false end parend P(full); V(empty); P(mutex); V(mutex); nextc:=buffer(out); out:=(out+1) mod n; consume an item in nextc; produce an item in nextp; buffer(in):=nextp; in:=(in+1) mod n; P(empty); V(full); P(mutex); V(mutex);

56 2.4 经典进程同步问题 一、生产者--消费者问题
2.4 经典进程同步问题 一、生产者--消费者问题 注意：要先对公用信号量执行P操作，再对互斥信号量执行 P操作，否则可能引起死锁!!! 例：分别交换生产者进程中以及消费者进程中的两个P操作的顺序。当mutex=1，empty=0，full=n 时，生产者先占用CPU执行，结果会怎样？ 交换两个V操作不 会有任何问题。 生产者： 消费者： P(mutex); P(mutex); P(empty); P(full); 放消息； 取消息； V(mutex); V(mutex); V(full); V(empty); 简单解释方式的不同 还有一种引发死锁的可能性，是什么？

57 2.4 经典进程同步问题 一、生产者--消费者问题
2.4 经典进程同步问题 一、生产者--消费者问题 利用AND型信号量解决：（不会引发死锁） begin parbegin producer: repeat produce an item in nextp; swait(empty, mutex); buffer(in):=nextp; in:=(in+1) mod n; ssignal(mutex, full); until false; end consumer: begin repeat swait(full, mutex); nextc:=buffer(out); out:=(out+1) mod n; ssignal(mutex, empty); consume an item in nextc; until false end parend 简单解释方式的不同

58 2.4 经典进程同步问题 二、读者—写者问题 问题描述：
2.4 经典进程同步问题 二、读者—写者问题 问题描述： 一个数据对象可被多个进程共享。其中有些进程要求读；另一些进程要求写或修改。我们把只要求读的进程称为 “reader进程”，其它称为“writer进程”。允许多个reader进程同时读共享的数据对象，但绝不允许一个 writer进程和其它writer进程或reader进程同时访问该共享的数据对象。（多个读者和多个写者间的关系） 简单解释方式的不同

59 利用记录型信号量解决 2.4 经典进程同步问题 二、读者—写者问题 1.基本工作： reader（读者）：读数据对象。
2.4 经典进程同步问题 二、读者—写者问题 利用记录型信号量解决 1.基本工作： reader（读者）：读数据对象。 writer（写者）：写数据对象。 2.同步：无，因要求中没有说明读者和写者要合作。 3.互斥：  数据对象互斥信号量wmutex（初值=1），用于读者进程和写者进程互斥访问数据对象。 写者--与其它写者、所有读者都要互斥。 读者--可与其它读者同时读（不互斥），但要与所有写者互斥。 简单解释方式的不同

60 2.4 经典进程同步问题 二、读者—写者问题 利用记录型信号量解决 其它读者在读，该读者可进入 正在读 写者想进入写，该写者阻塞
2.4 经典进程同步问题 二、读者—写者问题 利用记录型信号量解决 某个读者：想进入读 写者正在写，该读者阻塞 其它读者在读，该读者可进入 正在读 写者想进入写，该写者阻塞 其它读者想进入读，可以进入 故读者：进入时判断写者是否在内，读完后要释放数据对象。 第一个要求进入的读者 最后一个离开的读者 增加变量readcount，来表示正在读的读者数目。 由于多个读者共享readcount ，故也应作为临界资源处理。 设互斥信号量rmutex（初值=1），用于读者互斥访问readcount。 简单解释方式的不同

61 Var rmutex, wmutex:semaphore:=1, 1; readcount:integer:=0;
begin parbegin reader: begin repeat P(rmutex); if readcount=0 then P(wmutex); readcount:=readcount+1; V(rmutex);  perform read operation; readcount:=readcount-1; if readcount=0 then V(wmutex); V(rmutex); until false end writer:begin repeat P(wmutex); perform write operation; until false; parend

62 提问： 2.4 经典进程同步问题 二、读者—写者问题
2.4 经典进程同步问题 二、读者—写者问题 提问： 1.reader中的第一个signal(rmutex)和第二个 wait(rmutex) 能否去掉？ 2.若一个写者进程正在写数据对象，问每个读者进程和其它写者进程所在位置？（要求从状态、所在队列及执行到哪个语句三方面来说明） 简单解释方式的不同

63 2.4 经典进程同步问题 三、哲学家进餐问题 问题描述： 3 2 1 4
2.4 经典进程同步问题 三、哲学家进餐问题 问题描述： 有5位哲学家，他们的生活方式是交替进行思考和就餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五支筷子，每个哲学家饥饿时必须拿到其左、右最靠近他的各一支筷子时才能就餐。进餐毕，放下筷子又继续思考。 1 2 3 4 示意图 简单解释方式的不同

64 一支筷子(编号为i])一个互斥信号量chopstick[i]（初值=1）。
2.4 经典进程同步问题 三、哲学家进餐问题 利用记录型信号量解决 1.基本工作：哲学家：思考；就餐。 2.同步：无。 3.互斥：临界资源是筷子 一支筷子(编号为i])一个互斥信号量chopstick[i]（初值=1）。 简单解释方式的不同 提问：此算法有无问题？如何解决？

65 2.4 经典进程同步问题 三、哲学家进餐问题 var chopstick: array [0..4] of semaphore:=1, 1, 1, 1, 1; begin parbegin process i ( i=0, 1, 2, 3, 4): begin repeat think; P(chopstick[i]); P(chopstick[i+1] mod 5); eat; V(chopstick[i]); V(chopstick[i+1] mod 5); until false; end parend 简单解释方式的不同

66 2.5 管程机制 一、管程的定义 二、互斥和同步 三、利用管程解决生产者--消费者问题
2.5 管程机制 一、管程的定义 二、互斥和同步 三、利用管程解决生产者--消费者问题 信号量机制为互斥、同步问题的解决提供了有效和灵活的工具，但用信号量编写一个正确的程序比较困难。 Hoare(1974)和Hansen(1975)提出了一种高级的同步原语，称为管程。 管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。

67 2.5 管程机制 一、管程的定义 管程：管程是一个由一或多个过程、初始化代码及局部变
2.5 管程机制 一、管程的定义 管程：管程是一个由一或多个过程、初始化代码及局部变 量组成的集合。OS为每个共享资源设立一个管程,由用户编写(类似于”面向对象”的观点)其主要特性如下： 1. 局部于管程的变量仅能被管程内部的过程访问，而不能 被任何外部过程访问。 2. 一个进程通过调用管程内的一个过程而进入管程。 3. 任一时刻管程中只能有一个活跃进程。即任一时刻只能 有一个进程在管程中执行，其它想进入管程的进程阻塞， 等待管程可用。

68 2.5 管程机制 一、管程的定义 管程的描述： 管程的示意图： type monitor-name=monitor
2.5 管程机制 一、管程的定义 管程的描述： type monitor-name=monitor variable declaration; procedure entry p1(); begin  end; procedure entry p2();  procedure entry pn(); begin initialization code; end 管程的示意图： 共享数据 操作过程 初始化代码 进入队列  x y 相应于条件变 量x和y的队列

69 2.5 管程机制 二、互斥与同步 互斥： 管程的第3个特性，使它们能有效的完成互斥。 进入管程时的互斥由编译器负责，写管程的人无需关心。
2.5 管程机制 二、互斥与同步 互斥： 管程的第3个特性，使它们能有效的完成互斥。 进入管程时的互斥由编译器负责，写管程的人无需关心。 同步： 条件变量及两个相关操作wait和signal 条件变量（condition variables） x ：表示等待原因。 x.wait：执行该操作的进程阻塞，直至其它进程执行x.signal。 x.signal：唤醒x等待队列中的一个进程。如果x等待队列中无进 程阻塞，该操作不产生任何作用。

70 2.5 管程机制 二、互斥与同步 说明： 进程Q因执行x.wait处于阻塞状态，后来进程P执行了x.signal而将进程Q唤醒。为了避免管程中同时有两个活跃进程，需要有一条规则来决定让P和Q谁执行、谁阻塞。 处理方式1：P执行；Q等待。 处理方式2：Q执行；P等待。（Hoare采用） 处理方式3：执行signal的进程必须立即退出管程，即signal语句只可能作为一个管程过程的最后一条语句。(Hansen建议)

71 2.5 管程机制 三、利用管程解决生产者--消费者问题
2.5 管程机制 三、利用管程解决生产者--消费者问题 管程定义 type producer-consumer=monitor var in,out,count: integer; buffer: array[0..n-1] of item; notfull,notempty: condition; procedure entry put(item) begin if count n then notfull.wait; buffer(in):=item; in:=(in+1) mod n; count:=count+1; if count=1then notempty.signal; end procedure entry get(item) begin if count 0 then notempty.wait; item:=buffer(out); out:=(out+1) mod n; count:=count-1; if count=n-1then notfull.signal; end in:=out:=0; count:=0;

72 2.5 管程机制 三、利用管程解决生产者--消费者问题
2.5 管程机制 三、利用管程解决生产者--消费者问题 进程调用 producer: begin repeat produce an item in nextp; producer-consumer.put(nextp); until false; end consumer: begin producer-consumer.get(nextc); consume the item in nextc;

73 2.6 进程通信 进程通信IPC（Inter Process Communication） 指合作进程之间的信息交换。 方式：
2.6 进程通信 进程通信IPC（Inter Process Communication） 指合作进程之间的信息交换。 方式： 1. 低级通信方式：信号量和管程 信号量的缺点：一次只传递一个信号量，大量信息的传递需借助共享数据结构进行，而共享数据结构的定义和操作以及同步控制均要由程序员自己实现。 管程的缺点：管程在少数几种编程语言以外无法使用。 2. 高级通信方式：例如消息传递系统 优势：一次可以传递大量信息；进程中使用通信命令即可通信；通信过程由OS实现。 作为同步工具有效，作为通信工具低级

74 2.6 进程通信 一、消息传递系统（Message Passing System）
说明： 消息传递系统至少要提供两个操作：发送消息send(message) 和接收消息receive(message)。 如果进程P和Q想要通信，它们必须互相发送消息和接收消息；并且在它们之间一定存在着一条通信链路（communication link）。 通信链路和send/receive操作的逻辑实现方法： 直接或间接通信 对称或非对称地址 有容量或无容量的缓冲区 定长或变长消息

75 2.6 进程通信 一、消息传递系统（Message Passing System）
直接通信： 要通信的每个进程必须明确指出发送进程或接收进程的标识符。 send和receive原语的格式： send ( P, message )---发送消息给进程P； receive ( Q, message)---接收来自进程Q的消息。 通信链路的性质： 1. 要通信的一对进程之间的通信链路是自动建立的。进程只需 知道彼此的标识符。 2. 一条链路只连接一对进程。（点到点连接） 3. 每对进程之间只存在一条链路。

76 2.6 进程通信 一、消息传递系统（Message Passing System）
这种send/receive原语展示的是对称地址。即发送进程和接 收进程都要指出对方的标识符。 非对称地址方式下send和receive原语的格式： send ( P, message )---发送消息给进程P； receive ( id, message)---接收从任一进程发来的消息。Id是 receive操作的返回值，表示本次接收来的消息的发送者是谁。 直接通信的缺点： 一个进程的标识符发生改变，则与之通信的所有进程都要 修改 通信原语中的相应标识符。

77 2.6 进程通信 一、消息传递系统（Message Passing System）
间接通信： 通信进程利用信箱传递消息。但只有在获得一个可共享的信箱 的前提下，进程间才可通信。 send和receive原语的格式： send ( A, message )---将消息发送到信箱A； receive ( A, message)---从信箱A接收消息。 通信链路的性质： 1. 仅当要通信的一对进程具有可以共享的信箱时，通信链路 才能建立。 2. 一条链路可以连接多个进程。（多点连接） 3. 每对通信进程之间可以存在多条链路，但每条链路上只有 一个信箱。

78 2.6 进程通信 一、消息传递系统（Message Passing System）
信箱： 每个信箱的标识符是唯一的。 信箱的拥有者可以是OS，也可以是用户进程。归OS所有的信箱是 独立的，它不附属于任何进程。 如果OS提供了有关信箱的创建、撤消及通过信箱发送和接收消息的原语，则一个用户进程可为自己建立一个信箱，它就是该信箱的拥有者。当它终止时，该信箱自动消失。 进一步说明： 1. 要区分信箱的拥有者（只能从该信箱接收消息）和使用者（只能向该信箱发消息）。 2. 信箱创建后，其所有权和接收权可以通过系统调用命令传递给其它进程，这就可能导致一个信箱有多个接收者。

79 2.6 进程通信 一、消息传递系统（Message Passing System）
发送进程和接收进程的同步问题： 实现send和receive的不同策略（同步或异步）： 阻塞发送进程 发送进程发送消息后阻塞，直至消息被接收进程或信箱接收。 不阻塞发送进程 发送进程发送消息后，继续执行。 阻塞接收进程 接收进程阻塞直至消息到达。 不阻塞接收进程 接收进程接收消息时，不管收到还是收不到消息，都继续执行。 具体实现时，可采用不同的组合方式。如果发送进程和接收进程都阻塞，则叫会合（rendezvous）。

80 2.6 进程通信 一、消息传递系统（Message Passing System）
缓冲区： 不管通信是直接的还是间接的，通信进程交换的消息都会临时放置在通信链路中设置的缓冲区内。缓冲区分为三种方式： 无容量缓冲区 缓冲区长度为0，因此不能暂存任何消息。 这种情况下，发送进程必须阻塞，直至接收方接收消息。 有容量缓冲区 1.有界缓冲区：缓冲区长度为n，故可暂存n条消息。缓冲区不满时，发送进程可连续发送；满时，发送进程必须阻塞。 2.无界缓冲区：缓冲区长度无限，故可暂存任意多条消息。发送进程从不阻塞。

81 2.6 进程通信 二、示例：生产者-消费者问题 begin 采用间接通信方式： repeat const
2.6 进程通信 二、示例：生产者-消费者问题 采用间接通信方式： const capacity=;/*信箱的容量 null=;/*空消息 var i:integer; procedure producer; var pmsg:message; begin repeat receive(mayproduce,pmsg); pmsg:=produce; send(mayconsume,pmsg); until false; end produce consumer; var cmsg:message; begin repeat receive(mayconsume,cmsg); consume(cmsg); send(mayproduce,null); until false end creat box(mayproduce); create mailbox(mayconsume); for i=1 to capacity do parbegin producer; consumer; parend

82 2.7 线程的基本概念 一、线程的引入 引入进程：使多个程序并发运行。 进程：1.拥有资源的独立单位； 2.独立调度和分派的基本单位。
2.7 线程的基本概念 一、线程的引入 引入进程：使多个程序并发运行。 进程：1.拥有资源的独立单位； 2.独立调度和分派的基本单位。 进程是可独立运行的基本单位，这正是并发的基础。 但也由于1和2，使系统在创建、撤消进程及进行进程切换 时须付出较大的时空开销。 系统会限制参与并发运行的进程数目及切换频率。 限制了更高程度上的并发。 观点1回顾1.1.3；观点2是自底向上的观点；观点3是自顶向下的观点。

83 2.7 线程的基本概念 一、线程的引入 引入线程：减少程序并发执行时的时空开销，使并发性更好。 将进程的两个属性分开。
2.7 线程的基本概念 一、线程的引入 引入线程：减少程序并发执行时的时空开销，使并发性更好。 将进程的两个属性分开。 进程：拥有资源的独立单位； 线程：进程中的一个实体，是独立调度和分派的基本单位。 ----轻型进程 线程包含一个线程ID、一个程序计数器、一组寄存器和栈； 它可与其它线程共享所属进程的全部资源。 观点1回顾1.1.3；观点2是自底向上的观点；观点3是自顶向下的观点。

84 2.7 线程的基本概念 一、线程的引入 传统操作系统中使用的是单线程（single-threaded）方法，即每个
2.7 线程的基本概念 一、线程的引入 传统操作系统中使用的是单线程（single-threaded）方法，即每个 进程中只包含一个线程，因而线程的概念不被认识。例， MS-DOS：每次只允许一个进程运行，该进程中含一个线程。 UNIX：允许多个进程并发运行，每个进程中只有一个线程。 多线程指操作系统支持在同一进程中的多个线程的并发运行。 Windows NT、Solaris和OS/2等操作系统使用支持多个进程并发 运行，且支持同一进程中多个线程并发运行的方法。 许多在现代台式PC机上运行的软件包也是多线程的。例如一个字 处理软件可以有一个线程去显示图形，另一线程去读用户键入的 字符，第三个线程在后台执行拼写和语法检查。 观点1回顾1.1.3；观点2是自底向上的观点；观点3是自顶向下的观点。

85 2.7 线程的基本概念 二、用户级线程和内核支持线程 内核支持线程 用户级线程 P P 线程目录 进程 用户空间 内核空间 线程 用户空间
2.7 线程的基本概念 二、用户级线程和内核支持线程 线程目录 进程 用户空间 P 内核空间 线程 用户级线程 用户空间 P 内核空间 线程 内核支持线程 观点1回顾1.1.3；观点2是自底向上的观点；观点3是自顶向下的观点。

86 2.7 线程的基本概念 用户级线程 内核支持线程 仅存在于用户空间，创建、撤消和切换在 用户进程中的线程、系统进程中的线程，
2.7 线程的基本概念 用户级线程 仅存在于用户空间，创建、撤消和切换在 用户空间完成，内核不知道其存在。 优点： 1.线程切换时，CPU执行状态维持在目态。 2.可根据需要采用合适的线程调度算法， 而不用怕扰乱内核的进程调度算法。 3.可在任何OS上运行。 缺点： 1.线程执行系统调用命令，其所属进程 被阻塞。 2.内核每次将CPU分配给一个进程，故 该进程中只有一个线程可运行。线程 多时速度慢。 内核支持线程 用户进程中的线程、系统进程中的线程， 其创建、撤消和切换均由内核完成。 优点： 1.克服了用户级线程的缺点。 2.内核例程自身也可是多线程的。 缺点： 1.将控制在同一进程中的两个线程间切 换时，CPU执行状态将发生改 观点1回顾1.1.3；观点2是自底向上的观点；观点3是自顶向下的观点。