Homework 3 solution

Explain the difference between internal and external fragmentation for segmentation/paging
and allocation of files on disk.


Segmentation:  Segments are of variable size, the allocation is dynamic. When all blocks of free memory are too small to accommodate a segment, it results in external fragmentation.

Paging: Memory is allocated in fixed-sized unit (page frames), when the request is smaller than page size or can not be evenly divided by page size, at least part of one page (the last page) won't be used by the requester and unavailable for use by others, which is internal fragmentation.

Allocation of files on disk:
If following contiguous allocation method, as files are allocated and deleted, the free disk space will be broken into chunks and suffer from external fragmentation when the largest contiguous chunk is not sufficient for a request.

In case of linked allocation and indexed allocation, file blocks need not to be contiguous but they are allocated in unit of blocks, so internal fragmentation would still possibaly happen.

11.7 Explain the purpose of the open and close operations.

Answer:   The open operation informs the system that the named file is about to become active.   The close operation informs the system that the named file is no longer in active use by the user who issued the close operation.

12.1 Consider a file currently consisting of 100 blocks. Assume that the file control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory.

    a. The block is added at the beginning.
    b. The block is added in the middle.
    c. The block is added at the end.
    d. The block is removed from the beginning.
    e. The block is removed from the middle.
    f. The block is removed from the end.

                        Contiguous         Linked             Indexed
                      a. 201                         1                        1
                      b. 101                         52                      1
                      c.  1                            3                        1
                      d. 198                         1                        0
                      e. 98                           52                      0
                      f. 0                             100                     0

12.5 Consider a system that supports the strategies of contiguous, linked, and indexed allo-cation. What criteria should be used in deciding which strategy is best utilized for a particular file?

            Contiguous --  if file is usually accessed sequentially, if file is relatively small.
            Linked --  if file is large and usually accessed sequentially.
            Indexed  -- if file is large and usually accessed randomly.

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

Answer: DMA increases system concurrency by allowing the CPU to perform tasks while the DMA system transfers data via the system and memory busses. Hardware design is compli-cated because the DMA controller must be integrated into the system, and the system must allow the DMA controller to be a bus master. Cycle stealing may also be necessary to allow the CPU and DMA controller to share use of the memory bus.

14.2 Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is
            86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130
Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?



a. The FCFS schedule is 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130. The total seek distance is 7081.
b. The SSTF schedule is 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774. The total seek distance is 1745.
c. The SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86. The total seek distance is 9769.
d. The LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86. The total seek distance is 3319.
e. The C-SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 86, 130. The total seek distance is 9813.
f. (Bonus.) The C-LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130. The total seek distance is 3363.

14.17 The term  fast wide SCSI-II  denotes a SCSI bus that operates at a data rate of 20 megabytes per second when it moves a packet of bytes between the host and a device. Suppose that a fastwideSCSI-II disk drive spins at 7200 RPM, has a sector size of 512 bytes, and holds 160 sectors per track.

a. Estimate the sustained transfer rate of this drive in megabytes per second.
b. Suppose that the drive has 7000 cylinders, 20 tracks per cylinder, a head switch time
(from one platter to another) of 0.5 millisecond, and an adjacent cylinder seek time
of 2 milliseconds. Use this additional information to give an accurate estimate of the
sustained transfer rate for a huge transfer.
c. Suppose that the average seek time for the drive is 8 milliseconds. Estimate the I/Os
per second and the effective transfer rate for a random-access workload that reads
individual sectors that are scattered across the disk.
d. Calculate the random-access I/Os per second and transfer rate for I/O sizes of 4
kilobytes, 8 kilobytes, and 64 kilobytes.
e. If multiple requests are in the queue, a scheduling algorithm such as SCAN should
be able to reduce the average seek distance. Suppose that a random-access work-load
is reading 8-kilobyte pages, the average queue length is 10, and the scheduling
algorithm reduces the average seek time to 3 milliseconds. Now calculate the I/Os
per second and the effective transfer rate of the drive.


a. The disk spins 120 times per second, and each spin transfers a track of 80 KB. Thus, the sustained transfer rate can be approximated as 9600 KB/s.

b. Suppose that 100 cylinders is a huge transfer. The transfer rate is total bytes divided by total time. Bytes: 100 cyl * 20 trk/cyl * 80 KB/trk, i.e., 160,000 KB. Time: rotation time + track switch time + cylinder switch time. Rotation time is 2000 trks / 120 trks per sec, i.e., 16.667 s. Track switch time is 19 switch per cyl * 100 cyl * 0.5 ms, i.e., 950 ms. Cylinder switch time is 99 * 2 ms, i.e., 198 ms. Thus, the total time is 16.667 + 0.950 + 0.198, i.e., 17.815 s. (We are ignoring any initial seek and rotational latency, which might add about 12 ms to the schedule, i.e. 0.1%.) Thus the transfer rate is 8981.2 KB/s. The overhead of track and cylinder switching is about 6.5%.

c. The time per transfer is 8 ms to seek + 4.167 ms average rotational latency + 0.052 ms (calculated from 1 / (120 trk per second * 160 sector per trk)) to rotate one sec-tor past the disk head during reading. We calculate the transfers per second as 1/(0.012219), i.e., 81.8. Since each transfer is 0.5 KB, the transfer rate is 40.9 KB/s.

d. We ignore track and cylinder crossings for simplicity. For reads of size 4 KB, 8 KB, and 64 KB, the corresponding I/Os per second are calculated from the seek, rota-tional latency, and rotational transfer time as in the previous item, giving (respec-tively) 1/(0.0126), 1/(0.013), and 1/(0.019). Thus we get 79.4, 76.9, and 52.6 transfers per second, respectively. Transfer rates are obtained from 4, 8, and 64 times these I/O rates, giving 318 KB/s, 615 KB/s, and 3366 KB/s, respectively.

e. From 1/(3+4.167+0.83) we obtain 125 I/Os persecond.From8KBperI/O we obtain 1000 KB/s.