CS 300/1310 Spring 2023 Final Quiz
Welcome to our final quiz! We’re hoping this quiz provides you with an opportunity to review your knowledge and what you've learned in CS 300/1310. Our questions are designed to check your conceptual understanding, rather than asking you to memorize details.
Please make sure you read the rules below before you get started.
Rules
The quiz 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, public class materials, and online resources. Specifically:
- You may access a browser and a PDF reader.
- You may access your own notes and assignment code electronically.
- You may access the course site.
- You may access our lecture notes, exercises, and section notes.
- You may access our lecture, assignment, and section code.
- You may access online resources, including search engines, Wikipedia, and other websites.
- 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 ask the quiz questions on class discussion forums or other question forums such as Stack Overflow.
- You may not access solutions from any previous quiz, from this course or others, by paper or computer, except for those on the CS 300 course site.
- You absolutely may not contact other humans with questions about the quiz — whether in person, via IM, or by posting questions to forums — with the exception of course staff.
- You may not use AI tools (like ChatGPT, Github Copilot, Google Bard, and others) during the quiz.
Any violations of this policy are breaches of academic honesty and will be treated accordingly. Please appreciate our flexibility and behave honestly and honorably.
Additionally, students are taking the quiz at different times. Do not post publicly about the quiz until given permission to do so by course staff. This includes general comments about quiz difficulty.
Completing your quiz
You have 3 hours to complete the quiz starting from the time you press "Start". Different students may have different quizzes. Enter your answers directly in this form; a green checkmark appears when an answer is saved.
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.
You should not need to attach a drawing or other longer notes, but you may do
so by adding them to a final
subdirectory in your cs300-s23-projects
repository. Make sure you push your changes to GitHub before time is up, and
explain in this form where we should look at your notes.
Notes
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. Undefined Behavior (6 points)
QUESTION 1A. The following code snippet computes grades for students in CS 300, as well as their average, using multiple threads (one per student). Not only does it unfairly give low grades to students with the letter 'L'
in their name, it’s also buggy!
Identify three instances of undefined behavior in this code and explain why each instance you chose is undefined behavior.
#include <thread>
typedef struct student {
int grade;
char name[16];
} student_t;
const int num_students = 5;
const char* names[num_students] = {
"Malte Schwarzkopf", "Liz Jones", "Richard Tang", "Ed Bielawa", "Will Sun"
};
int sum = 0;
void compute_grade(student_t* student) {
if (strchr(student->name, 'L') != NULL){
student->grade = 50; // If name contains an 'L', assign a low grade
} else {
student->grade = 100; // Otherwise assign a 100
}
sum += student->grade;
}
int main() {
std::thread* threads = new std::thread[num_students];
for (int t = 0; t < num_students; t++) {
student_t student;
memcpy(student.name, names[t], strlen(names[t]) + 2);
threads[t] = std::thread(compute_grade, &student);
}
int avg = sum / num_students;
printf(“grade average: %d\n”, avg);
delete[] threads;
}
2. Operating Systems (4 points)
QUESTION 2A. Oren Optimizer is a recently hired graduate starting an exciting new job as a kernel programmer.
To start with a splash, Oren proposes to avoid wasting space on page tables for every process. Instead, Oren’s
suggestion is to create a single shared page table used by all processes, and add a set of flags in each L1
page table entry to indicate which processes can access the page it maps (if any).
Oren's plan is to store these new flags as 8 bits within the unused address bits (48-55) in the L1 page table
entry. He's using one bit per process, so that processes can still have shared pages accessible to multiple
processes (e.g., flags of 0000 0011
would allow processes 1 and 2 to access the page).
Give one reason why Oren’s plan will not work well.
3. Virtual Memory and Pagetables (18 points)
Nathan is reading the datasheet for the brand new x86-128
(codename GARGANTUAN) computer architecture. This architecture uses 16 byte virtual memory addresses (rather than 8 byte addresses as in x86-64
), and a virtual address space of 2128 bytes. Each page in x86-128
is 1MiB (220 bytes). With this information, help Nathan answer the following questions about address translation in x86-128
.
QUESTION 3A. How many entries can be stored in each page table page on x86-128
? Briefly explain how you get to your answer.
QUESTION 3B. How many levels of pagetables would you need to map virtual addresses that cover all 2128 bytes in the address space, and why?
QUESTION 3C. Using your answers from 3A and 3B, how are the bits in the address be split between:
- unused bits,
- indexes into different page table levels, and
- offset bits?
Give your answer as a bullet point list of bit ranges. For x86-64
, this may look like:
- [0, 11] – offset
- [12, 21] L1 index
- ...
4. Multiprocessing (12 points)
Malte is on a transatlantic flight on his way back to the CS 300 final and discovers that the "moving map" view in the In-Flight Entertainment (IFE) system appears to have very detailed, live-updating statistics about the airplane – current speed, altitude, temperature, tailfin identification number, flight route, and other information. Malte suspects that the IFE runs on an in-flight computer and accesses data provided by other airplane systems.
Some time into the flight, the IFE crashes, apparently due to data corruption in the IFE process's memory (caused by cosmic rays or by fellow passenger Eve, seated a few rows back). This makes Malte worry about the potential for the IFE software to run havoc and affect critical airplane functionality.
QUESTION 4A. Assume the airplane computer separates the IFE and other, critical control code in different processes. How could the IFE process and the control process safely share the information for the moving map? Identify a technique from the course that can enable this communication and explain how the processes would convey the data. (Hint: there are multiple plausible answers.)
QUESTION 4B. On further investigation, the in-flight computer – surprisingly – appears to be running a modified version of WeensyOS!
Explain, concretely, what changes to WeensyOS will have been needed to realize safe data sharing between the IFE process and the control process. Your answer may propose new system calls, new kernel data structures, and new user-space library code. Please explain concretely what these new features would look like. While you do not have to give actual code or pseudocode (unless you want to), for full credit, a specific answer with reference to actual syscalls, kernel data structures, or code structure is required.
5. Fork, Execv, and Pipes (10 points)
QUESTION 5A.
Yuki wants to have two different processes running two different programs, prog1
and prog2
, that are able to communicate with each other.
He decides to have a pipe between the two processes, where prog1
writes data and prog2
reads data using the pipe. He realizes that he can
use the execv
syscall to achieve this, by passing in the pipe's write or read end FD number as an argument to each program. This works because
a process's file descriptors and metadata are preserved after a call to execv
.
Unfortunately, Yuki wasn't able to finish writing his code because he had to finish grading KV Store! What he wrote so far is below:
char str[64]; // buffer for storing file descriptor to be passed as an arg
int main() {
// [A]
// [B]
// [C]
if(fork() != 0) {
// [D]
// [E]
} else {
// [F]
// [G]
}
}
// Fills and returns the given buffer with the integer as a string.
// You can assume this works.
char* int_to_str(int n, char* buf) {
itoa(n, buf, 10);
return buf;
}
Place the following code segments in their correct position(s) so that the program above achieves Yuki’s goal, and provide a brief explanation for your answer.
-
int fds[2]; pipe(fds);
-
char* argv1[3] = {"prog1", int_to_str(fds[0], str), nullptr}; execv("./prog1", argv1);
-
char* argv1[3] = {"prog1", int_to_str(fds[1], str), nullptr}; execv("./prog1", argv1);
-
char* argv2[3] = {"prog2", int_to_str(fds[0], str), nullptr}; execv("./prog2", argv2);
-
char* argv2[3] = {"prog2", int_to_str(fds[1], str), nullptr}; execv("./prog2", argv2);
-
close(fds[0]);
-
close(fds[1]);
You do not need to use all letters and can use each number as many times as you want. An example answer would be "A3 C5 E3 F2", along with an explanation.
6. Inter-Process Communication (4 points)
QUESTION 6A. Aijah remembers that system calls for I/O on pipes are expensive, and therefore wants to create her own implementation of pipes in user space!
Aijah realizes that pipes are typically used to enable communication between a parent and child process, and
remembers from lecture that parent and child processes can share certain memory segments after a call to fork
.
she decides that her pipe
implementation will have parent and child processes read and write to a fixed
location in this shared memory.
Aijah shows her idea to Malte, who tells her that this idea won’t work! Give one reason why Aijah’s idea is flawed.
7. Race Conditions (6 points)
QUESTION 7A. Tomás finds himself idle because there are no students at TA hours. He wanders the CIT, looking at the old computers in the stairwell. He finds a strange, ancient machine whose processor does not have registers! Instead, its two processors operate directly on 16-bit memory addresses, although each processor still has a cache for better performance.
An example program in the manual shows how to add and subtract numbers on this machine:
add addrA, addrB # addrB = addrA + addrB
Example:
add 0x7ffe, 0x4a56 # adds the values at memory addresses 0x7ffe and
# 0x4a56, storing the result in 0x4a56
add $1, 0x4a56 # adds 1 to the value stored at 0x4a56
Tomás reasons that because there are no registers that can contain stale values, this machine cannot have race conditions when running multi-threaded code, but this is incorrect!
Why is Tomás mistaken? Give a concrete example of how a race condition can still occur on this machine.
8. Synchronization (8 points)
You are the founder and CEO of CS300Bank! You write the following code for your service:
// this service has questionable security because all of its fields are public, but it's fine :)
typedef struct User {
int id; // unique id for each user
bool is_active; // are they an active member of the bank; can change at any moment
} user_t;
typedef struct BankAccount {
int balance;
User owner;
std::mutex mtx;
} bank_account_t;
// You may assume that amount > 0
bool deposit(BankAccount* act, unsigned int amount) {
std::unique_lock lock(act->mtx);
act->balance += amount;
return true;
}
You have threads that are responsible for transferring funds between two arbitrary bank accounts, and you write the following code to execute the transfer.
bool transfer(BankAccount* sender, BankAccount* receiver) {
if (!sender->owner.is_active || !receiver->owner.is_active) {
return true;
}
sender->mtx.lock();
receiver->mtx.lock();
bool success = false;
if (sender->balance > 0) {
receiver->balance += sender->balance;
sender->balance = 0;
success = true;
}
sender->mtx.unlock();
receiver->mtx.unlock();
return success;
}
QUESTION 8A. Unfortunately, transfer()
has two synchronization bugs! Identify each problem and
explain how you would modify the code to fix it. transfer()
should be implemented atomically (i.e., either
the entire transfer happens without interruption or it doesn't happen).
Please explain your changes in enough detail that someone could implement your ideas.
QUESTION 8B. After fixing the bugs, you find that your bank service runs very slowly. Your service is
designed to continually call the transfer()
function for two accounts until the sending user has a positive
balance and the transfer between them succeeds. Your investigation reveals that your service makes a lot of
extra calls to transfer()
.
Identify another synchronization primitive that you could introduce to the BankAccount
struct to address
this problem. Describe what lines of code you need to add to transfer()
and deposit()
to use that
synchronization primitive to improve performance.
9. WeensyOS (12 points)
The users of your completed WeensyOS are realizing that they often needed to allocate two consecutive pages of virtual memory, rather than just one as our sys_page_alloc
currently supports.
To solve this, Zack proposes the creation of a sys_2page_alloc
function, which allocates two consecutive pages of virtual memory if there are two pages available.
QUESTION 9A. Zack proposes the following implementation for sys_2page_alloc
:
int sys_2page_alloc(uintptr_t addr) {
// error checks for addr are omitted; assume addr error checking works
uintptr_t phys_addr = (uintptr_t) kalloc(PAGESIZE);
if (phys_addr == NULL) {
return -1;
}
memset((void*) phys_addr, 0, PAGESIZE);
memset((void*) phys_addr + PAGESIZE, 0, PAGESIZE);
int ret_map1 = vmiter(current->pagetable, addr).try_map(phys_addr, PTE_P | PTE_W | PTE_U);
int ret_map2 = vmiter(current->pagetable, addr).try_map(phys_addr + PAGESIZE, PTE_P | PTE_W | PTE_U);
if (ret_map1 == -1 || ret_map2 == -1) {
kfree((void*) new_mem);
return -1;
}
return 0;
}
For each of the following, indicate whether it is true or false about Zack’s implementation, and give a brief justification.
- This implementation violates process isolation (i.e., processes can corrupt each others’ memory).
- This implementation may cause access to a null pointer.
- This implementation might return
-1
even if there exist two available consecutive pages of physical memory.
QUESTION 9B. Christina proposes simply to call sys_page_alloc
within sys_2page_alloc
but on both addr
and
addr + PAGESIZE
. Will the addresses of the virtual memory pages be contiguous? Will the addresses of physical memory
pages be contiguous? For both questions, briefly explain why.
QUESTION 9C. Based on your answer in 9B, assuming that there is no existing mapping for addr
or addr + PAGESIZE
,
does Christina's implementation achieve the functionality Ed is seeking, i.e., allowing users to allocate two consecutive
pages of virtual memory if the memory is available?
10. KVStore (14 points)
Recall the bucket-based DbMap
class in the concurrent key-value store project, with an array of buckets and their
corresponding mutexes:
class DbMap {
size_t BUCKET_COUNT = 60;
list<DbItem> buckets[BUCKET_COUNT];
mutex bucket_mutexes[BUCKET_COUNT];
// ... helper insert/delete functions ... //
}
struct DbItem {
string key;
string value;
}
In the following, assume all mutexes are standard mutexes, rather than reader-writer locks.
QUESTION 10A. Joel wishes to transfer a database with millions of entries to our key-value store. To speed up the process, he
decides to repeatedly call MultiPut
with tens of thousands of key-value pairs from multiple clients at once. Explain why the
DbMap
, under this workload, is thread-safe and concurrent, but does not provide any speedup from parallelism.
QUESTION 10B. Carolyn claims that Put
operations on individual key-value pairs instead of MultiPut
operations on multiple
key-value pairs would allow for higher parallelism. Why is Carolyn correct?
QUESTION 10C. On receiving complaints that MultiGet
/MultiPut
operations were too slow, Pranav decides to revamp the
DbMap
structure by using a lock per DbItem
, rather than a lock per bucket, as shown below:
class DbMap {
size_t BUCKET_COUNT = 60;
list<DbItem> buckets[BUCKET_COUNT];
// Removed bucket_mutexes[BUCKET_COUNT];
}
struct DbItem {
string key;
string value;
mutex mtx; // Added mutex for each DbItem
}
Note that each bucket is represented by an unsorted, doubly-linked list of DbItems
.
Key-value store operations work as before, except that Pranav acquires the specific DbItem
's lock
instead of locking the relevant bucket’s lock, before interacting with the item.
Specifically, given a key’s bucket, Pranav specifies the behavior of operations as follows:
Get
: iterate through the list to search for theDbItem
with the same key. If found, lock the mutex, retrieve the value, then unlock and return the value. Otherwise, return an error (no locks will be acquired).Put
/Append
: iterate through the list to search for theDbItem
. If found, lock the mutex and update the value, then unlock and return; otherwise, append to the end of the list (no locks will be acquired).Delete
: iterate through the bucket to search for the DbItem. If found, lock theDbItem
, remove the item from the list, then unlock and return; otherwise, return an error (no locks will be acquired).
Explain why Pranav's design does not guarantee thread-safety, and provide a concrete example. (Hint: consider how doubly-linked list operations are implemented, especially insertions/deletions).
11. CS 300/1310 Feedback (6 points)
QUESTION 11A. What is one aspect of CS 300/1310 that we should definitely retain for future years? Any answer but no answer will received full credit.
QUESTION 11B. What is one aspect of CS 300/1310 (other than firing the instructor and dropping the exams) that we can improve for future years? Any answer but no answer will received full credit.
QUESTION 11C. Which CS 300/1310 projects were your most and least favorite ones, and why? Any answer but no answer will received full credit.