Notes 5 --- Blocking and Buffering

Idea behind buffering:

• Data organization:
  • Secondary memory is expressed in bytes, and secondary memory devices tend to be block-oriented --- all of a block is read or written at once.
  • Main memory is expressed in bits, and byte- or word-oriented (a difference in size typically of order 10^3).
  • File processing tends to be record-oriented, and record and block size are typically incommensurate.
  • Also, as we have seen, each file operation tends to be much slower than even main memory operations (by a factor of 10^3 or even 10^6), and even more so by contrast to CPU instructions.
• The file buffer mechanism:
  • handles the conversion.
  • allows a sequence of accesses to secondary memory to be carried out without needing to interrupt computer internal operations.
• In the read direction, it:
  • Takes a block from secondary memory.
  • Feeds the contents one word at a time (typically in groups corresponding to records) to main memory.
  • This raises a flag analogous to the "Memory Function Complete" from Architecture.
• In the write direction, the buffer mechanism:
  • Accepts input from the CPU.
  • Sets a flag inhibiting other write operations to the same device.
  • Eventually writes the (typically full) buffer to secondary memory.
  • When this is finished, a flag is reset to allow any conflicting memory operation to proceed.

Channels:

What really happens:

• In the write direction, data is fed from the buffer to the accumulator register of the device, which may then write them one byte at a time to secondary memory.
• Likewise, in the read direction, secondary memory is read one byte at a time from the medium, accumulated in the accumulator register, and then read as a word to the buffer.
• The channel deblocks the sequence of bytes into words (and conceptually into records), and may actually perform some transformation (for example, of offsets into pointers).
• The channel is under CPU control, but the CPU in general only invokes a channel program. Channel commands include:
  • move device (typically, its read-write heads) to a given location.
  • cause a read of a block from secondary storage into main memory.
  • cause a write of a block from main memory into secondary storage.
  • in some cases, may be able to read or write backwards.
  • read several blocks in sequence, or skip blocks (chain computations).
  • sense self, device, and buffer status (and use results in conditional execution).
  • operate on device drive unit.
  • do very simple control flow (based on status and interrupts).
  • raise interrupts to the CPU when exceptions or errors are detected.
  • halt on a halt instruction (returning MFC to the CPU) or a CPU interrupt.

Idea behind blocking:

1. The time spent in actual transfer of data is typically a small portion of access time, and most of the rest is essentially constant in the amount of data to be transferred.
2. Instead of on each operation transferring a byte from the middle of some record, operations will deal with semantically meaningful units of data (e.g., a record).
3. As with memory functions in Architecture, a certain amount of bookkeeping and other processing can occur during secondary memory accesses.
4. If we can use two buffers for a file, one can be used in processing while the other participates in a secondary memory operation.

Opening and closing files --- buffers:

• The symbol table entry is used at compile-time (or in the interpreter) to convert file access into access to the file_handle, buffer, and file_pointer.
• file_pointer is the location of the next block to be read/written.
• type_length and blocking_factor allow for blocking and buffering.

1. Delete the symbol table entry.
2. Dispose the data associated with the file handle, or mark it as invalid.
3. Make the file handle available again.
4. Free the space associated with the buffer.
5. Delete the file pointer (not necessarily in this order).

Choosing a blocking factor:

1. record size.
2. the amount of space available for the buffer.
3. the size of blocks, sectors, or tracks on the secondary memory device.
4. the file organization and the distribution of activity in the file.
5. processing time versus I/O time.
1. (0) and (1) are obvious, since the question of how many objects fit in a sack should take account not just of the size of the sack, but also the sizes of the objects; the value for (0) also tends to be exactly or approximately available. If record size is, say 411 bytes, and buffer space is 16384 bytes, then blocking factor can't be more than

                    floor ( 16384/411 ) = 39.

• If double buffering is to be used, available size has to be halved before the computation.
• (Note this neglects any overhead needed for the buffer; otherwise, the blocking factor for double buffering might be a little smaller.)
• The amount of free buffer space typically needs to be determined with the help of the operating system.
• For (2), typically we would like to have read and write operations deal with physically useful quantities. If we know the parameters of a device, we can modify the blocking factor (downward) so it always reads exactly one block, or two blocks, or a quarter-track, or a track, etc.
  • Note that this is a problem mostly for disks, drums, and related technologies, and not for tapes, where the block size is rarely if ever fixed a priori.

Time and blocking factor:

• Access time per block has a high constant part, and a relatively small dependence on blocking factor; processing time is approximately linear in blocking factor, with a small constant term (or none), so the two curves will cross at somewhere in the first quadrant (blocking factor vs. time), although not necessarily at a point feasible for the constraints discussed above; ideally, we would like to use this BF, or as close to it as is legal.
• A high variability in either processing time (typical) or access time (less likely) will result in less parallelism (why?).

For indexed sequential files, and those random access files which maintain key order, things are a little more complicated. In addition to the search tradeoff, there is an issue of locality of activity: the more likely consecutive requests are to refer to nearby records, the more payoff from a high blocking factor.

Degree of buffering:

• Typically, a file will be assigned a single buffer when it is opened.
• For large files in which both I/O and processing time can be expected also to be large, it makes sense to assign double buffers so one buffer's contents can be processed while the other participates in file I/O (that is, processing and I/O can occur in parallel).
  • If processing requirements are very high, it may even make sense to assign multiple buffers. This may also make sense if processing times (or, less frequently, access times) vary quite a bit.

Buffer pools:

In such cases, the operating system or the language environment may maintain a pool of available buffers (actually, chunks of buffer space), and use a policy to intercept and partially satisfy requests for additional buffers. If later, other buffers are freed, some of the buffers which could not be provided originally can be assigned to the file.