Running ITS (the Incompatible Timesharing System) on the KL-10
{This is a historical memo written by Richard Greenblatt prior to the arrival of MIT's KL10; it has been reproduced here relying upon a hardcopy of RG's original text formatter source file (which appears to be for TJ6 or something like that) which I printed out 'back in the day', and carefully saved away. Other than fixing a few spelling errors, no changes have been made to the contents of the text; but I have tried to make it look the way the text formatter format control directions indicate the original was supposed to look (e.g. centered headers, etc), and also used Mediawiki tables in a number of places to reproduce the tables which he had in the original, using fixed-format to create them there. I have elected not to reproduce his formatting - line breaks, etc - exactly.}
The only modification that Project MAC plans to make to the KL-10 microcode prior to getting "off the ground" is that necessary to allow us to run our time-sharing system ITS. We propose to implement this ITS pager by means of changes to the KL-10 microcode. For this purpose, we intend to employ the "Murphy mode" or "KL-10 paging" mode hardware mechanism in the KL-10 processor.
We do not, however, constrain ourselves to implementing on the KL-10 an exact copy of the existing ITS pager on the KA-10. Instead, our goal is to allow reasonably efficient operation of the system by means of a combination of changes to the system software itself and to the KL-10 microcode.
We note that the mapping hardware of the KL-10, once properly loaded, is sufficiently general to perform the required address translation entirely in hardware. We are concerned below with the details of how the look-behind memories in the paging hardware get loaded and with how certain error conditions are handled. None of this affects what happens in the case of a "normal instruction" when all required mapping data is found within the hardware pager memories.
[Historical note: the ITS pager was designed and built in 1968, and thus predates the KI-10. ITS itself has existed since 1966 and began life on the PDP-6 as a protect and relocate oriented system. The development of paging versions of ITS was contemporaneous with the earliest TENEX development and the design and construction of the BBN pager for TENEX.]
There follows a brief description of the relevant features of the ITS paging box and comparisons with the KI-10 paging box.
The ITS paging box is similar in overall concept to the KI-10 pager. Both are basically "one extra memory reference per reference" designs. That is, to obtain the physical core address, the processor starts from a base address which is a function of whether the processor is operating in user mode or executive mode. (In DEC parlance, this base address is called the process table pointer (user or executive)). The hardware computes an offset from this base address which is a function of the virtual page number being referenced. The next step is to make a memory reference at the computed address to obtain the mapping information corresponding to the referenced page. Then the access control part of the mapping information is examined versus the type of cycle being requested by the processor. If a no access condition is indicated, a "page fault" is generated by the hardware. Otherwise, the physical core address for the originally requested cycle is obtained by substituting for the virtual page-number part of the requested virtual memory address the physical page number obtained as part of the mapping information.
The page size used in KI-10 and KL-10 systems is 512 words (1000 octal) whereas the page size used in the ITS pager is 1024 words (2000 octal). Thus, whenever the microcode is to do an ITS type page load cycle, it must actually do two hardware cycles, one to load information for the "even half-page" and one for the "odd half-page". (Alternatively, one could do just one cycle "now", and wait for the "other" half page to be referenced before worrying about it. This would probably result in slightly lower efficiency, but is entirely acceptable if more convenient).
Also, the page size comes into consideration when extracting the virtual page number from the virtual address. An extra right-shift of 1 will probably have to be microprogrammed here, since only the top 8 bits are part of the virtual page number on ITS as opposed to 9 on the KI-10.
As sketched above, the starting point of the mapping process on the KI-10 is the selection of the appropriate PMT depending on whether the processor is in exec mode or user mode. In the ITS pager, the registers that serve this function are called DBRs. However, there are some differences between PMTs as used on KI-10 and DBRs as used on ITS.
It is proposed that these DBRs be stored in the register memory of the KL-10. When a page fault occurs, they will be accessed and the necessary operations performed under microprogram control.
The following is a list of differences between the DEC treatment of PMTs and the ITS treatment of DBRs. Following each point is a brief comment about any possible difficulties that may be caused, proposed solutions, etc.)
- The DBR points solely to page table information and has nothing to do with trap locations, interrupt locations, etc. [It is proposed that PMTs continue to exist as they now do and continue to serve all functions they currently do, except those directly connected with address translation].
- The DBR has a "limit" field which forces all attempts to reference a page higher than that via that DBR to page fail. [The motivation of this is similar to the "small user" provision of the KI-10, i.e., to avoid wasting space on page tables for small users. Since, however, ITS makes no non-trivial use of this feature, the limit field will be eliminated in KL-10 ITS mode.]
- The PMT must point to a page boundary, i.e. its low 9 bits are forced to be zero by the hardware. The DBR does not have this restriction. [Since the intent is to microprogram operation of the DBRs, presumably this restriction will not arise with the simulated DBRs. However, as noted above, the PMT will continue to exist, serving its other functions. For this reason, ITS will be changed so that the "user variable block" is 1000 octal long (it is currently 742) and its starting address is aligned on a 1000 octal word boundary.]
- There exist 3 hardware DBRs as opposed to 2 currently active PMTs on the KI-10. Instead of just the one user PMT of the KI-10, the ITS pager has two user mode DBRs, one of which is selected for virtual pages 0-177 octal, and the other of which is selected for virtual pages 200-377 octal. [This feature allows the monitor to set up fairly efficient user job to user job transfers with the BLT instruction. Basically, the monitor loads half of the map of user A (ie one DBR) and half of the map of user B (the other DBR). The monitor must do a computation on the addresses involved and can then execute a BLT instruction. In the most general case, the monitor might have to split up a transfer into three pieces, changing the DBRs between pieces. Since all operations with DBRs are to be performed under microprogram control, this should not cause problems. The microcode must first examine the user bit, and if it is set, then examine the high bit of the VMA to determine which DBR to use.]
On the KI-10, the PMTs are loaded by the DATAO PAG, instruction whereas on the ITS pager the DBRs are loaded by the LPM instruction and can be stored by the SPM instruction (actually these are the same op code, decoded on the AC field).
For completeness and background, a description of LPM and SPM will be given, but it should be kept in mind that there is a large amount of flexibility in this area. In other words, it really doesn't much matter how the DBRs get loaded just so they get loaded, and any convenient means will serve.
On the ITS KA-10 pager, op code 102 is defined to "hack the paging box". It has effect only in executive mode. The operation performed is further decoded by the AC, performing the following operations:
| LPM | Load Page Map | loads the map from a block of 8 words starting at E |
| LPMR | Load Page Map and Reset | Performs the same operations as LPM and, in addition, causes the contents of the associative memory to be discarded. For the purposes of this section, this distinction is not relevant. (See section below on "invalidating data ..".) |
| LPMRI | Do LPMR then set FAULT bit in FAULT status, presumably causing an interrupt. (See section below on XCTR). | |
| SPM | Stores the current map data in a block of 8 words starting at E. The format is identical to that used by LPM. |
The data blocks referred to by LPM and SPM have the following format:
| wd0 | 5 bits unused, 4 bit AGE, 9 bit FAULT ADDRESS, 18 bit JPC | (PC of last jump instruction executed in USER mode.) | ||||||||||||||||
| wd1 | 5 bits unused, 13 bits OPC (old pc) flags and 18 bit OPC. | [These are used by the monitor to reset the PC after a page fault. Since the KL-10 has other means of dealing with this problem, it will not be necessary to simulate or further worry about the OPC.] | ||||||||||||||||
| wd2 | 11 bits unused, 4 bit RBC (ring buffer counter). | Present for maintainance purposes only. [Not necessary to simulate]. | ||||||||||||||||
| 3 bit MAR condition, and 18 bit MAR. | The MAR is a debugging feature very similar in operation to the ADDRESS BREAK feature of the KI-10. [The mechanism of the ADDRESS BREAK can be used to implement the MAR]. | |||||||||||||||||
| wd3 | 6 bits unused, 12 bit FAULT STATUS, 18 bit QUANTUM TIMER | The FAULT STATUS field consists of the following bits:
See further discussion of FAULT STATUS under the section "determining what caused a page fault." | ||||||||||||||||
| wd4 | 5 bits unused, 5 bits OFA [output fault address, maintainence only], 7 bits DBRL1 and 19 bits DBR1. | [As mentioned earlier, the DBRL feature will not be implemented.] DBR1 is used to map user virtual addresses 0 - 377777 (octal). The 19 bit length of DBR1 allows a physical address anywhere in the 512K physical address space. However, on the KL-10 it would be perfectly acceptable to have DBR1 be 18 bits specifying an address in the low 256K if that were easier.] | ||||||||||||||||
| wd5 | 6 bits unused, 4 bits more OFA, 7 bits DBRL2 and 19 bits DBR2. | [DBR2 is used for user virtual addresses 400000-777777] | ||||||||||||||||
| wd6 | 10 bits unused, 7 bits DBRL3 and 19 bits DBR3. | [DBR3 is used for exec virtual addresses 400000-777777. Exec virtual addresses 0-377777 are unmapped. However, the feature of the KI-10 mapping the top 16K of this range on a per user basis would not cause any difficulties if present. (Presumably, however, it won't be.)] | ||||||||||||||||
| wd7 | 7 bits unused, 5 bits B-KEY, 5 bits C-KEY, and 19 bits ACP (AC pointer). | [The B-KEY and C-KEY control sections of the associative memory and are not relevant to the KL-10. The ACP is used during the XCTR instruction (eXeCuTe Relocated - very similar to the Executive XCT on the KI-10). See section on ACs referenced during an XCTR.] |
Running on a KA, ITS does not presently deal with the multiple AC block feature of the KI and KL. However, in order to simplify the problems of AC references by executive XCT (discussed below) it appears that the simplest thing to do is to change ITS to conform with the KI and KL convention that the monitor uses AC block 0 and the user jobs normally use AC block 1.
Both maps provide similar means for the monitor to reference User Virtual Memory while executing in exec mode. The KI-10 employs an additional interpretation of the AC field of the normal XCT instruction when used in exec mode (= PXCT), while the ITS pager employs a different op code (XCTR = 103). [This is a trivial difference. ITS can be changed, if desirable.]
Both instructions interpret two bits of the AC field to separately control for READs and WRITEs whether the USER virtual address or the EXEC virtual address space is to be used. [There is an incompatibility in that the READ bit on ITS controls only pure READ cycles. READ-MODIFY-WRITE cycles are under the control of the WRITE bit. On the KI, one bit control READ and READ-MODIFY-WRITE cycles and the other pure WRITE cycles. This incompatibility is not serious however, since ITS always uses both READ and WRITE mapping on XCTR'ed read-modify-write instructions. [There is an additional incompatibility having to do with byte instructions. The ITS pager addresses the byte pointer in user space, while the KI10 pager addresses the byte pointer in exec space (only the byte itself is in user space.) It would be trivial to conditionalize the software to circumvent this incompatibility.]
The ITS map, however, also interprets a third bit in the AC field of XCTR called the INHIBIT bit. If a page fault occurs under the control of an XCTR, the appropriate bits giving the type of FAULT (NO ACCESS, WRITE INTO READ ONLY, etc) are strobed into the FAULT STATUS as usual. However, if the INHIBIT bit is set in the XCTR, the FAULT bit is NOT set. Thus no interrupt occurs. Instead, the XCTR skips the next instruction. (It is illegal to XCTR a SKIP instruction in this fashion). Detecting that a page fault has occurred by the fact that XCTR skipped, the monitor has a chance to "clean things up", unlock switches, etc. Finally when the monitor desires to process the page fault, it does an SPM followed by an LPMRI. This sequence sets the FAULT bit, leaving the fault reason bits unchanged. An interrupt then occurs and is processed as normal. This feature is also useful for making mapped references at the interrupt level where a page fault might be "embarrassing" (or might not happen at all due to being PI in progress on a higher channel, etc).
It should be possible to write the microcode for the XCTR instruction in such a way that if the INHIBIT bit is on a flag will be set. This flag should be checked by either the page fail microroutine or the page-trap routine in the monitor, it doesn't matter much which. The effect of the flag should be to suppress handling of the page fault and return control to the address of the trapped XCTR + 2. The page-fail word would be stored in the UPT; this is analogous to the ITS pager strobing the FAULT STATUS. After cleanup, the page fault needs to be taken. Instead of using LPMRI, we could simply transfer to an alternate entry to the page trap subroutine. It is necessary for the software to avoid using XCTR INHIBIT while a page trap is in progress, unless it saves the page fail word, etc. This is already true with the ITS pager.
A complicated subject, particularly on the KI10! If an AC is referenced as a USER virtual address under the control of an XCTR, it is clearly not the right thing to reference the hardware ACs at the time since they are used by the monitor (at least on the KA). The ITS map provides a relatively straightforward feature for dealing with this problem. An ACP (AC pointer) register is provided, capable of holding a physical core address. The monitor loads this register with the address of the start of the block where it has saved the user's ACs. When the hardware detects that the user virtual address is an AC, it simply adds this register to the AC number, thus obtaining the physical core address to be used. [For purposes of ITS it is not acceptable to reference the shadow ACs in this case, because page 0 may be shared or swapped out. This is why it appears we want to leave the user ACs in AC block 1 and reference them from there].
The KI has a much more complicated feature which is intended to facilitate monitor calls from within the monitor, etc. [Since these are not used by ITS, the problem reduces to deciding which KI mode has the fewest screws associated with it and arranging to enter and stay in that mode. Of KI modes, the one accessed by USER IN/OUT = 1 and FAST MEMORY BLOCK nonzero seems to be the most winning].
ITS currently uses the AC-pointer feature to allow use of XCTR to reference other users' ACs, etc. It will be necessary for the software to keep track of which sets of ACs are loaded into which physical AC blocks.
The ITS map causes faults via the processor interrupt mechanism. ITS will be changed to make use of page traps a la KI and KL. The processor PI channel will be turned off with a CONO PI early in the page trap routine, to simulate the interrupt environment.
The page fail word has a different format from the FAULT STATUS register of ITS. ITS will be changed to use the KL-10 style page fail word.
Using the INHIBIT feature of XCTR, with the ITS map an interrupt level routine can safely make mapped references that would take page faults. (It must save the state of the pager with SPM first and restore it.) However, this feature is not necessary to run any of the IO devices we intend to support with the KL-10.
Slightly different is taking a page failure in the scheduler, which runs at PI channel 7 level. This can happen when trying to give the user an interrupt. However, it appears this will cause no problems with the KL-10.
The ITS pager does this with the LPMR instruction. Since this is part of loading the page map control registers, the subroutine to do that can be modified to issue the appropriate instruction (DATAO PAG?).
An AC block will be used to hold the page map control registers. They will be loaded by setting the user AC block number and using an XCTR of a BLT. Other registers outside of this block are the AC block number, EPT address, UPT address, quantum timer, and MAR. These will be implemented using the mechanisms already present in the KL10.
The registers in AC block 6 are:
| JPC | address of last jump instruction in user mode |
| DBR1, DBR2, DBR3 | addresses of 64-word page maps |
| AGE | value to stuff into page table words when they are touched by page ram refill. (See special features section below.) |
The non-cache feature will only be used for the DL10 control area and an area in which DF10 channel programs will be constructed. These will be in the low 128K of exec address space, so the page map words for these pages will not come from normal ITS page maps. When the MBOX asks the microcode to refill the page map RAM for locations in the low half of exec space, some sort of special action will have to happen. [As yet undetermined.]
The OPC is rendered unnecessary by the fact that the KL10 was designed with aborting of instructions by page faults in mind.
The JPC will live in AC block 6. At some point we will add microcode to the jump instructions to maintain the JPC. Since this is only a debugging feature it will not be implemented immediately.
The MAR will be simulated with the address break feature. Software will provide the translation to make the KL10 address break look like the ITS MAR to user programs. Hopefully the address break feature is sufficiently powerful.
It is unclear at present how ONE PROCEED will be implemented; perhaps by setting the trap flags in the PC to 3?
The QUANTUM TIMER is a register which increments every microsecond except when PI IN PROGRESS. It is per-user because it is loaded and stored by LPM and SPM. Hopefully the KL10 metering features will allow the same effect to be achieved. [What are EBOX ACCT and CACHE ACCT?]
The ITS page map has AGE bits. A 3 or 4 bit register contains a value which is stored into a field in each page table word when that word is picked up into the associative memory. This is used to determine whether pages have been referenced recently. This feature will be simulated by the page refill microcode.
Microroutine to handle page fail condition. Examines ITS page tables, stores age bits, refills page ram, determines if a page fault should be signalled to the software. If so, the KI/KL trap mechanism will be used.
- XCTR instruction, including special code for INHIBIT flag.
- LPM, LPMR, LPMRI, and SPM instructions will not be implemented. [Maybe it would be better to implement them? Then the software would need less changing, and it might be possible to flush KL10 instructions that do the same thing. However, this would require more microcode to be written and probably would take more microcode space. We should do whichever turns out to get the system working more quickly.]
- The KL10 MAP instruction is not useful for ITS and will be flushed.
- Later the JPC will be added.
