Fig. 11.2.1: Several jobs in a multiprogrammed computer system
Before we talk about protection, relocation and virtual memory in detail, we must review basic operating systems concepts which drive the need for more sophisticated memories.
Multiprogramming is the technique of keeping more than one partially completed user program in memory and switching rapidly from one to the other in order to give the illusion that the computer is working on all of them simultaneously. The operating system, abbreviated as the OS, is just another program whose code and data always occupy a portion of main memory. The OS is usually but not always at the section beginning at address 0. Some OS's start at high memory. Other OS's occupy several separate sections of memory.
User programs of varying sizes are loaded into memory when the user requests that a program be executed. These requests used to come in the form of a deck of punched cards, but now they come from a user's terminal. In Fig. 11.2.1, four user programs labeled A, B, C and D co-exist in memory. Suppose C finishes early and a new job E is started. E will need to be placed in memory somewhere, so it will probably try to fit within C's space if it is big enough. If not, D may be moved down towards B, a process called memory compaction, which causes holes (regions of unused memory) to coalesce into larger holes so that a new job may be started. In the very worst scenario, E may need almost all of memory so it may have to wait until A, B and D are done. These memory hogs will be kept waiting till 3:00 AM on Christmas day!
Fig. 11.2.1: Several jobs in a multiprogrammed computer system
User programs, often called jobs, use the main ALU for a while and then they start an I/O command. For example, job A may do a couple thousand additions and multiplications and then wish to write the result out to a file on the disk drive. Input and Output are often enormously slow compared to regular instructions, so a mechanism is used to offload the actual work of writing bytes on spinning disks, drums and tapes. Special-purpose computers, called controllers or channels, do the actual work of communicating with these devices. They are capable of also moving data from the I/O device into main memory while the main computer (the ALU) is doing other instructions. (Later we will investigate how it is that main memory can seemingly be used by different masters simultaneously. It actually can't but there are tricks to make it look like that.)
The huge disparity in access times for various kinds of memory is what allows multiprogramming to succeed. In the table at the top of the next page, the approximate access times of registers, memory and secondary storage are listed. Note the huge jump between main memory and even the fastest hard disks -- about four orders of magnitude, or a factor of one thousand.
To read from a it requires about --------------------------------------------------- register 70 nanoseconds main memory cell 700 nanoseconds hard disk sector 1,000,000 nanoseconds
When job A wants to do I/O, it tells the OS of its intentions and in effect says, "Here is what I need done. Now do it for me." User programs are never allowed to directly read or write hard disks so that various security measures can be enforced. The OS then schedules the I/O operation, possibly making it wait until another job's operation is done. When it is possible to go ahead, a controller gets the command and takes over from there. By this time, the main computer has put job A into suspended animation and has started working on B's program. A's code and data remain in memory although the CPU is not doing anything to them right now. After a long while (long as far as the computer goes but much shorter than a blink of an eye.) the I/O controller announces that it has successfully read or written the data and A must be restarted. The way the controller announces this is usually by sending an interrupt to the main CPU, sort of electronically tapping it on the shoulder. After more bookkeeping, the CPU marks job A as ready to run and when program B has reached its own I/O operation and must be put to sleep, the CPU lets A actually start up again where it left off. To be fair to user jobs, many OS's use what is called round robin scheduling, which lets every waiting program have a crack at the CPU before going back to the first job.
This, in a nutshell, is how most multi-user operating systems work. There are of course a million and one permutations of details but even personal computers are getting these kinds of systems. Windows 95 and MacOS 8, for example, are full pre-emptive multi-tasking systems.