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;
}

6pts These are the instances of undefined behavior we accepted:

1. Race condition on sum in compute_grade due to not sychronizing access between threads.
2. Race condition on sum in main due to not waiting for threads to join.
3. memcpy could copy names that are longer than the student_t buffer size.
4. memcpy reads strlen(names[t]) + 2 bytes, which is an out of bounds read on each string in names.
5. Passing a stack-allocated student_t struct that goes out of scope shortly after the thread is created.

We also accepted answers that mentioned the simple fact that we don't call join or detach on the threads. Technically, when we have not called join or detach on a thread, the standard defines that the thread will be terminated when the thread object is cleaned up (e.g. by delete[] threads), but in section we stated that this is UB, so we accepted this answer.

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.

4pts Possible answers include:

1. This limits the operating system to only having at most 8 processes.
2. Two processes can no longer use the same virtual address without sharing the underlying memory
3. This leads to virtual address space fragmentation. An example of this is that this scheme would make it more difficult for a process to make a large allocation of memory, as there may be pieces of the virtual address space that are mapped for a different process that prevents you from allocating a contiguous allocation of the virtual address space, even if there exists enough available virtual addresses to handle the large contiguous allocation.

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 2¹²⁸ bytes. Each page in x86-128 is 1MiB (2²⁰ 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.

2pts 2²⁰ / 2⁴ = 2¹⁶ (65,536) address entries per pagetable.

QUESTION 3B. How many levels of pagetables would you need to map virtual addresses that cover all 2¹²⁸ bytes in the address space, and why?

6pts 7 levels.

1MiB pages means that 2²⁰ bytes reside within a single page, and thus the offset size is 20. Considering that there are 2¹²⁸ bytes of addressable memory, this means that our page table needs to reference 2^128-20 = 2¹⁰⁸ pages.

• You would therefore need 2¹⁰⁸/2¹⁶ = 2⁹² L1 page tables to refer to all these pages.
• And therefore 2⁹²/2¹⁶ = 2⁷⁶ L2 page tables to refer to all these L1 page tables.
• And therefore 2⁷⁶/2¹⁶ = 2⁶⁰ L3 page tables to refer to all these L2 page tables.
• And therefore 2⁶⁰/2¹⁶ = 2⁴⁴ L4 page tables to refer to all these L3 page tables.
• And therefore 2⁴⁴/2¹⁶ = 2²⁸ L5 page tables to refer to all these L4 page tables.
• And therefore 2²⁸/2¹⁶ = 2¹² L6 page tables to refer to all these L5 page tables.
• And then one L7 page table to refer to all these L6 page tables.

QUESTION 3C. Using your answers from 3A and 3B, how are the bits in the address be split between:

1. unused bits,
2. indexes into different page table levels, and
3. 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
• ...

10pts

• [0, 19] – offset
• [20, 35] – L1 index
• [36, 51] – L2 index
• [52, 67] – L3 index
• [68, 83] – L4 index
• [84, 99] – L5 index
• [100, 115] – L6 index
• [116, 128] – L7 index
• No unused bits

1pt for getting everything right.

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.)

4pts Two possible answers.

1. The IFE process and the control process could use a pipe to communicate.
2. The two processes could have a shared memory region that is read-only for the IFE process but writable by the control process.

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.

8pts Multiple possible answers, depending on answer to previous question.

1. Add pipe() and exec() syscalls, add support for FDs, add read()/write() syscalls over FDs and pipes, (optionally) implement synchronized bounded buffer in the kernel. Control process writes flight stats into the pipe, IFE reads them out.
2. Add support for processes to map shared memory regions at well-known addresses. Map read-only in IFE process, but writably in control process. IFE reads data from the shared memory region, control process periodically writes new statistics. Need synchronization primitives (mutex/conditional variables) to avoid race conditions.

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.

1. int fds[2];
   pipe(fds);
   

2. char* argv1[3] = {"prog1", int_to_str(fds[0], str), nullptr};
   execv("./prog1", argv1);
   

3. char* argv1[3] = {"prog1", int_to_str(fds[1], str), nullptr};
   execv("./prog1", argv1);
   

4. char* argv2[3] = {"prog2", int_to_str(fds[0], str), nullptr};
   execv("./prog2", argv2);
   

5. char* argv2[3] = {"prog2", int_to_str(fds[1], str), nullptr};
   execv("./prog2", argv2);
   

6. close(fds[0]);
   

7. 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.

10pts Two possible solutions.

1. A1/B1/C1 followed by D6, E3, F7, and G4
2. A1/B1/C1 followed by D7, E4, F6, and G3

The process should first pipe before forking, so that both the parent and child process have access to the pipe. For either the child or the parent, we then want to close the end of the pipe that will not be used by the program we exec, and then exec the wanted program, while passing in the correct end of the pipe (the read end for prog2, the write end for prog1) as an argument. We also accepted answers where the read/write ends were not closed for partial credit, however it is good practice to close file descriptors that are not in use by a process.

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.

4pts The memory segments shared after fork (specifically, the code segment) are read-only, so processes can’t write to them! If we were to bypass this by having these shared pages be writable to different processes, that would violate process isolation! Beyond the scope of the class, but also accepted as an answer: Aijah could also mmap regions of memory as MAP_SHARED and writable, which both the child and parent process could write to after forking. However, being independent, the processes would be unable to coordinate reads/writes at the correct location in the shared memory.

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.

6pts Stale values can still exist in processor caches. This design merely moves the problem to the caching hierarchy. Example: Thread 1 on Processor 1 brings address 0x4a56 into the cache, Thread 2 on Processor 2 brings the same address into Processor 2's cache. Now Thread 1 modifies the value in Processor 1's cache and writes back to memory, but Processor 2 still has a stale value in its cache.

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.

4pts

1. Checking if the accounts are active occurs outside of the critical section and is not synchronized. Move the lock() calls to the start of the function or create unique_locks at the start.
2. Doesn't enforce a hierarchical locking scheme for accounts in transfer(), which can lead to deadlock. IDs can be used to give an absolute locking order.

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.

4pts Introduce a condition variable in each BankAccount class to wait in transfer() if the account's balance is negative. deposit() would then call notify_all because after a deposit, the balance is now greater than zero.

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.

1. This implementation violates process isolation (i.e., processes can corrupt each others’ memory).
2. This implementation may cause access to a null pointer.
3. This implementation might return -1 even if there exist two available consecutive pages of physical memory.

6pts

1. True, since kalloc() only allocates one page and the code maps the next physical page too.
2. False, because sufficient error checking on the pointer returned from kalloc() happens.
3. True, as the vmiter may require new physical pages to install the mappings, but no more pages may be available.

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.

4pts The virtual memory is necessarily contiguous (since we allocate a page at addr and a page at 1 page above addr, addr + PAGESIZE), but the physical memory may not be. Our two pages may be in entirely different places because of kalloc().

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?

2pts Yes, this works as intended. This is because, as long as there is no existing mapping for addr or addr + PAGESIZE, we can map both of these virtual addresses to physical pages. Even though the physical memory may not be contiguous, as long as it appears to the user that the memory is contiguous (i.e. as long as the virtual addresses are contiguous), it does not matter if the physical corresponding addresses are not, as the page table will handle the translation appropriately.

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.

4pts To ensure atomic operations, MultiPut operations must lock all relevant buckets before inserting into the map. Since the number of key-value pairs per MultiPut operation greatly exceeds the number of buckets, every bucket would be locked with high probability and essentially serialize all MultiPut operations.

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?

3pts Only one bucket needs to be locked before inserting the relevant item. The probability that separate Puts try to lock the same bucket is much lower, so multiple Puts can execute in parallel. By comparison, MultiPut locks many buckets at once and prevents other MultiPuts from executing in parallel.

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 the DbItem 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 the DbItem. 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 the DbItem, 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).

7pts The ordering of the linked list is not thread safe, and can change (this is a race condition)! For example, suppose thread T1 wants to get an element E into a list L, which contains E. Thread T2 wants to delete E from list L. Thread T1 finds the relevant bucket and parses the list for element E. Once thread T1 finds the location of element E in the list, but before it’s able to lock the associated mutex, T2 starts executing. T2 finds element E in the list and is able to lock its associated mutex. T2 then deletes E and removes it from the list. When T1 resumes executing, it tries to access element E, but that data has been deleted, even though thread T1 still thinks E exists in the list! This causes a segmentation fault, and the process crashes.

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.

2pts Any answer

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.

2pts Any answer

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.

2pts Any answer