学习笔记7

并发编程和并行计算是计算机科学领域的重要概念，它们充分利用多核处理器和多处理器系统的潜力，加速计算任务的执行。下面详细探讨这些主题：

并发编程和并行计算

并行计算基于分治原则，允许任务在同时执行，从而提高了计算速度。传统的顺序算法依次执行每个步骤，而在并行算法中，多个任务可以在同时执行。

在并行算法中，通常使用cobegin和coend块来表示多个任务的并行执行。所有这些任务都可以同时执行，但要在正确的时机进行同步，以确保计算的正确性。这种并行性在多处理器或多核系统中可以实现，因为这些系统具有多个处理组件。

与并行性不同，并发性是通过多任务处理来实现的。在单CPU系统中，一次只能执行一个任务。线程是实现并发性的关键概念。

线程原理

线程是某个进程中的独立执行单元，与进程共享同一地址空间。主线程在进程启动时创建，然后可以创建其他线程。所有这些线程都在相同的地址空间中执行，但是它们是独立的执行单元。这意味着如果一个线程被挂起，其他线程可以继续执行。

线程的优点包括创建和切换速度更快，响应速度更快，更适合并行计算。但也有一些缺点，如需要明确的同步、某些库函数可能不安全，以及在单CPU系统上可能会比顺序程序慢。

线程操作

线程管理函数

• 创建函数：pthread_create()用于创建线程。

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

  这个函数返回0表示成功，返回错误代码表示失败。pthread_id是指向pthread_t类型的指针，attr是指向线程属性的指针。

• 线程ID：pthread_equal()函数用于比较两个线程是否相同。

• 线程终止：线程可以通过pthread_exit()来显式终止。

• 线程连接：pthread_join()函数用于等待一个线程的终止并获取其返回值。

同步工具

1. 互斥量：互斥量是一种线程同步机制，用于避免多个线程同时访问共享资源。pthread_mutex_lock()和pthread_mutex_unlock()函数用于加锁和解锁互斥量。

2. 条件变量：条件变量允许线程等待某个条件的发生。pthread_cond_wait()和pthread_cond_signal()函数用于等待和通知条件的变化。

3. 屏障：屏障用于同步多个线程，让它们在达到某个点时等待彼此。pthread_barrier_init()和pthread_barrier_wait()函数用于初始化和等待屏障。

在并发编程中，这些线程管理函数和同步工具非常重要，因为它们有助于确保线程之间的正确协同工作。

总结，并发编程和并行计算是为了提高计算效率而使用的关键技术。线程是实现并发性的基本单位，通过适当的同步机制，可以实现多线程程序的正确性。同时，了解线程管理函数和同步工具也是非常重要的，它们帮助确保线程之间的协同工作。

线程同步与互斥量

在线程编程中，线程同步是确保多个线程按照某种顺序执行以维护数据完整性的关键。最简单的同步工具是锁，也称为互斥量。它允许执行实体（通常是线程）在有锁的情况下才能继续执行。以下是互斥量的基本用法：

初始化互斥量

互斥量可以以静态或动态方式初始化：

1. 静态初始化：

   pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
   

2. 动态初始化：

   pthread_mutex_t m;
   pthread_mutex_init(&m, NULL);
   

使用互斥量

互斥量的常见操作包括：

• pthread_mutex_lock(m)：获得锁，如果锁已经被其他线程获取，线程将被阻塞。
• pthread_mutex_unlock(m)：释放锁。
• pthread_mutex_trylock(m)：尝试获得锁，如果锁已经被其他线程获取，它不会阻塞，而是返回一个错误码。
• pthread_mutex_destroy(m)：销毁互斥量。

互斥量非常有用，特别是在处理共享数据时，以确保多个线程不会同时修改数据，从而避免数据不一致性问题。

防止死锁

死锁是一种情况，其中两个或多个线程互相等待对方释放资源，导致它们都无法继续执行。为了避免死锁，通常使用以下策略：

• 互斥量封锁协议：在获取多个互斥量时，按固定的顺序获取和释放，以避免循环等待。

while(1) {
   lock(m1);
   if (!trylock(m2))
      unlock(m1);
   else
       break;
}

• 条件变量：条件变量允许线程等待某个条件的发生，以减少忙等待，从而减少死锁的风险。

条件变量

条件变量通常用于线程之间的通信。初始化条件变量可以采用以下方式：

• 静态初始化：

  pthread_cond_t con = PTHREAD_COND_INITIALIZER;
  

• 动态初始化：

  pthread_mutex_t con_mutex;
  pthread_cond_t con;
  pthread_mutex_init(&con_mutex, NULL);
  pthread_cond_init(&con, NULL);
  

条件变量可以与互斥量结合使用，以在某些条件下等待或唤醒线程。

信号量

信号量是一种通用的同步机制，通常用于进程间同步，但也可以在线程中使用。信号量是一种数据结构，用于计数。

与条件变量相比，信号量的优点在于它可以控制允许进入临界区的线程数量，而不仅仅是等待某个条件的线程。

以上是关于线程同步、互斥量、条件变量和信号量的概述，这些工具非常重要，以确保多线程程序的正确性和性能。要避免死锁，必须小心谨慎地设计同步策略。

用线程快速排序

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 10
typedef struct{
int upperbound;
int lowerbound;
}PARM;

int A[N]={5,1,6,4,7,2,9,8,0,3};

int print()	// print current a[] contents
{
int i;
printf("[ ");
for (i=0; i<N; i++)
{
printf("%d ", A[i]);
}
printf("]\n");
}

void *qsort_1(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]; 
left = lowerbound - 1; 
right = upperbound;
if (lowerbound >= upperbound) 
pthread_exit(NULL);

while (left < right) 
{
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; 
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, qsort_1, (void *)&aleft);
pthread_create(&rightThread, NULL, qsort_1, (void *)&aright);// wait for left and right threads 
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_1, (void *)&arg); // wait for QS thread to finish 
pthread_join(thread, NULL);
printf("main %lu sorted array = ", me); 
print();
}

苏格拉底挑战