MCS-378 Homework Part 2 (Fall 2002)

When turning in a homework problem, if it is one from the book, you should indicate the exercise number. If it is not from the book, you should indicate the number I give with an x in it, as in 11.x1 below. These will be the reference numbers I use in reporting back your standing on the homework.

Chapter 11

Problem 11.x1: The Linux systems we are using in the lab have a file system that uses inodes like those illustrated on page 384 of our textbook. Each inode has room for 12 direct block pointers, then pointers to single indirect, double indirect, and triple indirect blocks. Each block holds 4KB (i.e., 4096 bytes). Each pointer to a block takes 4 bytes. Suppose a file is as big as it can be without using the triple indirect pointer. What fraction of the file is accessed by way of the double indirect pointer? If you give your answer as a value rounded to some number of decimal places, rather than as an exact fraction, be sure to give enough significant places to show just how close to 0% or 100% (as the case may be) the answer is. If the answer is close to 0, it should end in a digit that is non-zero. If the answer is close to 100%, it should end in a digit that is not 9. An exact fraction is also good.

Chapter 12

Problem 12.x1: The operating systems for general purpose workstation computers normally read input packets from their network interfaces on an interrupt-driven basis. In contrast, computers that are specially designed as dedicated inter-network routers normally poll for packets from their network interfaces. Explain why each strategy makes sense in context, and why the other wouldn't.

Chapter 13

Problem 13.x1: This is like exercise 13.2 from page 458, except that the queue of pending requests is 80, 1490, 850, 100, 900, 1100, 1600, 1720, 150.
Problem 13.x2: This is like exercise 13.3 from pages 458-459, except based on 13.x1 instead of 13.2. Part a says that seek time is proportional to the square root of distance, but part b gives a formula with a constant term as well as the term proportional to the square root of distance. To understand this, you need to understand that our authors have chosen to use "seek time" in two different senses in one problem. The full seek time of a disk is combined out of two parts: time to move the head arm, and "settling" time for the head to settle into its new position once it is done being moved. (Ask me if you care why settling is needed or how it is actually done.) It is the motion time that part a is referring to as proportional to the square root of distance. The settling time is independent of distance. Therefore, part b's formula is the realistic one for the total seek time, including settling as well as motion. (Note that this formula only applies to seeks of one or more cylinders. A "seek" of zero cylinders is actually no seek at all, and takes zero time, because settling is not needed if there is no motion.) In part b, you are being asked to determine specific numeric values for the parameters x and y. Also, even this formula is not a realistic one for all distances of seeks: for long-distance seeks, the arm accelerates to a maximum speed, then "cruises" at that maximum speed for a while, then decelerates back to a stop. However, we will ignore the complication introduced by the maximum cruising speed and use the book's formula.
As further clarification, let us use the following names:
d = the distance covered while accelerating
t = the time spent accelerating
L = the seek distance
T = the time spent accelerating and decelerating
t' = the total time spent, including settling

The equation in part a is consistent with these names; the d and t it talks about are those specified above. In addition to this equation relating d and t, you should be able to write two very simple equations, one relating d to L, and one relating t to T. Your goal in part a is to take those three equations and do some algebra to get an equation of the form
T = y L^1/2
where y is some constant that can be expressed in terms of the constant a.
The equation in part b is not consistent with the above names; what it calls t is really t'. The given equation is then
t' = x + y L^1/2
which makes sense, because it is saying that the total time, t' is a constant settling time, x, plus the acceleration and deceleration time, T. Your job is now, given two specific pairs of numerical values for t' and L, to find out what numerical values x and y must have.

Chapter 14

Problem 14.x1: Page 481 mentions that the Internet originally used a file containing all hosts, but "as the Internet grew, ... it became untenable, so ... the domain name system (DNS) is now in use." By searching on the web, try to find out when the transition occurred, how large the host table was then, and how much larger it would now be. These seemingly simple questions may have more than one answer. Be sure to explain where yours came from, both in the sense of where you found them and how they were derived.

Chapter 15

Problem 15.x1: This homework is essentially a mini-lab, involving the socket model for how a network server can operate. (We'll do a full-sized lab using RMI.)
Versions of the Server.java, Connection.java, and Client.java files from Figures 15.2-15.4 are in the directory ~max/MC78/2002-Fall/src/chap15/sockets/. (These versions are the ones the authors have made available on their web site. They are not identical to the ones in the book, due to bug fixes.)
First, make sure you understand how to compile and run these programs by doing so. In particular, make sure you can use telnet to access the Server. (You can use the name "localhost" rather than 127.0.0.1, or can telnet using the actual hostname, even from another machine.) Next, modify the Connection.java file (and possibly also the Server.java file) so that the server no longer prints out the date and time, but instead does the following:
- First, the server prints out a message. For the first connection, that message is "First time." See below for what the message should be thereafter.
- Next, the server should read a line of input. Even though this will be in the server, you should see Client.java for an example of how a line of input can be read from an input stream gotten from a socket.
- Finally, the server should store the line of input away as the message to print out the next time it gets a connection. Then it should close the socket.
Your new server won't be usable with the java Client, just with telnet. Try your new server out. Run it, and then repeatedly telnet to it. (As before, you can do so from different machines, or on the same machine using localhost.) Make sure that each time it reports the line of input that was provided the previous time, except the "First time."

Chapter 17

Problem 17.x1: NFS (the Network File System) has various parameters the system administrator can set. One is the timeout time, that is the length of time the client should wait for a response from the server before retrying the request. First, suppose the connection to the server is very reliable, but the server is sometimes heavily loaded. Would you prefer a short timeout or a long one under these circumstances? Why? Now suppose instead that the connection is rather unreliable, but the server is generally lightly loaded. Would you now prefer a short timeout or a long one? Why?

Chapter 18

Problem 18.x1: Do problem 18.10 on page 589 with the following extensions. You may assume that objects do not contain access rights to other objects. Explain why this is relevant. Also, explain how problem 18.10 relates to the Unix/Linux file system.

Chapter 19

Problem 19.x1: Browse the CERT Coordination Center web site and The Risks Digest looking for descriptions of incidents reported in 2002 in which security was compromised. Pick a small number (1-3) of closely related ones that interest you and give a brief description of what happened, and what lessons you can learn from it. Be sure to cite your source, including which CERT publication(s) or issue(s) of The Risks Digest you drew your example(s) from, the date(s), and the author(s). If possible, read any underlying sources cited by CERT or The Risks Digest, and cite those too.

Instructor: Max Hailperin