MCS-378 Homework (Fall 2001)

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 4.x1 below. These will be the reference numbers I use in reporting back your standing on the homework.

Note that I will add problems to this list from time to time, but unless I warn you otherwise, only by adding entire new chapters at the end. So if you check back, tell your browser to reload the page (in case it has an old version cached) and then look and see if there are any new chapters after what used to be the last chapter with problems

Chapter 4

Problem 4.x1: The file forker.c which is linked to the web version of this homework contains a simple program that loops three times, each time calling the fork system call described in section 4.3.1 of the textbook. Afterwards it sleeps (does nothing) for 30 seconds. Download this file, compile it using the command
```
cc -o forker forker.c
```
and then run it using the command
```
./forker
```
While the program is in its 30 second sleep, in a second terminal window do the command
```
ps x
```
to get a listing of processes. How many processes are shown running the ./forker command? Explain.
Problem 4.x2: Consider two variants of the program given in the textbook's Figure 4.8. In variant1, the line
```
printf("Child Complete");
```
has been removed. In variant2, both that line and also the preceding line
```
wait(NULL);
```
have been removed. Each of these variant programs is compiled and run in a shell terminal window. What difference might be observed between variant1's behavior and variant2's behavior? Explain. You are welcome to try the experiment if you would like.

Chapter 6

Problem 6.x1: Windows NT Workstation versions 3.x and 4.0 both provide some scheduling preference for the user's "foreground" application - the application with the window that is currently "in focus" (i.e., the window that would receive any keyboard input from the user). However, the nature of this scheduling preference was changed in NT 4.0 versus 3.x. (Windows 2000 retains the NT 4.0 approach. Since the change was between 3.x and 4.0, I'll refer to NT 4.0 below, but what you conclude about NT 4.0 is equally valid for Windows 2000.)
As background information, I'll summarize the scheduling algorithm used in both versions of NT. (This description is simplified, but gives the essential features.) The basic scheduling algorithm is a preemptive multilevel queue, with one queue for each priority level and round-robining among the processes at any one priority level. Under normal circumstances, all a user's processes will be at the same priority level (8, as it happens) and will use the same time quantum for round-robining (normally 30 milliseconds). Of course, a process may not run for its full time quantum - it can be preempted by an arriving higher-priority process, in which case it will get the remainder of its quantum when it resumes, or it can go into a waiting state before the quantum is up, in which case it gets a fresh quantum when it again becomes ready to run.
With this information as background, here is the difference between NT 3.x and 4.0: in 3.x, the foreground application gets boosted to a higher priority level, whereas in 4.0 it instead gets double the normal time quantum. (In 3.x it keeps the normal quantum and in 4.0 it keeps the normal priority.)
Explain what you would expect the user-visible results of this difference to be, and why. Specifically, answer each of the following questions, and explain your answers.
- Suppose the foreground process and background processes are all CPU-bound, that is, they run in the CPU as long as the OS allows them to, and need to do so for a considerable period of time. Does the foreground process progress faster or slower under 4.0 than under 3.x? How about the background processes: do they progress faster or slower under 4.0 than under 3.x?
- Now assume that the background processes are still CPU bound, but the foreground process is interactive. That is, it waits for input, spends some very short amount of CPU time responding to that input, and then waits again for the next input. Will the foreground process have a quicker or slower response time under 4.0 than under 3.x?

Chapter 7

Problem 7.x1: Explain why the notifyAll in Figure 7.36, page 214, can be safely changed to notify. Also, how can that code be changed to do fewer notifyAll or notify operations?
Problem 7.x2: Explain how the code in Figures 7.35-7.37, pages 213-215, can be changed to eliminate the dbReading instance variable.

Chapter 8

Do exercise 8.8 from page 249. (If this isn't challenging enough for you, you can do exercise 8.9 instead.)

Chapter 9

Problem 9.x1: Consider parallel parking along downtown streets. In some parts of town, there are white lines painted on the pavement, perpendicular to the curb and spaced at regular intervals. Each pair of consecutive lines marks one parking space. In other parts of town, there are no painted lines, and so each driver simply parks wherever there is room. Which kind of fragmentation is each part of town subject to? Explain, being sure to take into account what happens as parked cars leave and others take their place.

Chapter 10

Do exercise 10.9 from page 341. For part b, remember that a "bigger disk" doesn't normally mean a physically larger disk platter (e.g., a 5 inch platter instead of a 3 inch one). Instead, it means a larger capacity disk drive, which is often achieved by stacking more disk platters on the drive's spindle.
Do exercise 10.11 from page 342. If you find this tedious to do by hand, you might want to consider the alternative of writing a program.

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. How big does a file need to be before the triple indiect pointer gets used?

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

Do exercise 13.2 from page 458.
Do exercise 13.3 from pages 458-459. 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

Do problem 14.14 on page 499.

Chapter 15

Problem 15.x1: This howework 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/2001-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

Do problem 18.1 on page 588.

Chapter 19

Problem 19.x1: Browse The Risks Digest looking for descriptions of incidents 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 issue(s) of The Risks Digests you drew your example(s) from.

Instructor: Max Hailperin