Solutions Manual
Chapter 13
Section 13.1
Exercise 13.1.1
For this exercise we treat the sizes as if they were powers of 10 (i.e. petabyte is
1015). Results would be slightly different if powers of 2 were used (i.e. petabyte
is 250).
(a) Petabyte disk is 4000 times bigger than 250 gigabyte disk. Since log24000 ≈
(c) Terahertz processor is approximately 167 times faster than a 6 gigahertz
(2 cores, 3 gigahertz each) processor. Thus, there must be approximately
then the result would be equivalent (about 12 years).
2
(d) Year 2015 is 84 months from 2008, so there would be about 84
18 ≈5 dou-
Exercise 13.1.2
There would be 300 ·12
Section 13.2
Exercise 13.2.1
(a) Capacity of the disk is the product of 10 surfaces, times 100000 tracks,
times 1000 sectors, times 1024 bytes, or 1024 gigabytes, which is about 1
terabyte.
(b) The average number of sectors per track is 1000, and each sector is 1024
(c) The maximum seek time occurs when the head needs to move across all
(d) The maximum rotational latency would be a full rotation of the disk (e.g.
(f) Example 13.2 mentions that the average distance traveled by the head is
1
3of the way across the disk (Exercise 13.2.3 proves this). Therefore, the
which is 3 ms.
Exercise 13.2.2
The next request can be for a block on any cylinder with equal probability. There-
fore, the average number of cylinders the head will need to travel is the product
of the sum: 0 (if the request is for the block on cylinder 8192) +(1+2+…+8191)
Exercise 13.2.3
If the disk head is at cylinder 1, the average distance the head will move is
(1 +2+3+… +65535)
65536 . If the disk head is at cylinder 2, the average distance
the head will move is (1 +1+2+3+… +65534)
65536 and so on. We notice that the
one for each possible head position, and therefore, the average distance is
1
N
N
X
x=1 (x−1)(x)
2N
+(N−x)(N−x+1)
2N!=
For large N, this expression approaches N
3which is 1
3of the way across the disk.
Exercise 13.2.4
The inner track is shorter than the outer track by 1.75
0.75 =7
3. Thus, the probability
density function for the random sector position could be thought of as a trapezoid
with altitude 1 and bases band 3
7b. Since the area of this trapezoid must be 1,
Exercise 13.2.5
Since the disk controller postpones all other requests until the block is ready to
Case1 is when the block is small enough so that the modification takes less time
Case2 is when block is large (e.g. occupies most of the track). In this case even
the only delay between the start of read and start of write is 2 rotations.
Taking the worst case (case 2), the time to modify a block is then equals to: seek
time +rotational latency +2 rotations +transfer time (note that we do not explic-
13.2, it would take 6.46 +4.17 +2·8.33 +0.13 or 27.42 ms.
Section 13.3
Exercise 13.3.1
Cylinder of Request First time available
8000 0 +7+4.3 =11.3
Exercise 13.3.2
(a) Limiting the movement of the head to only the half of the cylinders im-
proves the average seek time. Which would be 1 +
65536
6
(c) Majority of requests may tend to come for the blocks located on the same
Exercise 13.3.3
(a) Assume there are nrequests for the pass. To perform one pass, the head
must travel across all tracks (65536), which would take about n+16.38 ms
(nstarts plus time to travel across all tracks). This is the seek time.
8
(b) The number of requests serviced in one pass is nfrom (a). Which is 16.38
(A−5.3).
(c) In the best case the request comes in right when the new pass is about to
start, so the waiting time would be 0. In the worst case, the request comes
in right after the pass has started, so the waiting time would be the time of a
Exercise 13.3.4
Since the throughput depends on the number of concurrent requests that the n
disks would be able to service, the problem could be reduced to finding the average
number of disks that would be servicing requests at one given time. We have n
disks, and each requests arrives for any of those disks at random. If the disk is
+(n−1) ·n−1
n·n−2
n·… ·2
n·n−1
n
+n·n−1
n·n−2
n·… ·1
n
Which is n
Exercise 13.3.5
Let the cylinder be a unit circle. Then the probability that a random block on the
Section 13.4
Exercise 13.4.1
(a) 1
Exercise 13.4.2
(a) 10
10
Exercise 13.4.3
8 hours is 1
1095 of the year. The probability that mirror disk will fail during the
Exercise 13.4.4
Hhours is H
8760 of the year.
(a) The probability of the data loss is a probability of one of the two disks
(b) In order for the data loss to occur, two additional disks must fail within
the Hhours of a first disk failure. The probability of first disk failure is
Exercise 13.4.5
Loss of data will occur when all three disks fail within Hhours. Probability of
the first disk failure is 3F. The probability of the rest two disk failing within H
Exercise 13.4.6
(a) 01010110
11
Exercise 13.4.7
(a) 01010110
Exercise 13.4.8
Only changes to the redundant disk needed to be made. The corresponding block
Exercise 13.4.9
(a) The blocks for the disks 5, 6, and 7 are: 10101111, 01111111, and 11101101
Exercise 13.4.10
Use the matrix in figure 13.10.
(a) Columns 1 and 7 differ in rows 1 and 2. Either row 1 or 2 can be used to
restore disk 1. We pick row 1, and so disk 1 is restored by taking modulo-2
12
Section 13.5
Exercise 13.5.1
(a) 15 (for CHAR) +2 (for INTEGER) +10 (for DATE) +8 (for TIME) =35
bytes.
Exercise 13.5.2
(a) 8 (for REAL) +17 (for CHAR) +1 (for BYTE) +10 (for DATE) =36
bytes.
Exercise 13.5.3
(a) 4 (for pointer) +4 (for pointer) +1 (for CHAR) +35 (for the data, from
13.5.1 (a)) =44 bytes.
Exercise 13.5.4
(a) 8 (for pointer) +10·2 (for integers) +36 (for the data, from 13.5.2 (a)) =64
bytes.
Section 13.6
Exercise 13.6.1
Megatron 747 disk has 216 tracks per surface and, thus, we need 2 bytes to address
Exercise 13.6.2
Exercise 13.6.3
(a) We would need the same size of 4 bytes for addressing the block. In addi-
tion, we would need to address any byte within the block. If we assume, as
Exercise 13.6.4
Exercise 13.6.5
Exercise 13.6.6
Each entry of the table occupies 4 bytes for physical address (see exercise 13.6.1),
plus k bytes for a logical address. Logical address has to be long enough to address
Exercise 13.6.7
On the first day no deletes occur, so 2(100 +2) =204 bytes are added to the block.
Exercise 13.6.8
Suppose it takes time tto swizzle a pointer. Further suppose we have npointers
Exercise 13.6.9
If we use no-swizzling, the total performance cost is np(k·10) =10npk. If we use
swizzling, the cost is np(((k−1) ·1) +30) =np(k+29). Elimination the common
term nfrom all three formulas, we get:
10pk vs. 20 +pk vs. p(k+29).
Section 13.7
Exercise 13.7.1
Exercise 13.7.2
We get 42 (from 13.7.1) +30 (average for the name) +50 (average for the address)
Exercise 13.7.3
(a)
(b)
other header information
record length
16
other header information
??
Exercise 13.7.4
This question is open to interpretation. There could be a large number of different
tests and each test could be taken by a patient many times. Therefore, the number
of test result fields can be unbounded, and it is not clear how to abtain the answers
based on the given data.
(a) Assume there are npossible test result values. The expected number of test
(c) If we pre-allocate space in the record for k, we will have to use 4 bytes for
a pointer plus 40kbytes, plus 4 bytes to a pointer to another block (or chain
of blocks). This does not seem to provide us much advantage in terms of
17
Exercise 13.7.5
Exercise 13.7.6
Assuming worst case, we need 17.38+8.33 =25.71 ms to position to the right
block to read. With 100 ms delay, this leaves 74.29 ms to read the data (to buffer
it in main memory). Thus, we can read a full 8 tracks of the cylinder and still have
7.65 ms left to read about 235 sectors. To simplify, we can assume we will read
Section 13.8
Exercise 13.8.8
1. Performance
2. Better disk space (and main memory) utilization
•Often, varying-length tuples require allocation of storage big enough
3. Simpler processing (algorithms)
18
