共计 13029 个字符，预计需要花费 33 分钟才能阅读完成。
OpenMP 线程同步 Construct 实现原理以及源码剖析（下）
前言
在下面文章当中咱们次要剖析了 flush, critical, master 这三个 construct 的实现原理。在本篇文章当中咱们将次要剖析另外两个 construct : barrier 和 single。
Barrier Construct
编译器角度剖析
在本大节当中咱们次要介绍 #pragma omp barrier 的应用，事实上这个 construct 在编译器的解决上非常简单，只是将这条编译领导语句变成了一个函数调用。
void GOMP_barrier (void) 每一条 #pragma omp barrier 都会变成调用函数 GOMP_barrier。咱们来看一个示例程序：
#include <stdio.h>
#include <omp.h>
int main()
{#pragma omp parallel num_threads(4) default(none)
{printf("tid = %d start\n", omp_get_thread_num());
#pragma omp barrier
printf("tid = %d end\n", omp_get_thread_num());
}
return 0;
}在后面的文章当中咱们曾经提到了编译器会将一个 parallel construct 编译成一个函数，下面的 parallel construct 被编译的之后的后果如下所示，能够看到的确编译成了调用函数 GOMP_barrier。
000000000040118a <main._omp_fn.0>:
40118a: 55 push %rbp
40118b: 48 89 e5 mov %rsp,%rbp
40118e: 48 83 ec 10 sub $0x10,%rsp
401192: 48 89 7d f8 mov %rdi,-0x8(%rbp)
401196: e8 a5 fe ff ff callq 401040 <omp_get_thread_num@plt>
40119b: 89 c6 mov %eax,%esi
40119d: bf 10 20 40 00 mov $0x402010,%edi
4011a2: b8 00 00 00 00 mov $0x0,%eax
4011a7: e8 a4 fe ff ff callq 401050 <printf@plt>
4011ac: e8 7f fe ff ff callq 401030 <GOMP_barrier@plt>
4011b1: e8 8a fe ff ff callq 401040 <omp_get_thread_num@plt>
4011b6: 89 c6 mov %eax,%esi
4011b8: bf 20 20 40 00 mov $0x402020,%edi
4011bd: b8 00 00 00 00 mov $0x0,%eax
4011c2: e8 89 fe ff ff callq 401050 <printf@plt>
4011c7: c9 leaveq
4011c8: c3 retq
4011c9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)源码剖析
void
GOMP_barrier (void)
{
// 失去以后线程的相干数据
struct gomp_thread *thr = gomp_thread ();
// 失去以后线程的线程组
struct gomp_team *team = thr->ts.team;
/* It is legal to have orphaned barriers. */
if (team == NULL)
return;
// 应用线程组外部的 barrier 只有所有的线程都达到这个同步点之后才可能持续往后执行
// 否则就须要进入内核挂起
gomp_team_barrier_wait (&team->barrier);
}下面的代码就是应用以后线程线程组外部的 barrier，让线程组当中的所有线程都达到同步点之后才持续往后执行，如果你应用过 pthread 中的线程同步工具路障 pthread_barrier_t 的话就很容易了解了。
在持续往后分析程序之前咱们首先须要理解两个数据类型：
typedef struct
{
/* Make sure total/generation is in a mostly read cacheline, while
awaited in a separate cacheline. */
unsigned total __attribute__((aligned (64)));
unsigned generation;
unsigned awaited __attribute__((aligned (64)));
} gomp_barrier_t;
typedef unsigned int gomp_barrier_state_t;咱们重点剖析一下 gomp_barrier_t，team->barrier 就是这个变量类型，在这个构造体当中一共有三个变量咱们重点剖析第一个和第三个变量的含意：
- total，这个变量示意一个须要期待多少个线程达到同步点之后才可能持续往后执行。
- awaited，这个变量示意还须要期待多少个线程。
- 初始化的时候 total 和 awaited 这两个变量是相等的，当有一个线程达到之后 awaited 就减去 1。
- generation 这个变量与 OpenMP 当中的 task 无关，这个变量略微有点简单，因为咱们的剖析不波及到 OpenMP 当中的工作，因而这类对这个变量不做剖析，这个变量的初始值等于 0。
构造体 gomp_barrier_t 初始化函数如下所示：
static inline void gomp_barrier_init (gomp_barrier_t *bar, unsigned count)
{
bar->total = count;
bar->awaited = count;
bar->generation = 0;
}当初咱们来对函数 gomp_team_barrier_wait 进行剖析，对于代码的具体都在代码的对应地位：
void
gomp_team_barrier_wait (gomp_barrier_t *bar)
{gomp_team_barrier_wait_end (bar, gomp_barrier_wait_start (bar));
}
static inline gomp_barrier_state_t
gomp_barrier_wait_start (gomp_barrier_t *bar)
{
// 因为咱们不剖析 OpenMP 当中的 task , 因而在这里可能认为 generation 始终等于 0
// 那么 ret 也等于 0
unsigned int ret = __atomic_load_n (&bar->generation, MEMMODEL_ACQUIRE) & ~3;
/* A memory barrier is needed before exiting from the various forms
of gomp_barrier_wait, to satisfy OpenMP API version 3.1 section
2.8.6 flush Construct, which says there is an implicit flush during
a barrier region. This is a convenient place to add the barrier,
so we use MEMMODEL_ACQ_REL here rather than MEMMODEL_ACQUIRE. */
// 这里将 awaited 还须要期待的线程数 -1 并且判断 awaited 是否等于 0
// 如果等于 0 则返回 1 反之则返回 0 如果不思考 task 只有最初一个达到同步点的线程
// 才会返回 1
ret += __atomic_add_fetch (&bar->awaited, -1, MEMMODEL_ACQ_REL) == 0;
return ret;
}
// 为了不便浏览上面的代码曾经删除了与 task 相干的局部
void
gomp_team_barrier_wait_end (gomp_barrier_t *bar, gomp_barrier_state_t state)
{
unsigned int generation, gen;
// 如果 state 等于 1 将会进入上面的 if 语句
if (__builtin_expect ((state & 1) != 0, 0))
{
// 如果是最初一个线程达到这里，那么将会从新将 awaited 变成 total
/* Next time we'll be awaiting TOTAL threads again. */
struct gomp_thread *thr = gomp_thread ();
struct gomp_team *team = thr->ts.team;
bar->awaited = bar->total;
// 如果还有须要执行的工作 那么将进入 if 语句
if (__builtin_expect (team->task_count, 0))
{gomp_barrier_handle_tasks (state);
state &= ~1;
}
else
{
// 如果没有须要执行的工作 那么则须要将之前被挂起的线程全副唤醒
__atomic_store_n (&bar->generation, state + 3, MEMMODEL_RELEASE);
futex_wake ((int *) &bar->generation, INT_MAX);
return;
}
}
// 如果 if 条件不满足，也就是说达到 barrier 的线程不是最初一个线程
// 那么将会执行到这里进行挂起
// 这里省略了代码 如果程序执行到这里将会被持续挂起 直到下面的 futex_wake 被执行
}
技巧剖析
- 在下面的构造体 gomp_barrier_t 当中有语句
unsigned total __attribute__((aligned (64)));前面的 __attribute__((aligned (64))) 示意这个字段须要应用 64 字节对齐，那么这个字段也占 64 字节，一般来说一个缓存行有 64 个字节的数据，也就是说这三个字段的数据不会存储在同一个缓存行，这样的话多个线程在操作这三个数据的时候不会产生假共享 (false sharing) 的问题，这能够很进步程序的效率。 - 咱们在后面探讨 critical construct 的时候谈到啦 critical 有匿名和命令两种形式：
#pragma omp critical
#pragma omp critical(name) 那么按情理来说 barrier 也应该有两种形式啊，那么为什么会没有呢？依据后面的程序剖析，咱们能够晓得，最重要的一行代码是 gomp_team_barrier_wait (&team->barrier); 因为每一个线程都属于一个线程组，每个线程组外部都有一个 barrier，因而当进行同步的时候只须要应用线程组外部的 barrier 即可，因而不须要应用命名的 barrier。
Single Construct
pragma omp single
在本大节当中咱们次要剖析 single construct，他的一半模式如下所示：
#pragma omp single
{body;}相似于下面的构造的代码会被编译器编译成如下模式：
if (GOMP_single_start ())
body;
GOMP_barrier ();对于 GOMP_barrier 函数咱们在后面的内容当中曾经进行了具体的剖析，他的性能就是应用一个线程组外部的 barrier 变量，当所有的线程都达到这个地位之后才放行所有线程，让他们继续执行，如果线程组的线程没有全副达到同步点，则达到同步点的线程会被挂起。
咱们应用一个理论的例子进行剖析，看一下最终被编译成的程序是什么样子：
#include <stdio.h>
#include <omp.h>
int main()
{#pragma omp parallel num_threads(4) default(none)
{
#pragma omp single
{printf("Hello World\n");
}
printf("tid = %d\n", omp_get_thread_num());
}
return 0;
}下面的 parallel 代码块被编译之后的反汇编程序如下所示：
00000000004011aa <main._omp_fn.0>:
4011aa: 55 push %rbp
4011ab: 48 89 e5 mov %rsp,%rbp
4011ae: 48 83 ec 10 sub $0x10,%rsp
4011b2: 48 89 7d f8 mov %rdi,-0x8(%rbp)
4011b6: e8 c5 fe ff ff callq 401080 <GOMP_single_start@plt>
4011bb: 3c 01 cmp $0x1,%al
4011bd: 74 1d je 4011dc <main._omp_fn.0+0x32>
4011bf: e8 7c fe ff ff callq 401040 <GOMP_barrier@plt>
4011c4: e8 87 fe ff ff callq 401050 <omp_get_thread_num@plt>
4011c9: 89 c6 mov %eax,%esi
4011cb: bf 10 20 40 00 mov $0x402010,%edi
4011d0: b8 00 00 00 00 mov $0x0,%eax
4011d5: e8 86 fe ff ff callq 401060 <printf@plt>
4011da: eb 0c jmp 4011e8 <main._omp_fn.0+0x3e>
4011dc: bf 1a 20 40 00 mov $0x40201a,%edi
4011e1: e8 4a fe ff ff callq 401030 <puts@plt>
4011e6: eb d7 jmp 4011bf <main._omp_fn.0+0x15>
4011e8: c9 leaveq
4011e9: c3 retq
4011ea: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)从下面的汇编程序咱们能够看到，被编译的程序的确调用了函数 GOMP_single_start，如果这个函数的返回值不等于 true 的时候就会执行函数 GOMP_barrier。这和咱们下面的剖析是一样的。
当初最次要的函数就是 GOMP_single_start，他的源代码如下所示：
bool
GOMP_single_start (void)
{struct gomp_thread *thr = gomp_thread ();
struct gomp_team *team = thr->ts.team;
unsigned long single_count;
if (__builtin_expect (team == NULL, 0))
return true;
// 首先取得线程本地保留的遇到的 single construct 数量
// 并且将这个数量进行加一操作 因为又遇到了一次
single_count = thr->ts.single_count++;
// 如果上面的操作还没有实现 线程组中保留的 single_count 和 线程
// 本地的 single_count 是相等的，因而才能够进行上面的比拟并替换
// 操作，当有一个线程胜利之后 前面的线程执行上面的语句都会返回 false
return __sync_bool_compare_and_swap (&team->single_count, single_count,
single_count + 1L);
}下面函数只有一个线程会执行返回 true，其余的线程执行都会返回 false，因而能够保障只有一个线程执行，single construct 代码块，下面的执行的次要原理就是依赖比拟并替换指令 (compare and swap , CAS) 指令实现的。
在剖析下面的代码的时候须要留神 team->single_count 和 thr->ts.single_count，这是两个不同的数据。__sync_bool_compare_and_swap 是编译器内置的一个函数，这个函数的次要作用是将 &team->single_count 指向的数据和 single_count 进行比拟，如果这两个数据相等则进行替换操作，如果操作胜利就返回 true，否则就返回 false。
pragma omp single copyprivate(…)
在这一大节当中咱们将介绍一个比拟少用的子句 copyprivate，并且剖析 single construct 在解决这个子句的时候是如何进行解决的。
咱们首先来理解一下这个子句改如何应用，这个是用于在 single construct 当中，当一个变量在每个线程当中都有一个正本的时候，在执行实现 single construct 之后只有一个线程的数据会被批改，如果想让所有线程晓得这个批改，那么就须要应用 copyprivate，比方上面的例子：
#include <stdio.h>
#include <omp.h>
int x = 100;
int y = -100;
#pragma omp threadprivate(x, y)
int main()
{#pragma omp parallel num_threads(4) default(none) copyin(x)
{x = omp_get_thread_num();
printf("tid = %d x = %d\n", omp_get_thread_num(), x);
#pragma omp single copyprivate(x, y)
{
x = 200;
y = -200;
}
printf("tid = %d x = %d y = %d\n", omp_get_thread_num(), x, y);
}
return 0;
} 在下面的程序当中 x 是一个全局变量，#pragma omp threadprivate(x) 会让每个线程都会有一个全局变量 x 的线程本地的正本，copyin(x) 是将全局变量 x 的值拷贝到每个线程本地的变量正本当中。咱们晓得只会有一个线程执行 single construct，那么只会有执行 single 代码的线程当中的 x 会变成 200，然而因为有 copyprivate，在线程执行完 single 代码块之后会将批改之后的 x 值赋给其余的线程，这样的话其余线程的 x 的值也变成 200 啦。下面的代码执行后果如下：
tid = 2 x = 2
tid = 3 x = 3
tid = 0 x = 0
tid = 1 x = 1
tid = 3 x = 200 y = -200
tid = 0 x = 200 y = -200
tid = 2 x = 200 y = -200
tid = 1 x = 200 y = -200如果咱们写的代码如下所示：
#pragma omp single copyprivate(x, y)
body;下面的代码会被编译器翻译成上面的样子：
datap = GOMP_single_copy_start ();
if (datap == NULL)
{
body;
data = allocate memory;
data.x = x;
data.y = y;
GOMP_single_copy_end (&data);
}
else
{
x = datap->x;
y = datap->y;
}
GOMP_barrier ();首先咱们来理解一下 GOMP_single_copy_start 的返回值：
- 如果这个线程的返回值是 NULL，那么就阐明这个线程会执行 single construct 中的代码，反之线程就不会执行 single 中的代码。
- 如果线程没有取得 single 代码块的执行权的话，那么这个线程将会被阻塞在函数 GOMP_single_copy_start 当中，只有 single 中的代码被执行实现之后线程才会被唤醒，具体来说是执行 single 代码块的线程进入到 GOMP_single_copy_end 中之后才会唤醒其余的线程，之所以这么做的起因是首先要失去最终的 x 的值，而后将这个值通过线程组之间的共享变量让没有执行 single 代码块的线程可能取得执行 single 代码块的线程当中的 x 的值，因为在没有执行实现 single 代码块之后是不可能晓得 x 的最终的值的，而不晓得 x 的最终的值，是不可能执行
x = datap->x;的，因而须要将线程阻塞在 GOMP_single_copy_start 当中。 - 如果线程的返回值不等于 NULL，那么就阐明这个线程没有获取到 single 代码块的执行权，这个返回值 datap 是指向 threadprivate 数据的指针，比方下面的例子就是指向 x 的指针，因为能够做到申请 x, y 内存空间的时候是间断的，晓得 x 的指针和 x 的大小就能够计算出线程公有变量 y 的地址，这是编译器能够做到的。
下面的两个动静库函数的源代码如下所示（具体的阐明曾经在正文当中）：
/* This routine is called when first encountering a SINGLE construct that
does have a COPYPRIVATE clause. Returns NULL if this is the thread
that should execute the clause; otherwise the return value is pointer
given to GOMP_single_copy_end by the thread that did execute the clause. */
void *
GOMP_single_copy_start (void)
{struct gomp_thread *thr = gomp_thread ();
bool first;
void *ret;
// 这个函数能够返回 true 或者 false 如果线程须要执行 single 代码块
// 则返回 true, 否则返回 false
first = gomp_work_share_start (0);
if (first)
{gomp_work_share_init_done ();
ret = NULL;
}
else
{
// 咱们在后面提到了 没有执行 single 代码块的线程会被阻塞在这个函数当中
// 理论就是在这个地位进行阻塞的，以保障 copyprivate 当中的变量的值曾经被更新啦
gomp_team_barrier_wait (&thr->ts.team->barrier);
// 这里就是没执行 single 代码块的线程的函数返回值
// 执行 single 代码块的线程会将 x, y 拷贝一份并且将指向 x, y 内存地址的
// 指针赋值给变量 thr->ts.work_share->copyprivate;（在函数 GOMP_single_copy_end 当中能够看到具体的代码）ret = thr->ts.work_share->copyprivate;
gomp_work_share_end_nowait ();}
return ret;
}
/* This routine is called when the thread that entered a SINGLE construct
with a COPYPRIVATE clause gets to the end of the construct. */
void
GOMP_single_copy_end (void *data)
{struct gomp_thread *thr = gomp_thread ();
struct gomp_team *team = thr->ts.team;
if (team != NULL)
{
// 这个函数只有执行了 single 代码块的线程才会执行
// 咱们在后面曾经提到了传给这个函数的参数是指向 x, y
// 内存地址的指针，当初将这个指针赋值给 thr->ts.work_share->copyprivate
// 那么其余的线程就可能通过 thr->ts.work_share->copyprivate 获取到 x, y
// 的值啦
thr->ts.work_share->copyprivate = data;
// 因为后面线程都被阻塞了 须要期待所有的线程都达到之后才可能持续往后执行
// 因而这个线程须要进入 barrier，当所有的线程都达到之后那么就可能持续往后执行了
gomp_team_barrier_wait (&team->barrier);
}
gomp_work_share_end_nowait ();}下面的整个流程如下图所示：
咱们在来看一下后面提到的应用 single copyprivate(x, y) 的程序
#pragma omp parallel num_threads(4) default(none) copyin(x)
{x = omp_get_thread_num();
printf("tid = %d x = %d\n", omp_get_thread_num(), x);
#pragma omp single copyprivate(x, y)
{
x = 200;
y = -200;
}
printf("tid = %d x = %d y = %d\n", omp_get_thread_num(), x, y);
}编译之后的汇编程序是怎么样的（重要的局部已在代码当中进行标出）：
00000000004011bb <main._omp_fn.0>:
4011bb: 55 push %rbp
4011bc: 48 89 e5 mov %rsp,%rbp
4011bf: 41 54 push %r12
4011c1: 53 push %rbx
4011c2: 48 83 ec 20 sub $0x20,%rsp
4011c6: 48 89 7d d8 mov %rdi,-0x28(%rbp)
4011ca: e8 81 fe ff ff callq 401050 <omp_get_thread_num@plt>
4011cf: 85 c0 test %eax,%eax
4011d1: 0f 85 c2 00 00 00 jne 401299 <main._omp_fn.0+0xde>
4011d7: e8 74 fe ff ff callq 401050 <omp_get_thread_num@plt>
4011dc: 64 89 04 25 f8 ff ff mov %eax,%fs:0xfffffffffffffff8
4011e3: ff
4011e4: 64 8b 1c 25 f8 ff ff mov %fs:0xfffffffffffffff8,%ebx
4011eb: ff
4011ec: e8 5f fe ff ff callq 401050 <omp_get_thread_num@plt>
4011f1: 89 da mov %ebx,%edx
4011f3: 89 c6 mov %eax,%esi
4011f5: bf 10 20 40 00 mov $0x402010,%edi
4011fa: b8 00 00 00 00 mov $0x0,%eax
4011ff: e8 5c fe ff ff callq 401060 <printf@plt>
401204: e8 87 fe ff ff callq 401090 <GOMP_single_copy_start@plt>
401209: 48 85 c0 test %rax,%rax
40120c: 74 4c je 40125a <main._omp_fn.0+0x9f>
40120e: eb 33 jmp 401243 <main._omp_fn.0+0x88>
401210: e8 1b fe ff ff callq 401030 <GOMP_barrier@plt>
401215: 64 44 8b 24 25 fc ff mov %fs:0xfffffffffffffffc,%r12d
40121c: ff ff
40121e: 64 8b 1c 25 f8 ff ff mov %fs:0xfffffffffffffff8,%ebx
401225: ff
401226: e8 25 fe ff ff callq 401050 <omp_get_thread_num@plt>
40122b: 44 89 e1 mov %r12d,%ecx
40122e: 89 da mov %ebx,%edx
401230: 89 c6 mov %eax,%esi
401232: bf 21 20 40 00 mov $0x402021,%edi
401237: b8 00 00 00 00 mov $0x0,%eax
40123c: e8 1f fe ff ff callq 401060 <printf@plt>
401241: eb 69 jmp 4012ac <main._omp_fn.0+0xf1>
# //////////// 没有取得 single construct 执行权的线程将执行上面的代码 ///////////
# 上面的 5 条汇编指令其实就是将 x, y 的数据拷贝到线程的公有数据 thread local storage
401243: 8b 50 04 mov 0x4(%rax),%edx #
401246: 64 89 14 25 fc ff ff mov %edx,%fs:0xfffffffffffffffc
40124d: ff
40124e: 8b 00 mov (%rax),%eax
401250: 64 89 04 25 f8 ff ff mov %eax,%fs:0xfffffffffffffff8
401257: ff
# ////////////////////////////////////////////////////////////////////////
401258: eb b6 jmp 401210 <main._omp_fn.0+0x55>
# //////////// 取得 single construct 执行权的线程将执行上面的代码 //////////////
# 上面的代码就是 x = 200
40125a: 64 c7 04 25 f8 ff ff movl $0xc8,%fs:0xfffffffffffffff8
401261: ff c8 00 00 00
# 上面的代码就是 y = -200
401266: 64 c7 04 25 fc ff ff movl $0xffffff38,%fs:0xfffffffffffffffc
40126d: ff 38 ff ff ff
# 上面的代码就是将 y 的值保留到 eax 寄存器
401272: 64 8b 04 25 fc ff ff mov %fs:0xfffffffffffffffc,%eax
401279: ff
# 将 eax 寄存器的值保留到栈上
40127a: 89 45 ec mov %eax,-0x14(%rbp)
# 将 x 的值保留到 eax 寄存器
40127d: 64 8b 04 25 f8 ff ff mov %fs:0xfffffffffffffff8,%eax
401284: ff
# 将 eax 寄存器的值保留到栈上
401285: 89 45 e8 mov %eax,-0x18(%rbp)
# 下面的几行代码就实现了线程公有数据的拷贝 上面的代码就是将栈上保留 x, y 的内存地址通过参数传递给函数 GOMP_single_copy_end 这样就能够保留在 thr->ts.work_share->copyprivate 上啦
401288: 48 8d 45 e8 lea -0x18(%rbp),%rax
40128c: 48 89 c7 mov %rax,%rdi
40128f: e8 ac fd ff ff callq 401040 <GOMP_single_copy_end@plt>
# ////////////////////////////////////////////////////////////////////////
401294: e9 77 ff ff ff jmpq 401210 <main._omp_fn.0+0x55>
401299: 48 8b 45 d8 mov -0x28(%rbp),%rax
40129d: 8b 00 mov (%rax),%eax
40129f: 64 89 04 25 f8 ff ff mov %eax,%fs:0xfffffffffffffff8
4012a6: ff
4012a7: e9 2b ff ff ff jmpq 4011d7 <main._omp_fn.0+0x1c>
4012ac: 48 83 c4 20 add $0x20,%rsp
4012b0: 5b pop %rbx
4012b1: 41 5c pop %r12
4012b3: 5d pop %rbp
4012b4: c3 retq
4012b5: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
4012bc: 00 00 00
4012bf: 90 nop总结
在本篇文章当中次要给大家深入分析了 barrier construct 的实现原理，以及 single construct 的两种应用形式并且深入分析了 copy private 的实现原理，具体的线程公有数据是如果通过 OpenMP 库函数进行传递的，整个过程还是有些简单的，须要认真的对整个流程进行思考才可能了解。以上就是本篇文章的所有内容心愿大家有所播种！
更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…
关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。
正文完
