计算机操作系统(第三章)_3.5(进程的互斥及同步)

1、计算机操作系统第三章 进程管理_2 第三章 进程管理第2页2022-2-8多进程对共享变量的并发访问可能会导致数据的不一致！3.5.1 资源共享引起的制约3.5 3.5 进程互斥进程互斥 例1 假设有两个并发执行的进程P1和P2。cobegin p1; p2;coendP1: . x = x + 1; P2: . x = x + 1; 第3页第三章 进程管理 X = X + 1 操作将被分解为几条机器指令来实现，如：1 将变量x的值放入寄存器 register = x 2 把寄存器中的值加1 register = register + 13 把寄存器的值存到x中 x = register第4页

2、第三章 进程管理 如果两个进程的执行顺序为：P1: R1=x; R1=R1+1; x=R1; P2: R2=x; R2=R2+1; x=R2time第5页第三章 进程管理 如果两个进程的执行顺序为：P1: R1=x; R1=R1+1; x=R1; P2: R2=x; R2=R2+1; x=R2time第6页第三章 进程管理 如果两个进程的执行顺序为：P1: R1=x; R1=R1+1; x=R1; P2: R2=x; R2=R2+1; x=R2time第7页第三章 进程管理 例2 对于生产者消费者问题。我们需要用一个变量(count)来记录当前缓冲区中的数据个数。开始时，count的值设为零，

3、如果生产者生产了一个产品放到一个新的缓冲中，则将count的值加1，如果消费者消费了某个缓冲区中的产品，则将count的值减1。生产者消费者1.exe生产者进程 while (true) /* produce an item and put in nextProduced */ while (count = BUFFER_SIZE); / do nothing buffer in = nextProduced; in = (in + 1) % BUFFER_SIZE; count +; 消费者进程 while (true) while (count = 0) ; / do nothing ne

4、xtConsumed = bufferout; out = (out + 1) % BUFFER_SIZE; count -; /* consume the item in nextConsumed */竞争条件 count+ 指令的执行可能被实现为 register1 = count register1 = register1 + 1 count = register1 count 指令的执行可能被实现为 register2 = count register2 = register2 - 1 count = register2 假如初始时“count = 5” ，可能会出现下面的交替执行情况

5、:S0: 生产者执行 register1 = count register1 = 5S1: 生产者执行 register1 = register1 + 1 register1 = 6 S2: 消费者执行 register2 = count register2 = 5 S3: 消费者执行 register2 = register2 - 1 register2 = 4 S4: 生产者执行 count = register1 count = 6 S5: 消费者执行 count = register2 count = 42022-2-8第三章 进程管理第12页第13页第三章 进程管理 进程的并发执行不

6、仅仅是用户程序的执行开始时间的随机性和提高资源利用率的结果，也是资源有限性导致资源的竞争与共享对进程的执行过程进行制约所造成的一一. . 互斥的概念互斥的概念 引例：引例： 宿舍电话的使用宿舍电话的使用 打印机的使用打印机的使用 1. 临界资源：一次仅允许一个进程使用的资源称为临界资源临界资源：一次仅允许一个进程使用的资源称为临界资源 引例中的电话和打印机都属于临界资源。除此之外，还有内引例中的电话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源。存变量、指针、数组等等也是临界资源。1.1.临界区：临界区： 每个进程中访问临界资源的那段程序段称为临界区（临界段）。进入

7、区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志退出区(exit section)：用于将正在访问临界区标志清除。剩余区(remainder section)：代码中的其余部分。第三章 进程管理第14页2022-2-82. 间接制约 间接制约：把由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约 直接制约：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程 对于每一类，系统应有相应的分配和释放相应公

8、有资源的管理办法，以制约并发进程。这就是互斥第三章 进程管理第15页2022-2-8互斥互斥定义定义: : 一组并发进程中的一个或多个程序段，因共享某一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该的单位执行。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥资源的并发进程同时进入临界区称为互斥。 一般情况下，作为程序段的一个过程不允许多一般情况下，作为程序段的一个过程不允许多个进程共同访问它。个进程共同访问它。第三章 进程管理第16页2022-2-8

9、互斥的例子：互斥的例子：例例1：进程：进程A、B共享一台打印机，则当一进程占用打印机后，另共享一台打印机，则当一进程占用打印机后，另一进程若也要使用打印机，则必须等待，直至它释放打印机。一进程若也要使用打印机，则必须等待，直至它释放打印机。例例2：机票预订系统：机票预订系统 A B 旅行社旅行社A查到某机座空；查到某机座空； ： ： 旅行社旅行社B查到某机座空；查到某机座空； 与其顾客商量；与其顾客商量； ： ： 旅行社旅行社A预订该机座；预订该机座； ： B预订该机座；预订该机座；第三章 进程管理第17页2022-2-8并发进程互斥必须满足的原则(1) 不能假设各并发进程的相对执行速度。即各

10、并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区。 (2) 并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区。(空闲让进） (3) 并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入 (4) 并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区准则准则(1)，(2)，(3)是保证各并发进程享有平等的、独立的竞争是保证各并发进程享有平等的、独立的竞争和使用公有资源的权利，且保证每一时刻至多只有一个进程在和使用公有资源的权利，且保证每一时刻至多只有一个进程在临界区。而准则临界区。而

11、准则(4)则是并发进程不发生死锁（将在后面讲述）则是并发进程不发生死锁（将在后面讲述）的重要保证。的重要保证。第三章 进程管理第18页2022-2-8 进入临界区的准则：进入临界区的准则： (1)(1)每次至多有一个进程处于临界区；每次至多有一个进程处于临界区； (2)(2)当有若干个进程欲进入临界区时，应在有限当有若干个进程欲进入临界区时，应在有限 的时间内使其进入；的时间内使其进入； (3)(3)进程在临界区内仅逗留有限的时间进程在临界区内仅逗留有限的时间。第三章 进程管理第19页2022-2-83.5.2 互斥的加锁实现 人们可能认为只需把临界区中的各个过程按不同的时间排列调用就行了，但

12、由于用户程序执行开始的随机性，要求该组并发进程中的每个进程事先知道其他并发进程与系统的动作。不可能把临界区中的各个过程按不同的时间排列调用。因此，互斥的实现必须通过加锁的方式进行解决。1、互斥的实现 当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区。第三章 进程管理第20页2022-2-8 二二. . 用锁实现互斥用锁实现互斥 1.1.锁和上锁锁和上锁、开锁操作开锁操作 解决进程互斥的最简单的办法是加锁。解决进程互斥的最简单的办法是加锁。 在系统中为

13、在系统中为每个临界资源设置一个锁位，每个临界资源设置一个锁位， 0 0 表示资源可用表示资源可用， 1 1 表示资源已被占用（不可用）。表示资源已被占用（不可用）。 同时同时, ,系统要提供上锁原语和开锁原语，供进程在使系统要提供上锁原语和开锁原语，供进程在使用临界资源之前和使用完临界资源之后使用。用临界资源之前和使用完临界资源之后使用。第三章 进程管理第21页2022-2-8 2 2. .用上锁原语和开锁原语实现进程互斥用上锁原语和开锁原语实现进程互斥 上锁原语上锁原语 进入临界区进入临界区csb 开锁原语开锁原语进程进程B 上锁原语上锁原语 进入临界区进入临界区csa 开锁原语开锁原语进程

14、进程A第三章 进程管理第22页2022-2-8main ( ) ppa ( ) ppb ( ) int w=0; : : cobegin lock(w); lock(w); ppa(); CSa; CSb; ppb(); unlock(w); unlock(w); coend : : 第三章 进程管理第23页2022-2-.3信号量和信号量和P P，V V原语原语1.1.信号量（信号量（Semaphore)Semaphore)（信号灯）（信号灯）第三章 进程管理第24页2022-2-8信号量：除赋初值外仅能由同步原语（P、V操作）对其操作的整型变量，其值与其所代表的资源使用情

15、况有关。信号量的物理意义： 当其值0代表可用资源的数量 当其值 0 0 时，表示绿灯，进程执行。时，表示绿灯，进程执行。( (表示系统拥有的表示系统拥有的资源个数资源个数) s 0 0 时，表示红灯，进程停止执行。时，表示红灯，进程停止执行。( ( |s|表示等待表示等待某资源的进程个数某资源的进程个数) ) 注意：创建信号灯时，应准确说明信号灯 s 的意义和初值 (这个初值绝不能为负值)。main ( ) pa ( ) pb ( ) pc ( ) int mutex=1; : : : cobegin p(mutex); p(mutex); p(mutex); pa( ); CSa; CSb;

16、 CSc; pb( ); v(mutex); v(mutex); v(mutex); pc( ); : : : coend 信号灯信号灯mutex的取值范围：的取值范围：-2、-1、0、1第三章 进程管理第30页2022-2-8思考：信号量的值有什么含义？ 信号量的值可以大于1吗？ P/V原语的使用方法 进程在进入临界区之前，执行P操作（申请资源）进程在退出临界区之后，执行V操作（归还资源）第三章 进程管理第32页 3.6.1. 3.6.1. 同步的概念同步的概念 互斥的概念来自于诸进程对独占使用资源（设备）的互斥的概念来自于诸进程对独占使用资源（设备）的竞争，同步来源于多个进程的合作。在人类

17、社会中竞争与竞争，同步来源于多个进程的合作。在人类社会中竞争与合作是永恒的。合作是永恒的。 同步同步：所谓同步就是并发进程在一些关键点上可能需：所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同要相互等待与互通消息，这样的相互制约关系称为进程同步。步。3.6 进程同步进程同步第三章 进程管理第33页2022-2-8直接制约：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程异步环境主要指各并发进程的执行起始时间的随机性和执行速度的独立性直接制约的进程互相给对方进程发送执行条件已经具备的信号，只要收到了制约进程发来

18、的信号便开始执行，而在未收到制约进程发来的信号时便进入等待状态 进程间的同步：把异步环境下的一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程。 合作进程：具有同步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件第三章 进程管理第34页2022-2-8同步机制应遵循的准则 空闲则入：其他进程均不处于临界区； 忙则等待：已有进程处于其临界区； 有限等待：等待进入临界区的进程不能死等； 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）3.6.2 私用信号量 一般来说，也可以把各进程之间发送的消息作为信号量看待。与进

19、程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关。因此，称该信号量为私用信号量（Private Semaphvre）。一个进程Pi的私用信号量Semi是从制约进程发送来的进程Pi的执行条件所需要的消息。与私用信号量相对应，称互斥时使用的信号量为公用信号量。第三章 进程管理第36页2022-2-83.6.3 用，原语操作实现同步用P、V原语不但可以实现对共享资源的互斥访问，还可以实现对共享变量的加1（V操作）和减1操作（P操作） 有了私用信号量的概念，可以使用，原语操作实现进程间的同步。利用，原语实现进程同步的方法与利用wait和signal过程时相同，也是分为

20、三步。首先为各并发进程设置私用信号量，然后为私用信号量赋初值，最后利用，原语和私用信号量规定各进程的执行顺序。图3.13 缓冲区队列第三章 进程管理第37页2022-2-8例：设进程PA和PB通过缓冲区队列传递数据（如图3.13）。PA为发送进程，PB为接收进程。PA发送数据时调用发送过程deposit(data)，PB接收数据时调用过程remove(data)。且数据的发送和接收过程满足如下条件：在PA至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中取出数据（假定数据块长等于缓冲区长度）； PA往缓冲队列发送数据时，至少有一个缓冲区是空的； 由PA发送的数据块在缓冲队列中按先进先出（FI

21、FO）方式排列。描述发送过程deposit(data)和接收过程remove(data)。第三章 进程管理第38页2022-2-8 解：由题意可知，进程PA调用的过程deposit(data)和进程PB调用的过程remove(data)必须同步执行，因为过程 deposit(data)的执行结果是过程remove(data)的执行条件，而当缓冲队列全部装满数据时，remove(data)的执行结果又是deposit(data)的执行条件，满足同步定义。从而，按以下三步描述过程deposit(data)和remove(data)：(1) 设Bufempty为进程PA的私用信号量，Buffull

22、为进程PB的私用信号量；(2) 令Bufempty的初始值为n（n 为缓冲队列的缓冲区个数），Buffull 的初始值为0；(3) 描述：第三章 进程管理第39页2022-2-8PA: deposit(data):begin local xP(Bufempty)；按FIFO方式选择一个空缓冲区Buf(x)；Buf(x) dataBuf(x)置满标记（Buffull）endPB: remove(data):Begin local x （Buffull）；按FIFO方式选择一个装满数据的缓冲区Buf(x)data Buf(x)Buf(x)置空标记 （Bufempty）end这里，局这里，局部变量部

23、变量x用用来指明缓来指明缓冲区的区冲区的区号，给号，给Buf(x)置置标志位是标志位是为了便于为了便于区别和搜区别和搜索空缓冲索空缓冲区及非空区及非空缓冲区。缓冲区。第三章 进程管理第40页2022-2-8PB: remove(data):Begin local x （Buffull）；按FIFO方式选择一个装满数据的缓冲区Buf(x)data Buf(x)Buf(x)置空标记 （Bufempty）end这里，局部变量x用来指明缓冲区的区号，给Buf(x)置标志位是为了便于区别和搜索空缓冲区及非空缓冲区。PA: deposit(data):begin local xP(Bufempty)；按F

24、IFO方式选择一个空缓冲区Buf(x)；Buf(x) dataBuf(x)置满标记（Buffull）end第41页进程的交互关系：可以按照相互感知的程度来分类相互感知的程度交互关系一个进程对其他进程的影响潜在的控制问题相互不感知(完全不了解其它进程的存在)竞争(competition)一个进程的操作对其他进程的结果无影响互斥，死锁（可释放的资源），饥饿间接感知(双方都与第三方交互，如共享资源)通过共享进行协作 一个进程的结果依赖于从其他进程获得的信息互斥，死锁（可释放的资源），饥饿，数据一致性直接感知(双方直接交互，如通信)通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息死锁，饥饿互

25、斥：互斥：指多个进程不能同时使用同一个资源；死锁：死锁：指多个进程互不相让，都得不到足够的资源；饥饿：饥饿：指一个进程一直得不到资源（其他进程可能轮流占用资源）经典进程同步问题3.6.3生产者消费者问题(the producer-consumer problem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。共享缓冲区生产指针消费指针Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer N满空指针移动方向第43页

26、 采用信号量机制：full是满数目，初值为0，empty是空数目，初值为N。实际上，full和empty是同一个含义：full + empty = Nmutex用于访问缓冲区时的互斥，初值是1 每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁(为什么？) 采用AND信号量集：Swait(empty, mutex), Ssignal(full, mutex), ConsumerProducerP(empty);P(mutex);/进入区 one unit - buffer;V(mutex);V(full);/退出区P(full);P(mutex);/进入区 one unit - buffer;V(mutex);V(empty);/退出区第44页flash演示演示: 生产者、消费者生产者、消费者生产者、消费者问题生产者、消费者问题有多个生产者不断重复以下过程：有多个生产者不断重复以下过程： 生产一产品生产一产品 放入缓冲单元放入缓冲单元有多个消费者不断重复以下动作：有多个消费者不断重复以下动作： 从缓冲中取出一个产品从缓冲中取出一个产品 把产品消费掉把产品消费掉问题：问题： 1. 如何防止两个生产者同时将产品放入同一个单元？如何防止两个生产者同时将产品放入同一个单元？ 2. 如何防止两消费者同时从同一个单元中取产品？如何