操作系统课件Chapter04-1.ppt

第四章 互斥、同步与通讯 并发进程(concurrent processes) 进程互斥(mutual exclusion) 进程同步(synchronization) 进程高级通讯(communication) 4.1 并发进程 4.1.1 顺序性与并发性 顺序性 内部顺序性：P1: a1,a2,a3; P2: b1,b2,b3 外部顺序性：a1,a2,a3,b1,b2,b3; b1,b2,b3,a1,a2,a3 特征：顺序性、封闭性、可再现性 并发性 内部并发性：P2: b1,b2,b3; P2: b1,b3,b2 外部并发性：a1,b1,b2,a2,a3,b3; b1,b2,a1,b3,a2,a3 特征：交叉性、开放性、不可再现性 4.2 进程互斥(mutual exclusion) 4.2.1 共享变量与临界区 4.2.2 临界区与进程互斥 4.2.3 进程互斥的实现 4.2.1 共享变量与临界区域 共享变量（shared variable） 多个进程都需要访问的变量。 临界区域（critical region） 访问共享变量的程序段。 嵌套临界区域 4.2.3 进程互斥的实现 算法框架 4.2.3 进程互斥的实现 Requirements: 正确性原则: 一次只允许一个进程活动在关于同一组公共变量的临界区中； 进展性原则: 临界区空闲时，多个竞争者在有限时间内确定下一个进入者； 公平性原则: 一个想要进入临界区的进程在等待有限个进程进入并离开临界区后获得进入临界区的机会。 4.2.3.1 进程互斥的软件实现 完全用程序实现，不需特殊硬件指令支持。 可用于单CPU和多CPU环境中。 有忙式等待问题。 不进入等待状态的等待 Lamport面包店算法 Eisenberg/Mcguire算法 Eisenberg/Mcguire算法 Eisenberg/Mcguire算法 4.2.3.2 进程互斥的硬件实现 4.2.3.2 进程互斥的硬件实现 4.2.3.2 进程互斥的硬件实现 4.2.3.2 进程互斥的硬件实现 4.2.3.2 进程互斥的硬件实现 4.2.3.2 进程互斥的硬件实现 4.3 进程同步 4.3.1 进程同步的概念 4.3.2 进程同步机制 进程同步和进程互斥的区别： －进程同步仅发生在有逻辑关系的进程间 －进程互斥可发生在任意两个进程之间 定义：一组进程，如果它们单独不能正常运行，但并发可以正常运行，这种现象为进程合作，参与合作的进程为合作进程 4.3.2 进程同步机制 定义：用于实现进程同步的工具称为同步机制（synchronization mechanism） 同步机制要求： 描述能力够用; 可实现; 高效; 使用方便. 典型同步机制 信号灯与PV操作(semaphore and PV operations) 管程(monitor) 会合(rendezvous) 条件临界区(conditional critical region) 4.3.3 信号灯与PV操作 信号灯变量 P操作原语 V操作原语 规定和结论 对于信号灯变量的规定： 必须置一次初值，只能置一次初值，初值=0; 只能执行P操作和V操作，所有其它操作非法。 几个有用的结论： 当s.value=0时，s.queue为空； 当s.value0时，|s.value|为队列s.queue的长度； 当s.value初=1时，可以实现进程互斥； 当s.value初0时，可以管理多个实例的同类资源。 用信号灯实现进程互斥 互斥例子：借书系统(revisited) 用信号灯实现进程互斥练习 试用P、V操作实现火车票联网订票系统中北京和上海两地的两个终端售票进程发售同一班次车票的过程(Try!) 解法 设置一个互斥信号量S，其初值为1 do{ 根据顾客订票要求找到公共数据单元k； P(S)； 读取k值，保存到变量R中； 若(R=顾客订票数)，则执行 (1) 将R的值减去顾客订票数 (2) 将R的值回写到k中 (3) V(S); (4) 售出顾客所订的票； 否则，执行： (1) V(S); (2) 屏幕打印”票已售完”，返回； }while(1) 用信号灯实现进程同步 用信号灯实现进程同步 Classical synchronization problems 例1. 生产者/消费者问题 例1. 生产者/消费者问题 环形缓冲区 问题分析 同步 互斥 程序 程序 并发性提高策略 并发性提高策略 练习 桌上有个只能装得下一个水果的空盘子。爸爸可向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果