多核体系结构与并行编程模型计算机科学导论第八讲

1、多核体系结构与并行编程模型计算 机科学导论第八讲 多核体系结构与并行多核体系结构与并行编程编程模型模型 计算机科学导论第八讲计算机科学导论第八讲 0551-6 多核体系结构与并行编程模型计算 机科学导论第八讲 课课 程程 内内 容容 课程内容课程内容 围绕学科理论体系中的模型理论围绕学科理论体系中的模型理论, 程序理论和计算理论程序理论和计算理论 1. 模型理论关心的问题模型理论关心的问题 给定模型给定模型M，哪些问题可以由模型，哪些问题可以由模型M解决；如何解决；如何 比较模型的表达能力比较模型的表达能力 2. 程序理论关心的问题程序理论关心的问题 给定模型给定模型M，如何用模型，如何用模型

2、M解决问题解决问题 包括程序设计范型、程序设计语言、程序设计、包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题计算理论关心的问题 给定模型给定模型M和一类问题和一类问题, 解决该类问题需多少资源解决该类问题需多少资源 多核体系结构与并行编程模型计算 机科学导论第八讲 讲讲 座座 提提 纲纲 基本知识基本知识 多核体系结构、并行编程模型多核体系结构、并行编程模型 内存一致性模型内存一致性模型 严格一致性模型、顺序一致性模型、内存一致性严格一致性模型、顺序一致性模型、内存一致性 模型的重要性模型的重要

3、性 共享内存并行编程模型共享内存并行编程模型 同步、锁、临界区、条件变量、死锁、数据竞争同步、锁、临界区、条件变量、死锁、数据竞争 消息传递并行编程模型消息传递并行编程模型 消息传递、同步与异步消息传递、同步与异步 多核体系结构与并行编程模型计算 机科学导论第八讲 对称多处理器对称多处理器 对称多处理器的体系结构对称多处理器的体系结构 二级二级 缓存缓存 内存内存 总线总线 二级二级 缓存缓存 二级二级 缓存缓存 二级二级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 处理器处理器处理器处理器处理器处理器 处理器处理器 基基 本本 知知 识识 必须在

4、必须在 处理器的处理器的 缓存中找缓存中找 到它操作到它操作 的大部分的大部分 数据，以数据，以 保证性能保证性能 通过共通过共 享内存来享内存来 进行通信进行通信 多核体系结构与并行编程模型计算 机科学导论第八讲 几个概念的粗略解释几个概念的粗略解释 任务：一般性的抽象术语，指由软件完成的一个任务：一般性的抽象术语，指由软件完成的一个 活动。例如，矩阵分块乘就是把矩阵乘分成多个活动。例如，矩阵分块乘就是把矩阵乘分成多个 任务任务, 以便于在对称多处理器上并行执行这些任务以便于在对称多处理器上并行执行这些任务 进程：任务在程序中的对应物，它有自己的数据进程：任务在程序中的对应物，它有自己的数据

5、 和代码，需要在处理器上运行直至结束。进程是和代码，需要在处理器上运行直至结束。进程是 操作系统进行资源分配和调度的独立单位操作系统进行资源分配和调度的独立单位 线程：是把进程细分出现的实际运行单位，线程线程：是把进程细分出现的实际运行单位，线程 是进程中一段顺序执行的语句序列。把进程分成是进程中一段顺序执行的语句序列。把进程分成 若干线程是为了提高进程执行过程中的并行性。若干线程是为了提高进程执行过程中的并行性。 线程是操作系统调度的基本单位线程是操作系统调度的基本单位 下面未严格区分进程和线程下面未严格区分进程和线程 基基 本本 知知 识识 多核体系结构与并行编程模型计算 机科学导论第八讲

6、 几个概念的粗略解释几个概念的粗略解释 并行并行(parallel): 多个可以同时执行的任务，在多处多个可以同时执行的任务，在多处 理器上同时执行理器上同时执行 并发并发(cuncorrent)：多个可以同时执行的任务，在：多个可以同时执行的任务，在 单处理器上交错执行单处理器上交错执行 并发是逻辑上同时发生，而并行是物理上同时发并发是逻辑上同时发生，而并行是物理上同时发 生。下面不区分并行和并发生。下面不区分并行和并发 基基 本本 知知 识识 t A B t A B 多核体系结构与并行编程模型计算 机科学导论第八讲 对称多处理器对称多处理器 对称多处理器的体系结构对称多处理器的体系结构 二

7、级二级 缓存缓存 内存内存 总线总线 二级二级 缓存缓存 二级二级 缓存缓存 二级二级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 处理器处理器处理器处理器处理器处理器 处理器处理器 基基 本本 知知 识识 多个高性能处理器多个高性能处理器 可以集成在一块芯片可以集成在一块芯片 上上 多核体系结构与并行编程模型计算 机科学导论第八讲 基基 本本 知知 识识 单核结构与多核系统结构单核结构与多核系统结构 执行单元执行单元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 执行单元执行单元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 执行单元执行单元 缓存缓

8、存 CPU状态状态 中断逻辑中断逻辑 单核结构单核结构多处理器结构多处理器结构 执行单元执行单元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 CPU状态状态 中断逻辑中断逻辑 超线程结构超线程结构 超线程技术充分利用执行超线程技术充分利用执行 单元中的空闲资源，以便在单元中的空闲资源，以便在 相同时间内完成更多工作相同时间内完成更多工作 执行单元中的资源：内存执行单元中的资源：内存 访问部件、算术运算部件和访问部件、算术运算部件和 浮点功能部件等浮点功能部件等 多核体系结构与并行编程模型计算 机科学导论第八讲 基基 本本 知知 识识 单核结构与多核系统结构单核结构与多核系统结构 执行单元执行单

9、元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 执行单元执行单元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 执行单元执行单元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 单核结构单核结构多处理器结构多处理器结构 执行单元执行单元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 CPU状态状态 中断逻辑中断逻辑 超线程结构超线程结构 超线程技术本质上就是多超线程技术本质上就是多 个线程共享一个执行核个线程共享一个执行核 两套两套CPU状态状态 +中断逻辑中断逻辑 是为了适应两个线程同时执是为了适应两个线程同时执 行的需要行的需要 多核体系结构与并行编程模型计算 机科学导论第八讲 基基 本本 知知

10、识识 单核结构与多核系统结构单核结构与多核系统结构 共享缓存的多核体系结构共享缓存的多核体系结构 执行单元执行单元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 执行单元执行单元 缓存缓存 CPU状态状态 中断逻辑中断逻辑 多核体系结构多核体系结构 执行单元执行单元 缓缓 存存 CPU状态状态 中断逻辑中断逻辑 执行单元执行单元 CPU状态状态 中断逻辑中断逻辑 多核处理器是多核处理器是 把两个甚至更多把两个甚至更多 的独立执行核嵌的独立执行核嵌 入到一个处理器入到一个处理器 的内部，每个线的内部，每个线 程都有完整的硬程都有完整的硬 件执行环境，各件执行环境，各 线程之间实现了线程之间实现了

11、真正意义上的并真正意义上的并 行行 多核体系结构与并行编程模型计算 机科学导论第八讲 基基 本本 知知 识识 单核结构与多核系统结构单核结构与多核系统结构 体系结构越来越复杂，若这些复杂的特征都要反体系结构越来越复杂，若这些复杂的特征都要反 映到编程语言中，才能写出较好利用体系结构优点映到编程语言中，才能写出较好利用体系结构优点 的程序，则编写程序将是很困难的工作的程序，则编写程序将是很困难的工作 需要设计好的编程模型并通过编译器和操作系统需要设计好的编程模型并通过编译器和操作系统 的帮助和支持来解决的帮助和支持来解决 采用超线程技术的多核体系结构采用超线程技术的多核体系结构 执行单元执行单元

12、缓存缓存 CPU状态状态 中断逻辑中断逻辑 CPU状态状态 中断逻辑中断逻辑 执行单元执行单元缓存缓存 CPU状态状态 中断逻辑中断逻辑 CPU状态状态 中断逻辑中断逻辑 多核体系结构与并行编程模型计算 机科学导论第八讲 基基 本本 知知 识识 并行编程模型并行编程模型 是底层体系结构与上层应用程序之间的桥梁是底层体系结构与上层应用程序之间的桥梁 向上隐藏并行处理器的细节，并向程序员提供表向上隐藏并行处理器的细节，并向程序员提供表 达并行的方法达并行的方法 向下充分利用硬件资源，高效且正确地完成应用向下充分利用硬件资源，高效且正确地完成应用 需求需求 任务划分、任务映射、数据分布、通信和同步是

13、任务划分、任务映射、数据分布、通信和同步是 设计并行编程模型时需要考虑的五个关键要素设计并行编程模型时需要考虑的五个关键要素 并行编程模型的另一种说法并行编程模型的另一种说法 并行编程模型是编写可被编译和运行的并行程序并行编程模型是编写可被编译和运行的并行程序 的一种模型的一种模型 多核体系结构与并行编程模型计算 机科学导论第八讲 基基 本本 知知 识识 并行编程模型的分类并行编程模型的分类 1. 按进程交互的机制来分按进程交互的机制来分 共享内存模型：进程共享可以异步地读写的全局共享内存模型：进程共享可以异步地读写的全局 数据空间数据空间 消息传递模型消息传递模型: 进程通过相互传递消息来交

14、换数据进程通过相互传递消息来交换数据 隐式模型：进程之间交互是用户不可访问的隐式模型：进程之间交互是用户不可访问的 2. 按问题分解按问题分解 任务并行：每个处理器执行不同的任务任务并行：每个处理器执行不同的任务 数据并行：把大任务分别成若干个相同的子任务数据并行：把大任务分别成若干个相同的子任务 3. 多核体系结构与并行编程模型计算 机科学导论第八讲 内存一致性模型内存一致性模型 内存一致性模型内存一致性模型 描述的是，在有共享内存的多处理器系统上，在描述的是，在有共享内存的多处理器系统上，在 它们读写共享内存操作的可能执行顺序中，哪些它们读写共享内存操作的可能执行顺序中，哪些 顺序是正确的

15、顺序是正确的 内存一致性模型是理解并行程序语义的一个关键内存一致性模型是理解并行程序语义的一个关键 为确保写出正确的并行程序，程序员必须准确理为确保写出正确的并行程序，程序员必须准确理 解并行程序的语义解并行程序的语义 随着多核处理器的广泛应用，并行程序设计已经随着多核处理器的广泛应用，并行程序设计已经 由一种特殊的、只需少数高端技术人才掌握的技由一种特殊的、只需少数高端技术人才掌握的技 巧，变为一种大多数程序员都应该掌握的基本技巧，变为一种大多数程序员都应该掌握的基本技 能能 多核体系结构与并行编程模型计算 机科学导论第八讲 内存一致性模型内存一致性模型 严格一致性（原子一致性）模型严格一致

16、性（原子一致性）模型 任何对内存位置任何对内存位置x的读操作，的读操作，得到的是得到的是最近一次最近一次对对 x的写操作所写入的值的写操作所写入的值 单处理器遵守严格一致性单处理器遵守严格一致性 下面下面, P1和和P2是处理器是处理器, x是共享变量是共享变量, 初值是初值是0。 W(x)1表示表示: 把把1写到写到x中中；R(x)3表示表示: 读取读取x,得得值值3 P1: W(x)1 P1: W(x)1 P2: R(x)1 R(x)1 P2: R(x)0 R(x)1 P1: W(x)1 P2: R(x)0 R(x)1 tt t 左边不符合严格一致性左边不符合严格一致性 多处理器多处理器+

17、共享内存时共享内存时, 会出现读写或写写操作的冲会出现读写或写写操作的冲 突突 多核体系结构与并行编程模型计算 机科学导论第八讲 顺序一致性模型顺序一致性模型 比严格一致性弱的模型比严格一致性弱的模型 在多处理器共享内存情况下，每个处理器执行的在多处理器共享内存情况下，每个处理器执行的 单个线程严格按照程序规定的顺序逐语句地进行单个线程严格按照程序规定的顺序逐语句地进行 内存访问操作内存访问操作 比顺序一致性还弱的统称为弱内存模型（不同情比顺序一致性还弱的统称为弱内存模型（不同情 况有不同名称）况有不同名称） 大多数程序员假定并行程序的运行满足顺序一致大多数程序员假定并行程序的运行满足顺序一致

18、 性，但现实中几乎所有的并行程序都在某种弱内存性，但现实中几乎所有的并行程序都在某种弱内存 模型下运行，而且不同的并行语言和处理器的内存模型下运行，而且不同的并行语言和处理器的内存 模型不同模型不同 内存一致性模型内存一致性模型 多核体系结构与并行编程模型计算 机科学导论第八讲 顺序一致性模型顺序一致性模型 例：互斥使用临例：互斥使用临 界区的并行线程界区的并行线程 若两个线程严格按照给出的语句顺序逐条执行，若两个线程严格按照给出的语句顺序逐条执行， 则它们能实现互斥功能，因为则它们能实现互斥功能，因为r1和和r2不可能同时为不可能同时为0 现实中，编译器和处理器内部进行的优化都会导现实中，编

19、译器和处理器内部进行的优化都会导 致内存操作的实际顺序和代码中的语句顺序不一致致内存操作的实际顺序和代码中的语句顺序不一致, 使得两个条件判断都为真，两个线程都进入临界区使得两个条件判断都为真，两个线程都进入临界区 内存一致性模型内存一致性模型 x和和y: 共享变量共享变量, 初始初始:x = 0, y = 0 x = 1;y = 1; r1 = y;r2 = x; if (r1= 0)if (r2= 0) critical region critical region 多核体系结构与并行编程模型计算 机科学导论第八讲 内存一致性模型的重要性内存一致性模型的重要性 它作为系统实现和程序员之间的

20、接口，对处理器它作为系统实现和程序员之间的接口，对处理器 体系结构的实现、并行语言的实现、并行程序的体系结构的实现、并行语言的实现、并行程序的 开发和验证都有重要意义开发和验证都有重要意义 以并行语言的设计和实现为例以并行语言的设计和实现为例 编译器的优化算法会调整源程序中的内存操作顺编译器的优化算法会调整源程序中的内存操作顺 序，使得目标程序和源程序的顺序不一致序，使得目标程序和源程序的顺序不一致 目标程序的执行顺序又可能被处理器进一步改变目标程序的执行顺序又可能被处理器进一步改变 并行语言的设计和实现必须考虑到这两种情况及并行语言的设计和实现必须考虑到这两种情况及 其效果的叠加，对源程序可

21、能表现出的行为进行其效果的叠加，对源程序可能表现出的行为进行 准确描述准确描述(并行语言的内存模型并行语言的内存模型)，便于正确编程，便于正确编程 内存一致性模型内存一致性模型 多核体系结构与并行编程模型计算 机科学导论第八讲 编程语言内存一致性模型的现状编程语言内存一致性模型的现状 由于优化算法的多样性，编程语言内存模型比体由于优化算法的多样性，编程语言内存模型比体 系结构的内存模型复杂系结构的内存模型复杂 Gosling等为第一版等为第一版Java语言给出的内存一致性模语言给出的内存一致性模 型型, 无法支持常用的优化算法无法支持常用的优化算法, 是一个失败的模型是一个失败的模型 Mans

22、on等给出的等给出的Java模型，虽被语言新标准所采模型，虽被语言新标准所采 纳，但模型十分晦涩，是纳，但模型十分晦涩，是Java语言中最复杂部分语言中最复杂部分, 极少有人能正确理解其含义极少有人能正确理解其含义 Boehm和和Adve试图为试图为C+提供一个简单的模型，提供一个简单的模型， 但很多地方有歧义或不清晰但很多地方有歧义或不清晰 内存一致性模型内存一致性模型 多核体系结构与并行编程模型计算 机科学导论第八讲 共享内存并行编程模型共享内存并行编程模型 使用共享内存的错误例子使用共享内存的错误例子 并行计算并行计算Fibonacci序列下一个元素的序列下一个元素的两个线程两个线程 对

23、两个线程的执行没有任何约束对两个线程的执行没有任何约束 下面是两个线程某次并行时的语句执行顺序下面是两个线程某次并行时的语句执行顺序 prev和和curr: 初值分为初值分为0和和1的共享变量的共享变量 int retval; int retval; retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t 多核体系结构与并行编程模型计算 机科学导论第八讲 共享内存并行编程模型共享内存并行编程模型 使用共享内存的错误例子使用共享内存的错误例子 并行计算并行计

24、算Fibonacci序列下一个元素的序列下一个元素的两个线程两个线程 对两个线程的执行没有任何约束对两个线程的执行没有任何约束 下面是两个线程某次并行时的语句执行顺序下面是两个线程某次并行时的语句执行顺序 prev和和curr: 初值分为初值分为0和和1的共享变量的共享变量 int retval; int retval; retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t 1 11 1 1 1 多核体系结构与并行编程模型计算 机科学导论第八讲 共享内存

25、并行编程模型共享内存并行编程模型 使用共享内存的错误例子使用共享内存的错误例子 并行计算并行计算Fibonacci序列下一个元素的序列下一个元素的两个线程两个线程 对两个线程的执行没有任何约束对两个线程的执行没有任何约束 下面是两个线程某次并行时的语句执行顺序下面是两个线程某次并行时的语句执行顺序 显然结果显然结果 不对不对 原因：原因： 对共享变对共享变 量的访问缺量的访问缺 乏约束乏约束 prev和和curr: 初值分为初值分为0和和1的共享变量的共享变量 int retval; int retval; retval = curr; retval = curr; curr = curr+p

26、rev; curr = curr+prev; prev = retval; prev = retval; t 1 11 1 1 1 多核体系结构与并行编程模型计算 机科学导论第八讲 共享内存并行编程模型共享内存并行编程模型 同步同步 同步是对线程执行的顺序进行强行限制的一种机同步是对线程执行的顺序进行强行限制的一种机 制，用来控制线程执行的相对顺序，可以有效解制，用来控制线程执行的相对顺序，可以有效解 决任何线程之间的冲突，而这些冲突有可能会导决任何线程之间的冲突，而这些冲突有可能会导 致线程的执行出现异常行为致线程的执行出现异常行为 简言之，同步主要用于协调线程执行和管理共享简言之，同步主要

27、用于协调线程执行和管理共享 数据数据 同步机制同步机制 信号量、锁（又可细分成多种）、条件变量、信号量、锁（又可细分成多种）、条件变量、 多核体系结构与并行编程模型计算 机科学导论第八讲 共享内存并行编程模型共享内存并行编程模型 锁锁 用来体现一种互斥的并行控制策略用来体现一种互斥的并行控制策略 一个线程在同一个时刻只能使用一个锁，一个锁一个线程在同一个时刻只能使用一个锁，一个锁 至多由一个线程获得。锁有两个原子操作：至多由一个线程获得。锁有两个原子操作： 1. acquire: 等待锁状等待锁状 态变为未加态变为未加 锁状态，然锁状态，然 后将其置为后将其置为 已加锁状态已加锁状态 prev

28、和和curr: 初值分为初值分为0和和1的共享变量的共享变量 L是锁是锁 int retval; int retval; L-acquire(); L-acquire(); retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; 多核体系结构与并行编程模型计算 机科学导论第八讲 共享内存并行编程模型共享内存并行编程模型 锁锁 用来体现一种互斥的并行控制策略用来体现一种互斥的并行控制策略 一个线程在同一个时刻只能使用一个锁，一个锁一个线程在同一个时刻只能使用一个

29、锁，一个锁 至多由一个线程获得。锁有两个原子操作：至多由一个线程获得。锁有两个原子操作： 2. release: 将锁状态将锁状态 由已加锁变由已加锁变 为未加锁为未加锁 prev和和curr: 初值分为初值分为0和和1的共享变量的共享变量 L是锁是锁 int retval; int retval; L-acquire(); L-acquire(); retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; L-release(); L-release(); 多

30、核体系结构与并行编程模型计算 机科学导论第八讲 共享内存并行编程模型共享内存并行编程模型 临界区（临界区（critical section） 指包含有共享变量的一段代码，这些共享变量和指包含有共享变量的一段代码，这些共享变量和 多个线程之间存在相关关系多个线程之间存在相关关系 多线程编程的主要挑战在于需要以多个线程执行多线程编程的主要挑战在于需要以多个线程执行 互斥操作的互斥操作的 方式实现临方式实现临 界区，以保界区，以保 证多个线程证多个线程 不会同时访不会同时访 问临界区问临界区 prev和和curr: 初值分为初值分为0和和1的共享变量的共享变量 L是锁是锁 int retval; i

31、nt retval; L-acquire(); L-acquire(); retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; L-release(); L-release(); 多核体系结构与并行编程模型计算 机科学导论第八讲 条件变量条件变量 例：生产者例：生产者/消费者问题消费者问题 一个典型的同步问题一个典型的同步问题 也称有限缓冲区问题也称有限缓冲区问题 生产者向缓冲区中写入生产者向缓冲区中写入 数据数据 消费者从缓冲区取得数消费者从缓冲区取得数

32、据并对数据进行操作据并对数据进行操作 生产者和消费者并行执生产者和消费者并行执 行行 共享内存并行编程模型共享内存并行编程模型 void producer() / 临界区开始临界区开始 / 产生下一个数据产生下一个数据 / 临界区结束临界区结束 void consumer() / 临界区开始临界区开始 / 消费下一个数据消费下一个数据 / 临界区结束临界区结束 多核体系结构与并行编程模型计算 机科学导论第八讲 条件变量条件变量 右边是生产者线程，条右边是生产者线程，条 件变量件变量C使用锁使用锁L来完成来完成 对共享数据的访问，可对对共享数据的访问，可对 条件变量条件变量C执行执行3种原子操种

33、原子操 作作（LC 的初值为的初值为false） 1. wait(L): 释放自身持有释放自身持有 的锁并处于的锁并处于C的等待队列。的等待队列。 执行完毕时，锁已被其他执行完毕时，锁已被其他 线程获得线程获得 共享内存并行编程模型共享内存并行编程模型 void producer() while(1) L-acquire(); / 临界区开始临界区开始 while(LC = true) C-wait(L); / 产生下一个数据产生下一个数据 LC = true; C-signal(L); / 临界区结束临界区结束 L-release(); 多核体系结构与并行编程模型计算 机科学导论第八讲 条件

34、变量条件变量 右边是生产者线程，条右边是生产者线程，条 件变量件变量C使用锁使用锁L来完成来完成 对共享数据的访问，可对对共享数据的访问，可对 条件变量条件变量C执行执行3种原子操种原子操 作作（LC 的初值为的初值为false） 2. signal(L): 发信号，允许发信号，允许 等待等待C的一个线程往下执的一个线程往下执 行。该操作完毕后，锁仍行。该操作完毕后，锁仍 然被发信号的线程持有然被发信号的线程持有 共享内存并行编程模型共享内存并行编程模型 void producer() while(1) L-acquire(); / 临界区开始临界区开始 while(LC = true) C-

35、wait(L); / 产生下一个数据产生下一个数据 LC = true; C-signal(L); / 临界区结束临界区结束 L-release(); 多核体系结构与并行编程模型计算 机科学导论第八讲 条件变量条件变量 右边是生产者线程，条右边是生产者线程，条 件变量件变量C使用锁使用锁L来完成来完成 对共享数据的访问，可对对共享数据的访问，可对 条件变量条件变量C执行执行3种原子操种原子操 作作（LC 的初值为的初值为false） 3. broadcast(L): 发信号，发信号， 允许所有等待允许所有等待C的线程往的线程往 下执行。该操作完毕后下执行。该操作完毕后, 锁锁 仍然被发信号的线

36、程持有仍然被发信号的线程持有 共享内存并行编程模型共享内存并行编程模型 void producer() while(1) L-acquire(); / 临界区开始临界区开始 while(LC = true) C-wait(L); / 产生下一个数据产生下一个数据 LC = true; C-signal(L); / 临界区结束临界区结束 L-release(); 多核体系结构与并行编程模型计算 机科学导论第八讲 生产者生产者/消费者问题消费者问题 void producer() void consumer() while(1) while(1) L-acquire(); L-acquire();

37、 / 临界区开始临界区开始 / 临界区开始临界区开始 while(LC = true) while(LC= false) C-wait(L); C-wait(L); / 产生下一个数据产生下一个数据/ 消费下一个数据消费下一个数据 LC = true;LC = false; C-signal(L);C-signal(L); / 临界区结束临界区结束/ 临界区结束临界区结束 L-release();L-release() 共享内存并行编程模型共享内存并行编程模型 Conditon C; Lock L; BooL LC = false; 多核体系结构与并行编程模型计算 机科学导论第八讲 条件变量条

38、件变量 条件变量本身实质上条件变量本身实质上 并没有需要检验的条件并没有需要检验的条件 值，而是使用共享数据值，而是使用共享数据 的状态来保存线程的条的状态来保存线程的条 件值，件值，用于多线程之间用于多线程之间 关于共享数据状态变化关于共享数据状态变化 的通信的通信 当特定条件满足时，当特定条件满足时， 线程等待或者唤醒其他线程等待或者唤醒其他 合作线程合作线程 共享内存并行编程模型共享内存并行编程模型 void producer() while(1) L-acquire(); / 临界区开始临界区开始 while(LC = true) C-wait(L); / 产生下一个数据产生下一个数据

39、 LC = true; C-signal(L); / 临界区结束临界区结束 L-release(); 多核体系结构与并行编程模型计算 机科学导论第八讲 死锁死锁 当一个线程因等待另一个线程的资源而阻塞，而当一个线程因等待另一个线程的资源而阻塞，而 同时该资源永远不会被释放同时该资源永远不会被释放 自死锁或递归死锁：线程自死锁或递归死锁：线程T试图获得一个锁，而试图获得一个锁，而 该锁已被线程该锁已被线程T自己拥有自己拥有 错序死锁：线程错序死锁：线程T1占有资源占有资源r1并等待由线程并等待由线程T2占有占有 资源资源r2；而线程；而线程T2占有资源占有资源r2并等待由线程并等待由线程T1占有

40、占有 资源资源r1 编程中的问题：怎样避免出现死锁编程中的问题：怎样避免出现死锁 共享内存并行编程模型共享内存并行编程模型 多核体系结构与并行编程模型计算 机科学导论第八讲 数据竞争数据竞争 多个并行线程都访问某个共享变量多个并行线程都访问某个共享变量v，其中至少有，其中至少有 一个线程修改一个线程修改v ，并且这些线程没有使用锁来控制，并且这些线程没有使用锁来控制 它们对它们对v的访问的访问 在有数据竞争的场合，各线程对数据的访问次序在有数据竞争的场合，各线程对数据的访问次序 是不确定的，计算结果依赖于这个次序是不确定的，计算结果依赖于这个次序 数据数据竞争有时是共享数据和通竞争有时是共享数

41、据和通信信的一种方式的一种方式，但但 多数情况下属于程序错误多数情况下属于程序错误 编程中的问题：怎样发现程序中的数据竞争编程中的问题：怎样发现程序中的数据竞争 共享内存并行编程模型共享内存并行编程模型 多核体系结构与并行编程模型计算 机科学导论第八讲 消息传递消息传递 消息传递是进程之间交换信息的一种方式，使用消息传递是进程之间交换信息的一种方式，使用 共享变量是另一种方式共享变量是另一种方式 在消息传递场合下，由于一个消息在被接收者接在消息传递场合下，由于一个消息在被接收者接 收之前，必须由发送者发送，因此隐含了同步机收之前，必须由发送者发送，因此隐含了同步机 制制 消息传递可以在分布式系统、共享内存的多处理消息传递可以在分布式系统、共享内存的多处理 器系统和单处理器系统中实现器系统和单处理器系统中实现。在分布式系统上。在分布式系统上 实现共享变量有较大难度实现共享变量有较大难度 实现消息传递依靠两个通信原语：实现消息传递依靠两个通信原语：send和和receive 消息传递并行编程模型消息传递并行编程模型 多核体系结构与并行编程模型计算 机科学导论第八讲 消息传递的发送和接收对象消息传递的发送和接收对象 进程对进程的传递：两个进程不依赖于线程自行进程对进程的传递：两个进程不依赖于线程自行 进行通信，是最常见的消息传递方式进行通信，