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.
typedef struct list_node {
int data;
struct list_node* next;
} list_node_t;
typedef struct list {
list_node_t* head;
pthread_mutex_t mutex;
} list_t;
int list_peek(list_t* lst) {
pthread_mutex_lock(&lst->mutex);
list_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 the source account and deduct funds from the balance
pthread_mutex_lock(&accounts[from_id].lock);
accounts[from_id].balance = accounts[from_id].balance - amount;
pthread_mutex_unlock(&accounts[from_id].lock);
// Lock the destination account and add funds to the balance
pthread_mutex_lock(&accounts[to_id].lock);
accounts[to_id].balance = accounts[to_id].balance + amount;
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 or errors are 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 code snippet is from a program that is supposed to print “snap” one time, “crackle” two times, and “pop” three times. The messages may appear in any order.
int thread_index = 0;
char* messages[] = {"snap", "crackle", "pop"};
// This thread prints one of the messages
void* thread_fn(void* arg) {
// Get this thread's index and update the next index
int my_index = thread_index++;
// Use the index to get this thread's message
char* message = messages[my_index];
// Get the number of times the thread should print its message from the thread parameter
int message_count = *(int*)arg;
// Print the messages
for (int i = 0; i < message_count; i++) {
printf("%s\n", message);
}
return NULL;
}
int main() {
// Create threads to print messages
pthread_t threads[3];
for (int i = 0; i < 3; i++) {
int count = i + 1;
pthread_create(&threads[i], NULL, thread_fn, &count);
}
// Wait for threads
for (int i = 0; i < 3; i++) {
pthread_join(threads[i], NULL);
}
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.