KT11-B Paging Option

The KT11-B Paging Option is an 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 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. It also 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 while the missing page is made resident.

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, map from virtual pages to physical pages; each map contains 128 entries, one for each virtual page in the PDP-11's address space. Two registers contain the number of the physical pages which holds the Exec and User page maps, respectively.

(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, leaving the page which contains the page map half empty. This is important in a number of places, 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).

Page 0 of Exec mode is not, however, located through the Exec mode page map; rather, it is the page which the Exec mode register points to, and 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, along with a copy of the SP, which is garnered from looking at the bus address associated with the two writes. (This way, if the user has an invalid SP, e.g. an odd address, that cannot cause the trap/interrupt handling to fail.) This is called a 'Modified Sequence'.

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 map when changing processes. With Exec-per-Process pages, changing to a new User mode page map also automatically also 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': the low 9 bits contain a physical page number, and the high 7 bits contain the page map entry number within the page map in that page. 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 (invisble 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.) The cache is cleared whenever either page table register is modified (which invalidates cached entries).

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.

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 maintainence 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; the mode is then set to '10'. 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 operations (i.e., not during fault handling), this register is loaded with the address of an instruction fetch, or of an instruction vector.

KTDT and KTAD

These registers are loaded with 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 in cache refill operations; the counter is incremented on each cache refill operation.

KTWN

Operations to this register are performeed to the User mode address give in the KTAD; this allows the operating system to perform memory cycles as code in User mode would, without needing to do a complex simulation.

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.