CS 162 Operating Systems and Systems Programming Summer 2021 Final Exam
INSTRUCTIONS
This is your exam. Complete it either at exam.cs61a.org or, if that doesn’t work, by emailing course staff with your solutions before the exam deadline.
This exam is intended for the student with email address
Copyright By PowCoder代写 加微信 powcoder
For questions with circular bubbles, you should select exactly one choice. You must choose either this option
Or this one, but not both!
For questions with square checkboxes, you may select multiple choices. You could select this choice.
You could select this one too!
You may start your exam now. Your exam is due at
Exam generated for
This is a proctored, closed-book exam. During the exam, you may not communicate with other people regarding the exam questions or answers in any capacity. If there is something in a question that you believe is open to interpretation, please use the “Clarifications” button to request a clarification. We will issue an announcement if we believe your question merits one.
Make sure you read through the exam completely before starting to work on the exam.
We will overlook minor syntax errors in grading coding questions. You do not have to add necessary #include statements.
(b) Student ID
(c) Please read the following honor code: “I understand that this is a closed book exam. I hereby promise that the answers that I give on the following exam are exclusively my own. I understand that I am allowed to use unlimited handwritten cheat-sheets of my own making, but otherwise promise not to consult other people, physical resources (e.g. textbooks), or internet sources in constructing my answers.” Type your full name below to acknowledge that you’ve read and agreed to this statement.
Exam generated for
Please EXPLAIN your answer in TWO SENTENCES OR LESS (Answers longer than this may not get credit!). Answers without any explanation GET NO CREDIT.
(a) (3 points)
i. In the Nth chance algorithm (assume N=10), if a page is evicted, this means that the page has not
been accessed in the past 10 memory accesses. True
ii. Explain your answer.
False. If a page is evicted, this means that it has not been accessed after 10 full sweeps of the clock hand.
Exam generated for
i. In an RPC system with multiple servers, dynamic binding is generally more fault tolerant than static binding.
True False
ii. Explain your answer.
True. With dynamic binding, if there is a failure in one server, the RPC client can select a different server at runtime. With static binding, since the endpoint is determined at compile time, this is not possible.
Exam generated for
(c) (3 points)
i. If the following functions are run concurrently, deadlock may occur.
int val1 = 0;
int val2 = 0;
void functionA() {
while(test&set(&val2));
printf(“Done!\n”);
void functionB() {
while(!compare&swap(&val1, 0, 1));
printf(“Done!\n”);
True False
ii. Explain your answer.
True. In this problem, the first two lines of each function implement lock acquisi- tion, while the second two lines of each function implement lock release.However, if both threads acquire different locks by running val1 = 1 and val2 = 1, then there will be a circular wait, hold & wait, and mutual exclusion when each thread tries to acquire the lock it doesn’t hold.
Exam generated for
i. If a system is using Round Robin scheduling and there are T threads running, each thread will have to wait exactly [(T – 1) x Q] ticks in between bursts of computation (assume that context switching is instantaneous).
True False
ii. Explain your answer.
False. Each thread will only wait exactly [(T – 1) x Q] ticks if none of the threads voluntarily yield the CPU or block before their quanta expires. Without this assumption, a thread may wait less than [(T – 1) x Q] ticks before running again.
Exam generated for
i. When a file is opened using fopen, a pointer to a FILE object is returned. A copy of this object is stored in kernel space.
True False
ii. Explain your answer.
False. fopen is a library function that runs in userspace. As a result, the FILE object is only allocated in userspace.
Exam generated for
i. is sending a packet from his computer to Mario’s computer. However, the TCP header of the packet becomes corrupted before the packet is sent out. The packet might still reach the destination machine.
True False
ii. Explain your answer.
True. The IP network layer/packet header is responsible for routing a packet to a destination IP address. Even though the IP layer is responsible for best-effort delivery, which means that the packet may not reach its destination or it may be corrupted, there is still a good chance that the packet will be delivered to the destination machine.
Exam generated for
(g) (3 points)
i. In the TCP protocol, if a packet is unacked, it has not reached its destination.
True False
ii. Explain your answer.
False. An unacked packet may have reached its destination, and the ACK message from the receiver may have been lost/corrupted.
Exam generated for
i. uses a Hard Disk Drive with multiple platters. Unfortunately, the arm on the HDD is broken and can no longer move. Now, will not be able to read from/write to more than a single sector on his disk.
True False
ii. Explain your answer.
False. Because ’s HDD has multiple platters, the HDD arm will be able to read from/write to one sector on each platter.
Exam generated for
i. Assume that Thread A and Thread B are in the same process. If Thread A tries to access memory address 0xABCD and this triggers a page fault, then it is guaranteed that Thread B will also page fault if it attempts to access the same memory address immediately after.
True False
ii. Explain your answer.
False. Only one counterexample is necessary. Counterexample 1: Address 0xABCD may be read-only. If Thread A attempted to write to the address, while Thread B read from it, this could cause the behavior described in the prob- lem. Counterexample 2: Thread A could have page faulted because the page was paged out to disk. Once the page was read into memory, Thread B would not page fault on the same access.
Exam generated for
(j) (3 points)
i. In the context of storage devices and filesystems, blocks and sectors are not synonymous.
True False
ii. Explain your answer.
True. Sectors are a physical location on a storage device. Blocks are a group of sectors that the OS can address.
Exam generated for
In the following multiple choice questions, please select all options that apply. Answering a question instead of leaving it blank will NOT lower your score (the minimum score for a single question is 0, not negative).
(a) (3 pt) Device drivers: (select all that apply) run in kernel mode
must poll the device hardware to determine if I/O has completed can only interface with block devices, such as Hard Disk Drives are part of an I/O device’s hardware
None of the above
(b) (3 pt) has created a new scheduling algorithm LJF, a non-preemptive algorithm that always schedules the longest available job and runs it to completion. Assuming that all jobs arrive at the same time and never block, which of the following scheduling algorithms are guaranteed to have the same throughput as LJF? Select all that apply. Hint: do not assume that context switching is instantaneous.
Round Robin
None of the above
Exam generated for
void *echo_1(void *arg) {
char *cmd = “echo”;
char *argv[3];
argv[0] = cmd;
argv[1] = “CS”;
argv[2] = NULL;
execvp(cmd, argv);
return NULL;
void *echo_2(void *arg) {
char *cmd = “echo”;
char *argv[3];
argv[0] = cmd;
argv[1] = “162”;
argv[2] = NULL;
execvp(cmd, argv);
return NULL;
int main() {
pthread_t thread1, thread2;
pthread_create(&thread1, NULL, echo_1, NULL);
pthread_create(&thread2, NULL, echo_2, NULL);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
None of the above
Exam generated for
their associated IDs are displayed below.
A client wants to lookup a key that hashes to 3, but it is only aware of node 32. Which nodes will receive a lookup request? Select all that apply.
None of the above
Assume that our system is using a journaling file system, and the current state of the log is as follows:
(e)
i. (2 pt) Which of the operations are guaranteed to have been applied already?
ii. (2 pt) Which of the operations are guaranteed to eventually be applied?
Exam generated for
(a) (4 pt) In 2PC, when a Worker has voted COMMIT but the Coordinator crashes before sending a GLOBAL- COMMIT/ABORT message, why can’t the Worker abort without running a termination protocol?
The goal of 2PC is to ensure that all Workers eventually make the same decision when deciding whether or not to perform an action requested by the Coordinator. If Worker A votes COMMIT and is waiting for a message from the Coordinator, there is a chance that all the other Workers also voted COMMIT, and the Coor- dinator logged a GLOBAL-COMMIT. If this is the case, Worker A must commit and perform the requested action to remain consistent with all other Workers, so it cannot prematurely abort.
(b) wants to throw a party, but he’ll only host the party if a majority of his friends commit to attending. He decides to use a modified version of 2PC to decide what to do. In this version of 2PC, he (the Coordinator) will send a VOTE-REQ message to his N friends (the Workers). If at least N/2 friends send a VOTE-COMMIT message back, will host the party and send a GLOBAL-COMMIT message to everyone. Otherwise, he will send a GLOBAL-ABORT message and cancel the party. Everything else about the 2PC algorithm remains the same.
i. (4 pt) Recall the termination protocol from lecture, in which a Worker node A is waiting for a GLOBAL-COMMIT/ABORT message from the Coordinator. In this protocol, the Worker contacts a friendly Worker P, and does the following:
• Case 1: If P has decided COMMIT/ABORT, A makes the same decision.
• Case 2: If P has not decided, P votes to ABORT and tells A to abort.
• Case 3: If P has voted COMMIT, P also needs to wait and can’t help A make a decision.
Explain why this termination protocol might fail given ’s modified 2PC scheme.
ii. (5 pt) Describe why ’s modified 2PC may be slower than regular 2PC in certain cases.
Case 2 will fail in ’s modified scheme. This part of the termination protocol assumes that a single ABORT vote will cause the Coordinator to send a GLOBAL-ABORT, which is true in the original 2PC scheme. However, in the modified scheme, even with a single ABORT vote, a majority of Workers can still vote to COMMIT, causing the Coordinator to send a GLOBAL-COMMIT. As a result, Worker P’s vote alone cannot determine the outcome of the system.
In the regular 2PC, the GLOBAL-ABORT state can be reached quicker. This is because the Coordinator would only need to wait for a single Worker to vote ABORT. On the other hand, in modified 2PC, the Coordinator would need to receive at least N/2 ABORT votes.
Exam generated for
bought a faulty machine! According to the vendor, the machine uses a single-level paging scheme for address translation and the Clock Algorithm for page eviction. The vendor promised that the processor had hardware-supported “use” and “modified” bits. However, after doing some testing, has discovered that the “use” bit is only set during read accesses, not during write accesses. In addition, the “modified” bit is never set by the MMU during a write access.
has asked for your help in implementing a version of the Clock Algorithm that will function correctly on this faulty hardware. For this problem, you can assume that all pages are writable (i.e. not read-only).
Your solution should be the fastest possible implementation of the Clock Algorithm, given these constraints. (a) (2 pt) Each Page Table Entry (PTE) consists of the following fields:
Page Number
(PPN) [23 Valid [1 Writable [1 Modified [1 OS Metadata [5 bits] bit] bit] Use [1 bit] bit] bits]
Currently, when a page is first loaded into memory, the page’s PTE is initialized with Valid=1, Use=0, Modified=0, and Writable=1. What change(s) do you need to make to these initial values to implement a functioning version of the Clock Algorithm on ’s faulty hardware?
(b) (7 points)
The data structure below is a C representation of the PTE described earlier. The numbers associated with each struct member (e.g. uint32 ppn : **23**) represent how many bits are used to store each value in memory, and are based on the table above.
typedef struct pte {
uint32 ppn : 23;
bool present : 1;
bool writable : 1;
bool use : 1;
bool modified : 1;
uint32 os : 5; // You will not need to use these bits in your solution.
Every time a page fault occurs, the function handle_page_fault, shown below, is invoked. Every time a page needs to be evicted, the function run_clock_algo, shown below, is invoked to perform the Clock Algorithm. Note that handle_page_fault calls handle_page_not_present, which in turn calls run_clock_algo if eviction is necessary.
/* This function is only invoked if a page is not present in memory. In
addition to normal page fault logic (e.g. running the clock algorithm using
`run_clock_algo`), this function will initialize the PTE as you specified in
Part 1 for any new pages loaded into memory. */
void handle_page_not_present(pte_t *pte);
/* This function takes in a single argument `pte`, which is a pointer to the PTE
of the page that caused the page fault. Any changes made to `pte` will modify
the actual page table entry. */
void handle_page_fault(pte_t *pte) {
Set Writable=0.
Exam generated for
/* Runs the clock algorithm, and returns the VPN (i.e. the array index) of the
page that should be evicted. `pte_arr` is a pointer to the page table
(represented as an array of PTEs). `num_pages` is the number of entries in the
page table. `clock_hand` is a value from 0 to `num_pages`.*/
size_t run_clock_algo(pte_t *pte_arr, size_t num_pages, size_t *clock_hand) {
while (ptr_arr[*clock_hand].use) {
pte_arr[clock_hand].use = 0;
*clock_hand = (*clock_hand + 1) % num_pages;
size_t old_clock_hand = *clock_hand;
*clock_hand = (*clock_hand + 1) % num_page;
return old_clock_hand;
Your task is to modify the handle_page_fault and run_clock_algo functions. You will add any logic that is necessary for the Clock Algorithm to function correctly on ’s faulty hardware. In addition, you need to make sure that the faulty modified bit is set manually when a page becomes dirty. To this end, there is an additional boolean write_access passed into handle_page_fault, specifying whether the memory access that triggered the page fault was a write operation or not. You can assume that whatever change(s) you specified in Part 1 have already been made (see handle_page_not_present).
For each blank, you may use as many lines as you need.
void handle_page_fault(pte_t *pte, bool write_access) {
________[A]________
handle_page_not_present(pte);
size_t run_clock_algo(pte_t *pte_arr, size_t num_pages, size_t *clock_hand) {
while (ptr_arr[*clock_hand].use) {
________[B]________
pte_arr[clock_hand].use = 0;
*clock_hand = (*clock_hand + 1) % num_pages;
size_t old_clock_hand = *clock_hand;
*clock_hand = (*clock_hand + 1) % num_page;
return old_clock_hand;
if (pte->present) {
if (write_access) pte->modified = 1;
pte->writable = 1;
pte->use = 1;
Exam generated for
pte_arr[clock_hand].writable = 0;
Exam generated for
(c) (4 pt) For this question, we assumed that all pages will be writable. Why would you need to employ a slower solution if some pages were read-only?
If some pages were read-only, this information would be encoded in the Writable bit of the PTE. One solution would be to store the read-only status of a page in the OS and page fault on every memory access to determine if a page is read-only. Another solution is to page fault on every memory access when the use bit is 0 (by setting the present bit equal to the use bit) to check if a memory access is a write operation and update the use bit if necessary. Either solution is slower.
Exam generated for
is experimenting with a new type of TLB designed specifically for multi-level page tables. Recall that multi-level page tables break up virtual addresses into three components instead of two:
Virtual P1 Index Virtual P2 Index Offset
where the Virtual P1 Index and Virtual P2 Index make up the Virtual Page Number.
However, instead of mapping Virtual Page Numbers to Physical Page Numbers, ’s TLB will map a Virtual P1 Index to the corresponding second-level page table. In other words, ’s TLB only caches the first level of address translation in a multi-level paging scheme.
For this problem, you will assume that ’s machine uses a two-level paging scheme. Each page is 1KiB, physical memory is 1 GiB large, and each process has a 32-bit virtual address space. You should also assume that each page table fits exactly within a single page.
(a) (3 pt) If ’s TLB is fully associative and contains 32 blocks, how large is the TLB in bits? Assume that each cache line of the TLB only contains the cache tag, the cache data, and a valid bit (no other metadata is necessary).
(b) (5 pt) Given the two-level paging scheme described earlier, explain what kinds of memory access patterns would cause ’s TLB to perform better than a traditional TLB.
1 KiB page -> 10 bit offset 32 bit virtual address – 10 bit offset = 22 bit VPN VPN / 2 = Virtual P1/P2 Index; 22 bits /
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com