Operating Systems: Virtualization, Concurrency & Persistence/

...

/

Concurrent Counters

Concurrent Counters

This lesson explains how to make a simple data structure like a counter thread safe while ensuring good performance.

We'll cover the following...

One of the simplest data structures is a counter. It is a structure that is commonly used and has a simple interface. We define a simple non-concurrent counter in the code excerpt below.

Press + to interact
typedef struct __counter_t {
    int value;
} counter_t;
void init(counter_t *c) {
    c->value = 0;
}
void increment(counter_t *c) {
    c->value++;
}
void decrement(counter_t *c) {
    c->value--;
}
int get(counter_t *c) {
    return c->value;
}

Simple but not scalable

As you can see, the non-synchronized counter is a trivial data structure, requiring a tiny amount of code to implement. We now have our next challenge: how can we make this code thread safe? The code excerpt below shows how we do so.

Press + to interact
typedef struct __counter_t {
  int             value;
  pthread_mutex_t lock;
} counter_t;
void init(counter_t *c) {
  c->value = 0;
  Pthread_mutex_init(&c->lock, NULL);
}
void increment(counter_t *c) {
  Pthread_mutex_lock(&c->lock);
  c->value++;
  Pthread_mutex_unlock(&c->lock);
}
void decrement(counter_t *c) {
  Pthread_mutex_lock(&c->lock);
  c->value--;
  Pthread_mutex_unlock(&c->lock);
}
int get(counter_t *c) {
  Pthread_mutex_lock(&c->lock);
  int rc = c->value;
  Pthread_mutex_unlock(&c->lock);
  return rc;
}

This concurrent counter is simple and works correctly. In fact, it follows a design pattern common to the simplest and most basic concurrent data structures: it simply adds a single lock, which is acquired when calling a routine that manipulates the data structure, and is released when returning from the call. In this manner, it is similar to a data structure built with monitors“Operating System Principles” by Per Brinch Hansen. Prentice-Hall, 1973. Available: http://portal.acm.org/citation.cfm?id=540365. One of the first books on operating systems; certainly ahead of its time. Introduced monitors as a concurrency primitive., where locks are acquired and released automatically as you call and return from object methods.

At this point, you have a working concurrent data structure. The problem you might have is performance. If your data structure is too slow, you’ll have to do more than just add a single lock; such optimizations, if needed, are thus the topic of the rest of the chapter. Note that if the data structure is not too slow, you are done! No need to do something fancy if something simple will work.

To understand the performance costs of the simple approach, we run a benchmark in which each thread updates a single shared counter a fixed number of times; we then vary the number of threads. The graph below ...