Final Assessment Practice

Below, you can find links to practice materials - these are full practice exams, but we have noted the questions relevant to the topics not covered on previous assessments. Understand that we are trying to give you a sense of what some CS110 exam problems have looked like in the past. Some of the material on past exams is different from the material from this quarter. Also note that some of the problems from the practice exams have been cannibalized to contribute to the discussion section handouts.

  • Practice Final 1: PDF | Solutions
    • Problems 2 and 3 cover multithreading
    • Problem 4 covers multithreading and networking
    • Ignore Problem 5b, since that assumed you implemented a MapReduce system, which we didn't require this quarter.
  • Practice Final 2: PDF | Solutions
    • Problem 3, 4a, 4b, and 4c cover multithreading
    • Problem 4d tests your understanding of thread safety with a networking library function
    • Ignore Problems 4e and 4f, since they too assume you completed a MapReduce assignment
  • Practice Final 3: PDF | Solutions
    • Problem 2 covers multithreading
    • Problem 3 covers multithreading and networking
    • Problem 4 is a collection of interesting short answer questions about all topics
    • Ignore Problem 4h, since we didn't cover nonblocking I/O this quarter.

Spring 2019 Final Exam, Selected Questions

This exam was not available in PDF format, so we've included the relevant questions below, along with the topic covered. Solutions to the problems can be found in this PDF.

Question 3 (Multithreading)

You're writing a simulation for moving necessary supplies to support a Mars colony. There are technicians who organize the supplies into a container and load it onto a rocket, astronouts who fly the rockets full of containers to Mars, and martians who unpack the containers. At the beginning of the simulation, one thread is spawned for each technician and one for each astronaut. Threads for the martians are spawned as needed (this process is described below). There is only one launchpad, which is used to load the cargo, and the astronouts (who fly their own rockets) must wait for the launch pad to become available.

A technician is responsible for organizing just one container and getting it onto a rocket (in other words, they perform the loading, as well). First, they must round up an empty container. There are a fixed number of containers available for all technicians to use. Once the technician has a container, they organize it with stuff and then load it. To load, a rocket needs to be at the launch pad and have space for another container. The technician who puts the final container on the rocket tells the astronaut to go. Once their container is loaded, the technician's work is done (and the thread exits).

Each astronaut thread is responsible for making one trip to pick up containers, taking them to Mars, and unloading. The astronaut first "refuels" the rocket and then goes to pick up containers. There is only one launch pad, so only one rocket can be loading at once. The astronaut hangs out while the technicians pile on the containers. Each rocket has a capacity that is established when created. The rocket is considered loaded when it is full to its capacity or it is the last rocket and there are no more containers to load. After the rocket is loaded, the astronaut "flys" the rocket to Mars. On Mars, the astronaut takes each container off the rocket and dispatches a separate martian thread to unpack it. Once the martians are dispatched, the astronaut waits for all spawned martian threads to finish, and only when that happens is the astronaut done (and the astronaut thread exits).

Each martian is responsible for "unpacking" one container. Once the container is unpacked, it is empty and should be made available to the packers who are in need of empty containers. (Assume that each container has a corresponding container that has already made the round trip and as a container is finished on Mars, one is immediately ready back on Earth). Several rockets can be unloaded simultaneously, and martians can work in parallel. Once the martian unpacks their box, their job is done (and their thread exits).

Here is the starting main function for the packing simulation.

const static int kNumContainersToMove = 300;
const static int kNumEmptyContainers = 70;

int main(int argc, char *argv[]) {
  RandomGenerator rgen; 
  vector<thread> threads;
  int totalRocketCapacity = 0;

  for (int i = 0; i < kNumContaineresToMove; i++) {
     // create technician threads
     threads.push_back(thread(technician));
  }

  while (totalRocketCapacity < kNumContainersToMove) { 
    // create astronaut threads
    int thisRocketHolds = rgen.getNextInt(10, kNumEmptyContainers);
    totalRocketCapacity += thisRocketHolds;
    threads.push_back(thread(astronaut, thisRocketHolds));
  }

  for (thread& t: threads) t.join();
  return 0;
}

// simulation functions already written for you
static void organize(); // for technician, to fill container with stuff
static void refuel();   // for astronaut, to prepare rocket
static void fly();      // for astronaut, fly to Mars
static void unpack();   // for martian, to unload container contents

Assume the above helpers are already written and are thread-safe, and you can just call them when you need to. Your job will be to write the technician, astronaut, and martian functions to properly synchronize the different activities and efficiently share the common resources.

Declare your global variables, mutexes, and semaphores, and then implement the technician, astronaut, and martian functions. Do not busy wait anywhere!

// declare your global variables here
// YOUR CODE HERE

void technician() {
    // YOUR CODE HERE
}

void astronaut(int capacity) {
    // YOUR CODE HERE
}

void martian() {
    // YOUR CODE HERE
}

Problem 4 (Multithreading a/c/d and General b)

Answer the four questions below. Limit your answers to 150 words or less.

a) Generally, there are two different ways we use semaphores (throughout lecture and the assignments, you have seen semaphores used in many different scenarios, but the way we use semaphores in these two scenarios falls into one of these two usage patterns). Describe these two use cases, and be explicit about how they differ.

b) Describe the difference between an "I/O Bound" program and a "CPU Bound" program. If we were to speed up the CPU on our computer, but it did not speed up the problem we were trying to solve with a program, would the program be I/O Bound or CPU Bound?

c) Our own solution for the ThreadPool class includes "lazy" initialization of worker threads. This means that we do not actually launch any worker threads until they are needed. So, for example, if we create a 64-thread ThreadPool (e.g., ThreadPool tp(64) ), and then we only scheduled ten threads to work, we would only actually create ten worker threads, at the time they are scheduled. As another example, suppose we had written the Farm problem with threads instead of processes. We could launch all farm workers at the beginning (non-lazy), or we could only launch a worker when it is needed, up to a maximum amount of total worker threads allowed (lazy). Explain the benefit of lazy thread initialization, and explain one downside to lazy thread initialization.

d) The following is the general pattern for using a condition variable:

m.lock();
cv.wait(m, []{return condition > 0});
m.unlock();

Explain two reasons why a mutex is necessary for a condition variable to work properly.