Show all solutions
Rules
The exam is open book, open note, open computer. You may search the Internet and class material arbitrarily, with the following exception: You absolutely may not contact people other than course staff (e.g., to ask questions on Stack Overflow, or an exam site, or your classmates). Use private Piazza questions to contact course staff if necessary.
Any violations of the spirit of this policy are breaches of academic honesty and will be treated accordingly.
You have five hours to complete this exam, starting from the time you access this page. The questions are not sorted by difficulty.
Completing your exam
Obtain an exam repository via this URL: https://classroom.github.com/a/z58luZrB
Write your answers in final.md
, sign your name in finalpolicy.md
, then
commit and push. Configure the grading server with your repository.
1. Resumption state (10 points)
A. At the beginning of proc::exception(regstate* regs)
, does
this->regs_ == regs
? Explain briefly.
B. Which registers are always preserved across a call to proc::yield
?
C. Of those registers, which are preserved by the C++ compiler’s
implementation of the calling convention and which are saved by Chickadee’s
implementation of proc::yield
?
In the following questions, we want you to explain how to access the value for
some logical registers. Possible answers might include “in CPU 0’s active
register set”; “in p->regs_->reg_rcx
”; “in regs->reg_rdx
, where regs
is
the argument to proc::exception
”; “the compiler will have saved this value
in some stack frame, if needed”; and “nowhere, that register is meaningless in
that context.” Explain briefly if unsure.
D. The %rsp
for a kernel task that is currently blocked within a call to
proc::yield
.
E. The %rax
for a user thread that is currently running on CPU 1.
F. The %rax
for a kernel task that is currently running on CPU 1.
G. The %rdi
for a user thread that is currently blocked due to a timer
interrupt.
H. The %rdi
for a kernel task that is currently blocked due to a timer
interrupt.
I. The %rdi
for a kernel task that is currently blocked within a call to
proc::yield
.
J. The %cr3
for a user thread that is blocked.
2. Interrupt handling (10 points)
A commodity OS interrupt handler typically behaves this way:
- The interrupt handler begins execution on a CPU stack when the CPU delivers an hardware interrupt.
- The handler communicates with hardware.
- The handler acknowledges the interrupt and the OS returns to normal processing on some kernel task stack.
Typical operating systems ensure Step 2 takes as little time as possible. This is because step 2 takes priority over all other processing, including new interrupts. But this can make interrupt handlers hard to reason about; in particular, interrupt handlers cannot block.
Describe how you would modify an OS to allow interrupt handlers to block. Be explicit about the new types of state that you would introduce to support sleeping interrupt handlers; describe when the state is created, how it is initialized, and when it is destroyed. To make your explanation concrete, explain how your design would support an interrupt handler which is triggered when a network packet arrives; the handler should write the packet data to disk using a blocking IO, and wait for the disk write to complete before terminating. Your design should still acknowledge interrupts as soon as possible.
3. System calls (10 points)
The return path from the syscall
instruction is currently very different
from the return path from an interrupt:
## the exception_entry return path:
restore_and_iret:
// restore `regstate` registers
popq %rax
popq %rcx
popq %rdx
popq %rbx
popq %rbp
popq %rsi
popq %rdi
popq %r8
popq %r9
popq %r10
popq %r11
popq %r12
popq %r13
popq %r14
popq %r15
popq %fs
// must `swapgs` if required
testb $1, 12(%rsp) // `reg_swapgs & 1`
jnz 1f
// returning to kernel mode
addq $24, %rsp
iretq
1: // returning to user mode
swapgs
popq %gs
addq $16, %rsp
iretq
## the syscall_entry return path:
addq $(8 * 19), %rsp
swapgs
iretq
A. Why does the exception_entry
return path execute the swapgs
instruction only sometimes? Explain briefly.
B. What would go wrong, if anything, if the syscall_entry
return path
were also used for exception_entry
? Explain briefly.
C. What would go wrong, if anything, if the exception_entry
return path
were also used for syscall_entry
? Explain briefly.
D. The current design has a serious flaw: it can lead to sensitive kernel information being exposed to a user process. Explain how this could occur; be specific.
4. Futexes (15 points)
Recall that futex
is a system call intended to be used by user-level locking
libraries.
A. Suppose that a user-level threading library wants to support a lock abstraction. Why is it a bad idea to implement the lock abstraction using spin waiting?
B. Is the primary purpose of futex
to improve correctness (e.g.,
preventing errors and race conditions, ensuring mutual exclusion) or
efficiency (e.g., raising utilization)? Explain your answer.
As Ulrich Drepper says, “futexes are tricky.” Here is a (we believe) correct futex-based implementation of a mutual-exclusion lock. In the next several questions, you will consider several modifications of this code.
struct futex_lock {
std::atomic<int> val_;
// 0 = unlocked; 1 = locked, no futex waiters;
// 2 = locked, maybe futex waiters
void lock() {
// Phase 1
for (unsigned i = 0; i < 40; i++) {
int expected = 0;
if (val_.compare_exchange_weak(expected, 1)) {
return;
}
sched_yield();
}
// Phase 2
int previous = val_.load(std::memory_order_relaxed);
if (previous != 2) {
previous = val_.exchange(2);
}
while (previous != 0) {
futex(&val_, FUTEX_WAIT, 2);
previous = val_.exchange(2);
}
}
void unlock() {
if (--val_ != 0) { // atomic decrement
val_ = 0;
futex(&val_, FUTEX_WAKE, 1);
}
}
};
Consider replacing the Phase 1 part of lock
with the following code (leaving
Phase 2 as is).
int expected = 0;
if (val_.compare_exchange_weak(expected, 1)) {
return;
}
C. Is this modified lock correct (does it provide mutual exclusion without starvation)? If not, explain why.
D. Describe a workload where this lock will likely perform essentially the same as the original. (Describe workloads in terms of their parameters, such as contention level.) Explain briefly.
E. Describe a workload where this lock will likely perform better than the original. Explain briefly.
F. Describe a workload where this lock will likely perform worse than the original. Explain briefly.
Now consider deleting lock
’s Phase 1 (going straight to Phase 2).
G. Is this modified lock correct? If not, explain why.
H. Explain how this lock’s performance will differ from the original (in cases when it works correctly).
Now consider replacing lock
’s Phase 1 with the following code.
for (unsigned i = 0; i < 40; i++) {
if (val_.exchange(1) == 0) {
return;
}
sched_yield();
}
I. Is this modified lock correct? If not, explain why.
J. Explain how this lock’s performance will differ from the original (in cases when it works correctly).
5. Barrelfish (12 points)
Section 4.6 of the Barrelfish paper describes the implementation of a lightweight URPC (user-level remote procedure call) system for inter-core communication among user-level processes. Describe how this would be implemented in Chickadee, following the Barrelfish design. Include at minimum:
A. The layout of the struct urpcregion
structure, which defines the layout
of a URPC shared-memory region.
B. Pseudocode for the char* receive(urpcregion* r)
function, which waits
until a new message is sent, then returns a pointer to the location of that
message’s data in the shared-memory region. (You’ll obviously also need a
design for send
, but you don’t need to write it if you don’t want to.)
C. New system calls required (you will need at least one!).
D. Anything else you think is relevant.
Make sure you consider the initialization process as well as normal operation.
6. NFS (13 points)
Suppose that you want to layer a user-mode journaling file system atop the
NFS file /nfs/diskfile
. The user-mode journaling file system, called ujfs,
will preallocate 10 GB of space for /nfs/diskfile
, and then treat
/nfs/diskfile
as a 10 GB disk; for example, the first part of /nfs/diskfile
will contain a superblock, and the latter part of /nfs/diskfile
will contain
data blocks and a journal. When ujfs wants to update a ujfs-level file, ujfs
will first write to the journal portion of /nfs/diskfile
, and then write to
the data block portion of /nfs/diskfile
.
Assume that (1) the NFS server and the NFS client may crash, but (2) the network connection between the NFS client and the NFS server is always available and has good performance. Describe any additional changes that would be required—to the network, to NFS, and/or to the ujfs code—for ujfs to provide equivalent consistency guarantees as a traditional journaling file system like ext4.
7. Virtualization (10 points)
Suppose that a hypervisor uses hosted interpretation to execute a guest application. Further suppose that the guest application contains a JIT compiler, such that the JIT compiler (1) allocates a new memory page, (2) marks that page as writable and executable, (3) writes binary code to the page, and then (4) jumps to the first instruction in the page. Can the hypervisor detect the jump and interpose on the dynamically-generated instructions? Why or why not?
8. Affinity (15 points)
Multiprocessor operating systems support notions of processor affinity and
CPU migration, in which tasks (including process threads and kernel tasks)
switch from processor to processor as they run. This can be important for load
balancing—maybe all the threads on processor 0 happen to exit at about the
same time, leaving processor 0 idle and the other processors oversubscribed—so
a good kernel scheduler will proactively migrate tasks to mitigate this
imbalance. There are also system calls that manage CPU placement directly,
such as sched_setaffinity
.
A. Design a system-call-initiated CPU migration for Chickadee.
Specifically, describe how you might implement a sys_sched_setcpu(pid_t p, int cpu)
system call, which should work as follows:
-
If
cpu < 0 || cpu >= ncpu
, then return an error. -
Otherwise, if
p != 0 && p != current()->id_
, then return an error (you’ll fix this in the next exercise). -
Otherwise, the system call returns 0 and the calling thread (process) next executes on CPU
cpu
. That is, when the system call returns 0, the unprivileged process code is executing on CPUcpu
.
If you need one or more struct proc
members, describe
them. Think about Chickadee synchronization invariants—your design should obey
them!—and describe any new invariants you might require.
B. Extend your sys_sched_setcpu
design so processes can change other
processes’ CPU placements (that is, support p != 0 && p != current()->id_
).
9. Hack (5 points)
A. Describe one feature of the x86-64 architecture you’ve encountered in Chickadee that you think is a hack, and explain why.
B. Describe one feature of your Chickadee that you think is a hack, and explain why.
Finally
Did you remember to sign your name in finalpolicy.md
?
Thank you for taking the course!