Java教程

第四章学习笔记

本文主要是介绍第四章学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

读书笔记

本章论述了并发编程,介绍了并行计算的概念,指出了并行计算的重要性;比较了顺序算法与并行算法,以及并行性与并发性;解释了线程的原理及其相对于进程的优势;通过示例介绍了Pthread中的线程操作,包括线程管理函数,互斥量、连接、条件变量和屏障等线程同步工具;通过具体示例演示了如何使用线程进行并发编程,包括矩阵计算、快速排序和用并发线程求解线性方程组等方法;解释了死锁问题,并说明了如何防止并发程序中的死锁问题;讨论了信号量,并论证了它们相对于条件变量的优点;还解释了支持Linux中线程的独特方式。编程项目是为了实现用户级线程。它提供了一个基础系统来帮助读者开始工作。这个基础系统支持并发任务的动态创建、执行和终止,相当于在某个进程的同一地址空间中执行线程。读者可通过该项目实现线程同步的线程连接、互斥量和信号量,并演示它们在并发程序中的用法。该编程项目会让读者更加深入地了解多任务处理、线程同步和并发编程的原理及方法。

知识点总结

一、线程

线程是某进程同一地址空间上的独立执行单元。创建某个进程就是在一个唯一地址空间创建一个线程。当某进程开始时,就会执行该进程的主线程。如果只有一个主线程,那么进程和线程实 际上并没有区别。但是, 主线程可能会创建其他线程。 每个线程又可以创建更多的线程等。 某进程的所有线程都在该进程的相同地址空间中执行, 但每个线程都是一个独立的执行单元。

  • 线程优点
    线程创建和切换速度更快:若要在某个进程中创建线程,操作系统不必为新的线程分配内存和创建页表,因为线程与进程共用同一个地址空间。所以,创建线程比创建进程更快。
    线程的响应速度更快:一个进程只有一个执行路径。当某个进程被挂起时,帮个进程都将停止执行。相反,当某个线程被挂起时,同一进程中的其他线程可以继续执行。
    线程更适合井行计算:并行计算的目标是使用多个执行路径更快地解决间题。基于分治原则(如二叉树查找和快速排序等)的算法经常表现出高度的并行性,可通过使用并行或并发执行来提高计算速度。
  • 线程缺点
    由于地址空间共享,线程需要来自用户的明确同步。
    许多库函数可能对线程不安全
    在单CPU系统上,使用线程解决间题实际上要比使用顺序程序慢,这是由在运行时创建线程和切换上下文的系统开销造成的。
  • 线程操作
    线程的执行轨迹与进程类似。线程可在内核模式或用户模式下执行。在用户模式下,线程在进程的相同地址空间中执行,但每个线程都有自己的执行堆栈。线程是独立的执行单元,可根据操作系统内核的调度策略,对内核进行系统调用,变为桂起激活以继续执行等。为了利用线程的共享地址空间,操作系统内核的调度策略可能会优先选择同一进程中的线程,而不是不同进程中的线程。

二、线程管理函数

Pthread并发编程
Pthread库提供了用于线程管理的以下APT。

pthread_create(thread, attr, function, arg): create thread
pthread_exit(status):terminate thread
pthread_cancel(thread) : cancel thread
pthread_attr_init(attr) : initialize thread attributes
pthread_attr_destroy(attr): destroy thread attribute

使用pthread_ create()函数创建线程。int pthread_create (pthread_t pthread_id,pthread_attr_t•attr,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) ,attr参数使用:
定义一个pthread展性变址pt:hread_attr_tattr
pthread_attr_init(&attr)初始化屈性变掀。
设置属性变垃并在pthread_ create()调用中使用。
必要时,通过pthread_attr_destroy(&attr)释放attr资源。
线程ID 是一种不透明的数据类型,取决于实现悄况。因此,不应该直接比较线程ID。如果需要,可以使用pthread_ equal()函数对它们进行比较。
int pthread_equal (pthread_t tl, pthread_t t2);
线程函数结束后,线程即终止。或者,线程可以调用函数 int pthraad_axit {void *status)
一个线程可以等待另一个线程的终止, 通过:int pthread_join (pthread_t thread, void **status__ptr);终止线程的退出状态以status_ptr返回。
在 Pthread中,锁被称为互斥量,意思是相互排斥。互斥变呈是用 ptbread_mutex_t 类型声明的在使,用之前必须对它们进行初始化。有两种方法可以初始化互斥址。
静态方法,pthreaa—mutex_t m = PTHREAD_MUTEX_INITIALIZER;定义互斥量m,并使用默认属性对其进行初始化。
动态方法,使用 pthread_ mutex _init() 函数

三、死锁预防

预防死锁
通过破坏产生死锁的四个必要条件来预防死锁,
但因互斥条件是必须的,所以不能破坏该条件。

预防死锁-破坏“请求和保持”条件
为了破坏该条件,OS需要保证:
当进程请求资源时,不可持有不可抢占资源。
可通过两个协议实现:

第一种协议
进程在开始运行前,一次性申请整个运行过程中所需的全部资源。
缺点:
资源严重浪费。
进程进程出现饥饿现象。
第二种协议
进程在开始运行前,仅请求初期所需资源,运行时逐步释放不再需要的资源,并请求新的所需资源。

预防死锁-破坏“不可抢占”条件
保持了不可抢占资源的进程,提出新资源申请,但不被满足时,释放所有已得到的资源。
实现复杂,且释放已有资源很可能付出很大代价。
预防死锁-破坏“循环等待”条件
对系统所有资源类型进行排序,并赋予不同序号,进程在请求资源时,必须按序号递增顺序请求资源。如果一个拥有高序号资源的进程,请求低序号资源,则需要先释放高序号资源,再请求低序号资源。
资源利用率与吞吐量相较前两策略改善不少。

缺点:
新设备的增加被限制。
资源标号困难。
限制用户编程思路。

避免死锁
在资源动态分配过程中,防止系统进入不安全状态,限制弱,但成本低。
避免死锁-系统安全状态
死锁避免中,系统状态被划分成安全状态与不安全状态,处于不安全状态时,系统可能进入死锁。
允许进程动态申请资源,但OS进行分配资源前,应先评估资源分配安全性,仅安全状态下可分配。

安全状态,是指OS能按某进程推进顺序为各进程分配资源(包括释放资源),满足各进程对资源的最大需求。
安全状态下不会出现死锁。
安全状态的例子见P119,很简单的一个例子。
避免死锁-利用银行家算法避免死锁
由Dijkstra的银行家算法是一个非常有代表性的避免死锁算法。
为实现银行家算法,每个新进程在进入系统时,先申明各所需资源的最大数目。
OS分配资源时,先确认有足够资源分配给该进程,再确认分配资源后是否会进入不安全状态。
银行家算法的数据结构
Available[]:可利用资源向量,包含m个元素的数组,表示系统中该类资源的数目。

Max[][]:nm矩阵,n个进程对m个资源的最大需求。
Allocation[][]:nm矩阵,n个进程已获得m个资源的数量。
Need[][]:n*m矩阵,n个进程所需的m个资源的数量。

关系:Need[i, j] = Max[i, j] - Allocation[i, j]
书本中的Need等二维向量,仅用一对[],但为了区分,变量名中我使用两对[]。
银行家算法
Request是进程p的请求向量,
Request[j]=k表示当前p进程对j资源需要k个数量。
如无特别说明,带序号的步骤为顺序步骤。
Request[][]<=Need[][],如果大于,则认为出错,因为超过了它原先宣布的最大值。
Request[][]<=Available[],如果大于,则等待。
将数据结构中各数据修改成分配资源后的值。
执行安全性算法,若安全,则分配数据,若不安全,则本次分配作废,进程等待。
安全性算法
设置两个临时变量Work[]=Available[]、Finish[]=false,分别表示当前可用资源数目、是否已经安全分配资源。
从进程集合中找到一进程i满足:Finish[i]false,并且Need[i, j]<Work[j]的进程,若找到,进入3,否则进入4.
设置Work[j]+=Available[i, j],Finish[i]=true,即分配完资源给进程,进程结束后释放资源,Work增加,安全分配,Finish置真。
步骤3结束后,跳回步骤2.
所有进程Finish[]true,是则表示处于安全状态,不是则不安全。

问题和解决思路

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

#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 *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 () ;
}
这篇关于第四章学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!