CS 162 Operating Systems and System Programming
Fall 2020 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.
Copyright By PowCoder代写 加微信 powcoder
This exam is intended for the student with email address
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. 2 You could select this choice.
2 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. We will overlook minor syntax errors in grading coding questions. You do not have to add necessary #include statements. For coding questions, the number of blank lines you see is a suggested guideline, but is not a strict minimum or maximum. There will be no limit on the length of your answer/solution.
Student ID
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 three 8.5×11, double-sided, handwritten cheat-sheet 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!). Also, answers without any explanation GET NO CREDIT!
# True False
It’s important in 2PC for workers to reply to the coordinator before logging the coordinator’s message, for otherwise an untimely crash can cause the message to never be sent to the coordinator, blocking the entire system.
Must log before responding, otherwise may be unable to recover a situation like the following: (1) send response, (2) crash before logging, (3) response packet is dropped.
Exam generated for
In 2PC, when the coordinator receives a request, the first thing it does is send a PREPARE message to workers.
# True False
The first thing it does is log the request.
Exam generated for
In 2PC, after the coordinator sends a request to workers, if it has not received a reply after some time, it will try to resend the request.
# True False
It will GLOABL-ABORT.
Exam generated for
AFS implements callbacks so that a write to a file from Node A instantly propagates to Node B, without Node B having to poll to update its cache.
# True False
Almost true, AFS does implement callbacks, but it has write through on close semantics, so all openers of a file are only updated of changes when they reopen.
Exam generated for
The Berkeley FFS discussed in class does not include the file name in the inode. True
File names are included in the directory entry instead.
Exam generated for
The Berkeley FFS discussed in class includes the file name in the inode. # True
File names are included in the directory entry instead.
Exam generated for
In the Berkeley FFS, each file descriptor uniquely corresponds to its own inode. # True
Different file descriptors may correspond to the same inode. (In the Unix system, file descriptors correspond to an entry in the global file table which contains info like permissions; that entry then identifies the inode.)
Exam generated for
The FAT file system can suffer from external fragmentation if we delete a lot of small files. # True
We can still use those unallocated blocks for large files.
Exam generated for
Soft links could lead to dangling references if a file is removed. True
Soft links do not include a reference count, so this is true.
Exam generated for
For a distributed hash table, as compared to recursive queries, iterative queries are more scalable (since clients do more work) and often faster (since the directory server is typically closer to storage
nodes). However, it’s often harder to enforce consistency for iterative queries. # True
False, the second reason (speed) is a con of iterative queries and a pro of recursive queries.
Exam generated for
Consider System A that has one queue serviced at a rate of N jobs per second, and System B that has N queues, each of which is serviced at the rate of one job per second. True or False: System A will have lower queueing delays on average than System B.
True # False
One server that can process N jobs per second is faster. It has better utilization (no load balancing problems), which gives lower queuing delays on average.
Exam generated for
Consider System A that has one queue serviced at a rate of N jobs per second, and System B that has N queues, each of which is serviced at the rate of one job per second. True or False: System A will have higher queueing delays on average than System B.
# True False
One server that can process N jobs per second is faster. It has better utilization (no load balancing problems), which gives lower queuing delays on average.
Exam generated for
As utilization approaches 100%, response time goes to infinity for any deterministic arrival process. # True
Given a deterministic arrival process and service time, it is possible to sustain a utilization of u = 1 with a bounded response time.
Consider the trivial scenario of: 1 job arrives every 5 seconds, and it takes exactly 5 seconds to service that job. Utilization is 1, but response time is boudned by 5 seconds.
Exam generated for
As utilization approaches 100%, the response time of a real system will approach infinity. # True
As utilization approaches 100%, the finite queues will fill up, causing requests to be dropped rather than delayed indefinitely.
Exam generated for
Since there is a disk head for every surface of every platter, it is possible to operate on each platter independently.
# True False
All of the disk heads are ridgedly tied together in a single head assembly that moves in and out as a unit.
Exam generated for
The disk head assembly must move for each sector that is read from the disk. # True
Since the disk platters are spinning, the head can stay stationary while a whole cylinder-worth of sectors are read.
Exam generated for
When devices use DMA, they typically work in terms of physical addresses. True
The DMA controller is not associated with any particular processes, and thus does not need to translate virtual addresses. Instead, it is given direct access to the memory bus, so that it can copy data (using physical addresses) without tying up the CPU.
Exam generated for
When devices use DMA, they typically work in terms of virtual addresses. # True
The DMA controller is not associated with any particular processes, and thus does not need to translate virtual addresses. Instead, it is given direct access to the memory bus, so that it can copy data (using physical addresses) without tying up the CPU.
Exam generated for
On a low-bandwidth network interface, it makes sense to poll for the first packet and use interrupts on subsequent packets
# True False
On a low-bandwidth network, polling will waste many CPU cycles, and we should use interrupts for all packets. Remember: interrupts are useful for low-frequency events (as we have here) and polling is good for high-frequency events.
Note: it’s not valid to say that we should use interrupts for the first packet and polling for the rest, because the arrival of the first packet doesn’t imply that more packets will arrive soon on a low-bandwidth network.
Exam generated for
On a high-bandwidth network interface, it makes sense to poll for the first packet and use interrupts on subsequent packets
# True False
On a high-bandwidth network, interrupts will have too high an overhead. We should use polling for all packets. Remember: interrupts are useful for low- frequency events (as we have here) and polling is good for high-frequency events. Note: we can alterntaively use a hybrid approach where interrupts are used for the first packet (to get started) and polling is used for all subsequent packets.
Exam generated for
Programmed IO requires special load and store instructions in the ISA that do not use the data cache so that updates are made directly to main memory and thus the device.
# True False
When using programmed IO, we want to ensure that our loads/stores are not cached in the data cache. If they were, then they would not make immediate changes to RAM, which are required to effect changes on the device. However, we don’t need special load/store instructions in order to avoid caching the data; most modern implementations have a bit in the page-table entry that tells the MMU not to cache the data.
Exam generated for
On modern SSDs, large contiguous reads are much faster than large random reads # True
SSDs don’t have moving parts so sequential reads/writes take the amount of time as random reads/writes
Exam generated for
On modern SSDs, large contiguous writes are much faster than large random writes # True
SSDs don’t have moving parts so sequential reads/writes take the amount of time as random reads/writes
Exam generated for
Modern operating systems must include an elevator scheduling algorithm within a device driver in order to get the benefits of track-local request scheduling.
# True False
Modern disk controllers can handle multiple requests at the same time and in- corporate optimizations such as elevator scheduling inside the controller.
Exam generated for
It is possible to design a disk storage system that can recover from more than two simultaneously failing disks without losing information.
True # False
Using an erasure code such as Reed-Solomon coding allows one to add any number of parity disks to a system, over and above the two that are tolerated with RAID 6.
Exam generated for
It is impossible to design a disk storage system that can recover from more than two simultaneously failing disks without losing information.
# True False
Using an erasure code such as Reed-Solomon coding allows one to add any number of parity disks to a system, over and above the two that are tolerated with RAID 6.
Exam generated for
It is possible for some SSD manufacturers to guarantee that their devices will not fail for some amount of time (say 5 years), even if a user writes continuously to the device.
True # False
Given the presence of wear-leveling functionality, some SSD devices are so large that a user would be unable to write enough data over 5 years to wear out any particular FLASH bit. (Note: this is not the same as being unable to write enough data to fill the SSD).
Exam generated for
Suppose Host A is trying to transfer a 1000 byte file over a TCP connection to Host B and the Initial Sequence Numbers (ISNs) in both directions are 0. Suppose 5 packets, each of size 200 bytes, are sent over the connection from Host A to Host B. If Host B sends back a packet with the ACK field set to 600, then only the first three packets have made it through to Host B.
# True False
TCP uses cumulative ACKs, where each ACK says it’s received all bytes up to the sequence number X – 1. Packet #5 could have been received even thought #4 has not.
Exam generated for
Suppose Host A is trying to transfer a 1000 byte file over a TCP connection to Host B and the Initial Sequence Numbers (ISNs) in both directions are 0. Suppose 5 packets, each of size 200 bytes, are sent over the connection from Host A to Host B. If Host B sends back a packet with the ACK field set to 400, then only the first two packets have made it through to Host B.
# True False
TCP uses cumulative ACKs, where each ACK says it’s received all bytes up to the sequence number X – 1. Packet #4 or #5 could have been received even thought #3 has not.
Exam generated for
TCP and UDP are both reliable transport-level protocols, but UDP is faster because we don’t care about the order of the packets.
# True False
UDP is not reliable.
Exam generated for
Because UDP provides unreliable, best-effort delivery, using UDP is no different than using native IP. # True
UDP is on the transport layer and allows us to connect processes to other pro- cesses, whereas IP does not give that functionality.
Exam generated for
The journal log may be located on a different disk than the contents of the filesystem it backs. True
There is no requirement for the journal to be on the same disk as the file system it backs. The journal must simply be append-only, non-volatile memory. Journaling file systems often use a faster, smaller disk (e.g. an SSD) for log writes. Common Mistake: the intent of journaling file systems is not to recover from a disk crash, but instead to recover from a system crash (e.g. the CPU).
Exam generated for
The journal log must be located on the same disk as the contents of the filesystem it backs. # True
There is no requirement for the journal to be on the same disk as the file system it backs. The journal must simply be append-only, non-volatile memory. Journaling file systems often use a faster, smaller disk (e.g. an SSD) for log writes. Common Mistake: the intent of journaling file systems is not to recover from a disk crash, but instead to recover from a system crash (e.g. the CPU).
Exam generated for
Because of the changes that are made to the buffer cache in Pintos Project 3, writes to a file are transactional. That is, if Thread A and Thread B attempt to write to a file at the same time, Thread C reading from the file after both writes complete should see either the contents of Thread A’s write followed by the contents of Thread B’s write OR the contents of Thread B’s write followed by the content of Thread A’s write. In particular, C cannot see a mix of writes from Thread A and Thread B.
# True False
This is true at a per-block level in the project, but nothing in the spec/design guarantees this sort of isolation for multi-block writes.
Exam generated for
2. (16.0 points) Multiple Choice a) (2.0 pt)
Which of the following are true about Two-Phase Commit?
TPC makes sure that all nodes either commit or abort despite possibility of nodes crashing.
2 TPC can still function correctly if it does not have a logging mechanism.
2 TPC is a distributed consensus algorithm that allows for progress despite the presence of malicious nodes (i.e TPC can solve the Byzantine Generals Problem).
2 Two-Phase Commit that can make progress despite indefinitely crashed or blocked nodes.
A logging mechanism is fundamental for TPC because that is how the process will come to a unanimous decision despite failures. TPC can handle failures, but it cannot handle nodes that are actively trying to compromise the decision making process (malicious nodes). Two-Phase Commit cannot continue to make progress in the presence of crashed and/or blocked nodes.
b) (2.0 pt)
Which of the following are false about Two-Phase Commit?
2 TPC makes sure that all nodes either commit or abort despite possibility of nodes crashing.
TPC can still function correctly if it does not have a logging mechanism.
TPC is a distributed consensus algorithm that allows for progress despite the presence of malicious nodes (i.e TPC can solve the Byzantine Generals Problem).
Two-Phase Commit that can make progress despite indefinitely crashed or blocked nodes.
A logging mechanism is fundamental for TPC because that is how the process will come to a unanimous decision despite failures. TPC can handle failures, but it cannot handle nodes that are actively trying to compromise the decision making process (malicious nodes). Two-Phase Commit cannot continue to make progress in the presence of crashed and/or blocked nodes.
c) (2.0 pt)
For Two-Phase Commit, given that all follower nodes will vote to COMMIT and all crashed nodes will eventually recover, in which cases could there be a GLOBAL-COMMIT?
After receiving a COMMIT vote from each follower, the coordinator sends a GLOBAL-COMMIT, and crashes.
The coordinator sends a VOTE-REQ to all followers. All (N – 1) followers log a VOTE-REQ. (N – 1) followers vote to commit, but 1 follower crashes before sending a COMMIT.
The coordinator crashes before sending a VOTE-REQ to all followers.
2 The coordinator crashes right after sending a VOTE-REQ to all followers. 2 All of the above.
Option 1: In recovery mode, the coordinator looks into the log and sees that it sent out a GLOBAL- COMMIT. It sends out another GLOBAL-COMMIT to all of its followers, and this can keep occurring until the coordinator receives all N ACKS. Option 2: Suppose the coordinator allotts X seconds for the followers to send a COMMIT or ABORT in response to their VOTE-REQ. If a follower crashes but recovers and sends a response within X seconds, it will be as if the follower didn’t crash. Option 3: On reboot, because the log doesn’t have a VOTE-REQ, the coordinator will resend a VOTE-REQ to all followers. Option 4: Because the coordinator hasn’t logged a global action after a VOTE-REQ, on reboot, the coordinator will send out a GLOBAL-ABORT.
Exam generated for
For Two-Phase Commit, given that all follower nodes will vote to COMMIT and all crashed nodes will eventually recover, in which cases is a GLOBAL-COMMIT guaranteed?
After receiving a COMMIT vote from each follower, the coordinator sends a GLOBAL-COMMIT, and crashes.
2 The coordinator sends a VOTE-REQ to all followers. All (N – 1) followers log a VOTE-REQ. (N – 1) followers vote to commit, but 1 follower crashes before sending a COMMIT.
2 The coordinator crashes before sending a VOTE-REQ to all followers.
2 The coordinator crashes right after sending a VOTE-REQ to all followers. 2 All of the above.
Option 1: In recovery mode, the coordinator looks into the log and sees that it sent out a GLOBAL- COMMIT. It sends out another GLOBAL-COMMIT to all of its followers, and this
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com