资源预览内容
第1页 / 共15页
第2页 / 共15页
第3页 / 共15页
第4页 / 共15页
第5页 / 共15页
第6页 / 共15页
第7页 / 共15页
第8页 / 共15页
第9页 / 共15页
第10页 / 共15页
亲,该文档总共15页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2012年5月52条件临界区域(条件临界区域(conditional critical region)条件临界区域(条件临界区域(CCR, Brinch Hansen )几乎与管程同时提出,特征:)几乎与管程同时提出,特征: 一种有特定语法结构的临界区,封装一个受保护变量一种有特定语法结构的临界区,封装一个受保护变量 线程只能在针对特定受保护变量的线程只能在针对特定受保护变量的 region 语句里访问该变量语句里访问该变量 访问同一受保护变量的访问同一受保护变量的 region 语句属于同一语句属于同一 CCR,其执行互斥,其执行互斥 每个每个 CCR 有一个布尔条件,任何到达相应有一个布尔条件,任何到达相应 region 语句的线程都必须等 到该条件为真且当时无其他线程在针对同一保护变量的语句的线程都必须等 到该条件为真且当时无其他线程在针对同一保护变量的 region 语句里语句里 CCR 可以嵌套,这时也要关心死锁问题(与管程的情况类似)可以嵌套,这时也要关心死锁问题(与管程的情况类似)CCR 的概念的概念 出现在并发语言出现在并发语言 Edison 里里 对对 Ada 95 和和 Java/C# 等语言的同步机制设计有很大影响这几种语言的并行机制实际上是管程和等语言的同步机制设计有很大影响这几种语言的并行机制实际上是管程和 CCR 的组合,不同语言采用的 方式有一些不同的组合,不同语言采用的 方式有一些不同2012年5月53条件临界区域条件临界区域基于条件临界区域(基于条件临界区域(CCR)的有界缓 冲区实现。)的有界缓 冲区实现。region 语句可以有布尔条 件,因此可以避免显式的条件变量语句可以有布尔条 件,因此可以避免显式的条件变量CCR 避免了避免了 signal 的语义问题:这里 用布尔条件而不是条件变量,且只能 在的语义问题:这里 用布尔条件而不是条件变量,且只能 在 CCR 开始等条件开始等条件采用采用 CCR 的描述相对最简单清晰。 但这种结构实际上明显低效:常见实现中退出的描述相对最简单清晰。 但这种结构实际上明显低效:常见实现中退出 CCR 的代码都立 即唤醒所有等待线程,让它们在各 自的环境里检查自己的条件最坏情况:每当有线程退出的代码都立 即唤醒所有等待线程,让它们在各 自的环境里检查自己的条件最坏情况:每当有线程退出 CCR, 就需要对所有等待线程做上下文的 切入切出,开销很大, 就需要对所有等待线程做上下文的 切入切出,开销很大2012年5月54Ada 95 的同步的同步Ada 83 的主要同步机制基于消息传递,的主要同步机制基于消息传递,Ada 95 增加了受保护对象增加了受保护对象? 受保护对象可以有三类子程序成员:函数、过程和入口受保护对象可以有三类子程序成员:函数、过程和入口 函数只能读对象数据,过程和入口可读可写。每个受保护对象有一个 读者写者锁,保证所有可能冲突的操作互斥函数只能读对象数据,过程和入口可读可写。每个受保护对象有一个 读者写者锁,保证所有可能冲突的操作互斥 过程或入口用于获得对受保护对象的排他性访问,多个函数可以并发 执行,但不能和过程或入口同时执行过程或入口用于获得对受保护对象的排他性访问,多个函数可以并发 执行,但不能和过程或入口同时执行 入口可带布尔卫,调用线程需要等卫成立(像入口可带布尔卫,调用线程需要等卫成立(像 CCR 的布尔表达式)的布尔表达式)? 三类特殊调用:限时调用,等待特定时长后作废;条件调用,不能立即执 行就转去执行一段替代代码;异步调用,立即执行一段替代代码,如果替 代代码结束前该调用可执行,就作废替代代码改执行调用三类特殊调用:限时调用,等待特定时长后作废;条件调用,不能立即执 行就转去执行一段替代代码;异步调用,立即执行一段替代代码,如果替 代代码结束前该调用可执行,就作废替代代码改执行调用? 入口卫不在调用线程的上下文中求值,因此比入口卫不在调用线程的上下文中求值,因此比 CCR 条件高效。所有卫都 在受保护对象的定义里,可在目标代码中成组检测不能在入口执行中等待条件,但可调用另一入口而入队,效果相同条件高效。所有卫都 在受保护对象的定义里,可在目标代码中成组检测不能在入口执行中等待条件,但可调用另一入口而入队,效果相同2012年5月55Java 的同步的同步多线程共享的对象有一个互斥锁,通过多线程共享的对象有一个互斥锁,通过 synchronized 语句获取语句获取引用同一对象的所有同步语句在执行上互斥,引用不同对象的同步语句可同 时执行。成员函数可为引用同一对象的所有同步语句在执行上互斥,引用不同对象的同步语句可同 时执行。成员函数可为 synchronized,相当于方法体用,相当于方法体用 synchronized(this) 语 句包围,对这种方法的调用将互斥调用共享对象的非同步方法,或对其语 句包围,对这种方法的调用将互斥调用共享对象的非同步方法,或对其 public 数据成员的访问都不互斥,它们 可以并发执行,也可以和数据成员的访问都不互斥,它们 可以并发执行,也可以和 synchronized 语句或方法并发进行线程通过调用预定义无参方法语句或方法并发进行线程通过调用预定义无参方法 wait 将自己挂起。虚拟机不能判断线程在给 定对象上挂起的原因,这使线程可能由于并不合适的原因而被唤醒,因此通 常必须把将自己挂起。虚拟机不能判断线程在给 定对象上挂起的原因,这使线程可能由于并不合适的原因而被唤醒,因此通 常必须把 wait 嵌在一个条件检测循环里嵌在一个条件检测循环里对对象执行对对象执行 wait 方法将释放该对象的锁。在嵌套 的同步语句或同步方法里执行方法将释放该对象的锁。在嵌套 的同步语句或同步方法里执行 wait 时,不释放线 程掌握的任何其他对象的锁(同步)时,不释放线 程掌握的任何其他对象的锁(同步)2012年5月56Java 的同步的同步? 要唤醒在一个对象上等待的线程,就必须在引用该对象的同步语句或方法 里执行要唤醒在一个对象上等待的线程,就必须在引用该对象的同步语句或方法 里执行 notify 方法(无参。显然要由另一线程执行)方法(无参。显然要由另一线程执行) 虚拟机响应虚拟机响应 notify 时取出在该对象上挂起的某线程并将它变成可运行。 如果当时不存在挂起进程,时取出在该对象上挂起的某线程并将它变成可运行。 如果当时不存在挂起进程,notify 相当于空操作相当于空操作 调用调用 notifyAll 方法唤醒在一个对象上等待的所有线程方法唤醒在一个对象上等待的所有线程? 如果一个线程等待的条件多于一个(其如果一个线程等待的条件多于一个(其 wait 嵌套在几个不同循环里),这 里无法保证被唤醒的确实是应该唤醒的线程嵌套在几个不同循环里),这 里无法保证被唤醒的确实是应该唤醒的线程 为保证确实能唤醒一个线程,人们通常用为保证确实能唤醒一个线程,人们通常用 notifyAll 而不用而不用 notify 为保证只有一个被唤醒线程进入执行,最先看到自己等待的条件已满足 的线程必须去修改对象状态,以保证其他被唤醒线程在得到运行机会的 时候立刻转回去休眠为保证只有一个被唤醒线程进入执行,最先看到自己等待的条件已满足 的线程必须去修改对象状态,以保证其他被唤醒线程在得到运行机会的 时候立刻转回去休眠 所有等待线程每次得到运行机会都将重新求值自己的条件。如果问题中 需要等待多个条件,这种所有等待线程每次得到运行机会都将重新求值自己的条件。如果问题中 需要等待多个条件,这种“解决方法解决方法”的代价可能很高的代价可能很高2012年5月57Java 的同步的同步在在 Java 5 版本之前,要实现高效程序,通常需要设法设计一种算法,保证其 中的线程在任何时刻都不同时等待多个条件版本之前,要实现高效程序,通常需要设法设计一种算法,保证其 中的线程在任何时刻都不同时等待多个条件2004 年发布的年发布的 java.util.concurrent 包提供一种更通用的解决方案。遇到上述 情况时可以定义一个包提供一种更通用的解决方案。遇到上述 情况时可以定义一个 Lock 变量,代替变量,代替 synchronized 语句和方法老代码语句和方法老代码现在可以写成现在可以写成Lock 变量在作用域结束不自动释放锁, 需要写语句明确释放显式释放有可能写错但是这种机制也使人可以实现一些有 用的算法,其中锁获取和释放不按后 进先出的顺序进行注意:用变量在作用域结束不自动释放锁, 需要写语句明确释放显式释放有可能写错但是这种机制也使人可以实现一些有 用的算法,其中锁获取和释放不按后 进先出的顺序进行注意:用 synchronized 语句或方法时, 锁的获取和释放是隐式的,而且总是后 获得者先释放语句或方法时, 锁的获取和释放是隐式的,而且总是后 获得者先释放2012年5月58Java 的同步的同步Java 还有还有 tryLock 方法,其行为与方法,其行为与 Ada 95 的限时入口调用类似,只在立即 可用或可选描述的时间内可用时得到锁(用一个布尔值报告成功与否)一个的限时入口调用类似,只在立即 可用或可选描述的时间内可用时得到锁(用一个布尔值报告成功与否)一个 Lock 变量可以有任意多个关联的变量可以有任意多个关联的 Condition 变量,利用这种机制很容 易描述线程需要等待多个条件的算法,其中不需要用变量,利用这种机制很容 易描述线程需要等待多个条件的算法,其中不需要用 notifyAll只用只用 synchronized 方法(不用锁或同步语句)的方法(不用锁或同步语句)的 Java 对象的行为像一个管 程,但这个对象的行为像一个管 程,但这个“管程管程”里只允许有一个条件变量如果里只允许有一个条件变量如果 synchronized 语句是以语句是以 wait 开始的循环,其功能与每次显式检查条件 的开始的循环,其功能与每次显式检查条件 的 CCR 类似。由于需要显式写类似。由于需要显式写 notify ,因此不必在退出临界区时都重新求 值条件,只需要在,因此不必在退出临界区时都重新求 值条件,只需要在 notify 时做时做2012年5月59Java 的同步的同步Java 和其他一些语言的设计说明,管程和和其他一些语言的设计说明,管程和 CCR 的差异实际上很模糊一些相关情况:的差异实际上很模糊一些相关情况:? 存在一种统一方法解决所有同步问题:对每个保护对象用一个布尔条件, 让线程在条件上忙等待存在一种统一方法解决所有同步问题:对每个保护对象用一个布尔条件, 让线程在条件上忙等待 这种方案不完美,因为需要在程序里到处使用低级的信号量,基于同 步语句或者方法的隐式互斥描述更清晰这种方案不完美,因为需要在程序里到处使用低级的信号量,基于同 步语句或者方法的隐式互斥描述更清晰? 有些问题可以很自然地用多重条件表述,如果需要用有些问题可以很自然地用多重条件表述,如果需要用 Java 的基本同步机 制描述,就必须在优美和高效之间做某种选择,很难兼得的基本同步机 制描述,就必须在优美和高效之间做某种选择,很难兼得? Java 5 增强的并发机制是企图缓解这种两难境况的一个尝试增强的并发机制是企图缓解这种两难境况的一个尝试 这里的这里的 Lock 变量既保留了管程和变量既保留了管程和 CCR 互斥和条件同步之间的差异, 又使人能把等待线程划分为一些等价类,可以按类分别唤醒互斥和条件同步之间的差异, 又使人能把等待线程划分为一些等价类,可以按类分别唤醒 类划分的粒度可以适当选择和改变,因此可以权衡设计,在类划分的粒度可以适当选择和改变,因此可以权衡设计,在 CCR 的 简单性到的 简单性到 Hoare 风格管程的效率之间任意选择适当的位置风格管程的效率之间任意选择适当的位置2012年5月60消息传递模型消息传递模型小型多处理器系统里常见共享存储器的并发程序设计在大
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号