Previous: Finding the Minimum Element Up: Examples

Multiple-Reader Multiple-Writer Linked List

This example defines a class that implements a linked list of integers. This class can be shared by multiple processes adding elements to the list (writers) and multiple processes making removals from the list (readers).

#include <iostream.h>

class List;

class ListNode  {
  private:
    int data;
    ListNode* next;

    ListNode (int d)
    {
      data = d;
      next = NULL;
    }
  friend class List;
};

class List  {
  private:
    ListNode* head;
    ListNode* tail;

  public:
    List (void)
    {
      head = new ListNode(0);
      tail = head;
    }

    atomic void append (int a)
    {
      ListNode* addition = new ListNode(a);
      tail->next = addition;
      tail = addition;
    }

    atomic int remove (int& item)
    {
      if (head==tail)
        return 0;
      else  {
        ListNode* old_head = head;
        head = head->next;
        delete old_head;
        item = head->data;
        return 1;
      }
    }
};

List L;

void producer (int id, int n)
{
  for (int i=0; i<n; i++)
    L.append(id*n+i);
}

int consumer (int id, int n)  
{
  int item;
  int sum = 0;
  for (int i=0; i<n; i++)
    if (L.remove(item) == 1)
      sum += item;
  return sum;
}

int main()
{
  par  {
    producer(0,10);
    producer(1,10);
  }
  int sum0, sum1;
  par  {
    sum0 = consumer(0,10);
    sum1 = consumer(1,10);
  }
  cout << "Sum of list received by consumer 0: " << sum0 << endl;
  cout << "Sum of list received by consumer 1: " << sum1 << endl;
  return 0;
}

Because modifications (appends and removals) to this list are atomic, an object of this list class can be shared between multiple threads of control. Instances of an append() operation and a remove() operation are guaranteed not to interfere with each other, or with other instances of the same operation. Thus, in the examples, two producers can safely be composed in parallel, as can two consumers. The result of the composition of these two producers is a linked list containing the integers 0 to 9 (in that order) interleaved with the integers 10 to 19. The language definition says nothing about how these two sequences will be interleaved (though a particular implementation may have a specific strategy).