Homework 11 Solutions

22C:116, Fall 2000

Problems from the text:

Do problems 7, 11 and 21 from pages 505 and 506 of the text.

7.

Independent implementations of Ricart and Argawala's algorithm can clearly be used for the two critical regions, just as two semaphores could be used on a uniprocessor. The resulting system is just as prone to deadlock as the result would be with two semaphores.

11.

There are several reasons: The part of the tape not currently over the record-playback head is well protected from data loss. In contrast, because the disk spins and the heads move, use of a magnetic disk to emulate a tape cannot guarantee that a failure will only damage the block currently scheduled to be written. Consider, for example, the consequences of a failure that causes the heads to move during a write operation.

The demand for real-time on-line inventory information makes it very desirable to maintain an up-to-date inventory database instead of only performing updates on a daily basis. The scheme outlined was generally used in an era when people worked from inventory reports that were printed out daily, and people were willing to live with the discrepancy between what is in their printout and what is found on the shelf.

21.

Resetting the world is impossible whenever an action is taken that cannot be undone. Holes cannot be undrilled, wires cannot be uncut, people cannot be forced to forget what was undone. Consider what happens when you abort a user transaction at a voting machine. The user may walk away in disgust. The user may try again, but not vote the same way as he originally intended.

Do problems 1 and 6 from pages 547 of the text. Problem 6 is relevant to the problem of writing a thread manager for classic UNIX systems (those that predate the addition of the select() system call).

1.
if 2/3 of the requests take 15 ms and 1/3 take 75+15 ms, we can ammortize this as 15+25 ms on average, or 40 ms per request on a single-threaded server. This comes to 25 requests per second. On a multithreaded server, assuming thread creation is free, note that we can overlap disk I/O with the processing of requests that do not involve disk I/O, but disk operations must be serialized. So, each request uses, on average, 25 ms of disk I/O time, and we can handle 40 such requests per second. The 15 ms of compute time taken per request is overlapped with this disk I/O. request processing, so the bottleneck is the time taken by disk opera

6.
If, as in UNIX, alarm clock signals terminate blocked read operations, you can test a file descriptor to see if it has pending input with the following algorithm:

	set alarm for a very short interval
	c = read(f,buf,len)
	if (c == 0) we conclude that no input was available from f