问题描述
利用LLVM （C、C++）或者Soot （Java）等工具检测多线程程序中潜在的数据竞争，并对比加上锁以后检测结果的变化，分析及给出案例程序并提交分析报告。
基本思路：
- 编写具有数据竞争的多线程程序（C或者Java）；
- 利用LLVM或者Soot将C或者Java程序编译成字节码；
- 利用LLVM或者soot提供的数据竞争检测工具检测；
- 对有数据竞争的地方加锁，观察检测结果；
解决方法
步骤一 编写具有数据竞争的多线程程序
由于只需要一个简单的具有数据竞争的代码，于是我翻出了以前写过了一个数组求和的代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
int thread_count = 8;
int n = 100000;
int *a, sum = 0;
void* calc_sum(void* rank){
long my_rank = (long) rank;
int i, j;
int local_n = n / thread_count;
int my_first_n = my_rank * local_n;
int my_last_n = (my_rank + 1) * local_n - 1;
for (i = my_first_n; i <= my_last_n; i++)
sum += a[i];
return NULL;
}
int main() {
pthread_t* thread_handles;
thread_handles = (pthread_t*)malloc(thread_count * sizeof(pthread_t));
srand(time(0));
a = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
a[i] = rand() % 100;
for (long i = 0; i < thread_count; i++) {
pthread_create(&thread_handles[i], NULL, calc_sum, (void*)i);
}
printf("Hello from the main thread\n");
for (int i=0; i < thread_count; i++)
pthread_join(thread_handles[i], NULL);
int ans = 0;
for (int i = 0; i < n; i++)
ans += a[i];
printf("The total sum is %d\n", sum);
printf("The right answer is %d\n", ans);
free(thread_handles);
return 0;
}
很显然，calc_sum中的sum会产生数据竞争，多个线程会同时访问sum。
步骤二 利用LLVM将Cpp程序编译成字节码
g++中有内嵌的LLVM工具，加上编译参数-fsanitize=thread即可检测数据竞争。
g++ -lpthread -g -o datarace datarace.cpp -fsanitize=thread
步骤三 利用LLVM提供的数据竞争检测工具检测
birdie@birdie-ThinkPad-E575:~/桌面/parallel/hw3$ ./datarace
==================
WARNING: ThreadSanitizer: data race (pid=2611)
Read of size 4 at 0x55cc5ced4030 by thread T2:
#0 calc_sum(void*) /home/birdie/桌面/parallel/hw3/datarace.cpp:18 (datarace+0x1403)
Previous write of size 4 at 0x55cc5ced4030 by thread T1:
#0 calc_sum(void*) /home/birdie/桌面/parallel/hw3/datarace.cpp:18 (datarace+0x1417)
Location is global 'sum' of size 4 at 0x55cc5ced4030 (datarace+0x000000004030)
Thread T2 (tid=2614, running) created by main thread at:
#0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
#1 main /home/birdie/桌面/parallel/hw3/datarace.cpp:32 (datarace+0x158b)
Thread T1 (tid=2613, finished) created by main thread at:
#0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
#1 main /home/birdie/桌面/parallel/hw3/datarace.cpp:32 (datarace+0x158b)
SUMMARY: ThreadSanitizer: data race /home/birdie/桌面/parallel/hw3/datarace.cpp:18 in calc_sum(void*)
==================
Hello from the main thread
The total sum is 1747941
The right answer is 4930329
ThreadSanitizer: reported 1 warnings
步骤四 对有数据竞争的地方加锁，观察检测结果
对calc_sum中的sum加锁。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
#include <unistd.h>
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int thread_count = 8;
int n = 100000;
int *a, sum = 0;
void* calc_sum(void* rank){
long my_rank = (long) rank;
int i, j;
int local_n = n / thread_count;
int my_first_n = my_rank * local_n;
int my_last_n = (my_rank + 1) * local_n - 1;
for (i = my_first_n; i <= my_last_n; i++) {
pthread_mutex_lock(&mutex);
sum += a[i];
pthread_mutex_unlock(&mutex);
}
return NULL;
}
int main() {
pthread_t* thread_handles;
thread_handles = (pthread_t*)malloc(thread_count * sizeof(pthread_t));
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
srand(time(0));
a = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
a[i] = rand() % 100;
for (long i = 0; i < thread_count; i++) {
pthread_create(&thread_handles[i], NULL, calc_sum, (void*)i);
}
printf("Hello from the main thread\n");
for (int i=0; i < thread_count; i++)
pthread_join(thread_handles[i], NULL);
pthread_attr_destroy(&attr);
int ans = 0;
for (int i = 0; i < n; i++)
ans += a[i];
printf("The total sum is %d\n", sum);
printf("The right answer is %d\n", ans);
free(thread_handles);
return 0;
重新编译代码：
g++ -lpthread -g -o nodatarace nodatarace.cpp -fsanitize=thread
运行可执行程序：
birdie@birdie-ThinkPad-E575:~/桌面/parallel/hw3$ ./nodatarace
Hello from the main thread
The total sum is 4950650
The right answer is 4950650
加锁后，不会发生数据竞争，可以成功执行程序。加法成功计算。
实验结果
数据竞争
未加锁前，具有数据竞争：
可以发现，加法的结果是不正确的。
加锁后
加锁后，数据竞争被消除：
实验中遇到的困难
这个困难，可真的是血和泪的教训。
一开始，尝试使用LLVM工具的时候，安装了clang编译器。然后还是利用上述的数组加法代码进行编译：
clang -fsanitize=thread -g -O1 datarace.cpp -pthread
结果发现，编译成功了。我心想，没道理啊，这不摆到明是数据竞争吗，难道是我设的数组太大了，clang没有检测出来吗。抱着将信将疑的态度，我换了一份具有更加离谱的数据竞争的代码：
#include <pthread.h>
#include <stdio.h>
int Global;
void *Thread1(void *x) {
Global++;
return NULL;
}
void *Thread2(void *x) {
Global--;
return NULL;
}
int main() {
pthread_t t[2];
pthread_create(&t[0], NULL, Thread1, NULL);
pthread_create(&t[1], NULL, Thread2, NULL);
pthread_join(t[0], NULL);
pthread_join(t[1], NULL);
}
我心想，这下总该数据竞争了吧，毕竟官方文档都是这么写的。然后我再次编译，还是没有任何报错或者是WARNING的信息。我觉得很不可思议，这不是官方文档的例子吗。接着我怀疑，该不会是clang只能检测c而不能检测cpp吧。虽然我自己觉得也不太可能，但毕竟为写的代码也没有用到c++特有的特性，于是改成c语言，再次尝试。
很显然，我还是成功编译了。带着疑惑，我开始在网上寻找答案，可是，一无所获。我开始逐一排查，难道是pthread的问题吗？于是我将代码改写成OpenMP，还是编译成功了。我很不理解，一气之下将clang给删除了，直接下载了clang和LLVM的源码来编译。还是徒劳无功，此时距离我开始做这个作业已经过去三天了，我依旧没有解决问题。然后我尝试了另外几种下载clang的方式，然后重新实施上述步骤，徒劳无功。
就当我快要放弃的时候，我突然想起来一件事，LLVM是怎么检测到我的数据竞争的？带着这个疑问，我运行了一下可执行程序，它终于发出数据竞争的WARNING了。对啊，clang不运行我的代码，它怎么知道我数据竞争了！
这三天的来回折腾，告诉了我一个道理，遇到一些使用工具上的困难，想想工具的原理是什么，不然就会像一个傻子一样。