之前的加锁并发其实并没有真正的提高效率, 因为还是就一个共享变量来操作, 本质上还是执行完了全部计算. 实际上现代处理器具有多个核心, 可以同时执行与核心数量相等的线程.
现在来看一下真正利用多个线程并行处理的程序
提高并行性的代码
将任务分配到不同线程的方法, 并不是采取加锁的方式, 而是让各个线程处理不相交的区域, 然后将结果汇总即可. 这样每个线程可以独立的工作, 无需同步或者依赖其他线程的计算结果.
CSAPP 采用了三种方法:
- 使用共享全局变量, 各个线程负责计算数组的一部分, 但在更新全局变量的时候依然采取加锁的方式
- 每个线程每次迭代的时候直接更新结果数组的一个元素, 最后主线程将结果数组求和
- 每个线程使用一个局部变量存放结果, 计算完毕之后再将局部变量放到结果数组中, 之后主线程对结果数组求和
这三种方式, 第一种的性能非常差, 是因为加锁还带来了额外的开销. 第二种的性能稍微好一些, 但第三种的性能最好, 而且基本上满足四核心(Haswell 处理器)的时候程序基本按照总时间/核心的速度运行的更快. 而在超过4核的时候, 调度开销有所上升, 所以一般并行程序都根据机器的核数量来写, 当然也有超线程技术, 就可以根据实际的线程数量来写.
并行程序的性能评价
并行程序的性能评价一般用 Sp = T1 / Tp 来评价, T1是程序在1个核上的执行时间, Tp是在P个核上的执行时间.
根据T1的不同, 如果T1是顺序执行版本, 则叫做绝对加速比. 如果T1是并行版本, 则叫做相对加速比.
还有一种评价方法叫做效率, 即 Ep = T1/(p * Tp) = Sp/p, 效率考虑到了核心数量的影响, 用来衡量并行化造成的开销影响, 高效率的程序在同步和通信上花费的时间更少.
练习 12.11 填写并行程序的指标表格
| 线程 t | 1 | 2 | 4 |
| 核 p | 1 | 2 | 4 |
| 运行时间 Tp | 12 | 8 | 6 |
| 加速比 Sp | 由于效率=1, 可算出加速比=1 | 1.5 | 加速比 = p*Ep = 2 |
| 效率 Ep | 100% | 效率 = 1.5/2 = 75% | 50% |
线程安全 – 线程不安全的函数
线程安全 thread-safety 的函数, 被多个并发程序调用的时候, 会一直产生正确的结果, 如果一个函数不具备这个条件, 就不是线程安全的.
有四种不安全函数:
- 不保护共享变量的函数. 这种函数类似于一开始编写的将cnt乘以2的函数, 压根没有保护共享变量, 随意读写. 将其修改成线程安全函数, 需要读写变量的地方加上PV操作.
- 保持跨越多个调用状态的函数. 这种函数的状态依赖于前次调用的结果, 比如随机数生成函数包, 每次会计算下一次的种子, 然而多线程调用的时候, 可能会在计算下一次种子之前再次访问这个函数, 这样就得到了连续多个一样的随机数. 修改这种函数一般需要修改源代码.
- 返回指向静态变量的指针的函数. 这个程序包在参加编译的时候, 在内存里放了一个静态变量, 然后将结果指向这个变量, 返回指针. 这导致多线程调用的时候, 全部都在共享这个静态变量. 改进的方法一种是重写这个函数, 另一种方法就是在调用这个函数的时候加锁, 然后将函数的返回值复制到一个私有的内存位置, 一般可以使用一个包装函数.
- 调用线程不安全函数的函数. 如果一个函数在调用上边三类函数, 这个函数也是线程不安全的, 但如果调用的是第一类和第三类, 可以通过加锁来让这个函数变成线程安全的.
线程安全 – 线程安全的函数
有线程不安全的函数, 也有线程安全的函数. 线程安全的函数有一类叫做可重入函数, 其特点是: 当它们被多个线程调用的时候, 不会引用任何共享数据..
注意, 并不是所有的线程安全函数都是可重入函数, 可重入函数只是一种线程安全函数. 像上边的线程不安全的第一类函数, 即使经过改造加锁, 也不是可重入函数, 因为操作了共享变量.
可重入函数相比不可重入的线程安全函数效率要高一些, 因为无需同步开销. 一般来说可以将上边的第二类函数, 通过改成每次由调用者传入变量, 将其修改成可重入的函数.
可重入函数又分为两种:
- 显式可重入函数: 即所有的函数参数都是传值而不是传递引用, 所有数据都是本地变量. 这个其实就是一个纯粹的过程.
- 隐式可重入函数: 即传递的参数中有指针, 但是指针不指向共享数据.
所以可重入不仅仅是被调用函数的特性, 还与调用者有关, 这点要注意.
大多数C标准库中的函数都是线程安全的. 不安全的常见函数有 rand, strrok, asctime, ctime, inet_ntoa, localtime. 这里边除了inet_ntoa之外, 都有结尾_r的线程安全版本.
竞争
当一个程序对其中的各个线程的执行顺序有要求, 而没有做同步处理的话, 线程之间就会产生竞争. 不应该假定线程会按照一种固定的顺序执行.
看一个简单的例子:
#include "csapp.h"
#define N 300
void *thread(void *vargp);
int main(){
pthread_t tid[N];
int i;
for (i = 0; i < N; i++) {
//将i的地址传给线程, 注意i 是main的局部变量, 对线程来说是共享变量
Pthread_create(&tid[i], NULL, thread, &i);
}
for (i = 0; i < N; i++) {
Pthread_join(tid[i], NULL);
}
exit(0);
}
void *thread(void *vargp) {
//读i的值, 注意, 很可能和i自增的过程发生竞争
int myid = *((int *) vargp);
printf("Hello, myid is %d\n", myid);
return NULL;
}
这个程序的意图是每次i自增之后, 新启动的线程读取i的新值. 也就是每一次i++必须发生在 myid = *((int *) vargp 之前, 从执行的结果看, 并不是这样. 因为二者的顺序并不是这样执行的.
如果要不出现竞争, 就要让线程的操作彼此独立, 即要么在操作共享变量上加锁, 要么让线程操作完全不同的内存空间. 这里使用完全不同的内存空间让线程使用, 程序修改如下:
#include "csapp.h"
#define N 300
void *thread(void *vargp);
int main(){
pthread_t tid[N];
//一个指针
int i, *ptr;
for (i = 0; i < N; i++) {
//申请一个内存空间, 每次传递给线程的ptr都不同. 即使被线程释放, 在传递给新线程相同的区域, 也不受影响, 因为线程已经将值保存在线程的局部变量中
ptr = Malloc(sizeof(int));
*ptr = i;
Pthread_create(&tid[i], NULL, thread, ptr);
}
for (i = 0; i < N; i++) {
Pthread_join(tid[i], NULL);
}
exit(0);
}
void *thread(void *vargp) {
//读取指针指向的值到局部变量
int myid = *((int *) vargp);
//释放内存
Free(vargp);
printf("Hello, myid is %d\n", myid);
return NULL;
}
练习 12.13 如果在主线程创建线程之后立刻释放内存, 会如何?
这里主线程释放内存的操作和线程取值的操作会发生竞争, 因为线程取值的操作在启动线程的时候未必能够完成, 如果主程序先释放内存, 线程取值的时候就会发生异常.
练习 12.14 不使用malloc或者free函数的方法
可以使用一个数组, 按照索引将i放入其中, 然后传递给线程这个数组的地址, 这样每个线程的id也是独立的.
这样的优点是程序运行速度比较快, 因为减少了申请和释放内存的开销. 弱点是程序的灵活性不足.
还一种可能是直接传值, 也就是把i直接强制转换成指针, 这样值是不变的. 线程由于拿到的就是值, 所以互相独立.
优点是速度比较快, 程序灵活性也有, 缺点是移植性差, 64位和32位系统没有问题, 但是更老的系统指针很可能装不下int类型的数值.
死锁
死锁是指一组线程全部在等待永远也无法为真的情况. 如果用两个信号量来实现互斥, 而各个线程的加锁顺序不同, 就可能出现死锁.
这里有一个简单的避免死锁的原则, 就是所有的线程都按照相同的顺序加锁, 然后按照加锁的反向顺序释放锁(即最后加的锁最先释放), 这个程序就不会出现死锁情况.
练习 12.15 死锁问题
初始时 s = 1, t = 0:
线程1: 线程2:
P(s) P(s)
V(s) V(s)
P(t) P(t)
V(t) V(t)
进度图就省略了, 这个程序一定会死锁, 因为不管如何, 两个线程都会运行到P(t)的位置, 然而t=0, 导致两个线程都阻塞, 就会发生死锁.
只要将 t 设置为1, 就可以避免这个情况.
看完了, 竟然看完了, 深刻的感觉到相比一年前的变化之大. 果然学一门硬技术才是吃饭的本钱. 下一步, 就是要找点算法书开始看了.
一路看到这里，感谢博主的分享！