Homework #7 Solution

Assignment: Problems 13.8, 14.2, 14.9

Problem 13.8

How does DMA increase system concurrency? How does it complicate the hardware design?

DMA increases system concurrency by freeing the CPU to perform other tasks while it handles data transfer to/from the disk.

The hardware design of a system with DMA is complicated because a special DMA controlled must be integrated into the system so that DMA and normal CPU operations can coexist.

 

Problem 14.2

Suppose that a disk drive has 5,000 cylinders. The drive is currently serving a request at cylinder 143 and the previous request was at cylinder 125. The queue of pending requests is:

86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130

What is the distance to satisfy these requests using the following algorithms?

a) FCFS

The FCFS algorithm just follows the order of the requests given.

The FCFS schedule is:

143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130

The total distance is: 7,081

 

b) SSTF

The SSTF algorithm starts a cylinder 143 and from there successively selects the shortest request from its current location.

The SSTF schedule is: 

143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774

The total distance is: 1,745

 

c) SCAN

The SCAN algorithm continues in the direction of the head servicing requests until the end of the disk. It then reverses, catching all requests back to the other end of the disk. The head continuously scans back and forth across the disk. 

The SCAN schedule is:

143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86

The total distance is: 9,769

 

d) LOOK

The LOOK algorithm is just like the SCAN algorithm, except the disk head only goes as far as the last request in each direction.

The LOOK schedule is:

143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86

The total distance is: 3,319

 

e) C-SCAN

The C-SCAN algorithm is similar to the SCAN algorithm, except that at the end of the disk, it returns all the way to the beginning before servicing more requests. In this fashion, it is more uniform, and the head motion is "circular"

The C-SCAN schedule is:

143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 0, 86, 130

The total distance is: 9,813

 

f) C-LOOK

The C-LOOK algorithm is a circular version of the LOOK algorithm. It doesn't scan on the way back to the beginning of the disk, rather operates in a circular fashion.

The C-LOOK schedule is:

143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130

The total distance is: 3,363

 

Problem 14.9

Explain why SSTF scheduling tends to favor the middle cylinders of a disk over the innermost and outermost cylinders.

The SSTF algorithm is biased toward the middle cylinders in much the same way the SCAN algorithm is. Since, in the SSTF algorithm, the closest cylinder is always chosen, then all middle cylinder references will serviced on the way to the end of the disk.

I present the book's answer to this question, even though I think it is more muddled... just FYI:

The center of the disk is the location having the smallest average distance to all other tracks. Thus the disk head tends to move away from the edges of the disk.

Here is another way to think of it. The current location of the head divides the cylinders into two groups. If the head is not in the center of the disk and a new request arrives, the new request is more likely to be in the group that includes the center of the disk; thus, the head is more likely to move in that direction.