《操作系统-进程互斥与同步.》由会员分享，可在线阅读，更多相关《操作系统-进程互斥与同步.（130页珍藏版）》请在金锄头文库上搜索。
1、并发：互斥与同步 1 本章教学目标 理解进程的并发性带来的问题 理解什么是临界区管理 掌握临界区管理的软、硬件方法 掌握信号量及PV操作解决互斥与同步问题 掌握管程的概念及用法 掌握进程间通信的方法 2 进程的顺序性 一个进程在顺序处理器上的执行是严格 按序的，一个进程只有当一个操作结束 后，才能开始后继操作 顺序程序设计是把一个程序设计成一个 顺序执行的程序模块，顺序的含义不但 指一个程序模块内部，也指两个程序模 块之间。 3 顺序程序设计特点 程序执行的顺序性 程序环境的封闭性 程序执行结果的确定性 计算过程的可再现性 4 进程的并发性(1) 进程执行的并发性：一组进程的执行在时间上是重叠
2、的 。 并发性举例：有两个进程A(a1、a2、a3)和B(b1、b2、 b3)并发执行。 a1, a2, a3, b1, b2, b3 a1, b1, b2, a2, a3, b3 从宏观上看，并发性反映一个时间段中几个进程都在同 一处理器上，处于运行还未运行结束状态。 从微观上看，任一时刻仅有一个进程在处理器上运行。 5 进程的并发性(2) 并发的实质是一个处理器在几个进 程之间的多路复用，并发是对有限 的物理资源强制行使多用户共享， 消除计算机部件之间的互等现象， 以提高系统资源利用率。 6 进程的并发性(3) 单处理机系统中，多道程序设计使得不同 的进程交错执行 多处理机系统中，不同的进
3、程可以同时执 行。 进程执行的速度不可预测，依赖于其它进 程的行为、操作系统处理中断的方式以及 操作系统的调度策略。 并发性使程序的执行失去了封闭性、顺序 性、确定性和可再现性 7 8 并发程序设计 while(true) input; process; output; while(true) input; send while(true) receive; process; send; while(true) receive; output； 程序1(i) 程序2(p) 程序3(o) 9 o1p1o2i2i1p2 i1 p3 p1 i3 p2 o1 i4 i2 o2 i5p4o3 (a)串行
4、工作 ipo (b)并行工作 t1 t5 t4 t3 t2 10 并发带来的问题 并发进程可能是无关的，也可能是交互的 无关的并发进程是指它们分别在不同的变 量集合上操作 交互的并发进程共享某些变量，之间具有 制约关系，有可能产生时间相关的错误。 11 无关的并发进程 无关的并发进程 一组并发进程分别在不同的变量集合上 操作 一个进程的执行与其他并发进程的进展 无关。 并发进程的无关性是进程的执行与 时间无关的一个充分条件，又称为 Bernstein条件。 12 Bernstein条件 设R(pi)=a1, a2, , an，表示程序pi在执行期间 引用的变量集； W(pi)=b1, b2,
5、, bn，表示程序pi在执行期间 改变的变量集； 两个进程的程序p1和p2满足Bernstein条件是指 引用变量集与改变变量集交集之并为空集，即： (R(p1)W(p2)(R(p2)W(p1)(W(p1)W(p2)= 13 Bernstein条件举例 例如，有如下四条语句： S1: a := x + y S2: b := z + 1 S3: c := a b S4: w := c + 1 于是有：R(S1)=x,y ,R(S2)=z， R(S3)=a,b，R(S4)=c；W(S1)=a, W(S2)=b，W(S3)=c，W(S4)=w。 S1和S2可并发执行，满足 Bernstein条件。
6、14 并发程序带来的好处 单处理器系统上，可有效利用资源，让处理器和 I/O设备，I/O设备和I/O设备同时工作，充分发挥 机器部件的并行能力； 硬件能并行工作仅有了提高效率的可能性，硬部件并 行性的实现需要软件技术去利用和发挥，这种软件技 术就是并发程序设计。 在多处理器系统上，可让进程在不同处理器上物 理地并行工作 并发程序设计是多道程序设计的基础，多道程序 的实质就是把并发程序设计引入到系统中。 15 与时间有关的错误 并发进程使得进程的执行不可预测，甚至 无法再现。 进程间的相互影响和制约导致对资源的共 享充满了危险，各种与时间有关的错误就 可能出现 结果不唯一 结果与进程执行的速度相
7、关 永远等待 进程相互等待产生死锁，或进程一直得不到资源产 生饿死现象 16 结果不唯一（例1） 生产者 while(true) /* produce an item in nextProduced; */ while(counter = BUFFER_SIZE) ; /* do nothing */ bufferin=nextProduced; in = (in+1)%BUFFER_SIZE; counter+; 消费者 while(true) while(counter = 0) ; /* do nothing */ nextConsumed = bufferout; out = (out
8、+1)%BUFFER_SIZE; counter-; /* consume the iterm nextConsumed */ register2=counter; register2=register2-1; counter=register2; register1=counter; register1=register1+1; counter=register1; 17 T0: 生产者执行 register1=counter; register1=5 T1: 生产者执行 register1=register1+1; register1=6 T2: 消费者执行 register2=count
9、er; register2=5 T3: 消费者执行 register2=register2-1; register2=4 T4: 生产者执行 counter=register1; counter=6 T5: 消费者执行 counter=register2; counter=4 T0: 生产者执行 register1=counter; register1=5 T1: 生产者执行 register1=register1+1; register1=6 T2: 消费者执行 register2=counter; register2=5 T3: 消费者执行 register2=register2-1; r
10、egister2=4 T4: 消费者执行 counter=register2; counter=4 T5: 生产者执行 counter=register1; counter=6 执行序列1 执行序列2 T0: 生产者执行 register1=counter; register1=5 T1: 生产者执行 register1=register1+1; register1=6 T2: 生产者执行 counter = register1; counter=6 T3: 消费者执行 register2=counter; register2=6 T4: 消费者执行 register2=register2-1
11、; register2=5 T5: 消费者执行 counter=register2; counter=5 执行序列3 18 结果不唯一（例2） P1: a = a +1; b = b + 1; P2: b = 2 * b; a = 2 * a; 线性执行 a=2 b=2; b=4; a=4; 并发执行 a=a+1; /a=2; b=2*b; /b=2; b=b+1; /b=3; a=2*a; /a=4; a =b=1; a !=ba =b 19 结果不唯一（例3） void T1() /按旅客订票要求找到Aj int X1=Aj； if(X1=1) X1-; Aj=X1; /输出一张票； el
12、se /输出票已售完 void T2() /按旅客订票要求找到Aj int X2=Aj； if(X2=1) X2-; Aj=X2; /输出一张票； else /输出票已售完 20 永远等待 int X = memory; void borrow(int B) while(BX) 进程进入等待主存资源队列; X=X-B; 修改主存分配表，进程获得主存资源 ； void return(int B) X=X+B; 修改主存分配表； 释放等待主存资源的进程； 可能永远 不会被唤醒 21 进程的交互 竞争 多个进程之间并不知道其他进程的存在，竞争共享硬设备、存储器、处 理器和文件资源等 两个控制问题 死
13、锁问题 饥饿问题 操作系统应该提供支持，合理分配资源，解决资源的竞争问题 进程的互斥访问是解决进程间竞争资源的手段 进程互斥是指若干进程因相互争夺独占型资源而产生的竞争制约关系 协作 一组进程之间相互知道对方的存在，协作完成同一任务。 进程的同步是解决进程间协作关系的手段。 进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动， 因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所 产生的协作制约关系 进程互斥关系是一种特殊的进程同步关系。 22 临界区管理 互斥与临界区 实现临界区管理的几种尝试 实现临界区管理的软件方法 实现临界区管理的硬件设施 23 互斥与临界区(1)
14、并发进程中与共享变量有关的程序 段叫“临界区”， 共享变量代表的 资源叫“临界资源”。 与同一变量有关的临界区分散在各 进程的程序段中，而各进程的执行 速度不可预知。 如果保证进程在临界区执行时，不 让另一个进程进入临界区，即各进 程对共享变量的访问是互斥的，就 不会造成与时间有关的错误。 24 互斥与临界区(2) 一次至多一个进程能够进入临界区内执行； 如果已有进程在临界区，其他试图进入的进程 应等待； 进入临界区内的进程应在有限时间内退出，以 便让等待进程中的一个进入。 临界区调度原则： 互斥使用、有空让进，忙则等待、有限等待 ，择一而入，算法可行； 25 Boolean inside1
15、= false; Boolean inside2 = false; Process P1() while(inside2); inside1 = true; /* critical section */ inside1 = false; /* remainder section*/ Process P2() while(inside1); inside2 = true; /* critical section */ inside2 = false; /* remainder section*/ 1 2 3 临界区管理的尝试 同时进入！ 26 Boolean inside1 = false; Boolean insid
