c - 线程内的线程？

Question

我想使用 pthread 实现分而治之，但我不知道如果我在一个线程中创建更多线程会发生什么。

根据我的理解，如果机器有一个2核处理器，它只能同时处理2个线程。如果线程多于2个，其他线程要等待资源，所以如果我在深入的时候创建越来越多的线程，实际上可能不会提高算法的速度，因为只能处理2个线程同时。

我在网上做了一些研究，似乎上层的线程可能处于非活动状态，只有最深层次的线程保持活动状态。如何做到这一点？此外，如果面线保持不活动状态，是否会影响底线？

Answer 1

有两种基本类型：分离式和可连接式。

可连接线程是您可以等待（或访问）终止使用的线程pthread_join。

使用多于内核的线程可能会有所帮助或有害 - 取决于您的程序！使用多线程来最小化或消除对资源的竞争通常是件好事。在程序中抛出太多线程实际上会减慢进程。但是，如果内核数与线程数匹配并且其中一个线程正在等待磁盘 IO（假设其他进程中没有发生任何重大事件），您可能会有空闲的 CPU 时间。

上层的线程可以不活动，只有最深的线程保持活动。如何做到这一点？

使用可连接线程，您可以完成您概述的嵌套线程方法，这在几个教程中进行了演示。基本流程是一个线程将创建一个或多个工作人员，并使用pthread_join. 但是，在大多数情况下，任务和线程池等替代方案更可取。

然而，这种方法不太可能是执行的最佳方法，因为它与硬件和调度操作没有关联（很好），特别是随着程序的深度和宽度的增长。

如果面线保持不活动状态，不会影响底线吗？

是的。然而，典型的问题是工作/线程不受限制。使用您概述的方法，很容易产生许多线程，并且为必须在有限数量的内核上执行的工作拥有大量不合逻辑的线程。因此，您的程序将浪费大量时间上下文切换和等待线程完成。创建许多线程也可能会浪费/保留大量资源，尤其是在它们短暂和/或空闲/等待的情况下。

因此，如果我在更深入的同时创建越来越多的线程，实际上它可能不会提高算法的速度，因为只能同时处理 2 个线程。

这表明使用这种方法创建线程是有缺陷的。您可能想要创建一些线程，并使用基于任务的方法——每个线程从集合中请求并执行任务。创建线程需要大量时间和资源。

Answer 2

如果您尝试进行双向分而治之，产生两个孩子并等待他们完成，您可能需要类似的东西：

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  pthread_create (left_child, NULL, routine, left_arg);
  pthread_create (right_child, NULL, routine, right_arg);

  /* wait for 'children' */
  pthread_join (left_child, &left_return_val);
  pthread_join (right_child, &right_return_val);

  /* merge results & return */
}

一个轻微的改进是，“父线程”不是休眠，而是同步地完成右子线程的工作，并产生更少的线程：

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  pthread_create (left_child, NULL, routine, left_arg);
  /* do the right_child's work yourself */
  right_return_val = routine (right_arg);

  /* wait for 'left child' */
  pthread_join (left_child, &left_return_val);

  /* merge results & return */
}

但是，当你深入 N 级时，你有不少孩子。获得的加速实际上取决于 CPU 在实际处理上花费的时间，以及等待 I/O 的时间等。如果您知道在具有P内核的机器上，您只能通过kP线程获得良好的加速，然后您可以设置线程的“工作池” kP，并继续重用它们，而不是像上面那样产生线程。这样，一旦kP产生了线程，就不会产生更多：

THREAD_POOL pool = new_thread_pool (k * P); /* I made this function up */

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  left_thread = get_worker (pool); /* Blocks until a thread is free  */
  /* get left_thread to do processing for you */

  right_thread = get_worker (pool); /* Blocks until a thread is free  */
  /* get right_thread to do processing for you */

  /* wait for 'children' */
  pthread_join (left_child, &left_return_val);
  pthread_join (right_child, &right_return_val);

  /* return the workers */
  put_worker (pool, left_thread);
  put_worker (pool, right_thread);

  /* merge results & return */
}

Answer 3

您应该能够创建比系统中的内核更多的线程。操作系统将确保每个线程都获得 CPU 的一部分来完成其工作。

但是，您可以创建的线程数 [可能] 有一个上限（请查看您的操作系统文档）。

因此，如果您在具有 2 个内核的系统中创建 5 个线程，那么每个线程将获得大约 40% 的 cpu（平均）。这并不是说一个线程必须等到另一个线程完全完成。当然，除非你使用锁。

当您使用锁来保护数据不被多个线程更改或访问时，可能会出现许多问题。典型的问题是：

• 死锁：线程 1 等待被线程 2 锁定的东西；线程 2 等待被线程 1 锁定的东西
• lock convoy：多个线程都在等待同一个锁
• 优先级反转：线程 1 对线程 2 具有优先级，但由于线程 2 大部分时间都有锁，所以线程 1 仍然要等待线程 2

我找到了这个页面（http://ashishkhandelwal.arkutil.com/index.php/csharp-c/issues-with-multithreaded-programming-part-1/），这可能是多线程编程的一个好的开始。