CS 105

Concurrency Practice Questions

Part 1

Consider the following two functions used in a multi-threaded system to transfer funds between two accounts:

void transfer_A_to_B(int amount) {
    pthread_mutex_lock(&mutex_A);
    pthread_mutex_lock(&mutex_B);

    account_A -= amount;
    account_B += amount;

    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
}

void transfer_B_to_A(int amount) {
    pthread_mutex_lock(&mutex_B);
    pthread_mutex_lock(&mutex_A);

    account_B -= amount;
    account_A += amount;

    pthread_mutex_unlock(&mutex_A);
    pthread_mutex_unlock(&mutex_B);
}

If two threads call these functions simultaneously—one executing transfer_A_to_B and the other executing transfer_B_to_A—what is the most likely result?

Which of these optons would (by themselves) avoid the deadlock in this code?

Part 2

Consider this code from the implementation of a shared bounded buffer:

void try_produce(int item) {
    if (count < MAX_SIZE) { 
        pthread_mutex_lock(&buffer_lock);
        buffer[count++] = item;
        pthread_mutex_unlock(&buffer_lock);
    }
}

This code contains a subtle but critical concurrency error. Please describe the error and provide a specific scenario (a sequence of events) that would cause the program to behave incorrectly.

Part 3

In a horrible time-travel accident, you're sent back to the 1980s. Semaphores exist, but PThread mutexes have not been invented yet. (On the positive side, 80's hair.)

You want to write this code:

pthread_mutex_lock(&lock);
/* critical section */
pthread_mutex_unlock(&lock);

But you can't. Instead, you have to use a binary semaphore. How would you rewrite this code using a binary semaphore? Here are two options:

Option 1

/* sem is initialized to 1 earlier in the program */
sem_wait(&sem);
/* critical section */
sem_post(&sem);

Option 2

/* sem is initialized to 0 earlier in the program */

sem_post(&sem);
/* critical section */
sem_wait(&sem);

You aren't sure, so you run both options. Afterwards you try actually thinking about the problem.

What do you find?

(When logged in, completion status appears here.)