Last time we saw how the use of computers had progressed from being under the control of the user to being controlled by computer operators and then the partial control of a program which remained in memory between jobs, the resident monitor.
This lead to the development of the first of the computer control languages, Job Control Languages (or JCLs). We saw that with computer operators an unambiguous sequence of instructions had to be given in order to ensure that our jobs were carried out as we required. Now a formal language must be used because it is to be interpreted by the resident monitor. We will return to look at these in detail later. For the time being you can think of cards with commands such as:
//job for robert
//run FORTRAN
program for robert
//link
//copy to tape robertA
//run
data
Before discussing this in more detail, it should be obvious that to make such a system work requires some form of secondary storage where commonly used programs and data can be kept permanently ready. This could be magnetic tape, but when magnetic disks became more affordable their speed of random access made them indispensable.
By the way, how does the monitor system get called at the end of the program?
Well, at least two cases have to be taken into account. Normal program termination and abnormal.
In the usual case the last thing any program does is either to return to the resident monitor (the address might be left on a stack somewhere). Or to make an explicit call to say I am finishing. In this case the call could be put there by the compiler. This is shades of how it works in modern operating systems. The difference is that we don't have true system calls yet, we just have ordinary procedure calls.
The abnormal case is when the currently running program does something wrong and causes an error. Many errors were fatal and the operators had to restart the system.
The reason for the fatal errors was that memory didn't have any protection. The code to interpret and perform all of these steps was permanently kept in memory (or easily accessible from disk). The permanent memory these operations occupied had to be preserved from use by all other programs.
Memory isn't the only thing that needs protection. Now that we have disks attached to the computer there may be files owned by many different people. At the moment we have no way of stopping someone accessing files owned by someone else.
All attached devices should ideally be protected as well. There is nothing to stop someone altering the I/O subroutines to print silly messages or even destroy the hardware (actually possible in some cases).
Before we add hardware memory (and by default device) protection we return to another improved way of reducing the time the processor spends waiting. It required a change in hardware.
Input from the user is still coming from decks of cards and output back to the user is via a printer. These are slow devices, we saw that offlining sped the work up, at least for the big fast computer that actually ran the programs. With the advent of disk drives which could be read from and written to (fundamentally different from tape, the same tape could either be read sequentially or written to sequentially), our one computer can do the same job as the three we used for offlining.
All we need to do to have the computer jump between several different activities at once. When a card is available to be read, the computer reads it and puts the data onto disk. Then it goes on with the program it is currently working on. When this program needs data it gets it quickly from disk.
Similarly output goes to disk. When the printer can take another character or another line of characters the output is taken from the disk and sent to the printer. This is known as SPOOLing (Simultaneous Peripheral Operation OnLine). In fact we still use this idea in almost all operating systems.
We didn't really need the disk, the same trick can be performed with I/O buffers in memory. The true magic was in doing several things at the same time. Which was possible with interrupts (or interruptions).
An interrupt is a hardware signal (just raising the voltage on a line into the processor) which forces the processor to jump to a specific address (where directly or indirectly the interrupt will be handled). What happens next is very important. If we want our processor to be able to return from the interrupt to the place it left working on the current program all necessary location information and status must be stored by the interrupt (and associated software). Usually machines store such information on a stack. Some older machines used to have one memory location for each possible source of interrupts, where the return address was saved.
The interrupt gives us a way of telling the processor that some I/O device is ready to provide data or accept data and the processor can jump off, handle the request and then return to where it was in the program.
Once we can do this we can have a program running on our computer and be receiving data for the next program from a card reader, storing the data into the I/O buffer on disk and printing data from the I/O buffer for a previous program. This overlapping of I/O with useful work is the solution we were looking for.
Remember that the monitor program in memory, already included some commonly used I/O routines. So we can add spooling to the tasks of the resident monitor.
We are getting very close to the next big step in the development of operating systems, but before we can carry on we need to deal with some of the problems associated with monitor systems.
The major problem was the potential for programs to do things they shouldn't, either by intention or by accident. With complete access to all memory every program could do whatever the programmer decided. Accounting information or private data could be changed. The resident monitor itself could be altered or corrupted etc.
With a sequence of programs all using the resident monitor, the interface between the resident monitor and normal user programs has to be carefully defined. This is the beginning of the system call interface. Other standards included file formats (object code files from different compilers might be linked together).
We also need a better way of coping with errors. When something goes wrong with a program or worse the resident monitor (possibly caused by a malfunctioning program) the operator has to restart the system. To increase the efficiency of the system there must be ways to handle such errors automatically.
A lot of problems are solved if we can restrict access to only part of memory. Unless we want to inspect every memory access by software (how could this be done?), which would be very slow, we are forced to add the protection features to the memory hardware.
We will look at this in detail later in the course. For now we will just assume that the hardware can detect when a program is trying to access memory outside of that which the system has allocated it and prevent the access from occurring. A greater flexibility of protection would be nice as well, e.g. being able to read but not write.
This partially solves our other protection problems. If we have hardware (such as disk devices) which are controlled by memory mapped registers we can make sure that the addresses which control the devices are in the protected memory area. The same holds for other devices. If we can separate users from the file system, accessible only through operating system functions, we can design a wide variety of file systems and protection mechanisms. It is highly likely we want to allow users to run programs but not alter them for example.
If the devices are not memory mapped, instead they are controlled by special commands, then the processor will have to have some way of preventing programs performing these commands. The processor will have to have a bit which says that it is currently allowed to use these commands. If the bit is not set, when a user program is running, then any attempt to use these commands will cause an error.
A similar scheme could be used for memory. Some memory is accessible when the bit is clear, all memory is accessible when the bit is set. Basically the processor operates in at least two different modes. An ordinary mode and a higher privilege mode. These are sometimes called user and kernel modes, or problem and supervisor mode or …
Even with simple SPOOLing systems we still find that the processor is doing nothing when the currently required data is not available. The computer system may also have other expensive devices attached to it which the current program is not using. We can solve both of these problems if we allow more than one program to be running at once, multiprogramming.
The spooling system required information about at least three different jobs at a time. The job that was currently running, the previous job which was having its output printed, and the next job which was having its data (and code) spooled onto disk.
It is only a small step to having several ready jobs on disk and when memories became large enough having several jobs in memory at once.
Now when one program is waiting for input, another program can be running. If a device is not being used we can load a program which will use it.
Now that we have several programs occupying memory simultaneously we need to return to the idea of protected areas of memory. Not only do we want to protect the functions performed by the resident monitor system, we also want to protect programs from each other.
How should we partition the memory. We could divide memory up into equal sized chunks. The obvious weak point of such a design is that programs will seldom be the correct size to best utilise memory. Small programs leave large chunks of unused memory. Large programs don't fit (actually there were provisions for allocating several memory chunks to large programs). An advantage of this scheme was that it was simple and programs could be compiled with a predefined partition allocated to them, eliminating the need for relocation at load time.
Another approach was to allocate memory depending on the size of the program. To enable this to work the system had to be able to load programs at different locations. Once again large programs provide a difficulty and the system must be able to recombine fragments of memory.
What if a program was bigger than the available memory? The program could manage its own area by overlaying part of its memory with the next part of the program. As long as the program never required more memory at any point of execution than was allocated to it, it could run.
By this stage we have the operating system doing complicated things with memory. We call this "memory management".
The eventual answer to these problems was the invention of virtual memory. As it now stands virtual memory allows programmers to write programs far larger than the amount of real memory on a machine and to securely protect that memory from unauthorised access.
Some people would say that virtual memory was a bad idea. As memory becomes dramatically cheaper it is foreseeable that secondary storage will disappear as we now know it.
Virtual memory poses all sorts of problems for operating systems. Completely new data structures such as page tables need to be maintained for each running program.
Different modes for the processor and protected memory meant that resources can be safely protected by the operating system. So how does an ordinary program now get access to a protected resource, for example a printer.
The answer is "indirectly". All user level programs have to ask the operating system to do the jobs for them. This asking is via system calls. A system call is like a software requested interrupt. The call always goes to a place in system memory which is totally out of the control of the user level program.
With these additions (protection and multiprogramming) in place, our operating systems had progressed to what became known as batch systems. Users still submitted jobs (usually as punched cards) and waited for the output to come from the system. But now the computer was being used most efficiently. Along with the job the user had to submit a list of resources which the job would require, how much disk space, how many files, special devices, etc.
This enabled the batch system to select which job should run next so as to maximise the use of the computer and attached devices. This was one of the many levels of scheduling, selecting which jobs should be competing for resources and which particular job should be running now.
First of all the computer operators applied high level decisions, "Sorry your programs can only run between the hours of midnight and 5am." When a job entered the computer system itself it was added to the list of jobs which could run, whether it did depended on the resources it needed and the resources which were currently available.
Then when the job was chosen to run and it required some I/O it was suspended and a job which didn't need to wait was given the processor. Eventually the required I/O will be completed and the original job will be able to continue.
With the simple SPOOLing system, it was the interrupts coming from the devices which controlled whether the current program or the I/O code was being performed. Now that we have several "equal" programs running we need a more sophisticated method of deciding which program should be running now and switching between programs. The system software which makes these decisions and does the switching is part of the scheduler, commonly called the dispatcher. It is the dispatcher's job to make sure that when a program needs to wait for something another program can start running. When a program is returned to (usually because the data it wanted is now available) it must find itself in exactly the state it was in before. From each program's point of view, it looks as though it is the only program running on the machine.
Now we have the operating system doing complicated things with programs. This came to be known as "process management".
With the arrival of protected memory and multiprogramming we have something recognisable even today as an operating system.
Something else was needed to stop one job taking over and monopolising the the system. One of the resources which a job was allocated was a certain amount of CPU time. A method had to be developed to stop a job using more than its requested time. A real-time clock or interval timer was essential in order to know how long the jobs had been running.
This clock can send interrupts (just like other devices) to take the processors attention away from the current job and determine whether that job should keep running. We will return to this shortly.
Now that we have several different programs all competing for the processor and other resources we have to be far more careful. Extra information now needs to be maintained both about programs…
and about resources...
Now that all I/O requests can be forced to go through the operating system we can make sure that the operating system allows only one program at a time to work with devices such as printers.
From the programmer's point of view very little had changed between monitor systems and batch systems. They still submitted their jobs and received the same printed output. The greatest advance was in security. It was now impossible(?) for someone else's work to trash your job. Of course this security was absolutely essential with the availability of high capacity disk drives.
In essence the batch systems made the computer operators' jobs easier. Many of the tasks associated with running the computer were now taken care of automatically. Some of the better batch systems even sent helpful messages to the operators when resources were required.
Previously the operators had to make decisions such as which jobs would run when. One major speed up we saw was executing a number of programs requiring the same memory configuration. This changed under the batch system. We widen our concept of efficiency to include all of the computer hardware, not just the processor. We now want to keep the disk drives, the printers, the tape drives, all busy. In order to do this we want to have a salmagundi of jobs running simultaneously.
It became common to specify a jobs resource requirements by placing it in a queue. Different queues were used to indicate the different requirements, as in the following example.
| Queue | 1 | 2 | 3 | 4 |
| Processor time (in seconds) default maximum | 120 1200 | 20 120 |
20 20 | 120 2000 |
| I/O time (in seconds) default maximum |
120 1200 | 20 120 | 20 20 | 120 2000 |
| Printer (in lines) default maximum |
500 2400 | 500 1200 | 300 500 | 500 3600 |
The user could specify limits up to the maximum allowed for a queue. If no limit was specified the default for that queue was applied.
To stop users abusing the system, they were limited to two jobs in any one queue at a time.