What’s the most important piece of software that you can buy for a general-purpose computer? The answer is, of course, the operating system. What’s the most useless piece of software that you can buy for a computer? In this case the answer is...the operating system? So, what is the operating system and why is it both useful and useless?
The solution to this conundrum is easy to find. Computers that perform dedicated tasks (e.g., an air-conditioning control system), don’t require operating systems. A general-purpose computer like a PC or a workstation, needs an operating system to control the computer’s resources (e.g., processor, memory, disk drives, display, mouse, keyboard). Without an operating system, it would be very difficult to perform even the simplest of tasks; for example locating a program and running it. The operating system itself doesn’t solve any problems—it’s not a word processor, a spread sheet, or a game. So you can now see why an operating system is both useful and useless—you need one to make a computer viable even though the operating system itself doesn’t “do anything”.
Suppose that the operating system didn’t exist—just imagine what it would be like using a computer. You want to edit a file, so you first load the editor in memory and then you load the file to be edited. How do you load these files? Where are they located on the disk? These activities are all carried out automatically by the operating system. In fact, it’s probably safe to say that the personal computer couldn’t have achieved its popularity without operating systems like Microsoft’s Windows and Apple’s System ??
 |
The user’s view of a modern operating system This demonstrates the power of the user interface—you can display several screens simultaneously and employ images or icons to represent programs and data files. |
Operating systems are not trivial pieces of code. A modern operating system might occupy tens of megabytes. In this chapter we are going to describe what the operating system does and look at three of its most important components: the scheduler that switches between programs (i.e., tasks); the memory management system that is responsible for keeping track of data; and the user interface that governs how the programmer and the operating system communicate with each other.
Before the invention of operating systems, you had to control the computer directly. In the very early days of the computer, the computer was programmed in machine code by using switches on a front panel to input 1s and 0s. Life was made a little easier in the 1950’s when data could be entered by means of punched cards or paper tape.
The first operating systems were called batch systems because they allowed a group of jobs (i.e., programs) to be submitted to a computer—normally in the form of large decks of punched cards. Jobs were executed in the order in which they were submitted. Students who went to university after the 1970’s, missed an era in which CS, EE, and math students walked around campuses carrying large card decks. The floppy disk hadn’t yet been invented.
The next generation of operating systems employed multitasking that permitted computers to run several jobs at the same time. The operating system was responsible for sequencing the execution of these jobs and ensuring that each job got the memory and resources it required. Multitasking operating systems were developed for mainframe computers by companies like IBM.
A close relative of a multitasking operating system is a timesharing system. From the late 1960’s onward when computers were still very expensive, the timesharing operating system was developed to allow several users to access the computer at the same time via on-line terminals. Each user sat at a terminal and was able to interact with the computer in real time. You could edit a program, compile it, and then run it without getting out of your seat.
Another relative of multitasking is the real-time operating system. The real-time operating system is found, primarily, in embedded computers used to control complex systems in industry. A real-time operating system is designed to ensure that all the various programs running something as complex as a chemical process can respond to external events (e.g., the detection of a dangerously high-temperature) within a guaranteed time.
As hardware became both cheaper and more powerful, distributed operating systems were developed for computers that could run tasks on several interconnected processors. The user is not aware of how the operating system assigns tasks to the individual processors.
The low cost of personal computers and the creation of computer networks led to the development of networked operating systems in the mid 1980’s. A networked operating system gives you control of your own system and makes other systems on the network appear as an extension of your computer. In a networked system you can access the resources of other computers.
One of the most important developments took place in the early 1980’s at the Xerox Palo Alto Research Center, where the graphical user interface, GUI, was developed. Users employ a pointing device such as a mouse to select options on a menu displayed on the screen. The graphical user interface was employed by both Apple in their Macintosh range of computers and by Microsoft in their Windows operating system.
To a considerable extent, you could say that operating systems have broadened the access to computers. First generation computers were programmed by people who had to be programmers, systems designers and engineers—they had to understand the computer almost at the circuit level. The batch and timesharing operating system allowed programmers, students and scientists to use the computer. However, you required a considerable body of knowledge to use a computer with a time-sharing operating system. The graphical operating system environments of the 1990’s have enabled the non-specialist to use the computer as a tool with almost no knowledge of the underlying computer science. In order to use a GUI effectively, you still have to understand about file and directories—operating systems that require no knowledge of computers whatsoever have not yet appeared.
The operating system performs two vital functions. First, it controls the entire computer system: the hardware, memory system, I/O system, display system, and software. When you load a program into memory, the operating system is responsible for locating it on disk and copying it to a region of memory currently unoccupied by other programs and data (you don’t have to worry about where programs are to go in memory because the operating system takes care of that). Second, the operating system provides the user interface. Not very long ago the computer user had to interact with the operating system by means of a special-purpose language called a job control language, JCL. Only highly-trained computer operators communicated with computers by means of these rather complex JCLs. The old (pre-Windows) MS-DOS operating system found on PCs is an example of a relatively simple JCL; for example; if you wish to delete a file called DIARY you enter the command DEL DIARY.
Today, graphical user interfaces have made life immensely easier for the computer user; you can run a program by selecting the icon on the display that represents the program. The cursor is moved from its current position to the icon by means of a mouse. Once the cursor is over the icon, you double-click a button on the mouse (i.e., press the button twice in rapid succession), and the operating system loads the program and transfers control to it. Similarly, some GUIs permit you to delete a file by dragging its icon to the symbol for a trash can.
The operating system is also responsible for the computer’s security (or lack of it); for example, the operating system determines who can use the system, who can access what files and what programs, and stands guard against viruses. Security is very important is systems in which two or more users can share a computer.
If you think about it, almost no two personal computers are alike—each system has a particular combination of processor and memory, mouse, keyboard, display, printer, disk system, and so on. All these elements that make up the computer system are referred to as devices. When a software house creates a new word processor, the company doesn’t want to produce a special version for each computer user to suit their specific combination of devices. A good operating system achieves device independency. The operating system is able to take a program and adapt its input and output to the particular configuration on which it is to run. In other word, the operating system matches user software to an individual system. If you buy CorelDRAW! graphics package, it will run on a ‘486 system with an ATI 600 x 800 display card and a 20 Gbyte IDE hard disk, or on a 3.8 GHz Pentium system with a ????x???? AGP-bus display card and a 400 Gbyte hard disk.
Let’s look in more detail at what the operating system does. When you first switch on a computer, a very small program that resides permanently in ROM is executed. This program, called a bootstrap loader, reads a program from part of the hard disk or the floppy disk and loads a program in memory. Once this program has been loaded, control is transferred to it. The program then reads the disk and loads the rest of the operating system into memory. The program in the ROM that starts the whole process is called a bootstrap loader because someone thought its operation was rather like trying to pull yourself up by your own bootstraps.
Once the operating system has been loaded, it sets up an appropriate environment for the computer. This environment comprises all the software and hardware elements required to run user programs on the computer. The operating system employs programs, called device drivers, that control the operation of the computer’s interface (keyboard, mouse, display, printer, sound cards etc.). A device driver is a part of the operating system that translates operating system requests into the actual commands needed to directly control actual hardware. Consider the video controller, a complex subsystem that displays an image on a CRT or LCD display. A particular manufacturer’s video controller might have an elaborate register structure that must be loaded with ten or more parameters in order to display an image. When the operating system needs to, say, draw a line from A to B, a complex series of instructions must be issued to the display controller. The device driver takes higher level commands from the operating system (e.g., draw a line form A to B) and provides the actual hardware with the data it needs to draw the line. Whenever you wish to upgrade the video controller, you plug in the replacement controller and load a new device driver. The device driver is normally written by the supplier of the video controller card, and supplied on a disk. When you install the device driver, it is linked to the operating system.
When the operating system has initialized the system, it awaits a user input. A modern graphical operating system like Windows displays icons and pull-down menus on the screen. When the user moves the mouse on the desk-top, the mouse sends a signal to the computer. The operating system intercepts this signal and uses it to move the cursor across the screen in sympathy with the mouse. When the user places the cursor over an icon representing a program and clicks a button on the mouse, the operating system detects the click and loads the appropriate program.
In order to load a program the operating system must be able to control the secondary storage devices. The operating system must know where the file represented by the icon is stored on the disk and then be able to load it into memory. File management is one of the most important services performed by the operating system. Without an operating system you would have to load file XYZ by, say, reading track 23 sectors 1,2,5,8, then track 29 sectors 2,5,9, ..., and so on, into memory. The operating system’s file control mechanism hides all the nasty realities of how a file is mapped onto a disk from the user.
Computers have to be able to respond to external events—interrupts. A typical personal computer might receive interrupts from serial and parallel ports, from the disk interface, from sound cards, and so on. When an interrupt occurs, a piece of software called an interrupt handler has to suspend the program currently being executed, identify the source of the interrupt, deal with the interrupt by running the appropriate interrupt handler, and then resume the suspended program. The software that deals with the interrupts is, of course, part of the operating system.
Modern computer systems are capable of running several programs simultaneously. You can be using a word processor while receiving a file via a modem, and display a clock with moving hands in a corner of the screen all at the same time. The ability of a computer to run two or more programs simultaneously is called multitasking. Because a CPU has a single program counter that steps through a program instruction by instruction, multitasking is, of course, impossible. However, the human time frame is very different to the computer’s time frame; a second is a fleeting moment to a human, but to a computer it is 1,000,000,000 nanoseconds or over 10,000,000 instructions.
 |
Multitasking by switching between three tasks If the operating system switches between programs A, B, and C rapidly (i.e., the programs are executed in the sequence ABCABCABCABC,...), the computer still executes programs sequentially but it appears to a human as if it were executing A, B, and C in parallel. Both television and the cinema rely on the same phenomenon; they show a rapid sequence of still images but the viewer perceives a moving image. |
One of the most important components of an operating system is its kernel or nucleus or first-level interrupt handler. This component deals with interrupts from all sources and is responsible for switching tasks (i.e., transferring control from one program to another). The kernel is important because its performance directly determines the efficiency of the operating system. If the operating system switches between tasks rapidly, it is vital that as little time as possible be devoted to the task switching process itself—the more time spent in switching tasks, the less time is available to the running of the tasks themselves.
An essential part of the kernel is the interrupt mechanism that facilitates the task switching process. Although we have already introduced interrupts when we described how the computer performs input/output operations, we provide a summary here.
· An interrupt is a request to the processor for attention
· The interrupt may be a hardware interrupt that is received from an external device
· The interrupt may be a software interrupt that is generated internally by means of a special instruction called a trap
· The interrupt may be a software interrupt that is generated by certain types of error
· The interrupt is dealt with automatically by calling an interrupt handler
· Interrupt handlers form part of the operating system
· An interrupt is transparent to the program that was interrupted—the interrupt handler preserves all working registers
 |
Software components in a computer This illustrates the simplified structure of the software in a typical general-purpose computer. The software components have been divided into two groups: those that belong to applications programs such as word processors or compilers (i.e., user 1 and user 2), and those that belong to the operating system (in the group that is shaded). The kernel (marked scheduler) is responsible for switching between tasks. |
 |
Hierarchical model of an operating system This demonstrates how the software components of a computer systems can be regarded as a hierarchical structure with the scheduler at the center surrounded by the other components of the operating system. The uppermost layer consists of the user tasks that employ the services of the operating system. There are two reasons for using a hierarchical model of the operating system. The first is that the outer layers request services provided by the inner layers (this model shares some of the features of the ISO model for open systems interconnection). The second is that the kernel at the heart of the operating system determines the fundamental characteristics of the operating system. |
A task or process is a piece of executable code that can be executed by the processor (i.e., CPU). Each task runs in an environment, that is made up of the contents of the processor’s registers, its program counter, and its status register, SR. The environment defines the current state of the task and tells the computer where it’s up to in the execution of a task.
 |
State diagram of a task in a multitasking
system At any instant a task can be in one of three state: running, runnable, or blocked. This is a state diagram for a task in a multitasking system. When a task is created, it is in a runnable state—it is waiting its turn for execution. When the scheduler passes control to the task, it is running (i.e., being executed). If the task has to wait for a system resource such as a printer before it can continue, it enters the blocked state. The difference between runnable and blocked is simple—a runnable task can be executed when its turn comes; a blocked task cannot enter the runnable state until the resources it requires become free. |
Consider the following task whose function is to get data from an input device and store it in a circular buffer. This 68000 assembly language code represents an endless repeat loop that reads data from an input device and stores it in a table in memory called Buffer. When the buffer is full the next character is stored at the first location in the buffer (i.e., the buffer is circular). Don’t worry if the assembly language code doesn’t mean a lot to you. What matters is that this program uses two CPU registers, A0 and D0, to hold temporary data, and also tests the 68000’s condition code register at two points in the program.
Reset LEA Buffer,A0 Reset buffer pointer
Re_Try BTST #Ready,Input_Status REPEAT
BNE Re_Try IF input ready THEN read input
MOVE.B Input_Data,D0 Read input
AND.B #$0F,D0 Mask input to 4 bits
MOVE.B D0,(A0)+ Store input in buffer
CMPA.L #Buffer+Length,A0 IF buffer full then reset pointer
BNE Re_try FOREVER
BRA Reset
 |
The environment of the buffer task This data structure describes this task’s environment—this information alone fully describes the state of the task at any instant during its life. |
 |
Switching tasks This illustrates how task switching is carried out in a system with two tasks. Initially the buffer program, shown in light shading at the top, is running. At time T during its execution, the buffer program is interrupted by the scheduler program in the operating system. The arrow from the buffer program to the scheduler shows the flow of control from the buffer program to the operating system. The scheduler stores the current values of the task’s registers, program counter and CCR in memory. As we have already said, these registers make up the environment of the buffer program and completely define its state. The scheduler then loads the processor’s registers with the environment of the new task and, therefore, causes the new task to be executed. You can see that control is passed back from the scheduler in the operating system to the new task. At a later time the scheduler interrupts this new task, saves its environment, and loads the processor with the registers saved from the buffer program. When this happens, the buffer program continues from the point at which it was suspended. We can represent the action of the scheduler by the following pseudocode. Save the environment of the current task
REPEAT
Find next runnable task
UNTIL a runnable task is located
Load the environment of the new task
Execute the new task
The scheduler not only switches tasks, but controls the order in which they are run. As we shall soon see, some schedulers allocate the amount of time each task can be run before being interrupted. Some schedulers prioritize tasks and ensure that a high priority task (e.g., a request for service from a disk drive) always runs before tasks with a lower priority. Suppose that the buffer program is currently being executed, and that a timer circuit generates a periodic hardware interrupt to invoke the scheduler every t seconds. This operation is called preemptive task switching, because a task is suspended by the active intervention of the scheduler whether or not the task has been completed. A non-preemptive scheduler is called by a task itself when the task has run to completion or requires an operating system service. When the scheduler in the operating system is called, it must ensure that the task that was just halted is left in such a state that it can later be resumed as if nothing had happened. The scheduler then locates the next task to run and passes control to it. Note that it’s the scheduler that’s responsible for causing a task to change state.
|
The way in which an operating system handles task switching depends on the nature of the operating system—some operating systems are specifically designed to switch tasks efficiently. A typical operating system maintains a table of task descriptors called task control blocks, TCBs, that describe the nature of each task and its status (some texts use the term PCB, process control block, rather than TCB).
 |
The task control block This describes the structure of a possible task control block (each real operating system has its own particular TCB structure). In addition to the task’s environment, a TCB contains a pointer to the next TCB in the chain of TCBs; that is, the TCBs are arranged as a linked list. (we encountered linked lists in when we introduced algorithms). A new task can be created simply by adding its TCB to the linked list. The TCB contains additional information about the task such as its priority, status (runnable or blocked), and memory requirements. |
When the scheduler is called the queue of tasks waiting to be run is searched for a suitable candidate. The operating systems designer can select one of several scheduling algorithms, each of which has advantages and disadvantages.
First-come, first-served scheduling, FCFS, is a simple non-preemptive algorithm. The linked list of task control blocks is arranged as first-in, first-out queue. Each new task created is added to the end (i.e., tail) of the linked list, and each task that is executed is taken from the front (i.e., head) of the list.
 |
The TCB structure in first-come,
first-served scheduling The top figure shows a chain for three TCBs, and the lower figure illustrates the effect of adding a new task to the chain. Because this algorithm is non-preemptive, each task is executed to completion (or until it requests operating system intervention) before the next task is executed. |
The FCFS algorithm is easy to implement, and is efficient because little time is lost in searching for the next task to run. An important parameter or figure of merit for a multitasking system is the average task waiting time each task has to wait before it is executed. Unfortunately, the FCFS algorithm can lead to a very long average waiting time. Moreover, the sequence in which the tasks are received radically affects the average waiting time.
 |
The effect of task sequencing on average
waiting time using the FCFS algorithm Suppose four tasks, t1, t2, t3, and t4, are entered into the task list with requirements of 3, 5, 2, and 10 ms, respectively. The waiting time for these tasks is 0, 3, 8, and 10 ms, respectively. The first task has a zero waiting time because it is executed immediately, and then each task is executed after all the tasks before it have been executed. In this example, the average waiting time is (0 + 3 + 8 +10)/4 = 5.25 ms. If the same four tasks arrived in a different order, say, t4, t1, t3, and t2, the waiting times would be 0, 10, 13, and 14 ms, respectively. These figures correspond to an average waiting time of (0 + 10 + 13 + 15)/4 = 9.5 ms. Simply changing the order of the tasks has had a considerable effect on the average waiting time. |
Another non-preemptive scheduling algorithm is called the shortest task next, STN, algorithm. Have you ever stood in line at a bank when everyone in front of you seems to require an endlessly complex transaction and all you want is to pay a bill? You feel like shouting, “Let me in—It’ll only take a few seconds”. The shortest task next algorithm behaves just like this and executes the task with the shortest time requirement. This algorithm requires each task to have a parameter that indicates the time required to execute the task. When a new task is first created, it is inserted into the linked list of TCBs at the appropriate point. The shortest task next algorithm discriminates against long tasks, although it ensures that short tasks are executed with very little waiting.
 |
The effect of task sequencing on average
waiting time using the STN algorithm If we apply this algorithm to the same four tasks described previously (t1, t2, t3, t4, with times of 3, 5, 2, and 10 ms), the shortest task next algorithm provides the sequence t3, t1, t2, t4, and an average waiting time of (0, 2, 5, 10)/4 = 4.25 ms. The STN algorithm provides the minimum average waiting time for any sequence of tasks. In practice, this non-preemptive algorithm cannot be applied accurately, because the operating system does not always know how long each task is to take. |
Priority scheduling arranges the task in order of their priority (i.e., importance). This scheduling strategy makes sense because some tasks are more important than others—the processor needs to read data from a high speed disk more urgently than it need to read data from a keyboard. No task may be executed until all tasks with a higher priority have been executed. When a new task is created, the linked list of task control blocks is searched and the priority field of each task read. The new task inserted in the position so that tasks in front of it have a higher equal priority, and tasks behind it have a lower priority
 |
Inserting a new task in a linked list of prioritized tasks |
Although priority scheduling is conceptually reasonable and behaves the way we do, it has a serious limitation. Under certain circumstances, low priority tasks may never be executed because higher priority tasks are always arriving. Such low priority tasks are said to be indefinitely blocked. One way of dealing with this type of blocking is to gradually increase the priority of old, low priority tasks in the queue. Eventually a low priority task will work its way up the queue. Now why don’t I do that with all those low-priority jobs I keep putting off.
A simple method of dealing with the task queue is called the round robin algorithm—each task gets a fixed amount of time, called a time quantum or time slice, before it is suspended. Round robin scheduling is preemptive, because a new task is run even though the current task has not yet been completed. The TCBs are arranged as a circular queue, so that the last entry in the queue points to the first. When all tasks have taken a turn, the first task in the queue is run, and so on. The round robin algorithm is called fair because each task gets an equal chance of being executed. Round robin scheduling is useful in time-sharing systems where several users are accessing a computer via terminals.
The performance of the round robin algorithm depends on the time slice allocated to each task. If the time slice is made very large and each task executes to completion, this algorithm becomes the same as the first-come first-served algorithm. If the time slice is very short, each task in a p-task system appears to have a processor working at 1/p the speed of the actual processor (this calculation neglects the time lost to task switching). With a short time slice, an operating system using the round robin task scheduling algorithm behaves like a time sharing system.
Here we have looked at some of the fundamental algorithms used to schedule tasks in a multitasking system. In practice there are many more algorithms that can be employed, each of which have their own advantages and disadvantages.
Now that we’ve looked at how the operating system switches between tasks, we are going to look at how the operating system manages the memory required by the tasks.
If all computers had an infinite amount of random access memory, life would be much easier for the operating system designer. When a new program is loaded from disk, you can place it immediately after the last program you loaded into memory. Moreover, with an infinitely large memory you never have to worry about loading programs that are too large for the available memory. In practice, real computers always have too little memory. In this section we are going to look at how the operating system manages the available memory.
 |
Memory fragmentation in a multitasking environment This demonstrates a multitasking system in which three programs are initially loaded into memory—task A, task B, and task C. In figure b task B has been executed to completion and deleted from memory to leave a hole in the memory. In figure c a new process, task D, is loaded in part of the unused memory and task A deleted. Finally, in figure d a new process, task E, is loaded in memory in two parts because it can’t fit in any single free block of memory space. |
A multitasking system rapidly runs into the memory allocation and memory fragmentation problems. Operating systems solve these problems by means of memory management that maps the computer’s programs onto the available memory space.
 |
The memory management unit This figure describes the arrangement of a memory management unit, MMU. Whenever the CPU generates the address of an operand or an instruction, it places the address on its address bus. This address is called a logical address—it’s the address that the programmer sees. The MMU translates the logical address into the location or physical address of the operand in memory. The logical address consists of two parts, a word address and a page address. |
 |
The structure of paged memory This figure illustrates the relationship between page address and word address for a very simple system with four pages of eight words (i.e., 4 x 8 = 32 locations). The address from the CPU in consists of a 2-bit page address that selects one of 22 = 4 pages, and a 3-bit word address that provides an offset (or index) into the currently selected page. A 3-bit offset can access 23 = 8 words within a page. If, for example, the CPU generates the address 10101, location 5 on logical page 2 is accessed. The 3-bit word address from the CPU goes directly to the memory, but the 4-bit page address is sent to the memory management unit. The logical page address from the CPU selects an entry in a table of pages in the MMU. Suppose the processor accesses logical page 2, the corresponding page table entry contains the value 3. This value (i.e., 3) corresponds to the physical page address of the location being accessed in memory; that is the MMU has translate logical page 2 into physical page 3. The physical address corresponds to the location of the actual operand in memory. The MMU translates a logical address P on page Q into physical address P on page R. |
Why should the operating system go to the trouble of taking an address generated by the processor and then using an MMU to convert it into a new address in order to access memory? To answer this question we have to look at how programs are arranged in memory.
A processor’s logical address space is composed of all the addresses that the processor can specify. If the processor has a 32-bit address, its logical address space consists of 232 bytes. The physical address space is composed of the actual memory and its size depends on how much memory the computer user can afford. We will soon see how the operating system deals with situations in which the processor wishes to run programs that are larger than the available physical address space. The function of the MMU is to map the addresses generated by the CPU onto the actual memory and to keep track of where data is stored as new tasks are created and old ones removed. With an MMU, the processor doesn’t have to worry about where programs and data are actually located.
 |
Logical and physical address space This shows the structure of both logical memory and physical memory at some point during the execution of tasks A, B, C, and D. As far as the processor is concerned, the tasks all occupy single blocks of address space that are located consecutively in logical memory. If you examine the physical memory, the actual tasks are distributed in real memory in an almost random fashion. Both tasks B and C are split into non-consecutive regions, and there are two regions of physical memory that are currently unallocated. Note also that the logical address space seen by the processor is larger than the physical address space—task D is currently located on the hard disk and is not in the computer’s RAM. |
Consider a system with 4 Kbyte logical and physical pages, and suppose the processor generates the logical address 88123416. This 24-bit address is made up of a 12-bit logical page address 88116 and a 12-bit word address 23416. The 12 low-order bits, 23416, define the same relative location within both logical and physical address pages. The logical page address is sent to the MMU which looks up the corresponding physical page address in entry number 881 in the page table. The physical page address found in this location is passed to memory.
 |
Mapping logical address space onto
physical address space Let’s look at the way in which the MMU carries out the mapping process. This demonstrates how the pages or frames of logical address space are mapped onto the frames of physical address space. The corresponding address mapping table is given by the table below. Notice that logical page 3 and logical page 8 are both mapped onto physical page 6. This situation might arise when two programs share a common resource (e.g., a compiler or an editor). Although each program thinks that it has a unique copy of the resource, both programs access a shared copy of the resource. |
|
Logical to physical address mapping table |
We’ve already said that a computer can execute programs larger than its physical memory. The means of accomplishing such an apparently impossible task is called Virtual memory and was first used in the Atlas computer at the University of Manchester, England, in 1960. mapping.
 |
A system with a smaller physical address space than a logical address space This illustrates a system with ten logical address pages but only five physical address pages. Consequently, only 50% of the logical address space can be mapped onto physical address space. The table below provides a logical page to physical page mapping table for this situation. Each entry in the logical address page table has two entries: one is the present bit that indicates whether the corresponding page is available in physical memory; the other is the logical page to physical page
|
|
Logical to physical address mapping table |
Because it’s impossible to fit all the data required by the processor in main memory at any instant, part of the data must remain on disk. When the processor generates a logical address, the memory management unit reads the mapping table to get the corresponding physical page address. If the page is present, a logical to physical address translation takes place and the operand is accessed. If the logical page is currently not in memory, an address translation cannot take place. In this case, the MMU sends a special type of interrupt to the processor called a page-fault.
When the processor detects a page-fault from the MMU, the operating system intervenes and copies a page of memory from the disk to the random access memory. Finally, the operating system updates the page mapping table in the MMU, and reruns the faulted memory access. This arrangement is called virtual memory because the processor appears to have a physical memory as large as its logical address space.
Virtual memory works effectively only if, for most of the time, the data being accessed is in physical memory. Fortunately, accesses to programs and their data are highly clustered. Operating systems designers speak of the 80:20 rule—for 80% of the time the processor accesses only 20% of a program. Note that the principles governing the operation of virtual memory are, essentially, the same as those governing the operation of cache memory.
When a page-fault is detected, the operating system transfers a new page from disk to physical memory, and overwrites a page in physical memory. So, which page gets the chop when a new page is loaded in memory? The most sensible way of selecting an old page for removal is to take the page that is not going to be required in the near future. Unfortunately, this algorithm is impossible to implement.
A simple page replacement algorithm is called the not-recently-used algorithm, NRU. When a page is created, it is marked with a time bit. The time bit is changed periodically (e.g., every 50 ms), and therefore, some pages are marked with a 1 and some with a 0. Suppose that the current time bit is 1, and a new page is marked with a 1. If a page is to be removed, the operating system selects a page at random that has a time bit set to 0. In this way, you ensure that the page you are overwriting was created in a previous time slot. The NRU algorithm is not optimum, but it is very easy to implement.
When an old page is replaced by a new page, any data in the old page frame that has been modified since it was created must be written back to disk. A typical virtual memory system clears a dirty bit in the page table when the page is first created. Whenever the processor performs a write operation to an operand on this page, the dirty bit is set. When this page is swapped out (i.e., overwritten by a new page), the operating system looks at its dirty bit. If this bit is clear, nothing need be done; if it is set, the page must be copied to disk.
Virtual memory allows the programmer to write programs without having to know anything about the characteristics or real memory and where the program is to be located. We are now going to look at another of life’s nasty realities that the operating system has to deal with—the computer equivalent of the gridlock.
Operating systems manage several tasks in a multitasking system. These tasks require various resources during the course of their execution; for example the CPU, the disk, access to other files, the printer, the mouse, the display, memory, and so on. One of the problems an operating system has to contend with is called deadlock that occurs when the operating system can’t go forward, and it can’t go back...
 |
The gridlock A type of deadlock that is found in everyday (big city) life is the gridlock. None of the lanes can move because each lane blocks its neighbor. The west bound lane is blocked by traffic in the south bound lane. But traffic in the south bound lane is blocked by traffic in the east bound lane. Traffic in the east bound lane is blocked by traffic in the north bound lane. Traffic in the north bound lane is blocked by traffic in the west bound lane, and so on.
|
Consider a situation in which process A in a computer has all the resources it needs to run, apart from the disk drive, which has been assigned to process B. Process A can run as soon as process B has used the disk drive and freed it. Process B has all the resources it needs to run, apart from the printer, which is currently assigned to process A. As soon as process A has released the printer, process B can run. This is an example of a deadlock because both processes have some of the resources they need, but neither process can run because the other has a resource it needs.
An operating system can deal with deadlock in several ways. The operating system can apply deadlock detection and periodically examine the way in which resources are currently allocated to processes. If a deadlock situation is detected, the operating system must take back resources that have been assigned to processes and then re-assign them. In terms of the gridlock analogy, the operating system is acting as a traffic cop that intervene and sorts out problems. This strategy can be expensive, because processing time is lost each time the operating system goes looking for deadlock. Moreover, it is not a completely effective strategy, because deadlocked processes are not dealt with until after they have occurred.
An alternative approach is to employ deadlock prevention and ensure that processes never become deadlocked. Essentially, the way in which resources are allocated to processes is designed to prevent deadlock. For example, if a process is required to specify all the resources it needs before it runs, the operating system can determine whether a deadlock will occur.
If the operating system permits a process to run only when all the resources it requires are free, deadlock cannot occur. Unfortunately, this strategy is sometimes very inefficient because resources may lie idle for a long time. Another solution is to force blocked processors (i.e., processes waiting for resources) to release resources in favor of a currently running process.
We have now looked at some of the ways in which the operating system controls the computer’s resources. We’re now going to look at how it controls another resource—the user.
Users interact with operating systems in one of two ways: via a command language like UNIX or MS-DOS, or via a graphical user interface, GUI, like Windows. The user interface is, of course, only a means of communication between the human and the operating system—the underlying operating system that manages files and switches between tasks is not directly affected by the user interface. Here we take a brief look at two user interfaces: the command line driven MS-DOS, and the Windows graphical user interface.
Operating systems have been around for a long time and their history is as fascinating as that of the processor architectures themselves. In the early days of the computer when all machines were expensive mainframes, the major computer companies designed operating systems to run on their own machines. One of the first operating systems that could be used on a variety of different computers was UNIX, which was designed by Ken Thompson and Dennis Richie at Bell Labs. UNIX was written in C; a systems programming language designed by Richie. Originally intended to run on DEC’s primitive PDP-7 minicomputer, UNIX was later rewritten for the popular PDP-11. This proved to be an important move, because, in the 1970’s, most university computer science departments used PDP-11s. Bell Labs was able to license UNIX for a nominal fee, and, therefore, UNIX rapidly became the standard operating system in the academic world.
UNIX is a very powerful and flexible, interactive, timesharing operating system that was designed by programmers for programmers. What does that mean? If I said that laws are written for lawyers, I think that a picture might be forming in your mind. UNIX is a user friendly language like a brick is an aerodynamically efficient structure. However, UNIX is probably the most widely used operating system in many universities—this is what Andrew Tannenbaum had to say on the subject
“While this kind of user interface [a user friendly system] may be suitable for novices, it tends to annoy skilled programmers. What they want is a servant, not a nanny.”
UNIX is a powerful and popular operating system because it operates in a consistent and elegant way. When a user logs in to a UNIX system, a program called the shell interprets the user’s commands. The commands of UNIX take a little getting used to, because they are heavily abbreviated and the abbreviations are not always what you might expect; for example, if you want help you type man which is short for “manual”. Similarly, the MS-DOS command type that lists the contents of a text file is given the more obscure name cat (short for catalogue) in UNIX. To be fair, UNIX facilities like the wildcard character “*” make it very easy to carry out powerful operations; for example, the command rm *.tmp allows you to delete any file that has the extension tmp.
Because of UNIX’s immense popularity in the academic world, it influenced the thinking of a generation of programmers and systems designers.
The first truly popular command line operating system was MS-DOS because it was designed to run on IBM’s PC. In 1980 IBM commissioned Bill Gates to produce an operating system for their new PC. Bill Gates was known to IBM because he had written a version of the language BASIC for the Intel 8080-based Altair personal computer. Because IBM’s original PC had only 64K bytes of RAM and no hard disk, a powerful operating system like UNIX could not be supported. Gates didn’t have time to develop an entirely new operating system, so his company, Microsoft, bought an operating system called 85-DOS. This product was modified and renamed MS-DOS (Micro Soft Disk Operating System).
Version 1.0 of MS-DOS, which was released in 1981, occupied 12K bytes of memory and supported only a 160 Kbyte 5 ¼” diskette. MS-DOS performed all its input and output transactions by calling routines in a read-only memory within the PC. These I/O routines are called the PC’s BIOS (basic input/output system). MS-DOS 1.0 also included a command processor, command.com, like UNIX’s shell.
Over the years Microsoft refined MS-DOS to take advantage of the improved hardware of later generations of PCs. MS-DOS 1.0 begat version 1.1, which begat version 2.0, and so on. After much begetting, which made Bill Gates one of the richest men in the World, MS-DOS reached version 6.2 in 1994. New versions of MS-DOS are eagerly awaited, and many PC users purchase the updates as soon as they are released. With so many versions of MS-DOS sold in such a short time, I would not be surprised if someone made the comment “You don’t buy MS-DOS; you rent it”.
MS-DOS now shares many of the features of UNIX but it lacks UNIX’s consistency. More importantly, the pressure to maintain backward compatibility with older versions of PCs and PC software has meant that MS-DOS cannot handle programs larger than 640 Kbytes. MS-DOS was designed for the 8086 microprocessor that could address only 220 = 1 Mbyte of address space. Unlike UNIX, MS-DOS was not designed as a timesharing system and, therefore, there is no logon procedure. In other words, MS-DOS has no security mechanism and the user can do anything he or she wants. UNIX has a superuser who is protected by a password and who has special privileges. The superuser is able to configure and maintain the operating system.
Any operating system has to access various types of data structure called, collectively, files. A file might be a program, a text document, a spreadsheet, a table, a figure, or any other data structure. Files have names that allows you, other programs and the operating system to access them. An MS-DOS file name is, unfortunately, restricted to eight characters (UNIX file names can be up to 255 characters). UNIX and MS-DOS allow the type of the file to be described by an extension after the filename; for example, the MS-DOS file test.exe indicates a file called test that is in the form of an executable program. Both UNIX and MS-DOS do not enforce the way in which file extensions are used—you can give a file any extension you want.
The data structure that holds the names of files is called a directory. Although all the names of the files can be put in a single directory, most computer users would find this approach impractical. A modern PC might have hundreds or even thousands of files. MS-DOS provides a hierarchical file structure that mimics the way in which people store their own information. Disk file structures are often compared to the filing cabinet, that has a series of draws holding folders and each folder contains individual files.
 |
The hierarchical file structure This shows how the filing cabinet analogy is applied to MS-DOS. A disk contains a directory called the root directory, that may contain files and subdirectories. Each subdirectory may contain files and further subdirectories.
|
A hierarchical file structure permits you to arrange files according to the way in which you use them. My own computer has a root directory containing the subdirectories TEESSIDE, personal, books, and publishers; the subdirectory publishers has further subdirectories PWS, OUP, WEST, MCGRAW. When you wish to access a file, you have to specify the path by which it is reached; for example, a letter to WEST called MAY21.DOC might be accessed via the path D:\PUBLISHERS\WEST\MAY21.DOC. The path is defined by starting at the root directory (i.e., disk drive D which is represented by D:\) and then moving through the successive subdirectories until the file has been located. The delimiter in this hierarchical structure is the backslash, \.
One of the advantages of a hierarchical structure is that file names don’t have to be unique. There is nothing to stop a filing system having a file called MAY21.DOC in two (or more) different subdirectories. Specifying the location of each file by means of its full path soon becomes tedious—especially when lots of files in many different subdirectories are to be accessed. MS-DOS alleviates this problem by means of the PATH command. MS-DOS is configured or tailored to your own particular environment by means of two special files, AUTOEXEC.BAT and CONFIG.SYS. You can use a PATH command in the AUTOEXEC.BAT file to provide MS-DOS with a list of paths to be searched for a file. For example, the statement PATH C:\;D:\WINDOWS;D:\PCTOOLS tells the operating system to look for a file first in the root directory on drive C, then in the subdirectory WINDOWS on drive D, and finally in the subdirectory PCTOOLS on drive D.
MS-DOS can be configured or tailored to the specific system on which it is to run. We have just said that when MS-DOS is first loaded into memory, two files called CONFIG.SYS and AUTOEXEC.BAT, are automatically executed. These files set up an environment to suit the structure of the computer; they tell the operating system where to find device drivers for the video display, the mouse, the printer, the sound card, and so on. The advantage of MS-DOS’s configuration files is that they allow the system to be tailored to suit the actual software and hardware environment. The disadvantage is that the configuration files can become quite complex and difficult for a non-expert user to understand.
Many believe that one of the most important factors in encouraging the expansion of computers into non-traditional environments has been the development of intuitive, user-friendly interfaces.
On the other hand, every time you install a new package, there is a good chance that it will modify the two configuration files (more if it runs under Windows). After a time, the configuration files become very difficult to understand. Even worse, when you delete an application, the changes it made to the configuration file are left behind.
Like UNIX, MS-DOS is, essentially, a programmer’s language. The need to make computers accessible to those who want to employ them as a tool, forced the development of graphical user interfaces like Windows. We don’t cover Windows here in any detail, because many of its features belong in the chapter on human computer interaction, HCI. Windows provides a GUI, or graphical user interface that the user accesses by means of a mouse (or any other pointing device).
Microsoft’s Windows is not just an operating system, it is a front-end that sits between the user and the underlying system
 |
A Windows screen This demonstrates the structure of a typical Windows screen. Programs and files (or directories) are grouped logically into sub-windows, and programs are run simply by moving the cursor to the appropriate icon and then double-clicking a button on the mouse. You don’t have to worry about learning the syntax of an operating system’s job control language to use Windows. |
 |
The pull-down menu This demonstrates a typical applications program, Microsoft Word, running under Windows. User programs employ the same type of interface used by Windows itself. The way in which commands are accessed is by means of pull-down menus. Here, the cursor has been moved to the item Edit on command line. Clicking on Edit pulls down a more detailed menu. In this case, the menu has 15 items. Some are grayed because they do not currently apply (e.g., Cut is grayed because no text has been selected and therefore this command is not available). The commands in a block can be activated by clicking on them or by pressing the keys given in the menu). If commands in a pull-down menu followed by three dots (e.g., Go To...) are selected and the mouse clicked, a further submenu is displayed. These submenus allow you to home in on the function you wish to carry out. This type of graphical operating system interface is good because many users can access operating system functions or use applications programs without ever reading the user’s manual. However, some programmers don’t like the GUI environment because they feel that the traditional command language is much more efficient and concise. In many ways this criticism of the Windows environment is valid. I have had to work with systems that require three windows to be pulled down and several parameters selected in boxes just to carry out a trivial action. Many software suppliers have appreciated this problem and now permit the user to define a button or an icon to perform an operation that they have defined. |
Over the years, the role of operating systems has broadened. At the beginning of this chapter we said that the operating system controlled the operation of the computer and performed no useful “applications level” work. The distinction between operation system and application is gradually blurring. Competition between software writers has forced operating systems designers to incorporate more and more added value. For example; operating systems like Windows 95 now incorporate network management functions, applications such as editors and calculators, and even gateways to the Internet.
The primary functions of an operating system are to manage system resources and to provide a user interface.
Operating systems can operate in: batch mode, timesharing mode, and real-time.
An operating system controls the disk system and automatically manages files.
An operating system loads programs and data in memory and automatically assign blocks of free memory to them.
The operating system is responsible for managing interrupts.
In a multitasking system, the operating system switches between tasks (or processes) so rapidly that the computer appears to be running several programs simultaneously.
The way in which a multitasking operating system decides which task is to be executed next, determines the nature of the operating system (e.g., real time, or timesharing).
The operating system manages the processor’s logical address space and maps logical addresses onto physical address space.
MS-DOS is a command-line driven operating system that has some of the characteristics of UNIX, but lacks UNIX’s consistency and multitasking facilities.
The Windows GUI (graphical user interface) environment runs on top of MS-DOS and provides a user interface that can be employed by users with little or no understanding of formal computer science and the syntax of computer command languages.
Under what circumstances is an operating system unnecessary?
Why are operating systems with a graphical user interface proving so popular?
Why do you think that some users don’t like graphical user interfaces?
A floppy disk can hold 1.4Mbytes of data and a punched card can hold 80 characters (bytes). Assume that the average punched card contains 40 characters and weighs 1 gm. What is the total weight of punched cards that can be carried on a floppy disk?
A multitasking system has 10 tasks. The overhead in switching between two tasks is 200µs. Suppose you wish to implement a time sharing system using the round robin scheduling algorithm and switch tasks as rapidly as possible. If the maximum overhead you are willing to allocate to task switching is 20% of the available processor time, what is the shortest time slice you can allow a process?
Six tasks, t1, t2, t3, t4, t5, and t6, have durations of 10, 20, 1, 5, 5, 9ms, respectively. What is the average waiting time if a first-come first-served scheduling algorithm is used?
For the same data as question 6, what would the average waiting time be if the smallest task first algorithm were used?
Write a program to emulate the task scheduling kernel of an operating system. To do this you will have to design your own task control block, and select a suitable task scheduling algorithm.
What is the difference between a logical address and a physical address?
Under what circumstances can a system’s logical address space be larger than the system’s physical address space? If you designed a system whose physical address space was larger than its logical address space, what do you think the consequences would be?
What is a hierarchical file structure and why is it so important? Can you think of any other way of organizing a file structure?
Tannenbaum prefers operating systems for programmers to operating systems for non-computer specialists. To what extent do you think that his feelings are justified? Suggest ways in which an operating system could be constructed to get the best of both worlds (i.e., a level of terseness that isn’t an insult to a professional programmer and a degree of user friendliness that enables even users with little or no training to cope)?
The PATH statement that can be used in an MS-DOS AUTOEXEC.BAT file tells the operating system which pathways to search for files whose locations are not specified fully. What are the advantages and disadvantages of the PATH statement?
Some professional programmers and computer scientists regard UNIX as a good operating system and MS-DOS as a bad operating system? Why do you think that they have formed this view? If MS-DOS is less than optimum, what factors do you think contributed?
Design a better, more flexible, and more powerful language than that used by the MS-DOS interface. For example, consider way of allowing more than one instruction to be written on the same line.
How do you think that the Windows environment could be improved to overcome the criticisms of those who prefer traditional command line operating systems like MS-DOS and UNIX.