c - 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 结束。它确实在不可预测的时间内以序列错误结束。这意味着，它会无限期地运行，在出现 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

除了@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 个核心上并行执行所获得的任何加速。

添加:

此外，检查函数调用返回的值中是否有错误代码非常重要，除非您不关心也不需要关心调用是否成功。特别是，您应该检查

• malloc()/calloc() 调用的返回值 - 如果不成功，这些值将返回 NULL分配，并且执行的总分配与您执行的总分配一样多，其中一些分配可能会失败。使用生成的 NULL 指针很容易导致段错误

• pthread_create() 调用的返回值——如果失败，它们将返回一个不同于 0 的值。之后依赖 pthread_kill() 来确定线程是否已成功创建是不安全的，因为失败的 pthread_create() 会使线程句柄的内容未定义。因此，任何依赖于句柄值的后续计算都会表现出未定义的行为。

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