并行计算

多线程基本概念

线程（Thread）是进程上下文（contex）中执行的代码序列，也称作轻量级进程。

在支持多线程的系统中，进程是资源分配的实体，线程是被调度执行的基本单元。

线程与进程的比较	内容
调度	线程是CPU调度的基本单位，进程是资源拥有的基本单位。同一进程中线程的切换不会引起进程切换，从而避免频繁的系统调用。
并发性	不仅进程之间可以并发执行，一个进程的多个线程之间也可以并发执行，一个进程下可设置多个线程
拥有资源	进程是拥有资源的独立单位；线程不拥有系统资源，但可以访问其所属进程的资源，即一个进程的资源可供其所有线程共享。
系统开销	进程在创建或销毁时系统均需要为之分配或回收资源，进程切换时系统需保存当前进程的所有设置；线程切换时只需保存和设置少量寄存器的内容，同一进程的线程之间的通信比较容易。

在计算机中，系统通过线程池管理线程。一个线程池可维护多个线程，等待调度器分配可并发执行的任务。避免了在短处理时间任务时创建与销毁线程的代价。

共享存储访问

计算机采用层次结构存储系统。

存储器层次结构

竞态条件与临界区

但是这样会出现竞态条件（Race Conditions）：当两个或多个线程试图在同一时刻访问共享内存或读写某些共享数据时，寄存器的值可能无法及时更新，导致最后的结果取决于线程的执行顺序。

为了解决这一困境，提出了临界区的概念：包含访问共享数据的代码。因此，在临界区内，任意时刻至多只能有一个线程在执行相关代码。

互斥锁

互斥锁（mutex）是实现线程同步的一种方法。线程对共享资源访问之前必须先获得锁，否则线程将保持等待状态，直到该锁可用。

实例分析

假设现有一段长文本，要求统计其中3的个数

普通的串行代码应为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int *array;
int length;
int count;

int countThree() {
    int i;
    count = 0;
    for (i=0; i<length; i++) {
        if (array[i] == 3) {
            count++;
        }
    }
    return count;
}

运用域分解并行化方法，将其划分为若干个子数据段：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


int t;
int *array;
int length;
int count;

int countThree() {
    int i;
    count = 0;
    // 创建线程
    for (i=0; i<t; i++) {
        thread_create(countThree_thread, i);
    }
    return count;
}

void countThree_thread(int id) {
    int length_per_thread = length / t;
    int start = id*length_per_thread;

    for (i = start; i<start+length_per_thread; i++) {
        if (array[i] == 3) {
            // 加互斥锁
            mutex_lock(m);
            count ++;
            // 解锁
            mutex_unlock(m);
        }
    }
}

但是，此并行算法的性能远不及串行算法：

算法性能分析1

这是因为加锁会消耗时间，同时所有线程两两互斥可看作串行逻辑，并没有变化。

改进方法：加锁过程应当放在循环计数外。当每个线程分别计数完成后，再将各个数目相加得到总数目。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


...
int private_count[MaxThreads];
mutex m;

void countThree_thread(int id) {
    int length_per_thread = length / t;
    int start = id*length_per_thread;

    for (i = start; i<start+length_per_thread; i++) {
        if (array[i] == 3) {
            private_count[id]++;
        }
    }
    // 汇总时必须加锁，防止出现竞争
    mutex_lock(m);
    count += private_count[id];
    mutex_unlock(m);
}

修改后并行效率大幅提升，但仍与串行有差距。这是因为计算机系统的cache一致性与伪共享，虽然不同线程的private_count形式上互不干扰，但在缓存中可能处于一个缓存块中，在更新数据时会发生阻塞。

算法性能分析2

一种解决办法是强行将计数器的占用加大，使它们分别位于不同的缓存块中。

PThread多线程

主要操作函数：

函数	功能
`pthread_create`	创建一个线程
`pthread_cancel`	终止另一个线程
`pthread_detach`	分离线程
`pthread_equal`	检查两个线程的id是否相等
`pthread_exit`	退出线程但不退出进程
`pthread_join`	等待一个线程
`pthread_self`	获得自己的线程id

Java多线程

创建方法：

通过Thread类的子类实现多线程。
定义一个实现Runnable接口的类实现多线程。