Обнаружение взаимоблокировок в поточно-связанном списке

Question

Недавно я получил домашнее задание для реализации поточно-ориентированного односвязного списка, который блокирует элементы в ручном методе, что означает, что для каждого элемента в списке есть отдельная блокировка. Я реализовал все функции и протестировал их без необходимостииметь дело с проблемными ситуациями с потоками, и все они работали, но я хотел проверить, не может ли быть ситуация тупика или голодания, но я не знаю, как это сделать, и могу ли я узнать по своему коду, есть ли у меня тупик илиголод?Я также не уверен, что там должно быть столько блокировок и разблокировок в коде.Обратите внимание, что в каждой функции я блокирую элемент и его преемника, достаточно ли этого?Любая помощь или предложение относительно моего кода, если он склонен к тупикам и голоданию или любым другим проблемам?Я опубликую свой код ниже.Заранее спасибо.

concurrent_list.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));

concurrent_list.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
}

Answer 1

Я думаю, что вы чрезмерно усложнили проблему и, в результате, есть несколько ситуаций, когда вы все равно попадете в одновременно обновляемый список.

Например, в вашем insert_value есть следующие строки перед тем, как заблокировать заголовок списка:

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

это может вызвать проблемы, если другой поток попытается удалить заголовок одновременно. Возможно, есть и другие.

Во многих случаях вы блокируете значение new там, где оно не нужно, потому что значение создано потоком и еще не передано.

Обычно вы используете один мьютекс для всего списка, если вы выполняете операции со списком. блокировка элементов может потребоваться, если вы разрешите одновременную модификацию элемента.

Полагаю, в вашем случае для большинства операций будет достаточно блокировки только элемента head.

Answer 2

Всегда существует риск, что код пользователя из этого списка будет заблокирован (сам по себе или взаимно с другим кодом пользователя). Вы не можете защитить от этого.

Прежде чем подумать о том, возможны ли взаимоблокировки в самом коде списка, необходимо исправить код:

Сам список не заблокирован. Замена head не может быть безопасно выполнена.

В delete_list:

• в случае списка с одним входом (temp == NULL): вы разблокируете, а затем освобождаете: это гонка, которая делает недействительной блокировку. Кроме того, в любом случае нет необходимости разблокировать, поскольку эта память будет освобождена.
• аналогично для случая, когда список содержит больше элементов, но вы также узнаете преемника после разблокировки (обратите внимание, что какой-то другой поток может увидеть разблокировку и изменить указатель преемника, тогда первый поток продолжает работать с неправильным преемник)

Я не продолжил, но думаю, что в остальной части кода есть похожие проблемы. Эти проблемы должны быть исправлены до нахождения тупиков.