第4章 并发编程

在早期，大多数计算机只有一个处理组件，即中央处理器CPU，受此硬件条件的限制，计算机程序通常是为串行计算编写的，在只有一个CPU的情况下，每次只能按顺序执行某算法的一个指令和步骤。但基于分治原则的算法经常表现出高度的并行性，可通过并行或并发执行来提高计算速度。近年来，随着多核处理器的出现，大多数操作系统都支持对称多处理（SMP）。

4.1 并行计算导论

1.顺序算法与并行算法

• 顺序算法

  begin
    step_1
    step_2
    ···
    step_n
  end

• 并行算法

  cobegin
    task_1
    task_2
    ···
    task_n
  coend

2.并行性与并发性

并行算法通常只识别可并行执行的任务，但没有规定如何将任务映射到处理组件。理想情况下，并行算法中的任务都同时执行，但只能在多处理器或多核系统中实现。
在单CPU系统中，并发性是通过多任务处理来实现的。

4.2 线程

1.线程的原理

线程是某进程同一地址空间上的独立执行单元，创建讴歌进程就是在一个唯一地址空间创建一个主线程。当某进程开始时，就会执行该进程的主线程。如果只有一个主线程，那么进程和线程没有区别。

• 如果一个线程被挂起，其他线程可以继续执行。
• 除共享共同的地址空间外，线程还共享进程的其他资源（用户id，打开的文件描述符，信号等）

2.线程的优点

• 线程创建和切换速度更快
• 线程的响应速度更快
• 线程更适合并行计算

3.线程的缺点

• 需要来自用户的明确同步（由于地址空间共享）
• 许多库函数对线程不安全
• 单CPU系统上，使用线程比使用顺序程序慢（创建线程和切换上下文的系统开销）

4.3 线程操作

• 内核模式：对内核进行系统调用，变为挂起、激活以继续执行等。
• 用户模式：线程在进程的相同地址空间中执行，每个线程都有自己的堆栈。

4.4 线程管理函数

1.创建线程

• pthread_create函数

int pthread_create (pthread_t *pthread_id,pthread_attr_t *attr,
                    void *(*func)(void *), void *arg);
  //成功返回0，失败返回错误代码
  //pthread_id：指向pthread_t类型变量的指针
  //attr：指向另一种不透明数据类型的指针，指定线程属性
  //func：要执行的新线程函数的入口地址
  //arg：指向线程函数参数的指针

2.线程ID

一种不透明的数据类型的，取决于实现情况

int pthread_equal(pthread_t t1, pthread_t t2);//比较线程ID

如果是不同的线程，返回0，否则返回非0。

3.线程终止

线程函数结束后，即终止。

int pthread_exit (void *status);//显示终止

正常终止返回0，异常终止返回非0。

4.线程连接

一个线程连接可以等待另一个线程的终止

int pthread_join(pthread_t thread, void **status_ptr);//终止线程的退出状态以status_ptr返回

4.5 线程示例程序

1.用线程计算矩阵的和

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 4
int A[N][N], sum[N] ;

void *func (void *arg)  //threads function
{  
    int j, row;
    pthread_t tid = pthread_self(); //get thread ID number
    row = (int)arg;  //get row number from arg
    printf("Thread %d [%lu] computes sum of row %d\n", row, tid, row);
    for (j=0; j<N; j++)  //compute sum of A[row]in globalsum(row]
        sum[row] += A[row][j];
    printf("Thread %d [%lu] done: sum[%d] = %d\n",
            row, tid, row, sum[row]);
    pthread_exit((void*)0);  //thread exit: 0=normal termination
}

int main (int argc, char *argv[])
{
    pthread_t thread[N] ;  //thread IDs
    inti, j, r, total = 0;
    void *status;
    printf ("Main: initialize A matrix\n");
    for (i=0; i<N; i++){
        sum[i] = 0;
        for (j=O; j<N; j++){
            A[i][j] = i*N + j + 1;
            printf("%4d ", A[i][j]) ;
            }
            printf("\n") ;
        }  
        printf("Main: create %d threads\n", N) ;
        for(i=0; i<N; i++){
            pthread_create (&thread[i], NULL, func, (void *)i);
        }
        printf("Main: try to join with threads\n") ;
        for(i=0; i<N; i++){
            pthread_join(thread[i], &status);
            printf("Main: joined with %d [%lu]: status=%d\n",
                    i, thread[i], (int)status);
        }                   
        printf("Main: compute and print total sum: ");
        for (i=0; i<N; i++) 
            total += sum[i];
        printf("total = %d\n", total);
        pthread_exit (NULL) ;
}

运行结果：

2.用线程快速排序

#include <stdio. h>
#include <stdlib.h>
#include <pthread.h>

typedef struct
{
    int upperbound;
    int lowerbound;
} PARM;

#define N 10
int A[N] = {5,1,6,4,7,2,9,8,0,3};

int print()
{
    int i;
    printf("[ ") ;
    for (i=0; i<N; i++)
        printf("%d ", a[i]);
    printf("]\n") ;
}

void *qsort (void *aptr)
{
    PARM *ap, aleft, aright;
    int pivot, pivotIndex, left, right, temp;
    int upperbound, lowerbound;

    pthread_t me, leftThread, rightThread;
    me = pthread_self() ;
    ap = (PARM *)aptr;
    upperbound = ap->upperbound;
    lowerbound = ap->lowerbound;
    pivot = a[upperbound];
    left = lowerbound - 1;
    right = upperbound;
    if (lowerbound >= upperbound)
        pthread_exit (NULL) ;

    while (left < right) {
        do { left++; }
         while (a[left] < pivot) ;
            do { right--; }
             while (a[right] > pivot) ;
             if (left < right ) {
                temp = a[left] ;
                a[left] = a[right];
                a[right]= temp;
             }
        }
    print() ;
    pivotIndex = left;
    temp = a[pivotIndex];
    a[pivotIndex] = pivot;
    a[upperbound] = temp;
    aleft.upperbound = pivotIndex - 1;
    aleft.lowerbound = lowerbound;
    aright.upperbound = upperbound;
    aright.lowerbound = pivotIndex + 1;
    printf("%lu: create left and right threads\n", me);
    pthread_create(&leftThread,NULL, qsort, (void *)&aleft);
    pthread_create(&rightThread, NULL, qsort, (void *) &aright);
    pthread_join (leftThread, NULL) ;
    pthread_join (rightThread, NULL);
    printf("%lu: joined with 1eft & right threads\n", me);
}

int main(int argc, char *argv[])
{
    PARM arg;
    int i, *array;
    pthread_t me, thread;
    me = pthread_self() ;
    printf("main %lu: unsorted array = ",me);
    print();
    arg.upperbound = N-1;
    arg.lowerbound = 0;
    printf("main %lu create a thread to do QS\n", me);
    pthread_create (&thread,NULL, qsort, (void *)&arg);
    pthread_join(thread, NULL) ;
    printf( "main %lu sorted array = ",me);
    print() ;
}

4.6 线程同步

当多个线程试图修改同一共享变量或数据结构时，如果修改结果取决于线程的执行顺序，则称之为竞态条件。在并发程序中，绝不能有竞态条件。

1.互斥量

锁：允许执行实体仅在有锁的情况下才能继续执行的同步工具。
在Pthread中，锁被称为互斥量，意为*互相排斥**。

• 静态方法

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER

• 动态方法
  使用pthread_mutex_init()函数

2.死锁预防

互斥量使用封锁协议，如果某线程不能获取互斥量，就会被阻塞，等待互斥量解锁后再继续。
死锁是一种状态，许多执行实体相互等待，都无法继续下去。
有多种方法可以解决死锁问题：死锁预防、死锁规避、死锁检测和恢复等。

3.条件变量

提供了一种线程协作的方法

• 静态方法

pthread_cond_t con = PTHREAD_COND_INITIALIZER

• 动态方法
  使用pthread_cond_init()函数

4.信号量

是一种数据结构，必须使用一个初始值和一个空等队列进行初始化。从执行实体的角度来看，对信号量的操作都是原子操作或基本操作。

5.屏障

线程连接操作允许某线程等待其他线程终止，在Pthread中，可以采用的机制是屏障以及一系列屏障函数。

6.Linux中的线程

Linux不区分线程和进程，它们都是由clone()系统调用创建的。

原文地址：http://www.cnblogs.com/weihehahaha/p/16796474.html