c - 检测线程安全链表中的死锁

Question

我最近做了一个作业，要实现一个线程安全的单链表，它可以手动锁定元素，这意味着列表中的每个元素都有一个锁。我实现了所有功能并测试了它们，而无需处理有问题的线程情况，它们都有效，但我想测试是否存在死锁或饥饿的情况，但我不知道该怎么做，我可以通过查看我的代码知道我是否可能遇到死锁或饥饿？我也不确定代码中是否需要这么多的锁定和解锁。请注意，在每个函数中，我都锁定了一个元素及其后继元素，这就足够了吗？如果我的代码容易出现死锁和饥饿或任何其他问题，有什么帮助或建议吗？我将在下面发布我的代码。提前致谢。

并发列表.h：

typedef struct node node;
typedef struct list list;

list* create_list();
void delete_list(list* list);
void print_list(list* list);
void insert_value(list* list, int value);
void remove_value(list* list, int value);
void count_list(list* list, int (*predicate)(int));

并发列表.c：

 #include <pthread.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <limits.h>
 #include "concurrent_list.h"

struct node {
  int value;
  node* next;
  pthread_mutex_t lock; // hand over hand implies a lock for every node
};

struct list {
  node* head;
};

// print the value of a node
void print_node(node* node)
{
  if(node)
  {
    printf("%d ", node->value);
  }

}

// create  a new empty list
list* create_list()
{
    list* l =(list*)malloc(sizeof(list));

    if(l == NULL) return NULL;

    l->head = NULL;

    return l;
}

// delete the entire list
void delete_list(list* list)
{
  if(list == NULL) return; // if list pointer is NULL then do nothing

  node* current = list->head;

  if(current == NULL) return; // if list head is NULL then do nothing

  pthread_mutex_lock(&(current->lock)); // lock list head

  node* temp = current->next;
  node* dummy;

  if(temp == NULL) // delete the only element in the list
  {
     pthread_mutex_unlock(&(current->lock));
     pthread_mutex_destroy(&(current->lock));
     free(current);
     return;
  }

  pthread_mutex_lock(&(temp->lock)); //lock successor of the head

  while (1)
  {
     pthread_mutex_unlock(&(current->lock)); // unlock current node
     dummy = current;
     current = temp; // current becomes it's successor
     pthread_mutex_destroy(&(dummy->lock));
     free(dummy); // free dummy because it is a pointer to current
     temp = temp->next; // current becomes it's successor
     if(temp == NULL) break; // exit loop if we are at the end of the 
     list
     pthread_mutex_lock(&(temp->lock)); // lock current's successor
  }

     pthread_mutex_unlock(&(current->lock));
     pthread_mutex_destroy(&(current->lock));
     free(current); // free the last element in the list
     list->head = NULL;
     free(list); // free the list
  }

  // insert function for a new value if a value already exists then do 
  nothing
  void insert_value(list* list, int value)
  {
     if(list == NULL) return; // if list pointer is NULL then do nothing

     node* new_node = malloc(sizeof(node)); // create new node

     if(new_node == NULL) return; // check if allocation fails

     new_node->value = value;

     new_node->next = NULL;

     pthread_mutex_init(&(new_node->lock),NULL);  // initialize fast mutex lock for the new node

     pthread_mutex_lock(&(new_node->lock)); // lock the new node

     if(list->head == NULL) // new node is the first element in the list
     {
        new_node->next = NULL;
        list->head = new_node;
        pthread_mutex_unlock(&(new_node->lock));
        return;
     }

      pthread_mutex_lock(&(list->head->lock)); // lock the head of the list

      node* temp;

      if(list->head->value >= new_node->value) // new node comes before the list head
     {
       new_node->next = list->head;
       temp = list->head;
       list->head = new_node;
       pthread_mutex_unlock(&(list->head->lock));
       pthread_mutex_unlock(&(temp->lock));
       return;
     }

    else
    {
      // Locate the node before the point of insertion //

     node* dummy;
     node* current = list->head;
     temp = current->next;

     if(temp == NULL) // new node comes after the list head
     {
         new_node->next = current->next;
         current->next = new_node;
         pthread_mutex_unlock(&(new_node->lock));
         pthread_mutex_unlock(&(current->lock));
         return;
     }

    pthread_mutex_lock(&(temp->lock)); // lock the successor of the head

  // perform hand over hand traversal of the list
  // and check if temp reaches the end of the list (NULL)

   while (temp->value < new_node->value)
   {
     pthread_mutex_unlock(&(current->lock));
     current = temp;
     temp = temp->next;
     if(temp == NULL) break;
     pthread_mutex_lock(&(temp->lock));
   }

   if(temp == NULL) // new node will be the last element in this case
   {
       current->next = new_node;
       new_node->next = NULL;
       pthread_mutex_unlock(&(current->lock));
       pthread_mutex_unlock(&(new_node->lock));
       return;
   }

   else // new node should be inserted inside the list
   {
       dummy = temp;
       new_node->next = current->next;
       current->next = new_node;
       pthread_mutex_unlock(&(dummy->lock));
       pthread_mutex_unlock(&(current->lock));
       pthread_mutex_unlock(&(new_node->lock));
       return;
   }
 }
}

 //delete the first appearance of a value in the list if it exists in the list
    void remove_value(list* list, int value)
    {
      if(list == NULL) return; // if list pointer is NULL then do nothing

      node* temp;
      node* current = list->head;

      if(current == NULL) return; // if list head is NULL then just go to a new line

     pthread_mutex_lock(&(current->lock)); // lock the head of the list

     if(current->value == value) // delete the head of list if it's value is equal to given value
    {
        temp = current;
        list->head = current->next;
        pthread_mutex_unlock(&(temp->lock));
        pthread_mutex_destroy(&(temp->lock));
       free(temp);
       return;
   }

    else
   {
       temp = current->next;

       if(temp == NULL)
       {
           pthread_mutex_unlock(&(current->lock));
           return;
       }

       pthread_mutex_lock(&(temp->lock)); // lock the successor of the head

        // perform hand over hand traversal of the list
       //  and check if temp reaches the end of the list (NULL)

    while (temp->value != value) // find the first appearance of a node 
    that has a value the same as the one given
        {
          pthread_mutex_unlock(&(current->lock));
          current = temp;
          temp = temp->next;
          if(temp == NULL) break;
          pthread_mutex_lock(&(temp->lock));
        }

         if(temp == NULL) // value not found
        {
            pthread_mutex_unlock(&(current->lock));
            return;
        }

        else // delete the suitable node
        {
            current->next = temp->next;
            pthread_mutex_unlock(&(current->lock));
            pthread_mutex_unlock(&(temp->lock));
            pthread_mutex_destroy(&(temp->lock));
            free(temp);
           return;
        }
    }
}

 //print the entire list
 void print_list(list* list)
 {
  if(list == NULL) // if list pointer is NULL then just go to a new line
  {
      printf("\n");
      return;
  }

      node* current = list->head;

      if(current == NULL) // if list head is NULL then just go to a new line
      {
         printf("\n");
         return;
      }

      pthread_mutex_lock(&(current->lock)); // lock the head of the list

      print_node(current); // print the head of the list

      node* temp = current->next;

      if(temp == NULL) // a list with 1 element
      {
         printf("\n");
         pthread_mutex_unlock(&(current->lock));
         return;
      }

     pthread_mutex_lock(&(temp->lock)); // lock the list head's successor

    while (1)
    {
       pthread_mutex_unlock(&(current->lock)); // unlock current node
       current = temp; // current becomes it's successor
       print_node(current); // print current node
       temp = temp->next; // // temp becomes it's successor
       if(temp == NULL) break; // exit loop if we reach the end of the list
      pthread_mutex_lock(&(temp->lock)); // lock temp
   }

    pthread_mutex_unlock(&(current->lock)); // unlock the last list 
    element
   printf("\n");
}

 // print how many nodes in the list satisfy a given predicate function
 void count_list(list* list, int (*predicate)(int))
 {

   int count = 0;

   if(list == NULL) // if list pointer is NULL then print that count = 
   0 and finish
   {
      printf("%d items were counted\n", count);
      return;
   }

   node* current = list->head;

   if(current == NULL) // if list head is NULL then print that count = 
   0 and finish
   {
       printf("%d items were counted\n", count);
       return;
   }

   pthread_mutex_lock(&(current->lock)); // lock the list head

   if(predicate(current->value)) count++; // check the predicate for 
   the list head

   node* temp = current->next;

   if(temp == NULL) // list has only 1 element
   {
      pthread_mutex_unlock(&(current->lock));
      printf("%d items were counted\n", count);
      return;
   }

   pthread_mutex_lock(&(temp->lock)); // lock the list head's successor

   while (1)
  {
    pthread_mutex_unlock(&(current->lock)); // unlock current node
    current = temp; // current becomes it's successor
    if(predicate(current->value)) count++; // check predicate for current node
    temp = temp->next; // // temp becomes it's successor
    if(temp == NULL) break; // exit loop if we reach the end of the list
    pthread_mutex_lock(&(temp->lock)); // lock temp
   }

   pthread_mutex_unlock(&(current->lock)); // unlock the last list element

   printf("%d items were counted\n", count); // print count
}

标签： clinked-listthread-safetydeadlock

Answer 1

该列表的用户代码总是存在死锁的风险（死锁本身或与其他用户代码相互死锁）。你无法避免这种情况。

在考虑列表代码本身是否可能存在死锁之前，必须更正代码：

列表本身未锁定。head无法安全地更换。

在delete_list：

• 在单条目列表的情况下（temp == NULL）：您解锁然后释放：这是使锁无效的竞争。此外，无论如何都不需要解锁，因为该内存将被释放。
• 类似地，对于列表包含更多元素的情况，但您也会在解锁后找到后继（注意，其他一些线程可能会看到解锁并更改后继指针，然后第一个线程继续使用错误的后继运行）

我没有继续，但猜测其余代码中存在类似问题。这些问题应该在发现死锁之前解决。