UNIVERSITY OF WISCONSIN-MADISON Computer Sciences Department CS 537 Fall 2012 Barton Miller Problem Set #3

## Problem 1

A particular disk has 64K cylinders, 16 tracks (surfaces) per cylinder, and 1K sectors per track. Cylinders are numbered from 0 (on the outside edge of the disk) to 65535 (on the inside). The disk revolves at 10,000 RPM, once every 6 milliseconds; disks are always spinning. Arm movement costs 1 milliseconds plus one-tenth (0.1) millisecond for each cylinder that the arm is moved. A disk request [c,t,s] is for the sector on cylinder c, track t, sector s. The following requests are in the disk queue:
 1: [70, 5, 5] 4: [40, 4, 3] 2: [11, 10, 6] 5: [11, 10, 5] 3: [99, 7, 6] 6: [90, 7, 18]
The arm is currently over cylinder 20, and the beginning of sector 0 is under the read head.
• How long will it take to complete all the I/O's in the queue if the service discipline is FCFS?
• How long will it take to complete all the I/O's in the queue if the service discipline is SSTF? In what order will the requests be performed? (for SSTF, make your decision based only on shortest seek time - ignoring rotational latency)
• How long will it take to complete all the I/O's in the queue if the service discipline is LOOK and the arm is currently moving toward higher cylinder numbers? In what order will the requests be performed?

## Problem 2.

In general, it takes many disk reads to find the descriptor for a file.
• How many blocks will have to be read from disk in UNIX (the version described in sections 27 and 29 of the Lecture Notes) to locate the descriptor for a file named /a/b/c? Assume that the first data block of the root directory is present in memory at the beginning of the operation, but none of the other relevant disk blocks is in main memory. You can also assume that all directory files are one (1) block long. Indicate what each disk operation is used for.
• How might your numbers change if the directory files are larger than one block?

## Problem 3.

When an operating system crashes, it often leaves the data that it stores on the disk in an inconsistent state. By inconsistent state, we mean that file system data structures do not correctly describe what should be in the files, directories, descriptors, and free lists. This can happen because it takes several disk reads and writes to update a file, its descriptors, and the free list. When the system comes up, it is necessary to validate that the file system and its data structures are all right (or figure out how to fix them).
• With an allocation scheme based on block pointers and a free block list (such as that used in UNIX), is it possible to tell, after a crash, if a given block that is on the free list should not be? If so, how? If not, why not?
• With an allocation scheme based on block groups and a free block bit map (such as that used in DEMOS), is it possible to tell, after a crash, if a block that is marked ``free'' in the bit-map should not be? If so, how? If not, why not?
• Suppose we know that a disk block appears both in the free list/map and in a file. Is there some action we could safely take? (I.e., we do not want to make matters any worse, and would like to make them better). If so, what? If not, why not?
• Suppose we know that a disk block appears in two files at the same time. Is there some action we could safely take? If so, what? If not, why not?