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?
Last modified:
Sun Dec 2 19:57:59 CST 2012
by
bart