CS372: Solutions for Homework 14

Problem 1:

Suppose a server workload consists of network clients sending 128-byte requests to a server which reads a random 50KB chunks from a server's file system and transmits that 50KB to the client. The server's file system is able to cache all metadata, so that each read consists of a single 50KB sequential read from a random location on disk. The server may have multiple disks and multiple network interfaces.

Each disk rotates at 10000 RPM and takes 5 ms on an average random seek. There are on average 300 sectors per track and each sector is 512 bytes (in actuality, the number of sectors per track will vary, but we'll ignore that. We'll also assume that each request is entirely contained in one track and that each starts at a random sector location on the track.)

To access disk, the CPU overhead is 30 microseconds to set up a disk access. The disk DMAs data directly to memory, so there is no CPU per-byte cost for disk accesses.

Each network interface has a bandwidth of 100 Mbits/s (that's Mbits not MBytes!) and there is a 4 millisecond one-way network latency between a client and the server. The network interface is full-duplex: it can send and receive at the same time at full bandwidth. The CPU has an overhead of 100 microseconds to send or receive a network packet. Additionally, there is a CPU overhead of .01 microseconds per byte sent.

  1. How many requests per second can each disk satisfy?
    Solution:
    A 10,000 RPM disk takes 6ms per rotation and an average rotational delay is 1/2 rotation ——> 3ms avg rotational delay.
    50KB is 100 * 512 byte sectors or 1/3 rotation to read the data (BW term is 2ms). So an average disk request takes
    5ms seek + 3ms rotation + 2ms Bw = 10ms

    So, a disk can support up to 100 requests per second.

    (Note a slight simplifying assumption: we ignore the effect that a track buffer might have. A track buffer would sometimes overlap some of the rotation time and some of the BW time by letting the read begin at the "end" of the 50KB chunk, wait for the beginning part to come around, and be done when the beginning part has been read...)

  2. How many requests per second can each network interface satisfy?
    Solution:
    Since the interface is full duplex, it will be limited by the send rate for the big packets (and the little incoming packets will not affect this). 50x2^10 bytes/request * 1 second/100X10^6 bits * 8 bits/byte = 4ms/request. So, a network interface can support up to 250 requests per second.

  3. How many requests per second can the CPU satisfy (assuming the system has a sufficient number of disks and network interfaces?)
    Solution:
    The CPU overhead is (100 + .01 * 128)us to receive the request + 30 us to set up the disk access + (100 + .01 * 50x2^10)us to send the reply = 743 us/request. So, the CPU can handle 1345 requests per second.

  4. What is the latency from when a client begins to send the request until it receives and processes the last byte of the reply (ignore any queuing delays).
    Solution:

*L_nw: how to pipeline? Here, I assume the (unrealistic) best case scenario: the CPU starts processing the packet when the first byte arrives and finishes processing the last byte just as the last byte arrives. Other reasonable assumptions would be to not start processing the packet once it has entirely arrived. In reality, a large NW send (like 50KB) would be broken into smaller packets, each of which would be processed once it has entirely arrived to get pipelining, but each also would pay an overhead.

Each arrow shows a dependency in time (the tail must happen before the head).

Total time on critical path is
o_nw + b_nw(128) + L_nw+ o_disk + seek + rot + bw + o_nw + b+nw(50x2^10) + L_nw = 100x10-6 + 128 bytes * 1 second/100x10^6 bits * 8 bits/byte + 4x10-3 + 30x10-6 + 100x10-6 + 50x2^10 * 1 second/100x10^6 bits * 8 bits/byte = 8.336ms

Problem 2:

Consider a distributed system where there is a file server and a number of client machines. To provide concurrency control, the file system includes a lock manager that issues locks to client machines upon requests. Locks can be either shared or exclusive. Shared locks are useful only for file reads, while exclusive locks are needed for file updates. The file server issues lock to a given client with a timed leases, such that when the lease expires, the lock is revoked and the client machine must re-apply to reacquire the lock. Answer the following questions:
  1. Why are leases useful?
    Solution:
    Needs solution.

  2. Consider the following scenario in accessing a file F.
    MachineRequest time:Request type: Duration until release
    A00:00Shared05
    B00:05Shared10
    C00:08Exclusive02
    D00:10Shared05
    B00:14Exclusive05
    A00:20Shared05
    Assuming that a lease is given for 10 time units, that clients cache the files for performance, that coherence is maintained by an update protocol, and figures showing the four machines and the file server as blocks (see example below), and identifying at each state transition which client machine holds which lock, and the state of the cache at each client. A state transition occurs when the state of the cache changes at one client, when a request is received, when a lock is acquired or when a lock is released.

    Time: 00:00
    Machine A
    Lock: Shared
    Cache: File F    		 Machine B
    Lock: None
    Cache: Empty    		 Machine C
    Lock: None
    Cache: Empty    		 Machine D
    Lock: None
    Cache: Empty

    Solution:
    Needs solution.

  3. If an "invalidate'' protocol is used for coherence, would the efficiency of the system increase or decrease? Why?
    Solution:
    Needs solution.

  4. Same as (b), but assume that machine C fails 1 time unit after it acquires the lock. Show the state transition diagrams as instructed in part (b). State clearly and precisely what precautions should be taken in writing the code that updates the file at machine C.
    Solution:
    Needs solution.

Problem 3

Sun's network file system (NFS) protocol provides reliability via: Which is the best network on which to implement a remote-memory read that sends a 100 byte packet from machine A to machine B and then sends a 8000 byte packet from machine B to machine B?
  1. A network with 200 microsecond overhead, 10 Mbyte/s bandwidth, 20 microsecond latency
  2. A network with 20 microsecond overhead, 10 Mbyte/s bandwidth, 200 microsecond latency
  3. A network with 20 microsecond overhead, 1 Mbyte/s bandwidth, 2 microsecond latency
  4. A network with 2 microsecond overhead, 1 Mbyte/s bandwidth, 20 microsecond latency

Solution:
Needs solution.

Problem 4

True or false. A virtual memory system that uses paging is vulnerable to external fragmentation.
Solution:
Needs solution.

Problem 5

In class, we discussed the fact that, if messages can be lost, it is impossible to devise an algorithm that guarantees that two nodes can agree to do the same thing at the same time (the two generals problem). However, weaker forms of agreement may be possible.

Suppose two nodes, A and B, communicate via messages and that the probability of receiving any message that is sent is P (0 < P < 1 ). You need not consider any other types of failures.

  1. Is it possible for A and B to agree with certainty to perform some action (but not necessarily perform it at the same time)? If not, explain why not. If so, describe a protocol that provides this guarantee.
    Solution:
    Needs solution.

  2. Is it possible for both nodes to agree to do the same thing at the same time with >99.99999% certainty (e.g. guarantee that there is less than a 0.0000 1% risk that one or both will fail to make the appointment)? If not, explain why not. If so, describe a protocol that provides this guarantee.
    Solution:
    Needs solution.

  3. Suppose that in addition to lost messages, either A or B may crash at any time and, once crashed, recover at some arbitrary time in the future. Is it possible for A and B to agree with certainty to perform some action (but not necessarily perform it at the same time)? If not, explain why not. If so, describe a protocol that provides this guarantee
    Solution:
    Needs solution.