Pthreads 和递归

Question

我正在为接触一门新语言而进行的一项培训任务苦苦挣扎。不幸的是，这次新语言是旧语言，它是 C。我的编程任务是生成 Langford-Strings，这应该不是主要问题。

我在 C 中的第一次尝试，使用递归方法非常有效：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int grade = 0;
const char* blank = "_";
const char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void generate(int position, char* string) {

  if (!string) {
    string = calloc(grade*2+1, sizeof(char));
    for (int i = 0; i < grade*2; i++) {
      string = strcat(string, blank);
    }
  }

  if (!strstr(string, blank)) {
    printf("%s\n", string);
    return;
  }

  if (position < strlen(string)) {
    if (string[position] != *blank) {
      char* nstring = calloc(grade*2+1, sizeof(char));
      strcpy(nstring, string);
      generate(position+1, nstring);
      free(nstring);
      return;
    } else {
      for (int i = 0; i<strlen(string); i++) {
        if (strchr(string, alphabet[i])){
          continue;
        }

        int index = strcspn(alphabet, &alphabet[i])+1;
        if (position+index+1<strlen(string)) {
          if (string[position]==*blank) {
            if (string[position+index+1]==*blank) {
              char* nstring = calloc(grade*2+1, sizeof(char));
              strncat(nstring, string, position);
              strncat(nstring, &alphabet[i], 1);
              strncat(nstring, &string[position+1], index);
              strncat(nstring, &alphabet[i], 1);
              strcat(nstring, &string[position+2+index]);
              if (position<strlen(nstring)) {
                generate(position+1, nstring);
              }
              free(nstring);
            }
          }
        }
      }
    }
  }
}

int main(int argc, char* argv[]) {
  if (argc < 2) {
    printf("Missing parameter of langford strings grade!\n");
    return 1;
  }

  grade = strtol(argv[1], NULL, 10);
  if (grade % 4 != 0) {
    if ((grade+1) % 4 != 0) {
      printf("Grade must be multiple of 4 or one less\n");
      return 1;
    }
  }

  generate(0, NULL);
  return 0;
}

效果很好，完全符合我的预期。

但是当我尝试线程化（旧式线程化，在递归的每个级别上生成一个新线程）时，它不仅每次都以 seqfault 结束。它确实在不可预测的时间内以 seqfault 结束。这意味着，它无限期地运行，在 seqfaulting 之前打印出两倍和三倍的结果，并且总是随机数量的结果。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <signal.h>
#include <errno.h>

size_t grade = 0;
const char* blank = "_";
const char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

struct thread {
  pthread_t* thread;
  size_t position;
  struct thread* threads[26];
  char* string;
};

void* alloc_thread_data() {
  struct thread* ret = calloc(1, sizeof(struct thread));
  ret->thread = calloc(1, sizeof(pthread_t));
  ret->position = 0;
  ret->string = calloc((grade*2)+1, sizeof(char));
  return (void*)ret;
}

void free_thread_data(struct thread* dst) {
  free(dst->string);
  free(dst->thread);
  free(dst);
}

void assemble_string(char* dst, char* src, size_t pos, size_t index) {
  strncat(dst, src, pos);
  strncat(dst, &alphabet[index-1], 1);
  strncat(dst, &src[pos+1], index);
  strncat(dst, &alphabet[index-1], 1);
  strncat(dst, &src[pos+2+index], (grade*2)-pos+index+2);
}

void* generate(void* data) {
  struct thread* args = (struct thread*)data;

  if (args->string && strlen(args->string)==0) {
    for (size_t i = 0; i<grade*2; i++) {
      strcat(args->string, blank);
    }
  }

  if (args->string && !strstr(args->string, blank)) {
    printf("%s\n", args->string);
    return NULL;
  }

  if (args->string && args->position<strlen(args->string)) {
    size_t sub = 0;
    if (args->string[args->position]!=*blank) {
      args->threads[sub] = alloc_thread_data();
      strcpy(args->threads[sub]->string, args->string);
      args->threads[sub]->position = args->position+1;
      pthread_create(args->threads[sub]->thread, NULL, generate, (void*)args->threads[sub]);
      sub++;
    } else {
      for (size_t i = 0; i<grade*2; i++) {
        if (strchr(args->string, alphabet[i])){
          continue;
        }

        int index = strcspn(alphabet, &alphabet[i])+1;
        if (args->string[args->position] == *blank) {
          if (args->string[args->position+index+1] == *blank) {
            args->threads[sub] = alloc_thread_data();
            assemble_string(args->threads[sub]->string, args->string, args->position, index);
            args->threads[sub]->position = args->position+1;
            pthread_create(args->threads[sub]->thread, NULL, generate, (void*)args->threads[sub]);
            sub++;
          }
        }
      }
    }

    for (size_t i = 0; i<sub; i++) {
      if (args->threads[i]->thread!=NULL) {
        if(pthread_kill(*args->threads[i]->thread, 0)==0) {
          pthread_join(*args->threads[i]->thread, NULL);
        }

        free_thread_data(args->threads[i]);
      }
    }
  }

  return NULL;
}

int main(int argc, char* argv[]) {
  if (argc < 2) {
    printf("Missing parameter of langford strings grade!\n");
    return 1;
  }

  grade = strtol(argv[1], NULL, 10);
  if (grade % 4 != 0) {
    if ((grade+1) % 4 != 0) {
      printf("Grade must be multiple of 4 or one less\n");
      return 2;
    }
  }

  struct thread* args = alloc_thread_data();
  pthread_create(args->thread, NULL, generate, (void*)args);
  if(pthread_kill(*args->thread, 0)==0) {
    pthread_join(*args->thread, NULL);
  }

  free_thread_data(args);
}

因此，如前所述，我设法在我的整个工作生活中绕过 C 编程，这样做只是为了好玩 - 所以我不希望我的代码有点全面。请帮助我找出线程方法有什么问题（当然，如果您在第一个方法中也看到任何众所周知的代码）。欢迎任何提示。

Answer 1

我可以诚挚地建议 它绝对没有意义（对我来说，至少......） "spawn a new thread" 这里？

唯一 "spawn a thread" 的原因是当您希望执行两个 此后，独立 活动，而这个算法显然没有。

发生段错误的直接原因是各种线程都在尝试操作相同的数据，而不考虑彼此，也不等待彼此。但是，恕我直言，问题的根本原因是......整个场景都是 胡说八道。 "Recursion" 和 "multi-threading" 根本不是一回事。如果您的 objective 在这里是为了学习线程，恐怕您刚刚学到的 （非常困难的方法） 比您想知道的要多得多。 . .

Answer 2

除了@EugeneSh 的错误配置。指出，这看起来像个问题：

pthread_create(args->threads[sub]->thread, NULL, generate,
        (void*)&args->threads[sub]);

注意与同样出现的其他调用的区别：

pthread_create(args->threads[sub]->thread, NULL, generate,
        (void*)args->threads[sub]);

[为了清晰和易于阅读，插入了换行符并标准化了缩进]。

args->threads[sub] 是一个 struct thread*。您想将该指针本身传递给 pthread_create()，如第二种情况，而不是它的地址，如第一种情况。

总的来说，我倾向于同意@MikeRobinson 的观点，即您对线程的使用不当。在你的进程中拥有比核心更多的可调度线程在性能方面从来没有用处，并且你可以非常快速地扩展到数千个总线程。我非常怀疑结果是否会优于您的单线程解决方案 - 上下文切换和缓存抖动的成本肯定会导致您可能会淹没您可能拥有的 4 - 12 核并行执行所获得的任何加速。

已添加：

此外，检查函数调用的值 return 以获取错误代码非常重要，除非您不关心也不需要关心调用是否成功。特别是，你应该检查

您的 malloc() / calloc() 调用的 return 值 -- 这些 return NULL 在分配不成功的情况下，并且随着您执行的总分配次数的增加，其中一些可能会失败。使用生成的 NULL 指针很容易导致段错误
您的 pthread_create() 调用的 return 值 -- 这些 return 在失败时不同于 0 的值。之后依赖 pthread_kill() 来确定线程是否创建成功是不安全的，因为失败的 pthread_create() 会留下线程句柄的内容 undefined。因此，任何依赖于句柄值的后续评估都会表现出未定义的行为。

我也有点怀疑你所有的 strncat()ing，因为这是一个臭名昭著的字符串溢出源。如果目标字符串有足够的容量，这些都可以，但我很难判断它们是否总是适合您的情况。

Pthreads 和递归

Pthreads and recursion

c

multithreading

pthreads

已添加：