Assignment 6

Assigned:
Friday, Mar 9, 2018
Due:
Friday, Mar 16, 2018 by 10:30pm
Collaboration:
You may not discuss or work on this assignment with any other students. Mentors can help you if you are confused about the assignment requirements or documentation, but they cannot provide any assistance that would require them to look at your code. Please see the assignments page for detailed assignment policies.
Submitting:
To submit your work, simply commit your final changes and push them to GitHub before the deadline. You do not need to create a pull request to turn in these assignments.

Overview

In this assignment, you will diagnose a number of concurrency errors in some simple example programs. Unlike previous individual assignments, this one will not require you to implement a working program. Instead, you will identify the issue for each code snippet and propose a solution. Solutions may require adding or removing synchronization primitives, reordering statements, or making other small changes to the code in the snippet.

You will have access to a GitHub repository for this assignment. Write all your responses for each problem in the README.md file in the repository.

Problem 1

This snippet of code shows a helper function that multiple threads may call at the same time. The helper function returns the integer held in the first node of a linked list, or -1 if the list is empty. Other threads may try to insert, delete, or modify data in the linked list at the same time that this helper is running. The list uses a single mutex to protect all of the list’s data, which is initialized in code not shown here.

int list_peek(list_t* lst) {
  pthread_mutex_lock(&lst->mutex);
  node_t* first = lst->head;
  pthread_mutex_unlock(&lst->mutex);
  
  if(first == NULL) {
    return -1;
  } else {
    return first->data;
  }
}

In your README file, answer these questions:

1. What is the name of the concurrency error in this code snippet?
Options are: atomicity violation, order violation, or deadlock.

2. How would you fix this error?
Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error you identified.

Problem 2

This code snippet shows a helper function that searches for a matching key in the a hash table bucket’s list. If it finds a matching key the function returns the value for that key, otherwise it returns -1. Each bucket of the hash table has its own mutex to allow for some concurrent accesses.

int bucket_find_key(dict_t* dict, int bucket_index, char* key) {
  // Lock the bucket
  pthread_mutex_lock(&dict->bucket_locks[bucket_index]);
  
  // Traverse the list of key/value pairs in this bucket
  bucket_node_t* current = dict->buckets[bucket_index];
  while(current != NULL) {
    // Return a match
    if(strcmp(current->key, key) == 0) {
      return current->data;
    }
    current = current->next;
  }
  pthread_mutex_unlock(&dict->bucket_locks[bucket_index]);
  
  // No match found
  return -1;
}

In your README file, answer these questions:

1. What is the name of the concurrency error in this code snippet?
Options are: atomicity violation, order violation, or deadlock.

2. How would you fix this error?
Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error you identified.

Problem 3

This code snippet shows a part of the main function, and the body of two threads created by main.

#define LENGTH 4096
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int* data = NULL;
int sum = 0;

// This thread function initializes the data array
void* init_thread_fn(void* arg) {
  pthread_mutex_lock(&mutex);
  data = malloc(sizeof(int) * LENGTH);
  for(int i=0; i<LENGTH; i++) {
    data[i] = i * 100;
  }
  pthread_mutex_unlock(&mutex);
  return NULL;
}

// This thread function adds up the values in the data array
void* worker_thread_fn(void* arg) {
  for(int i=0; i<LENGTH; i++) {
    pthread_mutex_lock(&mutex);
    sum += data[i];
    pthread_mutex_unlock(&mutex);
  }
  
  return NULL;
}

int main() {
  // Create a thread to initialize our global
  // TODO: check for errors
  pthread_t init_thread;
  pthread_create(&init_thread, NULL, init_thread_fn, NULL);
  
  // Create a worker thread
  // TODO: check for errors
  // TODO: make more worker threads someday
  pthread_t worker_thread;
  pthread_create(&worker_thread, NULL, worker_thread_fn, NULL);
  
  // Wait for initialization to complete
  pthread_join(init_thread, NULL);
  
  // Now wait for work to complete
  pthread_join(worker_thread, NULL);
  
  printf("sum is %d\n", sum);
  
  return 0;
}

In your README file, answer these questions:

1. What is the name of the concurrency error in this code snippet?
Options are: atomicity violation, order violation, or deadlock.

2. How would you fix this error?
Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error you identified.

Problem 4

This snippet shows a function that searches a linked list for a matching value. Unlike the previous list example, this linked list uses a mutex on every node to allow for more concurrent accesses. Other threads may attempt to insert or remove items in the list while this function is running.

bool list_contains(list_t* lst, int value) {
  // Traverse the list, keeping a pointer to the previous node
  node_t* current = lst->head;
  while(current != NULL) {
    // Lock the current node
    pthread_mutex_lock(&current->mutex);
    
    // Is there a match?
    if(current->data == value) {
      pthread_mutex_unlock(&current->mutex);
      return true;
    }
    
    // Move to the next node
    node_t* previous = current;
    current = current->next;
    
    // Unlock the previous node (was current until the last line)
    pthread_mutex_unlock(&previous->mutex);
  }
  
  return false;
}

In your README file, answer these questions:

1. What is the name of the concurrency error in this code snippet?
Options are: atomicity violation, order violation, or deadlock.

2. How would you fix this error?
Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error you identified.

Problem 5

This snippet shows a failed attempt to implement a barrier. Unlike the barrier you implemented, this one can only be used once.

typedef struct single_use_barrier {
  int num_threads;
  int threads_arrived;
  pthread_mutex_t mutex;
} single_use_barrier_t;

void barrier_init(single_use_barrier_t* b, int num_threads) {
  b->num_threads = num_threads;
  b->threads_arrived = 0;
  pthread_mutex_init(&b->mutex, NULL);
}

void barrier_wait(single_use_barrier_t* b) {
  pthread_mutex_lock(&b->mutex);
  b->threads_arrived++;
  while(b->threads_arrived < b->num_threads) {
    sleep_ms(1);
  }
  pthread_mutex_unlock(&b->mutex);
}

void barrier_destroy(single_use_barrier_t* b) {
  pthread_mutex_destroy(&b->mutex);
}

In your README file, answer these questions:

1. What is the name of the concurrency error in this code snippet?
Options are: atomicity violation, order violation, or deadlock.

2. How would you fix this error?
Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error you identified.