毕业论文范文——消息并行编程模型中的任务调度算法研究

本科生毕业论文论文题目 消息并行编程模型中的任务调度算法研究 学生姓名 学号 专 业 电子信息工程（试验班）年级 指导教师 职称 讲师、研究员 学 院 信息与电气工程学院 中国农业大学教务处制年 月中国农业大学学士学位论文 摘要摘 要随着多核处理器的发展，并行编程显得越发的重要起来。任务并行编程是这些年来的研究重点，但其采用共享存储的方式，极易产生诸如数据冲突、原子性违反、死锁等难以调试的并发错误。采用消息并行编程模型可以很好的避免这些问题，但又引入了消息通信开销。因此，如何设计任务调度算法使程序能以较适开销获得较好的并行性能具有重要的研究意义。本文首先介绍了任务并行编程模型Cilk的相关语言机制，并详细剖析了其高效的任务窃取策略。然后以Erlang和Go语言为背景介绍了消息并行编程技术，主要包括通信模块的实现，任务调度的实现。在上述研究的基础上，我们实现了自己的消息并行编程模型LibTSC。LibTSC采用了协程这一轻量级的任务机制，实现了任务窃取来作为负载平衡策略，并针对消息通信的特点对调度器做出了相应的优化。关键词：协程 并行编程 消息通信 任务窃取I中国农业大学学士学位论文 AbstractAbstractWith the development of multi-core processors, parallel programming is becoming more and more important.Task parallel programming is the focus in these years, but it used the shared memory, which is easy to produce such as data conflict, atomic violation,deadlock and so on concurrent error that is difficult to debug.The messages parallel programming model can avoid this problem well, but it also lead in the overhead of messages communication.Therefore, how to design the task scheduling to make the program obtain better parallel performance with a comfortable spending has important research significance.This article first introduces the task parallel programming modelCilk language, and analyzes its efficient strategy of work stealing in detail.Then on the background of Erlang and Go, we introduced the message parallel programming technology, mainly including the realization of the communication module and task scheduling mechanism.On the basis of the above research, we achieved the message parallel programming model-LibTSC.LibTSC adopted a light-weight task mechanism -coroutines, implement the work stealing mechanism as the load balancing strategy, and in the light of the characteristics of messages communication we make corresponding optimization in the scheduler.Key words：coroutines, Parallel programming, message communication, work stealingII中国农业大学学士学位论文 目录目 录III中文摘要I英文摘要II第一章 绪论11.1 研究背景及意义11.2 任务并行编程模型的相关概念21.3 任务并行编程语言Cilk51.4 研究目标、内容和技术路线12第二章 基于消息的并行编程模型132.1 Erlang中的任务调度策略介绍132.2 Go语言的任务调度策略介绍152.3 任务间消息通信机制19第三章 消息并行编程模型实现263.1 LibTSC体系架构263.2调度器基础协程实现263.3 消息通信机制channnel的实现283.4 任务派生算法设计313.5 负载平衡策略333.6 调度器的进一步优化35第四章 性能分析评价384.1 实验环境384.2 整体性能测试38第五章 结束语405.1 本文工作总结405.2 下一步工作计划40参考文献41致谢43作者简介44中国农业大学学士学位论文 第一章 绪论第一章 绪论1.1 研究背景及意义著名的“摩尔定律”指出：当价格不变时，集成电路上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍。由于能耗、工艺等问题，多年来通过提高处理器主频来提升性能的方法已经达到了物理极限，于是为了充分利用芯片上增加的器件，处理器厂商不可避免的向多核方向发展。然而多核处理器的核心数目并没有按照理论上的“摩尔定律”增加，而是增长的相对缓慢。例如服务器或PC电脑的处理器早在2006年就已经进入了四核时代，但直至2010年才迈入六核时代，2013年才刚出现12个核的处理器。芯片厂商并没有盲目的追求处理器核心数目的增长，而是很注意提高单核计算的性能。之所以出现这种现象，主要还是由于并行软件的发展速度远远落后于硬件，实际可执行的并行程序并不多。多核处理器的发展使得IT行业对并行程序的需求大大增加，面向多核甚至异构多核的高生产率程序开发方法和新的并行编程模型也如雨后春笋般浮现，例如MIT开发的Cilk1，Intel的TBB2，IBM的X103等。这些项目的主要设计思路就是降低并行程序设计的难度，提高软件生产效率，比如，IBM 2003年启动的X10其寓意就是要使开发效率提升10倍。这些新的并行编程模型的一个主要特征就是支持任务并行方式，因为与任务并行方式相对的数据并行方式更多的是使用在科学计算类应用中，相对而言任务并行方式更适合处理诸如web服务、图遍历、图搜索算法、通信领域中的信令控制、传统桌面应用等更多类型的程序。然而，上述的编程模型都采用共享存储的方式，极易产生诸如数据冲突、原子性违反、死锁等并发错误。共享内存的编程方式在语义上无法界定多任务间的执行顺序，导致多线程执行具有不确定性，使得错误很难发现和调试。尤其对于大规模的应用程序，由于采用模块式开发，特别是会采用第三方函数库，在不同的函数调用间几乎无法避免数据冲突（data race）的出现。数据竞争错误发生的主要原因是多个并行执行的任务对共享变量进行同时访问，并且至少有一次写访问。如图1-1所示的左侧代码，当其串行时，程序输出的结果是确定的，即x的值为1。当程序并行执行时，由于task1对x进行的自加操作和task2取x值进行判断的先后顺序是不确定的，进而导致输出结果的不确定。当task1对x进行自加操作在前时，输出结果与程序串行执行时相同；但当task2取x值进行判断在前时，会导致输出的x值为2，这明显与程序正确执行的结果不符。另一种主流的基于消息通信的并行编程模型，要求不同任务间的数据交互以显式消息发送和接收的方式实现，可以很大程度上避免数据冲突错误。使用消息并行编程模型修改上面提到的数据冲突示例程序，修改后的程序见图1-1右侧所示。这个程序中，task1执行完x自加操作后会发送消息，告诉task2我已经完成对数据的操作，而task2在没有接收到task1的消息之前，不会进行下面的取值判断操作，这样就避免了前面提到的数据冲突错误。图1-1 数据冲突程序举例基于消息的并行编程模型主要应用在分布式存储系统中，但近期产业界已经越来越认可在共享存储系统中同样适用基于消息的显式并行编程方式。尤其如Google公司最近推出的Go语言，尽管还是共享内存空间但明确建议程序员使用显式的消息通信方式，不鼓励直接使用锁等传统的互斥手段。基于消息的任务并行编程模型，尽管可以更好的保证程序执行的确定性和正确性，但是目前的任务调度算法很少考虑引入任务间的通信的情况，如何设计综合通信开销、负载平衡的任务调度算法使得程序能以较适能耗获得较好并行性能将是本文的研究重点。1.2 任务并行编程模型的相关概念1.2.1任务派发和同步机制派生和同步是并行程序中两个基本的控制结构。派生表示在“父”函数中对一个“子”函数的调用，但与普通的函数调用不同的是，被调用的“子”函数能够与调用者“父”函数一起被并行执行。同步则是一个“等待”的含义，他表示要等待所有派生的“子”函数完成后，“父”函数才能继续后续代码执行。我们使用Cilk语言中引入的strand 概念，来说明任务并行编程模型如何把代码中串行执行的部分和那些可以并行执行的部分区分开来。 strand用来描述程序中串行部分，更准确地说，strand的定义是“不包含任何并行控制结构的任意指令序列”。这样一个串行程序可以由许多短到只有单条指令的strand序列构成，或者是由包含整个程序的单个strand构成，或者是由其它任意划分构成。一个不是某个更长strand一部分的strand被称为最大strand，也就是起点和终点为并行控制结构的strand。传统串行程序的描述通常使用调用关系图或类层次图，对于并行程序，我们使用strand图来表达其中的串行或并行结构，如图1-2所示。strand图是一个有向无环图（DAG），其中，strands表示为直线和弧线（边），并行控制结构表示为圆形节点（顶点）。在该图中1、2、3、4都是strands，但其中只有strand2和strand3可以并行执行，A、B为并行控制结构，其中A为派生，B为同步。图1-2 strand图在并行程序中，派生的输入有且只有一个，输出有两个；同步的输入有两个或者更多，但输出只有一个。图1-3是一个拥有两次派生的strand图，在图中，strand2和strand3可以并行执行，strand2和strand4、strand5也可以并行执行。图1-3 两次派生的strand图但可以并行执行并不意味着就一定会并行执行，调度器会动态做出决定。实际上strand图只是用来表示Cilk程序中的串行和并行结构，并不代表程序的真实执行情况，因此strand图是不依赖于程序所运行之上的处理器数目的。有了上面的描述程序并行和串行结构的方法，就可以开始分析一个并行程序的性能了。为上面拥有两次派生的strand图的每一个strand加上以毫秒为单位的strand执行时间(处理器时间)，如图1-4所示。图1-4 带有执行时间的strand图工时的定义是完成程序所需的处理器时间总数，也就是所有标签数字之和，它代表着如果该程序在单个处理器上执行，它将运行的时间。在图1-4所示的DAG图中，6个strand的工时是55毫秒，也就说，这个程序在单个处理器上的执行时间是55ms.跨度，有时也被称作关键路径长度，是由程序起点到终点最长的一条路径，它表示在理想状态下（例如，没有调度开销）以及无限多处理器可用时，该程序会运行的时间。从在上面的strand图中剥离出的关键路径长度如图1-5所示。在这个strand图中，从起点到终点最长的一条路径的时间总和是34毫秒，也就是说，跨度是34毫秒。图1-5 关键路径长度1.2.2 并行任务执行单元进程、线程和协程进程是操作系统中最重要的一个概念，基本上是说程序执行的实例，它包括正在执行的程序代码以及其对应的数据，还包括了进程所占用的虚拟内存，信号量，文件目录，文件句柄等等。可以看出，创建一个进程代价是比较高的，所以操作系统中的进程数往往是有限的，不能无限制的增长，因为他要耗费太多的系统资源。进程之间可以互相通信，通过这种方式，来完成进程之间的沟通与协作。进程间通信的主要有两种方式：第一种是信号量，通过向其他进程发送信号，内核接收到这个请求，然后通知接受信号的进程来处理；第二个种方式是通过管道，两个进程共享一个管道信息，一个进程往管道的一端写数据，另外一个进程从管道的另外一端接收数据，从实现原理来看，更像是两个进程共享一段内存信息。在进程调度上，都是由操作系统内核进行调度。正常情况下，一个进程有一定的执行时间，当发生以下几种情况的时候，进程会被迫让出时间片，腾出CPU给其他进程，包括：1.当前正在执行的进程陷入I/O，被阻塞；2.进程被人为发送中断信号中断；3.进程用完时间片；4.有优先级更高的进程要执行，被抢占。由于进程进行一次调度，系统上需要做很多的工作，比如：保存当前进程的调用栈信息，cpu各个寄存器信息，虚拟内存交换，保护相关的资源等等，所以进行一次进程切换的代价是比较高的。由于创建进程的代价太高，所以在操作系统中，又出现了线程的概念，简单的说，就是一个进程可以拥有多个线程，每个线程都会共享进程所占用的资源信息，包括虚拟内存，文件资源等等。因此，线程所占用的资源远远小于进程，系统中就可以创建相对数量较多的线程，这些线程共享一个进程所占有的所有资源。在线程之间，不仅仅可以使用进程之间的通信方式：信号量、管道，还可以通过共享内存的方式进行通信。在调度层面，同一个线程组（共享一个进程）的切换相对比较高效，但是不同线程组之间的切换其实和进程切换效率差不多。需要特别提一下的是，在Linux操作系统中，其只提供了轻量进程的支持，未实现线程模型，因而线程在Linux内核中仍然是进程，只不过线程在创建时克隆了父进程相关的资源，因此创建出来的进程表现为“线程”。目前Linux中最流行的线程机制为LinuxThread，所采用的就是线程与进程一对一模型，线程的调度交给Linux的内核，而在用户级实现线程管理机制。使用线程来执行任务时会涉及到一个问题，就是这个执行的任务如果调用了非阻塞I/O，则需要等I/O完成了，才能进行后续的处理。为了解决这种情况，我们必须保存这个任务的上下文，然后跳过这个任务，去执行下一个任务，等操作系统I/O完成之后，再通知执行线程，那么这个线程会找到当时没有执行完成的任务，继续执行。这里面其实也会涉及到任务的上下文切换，但是这种切换代价很低，是可以在线程里面实现的，不需要调用内核完成切换，避免了性能开销。以上说的就是一个协程机制，这种机制的思路就是在用户级设计一个结构来调度任务，这个结构名字就要做协程。我们知道多个线程相对独立，有自己的上下文，切换受系统控制；而协程也相对独立，有自己的上下文，但是其切换由自己控制，由当前协程切换到其他协程由当前协程来控制。使用协程有三个好处：1.避免了传统的函数调用栈，使得无限递归成为可能；2.用户态的线程调度，极大降低上下文切换的开销，使得近乎无限并发的“微线程”成为可能；3.由于可以在用户态进行手工线程调度，这样可以避免锁机制。最后由图1-6来说明进程、线程和协程三者之间的关系：图1-6 进程、线程、协程三者关系1.3 任务并行编程语言Cilk1.3.1 Cilk语言1994年麻省理工学院的 Robert & Blumofe & Leiserson等人开展了基于任务窃取机制的调度算法研究4，证明了任务窃取机制能在引入很小开销的情况下有效实现负载均衡。1995年Robert 等人继续在上述研究的基础上开发出基于C的并行编程模型Cilk语言1。Cilk语言采用了在理论和实际中性能都非常好的任务窃取调度算法，并首次使用“工时”和“关键路径长度”来衡量一个使用Cilk编写的并行程序的性能。一个Cilk程序的执行过程可以被看作是一个动态展开的有向无环图（DAG），如图1-7所示，图的节点代表着一系列的线程，线程上运行着程序任务。图中向下的边表示执行中的父任务派生（spawn）出一个新的子任务，一次任务派生类似于一次子函数调用，但不同的是父任务可以和子任务并行执行，并且在接下来的执行中，父任务还可能再派生出新的并行执行的子任务。因此，父任务是不会像正常的C函数调用那样因等待子函数返回而被阻塞，相反的父任务还会继续派生出一个新的延续任务来执行后续的代码，并接收子任务返回的数据。父任务和派生出来的延续任务实际上是同一段程序，在图中用水平的线连接起来。此外，图中还有一类向上的弯曲曲线，代表着子任务执行完毕后与父任务进行数据同步。这样，一个Cilk程序就展开成了一个由节点和边构成的派生树，并且程序在执行时会按照DAG图约束的先后顺序进行执行。图1-7 Cilk程序并行执行模型图1998年Matteo Frigo 等人在Cilk-1的基础上继续优化5，发布Cilk-5版本，新版本仍然采用与第一版相同的“任务窃取”调度算法，但语言本身已经完全被重新设计，运行时系统也被重新构造。新实现版本的效率受助于一项从调度算法理论分析产生的清晰战略：集中精力最大限度的减少贡献于工时的开销，即使以增加关键路径的开销为代价。尽管，直觉上看起来好像是把开销转移到了关键路径，但是这种“工时第一”原则使得Cilk-5的实现更便捷，在当时的大多数机器上Cilk-5派生一个并行任务的典型开销只有C函数调用的2到6倍。很多跑在单线程上的Cilk程序与等价的C程序相比实际上没有明显的退化。特别的，Cilk-5提出了新奇的“双版本”编译策略和在任务窃取调度中实现就绪双端队列的“THE协议”。此外，新版本使用三个关键字来简化Cilk的使用。不同于Cilk-1中的调度器是可以确定的一段代码，在Cilk-5中编译器和运行时系统都承担起调度的责任。因此，运行时系统在进行调度时时刻遵循工时第一原则，也就说使在计算中由工时承担的调度器开销最小化，明确说来，就是将负载从工时转移到了关键路径。工时第一原则启发了编译Cilk程序的“双版本”策略，在编译中用到的cilk2c编译器是一个类型检查的源到源编译器，其通过调用Cilk的运行时库将一个Cilk程序翻译成一个C程序。C程序再通过gcc编译器产生可执行代码。cilk2c编译器针对每个Cilk程序生成两个版本一个“快”版本和一个“慢”版本。“快”版本在很多方面和Cilk程序的C省略大致相同，在大多数串行语义的情况下执行，“慢”版本在少数有并行语义并需要相关记录的情况下执行。所有在“慢”版本中产生的调度开销都只增加于关键路径的开销，而没有增加工时开销。工时第一原则也启发了运行时负载平衡调度器中的“THE”协议。Cilk的调度器采用了“任务窃取”算法，其中空闲处理器（称为偷取者），偷取繁忙处理器（称为受害者）的任务。Cilk的调度器保证窃取的开销只贡献于关键路径的开销，而不增加工时开销。然而，在窃取过程中很难避免由潜在受害者引起的互斥开销，进而导致工时增加。为了减少工时开销，Cilk-5使用了迪杰斯特拉协议（也称之为THE协议）而不是锁，来管理在任务窃取算法中的就绪线程的运行时双端队列。THE协议的一个额外好处是，它允许一个异常作为信号传递给工作线程，这在Cilk终止机制中得到了显著地应用。之后，开发者创建了一个Cilk Arts的商业公司，推出Cilk的商业化版本Cilk+，它同时支持对C和C+的扩展，并兼容GCC和微软的编译器。2009年，Intel公司收购Cilk Arts公司和Cilk+技术，扩展实现了并行数据结构Reducer视图，发布了融合在其编译器内的版本Intel Cilk Plus。在Cilk-5之后，用户可以使用三个关键字来便捷的使用Cilk技术获得并行程序性能的提升：1. cilk_spawncilk_spawn关键字修饰函数调用语句，表示派生出一个新的子函数，以告知Cilk运行时系统该函数可以（但不是必须）和调用者并行执行。2. cilk_synccilk_sync语句表示同步等待，即当前父任务不能继续和衍生的子任务并行执行，需要等所有子任务执行完返回之后，当前父任务才能继续执行。cilk_sync只同步由该父任务衍生的子任务，其他函数衍生的子任务并不受影响。在每个包含cilk_spawn的函数的结尾，存在隐式的cilk_sync。3. cilk_forcilk_for表示一个循环包含的迭代可以被并行执行，它用于取代常规的C、C+中的for循环。cilk_for的串行化就是将cilk_for换成for的结果。因此，一个cilk_for的循环必须是一个合法的C/C+ for循环，但是cilk_for循环有比C/C+的for循环更多的限制。因为循环体要并行执行，循环控制标量和非本地变量均不能被修改，否则将导致数据竞争。1.3.2 Cilk的任务调度模型Cilk编写的程序形成的strand图并不依赖于处理器的数目，调度器模型描述了运行时系统是如何将strand映射到工作线程的。引入并行结构后多个strand可以并行执行，但是在Cilk程序中，可以并行执行的strand并不一定会并行执行，调度程序会动态作出决定。考虑下面这个Cilk程序，图1-8是其strand图。Func1 1: A: spawn func 3();spawn func()2; B: sync; 4:spawn衍生出一个新的可以并行执行的任务，当有多个工作线程可用时，这个程序有两种可能的执行方式：1.整个程序由单一工作线程执行，或2.调度器选择在不同的工作线程上执行strand2和strand3。图1-8 strand图为了保证串行语义，衍生出来的函数（子任务，即例中的strand3）总是和进入衍生节点的那个strand在同一个工作线程上执行。于是，在这个例子中，strand1和strand3总是在同一个工作线程上执行。如果此时有其它工作线程可用，那么strand2（延续部分）可以在另外的工作线程上执行。我们称这样为窃取（steal），也就是说延续部分被新的工作线程窃取了。当出现第一种情况，即窃取不发生时，在A点父任务调用子任务，然后等待子任务执行完毕返回，父任务继续执行，在B点同步时不进行任何操作，执行过程如图1-9所示。此时程序是在一个线程上串行执行的，没有新的线程来并行执行。图1-9窃取没有发生当窃取行为发生时，如图1-10所示，在A点，原线程（图中的strand1）执行新衍生的子任务task3，另一线程（图中用虚线表示的strand2）窃取延续部分task2进行执行。在B点进行同步时，若task 3已经执行完，执行task2的线程则继续执行task1的4点的指令；若task 3没有执行完，则该线程挂起该任务并窃取其它任务并执行，直到task 3执行完，由执行task3的线程唤醒挂起的任务，然后执行task1的4点的指令。从这个过程中我们可以看出，strand4将由最后到达同步点的工作线程执行。图1-10 窃取行为发生在程序运行过程中，Cilk的运行时系统会将用户程序中的strand映射到操作系统线程上，为了保证程序的串行语义，Cilk的运行时系统采取了一些与众不同的策略。关于cilk的映射关系，需要重点理解以下两点：在cilk_spawn之后，衍生出来的函数总是和进入衍生节点的那个strand在同一个工作线程上执行。如果此时有其它工作线程可用，那么延续部分可以在另外的工作线程上执行。而cilk_sync之后，程序执行可以由进入同步节点的任一工作线程继续，主要是取决于哪一个线程最后到达同步点。1.3.3任务窃取算法的发展在并行编程模型中，程序员只需关注于任务划分，运行时系统实现的调度算法会负责任务映射和调度，从而实现负载平衡。调度算法主要有任务共享调度和任务窃取调度两种，任务共享调度是多个线程共享一个任务池或任务队列，新产生的任务放入到任务队列中，而线程从任务队列中拿任务执行；任务窃取调度是每个线程都有自己的任务队列，当一个线程的本地执行队列为空时，它会主动窃取其他线程任务队列中的任务，从而保证所有线程尽可能以最大负载工作，其示意图如图1-11所示。图1-11 任务窃取示意图1981年，Burton & M.R. Sleep6对函数式语言的研究带出了最早任务窃取的实现；1991年Squillante & Nelson7对比了任务窃取和任务共享两种调度算法，结合在共享存储系统上任务迁移代价的分析，认为任务窃取调度优于任务共享调度。1993年Blelloch et al8给出多线程的任务窃取调度所需的时间和空间上限；2001年，Berenbrink et al通过理论分析得出任务窃取具有稳定性；Acar et al9对亲密性调度进行了研究，他们利用数据局部性信息进行调度，每个处理器除了拥有一个执行的任务队列以外，还有一个队列用于指向与执行任务相关的任务，窃取时优先考虑窃取这个队列里的任务。2002年，Bender & Rabin10针对异构环境中处理器的执行速度不同，提出为每个处理器估计一个执行速度和处理器间的通信代价，运行快的处理器可以打断慢的处理器，把它现在正在执行的任务窃取过来执行。经过这些先辈们研究，可以看出任务窃取调度算法是一个稳定的、负载均衡的调度算法。因此任务窃取调度算法已经成为任务并行编程模型的基础和核心。1.3.4 Cilk中的工作线程和操作系统线程的交互前面提到过，Cilk中的工作线程就是操作系统线程，在程序执行时，Cilk的运行时系统会通过操作系统自身的相关机制来分配一个“工作线程”集合，但是，Cilk程序并不会总是100%用掉所有可用的处理器。在运行一个Cilk程序时，我们通过Windows的任务管理器“性能”标签页可以明显的观察到，所有的CPU都处于忙的状态，即使这个Cilk程序是串行执行时也这样。这样看来，Cilk看似很霸道，它会消耗掉系统所有的处理器资源，不给其他程序以执行机会。实际上，运行时调度程序仍然会给其它程序分配CPU，但只要没有其它程序请求处理器，空闲的工作线程就会立即重新进行工作窃取。因此，Cilk程序看起来像一直占用100%的处理器时间，但是事实上对系统或其它程序没有不利的效果。尽管同一个Cilk strand在运行过程中不会在工作线程间迁移，但是在cilk_spawn，cilk_sync，或cilk_for语句后工作线程会发生变更，这是因为这些语句会中止一个或多个strand并创建一个或多个新的strand。由于无法控制某个特定strand由哪一个工作线程来执行，最好不要使用Windows线程本地存储或Linux Pthread线程专有数据。此外，也不要跨越cilk_spawn，cilk_sync或cilk_for语句使用操作系统锁或互斥锁，因为在工作窃取后，OS线程会发生变更，由于只有加锁的线程能进行解锁操作，就会使程序陷入死锁，不能正确运行。1.3.5 Cilk中的任务窃取实现为避免中断、轮训机制或者是硬件锁机制带来的对工时开销的增加，Cilk-5的任务窃取是基于“THE”协议实现的，按照“工时第一”原则，该协议被设计成旨在最大程度降低工时的开销。由于Cilk-5本身是为共享存储的机器设计的，在“THE”协议的实现中，窃取者和受害者线程均可以对受害者线程的任务队列进行操作。实际上，“THE”协议采用的核心理念是假定只有读写是原子操作的Dijkstra协议，由于协议中采用了三个共享的全局变量“T”、“H”、“E”分别来表示任务队列的尾部、头部和异常位置，所以取名为“THE”协议。其关键思想是，受害者线程在任务队列尾部的操作（增加或减少T）将导致工时开销的加大，而窃取者线程对任务队列头部的操作（增加H）只贡献于关键路径的开销，这样就把开销从受害者转移到了窃取者身上。为了避免多个窃取者线程对同一受害者线程任务队列的竞争，协议中也为任务队列使用了硬件锁，但是这种硬件锁的开销是被平分到关键路径长度上的。此外为了解决受害者线程和窃取者线程对这个硬件锁的争用，协议中使用了对工时开销影响微弱的轻量级的Dijkstra协议，而只有在窃取者和受害者真正发生冲突了，才求助于硬件锁。受害者向任务队列中添加一个任务的过程总是安全的，而唯一窃取者和受害者可能发生冲突的情况出现在窃取者增加H的同时受害者减少T。这时可能会有三种情况，如图1-12所示。在情况a下，窃取者和受害者都可以取到相应任务进行执行。在情况b下，队列中只有一个任务，如果受害者在减少T时没有收到窃取者的干扰，那么受害者就可以得到该任务进行执行，同样的窃取者也能偷取到该任务只要在这时受害者没有尝试获取这个任务。如果窃取者和受害者都试图取该任务执行，那么这个协议能够保证窃取者和受害者中至少一个线程可以发现H大于T。如果是窃取者发现了H大于T，它将恢复H原来的值并放弃窃取操作，如果是受害者发现了H大于T，它也会恢复H原来的值，但会在获取锁后从新开始协议，这时由于获取了锁，其他窃取者不能再从这个队列中偷取任务，这样受害者就可以取得任务进行执行不再受干扰。在情况c下，队列为空，如果窃取者尝试窃取，它将会一直失败，如果受害者尝试取任务执行也将会失败，并且线程的控制权将交回给运行时系统。“THE”协议不会陷入死锁，因为任意时刻只有一个线程能够获取到该锁。图1-12 任务窃取时可能出现的三种情况Cilk使用“E”来进行异常的传递。在上面的介绍中，“H”扮演着双重角色，它既标志着任务队列的头部，也标记着线程取任务时不能越过的位置。在完整的“THE”协议实现中，使用“E”将“H”的这两种角色区分开来，“E”标记着线程不能越过的位置，而“H”仅仅只代表着任务队列的头部。一旦出现E大于T，就说明一些异常情况发生，当然其中包括任务被窃取。但它更重要的是被用来指示其他异常，比如，可以将“E”赋值为无穷大，这样线程在下次取任务时就会发现异常。完整功能的“THE”协议的流程图如图1-13所示。图1-13 “THE”协议流程图异常机制用于实现中止操作，当一个Cilk程序执行一个终止指令时，运行时系统线性遍历该程序产生的子代任务树。它标记子代任务需要中止，并发送一个中止异常信号给正在执行子任务的处理器。线程将在下次取任务时发现这个异常，放弃执行并立即返回。1.4 研究目标、内容和技术路线1.4.1 研究目标本文将在调研任务并行编程模型Cilk的任务调度算法的基础上，以消息并行编程模型Erlang和Go语言为背景，设计消息并行编程模型，实现消息通讯模块、任务调度模块，并针对消息并行模型的特点在任务调度上做相应的优化，使得并行程序能以较适能耗获得较好的并行性能。1.4.2 研究内容1.调研相关文献和代码，分析任务并行编程模型Cilk的任务派生、调度、窃取技术的算法及实现技术；2.分析现有的消息并行编程模型Erlang和Go等语言，吸取其中的优点，设计消息并行编程模型的基本框架；3.实现消息通讯模块、任务调度模块，并针对消息并行模型的特点在任务调度上做相应的优化调研相关文献和代码实现消息并行编程模型设计消息并行编程框架实验测试模型性能完成论文1.4.3 技术路线12中国农业大学学士学位论文 第二章 基于消息的并行编程模型第二章 基于消息的并行编程模型本章将以两种消息并行编程语言Erlang和Go为基础，介绍基于消息的并行编程模型语言。Erlang语言是面向分布式应用的语言，采用轻量级进程和消息通信模型，其不支持进程间的共享，状态信息完全需要依靠消息彼此传递11-13。Go是一种新型的、并发的、带垃圾回收的、快速编译的语言。它是一种编译型语言，它结合了解释型语言的游刃有余，动态类型语言的开发效率，以及静态类型的安全性2.1 Erlang中的任务调度策略介绍由于Erlang程序是运行在BEAM虚拟机之上，早期的BEAM虚拟机是单线程运行的，直到2006年才引入了SMP版本的BEAM虚拟机，经过了若干早期版本的演化，逐渐形成了今天的版本。最新版本的Erlang可以通过命令行参数指定是否启用SMP版本虚拟机。BEAM上的调度单位是process，这是一种虚拟机上的轻量级进程（由于Erlang的process是不共享内存的，行为更像进程而非线程，因此称它为轻量级进程），不对应C语言或OS级的概念。每个Erlang进程包括一个控制块、一个栈和私有的堆空间，一些特殊的结构，如二进制数据、ETS表是进程间共享的，使用全局堆空间。BEAM虚拟机里存在一些并行的调度器，一般情况下，一个调度器会映射为一个OS线程，每个调度器拥有各自的任务队列，调度器之间的负载平衡通过引入专门的任务迁移机制得以实现，其原理如图2-1所示。通常，调度器的数量与运行平台的处理器核数或硬件线程数相等，也可以通过BEAM命令行参数指定，或在运行时动态修改。在BEAM系统中，除了process之外，还存在三种其他的调度单位：端口（ports）、链入式驱动（linkd-in drivers）和系统级活动（system level activities），这三种特殊的任务形式主要用来进行IO操作和执行其他语言的代码等功能。与一些NATIVE语言不同，Erlang的调度器14，是一个轮转而非协作式的调度器，每个进程创建时会被分配一个称为reduction的值，是一个计算量的度量（基本上等同于函数调用的次数），类似OS的时间片。进程每执行一定量的计算后，reduction值就会累计，一旦达到阈值，该进程就会给切换出去，这种调度方式在Erlang中被称为“reduction-counting”。采用轮转的调度方式能更好的防止程序设计不当而导致的个别进程饿死的情况，同时能够实现更好的实时性功能。同时，Erlang还为进程提供了四个不同的优先级：max，high，normal和low。不同优先级进程按优先级调度，同级进程按轮转方式调度。每个调度器包含3个任务队列，Max和High具有单独的队列，normal和low则位于同一个队列调度器忽略一定次数的low级进程来实现normal和low二者间的差别。Erlang调度器之所以能够实现优先级轮转调度，主要是得益于其基于虚拟机的执行方式：由于每条Erlang指令都需要经过BEAM解释执行，因此process的运行完全处于BEAM的监控之下，使得BEAM可以方便的完成对进程的切换。图2-1 BEAM负载平衡原理图此外，Erlang调度器通过定期进行“任务迁移”来达到负载平衡。“任务迁移”过程在同一时刻只能由一个调度器发起。首先，根据各调度器的任务队列的长度计算一个“Migtation limit”的值，这个值就是各调度器就绪队列长度的均值；然后，开始计算“Migataion Path”，算法是：1. 计算各队列长度与“Migtation limit”差值；2. 找到差值中正最大和负最小的队列，记录一个从前者到后者进行任务迁移路径，以达到二者都接近“Migtation limit”；3. “Migatation Path”计算完成后，在每个调度时刻，调度器都会检查该路径，根据其指导去抓取（pull）或推送（push）相应任务队列的任务，然后再重复步骤1，直到达到负载均衡。图2-2显示了上述算法实现的过程。图2-2 任务迁移算法示意图Erlang语言通过消息通信进行进程间的相互通信，保证了程序运行的正确性，其采用的轮转式调度和任务迁移策略，也非常好的满足了负载平衡的要求。但轮转式调度和任务迁移策略实现的前提是必须要求语言是基于虚拟机运行的，这不仅限制了平台适应性，而且虚拟机本身也消耗了大量开销。2.2 Go语言的任务调度策略介绍对于线程调度器，一般有3种模型：N：1，即多个用户线程运行在一个OS线程上；1：1，即用户线程和OS线程一一对应。前者的优点是用户线程切换较快，但可扩展性不好，难以很好发挥多核处理器的并行性；而后者与之相反，其能很好的利用多核并行性，但是用户线程资源开销和调度成本都比较大。第三种是N：M的模型，即一定数量的用户线程映射到一定数量的OS线程上，从而在调度开销和并行性之间取得较好的折衷。Go1.1中，Dmirty Vyukov重新设计了Go的调度器，使其由原来的N：1模型进化到M：N模型，从而使Go在并行编程性能上有了显著的提升。Go的新调度器模型主要涉及3个核心概念：M、P及G，如图2-3所示：图2-3 Go调度器的三个核心数据结构G代表Go语言的用户级线程，也就是通常所说的Goroutine，结构体G中的部分元素如图2-4所示。其中goid是这个goroutine的ID，status是这个goroutine的状态，如Gidle、Grunnable、Grunning、Gsyscall、Gwaiting、Gdead等。图2-4 结构体G中的元素从结构体中可以看到，其中包含了栈信息stackbase和stackguard，有运行的函数信息fnstart。这些就足够成为一个可执行的单元了，只要得到CPU就可以运行。所有的goroutine都被放到了一个链表中，结构体的alllink域用于将链表结点起来。goroutine切换时的上下文信息是保存在结构体的sched域中的。goroutine是轻量级的“线程”或者称为协程，切换时不必陷入到操作系统内核中，所以保存过程很轻量。再来看一下结构体G中的Gobuf，其实只保存了当前栈指针，程序计数器，以及goroutine自身。记录g是为了恢复当前goroutine的结构体G指针，运行时库中使用了一个常驻的寄存器extern register G* g，这个是当前goroutine的结构体G的指针。这样做是为了快速地访问goroutine中的信息，比如，由于实现分段栈的原因，Go中并没有使ebp寄存器，不过这可以通过g-stackbase快速得到。结构体M是machine的缩写，是对机器的抽象，它对应着操作系统的物理线程。M必须关联了P才可以执行Go代码，但是当它处理阻塞或者系统调用时，可以不需要关联P，其包含的部分元素如图2-5所示。图2-5 结构体M中的元素结构体M中有两个G是比较重要的，一个是curg，代表结构体M当前绑定执行的结构体G。另一个是g0，是带有调度栈的goroutine。每个M中会有一个调用goroutine，所有调度相关的代码，会切换到该goroutine再去执行。普通的goroutine使用分段栈，初始栈大小分配的比较小，大约是4K多一点，而拥有调用栈的goroutine分配的栈大小是64K。和G类似，M中也有alllink域将所有的M链接在链表中。lockedg是某些情况下，G锁定在这个M中运行而不会切换到其它M中去。M中还有一个MCache，是当前M的缓存。P是Processor的缩写，Go1.1之后，才引入P，它的加入是为了提高Go程序的并发度，实现更好的调度，其代表着Go代码执行时需要的资源。当M执行Go代码时，它需要关联一个P，当M为idle或者在系统调用中时，它也需要P。P的数量由环境变量GOMAXPROCS来指定。所有的P被组织为一个数组，在P上实现了工作流窃取的调度器，P的结构如图2-6所示。图2-6 结构体P中的元素结构体P中的status代表着它相应的状态，如Pidle、Prunning、Psyscall、Pgcstop、Pdead。但跟G不同的是，P的状态中是不存在waiting的。在P中有一个Grunnable的goroutine的队列，这是一个P的局部队列。当P去执行Go代码时，它会优先从自己的这个局部队列中去取，这时可以不用加锁，提高了并发度。如果发现这个队列为空了，则去其它P的队列中拿一半过来，这样实现工作流窃取的调度。在窃取时需要给相应的队列进行加锁。除了上面三个基本的数据结构外，还有一个Sched是调度实现中使用的数据结构。大多数需要的的信息都已放在了结构体M，结构体G和结构体P中，Sched结构体只是一个存放的外壳，其结构如图2-7所示。可以看到，其中有M的idle队列，P的idle队列，以及一个全局的就绪的G队列。Sched结构体中的Lock是非常必须的，如果M或P等做一些非局部的操作，它们一般需要先锁住调度器。图2-7 结构体Sched中的元素假设goroutine在执行时要进入阻塞的系统调用，如果没有P，只有M的话，由于运行G的M陷入阻塞状态，M对应的OS线程就会被OS调度出去，就会导致系统线程中其他就绪的G也不能被执行。有了结构体P后，M必须与P绑定方能执行任务G，如图2-8所示。图2-8 M与P绑定执行G这样，如果M被阻塞后，运行时系统将会把P从处于阻塞的M中