Time-Sharing and how it's Implemented
In the 1960s and 1970s the BASIC language went hand in hand with Time-Sharing. In this article I talk about how Time-Sharing is implemented.
In this article, I discuss how Time-Sharing was implemented in the RSTS/E Operating System that supports the BASIC-PLUS language. RSTS/E was released in 1972 and designed to run on the PDP-11/45 and later computers. The PDP-11/45 had memory relocation and protection. What this meant was each user had a 64KB address space. Real memory could reach 256KB. Compared to the IBM PC, which came out in 1981, this was still very little memory. The IBM PC could have up to 640KB of memory.
The most important feature of the 11/45 was memory protection. If a fault occurred while running a user’s program, the address space would be re-initialized, on the 11/20 if a fault occurred the entire system would crash and be reloaded, affecting up to 11 other users.
There was a serious bug in the BASIC-PLUS interpreter, if you invoked the SPACE$ function with the parameter -32768% it would crash the interpreter. On the PDP-11/20 this would crash the entire machine. On the PDP-11/45 with memory protection, it would only crash a single user’s job, and would not affect other users.
Time-Sharing with an Event Driven Kernel
The RSTS/E OS was event driven. This meant the OS would enter a Sleep Loop waiting for things to happen. During the Sleep Loop, it would display a rotating pattern of lights on the console. You could easily see how busy the CPU was based on the display of the lights. If the rotating pattern was stable, that meant the CPU was not busy.
During the boot of the operating system it would initialize all the internal data structures and then enter the Sleep Loop. Hardware interrupts were used to generate the events that the operating system responded to. A hardware interrupt acts like a forced procedure call. The machine is looping and is suddenly woken up and forced to call a procedure based on the particular event that just occurred. All the interrupts were Input/Output related, except for one, which was a clock tick that occured every second.
The clock tick was used to forcibly wrest control from a user’s program. For example, if one of the user’s wrote a program that read 10 GOTO 10, the program could spin for one second, and then another forced procedure call would occur when the clock ticked. The RSTS/E kernel would then look to see if another job was runnable. If there was, then it would transfer control to that job, and allow it to run until the next interrupt or clock tick. Let’s say that person was running a CPU intensive program to compute digits of PI. It would run until the next interrupt.
For runnable programs, RSTS would use a round-robin scheduling algorithm. Let’s say we have the two jobs mentioned above, and they are interrupted by clock ticks every second. This would mean RSTS would do 10 GOTO 10 for one second, and then compute PI for one second, and then back to 10 GOTO 10 for another second, and this would go on ad infinitum until one or both of the users pressed Control-C to stop their programs.
If there were more than two programs runnable, let’s say 1, 5, 9, then the scheduling algorithm would go 1, 5, 9, 1, 5, 9, … etc. This process gets more complicated if the combined size of the runnable programs exceeds 256KB of physical memory. In this case, one or more of the jobs must be “swapped” out of physical memory, by writing the user’s memory to a special swap file. This would allow another job to be “swapped” in from the swap file. The algorithm to determine who gets swapped out and who gets swapped in tends to be more complicated. Not only is it necessary to share the CPU through a round-robin scheduling algorithm, it is necessary to share memory through a similar round-robin scheduling algorithm. As you can guess, managing these two goals can get quite complicated, particularly if you want to make maximum use of the CPU, and maximum use of the memory.
Disk I/O is very slow, but the CPU does not need to sleep while the Disk I/O is occurring. The CPU starts an input or output request and then goes on to do other things, like run some user programs. When the Disk I/O is complete an interrupt is generated to notify the kernel. Once again, control is wrested away from whatever is currently running, and RSTS needs to figure out what to do. It will, at a minimum, mark the job that started the Disk I/O as now runnable, and then go back to what was interrupted. Now that the job is runnable when it reaches its time in the round-robin queue it will be given some CPU time. RSTS has to juggle Disk I/O for swapping as well as Disk I/O for user file access. Things are getting more and more complicated. RSTS needs to manage the CPU round-robin queue, the swap memory round-robin queue, scheduling Disk I/O for swapping, and scheduling ordinary Disk I/O for file access.
We’ve seen two major uses of interrupts, Disk I/O and clock ticks. There are slower-paced interrupts that occur each time a user presses a key on their terminal, and each time a character has been displayed on a terminal. RSTS uses what is called full-duplex I/O. What this means is, that a user can type at the same time text is being printed or displayed. This was quite useful on a Teletype because you could start typing the next command while the Teletype was chattering away. It also meant that RSTS was responsible for echoing the characters a user types. Thus, I press the letter A, and the letter A is sent down the phone line to the computer, an interrupt occurs to the CPU, RSTS puts the character into a buffer, and echos the character back to the Teletype where it is printed. This occurs fast enough that there is no detectable delay. An interesting side effect of this is if the computer crashes, the echoing will stop, and the user will hear a click click with no noise coming from the print head.
When a user is typing commands, or responding to prompts from a program, RSTS puts the user’s job to sleep. This allows the job to be removed from the round-robin queue and potentially swapped out of memory. The user can still type, and the keystrokes will be echoed and placed in a buffer. The user is completely unaware that their job may not even be in memory. When the user types a carriage return, RSTS will mark the job as runnable. This alerts the schedulers that a job needs to be swapped in, and once swapped in, the job needs to be put in the round-robin queue to gain access to the CPU.
Not only is typing a slow process, but counter-intuitively printing is also a slow process. Teletype machines could only print 10 characters a second. The CPU is much faster, and an application program can generate text at a very fast pace. So RSTS would use a buffer to collect text coming from a program, and a Teletype device driver would drain the queue as text was printed. When an output buffer was filled, RSTS would put the job to sleep waiting for the output queue to be drained. While a Teletype was chattering away the user’s job is stopped, and may even be swapped out. Once again, the user has the illusion that the computer is dedicated to them.
Filesystem
A major requirement for an operating system is the filesystem. The filesystem is used to save people’s programs and data. RSTS has a filesystem that supports a single directory for each user. Users were identified by project and programmer numbers. When I was in High School each school had one number shared by all the students and one number shared by the faculty. I still remember our numbers were 100,1 and 100,2.
The filesystem is a complex process with complex data structures on the disk. The Unix system has a complex filesystem that allows more than one process to manipulate the filesystem at the same time. This was not the case for RSTS. It was deemed complex enough that they only wanted one user to have access to the filesystem at a time. This was again handled through a round-robin scheduling scheme. Jobs would queue up requests for access to the filesystem. This was done through a File Request Queue Block or FIRQB (affectionately called a Furk-Be). These blocks were handled by BASIC-PLUS and were not visible to the user.
Serialized access to the disk would slow things down to an unacceptable level, so File Requests only dealt with changes to the file directories. The location of sectors belonging to a file were cached in memory and were called a window to the file. Access to the sectors designated in the window required no access to the filesystem, and thus could run at full speed. If the need occured to access sectors outside the window, then a window turn request would be made via a FIRQB request to the filesystem.
Summary
If you read this article and the previous one on BASIC-PLUS, you will have a good sense of how a small Time-Sharing System with a BASIC language incremental compiler was built in the early 70s. Algorithms similar to the ones described here are still used today in Linux systems but with many layers of complexity added to them. Even though Linux is not used as a Time-Sharing system, it still has many processes running at the same time supporting Web Servers, Databases, and lots of other things. You can even have two administrators logged in via SSH at the same time. In this case it looks exactly like the old Time-Shared Unix which ran on a PDP-11/45 and was a contemporary OS to RSTS/E.