|
To: FFL Systems Group |
Date: June 1, 1966 - July 1,1966 |
|
From: Butler W. Lampson |
Version: 1 |
The, system comes in three major pieces; namely the monitor, the exec and the subsystems. The monitor is the guts of the system. It is mostly resident in core and it eventually takes care of all interactions between the programs and the outside world: all input-output, scheduling, swapping, handling the drum or disc, handling teletypes etc., etc., etc. The exec is mostly non-resident, i.e., swapped; it runs as a user program. Its function is to provide what you might call second level control. Namely, it takes care of implementing the command language by which the user controls the system; it takes care of file naming, which allows the user to give symbolic name’s to his files and reference them afterwards, and it provides a ‘number of special services such as floating-point, input-output, string handling operations and one thing and another. This we will discuss perhaps in some detail. The third component of the system is the subsystems. A subsystem is just some language or convenient facility which has been programmed and inserted in the system in such a way that you can get at it by giving its name as a command to the executive. A subsystem is regarded as a completely independent program, not closely connected to any part of the system proper. It’s basically just like a user program. The only difference between a subsystem and a user program is that the name of the subsystem is in an exec table together with information about the location of the subsystem and its starting address. If a user types in its name the exec will find it in the table, bring it into user core and start it up at the specified address. After that the user is talking to it just as though it was one of his own programs. The subsystems include the debugging system, the assembler, the editor, Fortran, Cal, Lisp, Snobol, etc., etc., etc. What we are going to be mostly concerned with is the monitor in this discussion, because the monitor is the most complicated and the most essential part of the system. The executive is much simpler, it interacts less with parts of itself, and it also is much easier to change since it runs as a user program. The errors made in changing the executive are likely to be less disastrous than errors made in changing the monitor.
That is the overall structure of the system. And as I say we’re going to be talking mostly about the monitor. We won’t be talking about subsystems at all except maybe to make a list of them.
The next thing we want to do is discuss all the hardware changes to the 940, everything which is different from what it says in the 930 manual. These changes come more or less under the following headings:
modifications to the instructions
to the interrupt system
to the memory addressing and bussing
and finally, various new I/O devices
We’ll take these more or less systematically in order. As far as instructions are concerned there are the following things. Two modes have been added to the standard 930. When the system is in normal mode it is operating like a standard 930 and there are no changes at all. By doing an EOM you can put it into system mode. In system mode it still works like a standard 930 except that some of the things that we’ll discuss in the memory system are enabled as well as a couple of new instructions which we’ll also discuss in a minute. You can get into user mode by doing a transfer with the sign bit of the instruction set. This way you get from system mode to user mode. In user mode there are large number of instructions that are called privileged. This means that in user mode they cannot be executed. If a privileged instruction is executed in user mode, it causes a trap. A trap is a forced transfer to a particular location in lower core, 40 or 42, something like that. There are four traps, each one with a unique location. At this location the system will put a transfer to a little subroutine that will do something about the trap. Namely, it will type out a little message “You made an error” or something like that. Or whatever you want it to do. Exactly what the system does do is something we will cover in more detail later on when we are discussing the relevant parts of the monitor. What the hardware does when it sees a privileged instruction trying to be executed in user mode is to force a transfer into this fixed location. The privileged instructions are all input/output instructions and anything that might halt the machine (which includes not only the explicit halt instructions but a whole lot of other instructions that are illegal for one reason or another). There are a lot of undefined opcodes in the 930.
Then, there are a couple of new instructions. There’s an instruction for clearing interrupts called BRI, which is exactly equivalent to branch indirect except for its effect on the interrupt system. In the normal 930 any branch indirect clears an interrupt, in fact, clears one interrupt level, so that if you have three interrupts hanging and you are sitting in the top priority one you do a BRU indirect which clears the top priority interrupt and also leaves you sitting back in the routine which is processing the interrupt of next lower priority. See figure 1. Because of the fact that the system sometimes wants to execute BRU indirect without clearing an interrupt, we’ve added a special instruction (BRI); which specifically serves to clear an interrupt and otherwise acts like a BRU indirect. BRU indirect then no longer clears interrupts. This is effective only in system mode, of course. Another change: the EAX instruction (effective address to index) has been modified. This instruction in the 930 computes its own effective address and puts it in the bottom 14 bits of the X register. Since EAX may be indexed or indirectly addressed, and in the latter case the indirect word may again be indexed or indirectly addressed, the computation involved may be non-trivial.
Example: if X contains 1212 and memory is
1000 LDA* 1400,
2
2612 BRU (12 + 12 + 12 = 1224)
then EAX* 1000 will put 01224 in the bottom 14 bits of X. This is a very important instruction. It has been slightly modified in system mode so that in addition to setting the address part of the index register to the effective address, it will set the sign bit of the index register zero or one, depending on whether the effective address was relabeled, was mapped or not. The mapping is simply determined by whether the sign bit is turned on or not, in system mode. If the sign bit of the instruction is turned on mapping starts right away. If it’s not, the first level will be done without mapping but if you go indirect you may again have the possibility that the sign bit is on, in which case mapping will start at that point. So, again, its not too easy to tell whether the final address is mapped or not. Consequently it’s very nice to be able to find out without explicitly running down the chain looking at all those sign bits, whether the address is mapped or not. And in order to accommodate this, in system mode EAX changes the top bit of the index register to zero or one depending on whether the final effective address is or is not mapped. The reason for this is that the way you normally use EAX is that a link has been put into location 0, a subroutine link essentially, and what you do is you say EAX* 0. And what this does is it goes out to 0 and in 0 there will be a link that was left by a POP. (See Fig. 2) Everyone knows about POPs?
What the EAX is going to do is to go back and pick up the effective address of this POP, namely ABC, 2., with the intention of using that as an argument. You do the EAX first, and that gives you the effective address in the X register and then in order to pick up the argument word all you have to do is say LDA 0, 2. In order to pick up the second word of the argument you say LDA 1, 2 and so on. The difficulty is that if you are in system mode and the address was mapped, then you must not say 0, 2 but you must turn a sign bit on, and say 0, 6; otherwise you won’t get any mapping. So you have to know whether you have mapping or not so you can decide whether to say 0, 2 or 0, 6. And this is the reason for this little gimmick. In some cases you don’t have to worry about this problem, in particular, if the only thing a POP needs is the first word addressed: ABC, 2 itself and not any subsequent words. Suppose you want to get that word into the A register. Just say LDA* 0, and that sends you indirect to 0, indirect to 2216 and off to ABC, 2 and gets it to you right away. The mapping problem is taken care of automatically, because when you go to 0 mapping is turned on because the sign bit is set. All right, so if you want to use a single word then you can get it automatically with LDA indirect, because the mapping will be turned on automatically by the convention that it gets turned on when you go indirect through a word that has a sign bit set. But if you need, say, ABC+1, 2 (for instance if you were doing a floating point POP and were addressing a floating point number which takes up two words), then you want to get the effective address in the X register so that you can do LDA 0, 2 and LDA 1, 2 and get both words. But in that case you need to know about the mapping. The only way you can avoid worrying about the mapping is to just assume that the POP came out of user mode. Then you always turn the sign bit on in the instruction. Or you assume it came out of system mode and you never turn it on, But if you want to have a POP that works both ways then you need this gimmick. The chances are good that you will be adding some SYSPOPs. Basically the reason for this is that, for instance, when you get something all set up and want to make a disk reference, the way you will probably do this is by executing a SYSPOP. Why? In order to make that disk reference you have to look up in a table, which is going to be permanently resident in core.
It probably will be nice not to have that table in the user’s own relabeling. The only time you need to reference that table is in this one case when you are actually ready to make a disk reference. So this means that probably the way you want to reference that table is by having a SYSPOP, so that when you are all set to reference it you put the relevant things in the A and B registers or whatever and execute the SYSPOP. The SYSPOP then, running in system mode, can reference the table by changing the relabeling or in some other way.
Now, what else is there about instructions? Oh yes, overflow instructions. The two basic input-output instructions on the 930 are called EOM (which stands for Energize Output M. Why M, I don’t know) and SKS. What EOM does is essentially to send signals to all the I/O devices and other miscellaneous hardware. Somebody is supposed to recognize the signal and say “That’s for me,” and turn itself on. SKS stands for Skip on Signal. It looks at lines coming in from the outside world and the address field selects one of these lines and skips or doesn’t skip depending on whether the line is on or off, up or down. Normally, of course, these instructions are privileged. However, in the normal 930 these instructions have one non-privileged use. Namely, they are used to turn off and to test the overflow indicator. It is necessary for the user to be able to do this. So, originally what we did is we had a whole lot of complicated logic to say EOM is privileged but if it is an overflow EOM it’s all right, it’s not privileged. Well, this was very messy. So in order to straighten out the situation we added a new instruction, opcode 22. I guess it doesn’t have a mnemonic of its own. It can have three or four different addresses corresponding to the three or four different overflow instructions that used to be handled by EOM and SKS. This instruction I guess even works in normal mode, although there is no particular reason to use it in normal mode. As a result of this change we have been able to make all EOMs and SKSs privileged.
The next thing is the interrupt system. The normal 930 has a priority interrupt scheme and perhaps it would be helpful it I describe it very briefly since most people will never get to the section of the manual in which the priority interrupt scheme is described. Priorities work like this. You buy them in bunches of two, and you can buy lots, so there are lots of priority interrupts. They are numbered: 1, 2, 3 up to 872 which is the most you can get. The idea is this. Each priority interrupt has a line from the outside world attached to it. And each priority interrupt also has an address in memory, starting at 201, so the first one has address 201 and the second one 202, etc. Signals can come in on these lines. And if a signal comes in—suppose just one signal comes in, on line 4—the effect is that at the end of the execution of the current instruction, whatever it is, the normal flow of execution will be stopped and the computer will instead be forced to execute the instruction in location (203) since this is the fourth interrupt. This instruction will normally be a BRM which will store the location counter and transfer off to some subroutine which is designed to process the interrupt. When the interrupt is processed you return from the subroutine with the BRI instruction that I discussed earlier, which will clear the interrupt. This much is common to all interrupt schemes. The priority thing comes in the following way. Suppose that while I’m processing interrupt number 4 a signal comes in on interrupt number 2. Now 2 is regarded as being of higher priority than 4, and what this means is that I want to execute 2 right away regardless of whether I’m executing 4 or not. So 2, being higher priority than 4, is able to interrupt 4, so that even though I am processing an interrupt on level 4 I am forced to execute the BRM at ,202. And at this point, when I am in the routine specified by the BRM in 204, I have two interrupts going. Interrupt 4, which is not executing, just hangs. When I exit from 2 with a BRI I go back and start executing 4 again.
Q Does it start all over again?
A No. It starts wherever it was. Say you execute the instruction at 202, which may be BRM 1202. What happens is that it stores the location counter in 1202 and goes to 1202+1, where there will be instructions that save the central registers: STA, STB, STX. After the routine at 1202 has run, it will restore everything with LDA LDB LDX, and then it’s going to say okay now I’m finished, so how do I exit? I exit by saying BRI 1202. Now BRI is exactly like BRU indirect. Remember? So what it does is to transfer off to the location specified in 1202, but it is exactly what was in the program counter when we executed the BRM 1202. It was exactly the location of the instruction which was about to be executed when the interrupt came along and said, No stop, don’t do that:’ So the effect is that I go back and continue executing whatever I was doing when the interrupt came along without any disturbance at all, provided, of course, the interrupt routine saves the central registers, It has to do that. The only thing the BRI does is to clear the highest priority interrupt. So I come back now from interrupt level 2 to interrupt level 4, which is restarted automatically. Eventually 4 gets finished, and then its BRI sends me back to whatever main non-interrupt program was executing.
Q Did you say that the central registers are not preserved?
A Not automatically, but every interrupt routine of course should preserve them, and if it doesn’t horrible things will happen.
Q It is never interrupted during the storing?
A It might be, it doesn’t matter. Suppose it’s interrupted after, doing STA. All right, that means some other routine will go off to do its operation, which presumably will preserve the central registers since it also has storing and loading instructions in it. When it comes back this one will just proceed with its storing and there’s no disturbance. Okay? An interrupt routine is supposed to be completely invisible to whatever it is interrupting, and if it’s not that means it wasn’t written right.
Now suppose on the other hand that I was in interrupt level 2 and interrupt 4 came along. Since 4 is lower priority than 2 I do not want to stop executing 2 when 4 arrives. What happens is that 4 just sits there and hangs. It’s an interrupt which is unfulfilled,—until 2 is finished. As soon as 2 is finished, 4, which has been hanging there, immediately gets in, and starts to execute.
Q How many things can we have hanging?
A As many as you want. You can have them all hanging, waiting for number 1, okay? Naturally, because of this priority scheme, you want to make a great effort to keep the high level interrupts short because they hang all the lower ones while they are going. It may be worthwhile to point out that above these priority interrupts there are several built-in interrupts in the computer, the ones relating to the TMCCs (2 for each), the clock interrupt and power fail. They are really in the priority scheme in the same way, differing only in their numbering and the fact that they come with specific devices. You can think of them as just being higher priority interrupts above 200.
Q The higher priority ones are in the middle there some place?
A Power fail is highest. Then comes the clock. Its location is 75. Then comes the W-buffer at 31 and 33, then other TMCC’s and DACC’s, then the regular priority interrupts.
Q There’s another priority in the channel?
A That’s right, each TMCC has two interrupts. The channels are higher than any of these 200s although you can get this rewired. You can make it go any way you want.
This is what you buy on an ordinary 930. There is one other little goodie you can get which allows you to say for each one of these interrupts whether you want anyone to pay any attention when the interrupt arrives or not. If you are paying attention the interrupts are said to be armed, and if you are not paying attention they are said to be disarmed. We use that feature in a couple of places. In addition, the whole interrupt system can be enabled or disabled. If it is disabled, any interrupt that comes in just sits there and waits. Disabled is sort of equivalent to saying, “Some really high priority thing has come along that is more important than anybody else. “ When you reenable the interrupts, any that are waiting immediately start trying to get in and the highest priority one does.
A Is there any possibility of losing an interrupt? No.
Q Suppose I made a 201 and is it possible 204 could get in twice?
A Yes, that is possible. If you have an interrupt coming up frequently, yes. Definitely.
Q Is this a normal occurrence?
A Never. That’s an absolute disaster. You arrange that device which generates interrupts so that it doesn’t generate them at such a high frequency. You can build a device so that it never generates an interrupt more often than every 5 milliseconds.
Q What if you disable the interrupts for 5 milliseconds’?
A Then you’re a fool, and you deserve to lose! You may disable for a short period of time because if an interrupt comes in during this time you may get badly confused. Particular reasons for disabling, which will show up when you look at the system itself, are that you may be operating (outside of any interrupt routine, in the main program) and you may want to fiddle a table that also gets fiddled by an interrupt routine. If you get interrupted in the middle of the fiddling process the interrupt routine will get very confused. So what you do is to turn interrupts off for the fiddling time. It must not be very long or you are likely to get yourself into serious trouble.
Q This means that a routine can’t cause the same interrupt it is processing?
A External devices cause interrupts. The program is not an external device. A program is a program. It cannot generate an interrupt.
Q But an interrupt routine may have I/O instructions in it?
It depends on what the interrupt is. It may, yes. But the routine can’t cause an interrupt. The only thing that the handling routine can do is fire the device up again. If the device is constructed so that immediately when it’s fired up it generates the same interrupt again, probably there will be a mess. If you have just fired the device up, there is no point in its causing an interrupt. You already know that you fired up. The significance of an interrupt is to tell you something you didn’t know.
A No it doesn’t disarm itself. I don’t understand why you think that it should.
Q You said if something is mechanically wrong it could be hung up in that interrupt for hours. Why?
A Because the interrupt keeps coming through.
Q Why would the interrupt keep coming through?
A Because it’s being generated each time. Each time you leave the handling routine you get the same interrupt again.
Q Why do you get an interrupt? What generates that interrupt?
A If the device is malfunctioning so that it has its interrupt line all the time, then you can get into trouble. You can get into trouble if you take a soldering iron and put it on top of the B register. If the hardware is not working then you’re in trouble.
Q How is that handled?
A When the hardware is not working you call a service man to fix it.
Q How do you find out what’s wrong?
A You have a diagnostic routine to run around and check everything. And this is, by the way, one of the significant problems of this system, because the diagnostic routines are not adequate.
We have modified the interrupt system slightly, in that it used to possible to shut out interrupts when you were sitting in certain kinds of loop, particularly if you were sitting in a loop of the form BRU* or BRX*. Also, something of the following form:
A LDA* B
B ZRO* A
could shut out interrupts. If the LDA is executed, then in following the indirection we go from A to B, from B back to A, from A to B and it’s an infinite loop. This is obviously an error, but any user can w rite this.
All three of these conditions in the 930 will tie up the interrupt system. All these things go so fast that they never allow the machine to get into a state in which an interrupt can occur. And this is obviously disastrous, since it means that the user, by making an indirect loop, which is not at all impossible, can hang the whole system forever. Once he starts there is no way to get out of it because there is no way to get an interrupt in to stop it. So that’s very, very bad and the way we correct this situation is by jiggling the insides of the machine so that there is no sequence of two instructions which don’t allow an interrupt in the middle, with one exception, which is EOM. Between every two instruction executions in the 940 it is possible to accept an interrupt. This means that the longest amount of time you could have to wait before an interrupt gets in is the longest amount of time for the longest executing instruction, which happens to be divide, which is 10 cycles, or 17.5 microseconds. So much for that.
Q Is time-slicing handled with interrupts?
A As we go through the system properly we will see all these interrupts and how they are handled one at a time, but it might be helpful to make a list, of the important ones anyway: there’s the clock, the W-buffer (which has two interrupts), the teletype interface, power fail, and the drum. There is also a link to a subsidiary machine, the PDP-5. This is driven through the DMC and if you drive displays through the DMC you will get an interrupt similar to this one. That’s all.
Q What about tapes, printer, etc.?
A They all go through the W-buffer.
Besides interrupts there are also traps. Traps are caused by illegal (privileged) instructions, memory violations (which we will discuss below), read only violations and something called the user mode trap. Those are the four traps. We will discuss them all in detail later on. Overflow is not a trap.
Overflow just occurs and sets an indicator which you have to look at. That’s an obsolete way of handling overflow, but that’s the way it’s handled in the 930, the 930 being more or less an obsolete machine.
We have quite a lot of things associated with the memory and will start with the things in the bussing hardware, which are less important. A 940 system always has at least two memory boxes. A memory box is some number of words of memory (4000, 8000, or 16000). Its significant property is that it operates independently of all other memory boxes. This means you can have memory references going on in two separate memory boxes at the same time. The CPU can’t have memory references going in two separate boxes because it needs to finish the first reference before it can start the second one. But you could have one box being run by the CPU and one run by the channel, for instance. For convenience, we’ll talk about a 32K machine which has two 16K memory boxes. Normally the way things are arranged is with addresses zero to 37777 in one box and 40, 000 to 77777 in the other.
We have modified this arrangement in the following way: all even addresses are in one box and all odd addresses are in the other box. This is called interleaving. The reason for this is the following: when you run I/O at very high speed, and particularly when you run our core speed drum, it transfers information in blocks and this means that if the drum starts to run out of this box, starts at location 4000 and wants to transfer from 4000 to 8000 say, it will take every memory cycle if it’s running at core speed, which means that nobody else will be able to get a cycle if you’re using the non-interleaved scheme.
When the drum starts to run out of one box it will lock the CPU out of this box because it has priority and has to get every cycle. It locks the CPU out of this box for 2000 memory cycles while it does the transfer. And that’s very bad, because it means the system can’t run at all, no interrupts can be processed, nothing. The CPU is completely hung. If you have interleaving, on the other hand, the drum will take one reference out of the first box, then one out of the second, t hen one out of the first, etc. , which means that the CPU can run at 50% of its normal speed at least. Probably it will be better than that. Interleaving is very simple to implement. Suppose we have a short address, six bits, a 64 word memory (See Fig. 3). You have address lines coming to the memory, the low order bit on the right. As the address lines come out of the computer they go into the memory. The usual way to arrange it is that they go straight into the memory. All you have to do to get interleaving is to interchange the low order and high order lines. This means that it will be even or odd that decides what the first bit is going to be on the lines coming into the memory. So where before it was the high order bit which decided which module you get, now it’s the low order bit, which decides which module you are going to get. So it’s completely trivial.
The second change in the memory itself is a little more subtle. Suppose we have the two modules and two devices going. We have a CPU, which is generating memory references in some random way to the two modules, and we also have the channels, say the RAD channel, which is also generating memory references. Now the RAD is a synchronous device and every four memory cycles it generates a word while it’s running. If the word isn’t disposed of by the time the next word comes along, a disaster has occurred, because the word is lost. The RAD has a buffer which sits there holding the word, and somewhere else the next word is being assembled. When the next word is finished being assembled it comes into the buffer, because there is no room for it anywhere else, and this means the first word has to be emptied out of the buffer by the time the second word comes along. The easiest way to handle this problem is to say that the RAD has to have priority sometimes, so we’ll give it top priority all the time. When it asks for this memory module we’ll give it this memory module and during the first cycle I guarantee the word will be out of the RAD buffer as fast as possible. Now this has the following disadvantage: if the CPU is asking for this box at the same time as the RAD, the CPU will get hung for one cycle while the RAD is looking at the box. This is interference. In this particular case, with two modules and the RAD getting one cycle out of four, there will be interference 1/8th of the time, so you get 12% degradation in CPU performance, simply due to the fact that 12% of the time when the CPU wants a memory cycle it has to wait
However, this analysis ignores an important point, namely, that when the RAD generates a memory request, it can wait for three cycles because another word is not going to come along for four memory cycles. So when it says, “I want memory, “ what it really means is, I’ve got to have one of the next four cycles, but I don’t care which one it is, just as long as I have one of those four cycles.” Each device using the memory sends it address lines and data lines, and a priority line or request line which says, “I want the memory”.
Built in somewhere is a gadget that settles ties on the basis of built-in priorities for the various lines. What you do is to make the priority line for the RAD a little bit more complicated: you use two lines instead of one. This means that the RAD can say either, “I want the memory with high priority, “ or, “I want it with low priority”. High priority means mine is higher than anybody else and low priority means mine is lower than lots of people, anyway, lower than the CPU. So what the RAD does is to ask for the memory with low priority on the first three cycles. If the CPU wants it the RAD has to wait. On the fourth cycle it asks for high priority, because there’s another word coming along pretty soon. If the CPU still wants the same module after three cycles, it will be hung on the fourth. In fact, the CPU almost never references the same module four times, because instructions, for one thing, go in alternating modules because of the interleaving. Furthermore, if you take random instructions and random addresses, it is 50-50 that the address will be in a different module than the instruction. So the chance of the CPU wanting the same module four times in a row is less than 1%. This means that you effectively reduce the RAD’s interference with the CPU from 12% to zero at the cost of putting in this very simple priority device.
Q How does the RAD buffering really work?
A There’s a buffer which holds the assembled word and this is the buffer that is connected directly with the memory. Then there is another buffer in which the RAD is assembling a word, six bits at a time, as it comes off the disk. In this buffer there are control signals telling where to put the next six bits, and when the fourth set of six bits is coming along that is the critical time. Probably, you can take one of those control signals right off and use it for the priority lines. And this a $500 modification. Mel invented this, he told Schmidt about it, and Schmidt asked SDS about it. They said they didn’t know anything about it and Schmidt went through the roof. So he made a tremendous row and got SDS to put it in.
So much for the modifications to the memory. The other thing about the memory is the relabeling, and that’s complicated. We will discuss it in some detail. Built into the system are 8 six bit registers which we usually draw like this. (see fig. 4) These are 48 flip flops. Each one of these six bit registers, which ‘e number zero to seven, is divided up into a five bit field and a one bit field, called A and R. When the computer addresses memory, it does so by generating a 14 bit address field. It goes through all kinds of gyrations: direct and indirect addressing, indexing, anything it wants, to generate these 14 bits. When it’s all finished it has the 14 bits which are the effective address and it ships them out to the memory
In between is the relabeling box, or the map. These terms are synonymous. The function of the map to make some kind of transformation on these 14 address lines and ship out some new address lines to the memory. In fact, there are 14 lines coming in here, 14 bits of address, enough for 16K. We have 65K of real core, so 16 lines have to come out of the map. Now the question is, how does this map work? It takes these 14 bits that come in and does some transformation and ships out 16 bits. It could be any transformation. You could run the bits through a random number generator and you could produce 16 new bits but that probably wouldn’t be good. You could add 50 to the address. That wouldn’t be too good either because you could have done that in the computer already.
Q Is the 930 memory extension register involved?
A Memory extension has nothing to do with this scheme and is never used. What this box does is the following: it takes a14 bit address and divides It up into eleven bits and three. The latter is called the page number P and the former the word address W. Pages are called blocks too. So eleven bits are shipped off to the side for the moment and we don’t worry about them. The top three bits of P give us some number from zero to 7. We use this number to select one of the 8 relabeling registers over here. We take the A field out of the appropriate register. Now we are going to make a new address which we are going to get by keeping the W field and gluing on the front of it A., which is the five bit field. we get from the relabeling register. The situation we have is a transformation yielding 11 bits of W field and 5 bits of A field, or a 16 bit address. We got these 5 bits of A field by using the 3 bit P field to select one of 8 relabeling registers. So we now have a 16 bit address, and this is the address we feed to the memory.
The significance of this is that there are 8 pages in the memory that the user can address, and we can make an arbitrary transformation, we can say that each individual one of these 8 pages is going to some page of the physical memory. In physical memory there are 32 pages of 2K each. In addressable memory, virtual memory we call it, there are 8 pages. These 8 registers define the relationship between the 8 pages of virtual memory and some combination of pages of real memory.
Now, there are a couple of little points. If the A field is zero and the R field is 1, then that is regarded as an error. The hardware generates a memory trap. That’s one of the four traps explained above. The second kind of trap was for memory violations. And the way you get a memory violation trap is to go through a relabeling register with 40 in it. That’s an error.
The R field is used in the following way. When the CPU ships out the address, it also ships a signal which says, “This is a load”, or, “This is a store”. And if it is a store and the R bit is on, that causes a read only trap. Thus, the R bit is turned on in each page which you want to protect from being changed. Whenever a relabeled memory reference for a store is generated and the R bit in the corresponding relabeling register is on, that causes a read only trap, which again goes off to a special place in the system. So this means that when you set up the relabeling, you can define for each virtual page whether it is protected from storing.
Note that real page zero cannot be made read-only, since 40 (100 000?) is interpreted as an error at all times. This particular convention is at variance with all the rest of the rules. So the number 40 is interpreted in a special way. Zero is interpreted in the normal way, as referring to real page zero.
For the pages of virtual memory that are unassigned the monitor will put 40 in the corresponding relabeling register. There is no reason why you should have 16, 000 words of memory assigned to you if your program doesn’t use 16, 000 words. It’s a big waste of real memory. You should have only as much memory assigned to you as you need. So what the system does is to assign as much memory as it thinks you need ( exactly what this is will be discussed later). It will put 40 in all the other relabeling registers. Relabeling register, there will be a trap generated by the hardware. The trap goes off to a specific routine in the system, and this routine will try to figure out what to do, whether that really is an error or whether it should assign you some more memory.
Q If I put a zero in one of the relabeling registers is or is not that an error?
A No, that means that virtual page will correspond to real page zero.
Q I want to protect users from violating the monitor?
A Then I just never put zero in the user’s relabeling.
Q Is the user free to change it on his own?
A He can change his pseudo relabeling, and when he does we check to see that he is doing it legally. When we discuss pseudo-relabeling, which we will do in great detail, you will see exactly what the restrictions are and how he can change this relabeling and what the relationship is between pseudo-relabeling and real relabeling. It is completely impossible for the user to ever get real block zero in his real relabeling.
Q How does he alter the monitor?
A Only by making a very special system call which causes very special things to happen. This machine has two instructions called POT and PIN (parallel output and parallel input). If you say POT OUTLOC it finds location OUTLOC and takes the 24 bits from there and puts them out on 24 lines and that’s all it does. What happens to the 24 lines is someone else’s responsibility. PIN likewise looks at the 24 lines and sticks them in the memory word addressed. What happens to these 24 lines after a POT is determined by what you do immediately before the POT, and what you normally do immediately before the POT is an EOM. So before the POT you specify the destination with an EOM. The EOM will have an address field which will be interpreted by the hardware to set some flip flops, which will decide what happens to the information provided by the POT.
In particular there are two EOMs for setting relabeling register one and relabeling register two (relabeling register one being the first four of the six bit relabeling registers and relabeling register two being the second four). The way you set the relabeling registers is to say EOM 20400B; POT RR1; EOM 21000B; POT RR2, and the contents of RR1 and RR2 will be used to set the relabeling. There is no way of reading the relabeling registers; you are just supposed to remember what you put in them.
Q You said if you put 40 in a relabeling register you got a memory violation when you address it. How did you get that?
A When you do this POT, you are outputting a certain memory word which you address. So you put into that memory word whatever you want to have in the relabeling registers.
Q This is done by the system.
A Yes. The system sometimes sets up the relabeling with 40 in some of the relabeling registers.
Q Why?
A Because it doesn’t want you to have 16K of memory. If you have a 4K program it’s ridiculous to assign you 16K of memory because this takes up 16K of valuable cores.
Q Just clear up one point. You never give the EOM and POT instructions to set the relabeling registers?
A Who’s “you”?
Q The user.
A The user can’t give an EOM—it’s privileged. Only the system sets the hardware relabeling. The next question is we have all this glorious machinery, but when it it used? The answer is this: all memory references generated by a program running in user mode are relabeled. Addresses generated by a program running in system mode are not relabeled. However, if the instruction has the sign hit set then the address normally will be relabeled. Furthermore, if the instruction goes indirect through a word that has the sign bit set addressing will become relabeled from that point on. In the assembly language setting of the sign bit is indicated by a , 4: LDA 0, 4. The thing following the comma is the number which tells what is supposed to go in the top three bits of the instruction word. 0, 2 mean indexing, 0, 4 relabeling (in system mode only). You could write 0, 6, which would be both. You can also set the third bit with 0, I, but that is the POP bit and you normally don’t set it this way, but with the opcode.
Q There was something about the sign bit indicating relocation in the 930 manual?
A The significance of that is that the standard 930 loader interprets that top bit as determining whether or not to relocate the address. It’s strictly a software function. We do not use it that way. This is the explanation of how you get relabeling in system mode. The sign bit of the instruction is set, or the sign bit of some word in the indirect chain is set and soon as you see the sign bit on you switch over to relabeled addressing. In the indirect chain you continue to relabel all the addresses after this point.
Q Why isn’t it possible for the system, the assembler, to set that bit for you?
A The assembler doesn’t know what you mean. If I am writing a system mode program, there is a definite difference between writing ABC and writing ABC, 4. And the assembler has no way of figuring out which one I meant.
Q The assembler could do something like this: when the program exceeds the page then all references—
A That has nothing to do with it. The significance of the bit is whether the system wants to look in the user’s memory. For instance, when a SYSPOP is executed and you come out to the part of the system that is executing the SYSPOP, you will have to look back into the user’s memory for the address of the argument of the SYSPOP. This will be done by invoking relabeling. That’s why we have this rule about indirection and sign bits which we discussed earlier when I was talking about EAX. When you do a SYSPOP the hardware sets location zero to contain the address of the SYSPOP and turns the indirect bit on. If the call came out of user mode it turns the sign bit on also. The same thing is true, by the way, of BRM. When BRM stores that link in system mode (for instance after an interrupt) it stores one or zero in the sign bit depending on whether it came out of user mode or not. So there is always this convention that an address which is relabeled has the sign bit on; a full word which contains a relabeled address has the sign bit on. This means that whenever I indirect through that word I automatically get relabeling activated without saying specifically that I want it. This is very nice. You don’t have to think in the program about whether relabeling is being activated or not.
Q Do I have to set the sign bit in user mode?
A In user mode everything is always relabeled. No, it would be disastrous if the user addressed anything absolute.
Q What happens if I set the sign bit in user mode? Does it matter?
A No, it has no effect in a regular instruction. If the POP bit is set, then it becomes a SYSPOP. In user mode if you execute a POP with the sign bit on, that is the signal that says “ This is a SYSPOP , go to system mode”. Normally if you execute a POP in user mode everything is done in the normal way: you put the link in user location zero and you transfer to user location 100 plus the address of the POP. If you put the sign bit on, this is a signal that says SYSPOP, put the link in absolute location zero and transfer to absolute location 100 plus the address. In those 64 words the system will put 64 links, 64 addresses which branch off to the 64 routines which are handling the 64 SYSPOPs. From there on it will do whatever it sees fit.
So the sign bit has two functions. The first thing it’s used for is to indicate relabeling in system mode. The second thing it’s used for is to indicate a SYSPOP in user mode. The third thing this bit is used for, which is really an adjunct of the first thing, is this: if I’m in system mode and I do any kind of transfer to a relabeled address, I automatically go into user mode. Suppose the user has executed a SYSPOP, which means that the link has been put into location 0. I start executing the SYSPOP, the SYSPOP goes cruising along and executes and finally it finishes and wants to return. The way a POP normally returns is with BRR 0 which means transfer to the address given in 0 plus one, which is exactly what you want. So the SYSPOP does BRR 0. Now what happens? The BRR goes off to 0 and it says “I’m supposed to go to this address plus one”, so it figures that out. Then it looks at the sign bit and it says, “Is that address relabeled or not?”
If it’s not relabeled, if the SYSPOP was called out of system mode it just goes off to the absolute address that was specified. If the SYSPOP was called out of user mode, then it will go back to user mode automatically, because a transfer to a relabeled address sends you back into user mode. This means that the SYSPOP returns immediately into user mode without any disturbance,, , with having to say explicitly to the hardware, “I want to go back to user mode. “ Everything is taken care of by this bit being on or off. A system mode routine can also go into user mode explicitly, as it were, by writing BRU*+1, 4.
Q Where does the POP find the sign bit?
A The sign bit can be anywhere along the chain of words you go through to get the address. So that, in particular, it can be in the instruction itself. For instance, I can do BRU AC, 4. The sign bit means that I will take ABC as relabeled and when I transfer to ABC I will go into user mode. If I do BRR 0 and 0 contains an address with the sign bit set, then the 0 will be taken as an absolute 0 since I’m in system mode and I go to absolute 0, BRR is similar to indirect addressing—so it works the same as BRU indirect. The only difference from BRU indirect is that it adds one to the address. So I go to this word, (0) which is absolute, and I say “Aha, I am still running down the chain”, so I have to add one to the address in O. Now I have to look to see if the next step is to be relabeled or not. The sign bit in 0 being on means that I’m now relabeled.
Q So the address that you go to has the sign bit?
A The word containing the address has the sign bit. I called a SYSPOP. It’s definitely not necessary for the word I return to have the sign bit on. That has nothing to do with it. The word that has the sign bit on is absolute.
Q You have your BRR indirect or whatever you have. It picks up the address and where the address is is where the sign bit is to be on?
A That depends. If it goes indirect the sign bit is anywhere in the addressing chain. It could be set in the instruction. That is not the way it usually is, but it doesn’t matter how it usually is. The point is to understand what the hardware does. It is not helpful to try to understand what it usually does, because then if it does something unusual you’ll foul up. What the hardware does is to look at the sign bits of all the words involved in the addressing chain, starting with the instruction and working down as many levels as is indicated by whatever the instruction says and whatever indirect bits may be on. Anytime during this chain when it finds the sign bit set, it switches to relabeled mode. When it’s all finished if it winds up in relabeled mode and if it’s a transfer instruction, then it transfers to user mode a t the time it does the transfer.
Q How does it know when it’s a transfer?
A Because if it’s BRU it says transfer. The transfer instructions are BRU, BRM, BRI, BRR.
To summarize the action of relabeling, there are 8 six bit relabeling registers, customarily drawn as in fig. 4. When I generate a relabeled address and the hardware ships it out to the memory, it ships it out along with a line that says relabel this before you send it to the memory. That means it goes through the relabeling box. What the relabeling box does is to separate the top 3 bits from the bottom 11 bits—11 plus 3 equals 14—take the 3 bits and use them to look up one of the 8 six bit relabeling registers. It takes the bottom 5 bits of those 6 bits and glues them on the front of the 11 bits, getting a 16 bit address. And this is the address it uses to reference absolute, real memory. This means that these 8 registers can be regarded as defining a map. They are explicit tabular definition of the map from the integers 0 through 7 to the integers 0 through 63. In this way each of the user’s virtual pages which he can address with 16K of address space is associated with one of the 32 pages which exist in the real memory. This association is completely arbitrary. The fact that virtual page 0 is associated with real page 23 has no connection with the lac* that virtual page 1 is associated with real page 14 and that virtual page 2 is said to be illegal because 40 is in the relabeling register. Each one of the 8 pages operates completely independently of all the others.
Q You’ve got 5 there, 5 bits gives you 32 pages, each 2K long, so you have 32 chunks of 2K each and 2K address portion is the 11 bits, the real page number itself is 5 bits, the page number is the 3 bits which give you 16K?
A Of virtual memory, right. Which is translated into 65 K of real memory.
Q The map is set up on a dynamic basis by the system itself?
A Correct. When the system finds a particular user it figures out from its tables which blocks of memory it has put the user’s program in and sets up the relabeling so that the user will see what he expects to see, regardless of how much convolution has been going on in the memory since the last time the user was around. You see, horrible things can happen, the user gets dismissed, he gets swapped out, lots of people come in and out and a long time later he comes in and he is just not anywhere like the same place in memory that he was in before.
Q Also the program can be non-contiguous?
A Right. Obviously, there is no relationship between one page and the next.
Q It is non-contiguous as far as pages are concerned but it is also non-contiguous as far as memory banks is concerned?
A The memory banks are interleaved. Nobody sees that except way, way down in the hardware. It is even possible to give two virtual pages to the same real page. You can do anything. What I’m trying to explain is the hardware, and you should understand it well enough so that you can understand all the things that can be done with it regardless of whether they are reasonable or not. It’s hard to tell beforehand which ones are reasonable and which ones aren’t. If you understand the hardware then you will be able to figure out any application regardless of whether it initially seems reasonable or not. If you try to understand it on the basis of what you want to do now, then you are just going to get confused when you find somebody doing something that is not what you originally had in mind. The hardware doesn’t care what you want to do. It says, “You give me certain bits and I’ll do certain things.” It’s very well defined and not too complicated and the most important thing is to understand exactly what it is the hardware is doing in terms of bits received and bits transmitted.
Q How long does relabeling take?
A It takes 20 nanoseconds but that’s slack. It’s 20 nanoseconds being wasted in the 930. In fact, there’s a lot more than 20 nanoseconds being wasted in the 930 at the moment. Relabeling is a trivial operation, a table lookup, and you can do it very fast. There is no logic required and you are not comparing anything with anything else, or doing anything the least bit complex.
Q How long does it take to set the register, about 7 microseconds?
A To do a POT takes 3 cycles, so the EOM plus POT takes 4 cycles. There is one more thing to be brought up which is a minor extension of what we already have. In addition to these 8 relabeling registers there are 2 more which are regarded as being part of another full word in which the other 2 registers don’t exist. This is called the monitor relabeling, the monitor map. The significance is the following: normally when the monitor addresses memory, if it has not been relabeled, it gets absolute memory. If the monitor addresses location 4720 it will get absolute location 4720 in the real absolute memory. We have put in the following little gimmick, however: if the monitor addresses something in the top 2 pages of its absolute addressing space, that is, if it addresses anything above 30, 000, it will be mapped automatically even though relabeling wasn’t specified, and it’s mapped through these additional registers. The reason for that is that the monitor can refer to memory which is neither absolute nor part of the user’s current relabeling without having to change the user’s current relabeling. For instance, the way these registers are used is that the top block is always defined to be the temporary storage block for the current user, which means the monitor can get at the information in the temporary storage block for the current user without having to do any relabeling twiddling. You can’t do that absolute, because that block is swapped like everything else. The way we used to handle this problem is that the monitor would have to explicitly change the relabeling. We had to get a word which has the relabeling for the temporary storage block, POT it out into one of the two regular relabeling words, and then fix that back up before going back to the user. But that was most unsatisfactory and this is much better.
Q Is that the zero page in the user’s core?
A No, the temporary storage block is something the user himself never sees. It’s block in which the system keeps the information about the user which it needs, as well as the drum buffers. The user never has access to that block. It’s a disaster if he gets access to it. It’s almost as bad as getting access to the system proper because all kinds of pointers and things are there—the system, for instance, keeps in that block information about what the user’s relabeling is, and a lot of other information like that. That block is sacred.
Q Another thing I don’t understand. You say the top 2 pages of the monitor itself are mapped, above 30, 000. If the monitor operates like a user, how does it have more than 16K?
A 30,000 octal. Addresses are always in octal. Sizes of things are often in decimal but addresses are always in octal.
Q Will you tell us exactly what goes into that monitor map?
A I’m talking about the hardware. You can put anything in it you want. These are two registers which operate exactly the same way as the 8 user mode relabeling registers. The only thing is that what invokes them is a little bit different. In particular, the way the hardware works, of course, it that it looks at an address coming out from the monitor. The address is again divided up 3 and 11. We want to map the top 2 pages. That means that we want to say, “If these 2 bits are one, then we are in the top 2 pages. Use the next bit to select a monitor relabeling register.” Instead of using all 3 bits to select one of 8 registers, the way it does in user mode, it only activates relabeling if the top two bits are ones, and uses the third bit to select one of the two registers.
Q What about the extension registers?
A They’re not useful. They’re much too difficult to handle and they can only address 32K and generally they’re not—they’re just very inflexible and confusing and not at all nice.
By the way, the monitor registers don’t have read only capability. That’s not a fact of any great significance, because the monitor, which is the only person using them, is supposed to know whether it should clobber the system or not.
There’s one more thing to cover under modifications to the hardware. There were four traps which we listed earlier, and we discussed three of them—illegal instruction, memory violation, and read only traps. There is one more trap, which is called the user mode trap, and its significance is that if it is on (it can be turned on or off by an EOM), whenever a transition occurs to user mode by way of a branch to a relabeled address (that’s the only way you can get a transition to user mode) the branch will be suppressed and the trap will occur instead.
Q What was that again?
A The user mode trap can be turned on or off, and when it’s on whenever a transition occurs into user mode, which happens by way of a branch to a relabeled address, the transfer will be suppressed and the trap will occur instead.
Q What is it for?
A If the clock interrupt occurs which says the user should be dismissed and you are in the middle of a SYSPOP of some kind you can’t dismiss him right away because you may leave the system in a bad state. You have to wait until the system is finished and goes back to user mode. In user mode you can dismiss him at any time, but you can’t necessarily dismiss him in system mode because the system may be doing something, and the clock interrupt routine doesn’t particularly know what the system is doing. What this means is that when the clock interrupts and figures out that it should dismiss the user, it looks to see whether it came out of system mode or not, which it can do so by looking at the sign bit of the address stored by the BRM. If it came out of user mode it dismisses him right away and if it came out of system mode it turns on the user mode trap. This means that when the system finishes whatever it was doing and goes back into user mode, a trap will occur and at that point the user will be dismissed. This sounds trivial, but it actually turned out to be quite important. The way we were handling this problem before is that the clock would set a flag, and practically every single exit from the system into user mode would check this flag, which was a damn nuisance, somewhat wasteful of time and very inconvenient.
Q Does this guarantee a certain number of microseconds of processing time?
A That is not the idea. The system can continue in system mode as long as it wants. Unless there is a bug in it, it is controlled and it doesn’t stay in system mode for very long. That covers the modifications fairly exhaustively. These things are all described in the paper which is referenced in the outline. Some of them aren’t; the user mode trap and the monitor map were added since this paper was written, but most of the things are described and many of them in some detail.
We ought to conclude by describing the unusual pieces of hardware that are attached to the system. Interrupt arming we already discussed. The clock is very simple, it’s a device which 60 times a second generates an interrupt, a very high priority interrupt, higher than anything except power fail. 60 times a second you get this interrupt. What you do with it is up to you.
Q Doesn’t the system keep track of it?
A The system keeps track of lots of things. It increments various counters, and decides whether it should dismiss people and one thing and another. But we will do that all in detail when we look at the system proper. We are looking at the hardware at the moment.
Q There’s only one clock?
A There’s one clock. Right. It generates an interrupt 60 times a second. Every time an interrupt occurs the system does something. Usually it just increments or decrements a counter. Under some circumstances it will do more things.
There’s the teletype interface, which is a box called the CTE 11 which is provided by SDS. Its characteristics are roughly the following: a lot of wires come into it. Something is on the end of these wires and this something has to have certain properties; it sends things down these wires in the certain way. If it sends 10,000 volts down the wires it will blow up the teletype interface, so it’s got to do something reasonable! It doesn’t have to be a teletype; it just has to be something that looks like a teletype. On the other side is the computer. There are the following connections: 24 lines, the POT-PIN lines, and there’s an interrupt line, or two interrupt lines. Whenever a character comes from the teletype, the teletype interface generates an interrupt. The computer in processing this interrupt does a PIN which reads 24 bits from the teletype, from the POT-PIN lines. These 24 bits contain two pieces of information: the number of the channel on which the character was input and the character itself, 8 bits o character.
Q There are eleven bits per character?
A Three bits are not part of the code, but are used for synchronization. Eight bits are the code. On output the CPU does a POT out to the teletype in which it specifies a teletype number and a character to be output. This character goes and sits in a buffer in the interface, and the interface does what’s necessary to output it. When the output is finished, after 100 milliseconds, there is a little timer, which causes the interface to generate an output interrupt. The CPU can do a PIN and find out which teletype is responsible for the output interrupt. The significance of the output interrupt is “I’ve finished outputting that character. You can give me another character if you want”. In this way the CPU can read input from the teletype interface and send output to the teletype interface. In both cases the teletype number as well as the character involved is sent.
There are two interrupts which the teletype system generates, one to say “I’ve got a character ready for you to read”, and the other to say, “I finished outputting what you told me to output and I’m ready to output something else.” Individual channels on the teletype interface operate, from the computer’s point of view, complete independently. Any interrupt may come from any of the channels and the fact that output is going on in another one. Those are the essential characteristics of the teletype interface hardware.
Q Do you have an interrupt for each teletype?
A No, two interrupts in all. It’s because there is only one interrupt for input and one for output that you have to provide the teletype number in the POT-PIN operation. This is obviously better because with 64 teletype it is ridiculous to have 128 interrupts.
Q Why is it that it works on a character basis than on a double character basis, for instance?
A Because you don’t want to work that way. You want everything character by character. That’s one reason. Another reason is that if you work on a double character basis, you have to twice as much buffering in the interface. The buffering represents about 2/3rds of the cost of the teletype interface, and it would be expensive to have more. If the interface has to collect—for instance, if you use the double character scheme for output—you ship two characters instead of one to the interface—the interface has to have storage for those two characters instead of for just one.
Q Doesn’t it have 24 bits for the 24 lines?
|
Char |
0 0 0 0 0 0 0 0 |
tty# |
|
0-7 |
8-17 |
18-23 |
|
PIN/POT Lines | ||
A Oh, no that’s quite different, there’s no 24 flip flops there. The way these lines are set up is this: a lot of them are always zero, the ones in the middle. The 8 lines for the character come from a character buffer, and the lines for the tty number come from some unary to binary decoder which sees line such and such and encodes it into binary. When you do the POT you send out 24 lines, 24 bits. When you PIN you read in 24 bits. Those 24 bits contain a character over on the left-hand side, the teletype number on the right-hand side and zeros in the middle.
That’s the hardware. What you can do as a user is very involved and is one of the things we will spend quite a bit of time on. There’s a lot of machinery associated with making the teletypes work the way the user wants them to work.
There’s one more piece of significant hardware and that is the drum or RAD and I will probably call it drum most of the time. This is primarily a swapping device. It operates at half core speed, full core speed, or one-quarter speed depending on what it is. The RAD operates at quarter core speed, and it runs over a special direct access to memory channel (DACC). Normally it is run with blocks of reasonable size, either 2000 words at a clip or 256 words at a clip, depending on whether it is being used for swapping or for file storage. Physically I believe the RAD can operate on units as small as 64 words. It is basically like any other I/O device with one exception. The channel has a little gimmick in it called the channel map. Memory is divided up into 2000 word pages, so that in the user’s relabeled memory absolute address 13777 may be right next to absolute 50000, because the pages are completely independent. If the user says, “I want output from 3700 to 4300, one 256 word block, this is normally read or written from one 256 word block on the RAD. The RAD channel works on absolute memory addresses, not on relabeled addresses, and this means a serious problem here, because this 250 word block is not a single block in absolute memory. If we start at 13700 and end at 50277 there is no way to tell the channel that we really want 13700 to 13777 and 50000 to 50277. The way the situation is corrected is the channel has a small map in it which essentially allows it to say, “When I cross the page boundary, I can switch from absolute addressing to addressing through the map, which allows me to get a different
The scheduler is what decides when programs get run, when they don’t get run, what happens when they have to wait for I/O, what happens if they compute for too long, etc. ‘The relevant section of the working document is section 2. The relevant section of the listing is the huge package called SPAC. PAC stands for “program active”, and this section of the listings contains a large amount of code. It contains the scheduler code at the beginning where it says “Scheduler” in the comment, and then it contains a lot of code associated with forks and a lot of code associated with the swapper, which we will have occasion to discuss later.
The idea is the following: there are these things in the system called processes. They are sometimes also called forks. In fact, they are always called forks in the working document. I will probably call them both. A process is a collection of information which suffices to allow a program to be executed. Looking at it in another way it is an entity which can execute instructions. The way a process is defined is this: suppose a process has been set running by some mystical process and we want to stop it. A process is defined by all the things we must save when we stop it if we are to start it up again in such a way that it will not know it has been stopped. What are ,these things? First of all, there is the map. Then there are the central registers, the A, B & X registers and the program counter. Besides that there is some kind of status information which says why we stopped it and when we should restart it. In actual fact there are some other things that are used to define a process besides these which have to do with other features of the system. These will be discussed later on.
All this information for each process is kept in a table called the PAC table or program active table, which you will find in the working document immediately following page 2-1.
Q Is there one of these for every active process?
A There is one of PAC table entry for every process, every active program, every fork, every whatever you want to call it. And it is this entry which essentially defines the program. If you have one of these you have a process and you can run it. If you don’t have one of these you have nothing. That’s what an active program is and these active programs are the things with which the scheduler deals. Each one of them, as I have said, is defined by a PAC table entry and is identified to the scheduler by its index in the PAC table, which is a negative number called PACPTR, a number which you will find occurring throughout the system. The significance of PACPTR is the following: that there is a bunch of symbols in the system called PX, PL, PB, etc. , etc. which you find running down the left hand side of the page 2A, and if you write something like this
LDA PL, 2
and you have PACPTR in X, you will then get PL word for that particular program, for the program identified by PACPTR.
Now the meaning of this from the point of view of the PAC table is the following: if the PAC table is a section of core, PL, PB, etc. are symbols whose values are addresses at the end of this section, and PACPTR is always negative. The first program in PAC is the one in the earliest core locations and has the biggest negative PACPTR. The smallest negative pack pointer is -12, since a PAC entry has 12 words. The size of PAC is a parameter; it is defined in MSYMS. Why the PACPTR is negative I’m not exactly sure, but we are now irrevocably committed to its being negative because there are lots of places where we do SKN.
PACPTR is the handle on the program and whatever you do with this active program, whether it’s running or whether it’s sitting on some queue somewhere waiting for this or that it is always identified by this number. If you ever get an entry in the PAC table which has no PACPTR pointing to it, then that entry is lost for good; you’ll never find it again. The next question is the following: suppose we have an active program—suppose we have lots of active programs—we have the following obvious problem. We can’t run them all at once, since we have only one CPU, so we have to run them one at a time. This means that first of all we have to be able to start them up and stop them. Secondly, we have to have some sort of rule for deciding which one we run next.
Q Where is the PACPTR kept?
A It depends. It’s just a number; you can put it anywhere. It may sit in some table or be in some queue entry, or anything. There is a word in the system called PACPTR which holds the PAC address of the program currently running.
Q How do you get it?
A Who is “you”?
Q The user.
A The user never sees a PACPTR. He has nothing to do with that. Remember, he doesn’t know that there’s time-sharing going on. He just has this big computer to himself.
Q This is set up in the beginning?
A When the monitor establishes a process it finds an empty slot in the PAC table for it. Maybe I should explain about that. There is this thing called the free program list, FPLST, which is essentially a list chained through all the empty entries in the PAC table. When you need a new entry in the PAC table, you pick one off the front of FPLST. And in the very beginning of the world the monitor sets up FPLST by putting all the entries in the PAC table on it. When you need an entry from the PAC table you take one from FPLST, and when one becomes obsolete you put it back on FPLSTT.
Q How do you know which number is the number for PACPTR.
A For what? Which number? For what PACPTR? That depends on which program it is for. Suppose a program is dismissed because it’s waiting for teletype 64, Then presumably somehow associated with teletype 64 there will be a word which contains the PACPTR of the program that’s waiting for teletype 64. When teletype 64 comes along and says “O. K. , it’s time to go”, you can find in that location the PACPTR for the appropriate program. Exactly how these things are organized is the function of the various parts of the system. You’ll see lots of places where PACPTRs show up. I can take PACPTR and put it in cell 103 and then I can come back later, take it out of cell 103 and do something with it.
Q But it’s usually kept in one place?
A No, it’s kept in lots of different places depending on what’s going on. The program will get dismissed for all kinds of different things, and PACPTR winds up in all kinds of different places.
Q Including the program?
A The program itself never sees its own PACPTR. It doesn’t know about that, remember?
Q Are there quite a number of these things, of PAC slots?
A It’s a system parameter how many there are. Look in MDBG and MSYMS.
We now proceed to discuss the operation of the scheduler. First, activation and dismissal. First of all, if a program is running how can it get dismissed? A dismissal occurs as the result of one of the following things: You might be waiting for I/O. For instance, you ask for a character from a teletype and the character is not there yet because the guy went for coffee. So there’s no character. Well, it’s ridiculous to leave you sitting there waiting for the character tying up the CPU while the guy gets his coffee. You get dismissed and eventually when the character arrives you get reactivated. Or alternatively, maybe you have 350 characters to type out. If the teletype output buffer is only 30 characters long, you ship 30 characters out one at a time to the teletype. Then you come along with the 31st character and there isn’t any room for it. So you have to be dismissed until there is more room. Again, you could request dismissal explicitly, usually on some specified condition like time or waiting for another process, or some other thing like that. Finally, you could compute too long; that’s called quantum overflow. Those are the important things.
So basically there are three ways to get dismissed: you could be dismissed if you asked for 40 that’s not ready, because of your explicit request or because you computed for a long time and the computer decided it was somebody else’s turn. Of these three kinds of dismissal, two are produced by your explicit request to the system. The other is produced essentially by an interrupt (the clock), and is involuntary.
Q What is the amount of time for which a program gets to run?
A It is defined in a very complicated way which I am about to explain.
Q How long can a program wait for a character, say, before it gets dismissed?
A If it asks for the character and the character is not there it gets dismissed immediately. You don’t sit there waiting for the character. That’s ridiculous because the time involved in getting the character is very long compared to the time involved in the CPU. At least 100 milliseconds, even if things are going full blast.
You’ve gotten yourself dismissed. Now the next thing is how you get reactivated. That is controlled by a word of the PAC table called PTEST. The exact details of how we get PTEST set up will be discussed in a minute but significance of PTEST is the following: it contains essentially two pieces of information, the activation condition and an address of some kind. The activation condition happens to be kept in the opcode bits of the word, and the address is kept in the address field. This is not essential.
Q How do we reactivate? What do I have to do, look at PTEST?
A Somebody is going to look at PTEST to decide about reactivation. Now the exact way in which we do that we will get to in a minute, but I want to explain how activation works first.
When the program is dismissed the thing that dismisses it will know why it’s being dismissed. Maybe the teletype routine is dismissing it because it asked for a character and none is there. Or maybe the drum routine is dismissing it because it asked for drum I/O and there are already six other people waiting for the drum so it’s down in some queue somewhere waiting for the drum. Or maybe it’s being dismissed waiting for 3 o’clock. The routine to process dismissals waiting for 3 o’clock knows it’s until 3 o’clock that it’s supposed to be waiting. In any event, whoever is doing the dismissing knows why the thing is supposed to be dismissed. If the dismissal is because of the quantum overflow there is no particular condition for reactivation. If the computer gets around to the process, it should be reactivated There are lots and lots of dismissal conditions. There are dozens of different things which can cause dismissal, many different kinds of I/O conditions and lots and lots of specific requests. The idea is the following: you do not want the scheduler to be aware of all these details of different possible conditions for reactivation. If it is, it has to know far too much about other parts of the system. We would like to have the scheduler decoupled from other parts of the system as much as possible. In other words, we would like to have a mechanism by which the scheduler really only knows that it’s supposed to go to some word and look at bit 23. If bit 23 is on the, program is activated, otherwise not.
Somebody else is responsible for how bit 23 gets turned on. If it’s the teletype dismissal, the teletype should be responsible for figuring out that “I should turn bit 23 on”, the scheduler is only responsible for looking at bit 23. In fact, we don’t even have the ability to look at bit 23; we have much more simple—minded things than that. The activation conditions are listed on page 2-4 of the working documents—and you see that there are not very many. The most commonly used ones are 0, 1, 2, and 3, which essentially say “Go and look at the word in the address over here and find out whether it’s >0, ≤0, ≥0 etc
For instance, the simplest possible way you could handle a dismissal would be the following: you dismiss the program until a word is ≤0 and set the word to +1. Then when it’s time to reactivate the program the interrupt that gets it reactivated sets the word to -1. Then the next time the scheduler comes along and test the activation it will say, “Aha, time to reactivate the guy”. Is this mechanism clear to everyone? This is quite important. The significance of it is that scheduler which decides to activate is decoupled completely from the routine which decides whether activation is permissible. Communication is achieved only through contents of certain memory cells. There are some activation conditions that are sort of funny and do have a little bit of relationship to the real world, like number 3. which is word !’c teletype early warning, early warning being a system parameter which says essentially how many characters you should allow to pile up in the teletype input buffer before activating a program. We’ll discuss that in more detail when we get to the teletype logic. And number 4, which refers to time delay, has an explicit reference to the c lock. Number 6, which is sort of funny one, word equals address of word plus 2, results from the conventions used in the I/O part of the system. All the I/O buffers have the form of 2 header words followed by the data words. The buffer is in some sort of initial state when the first header word points to the first data word, i. e. , points to the second word after itself. That’s the reason for condition 6.
Q Why don’t you show what happens in a typical I/O operation?
A Okay, suppose I am a program executing a TCI. I go bouncing off to the teletype routine and the teletype routine looks to see if there are any characters. Now there’s a word somewhere that says how many characters there are in the teletype buffer, It looks at that word, that word is zero. No characters. So the teletype routine sets up the activation condition, and the activation condition is this: there is a word in the teletype table which essentially says “It’s time to run this guy now, because a break character has come in, “ when it is positive; every break character increments it by 1. So when the teletype routine recognizes that it is time to dismiss the guy it sets the word to -1, and it sets up an activation condition which says activate on word non-negative. This means that every time the scheduler tests this condition it’s going to ask “Is this word > 0? “ and the answer is going to be “No”, as long as no break character comes in on the teletype. When the teletype interrupt routine is fired up by the arrival of a character and it observes that this character is a break character, it will increment the word.
Q This allows you to completely decouple the scheduler from all the routines that might cause an interrupt in the program?
A Exactly and this goes both ways. The scheduler doesn’t have to know about them and they don’t have to know about the scheduler. All the teletype interrupt routine knows is that if a break character arrives there’s this magic word it’s supposed to increment. All the scheduler knows is that there’s this magic word it’s supposed to look at to see whether it is negative or not. That’s the extent of the communication.
This, by the way, is a technique used throughout the system and explains many things which you otherwise might find extremely puzzling. The system is not organized on the basis of a subroutine which calls 6 second level subroutines each of which calls 6 third level subroutines etc. Very rarely do you call subroutines to more than two levels. Communication is always accomplished through tables in memory, and what happens is that one routine will set up a table and then it will go away. Later on some interrupt will come along and fire some other routine which will look at that table and on the basis of what it sees it will decide something. This is the philosophy on which the system is written. It is not the way most programs are written and is a little bit difficult to understand.
Q What’s a break character?
A A break character is a character which essentially says that the program is supposed to pay attention to this character right away. We’ll discuss that in more detail when we get to it.
So enough on activation and dismissal. Now, the question now is how to organize all these programs? Say we have three programs that are dismissed that are waiting to run. How do we organize them? Somehow the scheduler will have to be able to find them so it can look at their PTEST words. The stupidest way to do it would be to say “The scheduler will scan the PAC table, starting at the beginning and going to the end, and it will check the PTEST at each slot”. This is how we did it for a while and this system has the virtue of simplicity; there’s nothing to get out of order. There’s really a lot to be said for having a big table and just scanning it, because you don’t have lists and queues and little pointers and things and there’s so many fewer littler pointers that can be pointing to the wrong place. If you just have this simple scan there’s no way for the scheduler to get into a loop, whereas if you have a list and the list becomes circular the scheduler will go round and round and round and never gets out. And that, in fact, has happened.
Unfortunately, this scheme is basically not satisfactory in spite of the advantage of simplicity. First of all, it incorporates no mechanism for priority, because the position of the program in the PAC table is fixed and consequently there is no way of saying “This program is more important” by looking at it first. The second objection is the PAC table is very large and many of the slots are empty or are devoted to programs which are of no interest to the scheduler for. one reason or another. Consequently you waste a lot of time looking at things.
So we established a somewhat more ingenious scheme which involves having three scheduler queues. This mechanism is described rather compactly on page 2-5. The queues are called QTI, QIO and QQE. QTI stands for teletype queue. QIO stands for input-output queue, and QQE is for quantum exceeded, meaning you computed too long, you got time sliced. Whenever a program is dismissed, it is put on one of these queues, and the queues are organized in the following way: Each one has one word associated with it called the header word, and then the queue entries, which are PAC table entries, chained through PNEXT. There will be some programs on the teletype queue, and there will be some programs on the I/O queue and there will be some programs on quantum exceeded queue. The first word of the header for next queue, which in turn points to the first program, which points to the second program, which points to 0. And so it goes. Now we can define the priorities of the programs. There are three priorities corresponding to the three queues. QTI has the highest priority, QIO is the next highest priority, and QQE the lowest priority. You can always add more queues if you like. That’s not very hard.
Q For instance, if a guy comes out of QQE and executes and then is hung up on QTI? There’s no facility to scan QTI and give this guy higher-priority than someone already on QTI.
A No, there is not at the moment. However, there is a standard routine for putting people on queues and you could modify this routine quite easily. The routines called QPUT and QGET are responsible for putting people on queues.
Q All they do is splice pointers?
A That’s right. At the moment there is no mechanism in the scheduler to establish priority.