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. Which concurrency error(s) did you find in this code snippet? Select all that apply and explain your choice. Options are: atomicity violation, order violation, or deadlock.
2. How would you fix this code snippet? Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error(s) you identified.
This code snippet shows an implementation of the transfer function from the bank exercise we did in class.
This function moves funds from one account to another, and may run in multiple threads at the same time.
Each account has an associated lock in the account_t struct that should be held when accessing or updating the account balance.
void transfer(size_t from_id, size_t to_id, int amount) {
// If either account id is invalid, return immediately
if (from_id >= NUM_ACCOUNTS || to_id >= NUM_ACCOUNTS) return;
// If the from and to accounts are the same, return immediately
if (from_id == to_id) return;
// If the amount is zero or negative, return immediately
if (amount <= 0) return;
// Lock both accounts
pthread_mutex_lock(&accounts[from_id].lock);
pthread_mutex_lock(&accounts[to_id].lock);
// Transfer funds
accounts[from_id].balance = accounts[from_id].balance - amount;
accounts[to_id].balance = accounts[to_id].balance + amount;
// Unlock both accounts
pthread_mutex_unlock(&accounts[from_id].lock);
pthread_mutex_unlock(&accounts[to_id].lock);
}
The audit function runs concurrently in an additional thread to total up the balance across all accounts;
this function can run at any time, and should always return the correct balance.
The error is in the transfer function, but your proposed fix should not break the audit function.
int audit() {
// Lock all accounts
for (size_t i=0; i<NUM_ACCOUNTS; i++) {
pthread_mutex_lock(&accounts[i].lock);
}
// Compute the total balance
int balance = 0;
for (size_t i=0; i<NUM_ACCOUNTS; i++) {
balance += accounts[i].balance;
}
// Unlock all accounts
for (size_t i=0; i<NUM_ACCOUNTS; i++) {
pthread_mutex_unlock(&accounts[i].lock);
}
return balance;
}
Submit your answers to the following questions on gradescope:
1. Which concurrency error(s) did you find in this code snippet? Select all that apply and explain your choice. Options are: atomicity violation, order violation, or deadlock.
2. How would you fix this code snippet? Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error(s) 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. Which concurrency error(s) did you find in this code snippet? Select all that apply and explain your choice. Options are: atomicity violation, order violation, or deadlock.
2. How would you fix this code snippet? Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error(s) you identified.
This program snippet shows a GPU procedure to compute the average value of an array of doubles.
The program is designed to first compute the sum of the entire array, and then delegate a single thread to divide that sum by the array length to compute the average.
You may assume this kernel is invoked with valid inputs, which are a GPU pointer to an array of doubles and the length of that array, and then a pointer to a double that is initialied to zero before the kernel is called.
__global__ void array_average(double* values, size_t length, double* average) {
// Get this thread's index into the values array
size_t my_index = blockIdx.x * blockDim.x + threadIdx.x;
// Is the index in bounds?
if (my_index < length) {
// Yes. Add this thread's number from the values array to average to compute a sum.
*average = *average + values[my_index];
}
// Only one thread from one block should perform the final division
if (blockIdx.x == 0 && threadIdx.x == 0) {
// Divide the sum by the length to compute the average
*average = *average / length;
}
}
Submit your answers to the following questions on gradescope:
1. Which concurrency error(s) did you find in this code snippet? Select all that apply and explain your choice. Options are: atomicity violation, order violation, or deadlock.
2. How would you fix this code snippet? Describe your solution, and optionally include corrected code. Briefly explain why your change fixes the error(s) you identified.