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 time-sharing 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 instruction 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.

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

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"); a valid instruction, but one which normal code is unlikely to contain.

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.)

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 (which holds trap and interrupt vectors) is not 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 (i.e. the Exec mode page map must be in the first page of Exec mode address space).

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. (That 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 set of actions 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; 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.

Since it is the upper part of Exec mode address space, which includes the part of the address space reserved for device registers (the 'I/O page'), this does mean than if this feature is used, each User mode page map page has to contain 16 entries (8 Kbytes at 512 bytes per page) to allow access to the device registers (if they are to appear in the same place in the address space as they normally do).

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 for a page containing User mode page maps (below); the high 7 bits contain the shared page map entry number, which selects a page map entry in the 'User mode map for User Simple pages'. Each SEP can point to a different UMPM page, which is not necessarily associated with any particular process (i.e. ever used as a UMPM).

Implementation

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

The KA11 CPU of the -11/20 is also slightly modified, and a cable carries additional 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. Cache entries are divided into an associative memory entry, which is 8 bits wide (7 bits of page number, and 1 Exec/User bit), and a scratchpad memory entry, 16 bits wide. (Although these would seem, logically, to be single extended-width registers, the two sections are actually stored in different parts of the hardware, which is why they are described as paired entries.) Scrachpad entries hold page table entries; each associative memory entry contains the page number for the related scratchpad entry.

An option increases the size of the cache to 24 entries, which can reduce the amount of memory bandwidth 'wasted' on cache refills. It requires an additional scratchpad memory, and a group of associative memories. The base scratchpad memory is also used to hold many of the KT11-B's registers (below).

On a fault, the copy of the page table entry in the cache is cleared; that way, if the OS modifies the page table, and re-starts the instruction which faulted, the KT11-B does not use an old (and likely outdated) cached page table entry. The entire 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.

Buses

There are 4 UNIBUS slots in the KT11-B's backplane:

• UNIBUS from CPU (slots A/B14), slots A/B01
• Ending termination for that UNIBUS, slots A/B02
• UNIBUS out to memory and devices, slots A/B03
• Beginning termination for that one, slots A/B04

All devices must be moved 'down-stream' of the KT11 (apparently so that proper interrupt processing can be performed); this includes all devices that would normally be resident in the CPU backplane, including the console KL11/DL11 and the KW11-L Line Time Clock.

Since the latter is a single-height board which requires a specially-wired slot, a space is provided for it in the KT11-B backplane, at slot B09.

Debugging

The KT11-B supports the standard DEC W130/W131 maintenance board set; it plugs into slot A14 of the KT11-B. The two switches:

• Enable the maintenance clock
• Provide a maintenance clock pulse, moving the KT11-B from state to state

The lights display the KT11-B major and minor states, the state change control lines, and a number of other internal signals.

Programming

The KT11-B is controlled by a bank of eleven registers, described below. It also uses 4 page maps, stored in main memory.

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 maps

The address spaces seen by Exec and User mode are both optionally divided into two sections, each of which has its own page map.

Low Exec mode space is 'Exec Simple', controlled by a single Exec mode page map; high Exec mode space is Exec-per-Process, controlled by a page map which is part of the User mode page map (or, at least, stored in the same page as the UMPM). Low User mode space is 'User Simple', controlled by a per-user User mode page map; high User mode space is 'User Shared', and entries in the high part of the UMPM are indirect entries which point through another UMPM.

• The Exec mode page map for Exec Simple pages is in the high part (0400 and up) of page 0 of Exec mode space, which is in the page whose physical page number is in the KTEM register (below). (The low part of that page holds trap/interrupt vectors).
• The Exec mode page map for Exec-per-process pages is at the end of the low part (from 0376 down) of the current User mode page map page (which is in the page whose physical page number is in the KTUM register), above per-user kernel data (which starts at 0 of that page).
• The User mode page map for User Simple pages is at the start of the high part (0400 and up) of the User mode page map page.
• The User mode page map for shared pages is at the end of the high part of a User mode page map page, i.e. immediately after the User mode page map for Simple User pages; but it contains Shared Entry Pointers, not Page Map Entries, like the other three.

Thus one page map (Exec Simple) is in the Exec mode page map page, whereas the other three (Exec-per-Process, and both User mode page maps) are in the User mode page map page.

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, including which of five kinds of 'violation' happened, and are frozen when a fault occurs, so that the operating system can see what kind of cycle provoked the fault. They are:

• 02 - Source state
• 03 - Destination state
• 07 - Interrupted User (Modified Sequence performed)
• 11 - Instruction Violation (illegal in User mode; not an Entry)
• 12 - Address Violation (odd address)
• 13 - Write Violation (write to a read-only page)
• 14 - Privacy Violation (cycle other than Fetch to private page from public)
• 15 - Residency Violation (page not resident)

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 re-use 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.

The maintenance bits (actually seven, not five as stated in the Option Description) are not described in the Option Description, but are:

• 06 - Previous instruction User mode TRAP?
• 07 - Previous instruction fetch Private?
• 11 - Non-Simple reference (phase 1)
• 12 - Non-Simple reference (phase 0)
• 13 - Window (phase 1)
• 14 - Window (phase 0)
• 15 - Time out

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.

KTWN

Memory operations to this register are performed through to the User mode address given 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.

See also

• KT11-B Technical Manual