Apart from being stack- and tag-based, another notable architectural feature of the B5000 is that it is descriptor-based. Descriptors are the means of having data that does not reside on the stack as for arrays and objects. Descriptors are also used for string data as in compilers and commercial applications. Descriptors describe data blocks. Each descriptor contains a 20-bit address field referencing the data block. Each block has a length which is stored in the descriptor, also 20 bits. The size of the data is also given, being 4-, 6-, 8- or 48-bit data in a three bit field.

The various status bits are

Bit 47 — The presence bit (P-Bit)
Bit 46 — The copy bit
Bit 45 — The indexed bit
Bit 44 — The paged bit
Bit 43 — The read only bit

Bit 47 is probably the most interesting bit in the system – it was the way the B5000 implemented virtual memory. Virtual memory was originally developed for the Atlas project at the University of Manchester in the late 1950s. Keen to see this used in commercial applications, they invited engineers from several computer companies to a seminar, including those from Burroughs and IBM. The Burroughs engineers saw the significance of virtual memory and put it into the B5000. The IBM engineers weren't interested and IBM did not "invent" virtual memory for another ten years.

When a descriptor was referenced, the hardware checked bit 47. If it were 1, the data was present in memory at the location indicated in the address field. If bit 47 were 0, the data block was not present and an interrupt (p-bit interrupt) was raised and MCP code entered to make the block present. In this case, if the address field were 0, the data block had not been allocated (init p-bit) and the MCP would search for a free block the size of which was given in the length field. Note that in ALGOL, the bounds of an array were completely dynamic, could be taken from values computed at run time, which was unlike Pascal where the size of arrays was fixed at compile time. This was the main weakness of Pascal as defined in its standard, but which was removed in many commercial implementations of Pascal, notably the Burroughs implementations (both the University of Tasmania version by Arthur Sale and Roy Freak, and the Burroughs Slice implementation by Matt Miller et al.)

Note that in a program, an array was not allocated when it was declared, but only where it was touched for the first time – thus arrays could be declared and the overhead of allocating them was avoided if they weren't used.

Also note that low-level memory allocation system calls such as the malloc class of calls of C and Unix are not needed – arrays are automatically allocated as used. This saves the programmer the great burden of filling programs with the error-prone activity of memory management.

When porting programs in lower-level languages such as C, the C memory structure is dealt with by doing its own memory allocation within a large allocated B5000 block – thus the security of the rest of the B5000 system cannot be compromised by errant C programs. In fact, many buffer overruns in apparently otherwise running C programs have been caught when ported to the B5000 architecture. C, like Pascal, was also implemented using the Slice compiler system (using a common code generator and optimizer for all languages). The C compiler, run-time system, POSIX interfaces, as well as a port of many Unix tools was done by Steve Bartels. An Eiffel compiler was also developed using Slice.

For object-oriented programs which require more dynamic creation of objects than the B5000 architecture, objects are best allocated within a single B5000 block. Such object allocation is higher level than C's malloc and is best implemented with a modern efficient garbage collector.

The last p-bit scenario is when bit 47 is 0, indicating that the data is not in memory, but the address is non-zero, indicating that the data has been allocated and in this case the address represents a disk address in the virtual memory area on disk. In this case a p-bit interrupt is raised and it is noted as an 'other' p-bit.

Thus the B5000 had a virtual memory system integrated into the hardware – a virtual memory system that has to this day been unsurpassed, since all other systems must build virtual memory on top of lower-level hardware. ALGOL and the B5000 also represented a significant advance on the low-level, error-prone, and programmer intensive 'malloc' mechanisms of later systems.

You may have noted that the address field in the B5000 was only 20 bits which meant that only 1 Meg words (6MB) of memory could be addressed by descriptors. This was a significant restriction on the Bnm00 range of machines. With the advent of the A Series in the early 1980s, the meaning of this field was changed to contain the address of a master descriptor, which meant that 1 Meg data blocks could be allocated, but that the machine memory could be greatly expanded to gigabytes or perhaps terabytes.

Another significant advantage was realized for virtual memory. In the B5000 design, if a data block were rolled out, all descriptors referencing that block needed to be found in order to update the presence bit and address. With the master descriptor, only the presence bit in the master descriptor needs changing. Also the MCP can move blocks around in memory for compaction and only needs to change the address in the master descriptor.

Another difference between the B5000 and most other systems is that other systems mainly used paged virtual memory, that is pages are swapped out is fixed-sized chunks regardless of the structure of the information in them. B5000 virtual memory works with varying-size segments as described by the descriptors.

When the memory is filled to a certain capacity, an OS process called the 'Working Set Sheriff' is invoked to either compact memory or start moving segments out of memory. It chooses code segments first, since these cannot change and can be reloaded from the original in the code file, so do not need writing out, and then data segments which are written out to the virtual memory file.

P-bit interrupts are also useful to measure system performance. For first-time allocations, 'init p-bits' indicate a potential performance problem in a program, for example if a procedure allocating an array is continually called. Reloading blocks from virtual memory on disk can significantly degrade system performance and is not the fault of any specific task. Many of today's computer users are familiar with the fact that adding memory can improve system performance, and this is why. On B5000 machines, 'other p-bits' indicate a system problem, which can be solved either by better balancing the computing load across the day, or by adding more memory.

Thus the high-level architecture of B5000 machines helps optimization of both individual tasks and the system as a whole.

The last and maybe most important point to note about descriptors is how they affect the complementary notions of system security and program correctness. One of the best tools a hacker has against the wide-spread operating systems of today is the buffer overflow. This is particularly easily done in C and with a little more effort in assemblers. C, in particular, uses the most primitive and error-prone way to mark the end of strings, using a null byte as an end-of-string sentinel in the data stream itself.

Pointers are implemented on the B5000 by indexed descriptors. During data scanning and transfer operations, pointers are checked at each increment to make sure that neither the source not the destination blocks are overflowed. Thus a significant source of program errors can be detected early before software goes into production, and a more significant class of attacks on system security is not possible.

See also

B5000