c - 多线程向列表无限循环插入元素

Question

我是 C 编程和多线程的新手，我正在尝试编写一个程序来创建多个线程，并让每个线程将一个元素插入到带有虚拟节点的排序双向链表中。我的项目的目的实际上是同步链表的插入、删除、查找功能，但由于这个错误，我什至无法达到竞争条件的程度。这是我的代码。

//---------------------In a header file------------------


struct SortedListNode
{
    struct SortedListElement *prev;
    struct SortedListElement *next;
    const char *key;
};

typedef struct SortedListNode SortedList_t;
typedef struct SortedListNode SortedListElement_t;


void SortedList_insert(SortedList_t *list, SortedListElement_t *element)
{
    if (list->next == NULL && list->prev == NULL)
    {
        list->next = element;
        list->prev = element;
        element->next = list;
        element->prev = list;
        return;
    }

    int flag = 0;
    SortedListElement_t *currElement = list;
    while (flag == 0)
    {
        if (currElement->key == NULL)
        {
            currElement = currElement->next;
        }
        else if (strcmp(element->key,currElement->key) <=0)
        {
            element->prev = currElement->prev;
            element->next = currElement;
            currElement->prev->next = element;
            currElement->prev = element;
            flag = 1;
        }
        else if (currElement->next->key == NULL)
        {
            currElement->next = element;
            list->prev = element;
            element->next = list;
            element->prev = currElement;
            flag = 1;



        }
        else
        {
            currElement = currElement->next;
        }
    }
    return;
}

//-----------------------------In the source file----------------------

struct arg_struct {
  SortedList_t *list;
  SortedListElement_t ** element_array;
};

int num_iterations=10;

int main(int argc, char * argv[])
{


  int num_threads = 2;


  pthread_t threads[num_threads];

  struct arg_struct args;
  args.list = (SortedList_t *)malloc(sizeof(SortedList_t));
  args.list->next = NULL;
  args.list->prev = NULL;
  args.list->key = NULL;

  SortedListElement_t *element_array[(num_threads * num_iterations)];

  char * tempKey[(num_threads * num_iterations)];

  int i=0;
  for(i=0;i < (num_threads * num_iterations); i++)
  {
    element_array[i] = (SortedList_t *)malloc(sizeof(SortedList_t));
    element_array[i]->next = NULL;
    element_array[i]->prev = NULL;
    tempKey[i] = (char*)malloc(3 * sizeof(char));
    random_key_generator(tempKey[i],3);
    element_array[i]->key = tempKey[i];
  }

  args.element_array = element_array;


    for(int i=0;i <num_threads;i++)
    {

      pthread_create(&threads[i],NULL,&aux_operations, (void *) &args);
    }

      for(int i=0;i <num_threads;i++)
        pthread_join(threads[i], NULL);


  return 0;
}

void random_key_generator(char *dest,size_t length)
{
  char charset[] = "0123456789"
  "abcdefghijklmnopqrstuvwxyz"
  "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  while (length-- > 0) {
    size_t index = (double) rand() / RAND_MAX * (sizeof charset - 1);
    *dest++ = charset[index];
  }
  *dest = '\0';
}

void *aux_operations(void *arguments)
{

  struct arg_struct *args = arguments;
  int i=0;
  for(i=0;i<num_iterations;i++)
    SortedList_insert(args->list,args->element_array[i]);
}

当仅使用 1 个线程时，程序可以正常工作，但当使用超过 1 个线程时，程序会陷入 SortedList_insert 函数内的无限循环。我不确定是我的 SortedList_insert 实现导致了错误还是我处理线程的方式。

Answer 1

我没有看到您对列表或元素进行任何锁定。

多线程程序(进程)有多个“并行”执行的线程，这意味着操作系统的调度程序为每个线程分配一个时间片，并在该时间片结束时抢占它并给另一个进程(线程)时间片。

这意味着当插入正在进行时，执行插入的线程可能会被抢占。插入不完整。如果另一个线程现在对列表进行操作，它可能会发现列表是无序的。现在将发生未定义的行为。

因此您必须锁定正在处理的列表或元素。我不是线程专家，因此无法为您提供用于锁定列表的函数名称(例如信号量之类的东西可以完成这项工作)。