Search⌘ K
Home
Courses
Operating Systems: Virtualization, Concurrency & Persistence

Concurrent Linked Lists

Explore how to manage concurrency in linked lists by using locks effectively during insert operations while handling memory allocation failures. Understand code structuring to minimize locking errors and investigate hand-over-hand locking to improve concurrency, along with its practical performance trade-offs.

We'll cover the following...

You will now examine a more complicated structure, the linked list. Let’s start with a basic approach once again. For simplicity, we’ll omit some of the obvious routines that such a list would have and just focus on concurrent insert; we’ll leave it to the reader to think about lookup, delete, and so forth. The code excerpt below shows the code for this rudimentary data structure.

C
// basic node structure
typedef struct __node_t{
  int key;
  struct __node_t *next;
} node_t;
// basic list structure (one used per list)
typedef struct __list_t{
  node_t *head; 
  pthread_mutex_t lock;
} list_t;
void List_Init(list_t *L) {
    L->head = NULL;
    pthread_mutex_init(&L->lock, NULL);
}
int List_Insert(list_t *L, int key) {
  pthread_mutex_lock(&L->lock);
  node_t *new = malloc(sizeof(node_t));
  if (new == NULL) {
      perror("malloc");
      pthread_mutex_unlock(&L->lock);
      return -1; // fail
  }
  new->key  = key;
  new->next = L->head;
  L->head   = new;
  pthread_mutex_unlock(&L->lock);
  return 0; // success
}
int List_Lookup(list_t *L, int key) {
  pthread_mutex_lock(&L->lock);
  node_t *curr = L->head;
  while (curr) {
    if (curr->key == key) {
      pthread_mutex_unlock(&L->lock);
      return 0; // success
    }
    curr = curr->next;
  }
  pthread_mutex_unlock(&L->lock);
  return -1; // failure
}

As you can see in the code, the code simply acquires a lock in the insert routine upon entry and releases it upon exit. One small tricky issue arises if malloc() happens to fail (a rare case); in this case, the code must also release the lock before failing the insert.

This kind of exceptional control flow is quite error-prone; a recent study of Linux kernel patches found that a huge fraction of bugs (nearly 40%) are found on such rarely-taken code paths (indeed, this observation sparked some of ...