Sector Interleave

[Paul Koning]

> On Nov 30, 2015, at 8:39 PM, Johnny Billquist <bqt at update.uu.se> wrote:
> 
> On 2015-12-01 02:19, Paul Koning wrote:
>> 
>>> On Nov 30, 2015, at 8:12 PM, Johnny Billquist <bqt at Update.UU.SE> wrote:
>>> 
>>> ...
>>> DECtape never did interleaving that I know of.
>> 
>> Sure it does.  The DOS format, which was adopted by RSTS, has 4 way interleaving.  If you write a 500 block file, it writes every 4th block forward, then fills in one set of gaps reverse, then forward and backward again, resulting in finally all blocks used.
>> 
>> This is a software function, of course, and actually implemented in the file system, but it's certainly interleaving.  It doesn't apply to contiguous files (supported in DOS but not RSTS), which is why RSTS V4A sysgen with output to DECtape took so long -- writing a contiguous CIL file, in block order, madly seeking back & forth.
> 
> Oh. You mean that the software decided to use blocks 0,4,8,12,...
> 
> Yes, that would be doable. I was thinking of interleaving at the format level.
> 
> But such interleaving means the software have to keep rather good track of things...

True.  Interleaving, as described in this thread, is typically a software function; the software uses the blocks in an order different from the "ascending by 1" natural ordering.

I suppose it's possible to do something like interleaving where consecutive sector addresses are not physically adjacent on the media.  Come to think of it, that's exactly what the MSCP RX50 controllers do, since MSCP implements the mapping from LBA to physical addresses in the controller, not the host.  But in older systems where the controllers handle physical addresses and the mapping from LBA is in the driver, interleave is handled there (or above).

The CDC 844 controller (which handles drives that look like the RP04 or RP06) had a command to set 1:1 or 2:1 interleave.  The reason is that it would allow reading or writing several sectors without an intervening "seek" command.  Depending on the selected mode, the current sector address would advance by 1 or by 2 at the end of the operation (and, in the case of 2:1, wrap at track end the first time around).  That's the only case I have seen of interleave support in pre-MSCP controllers.

On the subject of DECtape, and "keeping good track of things" -- DOS format DECtape has 510 bytes per tape block, the other two bytes are used as the link word.  It's a bit like MSDOS FAT format (or CDC 6000 series, which did it 20 years earlier), but with the links in the blocks rather than in a separate region.  The directory points to the first block, and you get the next block address when you read the first.  Yes, that means no random access supported; in DOS, if you needed random access you were required to use a contiguous file, in which all 512 bytes per block are payload.

The interleaving is simply a side effect of the block allocation algorithm: when looking for the next block to allocate, it would start looking at current + 4 or current - 4 (depending on the direction for this block).   So starting from an empty tape you'd get a regular layout, but if there were already some allocated blocks you might get larger skips, and on a very nearly full tape possibly a smaller skip.

A very odd interleave shows up in the THE operating system for the Electrologica EL-X8 by Dijkstra, in its addressing for the paging drum.  That device is word addressable (think of an RF11, but somewhat larger: 512k 27-bit words).  The start word address of sector n is given by (n * 1025) mod 512k.  I assume that's done for the usual reasons interleaving is used, but while the formula is nicely spelled out in the literature, no explanation is given for why it was used.

	paul