QUIZ #1. 2--3 p.m., rooms 34-101 et al.
---------------------------------------------------------------------------------------
This quiz contains six problems whose relative weights are indicated below. Please
place each answer on the page with the question and hand in this booklet at the end of
the examination.
Put your name on this cover sheet AND at the bottom of each page of this booklet. The
booklet may be separated for grading so that each problem can be evaluated by one
grader. Be sure that you don't put part of the answer to a problem on the back of a
sheet for another problem!
Some parts of some problems may be much harder than others. Read them all through
first and attack them in the order that allows you to make the most progress. Write
down any assumptions and show your work, or you risk losing partial credit. Be neat.
If we can't figure out your answer we can't give you credit. On answers that involve
numbers, be sure to specify clearly the units of your answer.
---------------------------------------------------------------------------------------
Circle your recitation instance:
1. 10:00---Tennenhouse/McDonald
2. 11:00---Tennenhouse/DeHon 5. 11:00---Corbató/McDonald 7. 11:00---Waldspurger/Manning
6. 12:00---Waldspurger/DeHon
3. 1:00---Kaashoek/Manning 8. 1:00---Corbató/Joseph
4. 2:00---Kaashoek/Joseph
For Official Use Only
----------------------------
Problem Your Score Maximum
Score
1. (10 points) According to the paper by Schroeder et al., "Except during reconfiguration, Autonet never discards packets." (p. 1319, col 2). Louis Reasoner takes this statement to mean that if he is careful never to launch a packet during a reconfiguration, he can dispense with end-to-end verifications and simply assume that all packets will be delivered. Set Louis straight by pointing out two substantially different situations that may occur and that require that the sender verify that the intended recipient got the packet, even in Autonet.
Situation 1.
Situation 2.
2. (5 points) The X Window system deals with both big-endian and little-endian clients by providing two different network ports. Big-endian clients send requests and data to one port, while little-endian clients send requests and data to the other. The server may, of course, be implemented on either a big-endian or a little-endian machine. This approach is unusual. Most network servers provide only one network port, and require that all data be presented at that port in little-endian form. Explain the advantage of the structure chosen by X, as compared with the usual structure.
3. (25 points) For each of the following statements, circle whether it is True or False, and briefly explain. An answer without an explanation will receive no credit. And if you give a good enough explanation you may be able to get credit even if you say False to a point we thought was True, or vice-versa. But keep it brief!
a. One advantage of a microkernel over a monolithic kernel is that it reduces the load on the Translation Lookaside Buffer (TLB), and thereby increases its hit rate and its consequent effect on performance. TRUE/FALSE
b. Ethernet is not very scalable because a centralized mechanism is used to control network contention. TRUE/FALSE
c. The primary way that hierarchy reduces complexity is that it reduces the size of individual modules. TRUE/FALSE
d. The primary way that modularity reduces complexity is that it eliminates incommensurate scaling. TRUE/FALSE
e. As linear feature size goes down, the number of components that can be placed on a chip goes up with the inverse square. But overall computation capacity improves with the inverse cube of feature size. TRUE/FALSE
4. (25 points) Ben Bitdiddle has written a "style checker" intended to uncover writing problems in technical papers. The program picks up one sentence at a time, computes very hard for a while to parse it into nouns, verbs, etc., and then looks up the resulting pattern in an enormous database of linguistic rules. The database was so large that it was necessary to place it on a remote server and do the lookup with a remote procedure call.
Ben is distressed to find that the RPC's have such a long latency that his style checker runs much more slowly than he hoped. Since he is taking 6.033 he wonders if adding multiple threads to the client could speed up his program.
a. Ben's checker is running on a single-processor workstation. Explain how multiple client threads could reduce the time to analyze a technical paper.
b. Ben implements a multithreaded style checker, and runs a series of experiments with various numbers of threads. He finds that performance does indeed improve when he adds a second thread, and again when he adds a third. But he finds that as he adds more and more threads the additional performance improvement diminishes, and finally adding more threads leads to reduced performance. Give an explanation for this behavior.
c. Suggest a way of improving the style-checker's performance without introducing threads. (Ben is allowed to change only the client.)
5. (25 points) Suppose the longest packet you can transmit across the Internet can contain 480 bytes of useful data, you are using a lock-step end-to-end protocol, and you are sending data from Boston to California. You have measured the round-trip delay and found that it is about 100 milliseconds. (A lock-step protocol is one where you must wait for the recipient to send an acknowledgement of your previous packet before you can send the next packet.)
a. If there are no lost packets, estimate the maximum data rate you can achieve.
b. Unfortunately, 1% of the packets are getting lost. So you install a resend timer, set to 1000 ms. Estimate the data rate you now expect to achieve.
c. On Tuesdays the phone company routes some westward-bound packets via satellite link, and we notice that 50% of the round trips now take exactly 100 extra milliseconds. What effect does this delay have on the overall data rate when the resend timer is not in use. (Assume the network does not lose any packets.)
d. Ben turns on the resend timer, but since he hadn't heard about the satellite delays he sets it to 150 ms. What now is the data rate on Tuesdays?(Again, assume the network does not lose any packets.)
e. Usually, when discussing end-to-end data rate across a network, the first parameter one hears is the data rate of the slowest link in the network. Why wasn't that parameter needed to answer parts a-d of this question?
6. (10 points) OutTel corporation has been delivering j486 microprocessors to the computer industry for some time, and Metoo systems has decided to get into the act by building a microprocessor called the "clone486+", which differs from the j486 by providing twice as many processor registers.
Metoo has simulated many programs and concluded that having twice as many processor registers reduces the number of loads and stores to memory by an average of 30%, and thus improves performance, assuming of course that all programs are recompiled to take advantage of the extra registers.
The most popular operating system for the j486 is microkernel---based. As suggested, the hoped-for performance improvement won't be realized unless all applications, both client and server, and the microkernel itself are recompiled. Point out one other reason why Metoo may find the performance improvement to be less than their simulations of individual programs predicts. If you think of more than one reason, choose the one that is likely to reduce performance the most.