Final Quiz (Spring 2026) #


Rules #

Read these rules carefully! In this final, you CANNOT interact with others, use AI tools, broadly search the Internet, or access shared documents or editors. If you violate these rules, we will treat this as a matter of academic integrity and follow the process given by the Brown Academic Code for conduct violations.

The final is open book, open note, limited 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 some online resources. Specifically:

  • You may access any paper notes you took in class, and use the x86-64 assembly quick reference sheet we gave you.
  • You may access a web browser and a PDF reader.
  • You may access your own notes and your assignment code electronically.
  • You may access an Internet site on which your own notes and assignment code are stored.
  • You may run a C/C++ compiler, including an assembler and linker, or use a compiler explorer.
  • You may access manual pages and common utilities, including calculators and a Python interpreter.
  • You may access this year’s course website and notes on it, including lecture notes and links to reference materials, like cppreference.com.
  • You may access EdStem (though you may not post there during the final).
  • You may access other online reference materials that are not otherwise prohibited by this policy,so long as you bookmark them before the final to avoid needing to do a general web search (see below). Consider this a computer-based extension of the “open notes” policy: if you’ve discovered other online resources not linked on our site that work well for you, it’s okay to use them, so long as you make note of them beforehand.
    • Tip: you can bookmark sites in your browser, just make a doc with links, or add them to your other notes! Any format is fine, so long as it follows our other rules.
  • You may access previous CS 300 exams and their solutions found on our course website, although our questions will be different and prior exams do not have 1:1 equivalent questions, so the use of looking at them will be limited.
  • You may search for reference materials on Wikipedia or StackOverflow, but only from the search boxes built into these sites, and not a regular search engine.

However:

  • You cannot use AI tools (like ChatGPT, Github Copilot, Claude, and others) during the final. This also includes AI-based source code analysis tools, like assembly-to-C converters, IDE-based AI chatbots, coding agents, or other AI services. If your IDE or browser has an integrated AI, disable or hide it.
  • You cannot broadly search the Internet for answers to final questions. Instead, stick to our course site, your notes, and your bookmarks.
    • Exception: you may search for resources on Wikipedia and StackOverflow, but only from the search boxes built into these sites, and not from a general search engine.
  • You cannot access online question forums, except for StackOverflow and our course’s EdStem (as mentioned above).
  • You cannot access solutions from any previous exam, by paper or computer, except for those on our course site.
  • You absolutely may not contact other humans via chat, phone calls, posting questions to forums, a shared Google Doc, or anything like it, with the exception of the 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.

Additionally, students are taking the final at different times. Do not post publicly about the final until given permission to do so by course staff. This includes general comments about final difficulty.

Completing your final #

You have 180 minutes to complete the final starting from the time you press “Start”.

Different students may have different finals. 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-s26-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. VM/Page Tables (10 points) #

QUESTION 1A Jeffrey and Claire are considering the following statements about virtual memory and page tables. For each statement, help them figure out if the statement is correct! Write either “true” or “false” and explain your reasoning. You must provide an explanation to receive credit.

Some statements involve the x86-64 architecture, where virtual addresses use a 4-level page table structure, like we discussed in class. Here’s a diagram of the x86-64 virtual address layout, for reference:

Other questions involve other architectures. We don’t go into deep detail for those, but give you sufficient information to answer the questions.

  1. Two consecutive virtual addresses always correspond to consecutive physical addresses.
  2. On the x86-64 architecture, if two virtual addresses a and b have the same value for bits 12-20, then a and b must be located in the same physical page.
  3. On the x86-64 architecture, if two virtual addresses c and d have the same value for bits 12-47, then c and d must be located in the same physical page.
  4. MacOS on the ARM64 architecture (e.g., iPhones and Macbooks) uses pages that are 16,384 bytes (16 KB) in size. In this design, each virtual address needs a page offset of at least 14 bytes.
  5. In a future architecture where virtual addresses are 128 bits, physical addresses must also have at least 128 usable bits.

2. WeensyOS (10 points) #

Rahel is implementing the fork() system call in WeensyOS. When setting up the child process’ metadata, she writes the following line of code to set the %rsp register for the child process:

// Set child %rsp to parent %rsp
ptable[child_pid].regs.reg_rsp = ptable[parent_pid].regs.reg_rsp;

QUESTION 2A Ethan suspects that this line of code is problematic because using the parent’s %rsp register in the child would allow the child to modify the parent’s stack. Why is Ethan wrong and Rahel’s approach is actually correct? Briefly justify your reasoning (at most one sentence).

QUESTION 2B Ethan wants to modify WeensyOS to support threads and wants to implement a new system call sys_thread_spawn() that a process can use to start a new thread. Each new thread should share the same memory as the thread that calls sys_thread_spawn(), but be able to execute independently. Here’s an example of how a userspace process might use the new syscall:

void func(int x) {
    // Do some stuff ...
}

int process_main() {
    // ...

    // create thread starting from func, pass argument 42
    sys_thread_spawn(threadfunc, 42);
    // ...
}

To implement the kernel handler for the new syscall, syscall_thread_spawn(), Ethan starts with an implementation of syscall_fork(), which finds a free entry in ptable for the new thread, and then removes all the other code. From here, Ethan is brainstorming what other functionality would be needed to finish his implementation.

Which of the following operations would be needed in order to correctly implement threads? For each option, write “correct” or “incorrect” and briefly explain your reasoning (a few words, at most one sentence). You must provide an explanation to receive credit.

  1. Set the %rip register with the same value as the parent.
  2. Create a new page table to store virtual-to-physical address mappings for the new thread.
  3. Call kalloc to allocate a new page for the thread’s stack and map it in the page table.
  4. Set the %rsp register to point to MEMSIZE_VIRTUAL (i.e., the end of virtual memory), since the stack grows from high to low addresses.

3. Systems Calls and Kernel Protection (12 points) #

QUESTION 3A Malte wants to trim down what data is stored for each process in the process descriptor. Malte wants to remove %rbp from the list of registers that needs to be saved. He claims that saving it is unnecessary because the value of %rbp is available as part of the process’s stack memory, and specifically in the saved %rbp value at the top of the current (callee) function’s stack frame.

For reference, here is a diagram of a typical stack frame on x86-64:

Why is Malte wrong, and why does the value in the %rbp register actually need to be saved? (Answer in 1-2 sentences.)

QUESTION 3B Deepti was too distracted thinking about ice cream, so while editing the function in the kernel that implements the syscall_fork() system call, she wrote the following code:

int syscall_fork() {
  pid_t new_pid = 0;
  int i = 0;
  while (new_pid == 0) {
    if (ptable[i].state == P_FREE) {
      new_pid = i;
    }
    if (i == PID_MAX) {
      i = 0;
    } else {
      i++;
    }
  }

  // rest of fork() implementation...
}

When Deepti runs her kernel with this syscall_fork() function, she finds that it sometimes hangs indefinitely. Under what circumstances does her kernel hang, and why doesn’t the hardware timer interrupt help? (Answer in 2-3 sentences.)

Hint: in WeensyOS, interrupts are enabled in userspace, but disabled when executing kernel code.

QUESTION 3C Eve gained access to the kernel’s source code from lecture (DemoOS). As usual, Eve is trying to create a process that lets her hog all the processor time. Eve realizes that even though the kernel enables timer interrupts for userspace execution, which normally prevents Eve from hogging the processor, the kernel code uses a global variable, INTERRUPT_TIME, to set the timer interrupt frequency.

Note: in the actual WeensyOS code, the interrupt frequency is called HZ and defined via a #define in C. For the purposes of this question, assume that the frequence is stored in global variable INTERRUPT_TIME, defined as below.

int INTERRUPT_TIME = 1000;
...
// inside kernel setup function
init_timer(INTERRUPT_TIME);

Eve tries to take over the computer by finding the address of INTERRUPT_TIME (by looking at the object dump output) and changing INTERRUPT_TIME to be the largest integer possible. However, Eve’s attack is foiled by a clever student (you!) implementing protections when setting up process page tables (in process_setup of WeensyOS).

Answer the following questions about the attack and why proper memory protections help:

  1. Which memory segment of the kernel is INTERRUPT_TIME located in, and what general physical address range does this fall into? (2 pts)
  2. What arguments must be passed to vmiter::map() when setting up a process’s page table to ensure that Eve cannot write to INTERRUPT_TIME? Give your answer in terms of a range of virtual addresses, range of physical addresses, and permission flags to use for them (e.g., “VA range: 0x0 to MEMSIZE_PHYSICAL, PA range: 0x0 to MEMSIZE_PHYSICAL, permissions: PTE_P | PTE_W | PTE_U”).

4. KVStore/Sharding (10 points) #

Alex is working on implementing the Leave() function for his KVstore in Project 5B. In his version, instead of assigning the leaving server’s shards to the server listed first in the configuration, he assigns those shards to the server that is currently responsible for the least number of keys.

QUESTION 4A Give one example for when Alex’s approach might offer improved performance compared to the original approach in the project, and one example where it might decrease performance.

Hint: Consider that different keys may experience different request loads.

QUESTION 4B Akshay thinks the real scalability problem is the single, centralized shardcontroller. Instead, Akshay proposes that the KVStore should use two shardcontrollers, with each shardcontroller storing a copy of the same configuration. Then, clients could use either shardcontroller (e.g., by choosing at random), instead of being dependent on just the one shardcontroller.

Give one advantage and one disadvantage of Akshay’s two-shardcontroller approach; your answer for each should be a few words, at most one sentence.

QUESTION 4C Having discarded their prior approaches, Alex and Akshay decide on a new plan. Instead of partitioning keys by letter ranges (as in the KVStore project), Alex and Akshay hash-partition the keys by hashing them and then applying a modulo by the number of servers. In other words, a client now figures out which server is responsible for a key by computing:

responsible_server = hash(key) % num_servers

Alex and Akshay point out that with this scheme no shardcontroller is needed at all.

Give one reason why (or situation in which) Alex and Akshay’s scheme will perform worse than the original, range-based sharding approach with a shardcontroller. Explain in 1-2 sentences.

5. Threads (14 points) #

Yash and Allen are tired of hearing Malte complain about Courses@Brown (CAB), so they decide to start building their own version. They start by tackling the problem of reserving classrooms for each course: they write the following program that has a struct with information about each course, and a separate map (reservations) that maps each room (“MacMillan 117”) to a course name (“CS 300”). A room will point to an empty string if no course is assigned to it. For now, they ignore time slots and focus only on rooms, so no two courses should ever use the same room.

Yash and Allen want to use threads to handle requests to change classrooms. Each request makes a new thread that runs the function request_room_change. To protect their shared data, Yash and Allen use two mutexes: one for each course struct, and one for the reservations map. Here’s their program so far (with an example main() function that shows a request):

struct CourseInfo {
    CourseInfo(std::string n, std::string r, int s) {
        name = n;
        room = r;
        num_seats = s;
    }

    std::string name;
    std::string room;
    int num_seats;
    std::mutex course_mtx;
};

std::map<std::string, CourseInfo*> all_courses;
std::map<std::string, std::string> reservations; // map<room, course name>
std::mutex rooms_mtx;

bool request_room_change(std::string course_name, std::string new_room) {
    bool success = false;

    CourseInfo* course = all_courses[course_name]; // look up course

    course->course_mtx.lock();
    std::string current_room = course->room;

    if (reservations[new_room].size() == 0) { // if room is not in use
        rooms_mtx.lock();
        reservations[current_room] = "";
        reservations[new_room] = course_name;
        rooms_mtx.unlock();

        course->room = new_room;
        success = true;
    }

    course->mtx.unlock();
    return success;
}

int main() {
    CourseInfo* cs300 = new CourseInfo("cs300", "Salomon 001", 170);
    CourseInfo* visa120 = new CourseInfo("visa120", "List 120", 65);
    // ...

    // Example request
    std::thread th1 = std::thread(request_room_change, "cs300", "MacMillan 117");
    std::thread th2 = std::thread(request_room_change, "visa120", "MacMillan 117");
    // ...

    th1.join();
    th2.join();
    // ...
}

QUESTION 5A Yash and Allen test out their existing program with lots of requests and notice a bug: some courses end up double-booked in the same room! For example, if they print out the all_courses map after all requests are done, they sometimes see examples like this:

Course: CS 300, Seats:  170, Room: MacMillan 117
Course: VISA 120, Seats:  65, Room: MacMillan 117

Why does this problem occur? Explain your reasoning and give an example of a problematic interaction between threads. You can use the two threads created in main as an example, or create more.

QUESTION 5B Yash and Allen agree that they need to change how the mutexes are used, but they can’t decide how. The code below contains a copy of the request code with the mutex code removed. Propose a fixed version by assigning each line below to one of the points labeled (POINT A, POINT B, POINT C, …), and explain your reasoning.

Your answer should have the form “Line 1 => Point X, Line 2 => Point Y, …” followed by an overall explanation (2-3 sentences) of how your design solves the problem. You may assign two lines to one point in the code; if you do, specify which line must come first.

  • Line 1: rooms_mtx.lock();
  • Line 2: rooms_mtx.unlock();
  • Line 3: course->mtx.lock();
  • Line 4: course->mtx.unlock();
bool request_room_change(std::string course_name, std::string new_room) {
    bool success = false;

    CourseInfo* course = all_courses[course_name]; // look up course

    // ***** POINT A *****
    std::string current_room = course->room;

    // ***** POINT B *****
    if (reservations[new_room].size() == 0) { // if room is not in use
       // ***** POINT C *****
       reservations[current_room] = "";
       reservations[new_room] = course_name;
       // ***** POINT D *****

       course->room = new_room;
       // ***** POINT E *****
       success = true;
    }

    // ***** POINT F *****
    return success;
}

6. Fork/Pipes (12 points) #

Eric writes the following program that uses fork() to create two child processes that communicate with each other via a pipe:

int main() {
    int fds[2];
    pipe(fds);

    pid_t p1 = fork();
    if (p1 == 0) {
        printf("Child is born\n");
        write(fds[1], "hi", 2);
        exit(0);
    }

    pid_t p2 = fork();
    if (p2 == 0) {
        printf("Sibling is born\n");
        char buf[6];
        memset(buf, 0, 6);
        int read_bytes = 0;
        while (read_bytes != 2) {
           read_bytes += read(fds[0], buf, 6);
           printf("Received: '%s'\n", buf);
        }
        exit(0);
    }

    int status1;
    waitpid(p1, &status1, 0);

    int status2;
    waitpid(p2, &status2, 0);

    printf("Goodbye from %d\n", getpid());
    return 0;
}

QUESTION 6A Of the following options, which options MIGHT be printed as a result of running this program? For each option, say whether it can or cannot be printed, and in either case explain why this is the case (1-2 sentences).

Option 1:

Child is born
Sibling is born
Received:  'hi'
Goodbye from

Option 2:

Sibling is born
Child is born
Received: 'hi'
Goodbye from

Option 3:

Sibling is born
Received: 'hi'
Child is born
Goodbye from

Option 4:

Child is born
Sibling is born
Received: ''
Received: 'hi'
Goodbye from

QUESTION 6B While Eric isn’t looking, Alaina stealthily modifies Eric’s program: she swaps the order of the call to pipe() and the first call to fork(), so the program starts like this:

 int main() {
    int fds[2];

    pid_t p1 = fork();
    pipe(fds);   // <----- *** Now occurs AFTER fork!!! ****
    if (p1 == 0) {
        // ... rest of program unchanged ...
        }
   // ... rest of program unchanged ...
 }

When Eric runs the changed program, it prints only this:

Child is born
Sibling is born
// .. and then it hangs!

In two to three sentences, explain why Alaina’s change causes the program to hang. Your answer should provide an explanation that relates to how the processes use the pipe (i.e., it’s not sufficient to say “because fork is called first”).

7. UB (12 points) #

QUESTION 7A Curtis and Jennifer had some time over the reading period and want to improve how README files are processed during grading. They write the following program, but Deepti and Malte have some concerns about undefined behavior. What about Curtis’s and Jennifer’s code is suspicious?

Identify 3 instances of undefined behavior (out of four total), and for each instance, answer with the line number/code and a brief explanation of the issue (e.g. “Line 7, dereferencing a null pointer”).

Do not list more than three instances of undefined behavior. If you do, you will get no extra credit and lose points for each incorrect answer, regardless of the number of correct answers you provide.

You can assume that any helper functions not shown are correct and do not have UB.

 1 #include <thread>
 2 #include <vector>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <stdio.h>
 7
 8 struct ReadmeFile {
 9     char* project_id;
10     char* response;
11 };
12 const char* project_id = "WeensyOS";
13
14 int* analyze_response(char* response) {
15    int valid = 1;
17    if (strlen(response) < 50) {  // Check if response is long enough
18        valid = 0;
19    }
20    return &valid;
21 }
22
23 void process_readme(int* total_valid, ReadmeFile* readme) {
24     if (strcmp(project_id, readme->project_id) == 0) {
26        int* is_ok = analyze_response(readme->response);
27        *total_valid = *total_valid + *is_ok;
28     }
29 }
30
31 int main() {
32   std::thread threads[10];
33   std::vector<ReadmeFile> readmes;
34   int total_valid = 0;
35   int ready_to_grade = 0;

36   fetch_readmes(readmes);  // Code not shown, assume UB-free
37
38   for (int i = 0; i < 10; i++) {
39       threads[i] = std::thread(process_readme, &total_valid, &responses[i]);
40   }
41
42   // Can start grading after 20 valid READMEs are submitted
43   if (total_valid > 20) {
44      ready_to_grade = 1;
45   }
46
47   for(int i = 0; i < 10; i++) {
48       threads[i].join();
49   }
50
51   short* secret_code = (short*)malloc(sizeof(short));
52   *secret_code = 14235;
53   free(secret_code);
54   upload_results(*secret_code, responses, ready_to_grade);
55   return 0;
56 }

8. Condition Variables (14 points) #

Bhavani and Praveen are developing a synchronized queue that can be used to send data across threads, similar to a bounded buffer but bounded to a maximum number of elements (MAX_QUEUE_SIZE) rather than a buffer size.

Here is their code:

const unsigned long MAX_QUEUE_SIZE = 5;

struct Queue {
  unsigned long queue_len;
  std::condition_variable nonfull;
  std::condition_variable nonempty;
  // ... other fields for storing the data in the queue
}

void Queue::push(std::string s) {
  std::unique_lock guard(this->mutex);
  while (this->queue_len == MAX_QUEUE_SIZE) {
      this->nonfull.wait(guard);
  }

  this->add_item(s);
  // PART C: unlock mutex here for Part C
  this->queue_len++;
  this->nonfull.notify_all();
}

std::string Queue::pop() {
  std::unique_lock guard(this->mutex);
  while (this->queue_len == 0) {
      this->nonempty.wait(guard);
  }

  std::string s = this->remove_item();
  // PART C: unlock mutex here for Part C
  this->queue_len--;
  this->nonempty.notify_all();
  return s;
}

QUESTION 8A Bhavani writes a single-threaded test case that tries pushing and popping some items from the queue but finds that it blocks indefinitely. Give an example snippet of operations on the queue that could have caused this behavior.

For your answer, you may assume that a variable named queue exists and that it is an instance of Queue. Correct answers to this question require no more than about three lines of code.

QUESTION 8B Bhavani runs the (still unfixed) program with two threads, started at the same time where one pushes and one pops from the queue. She finds that it sometimes blocks indefinitely. Why might this be happening? Explain, in 2-3 sentences, why this might sometimes happen in the reader and sometimes happen in the writer. Your answer must address why the issue occurs some of the time.

QUESTION 8C Bhavani fixes the program and shows it to Praveen. Praveen proposes to make the critical region smaller and the program faster by making the following changes:

  1. Praveen proposes unlocking the mutex after adding/removing an item (at the lines marked “PART C” in the code), rather than using the guard; and
  2. Praveen proposes defining queue_len as an atomic variable (e.g., std::atomic<unsigned long>), since atomic variables are safe to access from multiple threads outside critical regions.

Bhavani argues that with these changes, the queue would no longer be properly synchronized. Why is Bhavani right?

Explain in one to two sentences, and give a concrete example of an execution that leads to incorrect behavior. For your concrete execution, be sure to mention whether you assume it runs multiple threads on a single CPU or there are multiple processors. Specify the execution as a sequence of steps/states, such as “1. T1 calls push() on an empty queue.”

Hint: For this question, think about boundary conditions (e.g., the queue is almost full or almost empty) and what thread interleavings could lead to problems such as an incorrect queue length or more/fewer items in the queue than indicated by queue_len.

9. CS 300 Feedback (6 points) #

QUESTION 9A What is one aspect of CS 300/1310 that we should definitely retain for future years? Any answer but no answer will receive full credit.

QUESTION 9B What is one aspect of CS 300/1310 (other than firing the instructors and dropping the exams) that we can improve for future years? Any answer but no answer will receive full credit.

QUESTION 9C Which CS 300/1310 projects were your most and least favorite ones, and why? Any answer but no answer will receive full credit.

Creative Commons Licence This work is licensed under a Creative Commons Attribution 4.0 International License.