精华内容
下载资源
问答
  • 并行程序的必要性
    千次阅读
    2015-04-03 01:11:26

    3.1
    在问候程序中,如果strlen(greeting)代替strlen(greeting)+1来计算进程1、2、…、comm_sz-1发送消息的长度,会发生什么情况?如果用MAX_STRING代替strlen(greeting)+1又会是什么结果?你可以解释这些结果吗?

    解答:
    ①这样的替换并不影响显示,不过传递的是两个不大一样的字符串。
    【引用 58页】在我们的程序,参数msg_size是消息字符串加上C语言中字符串结束符\0所占的字符数量。参数msg_type的值是MPI_CHAR。这两个参数一起告知系统整个消息有strlen(geeting)+1个字符。
    ②这个问题与上面的问题完全相反。这里MAX_STRING是绝对大于strlen(greeting)+1的,所以传递过去的字符数量会是MAX_STRING,会将接收区的缓存占满。不过,对于打印输出来说,并没有什么影响。

    3.2
    改变梯形积分法,使其能够在comm_sz无法被n整除的情况下,正确估算积分值(假设n≥comm_sz)

    解答:

    #include <stdio.h>
    #include <mpi.h>
    
    double f(double x){
      return x*x;
    }
    
    double Trap(
      double left_endpt,   /*  in  */
      double right_endpt,  /*  in  */
      int trap_count,      /*  in  */
      double base_len      /*  in  */
      ){
      double estimate, x;
      int i;
    
      estimate = (f(left_endpt) + f(right_endpt))/2.0;
      for (i = 0; i < trap_count - 1; i++){
        x = left_endpt + (i + 1) * base_len;
        estimate += f(x);
      }
      return estimate * base_len;
    }
    
    int main(){
      int my_rank, comm_sz, n = 64, local_n;
      double a = 0.0, b = 3.0, h, local_a, local_b, remain = 0.0;
      double local_int, total_int;
      int source;
    
      MPI_Init(NULL, NULL);
      MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
      MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
    
      //Get_data(my_rank, comm_sz, &a, &b, &n);
    
      h = (b - a)/n; //h is the same for all processes
    
      local_n = n/comm_sz; // So is the number of trapezoids
    
      local_a = a + my_rank * local_n * h;
      local_b = local_a + local_n * h;
      local_int = Trap(local_a, local_b, local_n, h);
    
    
    
      if (my_rank != 0){
        MPI_Send(&local_int, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
      } else {
    
        total_int =local_int;
        for (source = 1; source < (comm_sz); source++){
          MPI_Recv(&local_int, 1, MPI_DOUBLE, source, 0, MPI_COMM_WORLD,
                   MPI_STATUS_IGNORE);
          total_int += local_int;
        }
    
        // 这里是因为有一些矩阵没有计算到,所以,非整除的情况下结果会有比较大的缺失。
        // 这里将这些矩形在0号线程上补上。
        if (n%comm_sz){
          remain = Trap(h * local_n * comm_sz, b, n%comm_sz, h);
        }
        
        total_int += remain;
      }
    
      if (my_rank == 0){
        printf("With n = %d trapezoids, our estimate\n", n);
        printf("of the integral from %f to %f = %.15e\n", a, b, total_int);
      }
    
      MPI_Finalize();
      return 0;
    }
    
    

    3.3
    梯形积分法程序中那些变量是局部的,那些是全局的?

    解答:
    【引用63页】注意,我们对标识符的选择,是为了区分局部变量与全局变量。局部变量只在使用它们的进程内有效。梯形积分法程序中的例子有:local_a,local_b和local_n。如果变量在所有进程中都有效,那么该变量就称为全局变量。该程序中的例子有:变量a,b和n。这与你在编程导论课上学到的用法不同。在编程导论课上,局部变量是指单个函数的私有变量,而全局变量是指所有函数都可以访问的变量。

    3.4
    mpi_output.c程序中,每个进程只打印一行输出。修改程序,使程序能够按进程号的顺序打印,即,进程0先输出,然后进程1,一次类推。

    解答:
    其实这里的实现和3.1中的问候程序差不多。

    #include <stdio.h>
    #include <string.h>
    #include <mpi.h>
    
    int main(){
      int my_rank, comm_sz, q;
      char message[100];
    
      MPI_Init(NULL, NULL);
      MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
      MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
    
      //printf("Proc %d of %d > Does anyone have a toothpick?\n", my_rank, comm_sz);
    
      if (my_rank != 0){
        sprintf(message, "Proc %d of %d > Does anyone have a toothpick?", my_rank, comm_sz);
        MPI_Send(message, strlen(message)+1, MPI_CHAR, 0, 0, MPI_COMM_WORLD);
      } else {
        printf("Proc %d of %d > Does anyone have a toothpick??\n", my_rank, comm_sz);
        for(q = 1; q < comm_sz; q++){
          MPI_Recv(message, 100, MPI_CHAR, q, 0,MPI_COMM_WORLD, MPI_STATUS_IGNORE);
          printf("%s\n", message);
        }
      }
    
      MPI_Finalize();
      return 0;
    }
    

    3.5
    二叉树中有着从根到每个节点的最短路径,这条路径的长度称为该节点的深度。每个非叶子节点结点都有2个子节点深度都相同的满二叉树称为完全二叉树。用数学推导证明:如果T是一颗有着n个叶子节点的完全二叉树,那么叶子节点的深度为log(n)【底为2】

    解答:
    当n=1 => 0=log(1)时显然。
    假设当T具有n个叶子结点时的完全二叉树的深度为log(2),则
    当n=2k(以及2(k+1),…,2(k+p))时,由归纳假设知前2k个结点构成深度为log(n)的树,再由完全二叉树的定义知剩余的1(或2,…,2^k)个结点均填在第log(n)-1层上,故深度刚好增加了1。
    故n<=2^(k+1)时命题成立。证毕。
    (首先最好能先从直观上理解:完全二叉树中:
    1层 有1个叶子结点;
    2层 有2个叶子结点;
    3层 有4个叶子结点;
    ……
    k层 有2^(k-1)个叶子结点;)

    3.6
    假设comm_sz=4,x是一个拥有n=14个元素的向量
    a 如何用块划分法在一个程序的进程间分发x的元素
    b 如何用循环划分法在一个程序的进程间分发x的元素
    c 如何用b=2大小的块用块-循环划分法在一个程序的进程间分发x的值
    你的分配方法应该通用性足够强,无论comm_sz和n取何值都能分配。你应该使你的分配“公正”,如果q和r是任意的2个进程,分给q和r的x分量个数的差应尽可能小。

    解答:
    a 块划分

    进程0  | 0  1  2  3
    进程1  | 4  5  6  7
    进程2  | 8  9  10 11
    进程3  | 12 13
    

    b 循环划分

    进程0  | 0  4  8  12
    进程1  | 1  5  9  13
    进程2  | 2  6  10
    进程3  | 3  7  11
    

    c 块-循环划分

    进程0  | 0  1  8  9  
    进程1  | 2  3  10 11  
    进程2  | 4  5  12 13
    进程3  | 6  7
    

    3.7
    如果通信子只包含一个进程,不同的MPI集合通信函数分别会做什么。

    解答:
    这个验证起来很简单,就是将书中的程序,使用mpicc编译后,直接运行二进制文件就行了。
    可以看到的是,所有的操作就相当于这个进程发送信息给自己,然后完成对应的操作。
    个人感觉,当只有一个进程存在在通信子中时,就没有必要使用MPI来进行通讯了。

    3.8
    假定comm_sz=8, n=16
    a 画一张图来说明进程0要分发n个元素的数组,怎样使用拥有comm_sz个进程的树形结构的通信来实现MPI_Scatter。
    b 画一张图来说明原先分布在comm_sz个进程间的n个数组元素由进程0保存,怎样使用树形结构的通信来实现MPI_Gather.

    解答:
    这里个人感觉在细看一下73和74页的内容,就能知道这两个函数,是如何进行分配的了。
    至于这里说的树形结构,个人没弄明白是怎么样的一个图。

    3.9
    编写一个MPI程序实现向量与标量相乘以及向量点积的功能。用户需要输入2个向量和1个标量,都有进程0读入并分配给其他进程,计算结果由进程0计算和保存,并最终由进程0打印出来。假定向量的秩n可以被comm_sz整除。

    解答:

    #include <stdio.h>
    #include <stdlib.h>
    #include <mpi.h>
    
    #define N 4
    
    void Read_vector(
      double vector_a[],
      double vector_b[],
      double *scalar,
      int local_n,
      int n,
      int my_rank,
      MPI_Comm comm){
    
      double va[N], vb[N];
      int i;
    
      if (my_rank == 0){
        printf("Enter the vector_a:\n");
        for (i = 0; i < n; i++){
          scanf("%lf", &va[i]);
        }
    
        printf("Enter the vector_b:\n");
        for (i = 0; i < n; i++){
          scanf("%lf", &vb[i]);
        }
    
        printf("Enter the scalar:\n");
        scanf("%lf", scalar);
    
        MPI_Scatter(va, local_n, MPI_DOUBLE, vector_a, local_n, MPI_DOUBLE, 0, comm);
        MPI_Scatter(vb, local_n, MPI_DOUBLE, vector_b, local_n, MPI_DOUBLE, 0, comm);
      } else {
        MPI_Scatter(va, local_n, MPI_DOUBLE, vector_a, local_n, MPI_DOUBLE, 0, comm);
        MPI_Scatter(vb, local_n, MPI_DOUBLE, vector_b, local_n, MPI_DOUBLE, 0, comm);
      }
    }
    
    
    void vect_mult(
      double vector_a[],
      double vector_b[],
      double scalar,
      double v1_v2_buf[],
      double v1_s_buf[],
      double v2_s_buf[],
      int local_n,
      int n,
      MPI_Comm comm){
    
      double va[N], vb[N];
      int i;
    
      MPI_Allgather(vector_a, local_n, MPI_DOUBLE, va, local_n, MPI_DOUBLE, comm);
      MPI_Allgather(vector_b, local_n, MPI_DOUBLE, vb, local_n, MPI_DOUBLE, comm);
    
      for (i = 0; i < n; i++){
        v1_v2_buf[i] += va[i] * vb[i];
        v1_s_buf[i] += va[i] * scalar;
        v2_s_buf[i] += vb[i] * scalar;
      }
    }
    
    int main(){
      int my_rank, comm_sz, n = N, local_n;
      double vector1[N] = {0}, vector2[N] = {0}, scalar = 0.0, v1_v2 = 0.0;
      double v1_v2_buffer[N], v1_s_buffer[N], v2_s_buffer[N];
    
      MPI_Init(NULL, NULL);
      MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
      MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
    
      local_n = n / comm_sz;
    
      Read_vector(vector1, vector2, &scalar, local_n, n, my_rank, MPI_COMM_WORLD);
    
      vect_mult(vector1, vector2, scalar, v1_v2_buffer, v1_s_buffer, v2_s_buffer, local_n, n, my_rank, MPI_COMM_WORLD);
    
      int i = 0;
      if (my_rank == 0){
    #if 0
    // just for debug
        printf("\nvector1 is :\n");
        for (i = 0; i < n; i++){
          printf("%g, ", vector1[i]);
        }
    
        printf("\nvector2 is :\n");
        for (i = 0; i < n; i++){
          printf("%g, ", vector2[i]);
        }
    
        printf("\nscalar is %g\n", scalar);
    
        for(i = 0; i < n; i++){
          printf("v1_v2_buffer[%d] is %g\n", i, v1_v2_buffer[i]);
          v1_v2 += v1_v2_buffer[i];
        }
    #endif
        printf("\nvector1 * vector2 is %lf.\n", v1_v2);
    
        printf("\nvector1 * scalar:\n");
        for (i = 0; i < n; i++){
          printf("%lf ", v1_s_buffer[i]);
        }
    
        printf("\n\nvector2 * scalar:\n");
        for (i = 0; i < n; i++){
          printf("%lf ", v2_s_buffer[i]);
        }
    
        printf("\n");
      }
    
      MPI_Finalize();
    
      return 0;
    }
    
    

    3.11
    求n个数和的表达式:x0+x1+…+x[n-1]
    这n个数值的前缀和是n个部分和:x0, x0+x1, x0+x1+x2,…, x0+x1+…+x[n-1]
    求前缀和事实上是求数值总和的一般化,它不只求出n个值的总和。
    a. 设计一个串行算法来计算n个元素的前缀和。
    b. 在有n个进程的系统和说那个并行化(a)小题中设计的串行程序,每个程序存储一个x_i值。
    c. 设n=2^k, k为正整数。设计一个串行算法,然后将该算法并行化,使得这个并行算法仅需要k个通讯阶段。
    d. MPI提供一个集合通信函数MPI_Scan,用来计算前缀和。该函数对有count个元素的数组进行操作,sendbuf_p和recvbuf_p都应该指向有count个datatype类型元素的数据块。op参数和MPI_Reduce中的op一样。编写一个MPI程序使每个MPI进程生成有count个元素的随机数数组,计算其前缀和并打印结果。

    解答:
    a

    for (int i = 1; i < n; i++){
      a[i] += a[i - 1];
    }
    

    b

    //如何将x值分发到每个线程上就不写了
    //这里my_rank是进程号,假设my_rank号线程就是x[my_rank]
    for (int i = 0; i < my_rank;i++){
      x_my_rank += x[i];
    }
    

    c
    有k次的串行稍稍绕一点,开始以为是k次循环,后来是k个循环。
    下面下一个n为8的情况

    for(int i = 1; i < n; i += 2){
      x[i] += x[i - 1];
    }
    
    for(int i = 3; i < n; i += 4){
      x[i] += x[i - 2];
      x[i - 1] += x[i - 2];
    }
    
    for(int i = 7;i < n; i += 8){
      x[i] += x[i - 4];
      x[i - 1] += x[i - 4];
      x[i - 2] += x[i - 4];
      x[i - 3] += x[i - 4];
    }
    

    当然这里也可以用递归来写。

    使用MPI的话,一个for循环算作1次通讯,这样就满足了题目的条件。

    d.
    使用MPI_Scan并不容易,困扰了好几天。
    最后参考这里,并对原始代码进行修改,得到的如下代码。
    这里和题目中不大一样的就是每一个进程都只有1个元素的随机数组。
    这里暂时就不去纠结多个元素了。

    #include <stdio.h>
    #include <stdlib.h>
    #include <mpi.h>
    
    /* these variables are used by prefix sum also, hence here */
    
    int main(int argc, char **argv)
    {
      int i, num, psum, ksum, *arr, *input;
      int P, PID;
    
      MPI_Init(&argc, &argv);
      MPI_Comm_rank(MPI_COMM_WORLD, &PID);
      MPI_Comm_size(MPI_COMM_WORLD, &P);
    
      arr = (int*)malloc(P*sizeof(int));
    
      /* 0 creates input, sends */
      if (PID == 0) {
        srand(getpid());
        input = (int*)malloc(P*sizeof(int));
        printf("Input is:");
        for (i = 0; i < P; i++) {
          input[i] = rand()%10;
          printf(" %d", input[i]);
        }
        printf("\n");
      }
    
      MPI_Scatter(input, 1, MPI_INT, &num, 1, MPI_INT, 0, MPI_COMM_WORLD);
    
      /* prefix sum over all processes */
      MPI_Scan(&num, &psum, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);
      printf("%d: Scan: %d\n", PID, psum);
    
      free(arr);
    
      MPI_Finalize();
    
      exit(0);
    
    }
    /* prefix sum */
    
    

    3.12
    可以用环形传递来替代蝶形结构的全归约,在环形传递结构体中,如果有p个线程,每个进程q向进程q+1发送数据(进程p-1向进程0发送数据)。这一过程持续循环直至所有进程都获得理想的结果。我们可以用以下代码实现全归约:
    sum = temp_val = my_val;
    for (i=1;i < p; i++) {
    MPI_Sendrecv_replace(&temp_val, 1, MPI_INT, dest, sendtag, source, recvtag, comm, &status);
    sum += temp_val;
    }
    a. 编写一个MPIc恒旭实现这一算法。与蝶形结构的全归约相比,它的性能如何?
    b. 修改刚才的程序,实现前缀求和的运算。

    解答:
    A (1) 先来实现这个算法:(用c++实现)

    #include "mpi.h"
    
    #include <vector>
    #include <array>
    #include <iostream>
    
    int loop_pass(int argc, char* argv[])
    {
      int myid, numprocs, left, right;
    
      //MPI_Request request;
      MPI_Status status;
    
      std::vector<int> buffer{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    
      MPI_Init(&argc, &argv);
      MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
      MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    
      right = (myid + 1) % numprocs;
      left = myid - 1;
      if (left < 0) {
        left = numprocs - 1;
      }
    
      double start = MPI_Wtime();
      int temp = buffer.at(myid);
    
      for (int i = 1; i < numprocs; ++i) {
        MPI_Sendrecv_replace(
          &temp,
          1,
          MPI_INT,
          right, 1,
          left, 1,
          MPI_COMM_WORLD,
          &status);
        buffer[myid] += temp;
      }
      double end = MPI_Wtime();
    
      std::cout << "Thread ID[ " << myid << "] : " << buffer.at(myid) << std::endl;
    
      MPI_Finalize();
    
      if (myid == 0) {
        std::cout << "Runtime = " << end - start << std::endl;
      }
    
      return 0;
    }
    
    int main(int argc, char* argv[]) {
      loop_pass(argc, argv);
    }
    

    B

    #include "mpi.h"
    
    #include <vector>
    #include <array>
    #include <iostream>
    
    int loop_pass(int argc, char* argv[])
    {
      int myid, numprocs, left, right;
    
      //MPI_Request request;
      MPI_Status status;
    
      std::vector<int> buffer{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    
      MPI_Init(&argc, &argv);
      MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
      MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    
      right = (myid + 1) % numprocs;
      left = myid - 1;
      if (left < 0) {
        left = numprocs - 1;
      }
    
      double start = MPI_Wtime();
      int temp = buffer.at(myid);
    
      for (int i = 1; i < numprocs; ++i) {
        MPI_Sendrecv_replace(
          &temp,
          1,
          MPI_INT,
          right, 1,
          left, 1,
          MPI_COMM_WORLD,
          &status);
        if (myid >= i) {
          buffer[myid] += temp;
        }
      }
    
    
      double end = MPI_Wtime();
    
      std::cout << "Thread ID[ " << myid << "] : " << buffer.at(myid) << std::endl;
    
      MPI_Finalize();
    
      if (myid == 0) {
        std::cout << "Runtime = " << end - start << std::endl;
      }
    
      return 0;
    }
    
    int main(int argc, char* argv[]) {
      loop_pass(argc, argv);
    }
    

    (未完)

    更多相关内容
  • JAVA并行程序基础 学习笔记

    千次阅读 多人点赞 2021-03-13 09:08:24
    学习资料:《深入理解计算机系统》,《Java高并发程序设计》,《Java并发编程实战》,《Java并发编程的艺术》,《Java核心技术卷1》多线程一章,极客时间王宝令的Java并发编程实战课程… 以下大部分阐述来自上述书籍...

    学习资料:《深入理解计算机系统》,《Java高并发程序设计》,《Java并发编程实战》,《Java并发编程的艺术》,《Java核心技术卷1》多线程一章,极客时间王宝令的Java并发编程实战课程…

    以下大部分阐述来自上述书籍与课程中个人认为很重要的部分,也有部分心得体会,如有不准确的地方,欢迎评论区告诉我。后续还会更新并发包,并发算法等各种并发相关笔记,点点关注不迷路!ヽ(✿゚▽゚)ノ

    一.概念辨析

    1.进程 & 线程

    进程:操作系统对一个正在运行的程序的一种抽象。在一个系统上可以同时运行多个进程,而每个进程都好像在独占地使用硬件。(进程是线程的容器)
    而并发运行,则是说一个进程的指令和另一个进程的指令是交错执行的。这种机制叫做上下文切换。
    举例:当你双击一个exe程序时,这个.exe文件的指令就会被加载,那么你就能得到一个关于这个程序的进程。进程是活的,是正在被执行的,你可以通过任务管理器看到你电脑正在执行的进程。

    在这里插入图片描述

    线程:一个进程由将多个称为线程的执行单元组成,每个线程都运行在进程的上下文中,并共享同样的代码和全局数据。因为多线程之间比多进程之间更容易共享数据,也因为线程一般来说都比进程更高效。线程可以实现宏观上的“同时”执行,实际上是快速切换线程来达到几乎同时执行的效果。也可以称线程为轻量级进程,它是程序执行的最小单位。多核处理器中,同一个进程的不同线程也可以在不同的cpu上同时运行,此时就需要考虑通过锁,来保证操作的原子性。

    多进程与多线程的本质区别:每个进程都拥有自己的一整套变量,而线程则共享数据。多线程比多进程开销小得多。(当然也要看具体的操作系统,Windows和Linux是不同的,Windows开进程开销大,Linux开线程开销大,因此 Windows 多线程学习重点是要大量面对资源争抢与同步方面的问题,Linux 下的学习重点大家要学习进程间通讯的方法)

    2.同步 & 异步

    同步 Synchronous方法调用一旦开始,调用者必须等到方法调用返回后,才能继续后续的行为。

    异步 Asynchronous方法调用更像一个消息传递,一旦开始,方法调用就会立即返回,调用者就可以继续后续的操作。

    举例
    比如有一个计算圆周率小数点后 100 万位的方法pai1M(),这个方法可能需要执行俩礼拜,如果调用pai1M()之后,线程一直等着计算结果,等俩礼拜之后结果返回,就可以执行 printf(“hello world”)了,这个属于同步;如果调用pai1M()之后,线程不用等待计算结果,立刻就可以执行 printf(“hello world”),这个就属于异步。

    区别:同步就是要等到整个流程全部结束,而异步只是传递一个接下来要去做什么什么事情的消息,然后就会去干其他事。

    同步,是 Java 代码默认的处理方式。如果你想让你的程序支持异步,可以通过下面两种方式来实现:

    1.调用方创建一个子线程,在子线程中执行方法调用,这种调用我们称为异步调用;
    2.方法实现的时候,创建一个新的线程执行主要逻辑,主线程直接return,这种方法我们一般称为异步方法。

    3.并行 & 并发

    并行 Parallel:多个cpu实例或者多台机器同时执行一段处理逻辑,是真正的同时。

    并行二定律

    1.Amdahl定律 加速比=1/[F+(1-F)/n](n为处理器储量,F为并行比例) 由此可见,为了提高系统的速度,仅仅增加CPU处理器数量不一定能起到有效的作用。需要根本上修改程序的串行行为,提高系统内并行化的模块比重。

    2.Gustafson定律 加速比=n-F(n-1) 如果串行化比例很小,并行化比例很大,那么加速比就是处理起个数,只要不断累加处理起,就能获得更快的速度

    并发 ConCurrent:通过cpu调度算法,让用户看上去同时执行,实际上从cpu操作层面不是真正的同时。并发往往在场景中有公用的资源,那么针对这个公用的资源往往产生瓶颈,我们会用TPS或者QPS来反应这个系统的处理能力。

    总述
    并行就是同时进行,并发则是上下文快速切换(进程的运行不仅仅需要CPU,还需要很多其他资源,如内存,显卡,GPS,磁盘等等,统称为程序的执行环境,也就是程序上下文。)。单核处理器中,为了避免一个进程一直在使用CPU,调度器快速切换CPU给不同进程,于是在使用者看来程序是在同时运行,这就是并发,而实际上CPU在同一时刻只在运行一个进程。
    CPU进程无法同时刻共享,但是出现一定要共享CPU的需求呢?此时线程的概念就出现了。线程被包含在进程当中,进程的不同线程间共享CPU和程序上下文。(共享进程分配到的资源)单CPU进行进程调度的时候,需要读取上下文+执行程序+保存上下文,即进程切换。
    如果这个CPU是单核的话,那么在进程中的不同线程为了使用CPU核心,则会进行线程切换,但是由于共享了程序执行环境,这个线程切换比进程切换开销少了很多。在这里依然是并发,唯一核心同时刻只能执行一个线程。
    如果这个CPU是多核的话,那么进程中的不同线程可以使用不同核心,真正的并行出现了。

    4.死锁、饥饿、活锁

    死锁:所有线程互相占用了对方的锁,导致所有线程挂起。
    死锁四条件:
    1.互斥,共享资源 X 和 Y 只能被一个线程占用;
    2.占有且等待,线程 T1 已经取得共享资源 X,在等待共享资源 Y 的时候,不释放共享资源 X;
    3.不可抢占,其他线程不能强行抢占线程 T1 占有的资源;
    4.循环等待,线程 T1 等待线程 T2 占有的资源,线程 T2 等待线程 T1 占有的资源,就是循环等待。

    解决方法:破坏死锁后三个条件的任意其一(互斥一般不应被破坏)。
    1.对于“占用且等待”这个条件,我们可以一次性申请所有的资源,这样就不存在等待了。若申请不成功,wait();申请成功了,notifyAll()。
    2.对于“不可抢占”这个条件,占用部分资源的线程进一步申请其他资源时,如果申请不到,可以主动释放它占有的资源,这样不可抢占这个条件就破坏掉了。
    3.对于“循环等待”这个条件,可以靠按序申请资源来预防。所谓按序申请,是指资源是有线性顺序的,申请的时候可以先申请资源序号小的,再申请资源序号大的,这样线性化后自然就不存在循环了。

    饥饿:某些线程因为某些原因(优先级过低)无法获得所需的资源,导致无法运行。

    活锁:两个线程互相释放资源给对方,从而导致没有一个线程可以同时拿到所有资源正常执行。(出电梯时,和一个进电梯的人互相谦让,导致进电梯的人进不了,出电梯的人出不去)
    解决方法:让等待时间设定为随机值。

    为了处理这种异常情况,可以通过 jstack 命令或者Java VisualVM这个可视化工具将 JVM 所有的线程栈信息导出来,完整的线程栈信息不仅包括线程的当前状态、调用栈,还包括了锁的信息。

    5.锁 & 监视器(管程)

    锁为实现监视器提供必要的支持。

    是对象内存堆中头部的一部分数据。JVM中的每个对象都有一个锁(或互斥锁),任何程序都可以使用它来协调对对象的多线程访问。如果任何线程想要访问该对象的实例变量,那么线程必须拥有该对象的锁(在锁内存区域设置一些标志)。所有其他的线程试图访问该对象的变量必须等到拥有该对象的锁有的线程释放锁(改变标记)。锁,应是私有的、不可变的、不可重用的。
    细粒度锁:用不同的锁对受保护资源进行精细化管理,能够提升性能。

    1) 锁用来保护代码片段,任何时刻只能有一个线程执行被保护 的代码。
    2) 锁可以管理试图进入被保护代码的线程
    3) 锁可以拥有一个或者多个相关的条件对象
    4) 每个条件对象管理那些已经进入被保护的代码段,但还不能运行的线程

    用锁的最佳实践
    永远只在更新对象的成员变量时加锁
    永远只在访问可变的成员变量时加锁
    永远不在调用其他对象的方法时加锁

    监视器 Monitor是一中同步结构,它允许线程同时互斥(使用锁)和协作,即使用等待集(wait-set)使线程等待某些条件为真的能力。监视器也可以叫管程,意思是管理共享变量以及对共享变量的操作过程,让他们支持并发。管程和信号量是等价的,所谓等价指的是用管程能够实现信号量,也能用信号量实现管程。但是管程更容易使用,所以 Java 选择了管程。管程理论上能解决一切并发问题。

    他们是应用于同步问题的人工线程调度工具。讲其本质,首先就要明确monitor的概念,Java中的每个对象都有一个管程,来监测并发代码的重入。在非多线程编码时该管程不发挥作用,反之如果在synchronized 范围内,管程发挥作用。

    管程至少有两个等待队列。一个是进入管程的等待队列一个是条件变量对应的等待队列。后者可以有多个。

    wait/notify/notifyAll必须存在于synchronized块中。并且,这三个关键字针对的是同一个管程。这意味着wait之后,其他线程可以进入同步块执行。

    当某代码并不持有管程的使用权时,去wait或notify,会抛出java.lang.IllegalMonitorStateException。也包括在synchronized块中去调用另一个对象的wait/notify,因为不同对象的管程不同,同样会抛出此异常。

    管程三大模型:Hasen 模型、Hoare 模型和 MESA 模型

    1)Hasen 模型,要求 notify() 放在代码的最后,这样 T2 通知完 T1 后,T2 就结束了,然后 T1再执行,这样就能保证同一时刻只有一个线程执行。

    2)Hoare 模型,T2 通知完 T1 后,T2 阻塞,T1 马上执行;等 T1执行完,再唤醒 T2,也能保证同一时刻只有一个线程执行。但是相比 Hasen 模型,T2 多了一次阻塞唤醒操作。

    3)MESA 管程,T2 通知完 T1 后,T2 还是会接着执行,T1 并不立即执行,仅仅是从条件变量的等待队列进到入口等待队列里面。这样做的好处是 notify()不用放到代码的最后,T2 也没有多余的阻塞唤醒操作。但是也有个副作用,就是当 T1 再次执行的时候,可能曾经满足的条件,现在已经不满足了,所以需要以循环方式检验条件变量。

    Hasen 是执行完,再去唤醒另外一个线程。
    Hoare,是中断当前线程,唤醒另外一个线程,执行完再去唤醒。
    Mesa是进入等待队列(不一定有机会能够执行)。

    MESA 管程特有的编程范式:
    while(条件不满足) {
    	 wait();
    }
    

    Java 参考了 MESA 模型,语言内置的管程(synchronized)对 MESA 模型进行了精简。MESA 模型中,条件变量可以有多个,Java 语言内置的管程里只有一个条件变量,而 Java SDK 并发包实现的管程支持多个条件变量,不过并发包里的锁,需要开发人员自己进行加锁和解锁操作。

    二.并发编程的核心问题

    分工指的是如何高效地拆解任务并分配给线程。类似于“烧水泡茶”问题。

    同步指的是线程之间如何协作。当某个条件不满足时,线程需要等待,当某个条件满足时,线程需要被唤醒执行。

    互斥则是保证同一时刻只允许一个线程访问共享资源。也就是所谓的“线程安全”。核心技术为“锁”。

    三.并发的隐患

    【补充】

    数据竞争: 当多个线程同时访问同一数据,并且至少有一个线程会写这个数据的时候,如果我们不采取防护措施,那么就会导致并发 Bug。

    竞态条件,指的是程序的执行结果依赖线程执行的顺序。当你看到代码里出现 if 语句的时候,就应该立刻意识到可能存在竞态条件,因为可能同时在一个状态的时候,有多个线程通过了这个条件,然而他们之后的操作都可能使得这个条件不成。解决办法就是让这些方法之间互斥,例如可以采用单例模式,然后让所有方法以单例为加锁对象同步。

    1.缓存导致的可见性问题

    可见性:一个线程对共享变量的修改,另外一个线程能够立刻看到。

    volatiole变量的写先于读发生,保证了它的可见性。

    多核时代,每颗 CPU 都有自己的缓存,当多个线程在不同的 CPU 上执行时,这些线程操作的位置是不同的 CPU缓存,他们之间不具有可见性。

    2.线程切换带来的原子性问题

    原子性:一个或者多个操作在 CPU 执行的过程中不被中断的特性。

    “原子性”的本质其实不是不可分割,不可分割只是外在表现,其本质是多个资源间有一致性的要求,操作的中间状态对外不可见。

    举例

    例1:同时向一个变量发起两次修改请求,可能会导致变量修改失败。

    补充
    若要对一个变量进行操作
    至少需要三条 CPU 指令:

    指令 1:把变量从内存加载到 CPU 的寄存器;
    指令 2:在寄存器中修改变量;
    指令 3:将结果写入内存/缓存。

    在线程A将结果写入内存之前,线程B可能已经读入了初始的变量值。 然后线程A将修改结果写入内存后,线程B也将结果写入内存。这会导致线程A的修改被完全覆盖,因为线程B的初始值读入的是线程A修改之前的变量值。

    例2:在32位的系统上,读写long(64位数据)

    使用双线程同时对long型数据进行写入或读取。
    如果新建多个线程同时改变long型数据的值,最后的值可能是乱码。因为是并行读入的,所以可能读的时候错位了。

    3.编译带来的有序性

    有序性:程序按照代码的先后顺序执行。 编译器为了优化性能,有时候会改变程序中语句的先后顺序,例如程序中:“a=6;b=7;”编译器优化后可能变成“b=7;a=6”,有时候会导致意想不到的bug。
    (指令重排对于CPU处理性能是十分必要的)

    举例

    在 Java 领域一个经典的案例就是利用双重检查创建单例对象,例如下面的代码:在获取实例 getInstance() 的方法中,我们首先判断 instance 是否为空,如果为空,则锁定 Singleton.class 并再次检查 instance 是否为空,如果还为空则创建 Singleton 的一个实例。

    public class Singleton {
      static Singleton instance;
      static Singleton getInstance(){
        if (instance == null) {
          synchronized(Singleton.class) {
            if (instance == null)
              instance = new Singleton();
            }
        }
        return instance;
      }
    }
    

    假设有两个线程 A、B 同时调用 getInstance() 方法,他们会同时发现 instance == null ,于是同时对Singleton.class 加锁,此时 JVM 保证只有一个线程能够加锁成功(假设是线程 A),另外一个线程则会处于等待状态(假设是线程B); 线程 A 会创建一个 Singleton 实例,之后释放锁,锁释放后,线程 B 被唤醒,线程 B再次尝试加锁,此时是可以加锁成功的,加锁成功后,线程 B 检查 instance == null 时会发现,已经创建过 Singleton实例了,所以线程 B 不会再创建一个 Singleton 实例。

    这看上去一切都很完美,无懈可击,但实际上这个 getInstance() 方法并不完美。问题出在哪里呢?出在 new 操作上,我们以为的new 操作应该是:

    分配一块内存 M;
    在内存 M 上初始化 Singleton 对象;
    然后 M 的地址赋值给 instance 变量。

    但是实际上优化后的执行路径却是这样的:

    分配一块内存 M;
    将 M 的地址赋值给 instance 变量;
    最后在内存 M 上初始化 Singleton 对象。

    优化后会导致什么问题呢?

    我们假设线程 A 先执行 getInstance() 方法,当执行完指令 2 时恰好发生了线程切换,切换到了线程B 上; 如果此时线程 B 也执行 getInstance() 方法,那么线程 B 在执行第一个判断时会发现 instance != null ,所以直接返回 instance。 而此时的 instance 是没有初始化过的,如果我们这个时候访问 instance 的成员变量就可能触发空指针异常。

    在这里插入图片描述

    解决方案1:将Instance声明为volatitle,前面的重排序在多线程环境中将会被禁止

    public class Singleton {
    private static volatile Singleton sInstance;
    public static Singleton getInstance() {
        if (sInstance == null) {
            synchronized (Singleton.class) {
                if (sInstance == null) {
                    sInstance = new Singleton();
                }
            }
       }
       return sInstance;
    }
    private Singleton() {}
    }
    

    解决方案2:静态内部类

    public class Singleton {
        private Singleton(){};
        private static class Inner{
            private static Singleton SINGLETION=new Singleton();
        }
        public static Singleton getInstance(){
            return Inner.SINGLETION;
        }
    }  
    

    静态内部类不会随着外部类的初始化而初始化,他是要单独去加载和初始化的,当第一次执行getInstance方法时,Inner类会被初始化。

    静态对象SINGLETION的初始化在Inner类初始化阶段进行,类初始化阶段即虚拟机执行类构造器()方法的过程。

    虚拟机会保证一个类的()方法在多线程环境下被正确的加锁和同步,如果多个线程同时初始化一个类,只会有一个线程执行这个类的()方法,其它线程都会阻塞等待。

    解决方法3:原子类 AtomicInteger

    详情请见文末java并发包中的原子类

    四.解决原子性,可见性和有序性

    我们已经知道,导致可见性的原因是缓存,导致有序性的原因是编译优化,那解决可见性、有序性最直接的办法就是禁用缓存和编译优化,但是这样问题虽然解决了,我们程序的性能可就堪忧了。

    合理的方案应该是按需禁用缓存以及编译优化。那么,如何做到“按需禁用”呢?对于并发程序,何时禁用缓存以及编译优化只有程序员知道,那所谓“按需禁用”其实就是指按照程序员的要求来禁用。所以,为了解决可见性和有序性问题,只需要提供给程序员按需禁用缓存和编译优化的方法即可。

    Java 内存模型是个很复杂的规范,本质上可以理解为,Java 内存模型规范了 JVM 如何提供按需禁用缓存和编译优化的方法。具体来说,这些方法包括 volatile、synchronized 和 final 三个关键字,以及六项 Happens-Before 规则。

    volatile

    volatile 关键字并不是 Java 语言的特产,古老的 C 语言里也有,它最原始的意义就是禁用 CPU 缓存。当你使用了这个变量,就等于告诉了虚拟机,这个变量极有可能会被某些程序或线程修改。为了确保这个变量被修改后,应用程序范围内的所有线程都能看到这个改动,虚拟机必须得进行一些特殊的手段。

    volatile是轻量级的synchronized,如果使用恰当,它比synchronized的使用和执行成本更低,因为他不会引起上下文切换和调度。

    多线程的内存模型:main memory(主存)、working memory(线程栈),在处理数据时,线程会把值从主存load到本地栈,完成操作后再save回去(volatile关键词的作用:每次针对该变量的操作都激发一次load and save)。

    针对多线程使用的变量如果不是volatile或者final修饰的,很有可能产生不可预知的结果(另一个线程修改了这个值,但是之后在某线程看到的是修改之前的值)。其实道理上讲同一实例的同一属性本身只有一个副本。但是多线程是会缓存值的,本质上,volatile就是不去缓存,直接取值。在线程安全的情况下加volatile会牺牲性能。但相比较synchronized和锁,性能更佳。与普通变量相比,就是写入的操作慢一点,因为会加入许多内存屏障指令。

    内存屏障(memory barrier)是一个CPU指令。基本上,它是这样一条指令:
    a) 确保一些特定操作执行的顺序;
    b) 影响一些数据的可见性(可能是某些指令执行后的结果)。编译器和CPU可以在保证输出结果一样的情况下对指令重排序,使性能得到优化。插入一个内存屏障,相当于告诉CPU和编译器先于这个命令的必须先执行,后于这个命令的必须后执行。内存屏障另一个作用是强制更新一次不同CPU的缓存。例如,一个写屏障会把这个屏障前写入的数据刷新到缓存,这样任何试图读取该数据的线程将得到最新值,而不用考虑到底是被哪个cpu核心或者哪颗CPU执行的。

    内存屏障(memory barrier)和volatile什么关系?上面的虚拟机指令里面有提到,如果你的字段是volatile,Java内存模型将在写操作后插入一个写屏障指令,在读操作前插入一个读屏障指令。这意味着如果你对一个volatile字段进行写操作,你必须知道:1、一旦你完成写入,任何访问这个字段的线程将会得到最新的值。2、在你写入前,会保证所有之前发生的事已经发生,并且任何更新过的数据值也是可见的,因为内存屏障会把之前的写入值都刷新到缓存。

    1.原 子 性

    volatile并不能直接替代锁的作用,他只能保证可见性和有序性,但volatile保证不了原子性操作!!!!!

    修改一个变量值的JVM指令:

    mov    0xc(%r10),%r8d ; Load
    inc    %r8d           ; Increment
    mov    %r8d,0xc(%r10) ; Store
    lock addl $0x0,(%rsp) ; StoreLoad Barrier
    

    从Load到store到内存屏障,一共4步,其中最后一步jvm让这个最新的变量的值在所有线程可见,也就是最后一步让所有的CPU内核都获得了最新的值,但中间的几步(从Load到Store)是不安全的,中间如果其他的CPU修改了值将会丢失。

    最简单的一个例子是调用多次一个线程进行i++操作:

    一个变量i被volatile修饰,两个线程想对这个变量修改,都对其进行自增操作也就是i++,i++的过程可以分为三步,首先获取i的值,其次对i的值进行加1,最后将得到的新值写回到缓存中。
    线程A首先得到了i的初始值100,但是还没来得及修改,就阻塞了,这时线程B开始了,它也得到了i的值,由于i的值未被修改,即使是被volatile修饰,主存的变量还没变化,那么线程B得到的值也是100,之后对其进行加1操作,得到101后,将新值写入到缓存中,再刷入主存中。根据可见性的原则,这个主存的值可以被其他线程可见。
    问题来了,线程A已经读取到了i的值为100,也就是说读取的这个原子操作已经结束了,所以这个可见性来的有点晚,线程A阻塞结束后,继续将100这个值加1,得到101,再将值写到缓存,最后刷入主存,所以即便是volatile具有可见性,也不能保证对它修饰的变量具有原子性。

    除此之外,还有一个很重要的点。在JAVA中,Integer 属于不变对象,也就是说,如果你要修改一个值为1的Integer对象,实际上是新建一个值为2的Interger对象,i=Integer.valueOf(i.intValue()+1),

    2.可见性 & 顺序性

    为了解决volatile所带来的可能的可见性问题,jdk1.5以后添加了Happens-Before 规则,它规定了哪些指令不能重排。

    Happens-Before
    1)程序顺序原则:一个线程内保证语义的串行性。
    2)volatile规则:volatile变量的写先于读发生,这保证了它的可见性 。
    3)传递性:A先于B,B先于C,那么A必然先于C。
    4)管程中锁规则:解锁必须在加锁前。
    5)线程的start()方法先于它的每一个动作。
    6)线程的所有操作先于线程的终结(Thread.join())。
    7)线程的中断先于被中断线程的代码。
    8)对象的构造函数的执行、结束先于finalize()方法。

    1)程序顺序原则

    符合单线程里面的思维:程序前面对某个变量的修改一定是对后续操作可见的

    2 & 3)volatile 变量规则+传递性
    举例:
    在这里插入图片描述
    如果线程 B 读到了“v=true”,那么线程 A 设置的“x=42”对线程 B 是可见的。也就是说,线程 B 能读到 x = 42 。

    4)管程中锁的规则

    管程:是一种通用的同步原语,在 Java 中指的就是 synchronized,synchronized 是 Java 里对管程的实现。synchronized 关键字及 wait()、notify()、notifyAll() 这三个方法都是管程的组成部分。

    举例

    在多线程环境下,synchronized块中的方法获取了lock实例的monitor,如果实例相同,那么只有一个线程能执行该块内容

    public class Thread1 implements Runnable {
       Object lock;
       public void run() {  
           synchronized(lock){// 此处自动加锁
             ..do something
           }
       }// 此处自动解锁
    }
    

    也可以直接用于方法: 相当于上面代码中用lock来锁定的效果,实际获取的是Thread1类的monitor。更进一步,如果修饰的是static方法,则锁定该类所有实例。

    public class Thread1 implements Runnable {
       public synchronized void run() {  
            ..do something
       }
    }
    

    5)线程 start() 规则

    如果线程 A 调用线程 B 的 start() 方法(即在线程 A 中启动线程 B),那么该 start() 操作 Happens-Before 于线程 B 中的任意操作。

    6)线程 join() 规则

    如果在线程 A 中,调用线程 B 的 join() 并成功返回,那么线程 B 中的任意操作 Happens-Before 于该 join() 操作的返回

    synchronized

    关键字synchronized的作用是实现线程之间的同步,他的工作是对同步的代码枷锁,使得每一次,只能有一个线程进入同步块,从而保证线程之间的安全性。

    Java 编译器会在 synchronized 修饰的方法或代码块前后自动加上加锁 lock() 和解锁 unlock()

    三种使用方法:
    1.指定加锁对象
    2.直接作用于实例方法,锁定的是当前实例对象 this。
    3.直接作用于静态方法,锁定的是当前类的 Class 对象

    class X {
      // 修饰非静态方法
      synchronized void foo() {
        // 临界区
      }
      // 修饰静态方法
      synchronized static void bar() {
        // 临界区
      }
      // 修饰代码块
      Object obj = new Object()void baz() {
        synchronized(obj) {
          // 临界区
        }
      }
    }  
    

    实例方法要求thread指向的接口是同一个,
    而静态方法则不需要。

    五.多线程

    【拓】

    1.为什么要用多线程?

    提升 CPU 和 I/O 设备的利用率。

    2.线程数量最佳为多少?

    对于 CPU 密集型的计算场景,理论上“线程的数量 =CPU 核数”就是最合适的。不过在工程上,线程的数量一般会设置为“CPU 核数
    +1”,这样的话,当线程因为偶尔的内存页失效或其他原因导致阻塞时,这个额外的线程可以顶上,从而保证 CPU 的利用率。

    对于 I/O 密集型的计算场景,最佳线程数 =CPU 核数 * [ 1 +(I/O 耗时 / CPU 耗时)]

    3.局部变量需要多线程吗?
    不需要。局部变量存放在线程各自的的调用栈里,而每个线程都有自己独立的调用栈,不会共享,所以自然也就没有并发问题。

    1.线程的状态

    打开JAVA的Thread类里的State枚举类,可以看到

    public enum State {
    	NEW,
    	RUNNABLE,
    	BLOCKED,
    	WAITING,
    	TIMED_WAITING,
    	TERMINATED;
    }
    

    在这里插入图片描述
    1)Runnable to Blocked

    只有一种场景会触发这种转换,就是线程等待 synchronized 的隐式锁。synchronized 修饰的方法、代码块同一时刻只允许一个线程执行,其他线程只能等待,这种情况下,等待的线程就会从 RUNNABLE 转换到 BLOCKED 状态。而当等待的线程获得 synchronized 隐式锁时,就又会从 BLOCKED 转换到 RUNNABLE 状态。

    2)Runnable to Waiting

    1.获得 synchronized 隐式锁的线程,调用无参数的 Object.wait() 方法。

    2.调用无参数的 Thread.join() 方法。其中的 join() 是一种线程同步方法,例如有一个线程对象 thread A,当调用 A.join() 的时候,执行这条语句的线程会等待 thread A 执行完,而等待中的这个线程,其状态会从 RUNNABLE 转换到 WAITING。当线程 thread A 执行完,原来等待它的线程又会从 WAITING 状态转换到 RUNNABLE。

    3.调用 LockSupport.park() 方法。其中的 LockSupport 对象,Java 并发包中的锁,都是基于它实现的。调用 LockSupport.park() 方法,当前线程会阻塞,线程的状态会从 RUNNABLE 转换到 WAITING。调用 LockSupport.unpark(Thread thread) 可唤醒目标线程,目标线程的状态又会从 WAITING 状态转换到 RUNNABLE。

    3)Runnable to TIMED_WAITING
    WAITING和TIMED_WAITING都是等待状态,TIMED_WAITING 和 WAITING 状态的区别,仅仅是触发条件多了超时参数。.

    4)New to Runnable
    重写run或者实现Runnable接口或者继承Thread

    5)Runnable to Terminated
    线程执行完 run() 方法后,会自动转换到 TERMINATED 状态,当然如果执行 run() 方法的时候异常抛出,也会导致线程终止。有时候我们需要强制中断 run() 方法的执行,可以调用 interrupt() 方法。

    2.线程的基本操作(JAVA)

    1)新建一个线程
    Thread t1 = new Thread(){
                @Override
                public void run() {
                    ..do something
                }
            };
    t1.start();
    

    一般的类要实现线程,可以继承Thread类,当然也可以使用Runnable接口。最常使用的还是用正则表达式重写run函数。
    构造方法:public Thread(Runnable targert)

    2)终止线程

    不建议用已经被废弃的stop() ,因为它会自动释放被终止对象的锁。

    推荐使用的是用一个volatile修饰的布尔型变量来决定是否退出。

    volatile boolean stopme =false;
    public void stopMe(){
    	stopme = true;
    }
    ...
    while(true){
    	if(stopme){
    		break;
    	}
    	. . do something
    }
    
    3)线程中断

    三个方法

    1public void Thread.interrupt()
    	通知目标线程中断,也就是设置中断标志位。
    2public boolean Thread.isInterrupted()
    	判断当前线程是否被中断,也就是检查中断标志位
    3public static boolean Thread.interrupted()
    	判断是否被中断,并清除当前中断标志位
    

    Thread.sleep()方法会让当前线程休眠若干时间,它会抛出InterruptedException中断异常。此时,它会清除中断标记。所以我们应该在异常处理中再次将其中断

    try{
    	Thread.sleep(2000);
    } catch (InterruptedException e) {
    	System.ot,println("xxx");
    	Thread.currentThread().interrupt();
    	}
    	
    
    4)等待和通知

    wait()和notify()是Object类的方法。
    在一个实例对象上,在一个synchronzied语句中,调用wait()方法后,当前线程就会在这个对象上等待,并释放锁。直到有其他线程执行了notify()/notifyAll()。使用notify()/notifyAll()后,会唤醒处于等待状态的线程,是他们的状态变为Runnable。
    wait()会释放锁而sleep()不会。

    挂起(suspend)和继续执行(resume)已被废弃。

    5)等待线程结束和谦让

    join()是等待方法,该方法将一直等待到它调用的线程终止。

    Join方法实现是通过wait()在当前线程对象实例上。 当main线程调用t.join()时候,main线程会获得线程对象t的锁(wait 意味着拿到该对象的锁),调用该对象的wait(等待时间),直到该对象唤醒main线程 ,比如退出后。这就意味着main线程调用t.join时,必须能够拿到线程t对象的锁。

    用途:在很多情况下,主线程生成并起动了子线程,如果子线程里要进行大量的耗时的运算,主线程往往将于子线程之前结束,但是如果主线程处理完其他的事务后,需要用到子线程的处理结果,也就是主线程需要等待子线程执行完成之后再结束,这个时候就要用到join()方法了。(个人理解就是wait() + notify())

    不要在应用程序中,在Thread对象实例上使用类似wait()方法或者notify()方法等,可能会和API互相影响。

    yield()是谦让方法,它会让当前线程让出CPU,但线程还是会进行CPU资源的争夺。如果你觉得一个线程不是非常重要,又害怕占用过多资源,可以使用它来给其他线程更多的工作机会。

    6)线程组

    如果线程数量很多,而且功能分配明确,可以将相同功能的线程放置在同一个线程组里。
    activeCount()返回活动线程总数(不精确的)
    list()返回线程组中所有线程的信息。

    public class Test implements Runnable{
        public static void main(String[] args) {
            ThreadGroup tg = new ThreadGroup("GroupName");
            Thread t1 = new Thread(tg,new Test(),"ThreadName1");
            Thread t2 = new Thread(tg,new Test(),"ThreadName2");
            t1.start();
            t2.start();
            System.out.println(tg.activeCount());
            tg.list();
        }
    
        @Override
        public void run() {
            String groupAndName = Thread.currentThread().getThreadGroup().getName()+" - "+Thread.currentThread().getName();
            while(true){
                System.out.println("I am "+groupAndName);
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    

    7.守护线程

    守护线程是系统的守护者,他会在后台完成一些系统性的服务。如果应用内只有守护线程,那么JAVA虚拟机就会退出。

    t.setDaemon(true);
    t.start();
    

    设置守护线程必须得在start之前,不然该线程会被当作用户线程,永远无法停止。

    8.线程优先级

    内置三个优先级,数字越大优先级越高。【1,10】
    高优先级的线程 倾向于 更快地完成。

    至于问什么是倾向而不是一定,是因为JAVA线程的实现是采用1:1线程模型,也就是每个轻量级进程都有一个操作系统内核的支持,但问题是 不是所有的操作系统都有10个优先级,比如说windows中只有七个,那么当然就无法满足严格的优先级顺序。
    除此之外,windows还有优先级推进器,就是一个线程被切换频繁时,系统可能会越过优先级去为它分配执行时间,从而减少线程频繁切换带来的损耗。总而言之,不能太过依赖于优先级。

    public final static int MIN_PRIORITY = 1;
    public final static int NORM_PRIORITY = 5;
    public final static int MAX_PRIORITY = 10;
    

    并发包学习链接

    展开全文
  • 呜~ 就隔了一段时间没看并行计算,发现作业贼难顶,不得不写篇博客来记录一下复习(预习)的内容。 并行计算性能评测 并行机的一些基本性能指标 对并行计算机的性能关注点还是落在了CPU和存储器上,毕竟CPU和存储器...

    呜~ 就隔了一段时间没看并行计算,发现作业贼难顶,不得不写篇博客来记录一下复习(预习)的内容。

    并行计算性能评测

    并行机的一些基本性能指标

    对并行计算机的性能关注点还是落在了CPU和存储器上,毕竟CPU和存储器决定了计算机处理问题速度的上限。

    https://www.top500.org/收录了世界上前500台计算能力最强的计算机

    在这里插入图片描述
    可以看到,超算top 5领域美国就居了3个,我国神威·太湖之光排名4,看看神威的详细配置:

    在这里插入图片描述
    这么多核核内存orz… 不过好像处理器的频数并没有那么高,其实也就1.45GHz,个人笔记本都可以达到2.2GHz,台式机可以达到3.5GHz,或许是因为有千万个核,不需要太高的频率吧,再次Orx。后面是一些浮点运算计算能力,我后面会讲到。还有,这耗电也很厉害… 操作系统是Sunway RaiseOS

    讲了top 500,还是回到标题的内容上来,评价一个并行机有哪些指标?下面是一些参考,有一些我们刚才已经在上面的神威中学习了。
    在这里插入图片描述
    上面mention到了顺序执行时间和并行执行时间,一般有下面的式子成立:

    程序执行时间 = 计算时间 + 并行开销时间 + 相互通信时间

    加速比性能定律

    这个加速比其实我去年已经讲过了,在《计算机组成与设计》这里:https://blog.csdn.net/weixin_44026604/article/details/112167660,不过加速比可不仅仅是Amdahl定律

    所谓并行加速比,其实是相对串行时间而言的,就是指:对于一个给定的应用,并行算法的执行速度相对于串行算法的执行速度加快了多少倍。

    额,下面这些参数的意义得先有个了解才能继续往下聊:

    • n: 并行系统中处理器数
    • W: 问题规模(计算负载、工作负载,定义为给定问题的总计算量)
    • Ws: 应用程序中的串行分量
    • Wp: W中可并行化部分(Ws+Wp=W)
    • f: 串行分量比例
    • f =Ws/W
    • Ts: 串行分量的执行时间
    • Tp: 并行分量的执行时间
    • S: 加速比
    • E: 效率

    Amdahl定律

    Amdahl定律的出发点是在工作负载变化固定的情况下,增加处理器的个数来提高计算的速度,定律表达为:

    在这里插入图片描述
    上面这个式子就表示了:加速比不会随着处理器个数的无限增加而无限提高,而是会达到一个上限,这个上限是串行占比的倒数。一个程序,如果其串行分量越大,则其并行所获得加速比上限就越低;如果串行分量越小(意味着可并行的分量比例越大),则其并行所获得的加速比上限(天花板)就越高。

    在这里插入图片描述
    从上面的图中可以很清楚地看到,即使串行部分在程序中仅占了4%,但加速比的上限也就只能达到31了。所以,平时编OpenMP程序,运行时间与处理器核数不成正比也是可以理解的,毕竟一般程序都含有串行部分,相当于是一次函数,而不是正比例函数。

    如果再考虑一个并行开销,则Amdahl公式变为:

    在这里插入图片描述

    Gustafson定律

    Gustafson的出发点和Amdahl不同:Gustafson认为在固定的时间内,完成的事情越多,加速比越高。除非学术研究,在实际应用中没有必要固定工作负载而使计算程序运行在不同数目的处理器上。Gustafson定律认为,增多处理器必须相应地增大问题规模才有实际意义,公式表达为:

    在这里插入图片描述
    这个表达式看上去要比Amdahl乐观,它表示了:计算负载增加的情况下,相应的增加处理器的数量,所获得加速比也是在增加的。且从表达式看出,这个加速比似乎没有天花板?!!orz

    在这里插入图片描述

    当串行只占了4%左右,加速比保持在很高水平,如果再考虑一个并行开销:

    在这里插入图片描述

    有关加速的讨论

    一般的经验高速我们:
    在这里插入图片描述

    • 可达线性加速的应用问题
      矩阵相加、内积运算等,此类问题几乎没有通信开销

    • 可达p/logp加速的应用问题
      分治内的应用问题,类似于二叉树,树的同级可并行执行,但向根逐渐推进时,并行度将逐渐减少

    • 超线性加速:由于高速缓存内存的增加

    • 绝对加速:最佳串行算法所用的时间除以同一问题其并行算法所用的时间

    • 相对加速:同一算法在单处理器上运行的时间除以在多个处理器上运行的时间

    基准测试程序

    top 500的ranking可不是主观评出来的,而是程序跑出来的,测试计算机性能的程序一般称基准测试程序。了解一下就好:

    基本测试程序

    综合型基准测试程序Whetstone

    • 为不同的计算机浮点性能而设计的综合型基准测试程序
    • 即包括整数运算,又包括浮点运算,涉及数组下标索引、子程序调用、参数传递、条件转移和三角/超越函数等

    综合型基准测试程序Dhrystone

    • 为测试整数与逻辑运算性能而设计的综合型基准测试程序
    • 一种CPU密集型测试程序

    标准基准测试程序SPEC

    • 主要是测试CPU性能的
    • 强调开发能反映真实应用(如实际负载)的基准测试程序,并已推广到客户-服务器计算、商业应用、I/O子系统等

    数学库测试程序

    基准测试程序LinPACK

    • 用全精度64位字长的子程序求解100阶线性方程组的速度
    • 测试的结果以MFLOPS作单位给出
    • 作用BLAS1的第一个线性代数软件包

    基准测试程序LAPACK

    • 使用了数值线性代数中最新、最精确的算法
    • 采用了将大型矩阵分解成小块矩阵的方法,从而可有效地使用存储器
    • 建立在BLAS1、 BLAS2和BLAS3基础上

    基准测试程序ScaLAPACK

    • 是LAPACK的增强版 ,主要为可扩放的、分布存储的并行计算机而设计的

    并行测试程序

    NAS Parallel Benckmark

    • 1991年美国NAS项目所开发的并行测试程序
    • 其目的是为了比较各种并行机性能
    • 系由8个程序组成,测试范围从整数排列到复杂的数值计算

    PARKBENCH

    • 在1992年超级计算会议上确定的项目
    • 主要目标是确定并行机用户与厂商双方都能接受的、内容丰富的一批并行测试程序及标准
    • 4类PARKBENCH
    • 底层基准程序
    • 核心基准程序
    • 密集应用基准程序
    • HPF编译基准程序

    【本章小结】掌握Amdhl定律和Gustafson定律,理解其计算基本的出发点,了解并行计算机常见的性能指标和测试程序

    并行算法与并行计算模型

    并行算法概述

    算法表达

    在这里插入图片描述

    算法复杂性

    这里的复杂度不仅仅是时间或者空间复杂度,正是由于并行算法运行在多核上的特殊性,因此其复杂性指标多,举一些来介绍:

    • 运行时间t(n)
      • 算法运行在给定模型上求解问题所需的时间,包含计算时间和通信时间,分别用计算时间步和选路时间步作单位
    • 处理器数p(n)
      • 求解给定问题所用的处理器数目
    • 并行算法成本c(n)
      • c(n)=t(n)p(n)
      • 成本最优
    • 总运算量W(n)
      • 并行算法所完成的总的操作数量

    同步与通信

    同步就是多处理器之间要相互协作,在一些具有先后次序的问题上需要等待。譬如下面的求和算法:
    在这里插入图片描述

    通信简单理解就是数据交换。
    在这里插入图片描述

    并行计算模型

    PRAM模型(PRAM:并行随机访问存储器)

    特点:

    • 具有有限个或者无限个功能相同的处理器
    • 一个容量无限大的共享存储器
    • 在单位时间内,每个处理器能访问任一存储单元
    • 所有处理器同步执行PRAM指令(某些处理器可以空闲)
    • 一个算法的运行时间是指令周期数

    根据处理器对共享存储单元同时读、同时写的限制,PRAM模型又可分为:

    • 不允许同时读和同时写(PRAM-EREW)
      不允许两个处理器在同一时间访问同一存储单元,但允许访问不同的存储单元
    • 允许同时读不允许同时写(PRAM-CREW)
    • 允许同时读和同时写,但需要解决写冲突(PRAM-CRCW)

    下面是一个运行在PRAM模型上的求和算法:
    在这里插入图片描述
    在这里插入图片描述
    内层循环是可并行的,因此这个求和并行算法的时间t(n)=O(logn),处理器数p(n)=n/2,成本c(n)=O(nlogn),总运算量W(n)=n-1,加速比S(n)=O(n/longn)

    PRAM模型的优点:

    • 适合于并行算法的表达、分析和比较
    • 使用简单,隐含了通信和同步等细节
    • 易于设计算法,稍加修改便可运行在不同的并行计算机上
    • 可推广,加入一些诸如同步和通信等需要考虑的问题

    PRAM模型的缺点:

    • 所有的指令均按锁步方式操作,很费时
    • 共享单一存储器的假定不适合于分布存储的MIMD机器
    • 假设每个处理器均可在单位时间内访问任何存储单元而略去存取竞争和有限带宽等是不现实的

    APRAM模型(异步PRAM模型)

    特点:

    • 由p个处理器组成,每个处理器有其局部存储、局部时钟和局部程序
    • 处理器之间的通信需要经过共享全局存储器
    • 无全局时钟,各处理器异步独立执行各自的命令
    • 处理器间任何时间依赖关系需要明确地在各处理器地程序中加入同步路障
    • 一条指令可在非确定但优先的时间内完成
      • 局部操作:单位时间
      • 全局读和全局写:时间为d,d随p的增加而增加
      • 同步:时间为B,是p的非降函数
      • 一般有 2 ≤ d ≤ B ≤ p

    计算过程:

    • 计算由同步障分开的全局相组成
    • 在各全局相内,每个处理器异步执行
    • 在同一相内不允许两个处理器访问统一存储单元
    • 运行时间为:(tph为全局相内各处理器指令执行时间中的最长者)
      在这里插入图片描述
      下面是一个运行在APRAM模型上的求和算法:
      在这里插入图片描述
      在这里插入图片描述
    • 各处理器先求n/p个数的局部和,然后通过树自底向上逐层求和
    • 运行时间t(n) =
    • 处理器数p(n) =
    • 成本c(n) =
    • 加速比S(n) =

    APRAM模型的优点:

    • 比起PRAM更接近于实际的并行计算机
    • 保留了PRAM编程的便捷性
    • 使用了同步障,确保程序正确
    • 成本参数定量化,易于分析算法

    APRAM模型的缺点:

    • 与实际的并行计算机仍然相差较远
    • 不适合于消息传递并行计算机

    BSP模型(下面两个模型简单了解一下就可以了)

    在这里插入图片描述
    结构:

    • 处理器/存储器模块(处理器数为p)
    • 施行处理器/存储器模块对之间点到点传递消息的选路器(吞吐率为g)
    • 路障同步器(同步时间为L)

    计算过程:

    • 垂直结构:
      • 局部计算
      • 全局通信
      • 路障同步
    • 水平结构:
      • p个处理器之间并发执行
    • 一个超级步的运行时间 MAX(w+hg)+L,w为执行局部计算的时间,h为发送/接收消息的数目

    BSP模型的优点:

    • 强调了计算和通信的分离
    • 在一个超级步内,可将消息作为一个整体传递
    • 易于分析算法复杂性
    • 提供了一个用于编程的BSP函数库

    BSP模型的缺点:

    • 需要特殊的硬件支持全局路障同步,否则同步代价较大

    LogP模型

    一种分布存储的、点到点通信的多处理机模型,其中通信网络由一组参数来描述,但它并不涉及到具体的网络结构

    参数说明:

    • L表示在网络中消息从源到目的地所产生的延迟
    • o表示处理器发送或接收一条消息所需的额外开销
      • 在此期间内它不能进行其他操作
    • g表示处理器可连续进行消息发送或接收的最小时间间隔
      • g的倒数相应于处理器的通信带宽
      • L和g反映了通信网络的容量
    • p表示处理器/存储器模块数
    • L、o和g都可以表示成处理器周期的整数倍

    在这里插入图片描述
    LogP模型的优点:

    • 明确了通信网络的性能特征
    • 隐藏了并行机的网络拓扑、路由、协议
    • 可应用到共享存储、消息传递的编程模型中

    LogP模型的缺点:

    • 难以对算法进行描述、设计和分析

    BSP模型和logP模型不同之处

    • LogP基于成对消息传递,BSP进行整体通信
    • LogP增加了一个参数o,表示传递消息的额外开销
    • LogP鼓励计算与通信重叠,BSP强调计算与通信分离

    常见问题的并行算法

    向量运算

    这个十分简单,一点依赖关系都没有,直接上OpenMP,串行的时间复杂度为O(n),并行时间复杂度为O(1),并行伪码为:
    在这里插入图片描述

    归约

    在我看来,归约总是有点“归并”的味道,归约适用于求和、求最大值、计数等场景。下面是求总和的并行算法,时间复杂性为O(n),并行算法的复杂性为O(logn),所需的处理器数为n/2:
    在这里插入图片描述在这里插入图片描述

    扫描

    使用场景如求前缀和。下面是求前缀和的并行算法,串行时间复杂度为O(n),并行算法运行时间为O(logn),处理器数为n/2:
    在这里插入图片描述
    在这里插入图片描述
    求前缀和也有另外的解法,这种解法处理器数为n,运行时间为O(logn)
    在这里插入图片描述
    在这里插入图片描述

    矩阵相乘

    矩阵相乘的串行算法时间复杂度为O(n³),算法可优化到O(n2.81),但使用并行,可以降到更低,下面是两种并行算法:

    1. 处理器数为n²,运行时间为O(n)
      在这里插入图片描述
    2. 处理器数为n³,运行时间为O(logn)
      在这里插入图片描述

    无序数组的秩

    所谓数组的秩,就是指定x,求数组中小于x的元素的个数,串行算法时间显然为O(n),并行算法为:
    在这里插入图片描述
    这里是把求无序数组A的秩,转化为求数组B的和,直接使用前面的求和并行算法就好。

    处理器数为n/2,运行时间为O(logn)

    有序数组的秩

    串行可以使用二分,时间复杂度为O(logn)。一个简单的并行算法如下:
    在这里插入图片描述
    处理器数为n,运行时间为O(1)

    若处理器数为根号n,则可以分段并行求解:
    在这里插入图片描述
    这样子的运行时间仍旧为O(1)

    归并

    所谓归并,就是指将两个有序数组合并为一个整体有序数组,这里为了方便,在原先的两个数组末尾加上了哨兵,这两个哨兵都是正无穷。下面是归并的两种并行算法:

    并行算法1
    在这里插入图片描述
    这个算法的示意图:
    在这里插入图片描述
    核心是分段,分段进行排序,使用秩保证了分段之后的数字序列可以直接合并。

    这个算法的处理器数为p,平均运行时间为O(n/p)

    并行算法2

    先引入一个定义,由这个定义所引出来的一个定理可以帮助我们归并序列:

    双调序列:与单调序列相对,双调序列允许一个序列先增后降,或者先降后增(注意这里允许首尾相接),也就是下面几种情况都是属于双调序列

    在这里插入图片描述
    Batcher定理
    在这里插入图片描述
    由此我们可以设计以下算法:先将序列分为小序列和大序列,这样子就保证了小序列中的每个数都比大序列中的任意一个数小,那么采用递归方法就可以完成归并。
    在这里插入图片描述
    以上算法适用于数组个数为2k的情形

    如果数组个数大小不是2k,则并行算法改为:
    在这里插入图片描述

    算法首先将原来两个有序数组赋值到一个新数组c里面(这里还强制把数组长度变成2的幂次方),然后调用前面的双调归并算法。这种情况下所需要的处理器数m+n,运行时间是O(log(m+n))

    插入排序

    在这里插入图片描述
    我们发现,插入排序最终其实就是将每个数放到它的秩的位置上,其实不仅是插入排序,其他排序也可以利用这个思想。这种情形下的处理器数为n,运行时间为O(n)

    tips:冒泡排序没法并行化

    选择排序

    在这里插入图片描述
    处理器数为n²,运行时间为O(logn)

    归并排序

    前面我们已经讲了归并,知道了一般情形下归并的时间复杂度为O(logn),则按照归并排序的算法思想,易得归并排序的算法时间复杂度为O(log²n),处理器数为n/2。伪码如下(其实和串行伪码是一样的,只不过加上了并行)
    在这里插入图片描述

    快速排序的并行化

    自上而下构造一棵二叉排序树,中序遍历可得到一个有序序列
    在这里插入图片描述

    • 初始化
      root=i,选择根节点,每个处理器将自己的处理器号写入变量root,根据CRCW模型原理,最终只有一个处理器号会被写入变量root
      f[i] = root,设置所有节点的父亲为根节点
      LC[i] = RC[i] = n,设置所有节点的左右孩子为空
      在这里插入图片描述
    • 并行构造树的第二层
      每个Pi比较a[i]和a[f[i]]的大小
      <a[f[i]]的节点竞争成为f[i]的左孩子
      >a[f[i]] 的节点竞争成为f[i]的右孩子
      竞争失败的节点将其父亲指向胜利者
    • 循环构造树的第三层…
      在这里插入图片描述

    构造一级树的时间:O(1)
    平均树高:O(logn)
    平均时间复杂度:O(logn)
    并行中序遍历平均时间:O(logn)

    PSRS排序算法

    PSRS假设只有p个处理器,(p远小于要排序的数组的元素数),这个算法是怎么做的呢?

    在这里插入图片描述
    这个算法的示意图如下:
    在这里插入图片描述
    这里假设了数组大小为27,一共有3个处理器

    多路归并,既可以使用串行归并,也可以使用并行归并
    在这里插入图片描述

    展开全文
  • 快速掌握用python写并行程序

    千次阅读 2018-11-04 11:31:44
    这就要说下我前几天做的一个作业了,当时我用python写了个程序,结果运行了一天,这个速度可让我愁了,我还怎么优化,怎么交作业啊。于是小子就去各大论坛寻丹问药了,终于让我发现可以用并行计算来最大化压榨电脑的...

    小子今天想来谈谈“并行计算”,作为一个非科班人员,我为什么去捣鼓这么一个在科班里也比较专业的问题了。这就要说下我前几天做的一个作业了,当时我用python写了个程序,结果运行了一天,这个速度可让我愁了,我还怎么优化,怎么交作业啊。于是小子就去各大论坛寻丹问药了,终于让我发现可以用并行计算来最大化压榨电脑的CPU,提升计算效率,而且python里有multiprocessing这个库可以提供并行计算接口,于是小子花1天时间改进程序,终于在规定时间内做出了自己满意的结果,上交了作业。之后,小子对并行计算充满了兴趣,于是又重新在Google上游历了一番,大致弄清了GPU、CPU、进程、线程、并行计算、分布式计算等概念,也把python的multiprocessing耍了一遍,现在小子也算略有心得了,所以来此立碑,以示后来游客。
    小子本文分为四部分,一是大数据时代现状,其二是面对挑战的方法,然后是用python写并行程序,最后是multiprocessing实战。

    一、大数据时代的现状

    当前我们正处于大数据时代,每天我们会通过手机、电脑等设备不断的将自己的数据传到互联网上。据统计,YouTube上每分钟就会增加500多小时的视频,面对如此海量的数据,如何高效的存储与处理它们就成了当前最大的挑战。
    但在这个对硬件要求越来越高的时代,CPU却似乎并不这么给力了。自2013年以来,处理器频率的增长速度逐渐放缓了,目前CPU的频率主要分布在3~4GHz。这个也是可以理解的,毕竟摩尔定律都生效了50年了,如果它老人家还如此给力,那我们以后就只要静等处理器频率提升,什么计算问题在未来那都不是话下了。实际上CPU与频率是于能耗密切相关的,我们之前可以通过加电压来提升频率,但当能耗太大,散热问题就无法解决了,所以频率就逐渐稳定下来了,而Intel与AMD等大制造商也将目标转向了多核芯片,目前普通桌面PC也达到了4~8核。

    二、面对挑战的方法

    咱们有了多核CPU,以及大量计算设备,那我们怎么来用它们应对大数据时代的挑战了。那就要提到下面的方法了。

    2.1 并行计算

    并行(parallelism)是指程序运行时的状态,如果在同时刻有多个“工作单位”运行,则所运行的程序处于并行状态。图一是并行程序的示例,开始并行后,程序从主线程分出许多小的线程并同步执行,此时每个线程在各个独立的CPU进行运行,在所有线程都运行完成之后,它们会重新合并为主线程,而运行结果也会进行合并,并交给主线程继续处理。

     

    图一、多线程并行


    图二是一个多线程的任务(沿线为线程时间),但它不是并行任务。这是因为task1与task2总是不在同一时刻执行,这个情况下单核CPU完全可以同时执行task1与task2。方法是在task1不执行的时候立即将CPU资源给task2用,task2空闲的时候CPU给task1用,这样通过时间窗调整任务,即可实现多线程程序,但task1与task2并没有同时执行过,所以不能称为并行。我们可以称它为并发(concurrency)程序,这个程序一定意义上提升了单个CPU的使用率,所以效率也相对较高。

     

    图二、多线程并发


    并行编程模型:

     

    • 数据并行(Data Parallel)模型:将相同的操作同时作用于不同数据,只需要简单地指明执行什么并行操作以及并行操作对象。该模型反映在图一中即是,并行同时在主线程中拿取数据进行处理,并线程执行相同的操作,然后计算完成后合并结果。各个并行线程在执行时互不干扰。
    • 消息传递(Message Passing)模型:各个并行执行部分之间传递消息,相互通讯。消息传递模型的并行线程在执行时会传递数据,可能一个线程运行到一半的时候,它所占用的数据或处理结果就要交给另一个线程处理,这样,在设计并行程序时会给我们带来一定麻烦。该模型一般是分布式内存并行计算机所采用方法,但是也可以适用于共享式内存的并行计算机。

    什么时候用并行计算:

    1. 多核CPU——计算密集型任务。尽量使用并行计算,可以提高任务执行效率。计算密集型任务会持续地将CPU占满,此时有越多CPU来分担任务,计算速度就会越快,这种情况才是并行程序的用武之地。
    2. 单核CPU——计算密集型任务。此时的任务已经把CPU资源100%消耗了,就没必要使用并行计算,毕竟硬件障碍摆在那里。
    3. 单核CPU——I/O密集型任务。I/O密集型任务在任务执行时需要经常调用磁盘、屏幕、键盘等外设,由于调用外设时CPU会空闲,所以CPU的利用率并不高,此时使用多线程程序,只是便于人机交互。计算效率提升不大。
    4. 多核CPU——I/O密集型任务。同单核CPU——I/O密集型任务。

    2.2 改用GPU处理计算密集型程序

    GPU即图形处理器核心(Graphics Processing Unit),它是显卡的心脏,显卡上还有显存,GPU与显存类似与CPU与内存。
    GPU与CPU有不同的设计目标,CPU需要处理所有的计算指令,所以它的单元设计得相当复杂;而GPU主要为了图形“渲染”而设计,渲染即进行数据的列处理,所以GPU天生就会为了更快速地执行复杂算术运算和几何运算的。
    GPU相比与CPU有如下优势:

    1. 强大的浮点数计算速度。
    2. 大量的计算核心,可以进行大型并行计算。一个普通的GPU也有数千个计算核心。
    3. 强大的数据吞吐量,GPU的吞吐量是CPU的数十倍,这意味着GPU有适合的处理大数据。

    GPU目前在处理深度学习上用得十分多,英伟达(NVIDIA)目前也花大精力去开发适合深度学习的GPU。现在上百层的神经网络已经很常见了,面对如此庞大的计算量,CPU可能需要运算几天,而GPU却可以在几小时内算完,这个差距已经足够别人比我们多打几个比赛,多发几篇论文了。

    3.3 分布式计算

    说到分布式计算,我们就先说下下Google的3篇论文,原文可以直接点链接去下载:

    Google在2003~2006年发表了这三篇论文之后,一时之间引起了轰动,但是Google并没有将MapReduce开源。在这种情况下Hadoop就出现了,Doug Cutting在Google的3篇论文的理论基础上开发了Hadoop,此后Hadoop不断走向成熟,目前Facebook、IBM、ImageShack等知名公司都在使用Hadoop运行他们的程序。

    分布式计算的优势:
    可以集成诸多低配的计算机(成千上万台)进行高并发的储存与计算,从而达到与超级计算机媲美的处理能力。

    三、用python写并行程序

    在介绍如何使用python写并行程序之前,我们需要先补充几个概念,分别是进程、线程与全局解释器锁(Global Interpreter Lock, GIL)。

    3.1 进程与线程

    进程(process):

    • 在面向线程设计的系统(如当代多数操作系统、Linux 2.6及更新的版本)中,进程本身不是基本运行单位,而是线程的容器。
    • 进程拥有自己独立的内存空间,所属线程可以访问进程的空间。
    • 程序本身只是指令、数据及其组织形式的描述,进程才是程序的真正运行实例。 例如,Visual Studio开发环境就是利用一个进程编辑源文件,并利用另一个进程完成编译工作的应用程序。

    线程(threading):

    • 线程有自己的一组CPU指令、寄存器与私有数据区,线程的数据可以与同一进程的线程共享。
    • 当前的操作系统是面向线程的,即以线程为基本运行单位,并按线程分配CPU。

    进程与线程有两个主要的不同点,其一是进程包含线程,线程使用进程的内存空间,当然线程也有自己的私有空间,但容量小;其二是进程有各自独立的内存空间,互不干扰,而线程是共享内存空间。
    图三展示了进程、线程与CPU之间的关系。在图三中,进程一与进程二都含有3个线程,CPU会按照线程来分配任务,如图中4个CPU同时执行前4个线程,后两个标红线程处于等待状态,在CPU运行完当前线程时,等待的线程会被唤醒并进入CPU执行。通常,进程含有的线程数越多,则它占用CPU的时间会越长。

     

    图三、进程、线程与CPU关系

     

    3.2 全局解释器锁GIL:

    GIL是计算机程序设计语言解释器用于同步线程的一种机制,它使得任何时刻仅有一个线程在执行。即便在多核心处理器上,使用 GIL 的解释器也只允许同一时间执行一个线程。Python的Cpython解释器(普遍使用的解释器)使用GIL,在一个Python解释器进程内可以执行多线程程序,但每次一个线程执行时就会获得全局解释器锁,使得别的线程只能等待,由于GIL几乎释放的同时就会被原线程马上获得,那些等待线程可能刚唤醒,所以经常造成线程不平衡享受CPU资源,此时多线程的效率比单线程还要低下。在python的官方文档里,它是这样解释GIL的:

    In CPython, the global interpreter lock, or GIL, is a mutex that prevents multiple native threads from executing Python bytecodes at once. This lock is necessary mainly because CPython’s memory management is not thread-safe. (However, since the GIL exists, other features have grown to depend on the guarantees that it enforces.)

    可以说它的初衷是很好的,为了保证线程间的数据安全性;但是随着时代的发展,GIL却成为了python并行计算的最大障碍,但这个时候GIL已经遍布CPython的各个角落,修改它的工作量太大,特别是对这种开源性的语音来说。但幸好GIL只锁了线程,我们可以再新建解释器进程来实现并行,那这就是multiprocessing的工作了。

    3.3 multiprocessing

    multiprocessing是python里的多进程包,通过它,我们可以在python程序里建立多进程来执行任务,从而进行并行计算。官方文档如下所述:

    The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads.
    我们接下来介绍下multiprocessing的各个接口:

    3.3.1 进程process

    multiprocessing.Process(target=None,  args=())
        target: 可以被run()调用的函数,简单来说就是进程中运行的函数
        args: 是target的参数
    
    process的方法:
        start(): 开始启动进程,在创建process之后执行
        join([timeout]):阻塞目前父进程,直到调用join方法的进程执行完或超时(timeout),才继续执行父进程
        terminate():终止进程,不论进程有没有执行完,尽量少用。

    示例1

    from multiprocessing import Process
    
    def f(name):
        print 'hello', name
    
    if __name__ == '__main__':
        p = Process(target=f, args=('bob',)) # p进程执行f函数,参数为'bob',注意后面的“,”
        p.start() # 进程开始
        p.join() # 阻塞主线程,直至p进程执行结束

    3.3.2 进程池Process Pools

    class multiprocessing.Pool([processes])
        processes是进程池中的进程数,默认是本机的cpu数量
    方法:
        apply(func[, args[, kwds]])进程池中的进程进行func函数操作,操作时会阻塞进程,直至生成结果。
        apply_async(func[, args[, kwds[, callback]]])与apply类似,但是不会阻塞进程
        map(func, iterable[, chunksize])进程池中的进程进行映射操作
        map_async(func, iterable[, chunksize[, callback]])
        imap(func, iterable[, chunksize]):返回有序迭代器
        imap_unordered(func, iterable[, chunsize]):返回无序迭代器
        close():禁止进程池再接收任务
        terminate():强行终止进程池,不论是否有任务在执行
        join():在close()或terminate()之后进行,等待进程退出

    示例2

    from multiprocessing import Pool
    
    def f(x):
        return x*x
    
    if __name__ == '__main__':
        p = Pool(5) # 创建有5个进程的进程池
        print(p.map(f, [1, 2, 3])) # 将f函数的操作给进程池

    3.3.3 Pipes & Queues

    multiprocessing.Pipe([duplex])
        返回两个连接对象(conn1, conn2),两个连接对象分别访问pipe的头和尾,进行读写操作
        Duplex: True(default),创建的pipe是双向的,也即两端都可以进行读写;若为False,则pipe是单向的,仅可以在一端读,另一端写,此时与Queue类似。
    
    multiprocessing.Queue([maxsize])
        qsize():返回queuemember数量
        empty():如果queue是空的,则返回true
        full():如果queuemember数量达到maxsize,则返回true
        put(obj):将一个object放入到queueget():从队列中取出一个object并将它从queue中移除,FIFO原则
        close():关闭队列,并将缓存的object写入pipe

    示例

    from multiprocessing import Pool
    import time
    def f(x):
        return x*x
    if __name__ == '__main__':
        pool = Pool(processes=4)              # start 4 worker processes
        result = pool.apply_async(f, (10,))   # evaluate "f(10)" asynchronously in a single process
        print result.get(timeout=1)           # prints "100" unless your computer is *very* slow
        print pool.map(f, range(10))          # prints "[0, 1, 4,..., 81]"
        it = pool.imap(f, range(10))
        print it.next()                       # prints "0"
        print it.next()                       # prints "1"
        print it.next(timeout=1)              # prints "4" unless your computer is *very* slow
        result = pool.apply_async(time.sleep, (10,))
        print result.get(timeout=1)           # raises multiprocessing.TimeoutError

    3.3.4 进程锁multiprocessing.Lock

    当一个进程获得(acquire)锁之后,其它进程在想获得锁就会被禁止,可以保护数据,进行同步处理。
         acquire(block=True, timeout=None):尝试获取一个锁,如果blocktrue,则会在获得锁之后阻止其它进程再获取锁。
         release():释放锁

    3.3.5 共享内存——Value, Array

    共享内存通常需要配合进程锁来处理,保证处理的顺序相同。

    multiprocessing.Value(typecode_or_type, *args[, lock])
        返回一个ctype对象,
        创建c = Value(‘d’, 3.14),调用c.value()
    multiprocessing.Array(typecode_or_type, size_or_initializer, *, lock=True)
        返回一个ctype数组,只能是一维的
        Array(‘i’, [1, 2, 3, 4])
    Type codeC TypePython TypeMinimum size in bytes
    'b'signed charint1
    'B'unsigned charint1
    'u'Py_UNICODEUnicode character2
    'h'signed shortint2
    'H'unsigned shortint2
    'i'signed intint2
    'I'unsigned intint2
    'l'signed longint4
    'L'unsigned longint4
    'q'signed long longint8
    'Q'unsigned long longint8
    'f'floatfloat4
    'd'doublefloat8

    3.3.6 其它方法

    multiprocessing.active_children():返回当前进程的所有子进程
    multiprocessing.cpu_count():返回本计算机的cpu数量
    multiprocessing.current_process():返回当前进程

    3.3.7 注意事项:

    1. 尽量避免共享数据
    2. 所有对象都尽量是可以pickle的
    3. 避免使用terminate强行终止进程,以造成不可预料的后果
    4. 有队列的进程在终止前队列中的数据需要清空,join操作应放到queue清空后
    5. 明确给子进程传递资源、参数

    windows平台另需注意:

    • 注意跨模块全局变量的使用,可能被各个进程修改造成结果不统一
    • 主模块需要加上if name == 'main':来提高它的安全性,如果有交互界面,需要加上freeze_support()

    四、multiprocessing实战

    process、lock与value尝试:

    import multiprocessing as mp
    import time
    
    def job(v, num, l):
        l.acquire() # 锁住
        for _ in range(5):
            time.sleep(0.1) 
            v.value += num # 获取共享内存
            print(v.value)
        l.release() # 释放
    
    
    def multicore():
        l = mp.Lock() # 定义一个进程锁
        #l = 1
        v = mp.Value('i', 0) # 定义共享内存
        p1 = mp.Process(target=job, args=(v,1,l)) # 需要将lock传入
        p2 = mp.Process(target=job, args=(v,3,l)) 
        p1.start()
        p2.start()
        p1.join()
        p2.join()
    
    if __name__=='__main__':
        multicore()

    上述代码即对共享内存叠加5次,p1进程每次叠加1,p2进程每次叠加3,为了避免p1与p2在运行时抢夺共享数据v,在进程执行时锁住了该进程,从而保证了执行的顺序。我测试了三个案例:

    1. 直接运行上述代码输出[1, 2, 3, 4, 5, 8, 11, 14, 17, 20],运行时间为1.037s
    2. 在1的基础上注释掉锁(上述注释了三行),在没有锁的情况下,输出[1, 4, 5, 8, 9, 12, 13, 15, 14, 16],运行时间为0.53s
    3. 在2的基础上将p1.join()调到p2.start()前面,输出为[1, 2, 3, 4, 5, 8, 11, 14, 17, 20],运行时间为1.042s.

    可以发现,没锁的情况下调整join可以取得与加锁类似的结果,这是因为join即是阻塞主进程,直至当前进程结束才回到主进程,若将p1.join()放到p1.start()后面,则会马上阻塞主进程,使得p2要稍后才开始,这与锁的效果一样。
    如果如上述代码所示,p1.join()在p2.start()后面,虽然是p1先join(),但这时只是阻塞了主进程,而p2是兄弟进程,它已经开始了,p1就不能阻止它了,所以这时如果没锁的话p1与p2就是并行了,运行时间就是一半,但因为它们争抢共享变量,所以输出就变得不确定了。

    pool

    import multiprocessing as mp
    #import pdb
    
    def job(i):
        return i*i
    
    def multicore():
        pool = mp.Pool()
        #pdb.set_trace()
        res = pool.map(job, range(10))
        print(res)
        res = pool.apply_async(job, (2,))
        # 用get获得结果
        print(res.get())
        # 迭代器,i=0时apply一次,i=1时apply一次等等
        multi_res = [pool.apply_async(job, (i,)) for i in range(10)]
        # 从迭代器中取出
        print([res.get() for res in multi_res])
    
    multicore()

    pool其实非常好用,特别是map与apply_async。通过pool这个接口,我们只有指定可以并行的函数与函数参数列表,它就可以自动帮我们创建多进程池进行并行计算,真的不要太方便。pool特别适用于数据并行模型,假如是消息传递模型那还是建议自己通过process来创立进程吧。

    总结

    小子这次主要是按自己的理解把并行计算理了下,对进程、线程、CPU之间的关系做了下阐述,并把python的multiprocessing这个包拎了拎,个人感觉这个里面还大有学问,上次我一个师兄用python的process来控制单次迭代的运行时间(运行超时就跳过这次迭代,进入下一次迭代)也是让我涨了见识,后面还要多多学习啊。
    感谢您花费宝贵的时间阅读到这里,希望能有所收获,也欢迎在评论区进行交流。

    推荐好文:
    multiprocessing官方文档
    python多进程的理解 multiprocessing Process join run(推荐好文)
    多进程 Multiprocessing

    展开全文
  • 程序正确证明与并行程序设计

    千次阅读 2011-11-12 21:18:58
    程序正确证明与并行程序设计 (2011-08-20 20:27:59) 标签: 校园 分类: 工作篇 理论计算机科学   关于计算和计算机械的数学理论,也称为计算理论或计算机科学的数学基础。理论...
  • OS X上基于OpenMP进行并行程序开发

    千次阅读 2016-08-31 20:31:11
    OpenMP是目前被广泛接受的,用于共享内存并行系统的多处理器程序设计的一套指导的编译处理方案。它提供了对并行算法的高层的抽象描述。本文主要来讨论在OS X系统上利用GCC来开发基于OpenMP的并发程序的基本方法
  • 并行计算与MPI

    万次阅读 多人点赞 2019-06-01 16:54:08
    并行计算 1.1. 相关背景 (1)从1986年到2002年,微处理器的性能以平均50%的速度不断提升。但从2002年开始,单处理器的性能提升速度下降到每年大约20%,这个差距是巨大的。所以,从2005年起,大部分主流的CPU制造商...
  • 具有并行性的恰好是热点; 可扩展好; 易于实现; 为性能考虑,应当让所有的控制流尽量自由地运行。除非必要,尽可能不要对控制流的执行顺序做限制。 通常并行算法的设计设计几个部分:划分、通信、结果合并和...
  • 并行计算及并行算法

    万次阅读 多人点赞 2018-06-13 22:27:31
    一、并行计算  简单地说,并行计算就是在并行计算机上所做的计算。从普通意义上讲,它和常说的高性能计算、超级计算等是同义词。并行计算的初衷是为了努力仿真自然世界中一个序列中含有众多同时发生的、复杂且相关...
  • 什么是并行计算?

    万次阅读 多人点赞 2020-01-15 14:26:19
    最近项目需要实现程序并行化,刚好借着翻译这篇帖子的机会,了解和熟悉并行计算的基本概念和程序设计。帖子的原文见这里。 这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的...
  • java并行

    千次阅读 2019-08-13 15:55:58
    在java7之前,处理并行数据非常麻烦. 第一:你得明确的把包含的数据结构分成若干子部分. 第二:你要给每个子部分分配独立的线程. 第三:你需要在恰当的时候对他们进行同步,来避免不希望出现的竞争条件,等待所有线程完成,...
  • 不一样的排序算法【并行排序】

    千次阅读 2018-03-15 20:24:24
    大部分排序的程序都是串行的排序算法,比如冒泡排序,插入排序,选择排序,堆排序等等,但是随着计算机的发展,现在的计算机都是多核的处理器,串行排序无法高效的利用CPU,为了更加有效的利用CPU,我们在这里介绍...
  • 并行算法】并行循环

    千次阅读 2020-06-16 18:17:52
    一、循环的并行 在主要的程序结构中,循环结构一般是比较耗时的部分。如果可以并行执行循环,那么可以很大程度上提高Matlab程序的执行效率 ...编写Matlab并行程序时,有两种模式。利用Matlab提供的并行计算模块...
  • 并行计算与云计算有什么关系?

    千次阅读 2021-06-29 06:08:39
    在概述并行计算和云计算与什么关系之前,我们有必要先阐述一下并行计算、云计算等相关的概念,是大家对本文的内容能够理解更加透彻。1、并行计算并行计算其实早就有了,所有大型编程语言都支持多线程,多线程就是一...
  • MPI并行程序的调试技巧

    万次阅读 2014-05-19 22:06:49
    是的,你没有必要每个process都加,可以只针对有代表的process加上(例如你用到master-slave的架构那么就挑个master跟slave呗~)。 神马?「代表」很难选?! 我们可以把while循环改成: ```c while...
  • [并行计算] 1. 并行计算简介

    万次阅读 多人点赞 2017-07-20 15:30:07
    这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的先导。因此,它只涵盖了并行计算的基础知识,实用于刚刚开始熟悉该主题的初学者。
  • Java 8 - 并行流计算入门

    千次阅读 2021-03-23 23:06:39
    我们已经看到了新的 Stream 接口可以以声明方式处理数据集,无需显式实现优化来为数据集的处理加速。到目前为止,最重要的好处是可以对这些集合执行操作流水线,能够自动利用计算机上的多个内核。 在Java 7之前,...
  • 并发和并行的区别

    千次阅读 2020-03-05 21:18:35
    并发的实质是一个物理CPU(也可以多个物理CPU) 在若干道程序(或线程)之间多路复用,并发是对有限物理资源强制行使多用户共享以提高效率。 微观角度:所有的并发处理都有排队等候,唤醒,执行等这样的步骤,在微观...
  • CUDA C/C++ 教程一:加速应用程序

    千次阅读 多人点赞 2022-02-19 20:45:51
    文章目录1. CUDA简介2. 准备工作3. 加速系统4. 编写在GPU运行的代码4.1. 编写一个Hello GPU核函数5....近年来加速计算带来了越来越多的突破进展,应用程序对加速计算日益增长地需求、轻松编写加速计算的程序的.
  • 并行计算与集群技术

    千次阅读 2020-12-26 16:21:19
    第5章 并行计算与集群技术 并行计算(Parallel Computing) 也叫高性能计算(High Performance Computing) 、高端计算(High-end Parallel Computing) 或超级计算(Super Computing) .它的快速发展为其他技术、的发展...
  • 在项目程序已经完成好的情况下不需要大幅度的修改源代码,只需要加上专用的pragma来指明自己的意图,由此编译器可以自动将程序进行并行化,并在必要之处加入同步互斥以及通信。当选择忽略这些pragma,或者编译器不...
  • python_并行与并发、多线程

    千次阅读 2020-12-28 22:27:16
    轮询调度实现并发执行 程序1-8轮询完成,才再CPU上运行 问题三: 真正的并行需要依赖什么?并行需要的核心条件 多进程实现并行问题一: 什么是进程?计算机程序是存储在磁盘上的文件。只有把它们加载到内存中,并被...
  • 自九十年代开始,GPU的发展产生了较大的变化,NVIDIA、AMD(ATI)等GPU生产商敏锐的观察到GPU天生的并行性,经过他们对硬件和软件的改进,GPU的可编程能力不断提高,GPU通用计算应运而生。由于GPU具有比CPU强大的计算...
  • 串行测试 并行测试 随着技术的进步,随着组织从手动测试转向Selenium测试自动化 ,测试... 有些人不愿在Selenium中实施并行测试,而另一些人则不愿这样做,因为它们的Web应用程序足够小,可以由当前版本的窗口进行...
  • 指令级并行

    万次阅读 多人点赞 2018-07-02 16:49:08
    指令级并行流水线提高的是指令带宽(吞吐率),而不是单条指令的执行速度相关限制了流水线性能的发挥 结构相关:需要更多的硬件资源 数据相关:需要定向,编译器调度 控制相关:尽早检测条件,计算目标地址,延迟...
  • 串行、并行和并发

    千次阅读 2020-01-18 14:28:27
    串行、并行和并发 并行和并发 并发:1.一个处理器。2.逻辑上的同时运行 并行:2.多个处理器。2.物理上的同时运行 并发:一个咖啡机,交替 并行:多个咖啡机 并行:真正的“同时”运行,在同一时刻,有...
  • 并发和并行的理解

    千次阅读 2018-05-28 14:54:25
    软件开发,网站开发过程中经常有并发,并行这样的多线程处理与应用。因此,有必要对其进行了解与掌握。 多线程: 在了解线程之前,要先知道进程这个概念。进程是一个具有独立功能的程序关于某...
  • 并发、并行和协程

    千次阅读 2018-05-04 22:23:46
    几乎所有’正式’的程序都是多线程的,以便让用户或计算机不必等待,或者能够同时服务多个请求(如 Web 服务器),或增加性能和吞吐量(例如,通过对不同的数据集并行执行代码)。 并发和...
  • SQL Server 阻塞、死锁和最大并行

    千次阅读 2019-12-03 14:01:23
    1.阻塞 阻塞:是指当一个数据库会话中的事务,正在锁定其他会话事务想要读取或修改的资源,造成这些会话发出的请求进入等待的状态。SQL Server 默认会让被...但若设计不良的程序,就可能导致长时间的阻塞,这样就不...
  • 使用OpenMP并行化常见算法

    千次阅读 2020-02-10 22:22:09
    OpenMP并行化常见算法 openmp是强大的并行编译库,可以动态地设置多线程,使用方便。 这里我将以搜索算法为例,介绍如何用OpenMP把常见算法并行化。 旅行商问题 旅行商问题已经老生常谈了。指在有向带权图内,寻找一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 107,047
精华内容 42,818
热门标签
关键字:

并行程序的必要性