Chapter 7, Device Management, Ida A. Flynn and Ann McIver McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Company (1993)

Lesson A: System Devices, Sequential Access Storage Media, Direct Access Storage Devices, Fixed-Head Drums and Disks, Movable-Head Drums and Disks, Optical Disk Storage, Access Time Required, Access Time for Fixed-Head Disks, Access Time for Movable-Head Devices

Problem 1.  What is the difference between buffering and blocking?

Buffering is the use of intermediate storage areas for temporary storage of data transiting between devices (which includes main memory). 

• The purpose of buffering are to permit asynchronous transmission and fetching of data.  
• Examples of buffering:  Memory banks have memory buffer registers to receive data extracted from a memory cell while waiting to be placed onto the system data bus.   Areas of main memory are often reserved as buffers for data transiting between main memory and storage or output devices.  More sophisticated systems permit Direct Memory Access by I/O Channels or I/O Device Controllers, depending on how the system is configured.

Blocking is act of grouping of one or more logical records into a physical record.   Deblocking is the act of parsing a physical record into one or more logical records. 

• The purposes of blocking and deblocking are to reduce internal fragmentation of clusters (or sectors, on systems not needing to implement clusters) and reduce the average time per logical record for storage operations.

Problem 2.  Given the following characteristics for a magnetic tape:

Since there are 8 data tracks, 1600 bits per inch per track gives us 1600 bytes per inch across all data tracks.  The linear density is 1600 bpi.  The area density is 1600 bytes per inch for data.  There is an additional track at 1600 bits per inch for a parity bit.

Find the following:

1. C = Number of blocks needed. C = R / B = 200,000 / 10 = 20,000 blocks.
2. E = Size of the block in bytes.   E = B * A = 10 * 160 = 1600 bytes / block
3. F = Time required to read one block.

   U = # bytes per inch = D * (8 tracks) * (1 byte / 8 bits) = 1600 bytes / inch

   J = # of inches of tape used per block = E / U = 1 inch / block

F = H + (J/S) + H

F = H_(start) + (J/S) + H_(stop)  = 3 ms + 5 ms + 3 ms = 11 ms

4. T = Time required to write all of the blocks.  T = F * C = 220,000 ms = 220 s = 3 m  40 s
5. V = Amount of tape used for data only, in inches.  V = J * C = 20,000 inches = 1666 ft  8 in
6. X = Total amount of tape used (data + IBGs), in inches = V + (C - 1) * G = 20,000 + 9,999.5 = 29,999.5 in = 2499 ft  11.5 in

The tape is not long enough.

Problem 3.  Given the following characteristics for a disk pack with 10 platters yielding 18 recordable surfaces:

The statement of this problem was flawed.  It was deleted from the required list.  With some modifications, it is still a good problem.

A number like 10 ms is a measure of time.  It can be a period of revolution.  It is not a speed.  Speed is velocity, which has units of measure of length / time for linear velocity or  angle / time for radial velocity.  Computer scientists, physicists, engineers, and psychologists all use the same standard units of measure.  You can find the legal English Language translation of the SI units of measure (written in French) at the web site for NIST.  See http://physics.nist.gov/cuu/Units/units.html at the National Institute of Standards and Technology (formerly, National Bureau of Standards).

We are not told details of how the disk is formatted.  In particular, we do not know the number of bytes per sector and number of sectors per track.

Find the following:

1. D = Number of blocks per track
   E = B * L = 1600 bytes / block
   The number of blocks per track must be an integer.  The INT function finds the integer part of a number.
   D  = INT( R / E ) = INT(11.875) = 11 blocks / track
2. F = Waste per track = R - D * E = (19000 bytes / track) - (11 blocks / track) * (1600 bytes / block) = 1400 bytes / track
   This is a wastage of about 7.4%.
3. H = Number of tracks required to store the entire file.
   G = Number of records per track = (11 blocks / track) * (10 records / block) = 110 records / track
   The CEIL operator is the Ceiling operator.  It is similar to the INT operator, except that it takes the next higher integer if the argument is not an exact integer.
   H = Number of tracks = CEIL[ N / G ] = 1819 tracks
4. J = Total waste to store the entire file = (H - 1) * F = 2,545,200 bytes / file
5. K = Time to write all of the blocks.  (Use period of revolution; ignore the time it takes to move to the next track.)
   Assume it takes one revolution to record one track.
   K = H * T = (1819 tracks) * (10 ms / track) = 18190 ms = 18.19 s
6. M = Time to write all of the records if they are not blocked.  (Use period of revolution; ignore the time it takes to move to the next track.)
   
   Assuming we treat the disk like a tape.  The total file is 32,000,000 bytes long, which easily can fit in a PC RAM.  We can declare a buffer to be the length of the track, and worry about parsing the file back into records when we reread the data.
7. In this case, we use CEIL(N * L / R) = 1685 tracks.  This is 4 surfaces.
   
   M = (N * L / R) * T = 16.842 s
   
8. P = Optimal blocking factor to minimize waste = INT(R / L) = 118 records / block
   The wastage is Q = R - P * L = 120 bytes / track
9. What would be the answer to (e) if the time it takes to move to the next track were 5 ms?
   Since we used 1819 tracks, we used tracks on 4 surfaces.  When we change surfaces, we do not need to move the arm to another track.  Assume also that we do not need to move the arm to position it to the first record in the file.
   U = K + (1819 - 4)* 5 ms = 18190 ms + 9075 ms = 27265 ms = 27.265 s
10. What would be the answer to (f) if the time it takes to move to the next track were 5 ms?
    In this
    V = M + [CEIL(N * L / R) - 4] * 5 ms = 16842 ms + [1685 - 4] * 5 ms = 16842 + 8504 = 25247 ms = 25.247 s

Problem 6.  Would a drum be a better device than a disk when paging is used?  Why or why not?

Our text does not give enough information to make a decision.  Answer:  Use a disk.  Except in copiers, drums went out with punched cards, paper and metalic tape, and dinosaurs.  I was not able to find reference to drums on the internet except at computer history sites.  I also was not able to find a reference to bubble memory.

The real question should be to select between fixed and movable head secondary storage.   In a paging system, speed of  secondary storage access is a key in a paging device.

The answer is to use a fixed head device with a fast rotational speed.  The fixed head disk does not have to wait for the mechanical positioning of the read/ write head over the track, which is the huge time consumer on a disk drive with a movable head read/ write arm.  The tradeoff is that you cannot get the read heads as close together as you can create tracks on a disk.  You can compensate by having multiple sets of fixed read head arms that are offset, for a price (of course).  The moveable head disk drive merely adjusts the position of the head.

Look for people exploring applications of magnetoelectronic memories as they enter the marketplace in 2001 from Honeywell Corp.  See IEEE Spectrum, FEB 2000 and http://www.spectrum.ieee.org  Cost will certainly be a determining factor of what applications this technology will be used in.

Problem 8.  You are given a file of ten records (identified as A, B, C, ..., J) to be stored on a disk that holds ten records per track.   Once the file is stored, the records will be accessed sequentially:  A, B, C, ..., J.  It takes 2 ms to process [P] each record once it has been transferred into memory.  It takes 10 ms for the disk to complete one rotation, and therefore 1 ms to rotate for one record [r].  It takes 1 ms to transfer [T] the record from the disk to main memory.  Suppose you store the records in the order given:  A, B, C, ..., J.

Compute how long it will take to process all ten records.  Break you computation into:

• Time to transfer a record [T] 
• time to process a record [P] , and
• time to access the next record [r].

I changed "drum" to "disk".  (Hardware failure; couldn't find replacement parts.)  Assume that the records are already stored on the disk. This is inconsistent with the first sentence of the problem, but consistent with the questions.  We are not told whether the logical records are stored in individual sectors on a single disk track or blocked as one collective physical record.  Assume the worst case that our buffer holds only one record at a time, and we only have one buffer.  Assume the program does not ask for one record until it has completed processing the previous record.  Assume the disk read head is position over the first record when the problem starts.

a.  In the worst case, the system does not request a subsequent record until it completes processing of the current record.  The disk continues to rotate, and is past the subsequent record when ready to request its input.  The disk must complete its rotation to reposition for transmitting the subsequent record.  Each block above represents 1 ms of time.  From the start of reading one record until the start of reading the subsequent record is 11 ms.  From the start of reading the last record until the last record has completed processing is 3 ms.  The total time from starting to read the first record until the tenth record has completed processing is 102 ms.

• total time to transfer records = 10 ms
• total time processing records = 20 ms
• total time waiting to access the next record = 70 ms

b.  In the best case, read the whole track into a buffer all at once and deblock from the buffer as you need records.  With this strategy, the total time from starting to read the first record until the tenth record has completed processing is 30 ms.

• total time to transfer records = 10 ms
• total time processing records = 20 ms
• total time waiting to access the next record = 0 ms

Problem 9.  Given the same situation described in Problem 8:

1. Organize the records so that they are stored in nonsequential order (not A, B, C, ..., J) to reduce the time it takes to process them sequentially.
2. Compute how long it will take to process all ten records using this new order.  

The total time is 30 ms.

Break you computation into: 

• total time to transfer records = 10 ms
• total time processing records = 20 ms
• total time waiting to access the next record = 0 ms

If you have 3 processors, you can overlap the work.  The total time is 12 ms.