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.
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;
}
}
Submit your answers to the following questions on gradescope:
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.
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;
}
Submit your answers to the following questions on gradescope:
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.
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;
}
Submit your answers to the following questions on gradescope:
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.
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(¤t->mutex);
// Is there a match?
if(current->data == value) {
pthread_mutex_unlock(¤t->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;
}
Submit your answers to the following questions on gradescope:
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.