Spring 2019
University of California, Berkeley College of Engineering Computer Science Division EECS
Midterm III SOLUTIONS
John Kubiatowicz
Copyright By PowCoder代写 加微信 powcoder
May 2nd, 2019
CS162: Operating Systems and Systems Programming
Your Name: Your SID:
Discussion Section Time:
General Information:
This is a closed book exam. You are allowed 3 pages of notes (both sides). You have 2 hours to complete as much of the exam as possible. Make sure to read all of the questions first, as some of the questions are substantially more time consuming. Write all of your answers directly on this paper. Make your answers as concise as possible. On programming questions, we will be looking for performance as well as correctness, so think through your answers carefully. If there is something about the questions that you believe is open to interpretation, please ask us about it!
Problem Possible Score
5 31 Total 100
CS 162 Spring 2019 Midterm III
May 2nd, 2019
[ This page left for ] 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899
CS 162 Spring 2019 Midterm III Your SID:__________________________ May 2nd, 2019
Problem 1: True/False [18 pts]
Please EXPLAIN your answer in TWO SENTENCES OR LESS (Answers longer than this may not
get credit!). Also, answers without an explanation GET NO CREDIT.
Problem 1a[2pts]: A single file server can be constructed with a Byzantine Agreement algorithm for
file commit such that clients are protected against break-ins to the server. ⬜ True False
Explain: A Byzantine Agreement algorithm requires 3f+1 servers to tolerate f malicious servers. A system with only one server would tolerate f=0 (i.e. no) breakins.
Problem 1b[2pts]: When using RPC to communicate over the network, a client and host/server could share arguments and return values even if the communicating entities have processors with different “endianness” (i.e. x86 vs MIPS).
True ⬜ False
Explain: During the marshalling process at the source of an RPC packet, data is
normalized into an internet standard format (including endianness). At the destination, data is unmarshalled into the local format, translating into the local endianness.
Problem 1c[2pts]: When producing a queueing model of some system (such as a filesystem) and the distribution of request arrival times is unknown, the best estimate is to use a deterministic distribution.
⬜ True False
Explain: The best distribution to use when you do not have enough information is
typically a “memoryless” distribution since the aggregation of many independent processes often behaves in a memoryless fashion.
Problem 1d[2pts]: Direct Memory Access (DMA) refers to a situation in which the processor bypasses the cache to access DRAM directly.
⬜ True False
Explain: DMA is a mechanism that permits transfers directly to/from devices to
memory without involving the processor (thereby freeing the processor to do other things).
Problem 1e[2pts]: The Bitcoin blockchain could be used for distributed decision making. True ⬜ False
Explain: Proposed decisions are submitted to the mining network as potential
transactions. The mining network will serialize them, ultimately putting all proposed decisions into a global order, from which a winner could be selected (like earliest wins, or any other function from a set of proposals to a decision).
CS 162 Spring 2019 Midterm III May 2nd, 2019
Problem 1f[2pts]: The acronym “RAID” refers to RApid Insect Death, and is a general term for a whole class of insecticides.
⬜ True False
Explain: RAID stands for “Redundant Arrays of Inexpensive Disks” and refers to a
technique for combining disks together for reliability.
Problem 1g[2pts]: In the Fast File System (FFS) without a buffer cache, the number of disk accesses to retrieve the first byte of a file is always less than the number of disk accesses to retrieve the last byte of a file.
⬜ True False
Explain: For small files that can be described entirely with direct pointers, the first
and last byte takes the same number of disk accesses, namely two (one for inode, one for datablock).
Problem 1h[2pts]: The End-to-End principle suggests that the best way to achieve error-free communication is to provide 100% reliability at every hop in the network through error correction coding and retransmission.
⬜ True False
Explain: In fact, the End-to-End principle suggests exactly the opposite – since
reliability must be guaranteed at the endpoints anyway (there are many ways in which data can be lost other than just along a network line), there is no reason to work extra hard in the network to ensure 100% reliability.
Problem 1i[2pts]: The Journal in a “Journaled file system” has no benefit unless it can be placed on a separate physical disk from the filesystem.
⬜ True False
Explain: Journaling helps to ensure consistency of the file system by providing
transactional updates to the file system – even when the journal is on the same physical disk as the filesystem.
CS 162 Spring 2019 Midterm III Your SID:__________________________ May 2nd, 2019
Problem 2: Multiple Choice [17pts]
Problem 2a[2pts]: In consistent hashing, if we have N servers, how many servers must we move keys from when we add a server (choose one):
A: one (1).
B:⬜ two (2).
C:⬜ log(N).
Problem 2b[2pts]: Memory-mapped I/O is (choose one):
A hardware mechanism for assigning physical memory addresses to devices such that processor read and write operations to these addresses become commands to devices.
A software protocol that constructs a coherent distributed shared memory between multiple physical nodes, allowing communication between nodes to occur as reads and writes to the shared memory (address) space.
A technique for communication between processes using the mmap() system call. As a result, processes can interact via reads and writes to shared memory addresses.
A security mechanism for I/O devices that that prevents user-mode applications from directly accessing these devices, forcing device access to go through the system call interface.
Problem 2c[2pts]: What is two-phase commit (2PC) and what problem does it solve? (choose one):
Two-phase commit is an algorithm that can help to make progress on a distributed consensus problem even in the presence of malicious nodes.
Two-phase commit is used in single-server databases to ensure serializability of simultaneous transactions by controlling transaction commit order.
Two-phase commit is a distributed decision making algorithm that makes sure that all participants eventually come to the same decision whether to commit or abort – despite intermittent crashes and restarts of participants.
Two-phase commit is a distributed decision making algorithm that is valuable because it can continue to make forward progress despite crashed or unavailable participants.
CS 162 Spring 2019 Midterm III May 2nd, 2019 Problem 2d[2pts]: What is Network Address Translation (NAT)? (Select One):
A mechanism that is part of the Domain Name System (DNS) for handling website names that are not in English.
A mechanism for load-balancing incoming queries among a set of servers in a warehouse (cloud) computing system.
A mechanism for sharing one or more external IP addresses amongst a larger set of local (non-routable) IP addresses.
A mechanism whereby a local network router can handle outgoing messages by forwarding them to an authoritative router that participates the BGP routing protocol.
Problem 2e[3pts]: Which of the following are true about modern hard disks? (Mark all that apply):
They have an independent disk head on every surface of every platter. As a result, the disk can simultaneously read or write from different tracks on different platters.
Some of them gain bit density by overlapping tracks.
They have internal caching, allowing them to read a whole track at a time.
They have a lower bit density on the outside tracks from the inside tracks (because the surface of the outside tracks move under the disk head faster than that of the inside tracks).
Problem 2f[3pts]: Little’s Theorem has the following properties (Mark all that apply):
They support bit densities 1 Exabit (1015)/square inch It applies only to memoryless arrival distributions.
It says that the average number of jobs in the system is equal to the average arrival rate of jobs multiplied by the average length of time that a job stays in the system.
It shows why the average length of time spent in a queue grows without bound as the system utilization approaches 100%.
It applies only to systems in equilibrium.
It can be used to compute the average time spent in a queue, given the average length of the queue.
None of the above.
Their internal controllers can queue requests and perform variants of the elevator algorithm without consulting the operating system.
CS 162 Spring 2019 Midterm III Your SID:__________________________ May 2nd, 2019 Problem 2g[3pts]: The Berkeley FFS has the following properties (Mark all that apply):
C: D: E:
It changed the inode format from the BSD 4.1 file system to better reflect the overwhelming presence of small files in a typical UNIX filesystem.
It placed all the inodes together on the inner tracks of the disk for better performance.
It reserved 10% of the blocks to ensure that new files could get sequential groups of blocks for better read performance.
It performed skip-sector allocation of blocks to prevent processor delays during reading from missing blocks and forcing a complete rotation for each block read.
It placed the inodes and blocks for files within a directory close to the blocks and inodes for the directory to improve performance.
It introduced a B-tree format for directories in order get better lookup performance for directories with large numbers of files.
CS 162 Spring 2019 Midterm III May 2nd, 2019
Problem 3: Pintos/File Systems [24pts]
Consider the following inode_disk and indirect_block struct similar to what is in Pintos. Suppose sectors are 512 bytes.
struct inode_disk {
block_sector_t direct[12];
block_sector_t indirect;
block_sector_t triply_indirect; // Note that this is a triply
size_t size;
void unused[113];
// and that there is no doubly!
struct indirect_block { // doubly and triply indirect blocks look like this
block_sector_t block_nums[128];
Problem 3a[2pts]: What is the maximum file size supported by this design? Leave your answer unsimplified in the box:
512 (12 + 128 + 128128128)
Problem 3b[4pts]: How many sectors of each type are required to represent a maximum sized file
in this design? Leave your answer unsimplified in the box:
Data blocks:
12 + 128 + 128128128 Indirect blocks:
1 + 128128 Doubly indirect blocks:
Triply indirect blocks:
CS 162 Spring 2019 Midterm III Your SID:__________________________ May 2nd, 2019
Problem 3c[6pts]: Suppose that we have a file that is represented using the inode structures of (3a) and (3b) and that the current size of the file is 12 * 512 bytes long. We now want to write 512 characters to the end of this file. You may use the following functions:
void block_read(void *buffer, block_sector_t block_num);
void block_write(void *buffer, block_sector_t block_num);
block_sector_t block_allocate();
The block sector corresponding to the file’s inode_disk struct is 3:
block_sector_t FILE_INODE_BLOCK = 3;
Fill in the blanks in the following function such that after running this function, 512 characters are written to this file and persisted. Assume that the file is exactly 12 blocks long already. You may not need all of the blanks, but may only have 1 semicolon per line.
void Append512Chars () {
struct inode_disk inode;
block_read(&inode, FILE_INODE_BLOCK); // Read inode from disk
inode.indirect = block_allocate(); // Allocate new block for indirect
struct indirect_block indirect_block;
indirect_block.block_nums[0] = block_allocate();
void buffer[512];
memset(buffer, ‘a’, 512);
inode.size += 512; // Change the size
block_write(buffer, indirect_block.block_nums[0]); // Persist data
block_write(indirect_block, inode.indirect); // Persist indirect
block_write(inode, FILE_INODE_BLOCK); // Persist inode
CS 162 Spring 2019 Midterm III May 2nd, 2019
Suppose that we build our disk subsystem to handle a high rate of I/O by coupling many disks together. Properties of this system are as follows:
Has a total of 24 disks, each of which is 2TB in size
Uses disks that rotate at 12,000 RPM, have a data transfer rate of 81.92 MBytes/s (for each
disk), and have an 4.5 ms average seek time, 4KiB sector size
Has a SCSI interface with an 600s controller command time. Assume that a group of
consecutive sectors can be fetched with a single request.
Has a file system that groups sectors into 32KiB blocks
Is limited only by the disks (assume that no other factors affect performance).
Each disk can handle only one request at a time, but each disk in the system can be handling a different request. The data is not striped (all I/O for each request has to go to one disk).
EACH OF THE FOLLOWING ANSWERS SHOULD BE SIMPLIFIED TO SINGLE NUMBERS. HOWEVER, YOU MUST SHOW YOUR WORK TO CREDIT.
Problem 3d[4pts]: What is the average service time to retrieve a single disk block from a random location on a single disk, assuming no queuing time (i.e. the unloaded request time)? Hint: there are four terms in this service time!
Tser= Tctrl + Tseek + Trot + Txfer =
= 0.6𝑚𝑠 4.5𝑚𝑠 1⁄2 , /
= 0.6𝑚𝑠 4.5𝑚𝑠 2.5𝑚𝑠 .4𝑚𝑠 = 8ms
, / . / /
Problem 3e[2pts]: Assume that the OS is not particularly clever about disk scheduling and passes requests to the disk in the same order that it receives them from the application (FIFO). If the application requests are randomly distributed over a single disk, what is the bandwidth (bytes/sec) that can be achieved?
BW = 32768 bytes / Tser
= 32768 / (8ms 10-3 s/ms)
= 4,096,000 bytes/s = 4.096 MBytes/s
Problem 3f[2pts]: Suppose that the application has requests outstanding for all disks (but they are still randomly distributed, handed FIFO to disks), what is the maximum number of I/Os per second (IOPS) for the whole disk subsystem (an “I/O” here is a block request)?
1 Disk IOP takes 8ms = 0.008s (1/0.008) IOPS = 125 IOPS 24 Disks IOPS = 24 125 IOPS = 3000 IOPS
Page 10/26
CS 162 Spring 2019 Midterm III Your SID:__________________________ May 2nd, 2019
Problem 3g[4pts]: Treat the entire system as an M/M/m queue (that is, a system with m servers rather than one), where each disk is a server. All requests are in a single queue. Assume that the disk system receives an average of 2250 I/O random requests per second. For simplicity, assume that any disk can service any request. Assuming FIFO scheduling by the OS again, what is the mean response time of the system? You might find the following equation for an M/M/m queue (where any server can handle any request from the queue) useful:
Server Utilization ( ) Timeserver 1m
Time Time queue
Timeserver /m
server m1 Tserver = 8ms/IO = 0.008 s/IO
= 2250 IO/s
= 2250 IO/s 0.008 s/IO / 24 = 2.25 / 3 = (9/4) / 3 = 3⁄4 = 0.75
Tqueue =Tserver . =0.008s =0.001s=1ms .
Tsystem = Tqueue + Tserver = 1ms + 8ms = 9ms
Page 11/26
CS 162 Spring 2019 Midterm III May 2nd, 2019 [This Page Intentionally Left Blank]
Page 12/26
CS 162 Spring 2019 Midterm III Your SID:__________________________ May 2nd, 2019 Problem 4: Global Potpourri [10pts]
Problem 4a[4pts]: Suppose that you have a dedicated satellite connection between two points on the earth. The satellite will be in a geostationary orbit (at an altitude of 35,786 km). Assume that we will be using TCP over this connection. Assume that the satellite forwards all bits after a 100ms latency (fully pipelined, since there is no routing in the satellite). Also assume that we can use “jumbo TCP frames” with an MTU of 9000 bytes.
Parameter Speed of light
Transmission Bandwidth
TCP/IP header size
Data payload for ACK (has TCP/IP header)
V alue 3 105 km/s 5×109 bits/s
40 bytes 9000 bytes 0 bytes
Assume that computational time at the receiver (copying, code execution, etc) is zero. Accounting only for transmission time, what should the sender’s TCP window size be to achieve maximum bandwidth? Assume no packets are dropped. Show all of your work (no credit for a single number). Hint: don’t forget that the TCP/IP header is overhead.
If you do not have a calculator, you may leave the result as a simple mathematical expression. However, PLEASE PLUG IN ALL NUMBERS AND SPECIFY FINAL UNITS!
In order to ensure maximum bandwidth, we need to allow many packets to be in transit before we receive the first ACK. Once data is ACKed, we know that it has successfully made it to the destination and can be discarded. Consequently, the size of the transmission window is simply the amount of data that can be transmitted during one round-trip time.
1 RTT = 2 × 1-way time = 2 × [2 × 35786 km/(300000km/s) +0.100s] = 2× 0.338s = 0.676s Total BW = data bandwidth = [(9000-40)/9000] × 5×109 = 4.98×109 bits/s = 6.23 ×108 bytes/s So, Windows = 6.23 × 108 bytes/s × 0.676s = 4.21 × 108bytes
(Note that technically this is: 4.21 ×108/(1024)2 MiBytes = 401MiBytes)
Page 13/26
35,786 Kilometers
35,786 Kilometers
CS 162 Spring 2019 Midterm III May 2nd, 2019
Problem4b[3pts]: In class, we discussed the Chord distributed key-value store, which uses Consistent Hashing to store data among a large set of servers. Explain how key-value pairs are distributed among servers in Chord and how is it possible for the ‘get(key)’ process to return the value associated with ‘key’ in O(log(n))steps where n is the number of servers.
Each server has a randomly assigned name in an m bit space (e.g. derived by an m-bit hash over the IP address). Keys are also m bits in length. Servers are arranged in a large virtual ring, positioned by their m-bit names. (the ring is all values from 0 … 2m-1, wrapping around at zero).
Each key is placed on the server that has the smallest name value that is the key. Since keys and server names are randomly distributed this is probabilistically evenly distributed.
Servers know the identity (IP address) of the servers that are before (predecessor) and after
(successor) them in the ring, allowing a guaranteed O(n) lookup of any key. To achieve
points on the ring, namely 𝟐-way, 𝟒-way , 𝟖-way, … 𝒎-way around the ring. These fingers allow
O(log(n)), servers also dynamically discover “finger” pointers at geometrically distributed
short-cut routing to keys that takes, on average, log(n) hops to find a key.
Problem 4c[3pts]: Suppose that we have storage servers in machine rooms on every continent and wish to use them to provide “deep archival” service (the ability to recover data with extremely high probability despite a variety of global disasters). Suppose further that we only have enough total disk space for no more than a factor of four (x4) blowup in the size of the data. What can we do that would be (much) better than simply making four copies of every piece of data? (Hint: your answer has something to do with encoding and placement).
We should use an erasure coding (such as code mentioned in class) which requires any m of n “fragments” of data to be retrieved in order to reconstruct data. If n/m = 4, then the total data size is a 4-times the original data size, thereby meeting our size constraints. For example, we talked about m=16, n=64 in class.
We must also make sure that our various fragments are stored on servers that have independent failure modes. F
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com