Assessment 3 Practice
Below, you can find links to practice materials - these are full practice exams, but we have noted the questions relevant to the topics on this assessment. Understand that we are trying to give you a sense of what some CS110 exam problems have looked like in the past, but we may not replicate the structure of these practice midterms in the actual assessment. In particular, some of the material on past exams is different from the material from this quarter, and these exams were written for different environments (perhaps closed book, written for longer times - for instance, the final exams were usually 3 hours). Also note that some of the problems from the practice exams have been cannibalized to contribute to the section handouts.
- Practice Final 1: PDF | Solutions
- Problems 2 and 3 cover multithreading
- Practice Final 2: PDF | Solutions
- Problem 3 and 4c cover multithreading
- Practice Final 3: PDF | Solutions
- Problems 2 and 4f cover multithreading
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 technician
s who organize the supplies into a container and load it onto a rocket, astronout
s who fly the rockets full of containers to Mars, and martian
s 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 martian
s 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 "unpack
ing" 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 martian
s 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.