Section 4 Solutions

Sections Thu Oct 27 to Fri Oct 28

Solutions

1. Pendulum

Our solution has some optional print statements to report on what's happening.

// Increment count if less than the limit; otherwise, block 
// until count is below the limit.
static void up(pendulum& p) {
    // 1. If counter is at the limit, wait until in range
    p.countLock.lock();
    while (p.count == p.max) {
        cout << oslock << "\twaiting for count to drop below limit..." 
             << endl << osunlock;
        p.cvDecremented.wait(p.countLock);
    }

    // 2. Increment the counter 
    // and if we brought it back in range for decrementing, 
    // notify waiting threads
    p.count++;
    cout << oslock << "\tcount is now " << p.count << endl << osunlock;
    if (p.count == p.min + 1) p.cvIncremented.notify_all();
    p.countLock.unlock();
}

// Decrement count if greater than the limit; otherwise, block until 
// count is above the limit.
static void down(pendulum& p) {
    // 1. if counter is at the limit, wait until in range
    p.countLock.lock();
    while (p.count == p.min) {
        cout << oslock << "\twaiting for count to rise above limit..." 
             << endl << osunlock;
        p.cvIncremented.wait(p.countLock);
    }

    // 2. Decrement the counter
    // and if we brought it back in range for incrementing, 
    // notify waiting threads
    p.count--;
    cout << oslock << "\tcount is now " << p.count << endl << osunlock;
    if (p.count == p.max - 1) p.cvDecremented.notify_all();
    p.countLock.unlock();
}

2. Short Answer

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?

A1: It means that its range of addresses are, by default, private to the owning process, and that it's impossible for an another arbitrary, unprivileged process to access any of it. This is an advantage because other code/programs can't accidentally or intentionally examine another process's data. This is a disadvantage because it is exceptionally difficult to exchange data with other processes, and works against any efforts to breezily distribute work over multiple CPUs using multiprocessing.

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

A2: When we spawn a process, all parent info is cloned in the child, and if the child runs another program we can pass arguments via execvp. We can also use pipes to allow processes to communicate. We can use them separately from out STDIN/STDOUT/STDERR to send data back and forth, or we can redirect process input/output to/from pipes. A program can ignore command-line arguments if it wants to, but if its I/O is redirected before it's launched with execvp there isn't much it can do about it.

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

A3: Each thread of execution runs as if it's a miniature program. Threads have their own stack, and they have access to globals, dynamic memory allocation, system calls, and so forth. They're relatively lightweight compared to true processes, because you don't need to create a new process when creating a thread. We just cordon off a portion of the full stack segment for the new thread's stack, but otherwise the thread piggybacks off existing text, heap, and data segments of the process.

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?

A4: Because all threads have access to the same virtual address space, it's relatively easy to share information (e.g. via pass-by-reference). However, because two or more threads might want to perform operations on a shared piece of data, directives must be implanted into thread routines to ensure data and resources are shared without inspiring data corruption via race conditions, or deadlock via resource contention. That's a very difficult thing to consistently get right.

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

A5: We might prefer multithreading in scenarios where ease of data exchange is important, and multiprocessing where protection, privacy, and insulation from other processes' errors is important.

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

A6: It's not normally thread safe - it may take multiple operations (loading the existing value, modifying it, then writing the new value) and those operations could be interrupted. For instance, if a thread completes just the first two steps of loading the existing value and modifying it, but then gets swapped off the processor and another thread changes i, the original thread will eventually resume and continue on with stale data. Note that technically it's possible in some cases for i-- to compile down to one assembly instruction and be atomic, but it's not guaranteed, so we assume it's not.

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

A7: Busy waiting is consuming processor time waiting for some condition to change, instead of sleeping until you are notified that a condition is true. Busy waiting can unnecessarily consume CPU time.

Checkoff Questions

1. [Q1] Why does the implementation of pendulum use 2 condition variables, rather than just 1?

   • We have one condition variable per "event" in our code so that threads only wake up for the event they care about. It turns out in this case it would still work to have just 1 condition variable, and threads would only be woken up for the event they care about (since it's not possible for the pendulum to be both at the max and at the min simultaneously). But in other cases, having just one condition variable where more would be helpful mean that threads might be woken up for events they don't care about. (think like having separate radio station broadcasts vs. one broadcast everyone listens to). However, it would still functionally work (since a thread checks the condition again on wakeup).

2. [Q2] We need only two calls to counterLock.unlock() in the pendulum solution, one at the end of each of the up and down functions. But are there any other places where counterLock is also unlocked? If so, where?

   • When we call wait on a condition variable, it releases the lock after putting that thread to sleep, so another thread can acquire the lock.