View source for Guide to Multitasking Operating Systems:Fundamentals of Operating Systems

An operating system is a program that acts as an intermediary between a user and the computer hardware. The purpose of an operating system is to provide an environment in which a user can execute programs in a convenient and efficient manner.

The operating system must ensure the correct operation of the computer system. To prevent user programs from interfering with the proper operation of the system, the hardware must provide appropriate mechanisms to ensure such proper behavior.

The operating system provides certain services to programs and to the users of those programs in order to make the programming task easier.

Basically the functions of an operating system are:

* Program execution
* I/O operations
* File system
* Error detection
* Resource allocation
* Protection 

==Introduction to Operating Systems==

The first and basic need of an OS is to overcome the idle time of the CPU. In the beginning, jobs were run one at a time with the computer operator literally operating the computer by loading time cards and pushing buttons on the computer console. As time progressed, resident monitors, the first OS's, sat in main memory and automatically transferred control from one job to the next. This reduced the idle time of the CPU between jobs but not during the execution of jobs.

With this automatic sequencing, however, the CPU is often idle. The problem is the speed of the mechanical I/O devices, which are intrinsically slower than electronic devices. Even a slow CPU works in the microsecond range, with millions of instructions executed per second. A fast disk, on the other hand, might have a response time of 15 milliseconds and a transfer rate of 1 megabits/second, on an order of a magnitude slower than a typical CPU.

The slowness of the I/O devices can mean that the CPU is often waiting for I/O. As an example, as an examplem an assembler or compiler may be able to process 300 or more cards per second. A fast card reader, on the other hand, might read only 17 cards per second. This means that assembling a 1200 card program would require only 4 seconds of CPU time, but 60 seconds to read. Thus, the CPU is idle for 56 out of 60 seconds, or 93.3 percent of the time. The resulting CPU utilization is only 6.7 percent. The process is similar for output operations. The problem is that, while an I/O operation is occurring, the CPU is idle, waiting for the I/O to complete; while the CPU is executing, the I/O devices are idle.

Over time, of course, improvements in technology resultedin faster I/O devices. But CPU speeds increased even faster, so that the problem was not only unresolved, but also worsened.

====Off-line Operations====

One common solution was to replace the very slow card readers(input devices) and line printers(output devices) with magnetic-tape units. The majority of computer systems in the late 1950's and early 1960's were batch systems reading from card readers and writing to line printers or card punches. Rather than have the CPU read directly from cards, however, the cards were first copied onto a magnetic tape. When the tape was sufficiently full, it was taken down and carried over to the computer. When a card was needed for input to a program, the equivalent record was read from tape. Similarly, output was written to the tape and the contents of the tape would be printed later. The card readers and line printers were operated off-line, not by the main computer.


card reader ---->  CPU   ---- line printer
a.) on-line
card reader ---- tape drives ---- CPU ---- tape drives ---- line printer
b.) off-line

The main advantage of off-line operation was that the main computer was no longer constrained by the speed of the card readers and line printers, but was limited by the speed of the much faster magnetic tape units.

====Buffering and Spooling====

Buffering is the method of overlapping the I/O of a job with its own computation. The idea is quite simple. After data have been read and the CPU is about to start operating on them, the input device is instructed to begin the next input immediately. The CPU and the input device are then both busy. With luck, by the time that the CPU is ready for the next data item(record), the input device will have finished reading it. The CPU can then begin processing the newly read data, while the input device starts to read the following data. Similarly, this can be done for output. In this case, the CPU creates data that are put into a buffer until an output device can accept them.

Although off-line preparation of jobs continued for some time, it was quickly replaced in most systems. Disk systems became widely available and greatly improved on off-line operation. The problem with tape systems was that the card reader could not write onto one end of the tape while the CPU read from another. The entire tape had to be written before it was rewound and read. Disk systems eliminated this problem. Because the head is moved from one area of the disk to another, a disk can rapidly switch from the area of the disk being used by the card reader to store new cards to the position needed by the CPU to read the 'next' card.

In a disk system, cards are read directly from the card reader onto the disk. The location of card images is recorded in a table kept by the operating system. When a job is executed, the operating system satisfies its requests for card reader input by reading from the disk. Similarly, when the job requests the printer to ouput a line, that line is copied into a system buffer and is written to the disk. When the job is completed, the output is actually printed.

This form of processing is called spooling. The name is an acronym for simultaneous peripheal operation on-line. Spooling essentially uses the disk as a very large buffer, for reading as far ahead as possible on input devices and for storing output files until the output devices are able to accept them.

                   disk



 card reader        CPU              line printer

In addition, spooling provides a very important data structure: a job pool. Spooling will generally result in several jobs that have already been read waiting on disk, ready to run. A pool of these jobs on disk allows the operating system to select which job to run next, in order to increase CPU utilization. When jobs come in directly from tape, it is not possible to skip around and to run jobs in a different order. Jobs must be run sequentially, on a first-come, first-served basis. However, when several jobs are on a direct access device, such as a disk, job scheduling becomes possible.

The most important aspect of job scheduling is the ability to multiprogram. Off-line operation, buffering, and spooling for overlapped I/O have their limitations. A single user cannot, in general, keep either the CPU or the I/O devices busy at all times. Multiprogramming increases CPU utilization by organizing jobs so that the CPU always has something to execute.

The idea is as follows. The operating system picks and begins to execute one of the jobs in the job pool. Eventually, the job may have to wait for some task, such as a tape to be mounted, a command to be typed on a keyboard, or an I/O operation to complete. In a non-multiprogrammed system, the CPU would sit idle. In a multiprogramming system, the operating system simply switches to and executes another job. When that job needs to wait, the CPU is switched to another job, and so on. Eventually, the first job finishes waiting and gets the CPU back. As long as there is always some job to execute, the CPU will never be idle.

Multiprogrammed operating systems are fairly sophisticated. To have several jobs ready to run, the system must keep all of them in memory simultaneously. Having several programs in memory at the same time requires some form of memory management. In addtion, if several jobs are ready to run at the same time, the system must choose among them. This decision is CPU Scheduling. Finally, multiple jobs running concurrently require that their ability to affect one another be limited in all phases of the operating system, including process scheduling, disk storage, and memory management.

      0  ___________
        |           |
        |  monitor  |
        |___________|
        |           |
        |   job 1   |
        |___________|
        |           |
        |   job 2   |
        |___________|
        |           |
        |   job 3   |
        |___________|
        |           |
        |   job 4   |
        |___________|
        |           |
        |           |
  512 K |___________|

====Multitasking====

Multitasking(or time sharing) is a logical extension of multiprogramming. Multiple jobs are executed by the CPU switching between them, but the switches occur so frequently that the users may interact with each program while it is running. To understand the difference, we will first review the batch method.

When batch systems were first developed, they were defined by the 'batching' together of similar jobs. Card- and tape-based systems allowed only sequential access to programs and data, so only one application package( the FORTRAN compiler, linker, and loader, or the COBOL equivalents, for instance) could be used at a time. As on-line disk storage became feasible, it was possible to provide immediate access to all of the application packages. Modern batch systems are no longer defined by the batching together of similar jobs; other characteristics are used instead.

A batch operating system normally reads a stream of separate jobs(from a card reader, for example), each with its own control cards that predefine what the job does. When the job is complete, its output is usually printed (on a line printer, for example). The definitive feature of a batch system is the lack of user interaction between the user and the job while that job is executing. The job is prepared and submitted. At some later time(perhaps minutes, hours, or days), the output appears. The delay between job submission and job completion(called turnaround time) may result from the amount of computing needed, or from delays before the operating system starts processing the job.

An interactive, or hands-on, computer system provides on-line communication between the user and the system. The user gives instructions to the operating system or to a program directly, and receives an immediate response. When the operating system finishes the execution of one command, it seeks the next 'control statement'. The user can easily experiment and can see results immediately.

Time-sharing systems were developed to provide interactive use of a computer system at a reasonable cost. A time-shared operating system uses CPU scheduling and multiprogramming to provide each user with a small portion of a time-shared computer. Each user has a separate program in memory. When a program executes, it typically executes for only a short time before it either finishes or needs to perform I/O. I/O may be interactive; that is, output to a display, or input from a keyboard. Five characters per second may be fairly fast for people, but it is very slow for computers. Rather than let the CPU sit idle when this happens, the operating system will rapidly switch the CPU to the program of some other user.

Time-sharing operating systems are sophisticated. They provide a mechanism for concurrent execution. Also, as in multiprogramming, several jobs must be kept simultaneously in memory, which requires some form of memory management, protection, and CPU scheduling. So that a reasonable response time can be obtained, jobs may have to be swapped in and out of main memory. Hence, disk management must also be provided. Time-sharing systems must also provide an on-line file system and protection.

====System Calls====

System calls provide the interface between a running program and the operating system. These calls are generally available as assembly- language instructions, and are usually listed in the manuals used by assembly-language programmers.

Some systems may allow system calls to be made directly from a higher-level language programm in which case the calls normally resemble predefined function or subroutine calls. They may generate a call to a special run-time routine that makes the system call, or the system call may be generated directly in-line.

Several languages, such as C, Bliss, and PL/360, have been defined to replace assembly language for systems programming. These languages allow system calls to be made directly.

Three general methods are used to pass parameters to the operating system. The simplest approach is to pass the parameters in registers. In some cases, however, there may be more parameters than registers. In these cases, the parameters are generally stored in a block or table in memorym and the address of the block is passed as a parameter in a register. Parameters may also be placed, or pushed, onto the stack by the program, and popped off the stack by the operating system.

System calls can be roughly grouped into five major categories: process control, file manipulation, device manipulation, information maintenance, and communications

  1.) Process Control
      - End, Abort
      - Load, Execute
      - Create Process, Terminate Process
      - Get Process Attributes, Set Process Attributes
      - Wait for Time
      - Wait Event, Signal Event
      - Allocate Memory, Free Memory
  2.) File Manipulation
      - Create File, Delete File
      - Open, Close
      - Read, Write, Reposition
      - Get File Attributes, Set File Attributes
  3.) Device Manipulation
      - Request Device, Release Device
      - Read, Write, Reposition
      - Get Device Attributes, Set Device Attributes
      - Logically Attach  or Detach Devices
  4.) Information Maintenance
      - Get Time or Date, Set Time or Date
      - Get System Data, Set System Data
      - Get Process, File, or Device Attributes
      - Set Process, File, or Device Attributes
  5.) Communications
      - Create, Delete Communication Connection
      - Send, Receive Messages
      - Transfer Status Information

====System Structure====


==Process Management==

This topic deals with handling the many programs that may be in main memory at once. 

====Introduction to Process Management====

A process is a program in execution. In general, a process will need certain resources-such as CPU time, memory, files, and I/O devices-to accomplish its task. These resources are allocated to the process either when it is created, or while it is executing.

A process is the unit of work in most systems. Such a system consists of a collection of processes: operating system processes execute system code, and user processes execute user code. All of these processes can potentially execute concurrently.

The operating system is responsible for the following activities in connection with process management: the creation and deletion of both user and system processes; the scheduling of processes, and the provision of mechanisms for synchronization, communication, and deadlock handling for processes.

A process is more than the program code plus the current activity. A process generally also includes the process stack containing temporary data(such as subroutine parameters, return addresses, and temporary variables), and a data section containing global variables.

Note : A program by itself is not a process; a program is a passive entity, such as the contents of a file stored on disk, whereas a process is an active entity, with a program counter specifying the next instruction to execute. 

====Process State====

As a process executes, it changes state. The state of a process is defined in part by that process's current activity. Each process may be in one of three states:

[[Image:]]

'''Figure: Process State Diagram'''

* Running. Instructions are being executed.
* Waiting. The process is waiting for some event to occur(such as an I/O completion).
* Ready. The process is waiting to be assigned to a processor 

These names are rather arbitrary, and vary between operating systems. The states they represent are found on all systems, however. It is important to realize that in a single-processor system, only one process can be running at any instant. Many processes may be ready and waiting, however. 

====Process Control Block====

Each process is represented in the operating system by its own process control block(PCB). A PCB is a data block or record containing many pieces of the information associated with a specific process, including

* Process State. The state may be new, ready, running, waiting, or halted.
* Program Counter. The counter indicates the address of the next instruction to be executed for this process.
* CPU State. This includes the contents of general purpose registers, index registers, stack pointers, and any condition-code information. Along with the program counter, this state information must be saved when an interrupt occurs, to allow the process to be continued correctly afterward.
* CPU Scheduling Information. This information includes a process priority, pointers to scheduling queues, and any other scheduling parameters.
* Memory-management information. This information includes limit registers or page tables.
* I/O Status Information. The information includes outstanding I/O requests and a list of open files. 

The PCB serves as the repository for any information that may vary from process to process.

[[Image:]]

''Figure: The CPU can be switched from process to process'' 

====Concurrent Processes====

The processes in the system can execute concurrently; that is, many processes may be multitasked on a CPU. There are several reasons for allowing concurrent execution:

* Physical Resource Sharing. Since the computer hardware resources are limited, we may be forced to share them in a multiuser environment.
* Logical Resource Sharing. Since several processes may be interested in the same piece of information(for instance, a shared file), we must provide an environment to allow concurrent processes access to these types of resources.
* Computation speedup. If we want a particular task to run faster, we may break it into sub-tasks, each of which will be executing in parallel with the others. Notice that such a speed up can be achieved only if the computer has multiple processing elements(such as CPUs or channels)
* Modularity. We may want to construct the system in a modular fashion, dividing the system functions into separate processes.
* Convenience. Even an individual user may have many tasks to work on at one time. For instance, a user may be editing, printing, and compiling in parallel. 

Concurrent execution that requires cooperation among the processes requires a mechanism for process synchronization and communication.