CS414 Fall 2003 Homework 4. Due in class on October 21, 2003

1. In class, we discussed the Banker’s Algorithm for deadlock-free resource allocation. Consider a system with two kinds of resources, R₁ and R₂. Initially there are 2 units of R₁ and 10 units of R₂. Process P₁ has a maximum need of 2 units of R₁ and 3 units of R2, denoted NEED(P₁)={2,3}; NEED(P₂)={1,7}, NEED(P₃)={0,4}, NEED(P₄)={2,7}. At the start, no resources have been allocated.

a) Assume that the system is presented with the following requests, in the following order:

i. P₁ requests [1 unit of R₁ and 1 unit of R₂].

ii. P₂ requests 5 units of R₂.

iii. P₃ requests 2 units of R₂.

iv. P₄ requests [2 units of R₁ and 2 units of R₂].

Which requests will be granted, and which ones will be delayed? Note: We’ve used the notation [x units of R₁ and y units of R₂] when a process requests two resources at the same time. The system won’t grant the request unless it can grant the desired number of units in one “atomic” action.

b) After step (a), P₁ requests [1 unit of R₁ and 2 units of R₂]. Will P₁’s request be granted immediately?

c) Starting in the system state reached after step (b), give one example of a request that can be granted immediately and one example of a request that would be delayed.

2. Machines A and B are connected by a network that supports the Internet protocols. Each machine has an internal clock, and these clocks are extremely accurate for measurements of elapsed time. However, the clocks are not very well synchronized: there is some unknown and potentially large (but unchanging) clock skew CLOCK(A)-CLOCK(B). For example, perhaps when CLOCK(A) claims that it is 9:21.9827171am, CLOCK(B) reads 9:22.01934188am.

a) List some reasons that in a real network, delays from A to B might not be the same as delays from B to A.

b) List some reasons that in a real network, the delay from A to B might vary over time, perhaps rapidly, and perhaps by a large amount.

c) Assume that the network device driver has a mechanism for putting a timestamp on a packet, so that just as the packet is sent, the “outgoing” clock time is recorded on that packet, and just as a packet is received, the “incoming” clock time is recorded (each time, using the clock of the machine that did the send operation, or that received the packet). Design a protocol to compute the skew between the clocks on A and B.

d) Now, assume that A has a closer estimate of the true time than B. How would the skew be used to “synchronize the two clocks?

e) Can your clock “synchronization” algorithm from step (d) accurately synchronize the clocks on A and B in the presence of the kinds of variability you pointed to in steps (a) and (b)? Explain.

3. Suppose that MegaMusic.com maintains file servers worldwide with names like srv0000.MegaMusic.com, srv0001.MegaMusic.com, etc. Madonna’s new record “GutterTalk” is released, and lots of MegaMusic subscribers want to play cuts from it. They all access URL http://www.MegaMusic.com/Madonna/GutterTalk.html.

a) How would a MegaMusic customer judge the performance of the service?

b) How would people who run the company judge performance of the system?

c) How could the DNS be used to route user requests to servers so as to simultaneously satisfy both categories of goals?

4. Your close friend Doug “The Bug” Crump is developing a multi-user role playing game for the Internet. In this game, when user A fires a weapon at user B, a message is sent from user A’s computer to user B’s system to determine what damage was done. While waiting for a reply, the process on machine A is waiting for action by a process on machine B. Doug is trying to correct a deadlock in which A waits for B, B waits for C, etc, and a cycle arises.

a) Suppose that Doug implements a protocol that “chases wait-for” edges, as follows. If machine A has been waiting for a while, it sends a special message to B that checks B’s status. Initially, this message contains a null “visited” list. On reception, if B isn’t waiting for any other process, B can discard the message. On the other hand, if B is waiting for something to happen at C, B appends its node-id (“B”) to the list, and forwards the request to C. The idea is that if a cycle is present, we’ll see it in the list: A, B, C, D, B… and on detecting a cycle, the node that notices it can do something to stop waiting. But is Doug’s wait-for edge-chasing protocol correct? Explain.

b) Correct or not, will Doug’s protocol break deadlocks? Explain

c) At 4:30am, Doug wakes you up to say that his protocol in part (a) did have a bug, but he thinks he’s fixed it. He says that instead of assuming that a cycle represents a deadlock, he makes the message keep looping. If a message goes around the same loop twice, a deadlock is present (e.g. A, B, C, D, B, C, D, B). Is Doug’s new and improved solution bug-free, or does your friend need some sleep?