Computer Science 162
University of California, Berkeley Final Exam
August 14, 2020
Name Student ID
Copyright By PowCoder代写 加微信 powcoder
This is an open-book exam. You may access existing materials, including online materials (such as the course website). During the exam, you may not communicate with other people regarding the exam questions or answers in any capacity. For example, posting to a forum asking for help is prohibited, as is sharing your exam questions or answers with other people (or soliciting this information from them).
You have 170 minutes to complete it. If there is something in a question that you believe is open to interpretation, please make a private post on Piazza asking for clarification. If you run into technical issues during the exam, join our open Zoom call and we will try to help you out. The final page is for reference.
We will overlook minor syntax errors in grading coding questions. You do not have to add the necessary #include statements at the top.
Grade Table (for instructor use only)
Question: 1 2 3 4 5 6 7 8 9 10 11 12 Total Points: 1 10 26 8 8 16 18 14 13 20 26 0 160 Score:
1. (1 point) Please check the boxes next to the following statements after you have read through and agreed with them.
√ I will complete this quiz with integrity, doing the work entirely on my own.
√ I will NOT attempt to obtain answers or partial answers from any other people.
√ I will NOT post questions about this quiz on online platforms such as StackOverflow. √ I will NOT discuss any information about this quiz until 24 hours after it is over.
√ I understand the consequences of violating UC Berkeley’s Code of Student Conduct.
Final Exam – Page 2 of 34 Student ID:
2. (10 points) Operating System Concepts
Choose either True or False for the questions below. You do not need to provide justifications.
Each student received 10 questions, chosen randomly from the ones below.
(a) (1 point) If a file system does not use a buffer cache (i.e., all writes go directly to the storage device), then it does not need recovery mechanisms (e.g., journaling).
⃝ True √ False
(b) (1 point) Reed- allow a message of size n to be split into m fragments of size approximately nk , such that any k of the fragments are enough to recover the original message (for m > k).
√ True ⃝ False
(c) (1 point) The Internet Protocol (IP) delivers packets from a process on one host to a process on another host.
⃝ True √ False
(d) (1 point) The Internet Protocol (IP) guarantees that packets sent from one host to another will not be reordered in the network.
⃝ True √ False
(e) (1 point) The Internet Protocol (IP) guarantees that packets sent from one host to another will not be duplicated.
⃝ True √ False
(f) (1 point) The Transmission Control Protocol (TCP) uses timeouts to detect if a packet is
√ True ⃝ False
(g) (1 point) In a Transmission Control Protocol (TCP) connection, a host can remove data from the send buffer as soon as it sends a packet containing that data to the receiving host.
⃝ True √ False
(h) (1 point) In a Transmission Control Protocol (TCP) connection, a host can remove data from the receive buffer as soon as it is transferred into a process’ address space via a read system call.
√ True ⃝ False
(i) (1 point) In a Transmission Control Protocol (TCP) connection, the amount of “in-flight” data from one host to another is influenced by the advertised window size of the receiving host.
Final Exam – Page 3 of 34 Student ID:
√ True ⃝ False
(j) (1 point) The purpose of congestion control is to prevent one host from sending data so fast as to overwhelm the receiving host.
⃝ True √ False
(k) (1 point) Two-Phase Commit (2PC) allows multiple nodes in a distributed system to per- form an action simultaneously.
⃝ True √ False
(l) (1 point) With quorum consensus, the master (directory) node of a directory-based key- value store with replication can acknowledge a client’s put request without first waiting for acknowledgments from all replicas.
√ True ⃝ False
(m) (1 point) In a linearizable key-value store, a get that is processed concurrently with a put to the same key may see the either the old value (i.e., the value before the put is processed) or the new value (i.e., the value after the put is processed).
√ True ⃝ False
(n) (1 point) The Chord key-value store relies on a master node that is aware of all of the storage nodes in the system.
⃝ True √ False
(o) (1 point) In a hardware virtualization setup, while a process belonging to the Guest OS is executing on the processor, the page table used for address translation is the one maintained by the Guest OS. (Assume that the processor does not supported nested paging.)
⃝ True √ False
Final Exam – Page 4 of 34 Student ID:
3. (26 points) Short Answer
Each student received 11 questions, taken from the ones below as follows: one of a
or b, c, one of d or e, one of f or g, one of h or i, j, k, one of l or m, n, o, and p.
(a) (2 points) What system call must an RPC server successfully issue, for the operating system to complete the TCP three-way handshake for incoming RPC requests?
Solution: listen
(b) (2 points) What does the client stub do in a Remote Procedure Call?
Solution: Marshal the data and send it to the server.
(c) (2 points) Suppose that transferring data from a hard-disk drive has an average startup cost of 10 ms (including controller time, seek time, and rotation time) and can transfer data read sequentially on disk at 50 MB/s. At what transfer size is the half-power bandwidth achieved? Show your work.
Solution: 50 MB/s · 0.01 s = 500 KB
(d) (2 points) The concept of caching arises in a variety of systems. Give two examples of
caching in software systems that we studied in class.
Solution: There are multiple correct answers. Two particularly prominent examples
are demand paging and buffer caching.
(e) (2 points) The concept of transparency arises in a variety of systems. Give two examples of transparency in software systems that we studied in class.
Solution: There are multiple correct answers. Two examples are demand paging (pro- cess doesn’t have to know if page is in memory or in storage) and VFS (process doesn’t have to know what kind of file system is in use, or whether it is local or remote).
Final Exam – Page 5 of 34 Student ID:
(f) (3 points) In a journaling file system based on (the logging scheme that we discussed in class), why is it important to wait until the corresponding Commit is written to the log before performing an operation?
Solution: If we begin performing the operation before writing Commit to the log, then it’s unclear when scanning the log for recovery whether (1) the operation was not fully logged (in which case it should be aborted) or (2) whether it has finished being logged and the operation is partially performed (in which case it should be completed).
(g) (3 points) What property of the individual log entries allows the journaling file system discussed in class to never have to undo any operations during recovery?
Solution: Each log entry describes an idempotent operation.
(h) (3 points) Consider a journaling file system based on (the logging scheme that we discussed in class). Suppose that the system restarts after a crash. Upon inspecting its log, it finds a transaction in the log, including the final Commit entry of the transaction. What should the system do to process this transaction?
Solution: The system should replay the transaction, following the entries in the log (in the same order relative to other completed transactions in the log).
(i) (3 points) Consider a journaling file system based on (the logging scheme that we discussed in class). Suppose that the system restarts after a crash. Upon inspecting its log, it finds a transaction in the log, but the final Commit entry of the transaction is not present in the log. What should the system do to process this transaction?
Solution: The system should discard the transaction (i.e., not perform it).
(j) (2 points) In Two-Phase Commit, why must the coordinator write its final decision (Commit or Abort) to its local log before sending it to the worker nodes?
Solution: If it crashes and come back up after sending Global-Commit messages to one or more nodes, it must make sure that all additional Global messages it sends for that transaction are Global-Commits, regardless of which worker nodes it reach at that time.
Final Exam – Page 6 of 34 Student ID:
(k) (2 points) A student in CS 162 writes the following x86 assembly code that runs in Pintos in a kernel thread in kernel mode:
movl %eax, (%ebx)
movl (%ebx), %ecx
To her surprise, the registers %eax and %ecx contain different values after this code exe- cutes. Assume that no thread writes to the stack of any other thread, and that the memory address stored in %ebx does not belong to any thread’s stack. Which of the following are possible reasons why this may have happened?
In between the two instructions, the kernel context-switched to a different thread, which modified the value stored in the register %ebx.
In between the two instructions, the kernel context-switched to a different thread, √ which read the value in memory at the address stored in %ebx.
In between the two instructions, the kernel context-switched to a different thread, √ which wrote to memory at the address stored in %ebx.
%ebx contains a memory address that maps to an I/O device instead of physical memory.
(l) (2 points) Suppose that a Guest OS is running on a Host OS using a traditional hardware virtualization setup. Explain how control is transferred from the Guest OS’ system call handler to the guest process (i.e., the process running on the Guest OS) once the Guest OS finishes handling a system call.
Solution: The Guest OS executes an iret instruction intending to switch from kernel mode to user mode. This is a privileged instruction, and the Guest OS runs in un- privileged mode, so it traps to the VMM in the kernel. The VMM emulates the iret instruction by switching into the process running on the Guest OS.
(m) (2 points) Suppose that a Guest OS is running on a Host OS using a traditional hardware virtualization setup. Explain how control is transferred from the guest process (i.e., the process running on the Guest OS) to the Guest OS system call handler when the guest process issues a system call.
Solution: The VMM has replaced the host interrupt vector with one that points to different handlers. When the system call trap comes in, control is transferred to a handler in the VMM, which dispatches to the system call handler in the Guest OS.
Choose the best answer for each of the questions below, and explain your answer in the box provided.
(n) (2 points) Consider two periodic tasks, S and T. Each task consists of a series of CPU bursts; each task yields to the scheduler between CPU bursts but (for simplicity) has zero I/O time between CPU bursts. This is exactly the setup from Problem 3 on the Scheduling Lab. Is this an open system or a closed system? Explain.
Open system √ Closed system
Final Exam – Page 7 of 34 Student ID:
Solution: A task cannot make its next CPU burst until its previous one has been processed.
(o) (3 points) If a user writes to a file in the Network File System (NFS) and then closes it, then the user’s modifications are guaranteed to be visible to any user who reads the file immediately after the original user closed it. True or false? Explain.
True √ False
Solution: The NFS client polls the server, so if the user reads the file after another
user writes it but before her client polls the server, she will see stale data.
(p) (3 points) If a user writes to a file in the System (AFS) and then closes it, then the user’s modifications are guaranteed to be visible to any user who reads the file immediately after the original user closed it. True or false? Explain.
True √ False
Solution: Another user that already opened the file before the original user closed it will not see the new contents unless she closes the file and reopens it.
Final Exam – Page 8 of 34 Student ID:
4. (8 points) Operating System Abstractions
Each student received 4 questions out of the ones below, selected randomly. For
each question below, select all of the choices that apply. You should assume:
• Calls to open, fopen, fork, pthread_create, malloc, and realloc always succeed.
• Calls to read, write, dup, and dup2 succeed if a valid file descriptor is provided.
• The necessary header files from the C standard library are #included.
• Before each program is run, file.txt is an empty file.
• All threads eventually make progress. Make no other assumptions about the scheduler.
(a) (2 points) Which of the following could be the contents of file.txt after all processes of the program below terminate?
int main(int argc, char** argv) {
int fd = open(“file.txt”, O_WRONLY);
if (fork() == 0) {
write(fd, “a”, 1);
write(fd, “b”, 1);
} (empty) a b baa abb bab bbaa
the program below terminate?
int main(int argc, char** argv) {
int fd = open(“file.txt”, O_WRONLY);
if (fork() == 0) {
write(fd, “a”, 1);
write(fd, “b”, 1);
(empty) a b baa √ abb √ bab bbaa
aa bba
aab baab
aba baba
aa bba
aabb abab
aab baab
aba baba
aabb abab
(b) (2 points) Which of the following could be the contents of file.txt after all processes of
(c) (2 points) Which of the following could be the contents of file.txt after all processes of the program below terminate?
int main(int argc, char** argv) {
int fd = open(“file.txt”, O_WRONLY);
if (fork() == 0) {
write(fd, “a”, 1);
close(fd);
write(fd, “b”, 1);
close(fd);
Final Exam – Page 9 of 34
Student ID:
} (empty) a
baa abb bbaa
aa √ ab √ ba bb aab aba bba aabb abab baab baba
(d) (2 points) Which of the following could be the contents of file.txt after all processes of the program below terminate?
int main(int argc, char** argv) {
int fd = open(“file.txt”, O_WRONLY);
if (fork() == 0) {
dup2(fd, fd + 1);
write(fd + 1, “a”, 1);
write(fd + 1, “b”, 1);
} (empty) a b aa
baa abb bab bba bbaa
aabb abab
aab baab
aba baba
(e) (2 points) Which of the following could be the contents of file.txt after the program below terminates?
void* helper(void* arg) {
write(fd, “a”, 1);
int main(int argc, char** argv) {
fd = open(“file.txt”, O_WRONLY);
pthread_t thread;
pthread_create(&thread, NULL, helper, NULL);
pthread_join(thread, NULL);
write(fd, “b”, 1);
}(empty) a b aa √ab ba bb
(f) (2 points) Which of the following could be the contents of file.txt after the program below terminates?
void* helper(void* arg) {
write(fd, “b”, 1);
int main(int argc, char** argv) {
fd = open(“file.txt”, O_WRONLY);
write(fd, “a”, 1);
pthread_t thread;
pthread_create(&thread, NULL, helper, NULL);
}(empty) √a b aa √ab ba bb
Final Exam – Page 10 of 34 Student ID:
(g) (2 points) Which of the following could be the contents of file.txt after the program below terminates?
void* helper(void* arg) {
write(fd, “a”, 1);
int main(int argc, char** argv) {
fd = open(“file.txt”, O_WRONLY);
pthread_t thread;
pthread_create(&thread, NULL, helper, NULL);
write(fd, “b”, 1);
pthread_join(thread, NULL);
}(empty) a b aa √ab √ba bb
Final Exam – Page 11 of 34 Student ID:
5. (8 points) Pintos
Choose either True or False for the questions below. You do not need to provide justifications.
Each student received 5 questions, chosen randomly from the ones below.
(a) (1 point) In Pintos, a user program may obtain a pointer to the TCB by calling thread_current and then access its fields directly.
⃝ True √ False
(b) (1 point) In Pintos, interrupt handlers execute in their own stack, separate from the stack of any kernel thread.
⃝ True √ False
(c) (1 point) It is inherently unsafe to call sema_up on a semaphore in external interrupt context.
⃝ True √ False
(d) (1 point) The idle thread puts the processor to sleep with interrupts disabled. ⃝ True
(e) (1 point) Once a file is created, its length can never decrease unless it is removed and created again. (Assume that Project 3 is implemented.)
√ True ⃝ False
(f) (1 point) The kernel image (containing kernel code, globals, etc.) exists as a file in the Pintos file system.
⃝ True √ False
(g) (1 point) Pintos is a microkernel. ⃝ True
(h) (1 point) In the default Pintos file system (before Project 3), free disk blocks are allocated using a free list (i.e., an on-disk linked list).
⃝ True √ False
Fill in the blanks correctly for the questions below. You do not need to provide justifications. Each student received one of Part i and j. Every student received Part k.
(i) (1 point) What is the purpose of the “magic” field in struct thread in Pintos? Solution: Its purpose is to detect stack overflow.
Final Exam – Page 12 of 34 Student ID:
(j) (1 point) Why is it important for sizeof(struct thread) to not grow too large in Pintos?
Solution: Each struct thread is allocated on the same page as the thread’s kernel stack, so if struct thread grows too large, there may no longer be enough space left in the page for the thread’s kernel stack.
(k) (2 points) Suppose the scheduling timer expires while interrupts are disabled. When will the timer_interrupt function (i.e., the external interrupt handler) be invoked next?
Solution: It is invoked as soon as interrupts are re-enabled.
Final Exam – Page 13 of 34 Student ID:
6. (16 points) Priority Donation
Priority donation in Pintos can be formalized as a directed graph. Each thread in the system corresponds to a vertex in the graph. An edge from t1 to t2, denoted (t1, t2), exists in the graph if t1 is blocked on acquiring a mutex that t2 holds. Together with each thread t’s base priority, t.priority, the graph provides sufficient information to compute each thread’s effective priority.
(a) (1 point) What is the maximum number of outgoing edges from any particular vertex in the graph? Explain your answer.
Solution: 1 (one), because a thread can only be blocked on one mutex at a time.
(b) (1 point) It is safe to assume that the above graph has no cycles, because a cycle would indicate a particular type of scheduling bug in the kernel. What type of bug would a cycle indicate? (Hint: We spent a full lecture in class studying this type of bug.)
Solution: Deadlock
(c) (3 points) For any thread t (a vertex in the graph), let ep(t) denote the effective priority of t. Explain how to calculate ep(t). It is acceptable to write your answer as a formula or explain it in words; we do not expect you to write out pseudocode. Hint: Because the graph has no cycles, feel free to use a recursive definition, where ep(t) is defined using the effective priorities of t’s ancestors.
Solution: t’s effective priority is the maximum of t’s base priority, and the effective priorities of t’s immediate ancestors. Written out formally,
ep(t) = max ({t.priority} ∪ {ep(u) | (u, t) ∈ E})
where (u, t) denotes a directed edge from u to t and E is the set of edges in the graph.
(d) (2 points) Suppose that a particular thread changes its priority by calling thread_set_priority. Could other threads’ effective priorities immediately change as a result of this call? Ex- plain.
Solution: No; if the current thread calls thread_set_priority, then it must be run- ning (not blocked), so we know that it has no outgoing edges (i.e., it’s not donating to any other thread).
Suppose that we implement a new synchronization primitive
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com