Show all solutions
Rules
The exam is open book, open note, open computer. You may access the book and your own notes. You may also use computers or electronic devices to access your own class materials and public class materials. Specifically:
- You may access a browser and a PDF reader.
- You may access your own notes and problem set code electronically.
- You may access Internet sites on which your own notes and problem set code are stored.
- You may access the course site.
- You may access pages directly linked from the course site, including our lecture notes, exercises, and section notes.
- You may access any web pages referenced by the "Notes" section of the lecture PowerPoint slides.
- You may access our lecture, problem set, and section code.
- You may run a C or C++ compiler, including an assembler and linker.
- You may access manual pages and common utilities, including calculators and a Python interpreter.
However:
- You may not access class discussion forums, such as the Edboard, or other question forums, such as Stack Overflow.
- You may not access an on-line disassembler or decompiler.
- You may not access solutions from any previous exam, by paper or computer, except for those on the course site.
- You may not broadly search the Internet for answers to questions or access other courses’ materials. Stick to our course site and web pages referenced by the lecture PowerPoint slides.
- You absolutely may not contact other humans or AI assistants with questions about the exam—whether in person, via IM, via GitHub Copilot, or by posting questions to forums. The single exception is that you may contact course staff.
Any violations of this policy are breaches of academic honesty and will be treated accordingly. Please appreciate our flexibility and behave honestly and honorably.
Students are taking the exam at different times. Do not post publicly about the exam until given permission to do so by course staff. This includes general comments about exam difficulty.
Questions
If you have questions during the exam, raise your hand if you are taking the
exam in person. Otherwise, write us email at cs61-staff@g.harvard.edu
.
Don’t use the Edboard. We may not notice Edboard posts, and you aren’t
supposed to access the Edboard anyway.
Completing your exam
You have 3 hours (180 minutes) to complete the exam starting from the time you press Start. Different students may have different exams. Enter your answers directly in this form. A green checkmark appears when an answer is saved. (Click outside a text box to save the answer.)
Students with extra time accommodations: If your extra time is not reflected next to the start button, contact course staff and wait for confirmation before pressing it.
There is no need to explicitly “submit” the exam. Your changes are
automatically saved with timestamps on the grading server. We’ll grade
the latest version saved within your exam window. If you experience
bad network connectivity while taking the exam, be sure to save a copy
of your answers locally; after the exam, immediately email those
answers to cs61-staff@g.harvard.edu
. Course staff will also have
physical copies of the exam in case you cannot access the official
version hosted on the grading server.
Notes
The exam contains 14 questions in total (Q1A—B, Q2A—D, Q3A, Q4A—C, and Q5A—D). Assume a Linux operating system running on the x86-64 architecture unless otherwise stated. If you get stuck, move on to the next question. If you’re confused, explain your thinking briefly for potential partial credit.
1. Compiling, Assembling, and Linking (12 points)
QUESTION 1A. Suppose that a single program will launch four different
threads. Further suppose that each thread has the same entry point f()
,
i.e., for each thread, the function f
is passed to the constructor
for std::thread
. If we use a tool like objdump
to look at the
machine instructions in the program's executable binary, will we see
four copies of the instructions in f
(i.e., one per thread), or
one copy of the instructions in f
, or something else? Explain
your answer.
QUESTION 1B. In the program from above, suppose that we continue
to use objdump
to explore the executable binary. Will objdump
be able to find a section in the binary which contains the program's
heap? Why or why not?
2. Kernels (28 points)
QUESTION 2A. In Lecture 9, we looked at how system calls worked,
examining how a kernel must configure an x86-64 chip to properly
handle syscall
instructions. Suppose that, during the kernel's boot,
the kernel sets %IA32_LSTAR
to the boot-time %rsp
instead of
to reinterpret_cast<uint64_t>(syscall_entry)
. Why is this so
catastrophic? Explain what will happen during the first time
that user-level code invokes a syscall
instruction.
QUESTION 2B. In WeensyOS, why is the kernel stack empty when the CPU is executing user-level code?
QUESTION 2C. Recall that, on an x86 chip, assigning to %cr3
is a privileged operation. Further recall that, on x86 chips,
each entry in the interrupt descriptor table (IDT) contains
the virtual address for the handler function for a particular
interrupt or exception.
Suppose that a buggy WeensyOS kernel accidentally sets the
virtual address in an IDT entry to be an address for a function
in user memory (not kernel memory). When the relevant interrupt
or exception occurs and that user-level function executes,
would that function be able to set %cr3
to point to the
kernel's page table (allowing the user-level function to access
all memory)? Why or why not? You can assume that the user-level
function does indeed contain an instruction that would try to
set %cr3
to point to the kernel's page table.
QUESTION 2D. On a multi-core machine, why does each core need its own TLB? In your answer, describe what could go wrong if each core shared a single TLB.
3. Unicode (7 points)
QUESTION 3A. For an arbitrary string of characters in an arbitrary human language, is the UTF-32 encoding of that string guaranteed to always be larger than the UTF-8 encoding? Why?
4. Storage (21 points)
QUESTION 4A. Consider the following C++ code:
#define NUM_ELEMENTS 32768
#define NUM_ITERATIONS 1000000
unsigned int arr[NUM_ELEMENTS];
unsigned int sum = 0;
for (unsigned int i = 0; i < NUM_ITERATIONS; ++i) {
unsigned int index = (i * 8192) % NUM_ELEMENTS;
arr[index] = i + sum;
sum += i;
}
Assume that the variables sum
, i
, and index
live in
registers, whereas elements in arr
live in memory. Do the
memory accesses to arr
exhibit temporal locality, spatial
locality, both, or neither? Why?
QUESTION 4B. Consider a one-block cache that has an
implementation bug. Suppose that block b
is currently
cached and is clean. Further suppose that sometimes,
when the application requests block b
, the cache
doesn't return the cached block, but instead performs
a read of the slow underlying storage, evicting the
cache block and replacing it with the (equivalent!) one
that was just fetched from slow storage. Is this buggy
cache still a coherent cache? Why?
QUESTION 4C. Suppose that a single-threaded process X
is performing memory-mapped IO (both reads and writes) on
"foo.txt"
, whereas a single-threaded process Y
is
performing memory-mapped IO (both reads and writes) on
"bar.txt"
. In what situations (if any) would there be
memory-based race conditions on buffer cache pages?
5. Processes, Threads, and Synchronization (32 points)
QUESTION 5A. Consider a single-threaded process that receives a signal. Is it possible for the signal handler to run in parallel with the normal application code in the process, such that, on a two-core machine, the signal handler and the normal application code would execute simultaneously? Why?
QUESTION 5B. Suppose that, for each process on a Linux machine, you can inspect the process's virtual memory area (VMA) data structure maintained by Linux; however, you can't inspect the process's page table. Using only knowledge in the VMAs, could you determine how many pages of physical RAM are being used by all processes? Why?
QUESTION 5C. Consider a multi-threaded process that contains
two ticket locks T1
and T2
. Assume that the locks use the
implementation from Lecture 23. Explain how ticket locks intrinsically
prevent deadlock, or give an example of how deadlock could nonetheless
arise with T1
and T2
(and explain why ticket locks don't prevent
the deadlock).
QUESTION 5D. Consider the following (buggy!) implementation of a spinlock:
//This variable holds the spinlock.
std::atomic<unsigned> m = 0; //Initially unheld
void lock() {
m++; //Atomic read/modify/write
while (m != 1) { //Atomic read; note that the read
//might fetch a value greater than
//1 if multiple threads are trying
//to simultaneously grab the lock!
m = 0; //Atomic write
pause();
m++; //Atomic read/modify/write
}
//The hope is that, when `lock()` returns,
//m is 1, indicating that a single thread
//owns the lock.
}
void unlock() {
m--; //Atomic read/modify/write.
}
Explain why this implementation is broken, giving
a concrete example of how two threads can both
own the lock simultaneously. Hint: In your example,
assume that, at the beginning, a thread T1
calls lock()
with no other threads active, such that m
is set
to 1. Devise a bad interleaving of instructions from
threads T2
and T3
who subsequently call lock()
while T1
is still in the critical section.