MIT 6.828 HW6 Threads and Locking

Notes of MIT 6.828 HW6

In this HW, we learn to use locks to protect shared data structures in parallel programming.

In ph.c, thread runs in two phases. In the first phase each thread puts NKEYS/nthread keys into the hash table. In the second phase, each thread gets NKEYS from the hash table.

The problem happens in put(), which calls insert(key, value, &table[i], table[i]).

1
2
3
4
5
6
7
8
9

static void 
insert(int key, int value, struct entry **p, struct entry *n)
{
  struct entry *e = malloc(sizeof(struct entry));
  e->key = key;
  e->value = value;
  e->next = n;
  *p = e;
}

Each table[i] points to a linked list. We can see that insert() trys to insert a key into the list and modifies *p. However, table is shared between all threads, so when multiple threads try to insert, race condition may happen. Therefore, some keys are missing.

We can insert the following code in put(), which protect the shared data structure using locks.

Notice that we provide each table[i] with a separate lock to improve parallelism. A global lock also works, but might be slower.

1
2
3
4
5
6
7
8
9

static 
void put(int key, int value)
{
  int i = key % NBUCKET;
  // critical section
  pthread_mutex_lock(&locks[i]);
  insert(key, value, &table[i], table[i]);
  pthread_mutex_unlock(&locks[i]);
}