Sections Thu Oct 27 to Fri Oct 28

This section handout is based on problems by Jerry Cain, with modifications by Nick Troccoli.

Learning Goals

During this section, you will:

1. get practice writing multithreaded code
2. use mutexes to prevent race conditions
3. use condition variables to wait/notify for events

The main focus is on problem #1. Problem #2 provides additional discussion questions if there's time, or you can use them as additional review.

Get Started

Clone the section starter code by using the command below. This command creates a section4 directory containing the project files.

git clone /afs/ir/class/cs111/repos/lab4/shared section4

Next, pull up the online section checkoff and have it open in a browser so you can jot things down as you go.

1. Pendulum

For this problem, we will implement two atomic functions, up and down, that can increment and decrement a "pendulum counter". A pendulum counter is just like a regular counter, however it is limited to a specific max and min value that it cannot exceed. You can call up to increment the counter by 1, or down to decrement the counter by 1; but if up would increment beyond a max value, it must wait for another thread to decrease it first. And if down would decrement beyond a min value, it must wait for another thread to increase it first.

The pendulum counter info is bundled together in a struct so that we can pass one parameter to each thread instead of 3.

typedef struct pendulum {
    int count = 0;
    int max;
    int min;
} pendulum;

count is the current count, max is the highest this count is permitted to go, and min is the lowest this count is permitted to go.

Your task is to implement the following 2 atomic functions in pendulum.cc:

// increments the pendulum counter, blocking if necessary until the counter can be incremented.
void up(pendulum& p) { … }

// decrements the pendulum counter, blocking if necessary until the counter can be decremented.
void down(pendulum& p) { … }

As an example, if a thread calls up on a pendulum with count 4 and max 5, it would just increment the count to 5 and continue. But if a thread calls up on a pendulum with count 5 and max 5, it would block until the pendulum count decreases to allow for it to be incremented again, and then it would increment it to 5 and continue.

Here's an example program that spawns threads to increment and decrement a shared pendulum counter - a working implementation is provided in samples/pendulum_soln to run:

// A thread either increments or decrements the counter 100 times,
// sleeping a bit between each.
static void swingPendulum(size_t id, pendulum& p) {
    for (int i = 0; i < kNumIterations; i++) {
        // Half of threads increment, half decrement
        if (id % 2 == 0) {
            cout << oslock << "Thread " << id 
                 << " incrementing..." << endl << osunlock;
            up(p);
        } else {
            cout << oslock << "Thread " << id 
                 << " decrementing..." << endl << osunlock;
            down(p);
        }

        sleep_for(getSleepTime());
    }
}


int main(int argc, const char *argv[]) {
    thread threads[kNumThreads];
    pendulum p;
    p.max = 10;
    p.min = -10;

    for (size_t i = 0; i < kNumThreads; i++) {
        threads[i] = thread(swingPendulum, i, ref(p));
    }
    for (thread& t: threads) {
        t.join();
    }

    cout << "All done!" << endl;
    return 0;
}

Your task is to implement the up and down functions. You will need to add more fields to the pendulum struct (mutex/condition_variable_any) to manage the synchronization needed for this problem. Use the strategies outlined in lecture to think about what is necessary to coordinate the threads and avoid race conditions / deadlock!

2. Short Answer

Work through the following short answer questions that examine more design/big-picture questions about multithreading and synchronization, and compare multithreading and multiprocessing.

Q1: What does it mean when we say that a process has a private address space? What are the advantages and disadvantages of having a private address space?

Q2: How do we exchange information across process boundaries? When do processes have or not have a say in information being transferred?

Q3: Threads are often called lightweight processes. In what sense are they processes? And why the lightweight distinction?

Q4: Threads running within the same process all share the same virtual address space. What are the advantages and disadvantages of allowing threads to access pretty much all of virtual memory?

Q5: What are some scenarios where we might prefer multithreading in our programs, and what are some scenarios where we might prefer multiprocessing?

Q6: Is i-- thread safe? Why or why not?

Q7: What is busy waiting, and what problems can it cause?