Вложенные блокировки односвязного списка

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

Структура для блокировки имеет вид:

typedef struct node1 { 

  int value; 

  struct node1 *link;

  pthread_mutex_t lock; 

} node1_t;

Чтобы удалить узел из списка, необходимо выполнить следующие действия:

• провести поиск в списке, начиная с ListHead, пока не будет найден нужный узел;
• необходимо запирать каждый узел перед доступом к его содержимому, чтобы защитить список от эффектов параллельного удаления узлов. Поскольку поиск всегда начинается с ListHead, тупик не возникнет, поскольку блокировки осуществляются в одном и том же порядке;
• обнаружить нужный узел, чтобы запирался и этот узел и его предшественник, так как изменения коснутся обоих узлов. Вследствие того, что предшественник всегда блокируется первым, тупик предотвращается.

node1_t *delete(int value) {

  node1_t *prev,

  *current; prev = &ListHead;

  pthread_mutex_lock(&prev->lock); 

  while ((current = prev->link) != NULL) {

      pthread_mutex_lock(&current->lock); 

      if (current->value == value) {

         prev->link = current->link;

         pthread_mutex_unlock(&current->lock); 

         pthread_mutex_unlock(&prev->lock);

         current->link = NULL;

         return(current); 

      } 

      pthread_mutex_unlock(&prev->lock);

      prev = current; 

  } 

  pthread_mutex_unlock(&prev->lock); 

  return(NULL); 

}