KT11-B Paging Option

The KT11-B Paging Option is a memory management option for the PDP-11/20, produced by DEC's Computer Special Systems group; it can provide a "multi-user, machine-language timesharing environment".

It allows implementation of virtual memory; the address space is divided into pages, and when a reference it made to a page which is not 'resident' (i.e. present in physical main memory), the computation is stopped so the missing page can be made resident. It also allows the system to use up to 248 Kbytes of memory (the maximum allowed by the UNIBUS), although only a maximum of 64 KBytes is accessable (i.e. in the CPU's address space) at any one time.

Finally, hardware features prevent any user from interfering with the overall operation of the system. It does this by providing two modes for the CPU, 'User' and 'Exec', with certain operations (e.g. halting the machine) being dis-allowed in User mode.

By proper programming, the virtual memory (with separate address spaces for Exec and User mode) may be set up so that user processes cannot interfere with each other's memory, or the operating system's.

Additional features

Individual pages may be marked 'Private', which means that only access from code running in Private pages is allowed; i.e. information in such pages is hidden from code in 'Public' pages. This allows the use of proprietary software, while preventing it from being copied in an un-authorized manner.

Control may be transferred from code running in Public pages to Private pages only at 'entry points', locations which contain a particular instruction ("BR .+2").

Architecture

In both Exec and User mode, when the KT11-B is enabled, the address space is divided up into 128 virtual pages of 512 bytes each. Similarly, the potential 248 Kbytes of physical memory are divided into 496 physical pages, each of which can hold a page of virtual memory contents.

(In other words, pages of virtual memory cannot be assigned to arbitrary locations in physical memory, but must always be in blocks which start on 512 byte boundaries.)

Page maps, stored in main memory, provide mapping from virtual pages to physical pages; each map contains 128 entries (each one word long), one for each virtual page in the PDP-11's address space. (Note that a page holds 256 words, but the page map for a full PDP-11 address space only contains 128 page map entries, at one word each; this leaves the page which contains the page map half empty. This is important in a number of situations, below.)

Each page map entry contains a 9 bit physical page number in the low bits, and a 3 bit 'protection key' in the high bits. The protection key controls which types of access are allowed to that virtual page; bit 13 is Write Enable, bit 14 is Public, and bit 15 is Resident (the virtual page is currently contained in a physical memory page, i.e. the low bits of the entry are valid).

Two registers in the KT11-B contain the page numbers of the physical pages which hold the Exec and User page maps, respectively.

Details

Page 0 of Exec mode is not, however, located through the Exec mode page map (for reasons associated with caching page map entries, below). Instead, it is the page which the Exec mode page map register refers to; the Exec mode page map is stored in the high half of that page.

When a trap or interrupt happens in User mode, the saved PS and PC are not written to memory (as is normal on a PDP-11), but are instead stored in registers in the KT11-B. (This way, if the user has an invalid SP, e.g. an odd address, that cannot cause the trap/interrupt handling to fail.) A copy of the SP, garnered from looking at the bus address associated with the two writes, is also saved in a register. This is called a 'Modified Sequence', and it is used in many circumstances.

The Exec/User mode bit is not stored in the Processor Status word in the CPU, but in a register in the KT11-B.

Additional features

The KT11-B allows the upper part of the Exec mode address space to use page map entries that are stored in the same page of physical memory as the User mode page map, in the otherwise-unused upper half of the page; this is known as 'Exec-per-Process' mapping.

This allows the operating system to have a large amount of per-process data without either i) permanently dedicating scarce memory space in the Exec's address space to such data, or ii) having to change a number of page table entries in the Exec mode page map when changing processes. With Exec-per-Process pages, changing to a new User mode page map also automatically switches to the associated Exec-per-Process page map entries.

Similarly, User address space can be divided into two parts; 'simple' User address space in the lower part of the address space, and 'shared' User address space in the upper half, used for sharing code between two different users.

User page map entries for shared pages do not contain a page map entry (as described above); rather, they contain a 'shared entry pointer' (effectively an indirection to a shared page map entry): the low 9 bits contain a physical page number, and the high 7 bits contain the shared page map entry number. These entries also are stored in the otherwise-unused upper half of the page.

Implementation

The KT11-B is interposed between the KA11 CPU, and the rest of the system (memory and devices). There are two UNIBUSes, joined by the KT11-B; the UNIBUS from the CPU runs into the KT11-B, which processes UNIBUS cycles before passing them through to another UNIBUS, which holds all the memory, devices, etc.

The KA11 CPU of the -11/20 is also slightly modified, and a cable carries signals between the KA11 and KT11-B.

A page entry cache in the KT11-B (invisible to software) holds the 8 most-recently-used page table entries. (An option increases the size of the cache to 24 entries, which can reduce the amount of memory bandwidth 'wasted' on cache refills.) Cache entries are divided into an associative memory, 8 bits wide (7 bits of page number, and 1 Exec/User bit), and a scratchpad, 16 bits wide. Scrachpad entries hold page table entries; each associative memory entry contains the page number for the related scratchpad entry.

The cache is cleared whenever either page table register is modified; this is done by invalidating all cached entries by clearing the associative memories. Since the resulting all-zero's virtual page identifiers would match Exec mode, page 0, this is why that page is not handled through the Exec mode page map, but rather is handled directly.

Programming

The KT11-B is controlled by a bank of eleven registers:

Address	Name	Function
777572	KTWN	Window
777574	KTMR	Maintenance
777576	KTCS	Status and Control
777600	KTIC	Instruction Counter
777602	KTSP	Stack Pointer
777604	KTPC	Program Counter
777606	KTPS	Program Status
777610	KTAD	Address
777612	KTDT	Data
777614	KTUM	USER Map Control
777616	KTEM	EXEC Map Control

Note that these occupy the same locations as the standard PDP-11 Memory Management registers; 77757x are SSR0-2, and 7776xx are user PDRs.

The function of the important registers is given below.

KTCS

The KTCS controls the overall control and status of the KT11-B. The low two bits are a mode field:

• 00 - KT11-B disabled, system operates as a stock 11/20
• 01 - Destination only paging (for maintenance use only)
• 10 - Normal paging operation
• 11 - Start user

When 'Start user' mode is set, the next two bus data cycles are force-fed the contents of the KTPC and KTPS registers (below); the mode is then set to 'Normal paging'. This allows transfer of control to User mode: if the instruction after the one which sets 'Start User' mode in the KTCS is an RTI, the pair of bus 'jams' will load the CPU's PC and PS.

Bit 4 is the Exec/User mode bit; other bits contain information about the state of the KT11-B, and are frozen when a fault occurs, so that the operating system can see what kind of cycle provoked the fault.

KTUM and KTEM

The registers specify, in their lower 9 bits, the physical page number of the User and Exec page maps respectively. The upper 7 bits contain the boundary between the two kinds of pages in each mode: between normal Exec, and Exec-per-Process in the Exec mode register, and between ordinary and shared pages in the User mode register.

KTPC, KTPS and KTSP

These hold the copies of the PC, PS and SP saved during the Modified Sequence; the first two are also used during the transition from Exec mode to User (see above under KTCS).

KTIC

In normal operation (i.e., not during fault handling), this register is loaded with the address of each instruction fetch, or instruction vector, as they occur.

KTDT and KTAD

These registers hold the address and data of any memory cycle which causes a fault.

KTMR

In addition to various maintenance bits, this register also holds (in its low-order bits) the 'replacement counter', used to select a cache slot to reuse in cache refill operations. The counter is incremented on each cache refill operation; i.e. the newest cache entry goes into the cache slot which was filled the longest time ago.

KTWN

Memory operations to this register are performed through to the User mode address give in the KTAD; this allows the operating system to perform memory cycles just as code in User mode would, without needing to do a complex emulation.

Construction

The KT11-B is composed of a large number of single width FLIP CHIPs, most of them simple, generic ones; they are plugged into a custom wire-wrapped backplane.