第四章：并发编程

并行计算导论

顺序算法与并行算法

顺序算法：所有步骤通过单个任务依次执行，每次执行一个步骤，当所有步骤执行完成时，算法结束。
并行算法：cobegin-coend代码块来指定独立任务，所有任务都是并行执行的，紧接着cobegin-coend代码块的下一个步骤将只在所有这些任务完成之后执行。

并行性与并发性

在理想情况下，并行算法中的所有任务都应该同时实时执行。
真正的并行执行只能在有多个处理组件的系统中实现，比如多处理器或多核系统。
在单CPU系统中，一次只能执行一个任务。在这种情况下，不同的任务只能并发执行，即在逻辑上并行执行。

线程

线程的原理

线程是某进程同一地址空间上的独立执行单元。创建某个进程就是在一个唯一地址空间创建一个主线程。当某进程开始时，就会执行该进程的主线程。

线程的优点

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

线程的缺点

由于地址空间共享，线程需要来自用户的明确同步
许多库函数可能对线程不安全
在单CPU系统上，使用线程解决问题实际上要比使用顺序程序慢

线程操作

线程的执行轨迹与进程类似，线程可在内核模式或用户模式下执行。
在用户模式下，线程在进程的相同地址空间中执行，但每个线程都有自己的执行堆栈。

线程管理函数

创建线程

使用pthread_create()创建线程函数
int pthread_create(pthread_t *pthread_id,pthread_attr_t *attr,void *(*func)(void*),void *arg)
- pthread_id是指向pthread_t类型变量的指针
- attr是指向另一种不透明数据类型的指针，attr如果是NULL，将使用默认属性创建线程
- func是要执行的新线程函数的入口地址
attr 参数的使用步骤
- (1)定义一个pthread属性变量pthread attr tattr。
- (2)用pthread attrinit (&attr)初始化属性变量。
- (3)设置属性变量并在pthread create0)调用中使用。
- (4)必要时，通过pthread attr destroy (&attr)释放attr 资源。

线程ID

线程ID是一种不透明的数据类型，取决于现实情况
int pthread_equal(pthread_t t1,pthread_t t2);
如果是不同的线程，返回0，否则返回非0

线程终止

线程函数结束后，线程即终止
int pthread_exit(void *status)；
进行显式终止，其中状态是线程的退出状态。0退出值表示正常终止，非0表示异常

线程连接

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

线程同步

互斥量

最简单的同步工具是锁，它允许执行实体仅在有锁的情况下才能继续执行。在 Pthread中，锁被称为互斥量，意思是相互排斥。
初始化互斥量
- 静态方法
- 动态方法，使用pthread_mutex_init()函数，可通过attr参数设置互斥属性

pthread_mutex_lock(&m);
access shared data object;
pthread_mutex_unlock(&m);

死锁预防

互斥量使用封锁协议。
在任何封锁协议中，误用加锁可能会产生一些问题。
死锁是一个状态，在这种状态下，许多执行实体相互等待，无法继续进行下去.

条件变量

静态方法初始化
动态方法初始化

生产者——消费者问题

共享全局变量

int buf[NBUF];
int head,tail;
int data;

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NBUF 5
#define N	10
// shared global variables 
int buf[NBUF];	// circular buffers
int head, tail;	// indices
int data;	// number of full buffers
pthread_mutex_t mutex; 
pthread_cond_t empty, full;

int init()
{
    head = tail = data = 0; 
    pthread_mutex_init(&mutex, NULL); 
    pthread_cond_init(&full, NULL); 
    pthread_cond_init(&empty, NULL);
}

void *producer() 
{
    int i;
    pthread_t me = pthread_self();
    for (i=0; i<N; i++) // try to put N items into buf[]
    {
        pthread_mutex_lock(&mutex);	// lock mutex
        if (data == NBUF)
        {
            printf ("producer %lu： all bufs FULL： wait\n", me);
            pthread_cond_wait(&empty, &mutex); // wait
        }
        buf[head++] = i+1;
        head %= NBUF;
        data++;
        printf("producer %lu： data=%d value=%d\n", me, data, i+1);
        pthread_mutex_unlock (&mutex); 
        pthread_cond_signal(&full);
    }
    printf("producer %lu: exit\n", me);
}

void *consumer()
{
    int i, c;
    pthread_t me = pthread_self();
    for (i=0; i<N; i++)
    {
        pthread_mutex_lock(&mutex);	// lock mutex
        if (data == 0)
        {
            printf ("consumer %lu: all bufs EMPTY: wait\n", me); 
            pthread_cond_wait(&full, &mutex); // wait
        }
        c = buf[tail++];	// get an item
        tail %= NBUF;
        data--;	// dec data by 1
        printf("consumer %lu： value=%d\n", me, c); 
        pthread_mutex_unlock(&mutex);	// unlock mutex
        pthread_cond_signal(&empty);	// unblock a producer, if any
    }
    printf("consumer %lu: exit\n", me);
}

int main ()
{
    pthread_t pro, con;
    init();
    printf("main： create producer and consumer threads\n");
    pthread_create(&pro, NULL, producer, NULL);
    pthread_create(&con, NULL, consumer, NULL);
    printf("main: join with threads\n");
    pthread_join(pro, NULL);
    pthread_join(con, NULL);
    printf("main: exit\n");
}