CH03并发进程操作系统.ppt

第三章 并发进程 3.1 并发进程 3.2 临界区管理 3.3 信号量与PV操作 3.4 管程 3.5 进程通信 3.6 死锁 学习目标 并发的进程间为何要对话？(协作或竞争) 并发的进程间的对话方式(通信方式)有哪些？ 信号量(重点掌握) 共享文件 共享存储区 消息传递 并发的进程间如果沟通的不好的话会咋样？ 答：会死锁！ 掌握如何解决死锁问题 3.1 并发进程 顺序程序设计 并发进程 与时间有关的错误 进程间的交互 并发的进程(洗衣房的故事) A, B, C, D的任务是收衣服、洗衣服、干衣服和折衣服 洗衣服要用 30 分钟 干衣服要用 40 分钟 折衣服要用 20 分钟 顺序作业 流水线作业 ? D如何得知C使用完了洗衣机？ ! C使用完毕应该通知D！ 并发进程间的关系 并发进程执行时分别在各自的变量集合上操作，则称他们是独立或无关的。 进程 A 进程 B x = 1; y = 2; x = x + 1; y = y – 2; 并发进程执行时共享某些变量，一个进程的执行结果可能会影响其它进程的执行结果，则称他们是交互或相关的。 进程 A 进程 B x = 1; y = 2; x = y + 1; y = y * 2; 两个交互进程可能会产生的问题1 Ti是订票终端，x=2代表剩余票数，为所有终端共享 T1 : T2: … … T=x; ① T=x; ② if T=1 then ③ if T=1 then ④ x =T-1; ⑤ x =T-1; ⑥ … … 剩余票数最终结果不确定！可能是1，也可能是0. 两个交互进程可能会产生的问题2 //B表示申请和归还主存的容量，x表示空闲主存容量 procedure borrow (int B) { if B x then ① {申请进程进入等待队列等主存资源} ⑤ x = x - B; {修改主存分配表，申请进程获得主存资源} } procedure return (int B) { x = x + B; ② {修改主存分配表} ③ {释放等主存资源的进程} ④ } 可能会导致申请进程永远等待！ 交互的并发进程与时间有关的错误 错误的两种表现形式： 结果不惟一（飞机订票） 永远等待（内存管理） 无关的并发进程不会产生此类错误，如何判断并发的进程是无关的？Bernstein条件： R(pi)={a1,a2,…an}，程序pi在执行期间引用的变量集 W(pi)={b1,b2,…bm}，程序pi在执行期间改变的变量集 若两个程序的变量集交集之和为空集： R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={ } 则并发进程的执行与时间无关。 例题 (p211) 有如下四条语句： S1: a := x + y S2: b := z + 1 S3: c := a – b S4: w := c + 1 于是有： S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。 进程间的交互 竞争 多个进程访问同一共享资源时发生 可能出现两个问题：死锁和饥饿 解决竞争关系的手段 : 进程的互斥 协作 多个进程为完成同一任务需要分工协作 处理协作关系的手段 : 进程的同步 互斥是一特殊的同步，即逐次使用互斥资源 3.2 临界区管理 临界区（互斥区） 临界区管理的尝试 实现临界区管理的软件方法 实现临界区管理的硬件方法 临界区(互斥区) 由于相关的并发进程共享变量会引起与时间相关的错误，故引入一种机制来解决这种错误。 互斥：确保一个时刻仅有一个进程在访问共享资源。 共享变量代表的资源叫“临界资源”。 在并发进程中涉及到临界资源的程序段叫“临界区”。 一个时刻仅能让一个进程进入临界区 临界区(critical section)与互斥(mutual exclusion)是同一事物的两种描述方式 使用临界区的原则 实现互斥机制的基本手段 锁(lock)：阻止某进程做某事 在进入临界区前应该上锁 在离开临界区时要开锁 进程见到锁必须等待直到锁被打开 所有的同步互斥都引入了进程的等待！ 使用锁是为了实现互斥，必须满足临界区的使用原则，因此对锁的使用必须谨慎。 临界区管理的尝试 ? process P1 { while (turn != 1); turn = 2; } 临界区管理的尝试 1 process P1 { while