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

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

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

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

}