CS 300/1310 Spring 2022 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 so far. 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.

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 quizs. 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 midterm subdirectory in your cs300-s22-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. Operating Systems (8 points)

QUESTION 1A. Name and briefly describe two ways in which execution may transition from userspace into the kernel. When would either of these occur, and what component (userspace code, kernel, hardware) initiates it?

4pts Several options:

• System calls: initiated by userspace code when processes need the kernel to do something
• Timer interrupt: initiated by the hardware on a periodic basis
• Exceptions: initiated by the hardware when userspace processes perform forbidden operations (privileged instructions, page fault, bad memory access)
• Other interrupts: initiated by the hardware, e.g., when I/O data available

QUESTION 1B. Your friend Gina D'Bug is confused about why the PTE_U memory protection flag exists. After all, they argue, the kernel has its own page table, so there's no need to make kernel memory mappings available to processes and doing so only invites security problems. Instead, they propose to do away with PTE_U and just map only user-space accessible memory for processes, and kernel memory for the kernel.

Explain why Gina is wrong. [Hint: you may wish to consider the system call enter/return sequence.]

2pts Kernel memory must be mapped in the process page tables so that the processor can execute machine instructions from the kernel code segment after a syscall. Note that the syscall instruction changes protection level, but does not change the page table to the kernel page table.

QUESTION 1C. Eve, who is sick of not being able to access and modify kernel code, comes up with an ingenious attack. All she needs to do is modify the permission bits of the kernel pages in her process' pagetable so that her process also has access to kernel pages; in other words, she needs to set PTE_U on those pages. Why will Eve's attack fail?

2pts The page tables aren't accessible for writing by userspace code. Their physical pages don't have virtual addressed mapped to them that have PTE_U set (i.e., the page table pages are only accessible to software inside the kernel).

2. Virtual Memory (12 points)

QUESTION 2A. For each of the following statements, indicate whether it is true or false.

1. Each physical address has at most one corresponding virtual address (or zero if it's unmapped).
2. Each virtual address has at most one corresponding physical address (or zero if it's unmapped).
3. A non-identity virtual memory mapping is always more space-efficient than an identity mapping.
4. A non-identity address mapping is necessary for process isolation.

4pts

1. False (shared pages across processes)
2. True
3. False (will use at least as many page table entries, and may use more)
4. False (cf. WeensyOS step 2)

QUESTION 2B. The ARM64 architecture used in Apple Silicon processors uses 64-bit (8 byte) addresses, with only 48 of the 64 address bits actually used (as on x86-64). But ARM64 supports two different base page sizes: 4 KB and 16 KB. Why might the ARM64 designers have chosen to support larger pages?

2pts Reduced number of page table pages needed; much data in modern computing is much larger than 4 KB, so a coarser granularity makes sense; potentially better locality of data stored within a page (16 KB would be four different pages with 4 KB pages, which might be at very different physical addresses); lower TLB pressure.

QUESTION 2C. Both the 4 KB and 16 KB page sizes on ARM64 use four-level page tables, with virtual addresses split as shown below. (Note that each page table is itself stored in a 16 KB page when using 16 KB pages, and consequently can store more 8-byte entries than with 4 KB pages.)

4 KB pages

 63    48|47      39|38      30|29      21|20      12|11     0   <-- VA bit
+--------+----------+----------+----------+----------+--------+
| UNUSED | L4 index | L3 index | L2 index | L1 index | offset |
+-------------------+----------+----------+----------+--------+

16 KB pages

 63    48| 47 |46       36|35       25|24       14|13        0   <-- VA bit
+--------+----+-----------+-----------+-----------+-----------+
| UNUSED | L4 | L3 index  | L2 index  | L1 index  | offset    |
+--------+----+-----------+-----------+-----------+-----------+

[Note: because virtual addresses use only 48 bits, the L4 index here is a single bit. This means there can only be two L3 page tables when using 16 KB pages.]

Other (non-M1) ARM64 processors also support 64 KB pages, which allow for up to 52 address bits to be used! Based on what you know about page table design and above examples, how many levels of page table are needed to translate virtual addresses to physical addresses in this scheme with 64 KB pages? Briefly explain why, giving the bits that index into each level of the page table.

6pts Three levels. 64 KB page size means an offset of 16 bits (2^16 = 65,535). Each page table can store 64 KB / 8 bytes = 8,192 = 2^13 entries, so we need 13 bits of index for each level; L1 is bits 16-28, L2 is 29-41, L3 is 42-51 (we only have 10 bits left here).

3. Project 4: WeensyOS (6 points)

QUESTION 3A. Bruno is an eager CS 300 student who has decided to implement the exec system call as extra credit for their WeensyOS submission. Remember that on Unix systems, exec is a system call that replaces the currently running process with a new program. For example, in WeensyOS we might call exec from within p-allocator to switch to p-fork without rebooting. Bruno thinks that each of the following will change after a call to exec. For each, specify if Bruno is right ("true" or "false").

1. The process's page table will change.
2. The value in the processor's %rip register will change.
3. The virtual address of the stack will change.

3pts

1. True
2. True
3. False

QUESTION 3B. While implementing exec, Bruno realizes there's a wrinkle he hasn't considered: exec also allows the user to pass arguments to the new process in the form of a null-terminated array of pointers to null-terminated strings, such as:

char* arg0 = "p-fork";
char* arg1 = "10";
char* args[3];
args[0] = arg0;
args[1] = arg1;
args[2] = NULL;
sys_exec("p-fork", args);

Bruno decides that since args is available in the kernel as an argument to the system call, he can simply make the address passed in this argument available to the new process as argv, and the new program can then access its arguments. Why will Bruno's approach not work?

3pts Since the strings and the array are allocated in the old program's memory, they will be gone and the pointer will be invalid when the new program starts. The arguments either have to be copied to kernel memory or to a page that isn't replaced on exec.

4. Processes (10 points)

QUESTION 4A.

Consider the two programs below.

prog1:

int main() {
  char* argv[2];
  argv[0] = (char*) "prog2";
  argv[1] = nullptr;

  if (fork() == 0) {
    int r = execv("./prog2", argv);
    printf("After execv! pid %d\n", getpid());
  } else {
    int status;
    waitpid(-1, &status, 0);
    printf("Parent! pid %d\n", getpid());
  }
}

prog2:

int main() {
  printf("pid %d\n", getpid());
}

Which two of the following options are valid output if you run prog1? Give a brief justification for each invalid option.

1.

Parent! pid 5
pid 4

2.

pid 4
Parent! pid 4

3.

pid 5
Parent! pid 4

4.

pid 5
After execv! pid 5
Parent! pid 4

5.

After execv! pid 5
Parent! pid 4

6.

Parent! pid 4
pid 4

6pts

1. Wrong, parent will wait for child.
2. Wrong, child PID should change.
3. Correct.
4. Wrong, if execv is successful, parent code after execv will not run.
5. Correct.
6. Wrong, parent will wait for child and child PID should change.

QUESTION 4B. New engineer Chris P. Iper is developing a scheme to have three processes communicate via pipes. Here is the code Chris wrote:

int pipes[6];

for (int i = 0; i < 3; i++) {
  pipe(&pipes[i*2]);
  fork();
}

Chris suggests that after the pipes are set up in this way, each of the three processes can communicate with every other process by using the three pipes with ends in pipes (e.g., process 1 uses pipes[0] to read messages, while other processes use pipes[1] to write messages to process 1; process 2 uses pipes[2] to read messages, etc.).

Give two reasons why Chris's plan will not work as intended.

4pts

1. Chris will end up with eight processes, not three, because he forks in a loop that iterates three times.
2. The pipes arrays in different processes are independent, so the first process will only have one pipe available, and others are similarly limited.
3. Multiple processes shouldn't be using the same pipe to both read and write communicate (the question intended unidirectional messaging, but we accepted this answer too).

5. Threads and Race Conditions (10 points)

In the first project, we asked you to implement the Snake game with a single playable snake. Now that you are a huge Snake fan, you want to spice things up and use threads to create a multi-snake game! Your (naive) plan is to have one thread running for each snake on the board, and to have one score indicating the total points gained by all of the snakes.

QUESTION 5A. Give one reason why you might choose to use multiple threads for the multi-snake game instead of multiple child processes.

2pts Several possible answers, including: we're building a game that requires truly shared data across parallel requests; the additional security that interprocess communication provides isn't necessary here; much more intuitive design.

QUESTION 5B. What is one race condition you might encounter when running this multi-snake game without the addition of mutexes, atomic variables, and condition variables? Make sure to include the variable on which the race condition might occur and where it is stored in memory (e.g., stack, heap, data, or code segment).

2pts We might encounter a race condition on the score variable, which we store in the data segment as a global variable, since several snakes might eat food at the same time and try to increment the total score.

QUESTION 5C. Consider the following C++ code.

int secretNum = 404;

int main() {
    int numConcentrators = 1600;
    std::vector<int> courses = { 300, 320, 330 };
    std::thread p1(child, &courses);
    secretNum += 1;
    print();
    p1.join();
}

int child(std::vector* v) {
    secretNum *= 2;
    v->push_back(300);
    print();
    return 0;
}

void print() {
    char buf[100];
    snprintf(&buf[0], 100, "Hello from pid %d, secretNum=%d\n", getpid(),
             secretNum);
}

Indicate whether the following statements are true or false, and give a 1-sentence justification:

1. The thread running child() and the main thread share the integer secretNum.
2. The thread running child() and the main thread share the integer numConcentrators.
3. The thread running child() and the main thread share the vector courses.

6pts True. (Explanation: Threads share global variables.) False. (Explanation: Threads do not share their stacks.) True. (Explanation: Threads share their heap.)

6. Project 5: Vunmo (4 points)

QUESTION 6A. Your friend Razz B. Ree is currently trying to implement get_two_accounts in Vunmo, which, as you will recall, has the following method signature:

int Server::get_two_accounts(uint64_t first_id, account_t **first_account, uint64_t second_id, account_t **second_account)

Their current strategy is to lock the accounts in the order that they are passed into the function, since the first two arguments of the function will always come before the last two arguments of the function.

What is the problem with Razz's strategy, and what synchronization bug will it lead to? Assuming a single-processor system, give a concrete example of a sequence of function calls and timer interrupts across threads that will lead to this problem.

Provide your answer in the following format:

 1. Thread # calls FUNCTION_NAME(...) (provide arguments)
 2. Subsequent event 1
 3. Subsequent event 2 …

(You may refer to the account_t struct associated with an account ID as account_<id>.)

4pts The problem is deadlock; it can arise because of inconsistent locking order. Example trace:

1. Thread 1: get_two_accounts(1, account_1, 2, account_2)
2. Timer interrupt after thread 1 locks account_1 mtx
3. Thread 2: get_two_accounts(2, account_2, 1, account_1)
4. Timer interrupt after thread 2 locks account_2 mtx
5. Thread 1 tries to lock account_2 mtx, fails, and blocks
6. Interrupt switches execution to thread 2
7. Thread 2 tries to lock account_1 mtx, fails, and blocks

7. Synchronization (8 points)

QUESTION 7A. Consider the following piece of C++ code. Class LazyContainer exposes an expensive_object_t* via its get() method. Creating expensive_object_t is costly, so the field holding it is initialized the first time get() is called.

typedef struct expensive_obj {} expensive_obj_t;

class LazyContainer {
  expensive_obj_t* get();

 private:
  expensive_obj_t* o;
};

expensive_obj_t* LazyContainer::get() {
  if (!this->o) {
    this->o = create_expensive_obj(); // heap-allocates expensive_object_t
  }
  return this->o;
}

The code works fine in a single-threaded program: if this->o is not created, it is instantiated once. Subsequent calls to get() will not re-instantiate the object.

Now consider a multithreaded program in which two threads may execute get() concurrently. Which of the following issues can happen here, and how?

1. Null pointer dereference
2. Memory leak
3. Segmentation fault due to accessing memory in another address space
4. Use after free

4pts Memory leak. There is a data race with assigning a pointer to this->o. Two threads could both find o to be null, both create an expensive object, and assign to the o field. The first assignment to o will be overwritten by the second, causing a leak.

QUESTION 7B. Now consider this thread-safe implementation of LazyContainer::get():

class LazyContainer {
  expensive_obj_t* get();
 private:
  expensive_obj_t* o;
  std::mutex o_mtx;   // NEW
};

expensive_obj_t* LazyContainer::get() {
  this->o_mtx.lock();
  if (!this->o) {
    this->o = create_expensive_obj();
  }
  this->o_mtx.unlock();
  return this->o;
}

It is costly to obtain a mutex every time get() is called; this->o is not mutated after it is initialized, after all. Concerned about performance, an engineer proposes another solution:

expensive_obj_t* LazyContainer::get() {
  if (!this->o) {
    this->o_mtx.lock();
    this->o = create_expensive_obj();
    this->o_mtx.unlock();
  }
  return this->o;
}

The idea is to only use mutex when necessary: once this->o is initialized, all future accesses to this member are read-only and therefore do not require synchronization. Explain why this implementation is not thread-safe, giving a sequence of events that will lead to a problem.

4pts Example scenario:

1. Thread 1 and 2 both checks whether o is NULL, and both find o is NULL.
2. Both threads go into the if block.
3. Thread 2 obtains the mutex first, initializes o and returns.
4. Thread 1 obtains the mutex second, initializes o, overwriting the previously initialized object. The previous object is now leaked.

8. Networking and Distributed Systems (5 points)

QUESTION 8A. Consider the client/server sequence of system calls for network communication via TCP/IP (socket()/connect() on the client; socket(), bind(), listen(), accept() on the server). After which point in this sequence is the server port no longer available to other processes or connections on the same machine?

1pt After bind(), which associates the port with the listening socket.

QUESTION 8B. After getting a judge to drop all charges of cyber crime in exchange for three years of grading server maintenance, Eve has decided to end her hacker days. Instead, she now toils away building scalable distributed systems infrastructure for universities.

Brown University has hired Eve's company to improve the CAB system for course registration, which has been afflicted by outages and slowness when eager students descend to enroll in their classes.

Eve suggests increasing the scalability of CAB by sharding the backend across multiple different servers. But since Eve has little experience with distributed systems design, you need to help her decide how to shard CAB. Which of the following options would work best, and why?

1. Shard the workload by student ID, and have each course's information replicated on every server so that student enrollments can be processed locally.
2. Shard the workload by course ID, and direct student requests to the right server for the course they're trying to enroll in.
3. Order the courses by the number of students currently pre-registered in them and shard the range equally across servers.
4. Have data for all students and courses replicated on all servers and send each request to a randomly-chosen server.

4pts Sharding by course ID works best because all state related to a course is in the same place.

Sharding by student ID requires replicating course information, which will be difficult to keep consistent.

Sharding by the number of preregistered students will put all the most popular courses on the same server, potentially overloading it.

Sending requests to random servers requires all information to be replicated N times for N servers, which wastes space and raises consistency issues.

9. Project 6: Distributed Store (6 points)

Bacefook (without a dynamic implementation of the shardmaster) has been up and running for some time, but so far it hasn't been able to compete with the other social media giants (unfathomable!). Some users complain that it is too slow and have been leaving the platform.

QUESTION 9A. A new Bacefook intern, Zark Muckerberg, has a plan to address this! First, he wants to remove the pull-based model for shard configurations by removing the code where shards periodically query the shardmaster for the configuration, as he believes that all of these queries are unnecessarily increasing network traffic. Why will Zark's change break Bacefook's correctness?

2pts Removing the shardmaster querying code also gets rid of the code that moves data to the new shard. This means ShardKVs will not contain the data they are responsible for.

QUESTION 9B. Next, Zark wants to introduce dynamic load balancing. His plan is for all clients to notify the shardmaster whenever they make a request, so the shardmaster can keep track of the request load on each server and continuously change the configuration so that the load is always perfectly even between all of the servers. Assume that the shardmaster is very fast and contacting it can happen asynchronously, so the shardmaster will not bottleneck this scheme. What is a possible negative consequence of Zark's idea?

2pts Dynamically changing the configuration so that the load is always perfectly even changes the configuration too much, and will cause excess network traffic and overhead from moving keys too often.

QUESTION 9C. The CEO of Bacefook decides not to go with Zark's idea. Unfazed by the rejection, a resilient Zark comes back with a new proposal that he heard about in class: strongly consistent replication! Why will strongly-consistent replication for all data still not solve Bacefook's problem of slow response times?

2pts Strongly-consistent replication requires taking locks on all servers, which is strictly more work than what Bacefook is already doing without replication. This form of replication helps tolerate server failures, but does not improve performance.

10. CS 300/1310 Feedback (6 points)

QUESTION 10A. 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 10B. 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 10C. 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.