1. 概述

   本章介绍了并发编程，主要涉及了并行计算、线程及其原理、线程防死锁操作等。较为全面的介绍了多任务处理、线程同步和并发编程的原理及方法。

   目录
   • 1、并行计算
   • 2、线程
   • 3、线程管理
   • 4、线程同步
   • 5、实践

1、并行计算

1. 并行计算

   并行计算是一种计算方法，通过使用多个执行并行算法的处理器相较串行计算更快地解决问题。现代多核处理器的结构能很好的实现并行计算。计算机的发展未来也是并行计算。

2. 顺序算法与并行计算

   • 顺序算法

     一般代码块格式如下，顺序算法的每个代码块可能包含多个步骤。各个步骤都是通过单个任务依次执行，每次执行一个步骤。所有步骤都执行完后任务结束。

     begin
     	step_1;
     	step_2;
     	...
     	step_n;
     end
     // next step
     

   • 并行算法

     一般代码块的结构如下，并行计算的代码块中的所有任务并行执行，所有任务都结束后执行下一步骤。

     cobegin
     	task_1;
     	task_2;
     	...
     	task_n;
     coend
     // next step
     

3. 并行性与并发性

   • 并行性

     一个并行算法中的所有任务同时都在运行，一般在理想情况下的多处理系统中可实现并行运算。

   • 并发性

     在单CPU系统中，一次只可执行单个任务，只能通过并发执行实现逻辑上的并行执行。

2、线程

1. 线程介绍

   线程是与进程共享地址空间的独立执行单元，同时，线程也与进程共享其他资源。线程可以创建与自己共享地址的子线程，子线程也可再创建自己的子线程，进程就是通过它的主线程和子线程实现任务处理的。不同的操作系统实现线程的方式不尽相同，但目前几乎所有的操作系统都支持IEEE POSIX 1003.1的线程标准Pthread。

2. 线程的优点

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

3. 线程的缺点

   • 需要来自用户的明确同步
   • 库函数对于线程来说不够安全
   • 单CPU系统中上下文切换耗时过大

3、线程管理

​ 线程与进程类似，也有内核模式和用户模式。用户模式下线程在其进程的相同地址中执行，每个线程都拥有各自的执行 堆栈。内核模式下则根据系统内核的调度策略执行系统调用，也有挂起、激活等过程。系统内核调用会优先选择同一进 程中的线程。

线程管理函数

大部分操作系统都兼容POSIX Pthread线程标准，Pthread提供了如下用于线程管理的程序编程接口：

pthread_create(thread, attr, function, arg);	-> 创建线程
pthread_exit(status);			           -> 终止线程
pthread_cancel(thread);                     -> 取消线程
pthread_attr_init(attr);                    -> 初始化线程属性
pthread_attr_destroy(attr);                 -> 删除线程属性

• 创建线程

  可以使用pthread_create()函数创建线程：

  int pthread_create(pthread_t *pthread_id, pthread_attr_t *atr, void *(*func)(void *), void *arg);
  

  如果创建成功则返回0，失败则返回错误代码。

  参数：

  • pthread_id是指向pthread_t类型变量的指针。它会被操作系统内核分配的唯一线程ID填充。在POSIX中，pthread_t是一种不透明的类型.线程可以通过pthread_self()函数获得自己的ID。在Linux中，pthread_t类型被定义为无符号长整型，因此ID可以打印为%lu。

  • attr是指向另一种不透明数据类型的指针，它指向线程属性。

  • func要执行的新线程的新线程函数的入口地址。

  • arg指向线程函数参数的指针

    void *func(void *arg);
    

4、线程同步

1. 线程在进程的同一地址空间中执行，共享同一地址空间中的所有全局变量和数据结构。不同的线程对同一个共享资源进行操作时，如果结果取决于线程的执行顺序，就会产生竞争，这是并发程序所杜绝的。

2. 互斥量

   为了解决线程间的竞争，可以使用互斥量。它是一个锁，当拥有锁的时候才可以进行操作。

   互斥量可以通过静态和动态两种方式初始化。

3. 死锁预防

   互斥量采用了*协议，如果线程无法获取互斥量，那么就会被阻塞，等待互斥量解锁后才能继续操作。当多个实体互相等待时，死锁就会出现。应对方法有死锁预防、死锁规避、死锁检测和恢复等。

   预防死锁可以通过条件加锁函数pthread_mutex_trylock()实现。

4. 条件变量

   条件变量可以实现线程间协作

5、实践

​ 教材p-127的示例4.2：用并发线程快速排序

• 代码

/* * * chapter4 code example 4.2 QUICK SORT * * */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
typedef struct{
        int upperbound;
        int lowerbound;
}PARM;
#define N 10
int a[N] = {2,1,3,4,6,5,8,7,9,0};       //unsorted data
int print()     //print current A[] contents
{
        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];          //pick low pivot value
        left = lowerbound - 1;          //scan index from left side
        right = upperbound;             //scan index from right side
        if(lowerbound >= upperbound)
                pthread_exit (NULL);
        while(left < right){            //partition loop
                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;              //put pivot back
        temp = a[pivotIndex] ;
        a[pivotIndex] = pivot;
        a[upperbound] = temp;
        //start the "recursive threads"
        aleft.upperbound = pivotIndex - 1;
        aleft.lowerbound = lowerbound;
        aright.upperbound = upperbound;
        aright.lowerbound = pivotIndex + 1;
        printf("%lu: create left and right threadsln", me) ;
        pthread_create(&leftThread , NULL , Qsort , (void * )&aleft);
        pthread_create(&rightThread , NULL , Qsort , (void *)&aright);
        //wait for left and right threads to finish
        pthread_join(leftThread,NULL);
        pthread_join(rightThread, NULL);
        printf("%lu: joined with left & 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);
        //wait for qs thread to finish
        pthread_join(thread,NULL);
        printf ("main %lu sorted array = ", me);
        print () ;
}                                    

• 遇到的问题

  1、直接gcc qs.c时出现了如下报错：

解决：

​ 函数qsort是stdlib头文件中所定义的库函数之一，自定义的函数不能与它同名，将定义的qsort()函数改名为Qsort() 即可。

2、解决问题1后再次gcc qs.c时出现下列报错：

解决：

​ 使用了pthread头文件，程序编译时需要加上 -pthread 参数，即用如下模式编译：

gcc qs.c -pthread

​ 完成编译，得到可执行文件。

• 运行

  

• 教材结果