CS 162 Operating Systems and Systems Programming
Fall 2021 Midterm 3
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. 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
(a) Full name
(b) Student ID number
(c) Autograder login (e.g. student123)
Exam generated for
Please pick whether each statement is true or false and explain why. Explanations must be two sentences or less. You may not use semicolons to circumvent this limit. Any answer longer than two sentences will receive a 0.
(a) (3.0 points)
i. The structure of directories and files in FFS will always form a tree.
True False
ii. Explain.
While not the intention of the question, a soft link or interpreting . and .. as part of the structure would introduce cycles into the structure, not making it a tree regardless.
FFS supports hard links, which allow a file to have multiple parents, so the structure forms a directed acyclic graph (DAG) but not a tree.
Exam generated for
(b) (3.0 points)
i. A free space bitmap always uses less space than a free block list.
True False
ii. Explain.
When there is no free space, the free block list is empty and therefore takes no space.
Exam generated for
(c) (3.0 points)
i. A simple file system, which stores files contiguously, suffers from external fragmentation.
True False
ii. Explain.
Since a simple file system stores files contiguously, it suffers from external frag- mentation since if a block of memory isn’t big enough, we can’t use it to store this file.
Exam generated for
(d) (3.0 points)
i. It is easy to make changes (e.g. adding IPv6 support) in the network layer.
True False
ii. Explain.
IP is the “narrow waist”, the only network layer protocol that provides abstrac- tions for the layers above (Applications, Transport), and the layers below (Data Link, Physical) Changing it would require changing layers above and below the IP layer as well.
Exam generated for
(e) (3.0 points)
i. I/O bound tasks tend to have short CPU bursts.
True False
ii. Explain.
I/O bound tasks are interactive and so execute quickly.
Exam generated for
(f) (3.0 points)
i. The end-to-end principle states that the design of a system should be guided by end-to-end examples.
True False
ii. Explain.
It is a suggestion on which layer/module should implement certain functionalities.
Exam generated for
i. Fate sharing means if two processes in a distributed system rely on each other, then they should be co-located onto the same machine.
True False
ii. Explain.
This question was not graded due to this content not being covered during lecture.
Fate-sharing is about state placement.
Exam generated for
For the following questions, select all that apply. If none should be selected, don’t select any. Selecting an incorrect choice or not selecting a correct choice will lead to point deductions, but the overall score for each question will be a minimum of 0.
(a) (3.0 pt) Which of the following are true about I/O and file systems?
Sequential reads from a hard drive are faster than random reads.
Memory mapped I/O is implemented by hardware mapping physical memory addresses to device registers.
FFS organizes free blocks using a linked list.
A file in NTFS must be stored contiguously on disk.
Executable files are read from disk using memory mapped I/O upon calling exec.
(b) (3.0 pt) Which of the following are true about networking?
Congestion control ensures a fast sender does not overwhelm a slow receiver.
In TCP, the ACK packet contains the next sequence number that the receiver is expecting.
It is impossible to solve the Byzantine Generals problem with 1 malicious lieutenant among 3 total participants.
HTTP is a protocol in the transport layer.
TCP sessions survive changes of IP addresses.
(c) (3.0 pt) Which of the following are true about 2PC?
Once a worker has voted to abort, it is safe to proceed to abort its local update without waiting for the
global decision.
Once the coordinator has received at least one abort vote, it is safe to immediately record in its log
and send GLOBAL-ABORT.
For one run of the protocol, the total messages sent between the coordinator and N workers (i.e. not
counting the client) are exactly 4N (N vote requests, N votes, N global decisions, N ACKs).
Logging is not a necessary mechanism for 2PC.
It is possible for 2PC to come to a decision even if multiple workers are dead.
(d) (3.0 pt) Which of the following are true about ACID properties?
Atomicity means each transaction should be treated as an indivisible unit (either all operations take
effect, or none).
Consistency means all workers/replicas in the system must have the same view of the system state.
Isolation means concurrent transactions do not interfere with each other.
Durability guarantees the system is recovered to the correct state after a crash.
Isolation guarantees that transactions appear to be serialized.
Exam generated for
(e) (3.0 pt) Which of the following are true about Pintos?
All processes should start off by having the root directory as their current working directory. Current working directories are process-specific, as opposed to being thread-specific.
Reading and writing to different disk sectors can not be done concurrently.
Reading and writing to the same disk sector can not be done concurrently.
There cannot be two inodes with the same inode number within a file system.
(f) (3.0 pt) Which of the following are true about files?
FAT file system can suffer from external fragmentation.
FAT file system has good random access in comparison to extent or inode based file systems.
Empirical evidence suggests most files are small (less than 512K bytes).
A file descriptor is equivalent to the inode number.
An inode contains the file name in addition to direct, indirect, doubly indirect, and triply indirect pointers.
(g) (3.0 pt) Which of the following are true about reliability and networking?
With WAL, having idempotent operations makes it easy to maintain consistency.
With WAL, we can only apply changes to disk after they have been logged.
When using WAL, we only replay operations that occurred before a COMMIT. UDP is a reliable, ordered, error-checked packet delivery system.
In the internet layer module, each layer relies on the services from above.
Exam generated for
Answer each question in three sentences or less unless otherwise specified. You may not use semicolons to circumvent this limit. Any answer longer than three sentences will receive a 0. Any answer without explanation may not receive credit.
(a) (4.0 pt) In a file transfer program between two hosts over the internet, where would the conservative interpretation of the end-to-end principle dictate reliability be implemented? Explain.
(b) (4.0 pt) When using FFS, explain what happens with regards to the disk as free space drops below 10-20%.
(c) (4.0 pt) Explain how data can be recovered from a single disk failure using RAID 5.
(d) (4.0 pt) Of the four necessary conditions for deadlock, which is the one most commonly eliminated? Explain.
(e) (4.0 pt) Explain one situation where busy waiting is appropriate.
(f) (4.0 pt) In 2PC, what condition(s) must be met for a transaction to be committed? What condition(s) must be met for a transaction to be aborted?
The end-to-end principle dictates that verification of reliable transfer must be implemented at the two hosts (i.e. endpoints).
Fragmentation will occur as FFS will not be able to place contiguous blocks near each other (“failure to localize blocks” in paper). This will lead to poor disk throughput.
Parity blocks XOR data blocks across the other disk blocks within the same stripe unit. If one disk block fails, then that disk block can be reconstructed by XORing the rest of the disk blocks along with the parity block.
Circular waiting is the most commonly eliminated by defining a global acquisition order as seen in Project 2.
Eliminating mutual exclusion necessitates creating more resources. Eliminating hold and wait or no preemption requires changing the core functionality of an operating system. All of these are less feasible compared to defining a global acquisition order.
Implementing locks on multiprocessors, very short critical sections, tightly inter- acting threads, or ultra-low latency I/O are all situations where busy waiting is appropriate.
For a commit, the workers need to unanimously vote commit, and the coordina- tors need to log a GLOBAL-COMMIT. Other scenarios will lead to an abortion, such as the situation when the coordinator crashes before logging a GLOBAL-COMMIT and recovers.
Exam generated for
you supposed to implement in Project 3?
(h) (4.0 pt) There are two major protocols in the transport layer; one is best effort (packets can be lost, corrupted, and out of order), and another is reliable, ordered, and error-checked. Why would we ever want to use the best effort option?
Write-through caching is when you update a block on disk at the same time you update the block in the cache. Write-back caching is when you only update a block on disk when you evict a block from the disk. In project 3, we used a dirty bit to implement write-back caching.
The best effort option (UDP) is used in applications that prioritize speed and low overhead, and either don’t care about being “lossy” or implements their own protocol for reliability. For example, in streaming audio or video, it doesn’t matter if some packets are lost or corrupted, as long as most of the packets are sent, the user will still be able to hear/see the data well enough. Another example would be any application where real time data is very important (for example real time news, weather, stock price tracking, etc) and we don’t have time for anything beyond best effort delivery. Another example would be DNS, which only involves a single UDP request and needs to be fast with low overhead.
Exam generated for
Joy, Sophie, and Adina have recently been playing GamePigeon games. They need your help to ensure they play the same game using two-phase commit (2PC).
The trio will either choose to switch to a different game or continue playing the same game. If no action has been determined, they will continue playing the same game.
Joy is the coordinator while Sophie and Adina are workers. Currently, they are playing Word Hunt. Joy wants to switch to play Anagrams. Assuming no crashes and timeouts, here is the correct sequence of events.
1. Joy writes PREPARE to her log.
2. Joy sends Sophie VOTE-REQ to switch to Anagrams.
3. Sophie writes VOTE-COMMIT to her log.
4. Sophie sends OTE-COMMIT in favor of switching to Anagrams.
5. Joy sends Adina VOTE-REQ to switch to Anagrams.
6. Adina writes VOTE-COMMIT to her log.
7. Adina sends OTE-COMMIT in favor of switching to Anagrams.
8. Joy writes GLOBAL-COMMIT to her log.
9. Joy sends Sophie GLOBAL-COMMIT to switch to Anagrams.
10. Sophie writes GLOBAL-COMMIT to her log.
11. Sophie changes the game she is playing to Anagrams.
12. Sophie sends CK.
13. Joy sends Adina GLOBAL-COMMIT to switch to Anagrams.
14. Adina writes GLOBAL-COMMIT to her log.
15. Adina changes the game she is playing to Anagrams.
16. Adina sends CK.
17. Joy writes GOT-COMMIT to her log.
Only assume the situations specified in each question (i.e. situations don’t carry over into the next question). Assume that all transmissions over the network are instantaneous and guaranteed to succeed.
Answer each question in three sentences or less unless otherwise specified. You may not use semicolons to circumvent this limit. Any answer longer than three sentences will receive a 0. Any answer without explanation may not receive credit.
(a) (4.0 points)
i. Sophie is very excited to switch games such that she sends Joy the VOTE-COMMIT before writing it in
her log (i.e. switches steps 3 and 4). Could this be a problem? Yes
ii. Explain.
Sophie’s decision must be recorded in the log before she sends her decision to Joy. If Sophie crashes after sending VOTE-COMMIT without logging it before, she won’t remember what decision she made.
Exam generated for
(b) (4.0 points)
i. If Joy crashes right after step 7, is the trio guaranteed to keep playing Word Hunt?
Yes No
ii. Explain.
When Joy reboots, she will see that she has not logged a global action but has started a vote request. As a result, she will send out a GLOBAL-ABORT to everyone, so everyone will still play Word Hunt.
Exam generated for
i. If Joy crashes right after step 1 and never recovers, are Sophie and Adina guaranteed to switch to Anagrams?
Yes No
ii. Explain.
Since Joy never transmitted the VOTE-REQ, Sophie and Adina will timeout and abort.
Exam generated for
i. Adina forgets to send Joy an ACK (i.e. step 16 does not happen). If Adina doesn’t respond within the timeout, should Joy send a GLOBAL-ABORT to Sophie and Adina?
Yes No
ii. Explain.
Joy already decided to GLOBAL-COMMIT, so this transaction must take place. As a result, Joy will continue retrying GLOBAL-COMMIT until all ACKs are received.
Exam generated for
i. Joy wants to coordinate a specific time as well to play the game, so they decide to specify a time when sending messages and logging (e.g. “VOTE-REQ: Play Anagrams tomorrow”). Is this sufficient to handle the new time constraint?
Yes No
ii. Explain.
With the guarantee of transmissions, the General’s Paradox can be interpreted to be solved. The binary nature of the decision means that 2PC will still ensure system consistency.
On the other hand, the General’s Paradox may still come into play depending on the recovery mechanisms of the participants. The possibility of participant crashes still exists since there was no such assumption about this. As a result, the system may not be Byzantine fault tolerant.
Exam generated for
Kenneth wants to improve the average response time of the autograder. Suppose an autograder server processes each grade request in order as they arrive. All grade requests must wait in a single queue. Using a stopwatch, Kenneth determines that grade requests arrive in the autograder queue following a Poisson process. Moreover, he determines the service times are exponentially distributed. Therefore, the autograder queue is a M/M/1 queue.
He is exploring proposals to improve performance. Kenneth consults Michael and Nathan regarding some options he can choose.
Michael suggests adding another server. By adding another server, each individual autograder server will receive queries at a reduced λ2 arrival rate with service time Tservice.
On the other hand, Nathan suggests upgrading the current server. There will still be one server receiving requests at a rate of λ but it will complete each grade request twice as fast with service time Tservice .
The following assumptions are made.
• The average interarrival time for grade requests is 10 minutes.
• The average service time is 8 minutes.
• Each server has its own queue with incoming requests to the autograder evenly balanced across each
server’s queue.
Help Kenneth figure out which design will best reduce the average response time.
Express your answer in a decimal with a leading zero if necessary (i.e. 0.162 instead of .162) and without any trailing zeros (i.e. 162 instead of 162.0). Round to two decimals if necessary.
Answer each question in three sentences or less unless otherwise specified. You may not use semicolons to circumvent this limit. Any answer longer than three sentences will receive a 0. Any answer without explanation may not receive credit.
(a) (4.0 points)
i. Kenneth wants to assess the current state of the autograder, so he calculates that the current
autograder utilization is 0.8. Is this correct? Yes
ii. Explain.
u=λ×Tservice = 1 ×8=0.8. 10
Exam generated for
i. Assume Kenneth correctly calculated the utilization of 0.8. What is the current average response time (in minutes) of the system (i.e. without any modifications)?
ii. Explain.
Tsys=Tq+Tservice=Tservice× u +Tservice=8×0.8+8=40. 1−u 0.2
Exam generated for
i. Assume Kenneth correctly calculated the utilization of 0.8. What is the current average length of the queue currently (i.e. without any modifications)?
ii. Explain.
Lq =λ×Tq = 1 ×32=3.2. 10
Exam generated for
i. Assume Kenneth correctly calculated the utilization of 0.8. What is the average response time (in minutes) if Kenneth takes Michael’s suggestions?
ii. Explain.
By adding another server, the utilization will decrease by a factor of 2 as the
arrival rate on any single queue will decrease by 2. Therefore, Tsys = Tq + Tservice =
Tservice × 0.5u + 8 = 13.33. 1−0.5u
Exam generated for
i. Assume Kenneth correctly calculated the utilization of 0.8. What is the average response time (in minutes) if Kenneth takes Nathan’s suggestions?
ii. Explain.
By upgrading the server, the service time will decrease by a factor of 2. With half
the service time, utilization decreases to u = 0.4. Therefore, Tsys = Tq +0.5Tservice =
0.5Tservice × 0.5u + 4 = 6.67. 1−0.5u
Exam generated for
After his career as a 162 TA, Sean has been contacted by Korean entertainment companies to help build some distributed systems infrastructure to support their artists.
(a) (16.0 points) Instagram File System
EDAM Entertainment has asked Sean to design a file system for storing and receiving Instagram photos. Jieun wants to save her photos in high quality, which would result in 2048 photos, each of size 4 MiB. Each photo will be stored as an individual file.
Answer each question in three sentences or less unless otherwise specified. You may not use semicolons to circumvent this limit. Any answer longer than three sentences will receive a 0. Any answer without explanation may not receive credit.
i. (4.0 points)
A. Sean initially considers taking the simple route and implementing FAT32. Would he face any
issues? Yes No
B. Explain.
Sean would not face any issues since each photo is 4 MiB which is well within the 4 GiB file size limit for FAT32.
Alternatively, performance can be an issue with FAT32. If the disk sector size is very small in comparison to the photo sizes, then random access and locality is
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com