Operating
Systems
An
overview :
CONTENTS:
Overview
Booting
Multi-Programming
Scheduling
Memory Management Overview
Memory Protection
Fragmentation
Virtual Memory
Peripheral Sharing
In these pages I intend to look at computer operating systems. More
specifically, I will investigate what is meant by the term
"operating system", what
its overall role in controlling the computer is, and what its main functions
are. I will then take an in-depth view of the main components that go to make up
a general purpose multi-programming operating system, as can be found on most
modern computers.
OVERVIEW
Firstly let us define what is meant by the term "operating system". An operating system, is a collection of programmers that control the operation of a computer as efficiently as possible. It is the task of the operating system to effectively enhance the usefulness of the computer by presenting to its programmers and end users alike a virtual machine. That is, a simplified view of the computer, which is easier to understand and use than the bare hardware. The user will communicate with the OS via an interface, which is often called the shell. The shell may take one of two forms. That of a graphical user interface (GUI), in which commands are issued by means of clicking on pictorial representations of programs and actions, or a text based command line in which commands are keyed in by the user. The former is more intuitive for beginners, but the latter (generally used by older systems) offers greater flexibility in working. Either way the purpose of the shell is simply to acts as a shield between the user and the internal workings of the OS.
ie:
BOOTING
When a computer is switched on, the OS must be loaded from disk and run
before anything else can occur. This is done in 3 phases. The CPU automatically
jumps to a pre-set memory location, and begins executing what ever instructions
it finds there. These structions form a very simple program known as a
'bootstrap loader'. This results in the boot sector of the disk being loaded and
run. The memory location at which the loader is stored will, for obvious
reasons, always hardwired (ie, it cannot be changed, and keeps its contents even
when power is switched off). [The term 'bootstrap' loader is given to this
routine as it is supposed to drag a system up by its bootstraps!]
The boot sector stores a more advanced program which when run, controls the loading and execution of the main body of the OS from the disk. Because the boot sector is actually stored on the disk, it can easily be customised to load any operating system compatible with the hardware of the computer. This increased flexibility is vital, as it allows the operating system to be changed and updated cheaply, without the need to replace any of the hardware.
MULTI-PROGRAMMING
A true general purpose operating system should be capable of
SCHEDULING
In a muti-programming system, the user will need to be able to run several programs simultaneously, however the CPU is only capable of dealing with one of them at a time. To create the illusion that all the programs are running concurrently, the CPU must switch its attention between them rapidly. This is part of the wider challenge to the OS of determining the optimum sequence and timing of assigning jobs to the processor. This activity is called scheduling, and will be looked at in the next section. Before any scheduling can take place, however, the more basic question of how to switch between processes must be answered. During its life span in the operating system a process may be stopped and started millions of times. In order to work correctly, the process must able to tolerate these transitions. In order to restart where it left off, the state of the computer must be restored exactly as it was just prior to the processes' suspension. To enable this restoration to take place, the multi-programming system must create a Process Control Block for every process. This PCB will effectively contain a "snap shot" of the computer's internal state (along with some other process specific information that is needed elsewhere), and will be reloaded when the process is to restart. Typical information held in a PCB is: Processes' ID Processes' state Program counter (ie, its position in the program) The internal register state of CPU Memory limits of the process (see memory management) The processes' priority
A
list of associated files A list of the peripherals to be used. The Process
Identification Number is a unique value that is assigned to each process when it
enters the system, and it is by this that the OS is able to keep track of all
the processes it is managing. The process state is a flag to show whether the
process is either waiting for some CPU time, or is instead waiting for some
external event to take place before it continues (a key to be pressed etc). IE,
The process will be either: Ready to be processed, or Blocked from further
action for the time being. The scheduler is the part of a multi-programming
system that is concerned establishing the optimum sequence and timing of
assigning jobs to the processor. Scheduling is
exercised at three distinct levels:
High-Level Scheduling - This level deals with decisions as to whether to admit a new job into the system. (ie, If it is already overburdened then non-essential jobs might not be considered).
Medium-Level Scheduling - This level is concerned with decision to temporarily remove a process from the system (thus reducing the system load and increasing efficiency ith which other jobs can be processed), or to re-introduce an old one.
Low-Level
Scheduling - Decides which of the processes waiting in the
system should be assigned to the CPU. This level is known as the
dispatcher. At each level in
the scheduling process, the decisions taken will be based
upon such factors as priority of the job, the resource requirements
(memory and peripherals etc.) and time spent waiting for attention. It is up to
the dispatcher to share the CPU's time fairly between all the various processes
competing for attention. This is achieved by giving each process a time slice
(or quantum), consisting of a few milliseconds of CPU time. These quantum are
measured out by an independent timing circuit, which will be able to interrupt
the operation of the CPU once the period has elapsed. That is, the Timer
Interrupt would cause the CPU to suspend the currently executing process, and
start running a special program known as the "Interrupt Service
Routine", which in this case will be the dispatcher. Thus, after a process
has been executing for certain length of time, control of the CPU will be
returned to the dispatcher, so that it might select a different process to begin
executing. There are many different
strategies that might be used by the dispatcher to actually select a process,
but one of the most efficient when dealing with a wide variety of tasks is a
"Multi-level feedback queue". This system provides a slightly more
adaptive approach than a simple turn-base (or round-robin) style of operation,
and is used in some versions of UNIX. Click here for a full description of the
Multi-Level Feedback Queue.
MEMORY MANAGEMENT
One of the most difficult problems that must be overcome in a multi- programming system, is that of resourcing the available memory between all the different processes. The OS has a specific component dedicated to this task - the memory manager. As mentioned earlier, one of the main functions of an OS is to provide a much simplified virtual machine to the user and programmer alike. As such, when the programmer is writing a new application, they do not want to be concerned with the actual loading and positioning of the program in memory. It is up to the memory manager to take care of these details transparently. Let us make the assumption that the in a multi-programming OS the programs will be loaded into consecutive blocks of memory as illustrated below.
Now, the memory manger will present the programmer with the
simplification
that their own program is loaded from the start of the memory area
onwards. (Were this not the case then it would be impossible for
the programmer to reference a
specific memory address within the program - the program could be loaded into
any part of memory, so there would be no way of knowing the real location of any
part of it). If such a system is to
work, then it is up to the memory manager catch each attempt made by a program
to reference memory, and to transform it
into the real address at which the process is located. This is known as
Relocation. Relocation is implemented by keeping track of the offset in memory
(or distance from the start of the memory area) at which the program was placed,
and then applying the logic:
Real Address = Specified Address Within Prog.+ Offset in memory
MEMORY PROTECTION
In a perfect world this should prevent one program from interfering
with another.
In reality, however, this is not always the case. It is not uncommon for a
malfunctioning program to attempt to modify memory locations almost randomly;
locations which are not necessarily within its own bounds. This may well lead to
corruption not only of itself, but also of other programs in the system, thus
bringing whole system standstill. Another
facet of the memory manager must therefore be to protect programs from the
effects of one another. That is, it should catch any attempt made by a program
to access memory areas that don't belong to it, and identify it as being
potentially malfunctioning. That program should then be terminated, thus
minimizing the risk to others in the system. The user will be notified of the
problem, but all other programs will continue to work normally. In the situation
illustrated above, program two begins from a base address (or offset in memory)
of1024 and has an upper limit of 4096. It is said to have the bounds 1024 to
4096. In general, an illegal memory access by
this program could be identified as either:
Requested Address <0 or
FRAGMENTATION
So far we have made the assumption that programs are loaded into consecutive blocks of memory. In a real system, however, this strategy breaks down because of its volatile memory requirements. To illustrate, a medium sized program might reach its natural end and be removed from the system, thus freeing the memory space it occupied. A new (slightly smaller) program waiting to enter the system could then be loaded into this gap, filling most of it but still leaving a little unused space - a "hole". During continuous operation many such "holes" appear, and because they are too small to accommodate any program, the space they occupy is effectively lost. The memory is said to be fragmented, or less condensed than it might be. ie:In the above situation, if a moderate sized program were to be loaded into memory, then whilst the total free space is sufficient, there is no one block large enough to accommodate it. This is very inefficient use of memory! The solution is to subdivide each process of a program into small blocks or pages (typically about 4K in size). The memory space is then viewed as a set of page frames (of an equal capacity), over which the various pages of a process can be distributed. These pages need not be continuous in memory, or even appear in the correct order. The memory manager maintains a "page table" that enables it to locate any page, so it still presents to the programmer the illusion that memory is continuous. This paging technique overcomes the problem of fragmented memory since a program can now be loaded into several holes.
VIRTUAL MEMORY
Sometimes, though, no matter how many memory optimisation tricks are employed the total memory space available will be insufficient to store all the programs at the at once. This being the case, there is a final last-resort that will be used by the memory manager. It will try to create the illusion of additional memory space by using the backing store (a hard disk in the case of a PC) as an extension to main memory - as virtual memory!
In order to run, a process must be in the computers main memory (because this is the only area that can be referenced by the CPU). When a process is idle, however, this needn't be the case. A blocked process can easily be "swapped" out to the backing store in order to make room for another. It would take far too long to swap entire processes between the hard disk and main memory due to the (relatively) low transfer speed, but because the process has been split into several pages, only those pages which won't be needed for a while will be transferred. Click here for a description of how inactive pages may be identified. If a running process references a virtual memory address, then the memory manager will go to the page map table to find the real address of the reference. If the page containing the referenced address doesn't exist in memory then a page fault (or error) will occur. This will prompt the memory manager to retrieve the appropriate page from backing store into main memory. If main memory is full then a different page will first be swapped out to backing store in order to make room for the new one. Once this is competed, the page table must be updated with the new locations of the pages. The following diagram illustrates this. Click here for 101 interesting and imaginative ways to destroy a virtual memory system! And that concludes our look at memory management in a multi- programming OS. Thus far we have considered how the OS shares its resources of time, process allocation and memory. The final resource to be shared is that of the computer's peripheral devices.
PERIPHERAL SHARING
At any point that a process requires hardware interaction, a request
for control of that hardware must
be submitted to the OS. This gives the OS the power to control hardware usage,
and guard against dangerous situations where two or more conflicting processes
might try to Control one hardware device. Such conflicts may effectively be
resolved in two ways. The first method is for the OS to simply keep track of
which devices are in use. If a process requests control of a hardware device
that is busy,
then it can be made to wait (or blocked) until the device is free. This
approach does, however, have two major drawbacks. Processes will be kept in a
waiting state for a long time, causing long delays. Also, a rare situation may
occur in which a process will request (and be granted) control of a peripheral
device. Before that device can be marked as busy, however, the process might be
suspended and the next one begin. This second process may then request the same
device, and so on. More than one process thinks that it has control of the
peripheral! The second problem can solved by using the special "test and
set" operation in some CPU's, which can simultaneously check and change the
memory flag that shows the state of the device (avoiding the possibility of
being interrupted
before the operation is complete). The second approach to peripheral management
is a technique known as "Simultaneous Peripheral Output On Line" or
spooling. Instead of sending
data directly to a slow peripheral device (consuming much time and
blocking any other processes that need to use it), the information can be
sent to a quick temporary storage device. This can then slowly de- spool
the data to the appropriate hardware device independently of the
controlling process. The delays associated with hardware communications
are eliminated, thus greatly enhancing the efficiency of the machine. The only
down-side to this approach is the cost of the extra dedicated hardware. Click
here for a description of the ultimate conflict - the "Deadly
Embrace".
That concludes our look at multi-programming operating system. To summaries, in these pages we have looked generally at what is meant by an operating system, what its main features are, and at its overall role in operating the computer. We have also looked at the challenges involved in creating a modern multi-programming operating system - How multiple process can be controlled and the CPU's time resourced between them. The role of the memory manager in implementing systems such as relocation, protection, paging and virtual memory. And finally, we have seen how the peripheral devices of the computer can be resourced amongst competing processes whilst avoiding conflicts. I hope that this has been illuminating!
This web page was created by Huw Jeffries, 2nd January 1998