一、知识点归纳
1. 并发计算导论
在早期,大多数计算机只有一个处理组件,称为处理器或中央处理器(CPU)。受这种硬件条件的限制,计算机程序通常是为串行计算编写的。要求解某个问题,先要设计一种算法,描述如何一步步地解决问题,然后用计算机程序以串行指令流的形式实现该算法。在只有一个CPU的情况下,每次只能按顺序执行某算法的一个指令和步骤。但是,基于分治原则(如二叉树查找和快速排序等)的算法经常表现出高度的并行性,可通过使用并行或并发执行来提高计算速度。并行计算是一种计算方案,它尝试使用多个执行并行算法的处理器更快速地解决问题。过去,由于并行计算对计算资源的大量需求,普通程序员很少能进行并行计算。近年来,随着多核处理器的出现,大多数操作系统(如Linux)都支持对称多处理(SMP)。甚至对于普通程序员来说,并行计算也已经成为现实。显然,计算的未来发展方向是并行计算。
1.1顺序算法与并行算法
在描述顺序算法时,常用的方法是用一个begin-end代码块列出算法。begin-end代码块中的顺序算法可能包含多个步骤。所有步骤都是通过单个任务依次执行的,每次执行一个步骤。当所有步骤执行完成时,算法结束。
相反, 并行算法的描述使用cobegin-coend代码块来指定并行算法的独立任务。在cobegin-coend块中,所有任务都是并行执行的,紧接着cobegin-coend代码块的下一个步骤将只在所有这些任务完成之后执行。
1.2并行性与并发性
通常,并行算法只识别可并行执行的任务,但是它没有规定如何将任务映射到处理组件。在理想情况下,并行算法中的所有任务都应该同时实时执行。然而,真正的并行执行只能在有多个处理组件的系统中实现,比如多处理器或多核系统。在单CPU系统中,一次只能执行一个任务。在这种情况下,不同的任务只能并发执行,即在逻辑上并行执行。在单CPU系统中,并发性是通过多任务处理来实现的。
2. 线程
2.1线程的原理
一个操作系统(OS)包含许多并发进程。在进程模型中,进程是独立的执行单元。所有进程均在内核模式或用户模式下执行。在内核模式下,各进程在唯一地址空间上执行,与其他进程是分开的。虽然每个进程都是一个独立的单元,但是它只有一个执行路径。当某进程必须等待某事件时,例如I/O完成事件,它就会暂停,整个进程会停止执行。线程是某进程同一地址空间上的独立执行单元。创建某个进程就是在一个唯一地址空间创建一个主线程。当某进程开始时,就会执行该进程的主线程。如果只有一个主线程,那么进程和线程实际上并没有区别。但是,主线程可能会创建其他线程。每个线程又可以创建更多的线程等。某进程的所有线程都在该进程的相同地址空间中执行,但每个线程都是一个独立的执行单元。在线程模型中,如果一个线程被挂起,其他线程可以继续执行。除了共享共同的地址空间之外,线程还共享进程的许多其他资源,如用户id、打开的文件描述符和信号等。打个简单的比方,进程是一个有房屋管理员(主线程)的房子,线程是住在进程房子里的人。房子里的每个人都可以独立做自己的事情,但是他们会共用一些公用设施,比如同一个信箱、厨房和浴室等。过去,大多数计算机供应商都是在自己的专有操作系统中支持线程。不同系统之间的实现有极大的区别。目前,几乎所有的操作系统都支持Pthread,它是IEEE POSIX 1003.1c的线程标准(POSIX 1995)。
2.2线程的优点
- 线程创建和切换速度更快
- 线程的响应速度更快
- 线程更适合并行计算
2.3线程的缺点
- 由于地址空间共享,线程需要来自用户的明确同步。
- 许多库函数可能对线程不安全,例如传统的strtok()函数将一个字符串分成一连串令牌。通常,任何使用全局变量或依赖于静态内存内容的函数都是线程不安全的。为了使库函数适应线程环境,还需要做大量的工作。
- 在单CPU系统上,使用线程解决问题实际上要比使用顺序程序慢,这是由于在运行时创建线程和切换上下文的系统开销造成的。
3. 线程操作
线程的执行轨迹与进程类似。线程可在内核模式或用户模式下执行。在用户模式下,线程在进程的相同地址空间中执行,但每个线程都有自己的执行堆栈。线程是独立的执行单元,可根据操作系统内核的调度策略,对内核进行系统调用,变为挂起、激活以继续执行等。为了利用线程的共享地址空间,操作系统内核的调度策略可能会优先选择同一进程中的线程,而不是不同进程中的线程。
4. 线程管理函数
Pthread库提供了用于线程管理的以下API:
pthread_create(thread, attr, function, arg)
: 创建线程pthread_exit(status)
: 终止线程pthread_cancel(thread)
: 取消线程pthread_attr_init(attr)
: 初始化线程属性pthread_attr_destroy(attr)
: 销毁线程属性
4.1创建线程
使用pthread_create()函数创建线程:
int pthread_create(pthread_t *pthread_id, pthread_attr_t *attr, void *(*func)(void *), void *arg);
如果成功则返回0,如果失败则返回错误代码。pthread_create()函数的参数为:
pthread_id
是指向pthread_t类型变量的指针,用于存储线程的ID。attr
是指向线程属性的指针,可以为NULL表示使用默认属性。func
是要执行的新线程函数的入口地址。arg
是指向线程函数参数的指针。
线程属性参数attr
最复杂,可以使用pthread_attr_init()函数进行初始化,并设置属性,最后通过pthread_attr_destroy()函数释放资源。通常情况下,可以使用NULL作为属性参数,以使用默认属性。
4.2线程ID
线程ID是一种不透明的数据类型,取决于实现情况,因此不应该直接比较线程ID。如果需要比较线程ID,可以使用pthread_equal()函数进行比较:
int pthread_equal(pthread_t t1, pthread_t t2);
如果是不同的线程,则返回0,否则返回非0。
4.3线程终止
线程函数结束后,线程即终止,或者线程可以调用pthread_exit()函数进行显式终止,其中状态是线程的退出状态。通常,0表示正常终止,非0值表示异常终止。
4.4线程连接
一个线程可以等待另一个线程的终止,通过pthread_join()函数进行连接,同时终止线程的退出状态以status_ptr返回。
5. 线程同步
由于线程在进程的同一地址空间中执行,它们共享同一地址空间中的所有全局变量和数据结构。当多个线程试图修改同一共享变量或数据结构时,如果修改结果取决于线程的执行顺序,则称之为竞态条件。在并发程序中,绝不能有竞态条件,否则结果可能不一致。除了连接操作之外,并发执行的线程通常需要相互协作。为了防止出现竞态条件并且支持线程协作,线程需要同步。通常,同步是一种机制和规则,用于确保共享数据对象的完整性和并发执行实体的协调性。它可以应用于内核模式下的进程,也可以应用于用户模式下的线程。
5.1互斥量
互斥量是最简单的同步工具,它允许执行实体仅在有锁的情况下才能继续执行。在Pthread中,互斥量被称为“互斥量”,意思是相互排斥。互斥变量是用pthread_mutex_t类型声明的,在使用之前必须对它们进行初始化。互斥量可以通过静态方法或动态方法进行初始化。
5.2死锁预防
死锁是一种状态,在这种状态下,许多执行实体相互等待,因此都无法继续下去。有多种方法可以解决可能的死锁问题,其中包括死锁预防、死锁规避、死锁检测和恢复等。在实际系统中,唯一可行的方法是死锁预防,试图在设计并行算法时防止死锁的发生。
5.3条件变量
条件变量提供了一种线程协作的方法。在Pthread中,使用类型pthread_cond_t来声明条件变量,必须在使用前进行初始化。条件变量可以通过静态方法或动态方法进行初始化。
5.4屏障
屏障允许一组线程等待彼此达到某个同步点,然后一起继续执行。屏障可以用来控制线程的并行性,确保某些操作在所有线程都准备好之后才执行。在Pthreads中,可以使用pthread_barrier_t来创建和使用屏障。
创建屏障步骤:
- 主线程创建一个屏障对象pthread_barrier_t barrier;
- 调用pthread_barrier_init(&barrier NULL, nthreads);,用屏障中同步的线程数字对它进行初始化
- 工作线程使用pthread_barrier_wait(&barrier)在屏障中等待指定数量的线程到达屏障
二、ChatGpt提问
三、实践及代码托管
用线程快速排序
代码已托管至gitee,链接:https://gitee.com/wang-yuxuan333/123.git
具体详见线程快速排序.txt
四、问题及解决
代码中使用的qsort函数,已经被C标准库中的 qsort 函数占用,询问ChatGpt后得知,修改函数名,最终编译成功。