第四章学习笔记

第四章 并发编程

4.1 并行计算导论

1、顺序算法与并行算法

顺序算法:所有步骤通过单个任务依次执行,每次执行一个步骤。当所有步骤执行完成,算法结束。

并行算法:所有任务并行执行,所有任务完成后执行下一步。

2、并行性与并发性

在单CPU系统中,一次只能执行一个任务。在这种情况下,不同的热舞执行并发执行,即在逻辑上并行执行。在单周期CPU系统中,并发性是通过多任务处理来实现的。

4.2 线程

1、线程的原理

线程是某进程同一地址空间上的独立执行单元。

2、线程的优点

(1)线程创建和切换速度更快。

(2)线程的相应速度更快。

(3)线程更适合并行计算

3、线程的缺点

(1)由于地址空间共享,线程需要来自用户的明确同步。

(2)许多库函数可能对线程不安全。

(3)在单CPU系统上,使用线程解决问题实际上要比使用顺序程序慢,这是由在运行时创建线程和切换上下文的系统开销造成的。

4.3 线程操作

线程的执行轨迹与进程类似。线程可在内核模式或用户模式下执行。线程时独立执行单元,可根据操作系统内核的调度策略,对内核进行系统调用。

4.4 线程管理函数

pthread库提供了用于线程管理的以下API。
第四章学习笔记

1、创建线程

使用pthread_creat函数创建线程。

int pthread_creat(pthread_t *pthread_id,pthread_attr_t *attr,void *(*func)(void *),void *arg);

其中,attr参数最复杂。下面给出了attr参数的使用步骤。

(1)定义一个pthread属性变量pthread_attr_t attr。

(2)用pthread_attr_init(&attr)初始化属性变量。

(3)设置属性变量并在pthread_create()调用中使用。

(4)必要时,通过pthread_attr_destory(&attr)释放attr资源。

创建分离线程

第四章学习笔记

每个线程都是用默认堆栈的大小来创建。在执行过程中,线程课通过函数找到他的堆栈大小:

size_t pthread_attr_getstacksize()

它可以返回默认的堆栈大小。

2、线程ID

线程ID是一种不透明的数据结构类型,取决如实际情况,如果需要可以使用pthread_equal()函数对他们进行比较

int pthread_equal (pthread_t t1,pthread_t t2)

如果是不同的线程返回0,否则非0.

3、线程终止

int pthread_exit (void *status);

0表示正常终止,非0表示异常终止。

4、线程连接

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

int pthread_join(pthread_t,void **status_Ptr);

终止线程的退出状态一status_ptr返回。

5、线程同步

同步是一种机制和规则,用于确保共享数据对象的完整性和并发执行肢体的协调性。

1、互斥量

最简单的同步工具时锁,它允许执行实体仅在有锁的情况下才能继续执行。在Pthread中,锁被称为互斥量。在使用钱必须对他们进行初始化。

(1)静态方法

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

定义互斥量m,并使用默认属性对其进行初始化。

(2)动态方法

pthread_mutex_init(pthread_mutex_t *m,pthread_mutexattr_t,*attr);

通常attr参数可以设置位NULL,作为默认属性。

初始化完成后,线程可以通过以下函数使用互斥量。

!第四章学习笔记

线程使用互斥量来保护共享数据对象。

互斥量的典型用法

线程先创建一个互斥量并对它进行依次初始化。新创建的互斥量处于解锁状态,没有所有者。每个线程都试图访问一个共享数据对象:

第四章学习笔记

只有获取了互斥量的线程才能访问共享数据对象。

2、死锁预防

互斥量使用*协议。有多种方法可以解决可能的死锁问题,其中包括死锁防御、死锁规避、死锁检测和回复等。在实际情况中,唯一可行的方法时死锁预防,试图在设计并行算法是防止死锁发生。

一种简单的死锁预防时对互斥量进行排序,并确保每个线程只在一个方向请求互斥量,这样请求序列中就不会有循环。

条件加锁和退避预防死锁
第四章学习笔记

3、条件变量

作为锁,互斥量仅用于确保线程只能互斥地访问临界区中的共享数据对象。条件变量提供了一种线程协作的方法。在Pthread中,使用othread_cond_t来声明条件变量,而且必须在使用前进行初始化。

(1)静态方法

pthread_cond_t con = PTHREAD_COND_INITALLIZER;

(2)动态方法

使用pthread_cond_init()函数,通过attr参数设置条件变量。

4、信号量

信号量是进程同步的一般机制。(计数)信号量是一种数据结构

struct sem{

int value;

struct process *queue

}s;

最有名的信号量操作时P和V,定义见下文。

第四章学习笔记

5、屏障

线程连接操作允许某线程(通常是主线程)等待其他线程终止。在某些情况下,保持线程活动会更好,但应要求他们在所有线程都达到指定同步点之前不能继续活动。在Pthreads中,可以采用屏障以及一系列屏障函数。

首先,主线程创建一个屏障对象

pthread_barrier_init(&barrier NULL,nthreads);

用屏蔽中同步线程数字对他进行初始化。然后,主线程创建工作线程来执行任务。

6、linux中的线程

与其他操作系统不同,Linux不区分进程和线程。对于Linux内核,线程只是一个与其他进程共享某些资源的进程。在Linux中,进程和线程都是由clone()系统调用创建的。

int clone(int(*fn)(void *),void *chile_stack,int flags,void *arg)

实践与代码

例4.1:用线程计算矩阵的和

假设计算一各N*N整数矩阵中所有元素的和。

源代码

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

void *func(void *arg)
{
        int j,row ;
        pthread_t tid = pthread_self();
        row = (int)arg;
        printf("Thread %d [%lu] computes sum of row %d\n",row,tid,row);
        for(j=0;j<N; j++)
                sum[row] += A[row][j];
        printf("Thread %d [%lu] done:sum [%d] =%d\n",row,tid,row,sum[row]);
        pthread_exit ((void*)0);
}
        int main(int argc, char *argv[])
{
        pthread_t thread[N];
        int i,j,r,total = 0;
        void *status;
        printf("Main: initialize A matrix\n");
        for(i=0; i<N;i++){
                sum[i] = 0;
                for(j=0;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 thread\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 ("tatal = %d\n",total );
        pthread_exit(NULL);
}

主线程会先生成一个N×N整数矩阵。然后,它会创建N个工作线程,将唯一行号作为参数传递给各工作线程,并等待所有工作线程终止。每个工作线程计算不同行的部分和,并将部分和存入全局数组 int sum[N]的相应行中。当所有工作线程计算完成后,主线程继续进行计算。它将工作线程生成的部分和相加来计算总和。

运行结果

第四章学习笔记

例4.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}; // unsorted data

int print()//print current a[] contents

{

	int i;

	printf("[ ");

	for (i=0 ; i<N; i++)

		printf ("%d ", a[i]);

	printf("]\n");

}

void *asort(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 threads\n" , me) ;

	pthread_create (&leftThread,NULL,asort,(void * ) &aleft) ;

	pthread_create (&rightThread,NULL,asort,(void * ) &aright) ;

	//wait for left and right threads to finish

	pthread_join (leftThread,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,asort,(void *)&arg);

// wait for Qs thread to finish

pthread_join (thread,NULL);

printf ( "main %lu sorted array = " , me) ;

print () ;

}
当程序启动时,它作为进程的主线程运行。主线程调用qsort(&arg),其中arg =[lowerbound=0, upperbound=N-1]。qsort()函数实现一个N个整数数组的快速排序。在qsort()中,线程会选择一个基准元素,将数组分成两部分,这样左边部分的所有元素都小于基准元素,右边部分的所有元素都大于基准元素。然后,它会创建两个子线程来对这两部分进行排序,并等待子线程完成。每个子线程通过相同的递归算法对自己的部分进行排序。当所有的子线程工作完成后,主线程继续工作。它会打印排序后的数组并终止。

运行结果

第四章学习笔记

问题与解决方法

问题:在试用Linux 线程模块时,编译命令为 gcc c4.*.c时,会出现如下错误
第四章学习笔记

解决办法:在网上搜索后发现是未找到库,将命令修改后
gcc c4.*.c -pthread
就能编译成功了

代码链接

https://gitee.com/lhp6666/linux/tree/master/

上一篇:线程的属性


下一篇:c++项目中 锁的使用