Section 8: Multithreading

Discussion: Race Conditions and Synchronization

DISCUSSION A: What is a race condition? Give an example of a race condition. Why does a race condition occur in your example?

DISCUSSION B: What are atomics? What are mutexes? In what way are atomics and mutexes alike? In what way are they different?

Question 1: Sync or Swim

In the following, we will look at a set of C++ programs that increment variables in multiple threads. For each of the programs, does it contain a race condition or not?

QUESTION 1A: Does this program contain a race condition? What does it print?

#include <iostream>
#include <thread>

void increment(int n) {
    for (int i = 0; i < 1000000; i++) {
        n++;
    }
    printf("n: %d\n", n);
}

int main() {
    int n = 0;
    std::thread t1(increment, n);
    std::thread t2(increment, n);
    std::thread t3(increment, n);

    t3.join();
    t2.join();
    t1.join();

    printf("n: %d\n", n);
}

QUESTION 1B: Does this program contain a race condition? What does it print?

#include <iostream>
#include <thread>

int n = 0;

void increment(int* n) {
    for (int i = 0; i < 1000000; i++) {
        *n = *n + 1;
    }
    printf("n: %d\n", *n);
}

int main() {
    std::thread t1(increment, &n);
    std::thread t2(increment, &n);
    std::thread t3(increment, &n);

    t3.join();
    t2.join();
    t1.join();

    printf("n: %d\n", n);
}

QUESTION 1C: Does this program contain a race condition? What does it print?

#include <iostream>
#include <thread>

void increment(int* n) {
    for (int i = 0; i < 1000000; i++) {
        *n = *n + 1;
    }
    printf("n: %d\n", *n);
}

int main() {
    int* n = new int;
    *n = 0;

    std::thread t1(increment, n);
    std::thread t2(increment, n);
    std::thread t3(increment, n);

    t3.join();
    t2.join();
    t1.join();

    printf("n: %d\n", *n);
    delete(n);
}

QUESTION 1D: Does this program contain a race condition? What does it print?

#include <iostream>
#include <thread>

void increment_three(int n[3]) {
    for (int i = 0; i < 1000000; i++) {
        n[0]++;
        n[1]++;
        n[2]++;
    }

    printf("n0: %d\n", n[0]);
    printf("n1: %d\n", n[1]);
    printf("n2: %d\n", n[2]);
}

int main() {
    int n[3];
    n[0] = 0;
    n[1] = 0;
    n[2] = 0;

    std::thread t1(increment_three, n);
    std::thread t2(increment_three, n);
    std::thread t3(increment_three, n);

    t3.join();
    t2.join();
    t1.join();

    printf("n0: %d\n", n[0]);
    printf("n1: %d\n", n[1]);
    printf("n2: %d\n", n[2]);
}

QUESTION 1E: Does this program contain a race condition? What does it print?

#include <iostream>
#include <thread>
#include <atomic>

std::atomic<int> n(0);

void increment(std::atomic<int>* n) {
    for (int i = 0; i < 1000000; i++) {
        atomic_fetch_add(n, 1);
    }
    printf("n: %d\n", n->load());
}

int main() {
    std::thread t1(increment, &n);
    std::thread t2(increment, &n);
    std::thread t3(increment, &n);

    t3.join();
    t2.join();
    t1.join();

    printf("n: %d\n", n.load());
}

Question 2: The Key to Locking

In this question, we'll explore different strategies using mutexes to synchronize access to grades in the CS 300 grading server. In the grading server, each student is represented using the following struct:

struct student_t {
    std::string name;
    double snake_grade;
    double dmalloc_grade;
    double file_io_grade;
    double weensy_os_grade;
    double concurrent_store_grade;
    double distributed_store_grade;
    double time_machine_grade;
    double src_store_grade;
    double midterm_grade;
    double final_grade;
}

The grades for all students are stored in the following array:

    student_t grades[num_students_in_course]

For each of the following questions, discuss the advantages and disadvantages of the described locking strategy. You may want to consider the runtime, memory usage, or effect on parallelism of each strategy.

Note that locking and unlocking mutexes costs significant processor time and that mutexes take up a significant amount of memory.

QUESTION 2A One method of synchronizing access to the grades array using mutexes is coarse-grained locking. In coarse-grained locking, there is a single mutex associated with the grades array. Whenever a thread wants to read or write to the grades array, it must first lock the mutex. When that thread is done reading or writing to grades, it unlocks the mutex.

What are the advantages and disadvantages of using coarse-grained locking to synchronize access to the grades array?

QUESTION 2B Another locking strategy the CS 300 staff can use to synchronize access to the grades array using mutexes is fine-grained locking. In fine-grained locking, subsets of the grades array have mutexes associated with them.

One method of implementing fine-grained locking is associating a mutex with each student. If a thread wants to read or modify a student's entry in grades, that thread must first lock the mutex associated with that student. Once the thread is done reading or modifying that student's entry in grades, it unlocks the mutex.

What are the advantages and disadvantages of using this fine-grained locking strategy to synchronize access to the grades array? (You may want to its effects on runtime, memory, and parallelism to coarse-grained locking).

QUESTION 2C When implementing a fine-grained locking strategy, there are many possible ways to divide up shared memory such as the grades array into portions that should be locked.

Another method of fine-grained locking is associating a mutex with each assignment in CS 300. If a thread wants to read or modify a grade entry for an assignment, it must first lock the mutex associated with that assignment. Once the thread is done reading or modifying that assignment's entry in grades, it unlocks the mutex.