多核结构与程序设计 杨全胜 http://www.njyangqs.com/ 东南大学成贤学院计算机系.

Presentation on theme: "多核结构与程序设计 杨全胜 http://www.njyangqs.com/ 东南大学成贤学院计算机系."— Presentation transcript:

1 多核结构与程序设计 杨全胜 东南大学成贤学院计算机系

2 进程、线程和并行程序设计 内容 进程的概念 什么是线程 线程的设计 互斥与同步 并行程序设计的常见问题

3 进程的概念 现代操作系统以进程的形式来加载程序 进程是一个四元组(P,C,D,S) 进程的特征 进程是程序的一次动态执行 进程是资源的拥有者
资源特征，包括程序执行所必需的计算资源 执行特征，包括在进程执行过程中动态改变的特征

4 进程的概念 进程的状态 退出状态 非存在 状态 运行状态 就绪状态 挂起状态

5 进程的概念 进程间的通信 现代操作系统提供基本的系统调用函数，允许位于同一台处理机或不同处理机的多个进程之间相互交流信息 表现形式 实现方法
同步 聚集（归约） 实现方法 在共享存储模式下，通信可以通过操作系统读/写共享缓存来实现。 在分布式存储模式下，通信要依赖网络。 通信：进程间的数据传递称为进程间通信。 同步：同步是使位于相同或不同处理机中的多个进程之间相互等待的操作，它要求进程的所有操作均必须等待到达某个控制状态之后才进行。 聚集（或规约）：聚集将位于相同或不同处理机中的多个进程的局部结果综合起来，通过某种操作，产生一个新的结果，存储在某个指定的或者所有的进程的变量中。

6 进程、线程和并行程序设计 内容 进程的概念 什么是线程 线程的设计 互斥与同步 并行程序设计的常见问题

7 什么是线程 进程(process)与线程(thread) 进程不适合细粒度的共享存储并行程序设计
一个进程有一个主线程来初始化进程和开始执行指令。 线程能在进程内创建其他线程 每个线程有它自己的堆栈 进程内的所有的线程共享代码和数据段

8 什么是线程 线程是进程上下文中执行的代码序列，又称为轻量级的进程。它是操作系统能够调度的最小单元
进程中可以只有一个线程串行执行，也可以是多个线程共享资源下并行执行。 CODE DATA FILE REG STACK thread

9 什么是线程 使用线程优于进程的地方 创建一个线程比创建一个进程的代价要小 线程的切换比进程间的切换代价小 多线程可以充分利用多处理器
数据共享 数据共享使得线程之间的通信比进程间的通信更高效 快速响应特性 在系统繁忙的情况下，进程通过独立的线程及时响应用户的输入

10 什么是线程 线程级别 用户级线程 有关线程的所有管理工作都由在用户级实现的线程库来支持 因操作系统调度进程而被同时调度
由线程API来创建和管理，无需内核参与，操作更快 OpenMP, Pthreads, Windows thread API 进程中的所有线程将共享相同的时间片 当一个线程被挂起，同一进程中的其他线程也会被挂起，因此并行性不高

11 什么是线程 线程的级别 内核级线程 内核级线程由操作系统内核调度与管理 并行度高 内核创建和管理内核级线程的代价高，但好于对进程的代价
当一个线程被挂起，同一进程的其他线程依然可以运行。 在进程中的不同内核线程能够运行在不同的CPU或核中。 内核创建和管理内核级线程的代价高，但好于对进程的代价

12 什么是线程 线程的级别 硬件级线程 由硬件来调度 SMT: 同时多线程 CMT: 芯片多线程 超线程技术(intel的HT)
UltraSPARC (SUN) CMT: 芯片多线程 芯片多进程+多线程 也许是简单核，但是多线程 多核 众核

13 什么是线程 多线程的映射模型 对于实现了用户级线程和内核级线程的操作系统，用户级线程和内核级线程之间的可以有不同的映射方式 多对一模型
把多个用户级线程映射到一个内核级线程 线程的管理在用户空间实现，所以效率高。 当一个线程因调用系统调用被阻塞时，整个进程被阻塞 一对一模型 把每个用户级线程影射到一个内核级线程。 当一个线程阻塞时，其他线程仍然可以运行。 多对多模型 将m个用户级线程影射到n个内核级线程，m≥n 用户可以创建所需要的用户级线程，通过分配适当数目的内核级线程获得并发执行的优势并节省系统资源。

14 什么是线程 线程的生命周期 线程的标识 线程的创建 线程的终止 通常用一个整数来标识一个线程 自动创建从main函数开始的主线程
调用函数库接口创建一个新的线程(pthread_create) 线程的终止 执行完毕，或者调用了pthread_exit 主线程退出导致整个进程会终止

15 什么是线程 线程的状态 就绪（ready）：线程等待可用的处理器。 运行（running）：线程正在被执行。
阻塞（blocked）：线程正在等待某个事件的发生（比如I/O的完成，试图加锁一个被上锁的互斥量）。 终止（terminated）：线程从起始函数中返回或者调用pthread_exit。

16 什么是线程 线程状态的变迁

17 进程、线程和并行程序设计 内容 进程的概念 什么是线程 线程的设计 互斥与同步 并行程序设计的常见问题

18 线程的设计 为了功能而线程化 为了性能而线程化 分解工作 开发应用程序的时候进行线程化的最佳时机是设计阶段 为了节省周转时间而线程化
为了吞吐量提高而线程化 分解工作 任务分解 数据分解 Turnaround:周转时间

19 线程的设计 为功能而线程化 分配不同的线程来完成应用程序的不同功能 这是最容易的方法，因为功能重叠的机会很罕见。
在一个应用程序中控制并发功能的执行是比较容易的。 即使在计算间没有直接的影响，功能之间的依赖性还会维持。 Describe and define the idea of threading for functionality. To simplify code, you can design it to assign different threads for functions such as a thread each for input, the graphical user interface (GUI), computation, and output. Threading for functionality is the easiest method because the chances of function overlapping are rare. This makes it easier to control execution of the concurrent functions within an application. Threading is easier than switching functions within a serial code. By assigning different threads to different functions, all the functions will be independent of each other. However, there can still be dependencies between functions even if there is no direct interference between computations. Clarify their queries (if any) related to this slide.

20 线程的设计 为功能而线程化 举例: 为了简化代码，为下列部分设计不同的线程 考虑在建一个房屋中的不同的人： 输入、图形用户界面、计算和输出。
泥瓦匠, 木匠, 盖屋顶的人, 水暖工和油漆匠。 Consider a situation where you need to build a house. To complete the job faster, you require several people, each doing smaller and specialized tasks. You may require a bricklayer to build the walls, a carpenter to make the floors, doors, and windows, a roofer to build the roof, a plumber to do the water fittings, and a painter to paint the house. All these people will perform their dedicated task. Questions for Discussion: What kinds of dependencies are there between the tasks that go into building a house? A: There will be dependencies between the workers’ tasks. For example, the roofer cannot start constructing the roof and the painter cannot paint the walls until the bricklayer builds the walls. In addition, you cannot carpet the floor until the carpenter lays the floor. Therefore, by assigning different tasks to different people, all the people will be independent of each other when they do their work. As a result, many tasks can be done in parallel. However, the dependencies will require some scheduling and coordination between tasks. Therefore, dividing the work among all these people helps you build the house faster.

21 线程的设计 为性能而线程化 通过将执行在并行环境下的大量的计算分解开来进行应用程序的并行化，能够提高计算的性能。 比如：
线程化是为了改善周转周期和吞吐量 比如： 搜索太空实验室碎片 把全部搜索区域分成多个分段，并安排一个工人去搜索一个分段 For applications that require a large amount of computation, several serial optimization techniques are available that can increase performance. After these optimizations, you should consider threading the code to further improve efficiency and performance.

22 线程的设计 为缩短周转周期而线程化 用可能的最小的时间完成一个任务 举例：安排一个饭桌时候的不同任务： 一个侍者摆放盘子。
一个侍者折叠和放置餐巾。 一个侍者摆放花和蜡烛。 一个侍者摆放器皿 汤匙、刀子和叉子 一个侍者放玻璃杯

23 线程的设计 为了吞吐量而线程化 在固定的时间内完成最多的任务 举例：安排一个饭局时候的不同任务： 对多个侍者的安排： 每个桌子安排一个侍者。
一个侍者能摆放所有桌子的所有盘子；另一个可以摆放所有的玻璃杯；以此类推。

24 线程的设计 任务分解（客户/服务器编程模式） 数据分解（工作组编程模式） 数据流分解（流水线编程模式） 分解 设计 评论 任务分解
不同的工作安排不同的线程 常见于有几个独立的功能的应用 数据分解 多个线程针对数据的不同部分执行相同的操作 常见于音频处理、图像处理和科学计算程序中 数据流分解 一个线程的输出是第二个线程的输入 特别注意需要消除启动和关闭延迟的情况

25 线程的设计 线程化的好处: 提高性能 更好的资源利用 有效的数据共享 能够使用多核处理器 线程共享数据会比较快，因为他们共享相同地址空间。
在多核处理器中使用多线程，你可以用更少的时间完成更多的任务。 更好的资源利用 线程甚至可以减少单核处理器的延迟。 有效的数据共享 使用共享存储来共享数据

26 线程的设计 使用线程的难点 数据竞争 死锁 代码复杂性 可移植性问题 测试和调试的难度

27 进程、线程和并行程序设计 内容 进程的概念 什么是线程 线程的设计 互斥与同步 并行程序设计的常见问题

28 互斥与同步 竞争条件 数据竞争 引发两种可能的冲突: 为了使用共享资源，线程彼此竞争
虽设定了执行顺序，但是不能保证就按照这个顺序执行， 而结果却由执行的顺序决定 是并发程序中最常见的错误（与时间有关的错误）. 数据竞争 指存储器访问冲突的情况 多个线程并发访问同一个存储单元时，至少有一个线程要 改变那个单元的值，就会出现数据竞争 引发两种可能的冲突: 读/写冲突 写/写冲突 竞争条件举例： 5个人抢4个凳子，最后剩下的人每次不一样

29 互斥与同步 数据竞争 隐含的数据竞争 线程1 线程2 x+=1 x+=2 a[i]+=1 a[j]+=1 *p+=1 *q+=1
Foo(1) Foo(2) add [edi],1 add [edi],2 线程1 线程2 t=x x=t+1 u=x x=u+2 如果一开始 x=0，那么结束的时候x=? Foo那句可能在函数中隐含将参数与某共享变量运算 ADD的那两句在指令级还是存在先读EDI，再写[EDI]两个步骤 注意: x+=1 编译成 t=x; x=t+1

30 互斥与同步 互斥 临界区 举例：银行的保管箱 是代码中访问（读和写）共享变量的那部分代码 多个线程访问同一个临界区的原则：
进入区 临界区 互斥 临界区 是代码中访问（读和写）共享变量的那部分代码 多个线程访问同一个临界区的原则： 一次最多只能一个线程停留在临界区内 不能让一个线程无限地停留在临界区内，否则其他线程 将不能进入该临界区 线程互斥是指对于共享资源，在各线程访问时的排 它性 举例：银行的保管箱 维护人员确保互斥 退出区

31 互斥与同步 同步 线程同步是指线程之间所具有的一种制约关系，一个线程的执行依赖另一线程的消息，当它没有得到另一个线程的消息时应该等待，直到消息到达时才被唤醒 使用同步对象来确保互斥: 信号量、互斥量、条件变量、读/写锁、事件和栅障。 一个线程获得同步对象，其他线程必须等待 当获得同步对象的线程完成，释放对象，将对象给等待的线程。 举例: 图书馆 一个顾客借了一本书 其他人必须等着书被还回来 分布式共享结构

32 互斥与同步 栅障同步 如果多个线程在继续向下执行前，需要完成各自任务并达到某个新起点，则在此点设置栅障
是用来确保在栅障之前代码段做的修改在线程要越过栅障继续执行前全部完成。 线程在栅障的地方暂停 当所有的线程到达栅障的时候，所有线程被释放继续执行 举例：跑步

33 互斥与同步 死锁 当两个线程因为互相等待被对方拥有并且不会释放的资源而被阻塞的时候，会发生死锁。 产生死锁的原因主要是：
因为系统资源不足。 进程运行推进的顺序不合适。 资源分配不当等。 死锁的四个必要条件: 互斥条件 请求与保持条件 不可剥夺条件 循环等待条件 死锁、活锁和饿死 :28 《并行计算机互连网络》中死锁，活锁与饿死 死锁：一组报文将永远被阻塞，每个报文总在请求其他报文占用的资源，而自己又占用着其他报文所请求的资源。 活锁：在有些情况下，某些报文即使没有被永久阻塞，它们也不能到达相应的目的节点，这时是因为报文到达目的节点的所请求的通道被其他报文占用，报文只能围绕着目的节点却永远不能到达目的节点，这种情况为活锁。只有允许报文沿非最短路径发送时才会出现这种情况。例如一个死锁永久阻塞了一些报文，而这些报文恰好占用了其他报文到达目的节点需要的缓冲器，于是这些报文无法到达目的节点，只能在目的节点周围不断的绕道路由，从而产生活锁。这也说明了死锁、活锁和饿死是相互影响的，一种情况可能会导致另一种情况的发生。 饿死：如果网络流量紧张，某个报文由于所请求的资源总是分配给其他请求同一资源的报文，该报文也会被永久性阻塞。这种情况为饿死。通常是由于仲裁冲突时使用不合理的资源分配策略所致。 操作系统中：死锁定义：一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。结论：参与死锁的进程至少有二个 每个参与死锁的进程均等待资源 参与死锁的进程中至少有两个进程占有资源； 死锁进程是系统中当前进程集合的一个子集。

34 互斥与同步 死锁 死锁的预防 破坏“互斥”条件 破坏“请求与保持”条件 破坏“不可抢占”条件 破坏“循环等待”条件
在系统里取消互斥。但一般来说“互斥”条件是无法破坏的。 破坏“请求与保持”条件 不允许进程在已获得某种资源的情况下，申请其他资源。 创建进程时，要求它申请所需的全部资源。 要求每个进程提出新的资源申请前，释放它所占有的资源。 破坏“不可抢占”条件 允许对资源实行抢夺。 破坏“循环等待”条件 将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。

35 互斥与同步 死锁 死锁的避免 一个进程序列{P1,…Pn}是安全的,如果对于其中每一个进程Pi(1<=i<=n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和 现有12个资源供3个进程共享,进程P1总共需要9个资源,但第一次先申请2个;进程P2总共需要10个资源.第一次申请5个;进程P3总共需要4个资源,第一次请求2个，1）这样请求后，系统安全吗？2）如果接着P1第二次申请1个，能给它吗？ 银行家算法 (1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2) 顾客可以分期贷款,但贷款的总数不能超过最大需求量; (3)当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 现有12个同类资源供3个进程共享,进程P1总管需要9个资源,但第一次先申请2个;进程;P2总管需要10个资源.第一次要求分配5个资源;进程P3总共需要4个资源,第一次请求2个资源.经第一次分配后,系统中还有3个资源未被分配,这时,系统处于安全状态,因为还剩余3个资源,可把其中的2个资源在分配给进程P3,系统还剩余一个资源.进程P3已经得到了所需的全部资源,能执行到结束而且归还所占的4个资源,现在系统有5个可用资源,可分配给进程P2.同样的,进程P2得到了所需的全部资源,执行结束后可归还10个资源,最后进程P1也能阿到尚需的7个资源而执行到结束,然后,归还9个资源.这样,三个进程都能在有限的时间内得到各自所需的全部资源,执行结束后系统可收回所有资源.其安全序列为P3,P2,P1. 若进程P1在P3之前提出再申请一个资源的要求,系统从剩余的资源中分配一个给进程P1后尚剩余2个资源, 虽然剩余的2个资源可满足进程P3的需求,但当进程P3得到全部资源而且执行结束后,系统最多只有4个可用资源,而进程P1和进程P2还分别需要6个资源和5个资源,显然,系统中的资源已不能满足剩下两个进程的需求了,即这两个进程已经不能在有限的时间里得到需要的全部资源,因此找不到安全序列,系统已从安全状态转到了不安全状态. 操作系统按照银行家的规定为进程分配资源,进程首先提出对资源的最大需求量,当进程在执行中每次申请资源时,系统测试该进程已占有的资源与本次申请的资源数之和是否超过了该进程对资源的最大需求量.若超过则拒绝分配资源，若没有超过,则系统在测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配.这样做,能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行结束.执行结束后归还的资源加入到系统的剩余资源中,这些资源又至少可以满足另一个进程的最大需求…..于是,可以保证系统中所有进程都能在有限的时间内得到需要的全部资源. 银行家算法是通过动态的检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源的,在能确保系统处于安全状态时才把资源分配给申请者,从而避免系统发生死锁.由于银行家算法是在系统允许期间实施的,要话费相当多的时间,该算法需要m*n*n操作.银行家算法要求每类资源的数量是固定不变的,而且必须事先知道资源的最大需求量,这难以做到,不安全状态并非一定是死锁状态,如果一个进程申请的资源当前是可用的,但该进程必须等待,这样资源利用率会下降.

36 互斥与同步 饿死 当一个线程正在等一个资源而该资源被其他线程拥有，但 由于某种原因这个资源永远不能被这个线程使用的时候， 发生饥饿（但没死锁）。如果等待是永久的，那就是饿死。 举例 在使用小文件优先的打印系统中一个大文件请求打印。 活锁 忙等待的时候发生的饥饿 锁的粒度 锁的粒度是上锁后保护的共享数据的多少 减小锁的粒度可以提高对共享数据访问的并行性 在一个动态系统中，资源请求与释放是经常性发生的进程行为．对于每类系统资源，操作系统需要确定一个分配策略，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。 资源分配策略可能是公平的(fair)，能保证请求者在有限的时间内获得所需资源；资源分配策略也可能是不公平的(unfair)，即不能保证等待时间上界的存在。 在后一种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待．当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death)。             考虑一台打印机分配的例子，当有多个进程需要打印文件时，系统按照短文件优先的策略排序，该策略具有平均等待时间短的优点，似乎非常合理，但当短文件打印任务源源不断时，长文件的打印任务将被无限期地推迟，导致饥饿以至饿死。               与饥饿相关的另外一个概念称为活锁 (live lock) ，在忙式等待条件下发生的饥饿，称为活锁。例如不公平的互斥算法 不进入等待状态的等待称为忙式等待。另一种等待方式是阻塞式等待，进程得不到共享资源时将进入阻塞状态，让 出 CPU 给其他进程使用。忙等待和阻塞式等待的相同之处在于进程都不具备继续向前推进的条件，不同之处在于处于忙等待的进程不主动放 弃 CPU ， 尽 管 CPU 可 能被剥夺，因而是低效的；而处于阻塞状态的进程主动放弃 CPU ，因而是高效的。有人说活锁是数据资源分配引起的，而饿死是处理器资源分配引起的。不同领域中，本质应该是一样的。

37 互斥与同步 同步原语 信号量 信号量可以表示为一个整数，并且被两个基本原语操 作所界定: 信号量的物理含义
P(S) { // P操作的定义 S.value--; if(S.value<0) { 加本线程到S.L; Block(); } V(S) { //V操作的定义 S.value++; if(S.value<=0) { 从S.L中删除某线程P; Wakeup(P); } 互斥与同步 同步原语 信号量 信号量可以表示为一个整数，并且被两个基本原语操 作所界定: P: Proberen，意味着测试。 如果信号量的值大于0，P操作把信号量的值减1并返回； 如果当前信号量的值为非正数则P会等待。 V: Verhogen，意味着增加 V操作对信号量的值加1，并唤醒那些等待的进线程 信号量的物理含义 当信号量S.value>0时，表示有S.value个可用资源 当信号量S.value=0时，表示所有资源被用，但无线程 等待 当信号量S.value<0时，表示所有资源被用，且还有 |S.value|个线程在等待资源 P(mutex); sum++; V(mutex); 荷兰语Proberen（测试） 荷兰语Verhogen(增加) 考虑图书馆中有30本书可借，有50个要借此书的人的借还书操作

38 互斥与同步 同步原语 信号量 信号量用于互斥 一个单向的独木桥，一次只能走一个人，若用进程表示 每个人，用P、V操作给出各人的过桥过程
过桥问题    解：设信号量初值S=1            人进程Pi(i=1,2,3,…)            到达桥头            P(s)            桥行驶            到达桥另一端            V(s) 若有一售票厅只能容纳300人，当少于300人时，可以进入。否则，需在外等候， 若将每一个购票者作为一个进程，请用P、V操作编程。         解：信号量初值S=300                 购票者进程Pi(i=1,2,3,…)                 P(s)                 进入售票厅                 购票                 退出售票厅                 V(s)

39 互斥与同步 同步原语 信号量 信号量用于同步 生产者-消费者问题（缓冲区为空，消费者不能再消费， 缓冲区为满，生产者不能再生产）
一个生产者，一个消费者，公用一个缓冲区 一个生产者，一个消费者，公用n个环形缓冲区 多个生产者，多个消费者，公用n个环形缓冲区 桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹 果或者桔子，儿子专等吃盘中的桔子，女儿专等吃盘中 的苹果。规定当盘空时一次只能放一只水果供吃者取用， 请用P、V操作实现爸爸、儿子、女儿三个并发进程的同 步。 （1）一个生产者，一个消费者，公用一个缓冲区。 定义两个同步信号量： empty——表示缓冲区是否为空，初值为1。    full——表示缓冲区中是否为满，初值为0。 生产者进程 while(TRUE){ 生产一个产品;      P(empty);      产品送往Buffer;      V(full); } 消费者进程 while(True){ P(full);    从Buffer取出一个产品;    V(empty);    消费该产品;    } （2）一个生产者，一个消费者，公用n个环形缓冲区。 定义两个同步信号量： empty——表示缓冲区是否为空，初值为n。 full——表示缓冲区中是否为满，初值为0。     设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指 ，指向下一个可用的缓冲区。 生产者进程 while(TRUE){      生产一个产品;      P(empty);      产品送往buffer（in）；      in=(in+1)mod n；      V(full); } 消费者进程 while(TRUE){  P(full);    从buffer（out）中取出产品；    out=(out+1)mod n；    V(empty);    消费该产品;    } （3）一组生产者，一组消费者，公用n个环形缓冲区     在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。 定义四个信号量： empty——表示缓冲区是否为空，初值为n。 full——表示缓冲区中是否为满，初值为0。 mutex1——生产者之间的互斥信号量，初值为1。 mutex2——消费者之间的互斥信号量，初值为1。     设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。 生产者进程 while(TRUE){      生产一个产品;      P(empty);      P(mutex1)；      产品送往buffer（in）；      in=(in+1)mod n；      V(mutex1);      V(full); } 消费者进程 while(TRUE){  P(full)    P(mutex2)；    从buffer（out）中取出产品；    out=(out+1)mod n；    V（mutex2）；    V(empty);    消费该产品;    }   需要注意的是无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。应先执行同步信号量的P操作，然后再执行互斥信号量的P操作，否则可能造成进程死锁。 桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。 分析在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。     解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下： int S＝1; int Sa＝0; int So＝0;       main()       {         cobegin             father();                  son();                    daughter();            coend     ｝     father()     {         while(1)           {             P(S);             将水果放入盘中;             if（放入的是桔子）V(So);             else  V(Sa);            }      }     son()     {         while(1)           {              P(So);              从盘中取出桔子;              V(S);              吃桔子;             ｝     }     daughter()     {          while(1)             {               P(Sa);               从盘中取出苹果;               V(S);               吃苹果;             ｝ ｝

40 互斥与同步 同步原语 互斥量（锁） 锁类似于信号量，但在一个实例中只有一个线程能操作锁。也就是说锁实际上是特殊的信号量，其资源只有1个。
Thread A …… mutex lock(); sum=sun+1; mutex unlock(); Thread B …… mutex lock(); sum=sun*2; mutex unlock(); 同步原语 互斥量（锁） 锁类似于信号量，但在一个实例中只有一个线程能操作锁。也就是说锁实际上是特殊的信号量，其资源只有1个。 锁上的两个基本的原子操作: Acquire()或lock():以原子形式等待锁状态到“开锁”，等到后进临界区操作，并设置锁状态为“上锁”。 Release()或unlock(): 以原子状态改变锁状态从“上锁”到“开锁”。

41 互斥与同步 同步原语 事件 事件(Event)是WIN32提供的最灵活的线程间同步 方式。 事件存在两种状态： 事件可分为两类：
激发状态(signaled or true) 未激发状态(unsignal or false) 事件可分为两类： 人工重置：这种对象只能用程序来手动设置，在需 要该事件或者事件发生时，采用SetEvent及 ResetEvent来进行设置。 自动重置：一旦事件发生并被处理后，自动恢复到 没有事件状态，不需要再次设置。

42 进程、线程和并行程序设计 内容 进程的概念 什么是线程 线程的设计 互斥与同步 并行程序设计的常见问题

43 并行程序设计的常见问题 更多的线程意味着更高的性能吗？

44 并行程序设计的常见问题 更多的线程意味着更高的性能吗？ 原因: 有用的尝试 线程启动和终止的代价掩盖了有用的工作 共享固有硬件资源的开销
频繁切换进程或线程容易引起Cache颠簸 切换线程本身有代价 有用的尝试 运行的线程数量最好低于等于硬件线程数 用OpenMP来做工作 使用线程池 任务窃取 Overhead from having to share fixed hardware resources: 如线程太多，使用cache资源太多，就有可能在频繁淘汰cache数据的时候造成各线程实际上在彼此淘汰对方的数据，结果在线程切换中数据频繁进出Cache形成颠簸而使性能下降。虚存的管理和使用上也有类似情况。 另外，一个称为护航(convoying)的问题会出现，这个现象是一个线程在进入临界区后，因为时间片到而被挂起，这时，线程被挂起，而它占用的锁或信号量却没有放开，致使更多等待该临界区的线程被困。 使用OpenMP的好处是它能择优设定线程个数，并管理线程 线程池是一组由池中的软件线程所服务的任务的集合，该结构用于维持一组长期存在的软件线程，每个软件线程完成一个任务后就立即接受下一个任务，消除了线程因完成短期任务而进行的初始化过程所带来的开销。 任务窃取（ Work stealing ）是指每个线程都有自己私有的任务集合。当一个 线程运行完自己的任务后，在程序员自己制定的任务调度算法下，从其他线程的任务集合中窃取任务来运行。任务窃取实现了较好的cache利用率和负载平衡，因为该线程往往会重用自己cache中常用的数据。制定好的窃取算法是关键

45 并行程序设计的常见问题 竞争激烈的锁 优先级倒置 竞争激烈的锁的解决方法
如果不是资源抢占式优先级，则有可能一个低优先级的线程占用了锁，而高优先级的线程等待并可能错过临界期限。 优先级倒置的解决办法 优先级继承 优先级顶置 竞争激烈的锁的解决方法 资源复制 将资源分区，并用一个独立的锁来保护每个分区 细粒度锁 读者-写者锁 同一时刻只有一个写者可以获得锁，但多个读者可以同时获得锁，注意可能造成写者被饿死 三个线程L,M,H，优先级为低，中，高。L占用资源R，H得不到R而被挂起，则M如果不申请R则可以因为线程优先级高（非资源优先级）等原因而优先于H而替换了L在CPU中运行，L在等待M让出CPU，H等L让出R，因此低优先级的M间接阻塞了高优先级的H。 优先级继承：让获得R的线程L继承H的优先级，这样L就不会被M打断而尽快的结束，释放R 优先级顶置：把所有资源的优先级安排为最高线程优先级+1，凡是拥有该资源的线程的优先级被临时赋予该资源的优先级，这样使其成为最高优先级线程，能保证尽快结束，释放资源。 如果多个线程申请锁的速度比线程执行对应临界区的速度快，就形成对锁的激烈竞争 Priority inversion:优先级倒置，如果不是抢占式优先级，则有可能一个低优先级的线程占用了锁，而高优先级的线程等待。 Fine-grained locking：细粒度锁 Reader-writer lock:同一时刻只有一个写者可以获得锁，但多个读者可以同时获得锁，注意可能造成写者被饿死

46 并行程序设计的常见问题 非阻塞算法 非阻塞算法具有的特征 比较并交换 无阻塞：只要没竞争，线程就可以持续执行 无锁：系统整体持续执行
无等待：每个线程都可以持续执行，哪怕遇到竞争 比较并交换 CAS原语操作 内存位置V 预期原值A 新值B Public class NonblockingCounter { private AtomicInteger Value; Public int getValue() {return value.get()}; public int increment() { int v; do { v=value.get(); } while(!value.compareAndSet(v,v+1)); return v+1; } Three different non-blocking guarantees Obstruction freedom 无阻塞 Lock freedom 无锁 Wait freedom 无等待 CAS操作如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置的值更新为新值。否则处理器不做任何操作。 CAS有效地说明了“我认为位置V应该包含值A，如果是的，则将B放到这个位置。否则，不要更改该位置，只告诉我这个位置现在的值” compareAndSet方法规定“将这个变量更新为新值，但是如果从我上次看到这个变量之后，其他线程修改了它的值，那么更新失败” 现代处理器提供了可以自动更新共享数据，而且能够检测到其他线程的干扰，而compareAndSet就用这些代替了锁定。

47 并行程序设计的常见问题 非阻塞算法 ABA问题 Cache行乒乓效应
CAS原语操作的时候，如果有一个线程将该数字从A改到B又改回A，其他线程可能就感知不到这一变化，从而引起混乱。 不要重用A 可以利用加值的版本号等方法来解决 Cache行乒乓效应 由于cache行没有锁，所以多核线程使用同一行的 话会引起强烈颠簸 Three different non-blocking guarantees Obstruction freedom 无阻塞 Lock freedom 无锁 Wait freedom 无等待 ABA problem 无阻塞执行的时候，要更新一个数据不是对其上锁，而是重复写这个数据，直到发现该数据被改掉，如果此时刚好有另一个线程将该数字从A改到B又改回A，本线程可能就感知不到这一变化。 Cache line Ping-ponging 由于cache行没有锁，所以多核线程会使用同一行的话会引起强烈颠簸 Memory reclamation problem 比如C语言的一个线程在回收一个指针的时候不知道是否有别的线程在用（因为没有锁）

48 并行程序设计的常见问题 非阻塞算法 内存回收问题 一些建议 比如C语言的一个线程在回收一个指针的时候不知 道是否有别的线程在用（因为没有锁）
直接使用原子增和原子减一般来说是安全的 对链状结构构造非阻塞算法要使用公认正确的算法 Three different non-blocking guarantees Obstruction freedom 无阻塞 Lock freedom 无锁 Wait freedom 无等待 ABA problem 无阻塞执行的时候，要更新一个数据不是对其上锁，而是重复写这个数据，直到发现该数据被改掉，如果此时刚好有另一个线程将该数字从A改到B又改回A，本线程可能就感知不到这一变化。 Cache line Ping-ponging 由于cache行没有锁，所以多核线程会使用同一行的话会引起强烈颠簸 Memory reclamation problem 比如C语言的一个线程在回收一个指针的时候不知道是否有别的线程在用（因为没有锁）

49 并行程序设计的常见问题 可重入函数 一个可重入函数在执行中不使用静态数据，不返回指向静态数据的指针。所有使用到的数据都有函数的调用者提供。
一个函数可能会被多个执行流并发访问，因此该函数需要是可重入的。 一个可重入函数在执行中不使用静态数据，不返回指向静态数据的指针。所有使用到的数据都有函数的调用者提供。 对于返回指向静态数据的指针的非可重入函数的改造 返回指向动态分配空间的指针，调用者负责释放资源，函数的参数不用修改，但这样不安全，所以不推荐。 使用由调用者提供的存储空间（推荐使用），要修改函数的参数 在连续的调用之间（由函数）保存信息的改造 由调用者负责保存

50 并行程序设计的常见问题 可重入函数 不可重入函数 可重入函数 char *strtoupper(char *string) {
static char buffer[MAX_STRING_SIZE]; int index; for(index=0;string[index];index++) buffer[index]=toupper(string[index]); buffer[index]=0; return buffer; } char *strtoupper_r( char *in_str, char *out_str ) { int index; for(index=0;in_str[index];index++) out_str[index]=toupper(in_str[index]); out_str[index]=0; return out_str; } 不可重入函数 可重入函数

51 并行程序设计的常见问题 线程安全的函数与函数库 一个线程安全的函数通过加锁的方式来实现多线程对共享数据的安全访问 为共享资源加锁
使用非线程安全函数库的解决方法 使用作用于整个函数库的锁，在每次使用该函数库的时候加锁 使用作用于单个库组件或是一组组件的锁 在Windows下，要动态链接线程安全版本的运行库，就需要使用编译选项/MD，如果要调试程序，编译选项是/MDd

52 并行程序设计的常见问题 内存问题 带宽 Cache的利用 使用更紧密的压缩（pack）数据 减少核间移动数据的频繁度 最小化数据移动
使用整数时，根据实际情况选择够用且长度最短的 整数类型 用一位表示一个布尔值 减少核间移动数据的频繁度 Cache的利用 最小化数据移动 Cache遗忘分块技术-将整个问题递归地划分成更小 的子问题，最终每个子问题变的非常小能够放到 cache中。 重组代码的顺序 Cache-oblivious blocking － Cache遗忘分块技术，将整个问题递归地划分成更小的子问题，最终每个子问题变的非常小能够放到cache中。 重组代码顺序比如第二章中调整循环嵌套顺序等

53 并行程序设计的常见问题 Cache相关的问题 伪共享（多个核操作同一Cache行的不同部分） 存储一致性（对存储器操作的顺序要确定）
解决办法 尽可能采用专用数据 利用编译器的优化功能来制定存储数据的边界对齐 存储一致性（对存储器操作的顺序要确定） 对同步变量的访问满足一致性要求 对同步变量的访问，只有在以前的写操作在各处都完成之后才能完成 对数据的读或写，只有在以前的对同步变量的操作完成之后才能完成 False sharing 伪共享 当多个核或线程操作同一cache行的不同部分的时候，会出现乒乓效应