（四）进程互斥 一、进程互斥的概念 1. 临界资源 例1：两个进程A、B共享一台打印机

Presentation on theme: "（四）进程互斥 一、进程互斥的概念 1. 临界资源 例1：两个进程A、B共享一台打印机"— Presentation transcript:

1 （四）进程互斥 一、进程互斥的概念 1. 临界资源 例1：两个进程A、B共享一台打印机
若不加以控制，两个进程的输出结果可能交织在一起，很难区分。 例2：两个进程共享一个变量x 设： x代表某航班已卖出的机座数，初值为0。p1和p2为两个售票进程，功能是对共享变量x的值加1。 这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2。

2 两进程并发执行的两种可能次序: 序列A 序列B p1: r1 := x ; p1: r1 := x ; r1 := r1 + 1 ; p2: r2 := x; x := r1 ; r2 := r2 + 1 ; P2: r2 := x ; x := r2 ; r2 := r2 + 1 ; p1: r1 := r1 + 1 ; x := r2 ; x := r1 ; 执行结果：x = 2 执行结果：x = 1

3 特点：当两个进程公用一个变量时，它们必须顺序的访问，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。
（1）什么是临界资源 我们把一次（一段时间内）仅允许一个进程使用的资源称为临界资源。 许多物理设备，如输入机、打印机、磁带机等都具有这种性质。 软件资源，如公用变量、数据、表格、队列等也都具有这一特点。

4 （2）什么是临界区 每个进程中访问临界资源的那段程序段称为临界区（临界段）。

5 （3）什么是互斥 例如：进程A正在执行CSa段时，进程B就不能进入CSb段执行。 进程A 进程B
在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约的关系称为互斥。 例如：进程A正在执行CSa段时，进程B就不能进入CSb段执行。 进程A 进程B … … x = 0 CSb x = x + 1 CSa … … x = x + 1 …

6 操作系统如何保证进程的互斥呢？ （1）保证进入 （2）排它性 （3）有限性 ?这些原则如何实现呢？
当有若干个进程欲进入临界区时，应在有限的时间内使其进入； （2）排它性 每次至多有一个进程处于临界区； （3）有限性 进程在临界区内仅逗留有限的时间。 ?这些原则如何实现呢？

7 用变量w代表某种资源的状态，w称为“锁”
二. 锁和上锁、开锁操作 1. 什么是锁 用变量w代表某种资源的状态，w称为“锁” 2. 进程使用临界资源的操作 锁操作： 1.考察锁位的值； 2.若原来的值是为“0”，将锁位置为“1”（占用该资源）； 3.若原来值是为“1”，（该资源已被别人占用），则转到1。 开锁操作： 进程使用完资源后，将锁位置为“0”，称为开锁操作。 每个临界资源设置一个锁位: 0:资源可用 1:资源占用。

8 算法 lock 3. 上锁原语和开锁原语 （1）上锁原语 （2）开锁原语 算法 unlock 问题：
输入：锁变量w 输出：无 { test ： if (w为1) goto test ;/* 测试锁位的值 */ else w = 1 ; /* 上锁 */ } （2）开锁原语 算法 unlock 输入：锁变量w 输出：无 { w = 0 ; /* 开锁 */ } 问题： （1）效率低。当锁已上时，当前上锁的进程忙等； （2）无法实现。当锁已上时，当前上锁（原语）的进程占有CPU不放，谁来开锁呢？死锁！

9 改进的算法 算法：lock（w） 输入：W（锁变量） 输出：无 { if（w == 1） sleep(pri,w);
} 算法：unlock（w） 输入：W（锁变量） 输出：无 { if（等待W队列不空） wakeup(w)； W = 0； /* 开锁 */ }

10 4. 用上锁原语和开锁原语实现进程互斥 进程A 进程B 上锁原语 开锁原语 进入临界区CSa 上锁原语 开锁原语 进入临界区CSb

11 三. 信号灯和P、V操作 什么是信号灯 信号灯是整型变量。 a ≥ 0时，表示绿灯，进程可继续执行。
信号灯是一个确定的二元组（s，q），s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的值对并发进程和共享资源进行控制和管理。 注意：创建信号灯时，应准确说明信号灯s的意义和初值（这个初值绝不能为负值）。

12 P操作原语的实现 2. P、V操作 信号灯的值只能由P、V操作来改变。 （1）P操作 入 口 s=s-1 P操作定义
入 口 信号灯的值只能由P、V操作来改变。 （1）P操作 P操作定义 对信号灯s的P操作记为P（s）。 P（s）是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用P（s）的进程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。 s=s-1 Y s>=0 N 返 回 入信号灯等待队列 置“等待状态” 转进程调度

13 V操作原语的实现 （2） V操作 入 口 s=s+1 S<=0 置“就绪状态” 转进程调度 入就绪队列 返 回 V操作定义
入 口 s=s+1 S<=0 从该信号灯的等待队列中取出首元素 置“就绪状态” 转进程调度 Y N 入就绪队列 返 回 V操作定义 对信号灯s的V操作记为V（s）。 V（s）是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行， 否则，要帮助唤醒在信号灯等待队列上的一个进程。

14 3. 用信号灯的P、V操作实现进程互斥 设：mutex为互斥信号灯，初值为1。 （1）框图描述 进程Pa 进程Pb P(mutex)
进入临界区CSa P(mutex) V(mutex) 进入临界区CSb

15 （2）程序描述 Main( ) { int mutex = 1; /*互斥信号灯*/ cobegin Pa（）； Pb（）； coend }
{ … P(mutex); CSa; V(mutex); … } Pb( ) { … P(mutex); CSb; V(mutex); … }

16 用两个进程共享打印机的例子 设信号灯print表示打印机，初值为1，表示打印机可用(也可理解为有一台打印机)。
(print也是用于互斥的信号灯，教材上设置为mutex。)

17 假设有N个并发进程共用一台打印机，设互斥信号灯mutex的初值为1，则： mutex的取值范围为多少？信号灯的值分别代表什么含义？
（3）信号灯可能的取值 假设有N个并发进程共用一台打印机，设互斥信号灯mutex的初值为1，则： mutex的取值范围为多少？信号灯的值分别代表什么含义？

18 诸N个并发进程，互斥信号灯mutex的初值为1时，则：
（3）信号灯可能的取值 诸N个并发进程，互斥信号灯mutex的初值为1时，则： mutex的取值为：1～-(N-1). 其含义为： 1 ：表示有进程进入临界区。有一个资源，无进程等待； 0 ：表示有1个进程进入临界区。无资源，无进程等待； -i ：表示一个进程进入临界区。无资源，且有i (i<=N)个进程等待进入。

19 （五）进程同步 一、进程同步的概念 1. 进程同步的例子 引例 1 ：两位同学约好星期天去东湖，早上8:00在校门口，不见不散。
当一个同学先来到校门口，要等另一个同学，到齐后一道打的去东湖。

20 所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。
2. 什么是进程同步 同步： 所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。 互斥的概念来自于诸进程对独占使用资源（设备）的竞争 同步来源于多个进程的合作 在人类社会中竞争与合作是永恒的

21 病人就诊的例子 病人看病活动： … 要病人去化验； 等化验结果； 继续诊病； 医生化验活动： … 等要化验的病人； 进行化验； 开出化验单；
等待 唤醒后 唤醒后 等待

22 在操作系统中，同步有各种各样，但归纳起来有两类：
3. 进程同步的分类 在操作系统中，同步有各种各样，但归纳起来有两类： 诸进程合作完成某工作的逻辑顺序。 对系统资源的共享。如两个进程共享一个缓冲区完成誊抄问题

23 a.合作进程的执行次序 用进程流图来描述诸进程合作完成某一任务的次序。

24 1、说明进程的同步关系 进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。 2、设置信号灯，说明含义、初值。 s13 = 0 表示进程P1尚未执行完成 s23 = 0 表示进程P2尚未执行完成

25 3、写出程序描述 P1( ) { …; v(s13); } P2( ) { …; v(s23); P3( ) { p(s13);
{ …; v(s13); } P2( ) { …; v(s23); P3( ) { p(s13); p(s23); ….;

26 b.共享缓冲区的合作进程的同步 设有一个缓冲区buffer，大小为一个字节，CP进程不断产生字符，送buffer，IOP进程从buffer中取出字符打印。如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。

27 要保证打印结果的正确，CP、IOP必须遵循以下同步规则：
(1)当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待； (2)当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须等待。 解决这个问题的步骤： (1)分析问题，弄清楚同步关系，如上分析； (2)设置信号灯，说明含义、初值； (3)写出程序描述。

28

29 c. 生产者－消费者问题 我们把上面的例子扩充，假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有n个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印。 在我们生活中有很多这样的例子。

30 生产者－消费者问题 对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待； 对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。 这种相互等待，并互通信息就是典型的进程同步。 同时，缓冲区是个临界资源，因此，诸进程对缓冲区的操作程序是一个共享临界区，因此，还有个互斥的问题。

31 生产者－消费者问题

32 生产者－消费者问题

33 用PV操作解决下面问题： 司机进程： Repeat 启动车辆； 正常行驶； 到站停车； Until ……
例 题 用PV操作解决下面问题： 司机进程： Repeat 启动车辆； 正常行驶； 到站停车； Until …… 售票员进程： Repeat 关门； 售票； 开门； Until ……

34 同步要求：先关门，后开车； 先停车，后开门； 信号灯：S_Door, {初值为0} S_Stop, {初值为0} 司机进程： 售票员进程：
Begin Repeat P(S_Door); 启动； 驾驶； 停车； V(S_Stop); Until false; End 售票员进程： Begin Repeat 关门； V(S_Door); 售票； P(S_Door); 开门； Until false； End 34

35 补充题： 有十个读者和两个编辑同时处理一篇文章，对于读操作是可以同时进行的；若有读者正在读，编辑就不能工作；若编辑正在处理，读者就不能读，编辑与编辑的工作也是互斥的，试用信号灯及P、V操作描述读者与编辑之间协同工作，并给出类C程序。 35

36 一种解法，正确吗？ mutex：互斥信号灯，初值为1。 main（） { int mutex=1，couter=0； cobegin
readi（）； (i=1-10) editerj（）； (j=1,2) coend } mutex：互斥信号灯，初值为1。 readi() { if(couter = = 0) p(mutex); couter ++; 读文章； couter --; if(couter == 0) v(mutex); } editerj() { p(mutex); 处理文章; v(mutex); } 一种解法，正确吗？ 36

37 用于读者与编辑、编辑与编辑的互斥信号灯，初值为1
读者、编辑问题正解 mutex: 用于读者与编辑、编辑与编辑的互斥信号灯，初值为1 mutex1: 用于对couter操作的互斥的信号灯，初值为1。 37

38 main（） { int mutex1= mutex=1， couter=0； cobegin readi（）； editeri（）；
coend } readi() { p(mutex1); couter ++; if (couter = = 1) p(mutex); v(mutex1); 读文章； p(mutex1); couter --; if (couter == 0) v(mutex); } editj() { p(mutex); 处理文章; v(mutex); } 38

39 (六)线程的基本概念 进一步提高进程的并发性时产生问题： 在OS中，进程的引入提高了系统资源的利用率。 进程切换开销越来越大
进程间通信效率受限 多处理机系统调度

40 在只有进程概念的操作系统中进程是： 在引入线程的操作系统中： 系统资源分配的单位 处理器调度的对象 线程是处理机调度的对象；
进程是系统资源的分配单位； 一个进程可同时具有多个线程。

41 (六)线程的基本概念 1. 什么是线程 线程是比进程更小的活动单位，它是进程中的一个执行路径。 线程可以这样来描述： 进程中的一条执行路径；
它有自己私用的堆栈和处理机执行环境； 它与父进程共享分配给父进程的主存； 它是单个进程所创建的许多个同时存在的线程中的一个。

42 2. 线程的特点 创建一个线程比创建一个进程开销要小得多。
线程（Thread）是一个动态的对象，是处理机调度的基本单位，表示一个进程中的一个控制点，执行一系列的指令。 实现线程间通信十分方便，因为一个进程创建的多个线程可以访问整个进程的所有资源，包括共享地址区域和数据，因此，线程间通信比较简单方便。 在进程内创建多线程，可以提高系统的并行处理能力，加快进程的处理速度。 同一个进程中线程切换简单。进程中所有线程是共享一个进程图像的。

43 单进程 单进程 多线程 多进程 单线程 每个进程只有一个线程 多进程 多线程 每个进程只有多个线程

44 线程的实现机制 内核线程（Kernel-Level Thread） 用户线程（User-Level Thread）
在OS内核完成创建、撤消、执行一个指定的函数线程。 在支持内核线程OS中，内核维护进程和线程上下文，线程切换由内核完成。处理机分配对象是线程。某个线程因中断阻塞不影响其它线程的执行。 多线程的进程可获得更多的处理机时间。Windows Server 2003支持内核线程。 用户线程（User-Level Thread） 不依赖OS核心，由应用进程利用线程库提供创建、同步、调度和管理线程。 由于不需要操作系统支持，任何操作系统都可以支持。甚至单用户操作系统。

45 轻量级进程（Light weight process）
线程实现的机制 轻量级进程（Light weight process） 由内核支持的用户线程。一个进程可有一个或多个轻量级进程。每个轻量级进程由一个单独的内核线程来支持。由于同时提供内核线程控制机制和用户线程库，可以很好地把内核线程和用户线程的优点结合起来。

46 （七）Unix进程 Unix进程树的结构

47 进程图象的组成 基本进程控制块 proc结构
在UNIX系统核心中有一进程表，每个进程占用一个表目，称为基本进程控制块，存放进程的最基本的管理和控制信息，不论进程是否处于运行状态，系统都要访问这些信息，因此它必须常驻内存。基本进程控制块定义为proc结构。 进程的进程图象（有的文献上称上下文，context） U区、共享正文区、数据区和用户栈区组成 。

48 进程图象 共享正文区 用户地址空间 代码 数据 用户栈 用户栈区 数据区 U 区 user 核心栈

49 进程控制块(PCB) proc结构 proc.h (基本的) 基本进程控制块，它包含进程控制和管理的最基本的信息
user结构 user.h (扩充的) 包括进程调度、用户管理、进程图象管理、文件系统及缓冲区管理方面的信息 正文控制表 text.h 系统的正文控制表，管理共享正文区，每个共享程序装入内存之后，就占用该结构的一个表目，使用该共享程序的进程，在其proc结构中有一个指针指向该表目

50 数据结构之间的关系

51 UNIX进程状态转换 僵死 exit fork sleep swith wakeup wakeup 用户态运行 核心态运行 被抢占 创 建
中断自陷及返回 中断 自陷 中断自陷 及返回 exit fork 被抢占 sleep swith 有内存 创 建 wakeup 内存就绪 内存睡眠 换出 换进 换出 无 内 存 wakeup 外存就绪 外存睡眠

52 UNIX系统的进程控制 运行状态转换成睡眠状态 sleep() 运行状态转换成僵死状态 exit()
睡眠状态转换成就绪状态 wakeup() 新创建进程 fork() 等待进程终止 wait() 执行用户程序 exec()

53 第四章 小结 一. 进程概念 二. 进程控制 1. 进程引入 程序的顺序执行、并发执行的定义与特点 2. 与时间有关的错误：定义、誊抄实例
第四章 小结 一. 进程概念 1. 进程引入 程序的顺序执行、并发执行的定义与特点 2. 与时间有关的错误：定义、誊抄实例 3. 进程定义、进程与程序的区别 4. 进程状态 三个基本状态、状态变迁图 5. 进程描述 pcb结构与作用、进程的组成、Unix进程控制块结构、Unix进程的组成 二. 进程控制 1. 进程控制的功能 2. 基本进程控制原语 创建原语、撤销原语、等待原语、唤醒原语 3. 进程控制原语的主要功能及结构变化

54 三. 进程同步机构 1. 锁 上锁原语、开锁原语 2. 信号灯 P操作、V操作 四. 进程互斥 五. 进程同步 1. 同步概念
1. 锁 上锁原语、开锁原语 2. 信号灯 P操作、V操作 四. 进程互斥 1. 临界资源 2. 临界区 3. 互斥 4. 用信号灯的P、V操作实现进程互斥 五. 进程同步 1. 同步概念 2. 合作进程的执行次序 3. 共享缓冲区的合作进程的同步 4. 生产者－消费者问题