进程的互斥与临界区 1)进程的互斥是由多个进程竞争同一共享资源而产生的相互 制约的关系 这种因共享资源而产生的关系称为进程的互斥(Mutual Exclusion)以 互斥关系使用的共享资源称为临界资源(Critical Source)。 临界资源包括： 硬件（打印机、显示器、软驱.) 软件（公共变量、数据、子程序.) 2) 每个进程中访问临界资源的那段代码称为临界区。为保证对 临界资源的互斥访问，进程的代码由以下部分组成： ①进入区(entry section)一申请进入临界区 ②临界区(critical section一访问临界资源 ③退出区(exit section)一退出对临界资源的访问 ④剩留区（remainder section)- 进程其他部分 电子科技大学刘民岷 进程同步和互斥 2
电子科技大学 刘民岷 2 1、进程的互斥与临界区 进程同步和互斥 1）进程的互斥是由多个进程竞争同一共享资源而产生的相互 制约的关系 这种因共享资源而产生的关系称为进程的互斥（Mutual Exclusion）以 互斥关系使用的共享资源称为临界资源（Critical Source）。 临界资源包括： • 硬件（打印机、显示器、软驱……） • 软件（公共变量、数据、子程序……） 2）每个进程中访问临界资源的那段代码称为临界区。为保证对 临界资源的互斥访问，进程的代码由以下部分组成： ①进入区（entry section）——申请进入临界区 ②临界区（critical section ——访问临界资源 ③退出区（exit section） —— 退出对临界资源的访问 ④剩留区（remainder section） ——进程其他部分
进程的同步 进程的同步(Syrchronization):多个并发进程协作完成某项任务 的过程中需要相互传递某种信息，进程之间通过在执行时序上 的一种限制而达到相互合作 例：A进程负责从健盘读取数据到缓冲区，B进程负责从缓冲区读取数据进行 计算 A进程 B进程 从键盘读入数据 等待A进程发数据 送缓冲区 送缓冲区的信号 缓冲区满 读缓冲区数据 向B发信号 并计算 等待部进程发回信号 向A进程发信号 等待下批信号送缓冲区 (缓冲区数据已取走) 进程的同步与互斥是两个既有区别又有联系的概念，并发进程的异步 运行都必须按一定的相互约束的时序进行，因此，互斥也是一种同步 关系。 电子科技大学刘民岷 进程同步和互斥 3
电子科技大学 刘民岷 3 2、进程的同步 进程同步和互斥 • 进程的同步(Syrchronization)：多个并发进程协作完成某项任务 的过程中需要相互传递某种信息，进程之间通过在执行时序上 的一种限制而达到相互合作 • 例：A进程负责从键盘读取数据到缓冲区，B进程负责从缓冲区读取数据进行 计算 • 进程的同步与互斥是两个既有区别又有联系的概念，并发进程的异步 运行都必须按一定的相互约束的时序进行，因此，互斥也是一种同步 关系
、信号量和PV操作 3 1、 同步机制 通常把实现进程同步与互斥的机制称为同步机制，同步机制目标是解 决对临界资源的访问问题，应遵守以下规则： >空闲让进：无进程处于临界区内，可让一申请进入临界区的进程进入 忙则等待：若临界区内有进程，其余申请进入临界区的进程必须等待 有限等待：进程进入临界区的要求必须在有限时间内得到满足 让权等待：等待进入临界区的进程，若占有CPU必须立即释放 传统同步机制的实现之一.--硬件指令：Test and Set(TS) > 为临界资源设置“锁”，即设置一个锁变量L0ck; Lock=false,”开锁“，表临界资源空闲； >Lock=true,”关锁“，表临界资源不空； 。 TS的缺点： 当一个进程在临界区上执行时，其它任何企图进入临界区的进程都 进入循环等待，不断调用TS测试，造成处理机浪费。 电子科技大学刘民岷 进程同步和互斥 4
电子科技大学 刘民岷 4 3、信号量和PV操作 进程同步和互斥 1、同步机制 • 通常把实现进程同步与互斥的机制称为同步机制，同步机制目标是解 决对临界资源的访问问题，应遵守以下规则： 空闲让进：无进程处于临界区内，可让一申请进入临界区的进程进入 忙则等待：若临界区内有进程，其余申请进入临界区的进程必须等待 有限等待：进程进入临界区的要求必须在有限时间内得到满足 让权等待：等待进入临界区的进程，若占有CPU必须立即释放 • 传统同步机制的实现之一------硬件指令：Test and Set(TS) 为临界资源设置“锁”，即设置一个锁变量Lock; Lock=false，”开锁“,表临界资源空闲； Lock=true,”关锁“，表临界资源不空； • TS的缺点： 当一个进程在临界区上执行时，其它任何企图进入临界区的进程都 进入循环等待，不断调用TS测试，造成处理机浪费
3、信号量和PV操作（续） 2、PV操作 。 1986年荷兰计算机科学家Dijkstra把互斥的关键含义抽象为信号量 (Semaphore)),提出典型同步机制一P、V操作。 ·设信号量为S(整数)，用$的值表示共享资源的使用情况，P、 V操作的定义如下： -P(S): 。S=S-1; ·若S>=0,该进程继续执行；否则，进程阻塞进入S信号量的等 待队列，直到其它进程执行V(S)操作为止。 -V(S): ·S=S+1; ·为 若S>0,则进程继续执行；否则唤醒阻塞队列中的一个进程， 使其进入就绪状态。 显然S可用于表示资源的数量，S>0,表示可分配的资源数量；S<0, S绝对值表示等待队列中的进程数目。 电子科技大学刘民岷 进程同步和互斥 5
电子科技大学 刘民岷 5 3、信号量和PV操作（续） 进程同步和互斥 2、PV操作 • 1986年荷兰计算机科学家Dijkstra把互斥的关键含义抽象为信号量 （Semaphore），提出典型同步机制——P、V操作。 • 设信号量为S（整数），用S的值表示共享资源的使用情况，P、 V操作的定义如下： – P(S): • S=S-1; • 若S>=0,该进程继续执行；否则，进程阻塞进入S信号量的等 待队列，直到其它进程执行V(S)操作为止。 – V(S): • S=S+1; • 若S>0,则进程继续执行；否则唤醒阻塞队列中的一个进程， 使其进入就绪状态。 – 显然S可用于表示资源的数量，S>0,表示可分配的资源数量；S<0， S绝对值表示等待队列中的进程数目
3、信号量和PV操作（续） 3、用PV操作实现进程间互斥 ·设A、B进程竞争临界资源，mutex为互斥信号量。初值为l,利 用P、V操作实现的进程互斥模型如下： A进程 B进程 ! P(mutex); P(mutex) 进入A临界区： 进入B临界区： V(mutex); V(mutex); 。进入时mutex<0,则... 。 退出时mutex+l, 。 每次只允许一个进程进入临界区。 电子科技大学刘民岷 进程同步和互斥 6
电子科技大学 刘民岷 6 3、信号量和PV操作（续） 进程同步和互斥 3、用PV操作实现进程间互斥 •• 设A、B进程竞争临界资源，mutex为互斥信号量。初值为1，利 用P、V操作实现的进程互斥模型如下： • 进入时mutex<0,则…… • 退出时mutex＋1， • 每次只允许一个进程进入临界区
3、信号量和PV操作（续） 4、用PV操作实现进程间同步 例一：如图一个打印进程、一个计算进程和一个缓冲区。缓冲 区为空时计算进程才能不断将结果送入缓冲区；打印进程必须在 缓冲区不空时，才可以取出数据打印。 两信号量S1,S2初值为0，S1表示缓冲区数 计算进程 打印进程 据是否满，S2表示缓冲区是否为空。P、V 操作实现计算、打印进程同步的模型如下： S2 计算进程CP 打印进程IOP 缓冲区 计算结果送缓冲区： P(S1): V(S1): 从缓冲区取数打印： P(S2): V(S2): 电子科技大学刘民岷 进程同步和互斥 7
电子科技大学 刘民岷 7 3、信号量和PV操作（续） 进程同步和互斥 4、用PV操作实现进程间同步 • 例一：如图一个打印进程、一个计算进程和一个缓冲区。缓冲 区为空时计算进程才能不断将结果送入缓冲区；打印进程必须在 缓冲区不空时，才可以取出数据打印。 两信号量S1，S2初值为0，S1表示缓冲区数 据是否满，S2表示缓冲区是否为空。P、V 操作实现计算、打印进程同步的模型如下：
3、信号量和PV操作（续） 5、用PV操作实现进程之间的同步一！ 三个并发进程 进程gt从输入设备上读数据，存入 Get Copy Put Buffer1;进程copy不断将Buffer1中的内 容复制到Buffer2;进程put将Buffer2中的 内容打印输出。三个进程必须协调同步， 设4个信号量S1、S2、S3、S4,S2S3表示 S Buffer12和Buffer2是否装满数据；S1,S, 表示Buffer1、Buffer2是否为空，初值为 Bufferl Buffer2 S1=1;S2=0;S3=0;S4=1,如右图： 同步模型如下所示： 进程get 进程copy 进程put + P(S): P(S2): P(S): P(S); ↓ 从输入设备读数据存 将Bufferl的内容复 将缓冲区Buffer2数 入Bufferl: 制到Buffer2; 据打印输出： V(S) V(S,); v(S3: V(s,): 电子科技大学刘民岷 进程同步和互斥 8
电子科技大学 刘民岷 8 3、信号量和PV操作（续） 进程同步和互斥 5、用PV操作实现进程之间的同步——三个并发进程 • 进程get从输入设备上读数据，存入 Buffer1；进程copy不断将Buffer1中的内 容复制到Buffer2；进程put将Buffer2中的 内容打印输出。三个进程必须协调同步， 设4个信号量S1、S2、S3、S4，S2，S3表示 Buffer1和Buffer2是否装满数据；S1，S4 表示Buffer1、Buffer2是否为空，初值为 S1=1;S2=0;S3=0;S4=1，如右图： Buffer1 Buffer2 Get Copy Put S1 S2 S4 S3 同步模型如下所示： 进程get P(S1); 从输入设备读数据存 入Buffer1； V(S2) 进程copy P(S2); P(S4); 将Buffer1的内容复 制到Buffer2； V(S1); V(S3); 进程put P(S3); 将缓冲区Buffer2数 据打印输出； V(S4);
3、信号量和PV操作（续） 5、生产者消费者问题 一并发进程的同步和互斥问题的一般化。 生产者：释放某一类资源的进程； 消费者进程 out. 消费者：使用某一类资源的进程。 一组消费者进程(C1,C2,…,Cm)和一组生 产者进程(PP2,…,P)通过一个由n个单元组成 的环形缓冲区联系起来（如图）。每个单元可放 生产者进程 in 一个“产品”放入缓冲区内。消费者进程侧不断 生产者消费者问题 地从缓冲区取出“产品”。显然，生产者进程与 消费者进程在使用缓冲区时有以下制约关系： >缓冲区中至少有一个单元为空，生产者进程才能放入“产品”。 >缓冲区中至少有一个单元是满的，消费者进程才能取出“产品” >各消费者进程与各生产者进程只能互斥地使用临界资源缓冲区。 电子科技大学刘民岷 进程同步和互斥 9
电子科技大学 刘民岷 9 3、信号量和PV操作（续） 进程同步和互斥 5、生产者消费者问题 —— 并发进程的同步和互斥问题的一般化。 • 生产者：释放某一类资源的进程； • 消费者：使用某一类资源的进程。 • 一组消费者进程（C1，C2，…，Cm）和一组生 产者进程（P1,P2,…,Pk）通过一个由n个单元组成 的环形缓冲区联系起来（如图）。每个单元可放 一个“产品”放入缓冲区内。消费者进程则不断 地从缓冲区取出“产品”。显然，生产者进程与 消费者进程在使用缓冲区时有以下制约关系： 消费者进程 生产者进程 in 生产者消费者问题 out 缓冲区中至少有一个单元为空，生产者进程才能放入“产品”。 缓冲区中至少有一个单元是满的，消费者进程才能取出“产品”。 各消费者进程与各生产者进程只能互斥地使用临界资源缓冲区
3、信号量和PV操作（续） 5、生产者消费者问题 ·根据上述分析，设置以下信号量： ①公用信号量mutex:初值为l,用于实现临界区互压； ②生产者私有信号量empty:初值为n,表示空缓冲单元数； ③消费者私有信号量fu止：初值为0，表示满缓冲单元数目； ④指针in,out分别指向当前第一个空缓冲区和第一个满缓冲区。 生产者进程： 消费者进程： 生产一个产品： P(full)防 P(empty); P(mutex); P(mutex); 从out所指向的缓冲区取产品： 将产品放入in所指向的缓冲区； out=(out+1)mod n; in=(in+1)mod n; V(mutex); V(mutex); V(full); V(empty); 电子科技大学刘民岷 进程同步和互斥 10
电子科技大学 刘民岷 10 3、信号量和PV操作（续） 进程同步和互斥 5、生产者消费者问题 • 根据上述分析，设置以下信号量： ① 公用信号量mutex:初值为1，用于实现临界区互斥； ② 生产者私有信号量empty: 初值为n，表示空缓冲单元数； ③消费者私有信号量full: 初值为0，表示满缓冲单元数目； ④指针in,out分别指向当前第一个空缓冲区和第一个满缓冲区。 生产者进程： 生产一个产品； P(mutex); in=(in+1)mod n； 将产品放入in所指向的缓冲区; … P(empty); V(full); 消费者进程： P (full); 从out所指向的缓冲区取产品； V (mutex); out=(out+1)mod n； … P (mutex); V (empty); V(mutex);
电子科枝大学 本节完 主讲教师：刘民岷 ■ 航空航天学院 软件技术基础课程组 进程同步和互斥 11
11 本节完 进程同步和互斥 主讲教师：刘民岷 航空航天学院 软件技术基础课程组