高性能科学计算理论和方法课件：第四章PPT.ppt

1、用Pthreads进行共享式内存编程共享内存系统进程n一个进程就是运行在处理器上的一个程序实例n在大多数系统中，在默认状态下，一个进程的内存块是私有的：其他进程无法直接访问，除非操作系统进行干涉。n例如：如果正在使用文档编辑器写程序（一个运行文档编辑器的进程），肯定不希望浏览器（另一个进程）覆盖文档编辑器正使用的内存数据。n这一设计在多用户环境下更为重要，一个用户的进程是绝对不允许访问其他用户进程拥有的内存的。线程n我们在运行共享内存程序时，希望有些数据对多个进程都是可用的。因此，典型的共享内存“进程”允许了进程间互相访问各自的内存区域。n它们也经常共享一些区域，例如共享对stdout的访问。

2、n事实上，除了它们各自拥有独立的栈和程序计数器外，它们基本上可以共享所有其他区域。n为了方便管理，一般采用的方法是：启动一个进程，然后由这个进程生成这些“轻量级”进程。轻量级进程由此得名。n更通用的术语是线程。线程是类似于一个“轻量级”的进程。进程和线程n一个进程就是运行在处理器上的一个程序实例n线程是类似于一个“轻量级”的进程POSIX Threadsn也经常称为Pthreads线程库n一个类似Unix操作系统（如Linux、Mac OS X）上的标准库nPthreads不是编程语言 (如C或Java)，而是与MPI一样，它拥有一个可以链接到C程序中的库n它定义了一套指定用于多线程编程的应用

3、程序编程接口（ API）注意nPthreads API只有在支持POSIX的系统（Linux、Mac OS X，Solaris、HPUX等）上才有效“Hello，World程序n先来看一个Pthreads程序。在程序4-1中，主函数启动了多个线程，每个线程打印一条消息，然后退出。Hello World! (1)declares the various Pthreadsfunctions, constants, types, etc.Hello World! (2)Hello World! (3)运行一个Pthreads程序. / pth_hello . / pth_hello 1Hello f

4、rom the main threadHello from thread 0 of 1. / pth_hello 4Hello from the main threadHello from thread 0 of 4Hello from thread 1 of 4Hello from thread 2 of 4Hello from thread 3 of 4准备工作n 我们仔细研究程序4-1的代码。首先，我们注意到，这个简单的c程序只有main函数和另外一个函数。n程序中包含了我们熟悉的stdio.h和stdlib.h两个头文件，也有一些新增的不同之处。n程序的第3行包含了pthread.h头

5、文件，这是Pthreads线程库的头文件，用来声明Pthreads的函数、常量和类型等。准备工作n第6行定义了一个全局变量thread_count。在Pthreads程序中，全局变量被所有线程所共享，而在函数中声明的局部变量则（通常）由执行该函数的线程所私有。n如果多个线程都要运行同一个函数，则每个线程都拥有自己的私有局部变量和函数参数的副本。全局变量n全局变量可能会在程序中引发令人困惑的错误。n一个引发错误的例子全局变量例子n例如，我们写一个有全局变量int x的程序，函数f内也有一个名为x的局部变量，但我们却忘了在函数中声明这个局部变量x。n编译时是不会有错误或者警告出现的，因为函数f有权

6、访问全局变量x。n然而在运行时，程序却输出了奇怪的结果，这是由全局变量x引起的。过了几天，我们才发现导致全局变量x有奇怪值的原因出自函数f。全局变量n根据经验法则，应该限制使用全局变量，除了确实需要用到的情况外，比如线程之间共享变量。线程数目的生成n程序中的第15行表示从命令行中读取需要生成的线程数目。n不同于MPI，Ptheads程序和普通串行程序一样，是编译完再运行。将命令行参数作为输入值传入程序，由此来确定线程的数目，不失为一种简单方便的方法，但也并不仅仅局限于这一种方法。strtol函数nstrtol函数的功能是将字符串转化为long int（长整型），它在stdlib.h中声明n它的

7、语法形式为：n它返回由number_p所指向的字符串转换得到的长整型数，参数base是表达这个整数值所用的基（进位计数制）。n如果end_p不是NULL，它就指向number_p字符串中第一个无效字符（非数值字符）。启动线程n正如我们已经提到的，Pthreads不同于MPI程序，它不是由脚本来启动的，而是直接由可执行程序启动。n这样会增加一些复杂度，因为我们需要在程序中添加相应的代码来显式地启动线程，并构造能够存储线程信息的数据结构。pthread_t对象n代码第17行为每个线程的pthread_t对象分配内存，pthread_t数据结构用来存储线程的专有信息，它由pthread.h声明。n

8、pthread_t对象是一个不透明对象。对象中存储的数据都是系统绑定的，用户级代码无法直接访问到里面的数据。pthread_t对象nPthreads标淮保证pthread_t对象中必须存有足够多的信息，足以让pthread_t对象对它所从属的线程进行唯一标识。n例如：Pthreads有一个库函数，利用这个函数可以让线程取得它的专有pthread_t对象；还有一个pthreads函数，通过检查两个线程的pthread_t对象来确定它们是否为同一个线程。启动线程n在第1921行的代码中，调用pthread_create函数来生成线程。它与大多数的Pthreads库函数一样，有一个前缀pthread

9、，它的语法为：int pthread_create (pthread_t* thread_p /* out */ ,const pthread_attr_t* attr_p /* in */ ,void* (*start_routine ) ( void ) /* in */ ,void* arg_p /* in */ ) ;pthread_create函数n第一个参数是一个指针，指向对应的pthread_t对象。注意，pthread_t对象不是由pthread_create函数分配的，必须在调用pthread_create函数前就为pthread_t对象分配内存空间。n第二个参数不用，所以只

10、是在函数调用时把NULL传递给参数。n第三个参数表示该线程将要运行的函数；最后一个参数也是一个指针，指向传给函数start_routine的参数。Pthreads函数的返回值n大多数Pthreads函数的返回值用于表示线程调用过程中是否有错误。为了减少复杂性，在本章（以及本书后面的内容）中，我们一般忽略Pthreads函数的返回值。由pthread_create生成并运行的函数n原型： void* thread_function ( void* args_p ) ;nvoid* 可以转换成C语言中任意指针类型nargs_p可以指向一个列表，该列表包含一个或者多个thread_function函

11、数需要的数值。n类似地，thread_function返回的值也可以是一个包含一个或者多个值的列表。由pthread_create生成并运行的函数n在我们的代码中，调用pthread_create函数时，传入最后一个参数采用了一个常用的技巧：为每一个线程赋予了唯一的int型参数rank，表示线程的编号。n首先，我们先解释一下这么做的理由，然后再具体探讨如何做。线程编号n考虑以下问题：运行一个生成了两个线程的Pthreads程序，当其中一个线程遇到了错误时，我们或者用户如何才能知道是哪个线程出了问题呢？我们不能简单地输出pthread_t对象，因为它是不透明的。n如果我们启动线程时赋予第一个线程

12、编号为0，第二个线程编号为1，那么通过错误信息中线程的编号就能非常容易地判断是哪个线程出错了。线程函数n既然线程函数可以接收void*类型的参数，我们就可以在main函数中为每个线程分配一个int类型的整数，并为这些整数赋予不同的数值。n当启动线程时，把指向该int型参数的指针传递给pthread_create函数。然而，程序员会用类型转换来处理此问题：不是在main函数中生成int型的进程号，而是把循环变量thread转化为void*类型，然后在线程函数hello中，把这个参数的类型转换为long型（第33行）。关于类型转换n类型转换的结果是“系统定义”的，但大多数C编译器允许这么做。n不过

13、，如果指针类型的大小和表示进程编号的整数类型不同，在编译时就会收到警告。在我们使用的机器上，指针类型是64位，而int型是32位，为了避免警告，我们用long型替代了int型。关于线程编号和线程函数n需要注意的是，我们为每一个线程分配不同的编号只是为了方便使用。事实上，pthread_create创建线程时没有要求必须传递线程号，也没有要求必须要分配线程号给一个线程。n还需要注意的是，并非规定每个线程都要运行同样的函数。一个线程运行hello函数的同时，另一个线程可以运行goodbye函数。n与编写MPI程序的方法类似，Pthreads程序也采用“单程序，多数据”的并行模式，即每个线程都执行同

14、样的线程函数，但可以在线程内用条件转移来获得不同线程有不同功能的效果。运行线程n运行main函数的线程一般称为主线程。所以，在线程启动后，会打印一句： Hello from the main threadn同时，调用pthread_create所生成的线程也在运行。这些线程通过第33行的类型转换代码获得各自的编号，然后打印各自的消息。n注意，当线程结束时，由于它的函数的类型有一个返回值，那么线程就应该返回一个值。在本例中，线程没有需要特别返回的值，所以只返回NULL。运行线程n在Pthreads中，程序员不直接控制线程在哪个核上运行。在pthread_create函数中，没有参数用于指定在哪个

15、核上运行线程。n线程的调度是由操作系统来控制的。在负载很重的系统上，所有线程可能都运行在同一个核上。事实上，如果线程个数大于核的个数，就会出现多个线程运行在一个核上。当然，如果某个核处于空闲状态，操作系统就会将一个新线程分配给这个核。停止线程n代码的第25行和第26行为每个线程调用一次pthread_join函数。调用一次pthread_join将等待pthread_t对象所关联的那个线程结束。npthread_join的语法为：n第二个参数可以接收任意由pthread_t对象所关联的那个线程产生的返回值。在我们的例子中，每个线程执行return，最后，主线程调用pthread_join等待这

16、些线程完成并最终结束。停止线程n将这个函数命名为pthread_join的原因是，这个名字常常用于多线程的图解描述。n如图4-2所示，假设主线程在图中是一条直线，调pthread_create后就创建了主函数的一条分支或派生，多次调用pthread_create就会出现多条线程分支或派生。n当pthread_create创建的线程结束时，从图4-2中可以清楚地看到，这些分支最后又合并(join)到主线程的直线中。错误检查n为了使程序紧凑易读，我们省略了许多在“真正”程序中常见而重要的细节。n例子中的程序（以及很多其他程序）发生错误的很大一部分原因是用户的输入出错或者缺少输入。因此，检查一个程序

17、时，最好一开始先检查命令行参数；允许的话，还可以检查输入的实际线程数目是否合理。n另外，检查由Pthreads函数返回的错误代码也是一个好办法，尤其是在你刚开始使用这个库，对具体的函数功能不怎么熟悉的时候。启动线程的其他方法n在我们的例子中，用户通过在命令行键入参数来决定生成多少个线程，然后由主线程来生成这些“辅助”线程。当线程运行时，主线程会打印消息，然后等待其他线程结束。这种多线程的编程方法与MPI的编程方法类似，在MPI系统中，也会启动一组进程，然后等待它们的完成。n然而，还有一种完全不同的多线程程序设计方法。在这种方法中，辅助线程根据需要而启动。举个例子，一台专门处理旧金山湾区高速公路

18、交通信息的Web服务器，假设主线程接收请求，辅助线程完成请求。平常周二的凌晨1点，可能只有很少的网络请求，但到了晚上5点，却会出现数千个请求。因此，设计Web服务器的一个很自然的做法是，请求来到之后，主线程启动辅助线程进行请求处理。Pthreads矩阵-向量乘法Matrix-Vector Multiplication in pthreads矩阵-向量乘法n让我们用Pthreads写一个矩阵-向量乘法程序。n如果A=(aij)是一个m*n的矩阵，x是一个n维列向量，矩阵-向量的乘积Ax=y是个m维的列向量。串行的伪代码并行化代码n通过把工作分配给各个线程将程序并行化。n一种分配方法是将线程外层的

19、循环分块，每个线程计算y的一部分。例如，假设m=n=6，线thread_count（或t）为3，则计算可以按下列情况分配：并行化代码n为了计算y0，线程0将执行代码：n因此，线程0需要访问矩阵A的第0行以及向量x中的每一个元素。n更一般地，被分配给yi的线程将执行代码：使用3个线程thread 0general case并行化代码n我们发现，每个线程除了访问各自分配到的矩阵A的第i行以及y分量外，还要访问X中的每个元素。这意味着最低限度下，要共享向量x。n如果矩阵A和y是全局变量，主函数就可以简单地通过读取标准输入stdin来初始化矩阵A，乘积向量y也可以很容易被主线程打印输出。并行化代码n接

20、下来，我们只要编写每一个线程的代码，确定每个线程计算哪一部分的y。n假设，m与n都能被t整除，在例子中，m=6，t=3，每个线程能分配到m/t=3行的运算数据，而且，线程0处理第一部分的m/t行，线程1处理第二部分的m/t 行，以此类推。n所以线程q处理的矩阵行是： 第一行： 最后一行：Pthreads的矩阵向量乘法与MPI对比n用MPI编写一个矩阵-向量乘法的程序工作量比较大，因为它的数据结构必须是分布式的，即每个MPI的进程只能直接访问自己的局部内存。所以，在MPI代码中，需要显式地将x分配到每一个进程的内存中。n从这个例子看，编写一个共享内存的并行程序比编写分布式内存的程序容易，但我们接

21、下来就会看到：共享内存程序也有更复杂的情况。练习n编写完整的Pthreads矩阵-向量程序n提示：临界区（Critical sections）共享变量被改写？n因为共享内存区域是较理想的存储访问方式，所以矩阵-向量乘法的代码很容易编写。n在程序初始化后，线程只读取除了y以外的所有变量。即在主函数创建线程后，除了y以外，没有任何共享变量被改写。即使是y，也是每个线程各自改变属于自己运算的那一部分，没有两个或两个以上线程共同处理同一部分y的情况。n如果情况变了会怎样？如果多个线程需要更新同一内存单元的数据会怎样？估计值估计值的并行化n我们尝试用并行化矩阵-向量乘法的方法来并行化这个程序：将for循

22、环分块后交给各个线程处理，并将sum设为全局变量。n为了简化计算，假设线程数thread_count，简称t能够整除项目总数n。一般地，对于线程q，循环变量的范围是：n注意第一项的符号。使用线程函数来计算使用双核处理器n可以看到，随着n的增加，单线程的估算结果也越来越准确。n事实上，n每增大十倍就能获得更加精确的结果。n两个线程的运算结果与n= 105时一样，然而，对于n值较大的情况，双线程的计算结果反而变糟。事实上，多次运行这个双线程程序，尽管n未变，但每次的结果都不同。n结论：当多个线程尝试更新同一个共享变量时，会出现问题。可能的竞争条件n先看一个例子，用一条C语句将存储单元y的内容加到存

23、储单元x中去： x=x+yn机器的处理过程一般比这个式子更加复杂。n因为x和y中的值都存储在计算机的主存中，无法直接进行加法运算，需要先将它们从主存中加载到CPU的寄存器中后，才能进行加法运算。当运算完成后，必须将结果再从寄存器重新存储到主存中。可能的竞争条件n假设有2个线程，每个线程对并存储在自己私有变量y中的值进行计算。还假设将这些私有变量加到共享变量x中，主线程将x的初始值置为0。n每个线程执行以下代码： y= Compute(my_rank); x=x+y;n假设线程0计算出的结果为y=1，线程1计算出的结果为y=2，则“正确”结果就应该是x=3。n但是，事情总有意外。可能的竞争条件可

24、能的竞争条件n如果在线程0存储它的结果前，线程1就将x的值从内存复制到寄存器，那么线程0计算出的结果就会被线程1的值重写。n问题也可能反过来：如果线程1先处理数据，则最后x的结果会被线程0的值重写。n事实上，除非一个线程在其他线程从内存读取x前就把它要改写的值写回内存，否则“先到者”的结果肯定会被“后来者”重写。临界区概念n这个例子反映了共享内存编程的一个基本问题：当多个线程尝试更新一个共享资源（共享变量）时，结果可能是无法预测的。n更一般地，当多个线程都要访问共享变量或共享文件这样的共享资源时，如果至少其中一个访问是更新操作，那么这些访问就可能会导致某种错误，我们称之为竞争条件( race

25、condition)。n在我们的例子中，为了使代码产生正确的结果，需要保证一旦某个线程开始执行x=x+y，其他线程在它未完成前不能执行此操作n因此，代码x=x+y就是一个临界区。临界区就是一个更新共享资源的代码段，一次允许只一个线程执行该代码段。忙等待（Busy-Waiting）n当线程0要执行x=x+y时，它需要先确认线程1此时没有在执行同样的语句.n一旦线程0确认后，它需要通过某些办法，告知线程1它目前正在执行该语句，以防止线程1在线程0的操作完成前，执行该语句而导致出错。n最后，当线程0完成操作后，也需要通过某些办法，告知线程1它已经结束了这个语句的执行，线程1此时可以安全地执行这个语句

26、了。忙等待（Busy-Waiting）n一个不涉及新概念的简单方法就是使用标志变量，设标志flag是一个共享的int型变量，主线程将其初始化为0。而且，将下列代码加到我们的例子中：n假定线程1先于线程0完成第1行的赋值，当它运行到第2行的while循环时会怎样呢？忙等待（Busy-Waiting）n仔细观察，你会发现这个while是个空循环语句，如果条件flag！=my_rank为真，那么线程1会再一次执行对这个条件的判断。事实上，它会一直执行下去直到条件为假时，才会接下去执行x=x+y这条语句。n因为flag的初始值为0，所以直到线程0执行完flag+前，线程1都无法执行x = x+y。事实

27、上，我们发现，除非线程0发生无法恢复的错误，否则它的进度最终还是会追上线程1。n当线程0执行循环时，因为条件为假，所以会执行临界区中的x =x+y，完成后会执行flag+，从而使线程1最终进入临界区。忙等待（Busy-Waiting）n这段代码有一点很关键：在线程0执行flag+前，线程1不会进入临界区。如果严格地按照书写顺序来执行代码的话，就意味着直到线程0完成，线程1都不会进入临界区。nwhile循环语句就是忙等待的一个例子，在忙等待中，线程不停地测试某个条件，但实际上，直到某个条件满足之前（在我们的例子中，是flag! =my_rank条件为false），这些测试都是徒劳的。忙等待（Bu

28、sy-Waiting）n需要注意的是，“忙等待”这种方法有效的前提是，“严格地按照书写顺序来执行代码”。n如果有编译器优化，那么编译器进行的某些代码优化的工作会影响到忙等待的正确执行。n编译器无法知道程序是否为多线程的，所以它不知道变量x和flag的值会被其他线程修改。忙等待（Busy-Waiting）n如果我们的代码：n只被一个线程执行，那么whlle( flag ！=my_rank)和x =x+y语句的执行顺序就不再重要了。忙等待（Busy-Waiting）n编译优化为了充分利用寄存器，可以将某些语句的顺序交换。那么，代码就会变为：n这段代码会使忙等待失效。为了防止出现这种情况，最简单的方

29、法就是美闭编译优化的选项。忙等待（Busy-Waiting）n因此，我们发现忙等待不是控制临界区最好的方法。n线程1在进入临界区前，只能一遍又一遍地执行flag+，如果线程0由于操作系统的原因出现延迟，那么线程1只会浪费CPU周期，不停地进行循环条件测试。这对性能有极大的影晌。n另外，关闭编译器优化选项同样也会降低性能使用忙等待来求全局和的Pthreads程序忙等待（Busy-Waiting）n如果编译该程序并开启2个线程来运行这个程序，结果是正确的。然而，增加了计算运行时间的代码后，我们发现当n=108时，串行求和比并行求和快。在双核系统中，双线程运行这段代码历时19.5秒，而串行运算只要2

30、.8秒！n为什么会这样？是启动线程和合并线程导致的开销吗？测试线程本身的开销n可以编写一个简单的Pthreads程序来估算一下启动线程和合并线程导致的开销：n我们发现，在特定的系统上运行上述代码，从启动第1个线程到合并第2个线程之间所经历的时间少于0.3毫秒，所以导致运行慢的原因不在于线程本身的开销。忙等待（Busy-Waiting）n进一步仔细观察这个使用了忙等待的线程函数，我们看到线程的临界区是程序的第16行。nflag初始化的值为0，所以在线程0完成临界区运算并将flag加1之前，线程1必须等待。线程1开始进入临界区后，线程0也需要等待线程1完成运算。n可见，线程不停地在等待和运行之间切

31、换，显然是等待以及对条件值加1的操作使得整体的运行时间增加了7倍。忙等待（Busy-Waiting）n因为临界区中忙等待不是保护临界区的唯一方法。事实上，还有很多更好的方法。然而，因为临界区的代码一次只能由一个线程运行，所以无论如何限制访问临界区，都必须串行地执行其中的代码。如果可能的话，我们应该最小化执行临界区的次数。n能够大幅度提高性能的一个方法是：给每个线程配置私有变量来存储各自的部分和，然后用for循环一次性将所有部分和加在一起算出总和。循环后用临界区求全局和的函数(1)循环后用临界区求全局和的函数(2)循环后用临界区求全局和的函数的性能n在双核系统上运行以上程序，当n=108时，总运

32、算时间减为1.5秒，有了实质上的改进。互斥量n处于忙等待的线程仍然在持续使用CPUn互斥量是互斥锁的简称，它是一个特殊类型的变量，通过某些特殊类型的函数，互斥量可以用来限制每次只有一个线程能进入临界区n互斥量可以保证了一个线程独享临界区，其他线程在有线程以及进入该临界区的情况下，不能同时进入。互斥量nPthreads标准为互斥量提供了一个特殊类型： pthread_mutex_tn我们不使用第二个参数，给这个参数赋值NULL即可。互斥量n当一个Pthreads程序使用完互斥量后，它应该调用：n要获得临界区的访问权，线程需要调用：互斥量n当线程退出临界区后，他应该调用：n调用pthread_mu

33、tex_lock会使线程等待，直到没有其他线程进入临界区；n调用pthread_mutex_unlock则通知系统该线程已经完成了临界区中代码的执行。用互斥量计算全局和n通过声明一个全局的互斥量，可以在求全局和的程序中用互斥量代替忙等待。n主线程对互斥量进行初始化，然后，用互斥量替换忙等待和增量标志，在线程进入临界区前调用pthread_mutex_lock，在执行完临界区中的所有操作后再调用pthread_mutex_unlock。用互斥量计算全局和(1)用互斥量计算全局和(2)第一个调用pthread_mutex_lock的线程会为临界区“锁门”，其他线程如果也想要进入临界区，也需要先调用

34、pthread_mutex_lock，这些调用了pthread_mutex_lock的线程都会阻塞并等待，直到第一个线程离开临界区。所以只有当第一个线程调用了pthread_mutex_unlock后，系统才会从那些阻塞的线程中选取一个线程使其进入临界区。这个过程反复执行，直到所有的线程都完成临界区的操作。进入临界区的顺序n注意，在使用互斥量的多线程程序中，多个线程进入临界区的顺序是随机的n第一个调用pthread_mutex_lock的线程率先进入临界区，接下去的线程顺序则由系统负责分配。nPthreads无法保证线程按其调用pthread_mutex_lock的顺序获得进入临界区的锁。性能

35、比较计算的程序，使用n=108个项目，在一个有两个4核处理器的系统上的运行时间（秒）关于忙等待采用忙等待，并且线程个数多于核的个数时，可能的线程执行顺序关于忙等待n假设有2个核和5个线程，再假设线程0在执行临界区，线程1处于忙等待状态，线程2、线程3、线程4被操作系统挂起。n当线程0完成临界区的操作将flag设为1时，线程1进入临区，操作系统可以调度线程2、线程3、线程4中的一个。n假设操作系统调度到线程3，它在while语句上循环等待。n当线程1也完成了临界区操作，将flag设为2，操作系统就可以调度线程2或线程4。n如果它选择了线程4，则线程3和线程4都会在忙等待中循环，直到操作系统将它们

36、中的一个挂起，并调度线程2。练习n利用忙等待或者互斥量来编写求值的Pthreads程序生产者-消费者同步和信号量Producer-Consumer Synchronization and Semaphores问题n忙等待能事先确定线程执行临界区代码的顺序n如果采用互斥量，那么哪个线程先进入临界区以及此后的顺序由系统随机选取。n有一些应用，需要控制线程进入临界区的顺序。使用互斥量的程序存在的问题发送消息的例子n 在更复杂的例子中，每个线程都会向其他线程“发送消息”。n例如，假设我们有thread_count或t个线程，线程0向线程1发送消息，线程1向线程2发消息，线程t-2向线程t-1发消息，线

37、程t-1向线程0发送消息。n当一个线程“接收”一条消息后，它打印消息并终止。发送消息的例子n为了实现消息的传递，分配了一个char*类型的共享数组，每个线程初始化消息后，就设定这个共享数组中的指针指向要发送的消息。n为了避免引用到没有被定义的指针，主线程将共享数组中的每项都先设为NULL，具体参见程序4-7。使用Pthreads发送信息的第一种尝试消息发送结果n当在双核系统上运行多于两个线程的程序时，我们发现消息始终收到。n例如，在线程t-1把消息复制到message数组前，最先运行的线程0早已结束。n这一点也不令人惊奇，如果把第12行的if语句替换成忙等待的while语句，问题就可以得到解决

38、：可以用互斥量吗？现在，假设有两个线程，线程0运行得远比线程1快，所以当它运行到第7行的pthread _mutex_lock时，线程1才刚刚运行到第2行。线程0获得锁，并继续执行printf语句，这会导致线程0引用空指针（此时，线程0的messagesmy_rank还是NULL。），然后使得整个程序崩溃。信号量nPthreads提供另一个控制访问临界区的方法：信号量( semaphore)n信号量可以认为是一种特殊类型的unsigned int无符号整型变量，可以赋值为0、1、2、。n大多数情况下，只给它们赋值0和1，这种只有0和1值的信号量称为二元信号量。n粗略地讲，0对应于上了锁的互斥量

39、，1对应于未上锁的互斥量。信号量n要把一个二元信号量用做互斥量时，需要先把信号最的值初始化为1，即开锁状态。n在要保护的临界区前调用函数sem_wait，线程执行到sem_wait函数时，如果信号量为0，线程就会被阻塞。如果信号量是非0值，就减1后进入临界区。n执行完临界区内的操作后，再调用sem_post对信号量的值加1，使得在sem_wait中阻塞的其他线程能够继续运行。信号量n信号量与互斥量最大的区别在于信号量是没有个体拥有权的，主线程将所有的信号量初始化为0，即“加锁”，其他线程都能对任何信号量调用sem_post和sem_wait函数。使用信号量让线程发送消息不同信号量函数的语法Se

40、maphores are not part of Pthreads;you need to add this.我们不使用sem_init函数的第二个参数，对这个参数只需传入常数0即可。生产者-消费者同步n最后，需要指出的是：程序4-8中的消息传递不涉及临界区。n问题已经不再是一段代码一次只能被一个线程执行，而变成了线程my_rank在线程source发出消息前一直被阻塞。n这种一个线程需要等待另一个线程执行某种操作的同步方式，有时称为生产者-消费者同步模型。 练习n用信号量编写发送消息的Pthreads程序路障和条件变量路障和条件变量BARRIERS AND CONDITION VARIABL

41、ES路障n通过保证所有线程在程序中处于同一个位置来同步线程。这个同步点又称为路障。n只有所有线程都抵达此路障，线程才能继续运行下去，否则会阻塞在路障处。路障应用1n路障有很多应用。n比如第2章讨论的计时多线程程序，希望所有线程能够在同一时间点开始计时，在最后一个线程完成（“最慢”的线程）时再报告时间。使用路障计算“最慢”线程的时间路障应用2n路障另一个非常重要的应用是调试程序。n正如你可能已经看到的，当并行程序发生错误时，很难确定具体是哪个位置出现错误。当然，可以让每个线程都打印消息，来表明它运行到程序的哪个点，但当打印的消息越来越多后，这方法就不管用了。使用路障来调试程序路障的实现n许多Pt

42、hreads的实现不提供路障，为了使得程序具有可移植性，我们需要自己实现路障。n有很多方法来实现路障，我们将具体讨论其中的三种方法。其中的两种方法已经在之前做过介绍，第三种方法使用了新的Pthreads对象：条件变量(conditional varialble)。忙等待和互斥量n用忙等待和互斥量来实现路障比较直观n我们使用一个由互斥量保护的共享计算器n当计算器的值表明每个线程都以及进入临界区，所有线程就可以离开忙等待的状态了忙等待和互斥量We need one counter variable for each instance of the barrier,otherwise problem

43、sare likely to occur.用忙等待和互斥量来实现路障存在的问题n问题一：n这种实现会有与其他使用忙等待程序一样的问题：线程处于忙等待循环时浪费了很多CPU周期，并且当程序中的线程数多过于核数时，程序的性能会直线下降。用忙等待和互斥量来实现路障存在的问题n问题二：共享变量counter。n如果我们想要实现第2个路障并重新使用counter这个变量作为计数器，那么会发生什么状况呢？n当第一个路障完成时，counter的值为thread_count。除非重置counter的值，否则第一个路障的循环条件counterthread_count一直处于false状态，路障也就无法阻塞线程了

44、。用忙等待和互斥量来实现路障存在的问题n问题二：共享变量counter。n此外，试图将counter值重置为0几乎注定会失败。n如果最后一个线程进入循环并重置counter值，那么其他一些处于忙等待的线程将永远看不到counter=thread_count的条件成立，并永远处于忙等待中。n如果线程在经过路障后重置counter值，另一些线程可能在重置前就已经进入了第二个路障，由这些线程引起的counter增加值就会因重置而丢失，这会导致所有线程都被困在第二个路障的忙等待中。n所以，如果想要使用这种实现方式的路障，则有多少个路障就必须要有多少个不同的共享counter变量来进行计数。使用信号量实

45、现路障我们采用两个信号量：count_sem，用于保护计数器；barrier_sem，用于阻塞已经进入路障的线程。counter_sem信号量初始化为1（开锁状态），第一个到达路障的线程调用sem_wait函数，则随后的线程会被阻塞直到获取访问计数器的权限。当一个线程被允许访问计数器时，它检查counternextn后，对curr_p的引用可能会导致段违规。多个线程同时访问链表的问题n通常，可以把问题归绪为：在执行Insert或Delete的同时执行其他操作。多线程同时执行Member操作，即读链表结点是没有问题的；但当多个线程同时访问链表且至少有一个线程正在执行Insert或Delete操作

46、，即写链表结点时，是不安全的。解决方案#1n在对链表进行访问之前先加锁是一个显而易见的方案n每次调用这三个函数时需要用互斥量来保护In place of calling Member(value).存在问题n必须串行访问链表n如果对链表大部分的访问操作都是Member，那么就失去了开发并行性的机会n另一方面，如果对链表大部分的访问操作是Insert和Delete，这可能是最后的解决方案，因为大部分的操作都需要串行执行，而这个解决方案很容易实现。解决方案#2n我们可以对链表上的单个结点上锁，而不是对整个链表上锁n“细粒度锁”方法：存在问题nMember函数的实现比原来的更复杂n它比原来的实现慢，

47、因为每次访问一个结点时，都必须对结点加锁和解锁。n每个结点都增加了一个互斥量域，这必然增加了整个链表对存储量的需求。用每个链表结点拥有一个互斥量的方法来实现Member函数(1)用每个链表结点拥有一个互斥量的方法来实现Member函数(2)练习n用每个链表结点拥有一个互斥量的方法来实现Insert和Delete函数Pthreads读写锁n前面两种方法都不让正在执行Member函数的线程还可以同时访问链表的任意结点。n第一个方法在任一时刻只允许一个线程访问整个链表n第二个方法在任一时刻只允许一个线程访问任一给定结点。Pthreads读写锁nPthreads的读写锁可以作为另一种可选方案。除了提供

48、两个锁函数以外，读写锁基本上与互斥量差不多。n这两个函数，第一个为读操作对读读写锁进行加锁，第二个为写操作对读读写锁进行加锁Pthreads读写锁n多个线程能通过调用读锁函数而同时获得锁，但只有一个线程能通过写锁函数而获得锁。n因此，如果任何线程拥有了读锁，则任何请求写锁的线程将阻塞在写锁函数的调用上。Pthreads读写锁n如果任何线程拥有了写锁，则任何想获取读或写锁的线程将阻塞在它们对应的锁函数上保护链表函数读写锁函数的语法n这个新的Pthreads函数的语法是n与互斥量一样，读写锁在使用前应该初始化，在使用后应该销毁。那个实现最好？n我们想知道这三个实现哪个是“最好”的，因此我们编写了一

49、个小程序，其中包括这三种实现。n在程序中，主线程首先向空链表中插入用户指定数量的随机生成的键值。被主线程启动后：每个线程对链表执行用户指定数量的操作。用户还要指定每类操作( Member、Insert、Delete)所占的百分比。然而，哪个操作发生以及对哪个键值进行操作取决于一个随机数生成器。n例如，用户可能会指定：插入1000个键值到初始的空链表中，线程总共执行1 00 000个操作。而且，她可能还会指定80%的操作是Member，15%是Insert，剩下的5%足Delete。链表性能100,000 ops/thread99.9% Member0.05% Insert0.05% Delet

50、en在两个表中，当线程数为1时，读写锁与单互斥量实现的执行时间是一样的。这很好理解：因为没有对读写锁和互斥量的竞争，这些操作是串行执行的，这两种实现的开销都包含对链表进行操作前的函数调用和操作后的函数调用。n另一方面，使用每个结点一个锁的实现比较慢。这也是好理解的，因为每次单个结点被访问，将会有2个操作（一次加锁、一次解锁），因此开销更大。链表性能100,000 ops/thread80% Member10% Insert10% Deleten在多个线程的情况下，每个结点一个互斥量的实现仍然维持其低效性。与其他两个实现相比，过多的加锁和解锁使这个实现开销太大。n当Insert和Delete操作