第四章 并发编程

并行计算

要求解某个问题，先要设计一种算法，描述如何一步步地解决问题，然后用计算机程序以串行指令流的形式实现该算法。在只有一个 CPU的情况下，每次只能按顺序执行某算法的一个指令和步骤。但是，基于分治原则(如二又树查找和快速排序等)的算法经常表现出高度的并行性，可通过使用并行或并发执行来提高计算速度。并行计算是一种计算方案，它尝试使用多个执行并行算法的处理器更快速地解决问题。

• 顺序算法与并行算法
  
  begin-end代码块中的顺序算法可能包含多个步骤。

• 并行性与并发性

  • 在理想情况下，并行算法中的所有任务都应该同时实时执行。
  • 真正的并行执行只能在有多个处理组件的系统中实现，比如多处理器或多核系统。
  • 在单CPU系统中，一次只能执行一个任务。在这种情况下，不同的任务只能并发执行，即在逻辑上并行执行。

线程

• 线程的原理

  • 线程是某进程同一地址空间上的独立执行单元。创建某个进程就是在一个唯一地址空间创建一个主线程。当某进程开始时，就会执行该进程的主线程。

• 线程的优点

  • 线程创建和切换速度更快

  • 线程的响应速度更快

  • 线程更适合并行运算

• 线程的缺点

  • 由于地址空间共享，线程需要来自用户的明确同步。

  • 许多库函数可能对线程不安全。通常，任何使用全局变量或依赖于静态内存内容的函数，线程都不安全。

  • 在单CPU系统上，使用线程解决问题实际上要比使用顺序程序慢。

线程操作

• 线程的执行轨迹与进程类似。线程可在内核模式或用户模式下执行。在用户模式下，线程在进程的相同地址空间中执行，但每个线程都有自己的执行堆栈。

线程管理函数

• 创建线程

  • 使用pthread_create()

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

  • attr 参数的使用步骤。
    (1)定义一个pthread属性变量pthread attr tattr。
    (2)用pthread attrinit (&attr)初始化属性变量。
    (3)设置属性变量并在pthread create0)调用中使用。
    (4)必要时，通过pthread attr destroy (&attr)释放attr 资源。

• 线程ID

  int pthread_equal(pthread_t t1,pthread_t t2);
  

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

• 线程终止

  int pthread_exit(void *status)；
  

  进行显式终止，其中状态是线程的退出状态。

• 线程连接

  int pthread_join(pthread_t thread,void **status_ptr)
  

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

线程示例程序

• 用线程计算矩阵的和

  #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 threads\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);
  }
  

• 用线程快速排序

  #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()	
  {
      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;
      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();
  }
  

线程同步

多个线程试图修改同一共享变量或数据结构时，如果修改结果取决于线程的执行顺序，则称之为竞态条件。在并发程序中，绝不能有竞态条件。否则，结果可能不一致。

• 互斥量

  • 最简单的同步工具是锁，它允许执行实体仅在有锁的情况下才能继续执行。在 Pthread中，锁被称为互斥量，意思是相互排斥。

  • 静态方法

  • 动态方法

• 死锁预防

  • 互斥量使用封锁协议。

  • 在任何封锁协议中，误用加锁可能会产生一些问题。

  • 死锁是一个状态，在这种状态下，许多执行实体相互等待，无法继续进行下去

• 条件变量

  • 静态方法

  • 动态方法

• 生产者-消费者问题
  共享全局变量：

  int buf[NBUF];
  int head,tail;
  int data;
  

• 信号量

  • 信号量是进程同步的一般机制。

  • 在使用信号量之前，必须使用一个初始值和一个空等待队列进行初始化。

• 屏障

  • 在 Pthreads中，可以采用的机制是屏障以及一系列屏障函数。

• 用并发线程解线性方程组

• Linux中的线程

  • Linux不区分进程和线程。

  • 对于Linux内核，线程只是一个与其他进程共享某些资源的进程。

  • 在 Linux 中，进程和线程都是由 clone（）系统调用创建的：

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

苏格拉底挑战

关于线程的苏格拉底挑战

关于线程同步的苏格拉底挑战

遇到的问题

问题：线程中，线程调度是如何进行的？
解决方法：问gpt
GPT的回答：