Operating System

INTRODUCTION

Operating system is a program that manages the computer hardware. It also provides a basis for application programs and acts as an intermediary between a user of a computer and the computer hardware. An operating system is an important part of almost every computer system. A computer system can be divided roughly into four components:
The hardware – the central processing unit (CPU), the memory, and the input/output (I/O) devices provides the basic computing resources.
The operating system - controls and coordinates the use of the hardware among the various application programs for the various users.
Application programs – such as word processors, spreadsheets, compilers, and web browsers define the way in which these resources are used to solve the computing problems of the users.
Users.

MAINFRAME SYSTEMS

Mainframe computer systems were the first computers used to tackle many commercial and scientific applications.

1.Batch Systems
The user did not interact directly with the computer systems. They prepared a job which consisted of the program, the data, and some control information about the nature of the job and submitted it to the computer operator. After some days the output appeared. The output consisted of the result of the program. The major task was to transfer control automatically from one job to next.
To speed up processing, operators batched together jobs with similar needs and ran them through the computer as a group. Thus the programmers leave their programs with the operator. The operator would sort programs into batches with similar requirements and, as the computer became available, would run each batch. The output from each job would be sent back to the appropriate programmer.

2.Multiprogrammed Systems

Multiprogramming increases CPU utilization by organizing jobs so that the CPU always has one to execute.The concept of multiprogramming is that the operating system keeps several jobs in memory simultaneously. This set of jobs are kept in the job pool. The OS picks up and execute one of the jobs in the memory.
· In non-multiprogramming system, the CPU would sit idle.
· In multiprogramming system, the OS simply switches to, and executes, another job. When that job needs to wait, the CPU is switched to another job, and so on. The first finishes waiting and gets the CPU back. As long a at least one job needs to execute, the CPU is never idle.
Multiprogramming operating systems are used for decisions for the users. All the jobs that enter the system are kept in the job pool. This pool consists of all processes residing on disk awaiting allocation of main memory. If several jobs are ready to be brought into memory, and if there is not enough room for all of them, then the system must choose among them. Making this decision is job scheduling. If several jobs are ready to run at the same time, the system must choose among them, this decision is CPU scheduling.

3.Time – Sharing Systems

Time sharing or multitasking is a logical extension of multiprogramming. The CPU executes multiple jobs by switching among them, but the switches occur so frequently that the users can interact with each program while it is running.
An interactive (or hands-on) computer system provides direct communication between the user and the system. The user gives instructions to the operating system or to a program directly, using a keyboard or a mouse, and waits for immediate results.
A time-shared operating system allows many users to share the computer simultaneously. Each action or command in a time –shared system tends to be short, only a little CPU time is needed for each user. As the system switches rapidly from one user to the next, each user is given the impression that the entire computer system is dedicated to her use, even though it is being shared among many users.
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 atleast one separate program in memory. A program loaded into memory and executing is commonly referred to as a process. When a process executes, it typically executes for only a short time before it either finishes or needs to perform I/O.

DESKTOP SYSTEMS

Personal computers PCs appeared in the 1970s. During their first decade, the CPUs in PCs lacked the features needed to protect an operating system from user programs. PC operating systems therefore were neither multiuser nor multitasking. The MS-DOS operating system from Microsoft has been produced multiple flavors of Microsoft Windows, and IBM has upgraded MS-DOS to OS/2 multitasking system. UNIX is used for its scalability, performance, and features but retains the same rich GUI. Linux, a UNIX operating system available for PCs, has also become popular recently.
OS has developed for mainframes. Micro computers were able to adopt some of the technology developed for larger OS. On the other hand, the hardware costs for micro computers are sufficiently low that individuals have sole use of the computer, and the CPU utilization is no longer a prime concern.
Earlier file protection was not necessary on a personal machine. But these computers are now often tied into other computers over local-area networks or other Internet connections. When other computers and other users can access the files on a PC, file protection becomes essential feature of the operating system. The lack of such protection has made it easy for malicious programs to destroy data on the systems such as MS-DOS and the Macintosh operating system. These programs are self-replicating, and may spread rapidly via worm or virus mechanism.
MULTIPROCESSOR SYSTEMS

Multiprocessor systems have more than one processor or CPU. Multiprocessor systems also known as parallel systems. Such systems have more than one processor in close communication, sharing the computer bus, the clock, and sometimes memory and peripheral devices.

Advantages of the multiprocessor systems are:

1. Increased throughput: By increasing the number of processors, get more work done in less time. When multiple processors cooperate on a task, a certain amount of overhead is incurred in keeping all the parts working correctly.
2. Economy of scale: Multiprocessor systems can save more money than multiple singe-processor systems, because they can share peripherals, mass storage, and power supplies. If several programs operate on the same set of data, it is cheaper to store those data on one disk and to have all the processors share them, than to have many computers with local disks and many copies of the data.
3. Increased reliability: If functions can be distributed properly among several processors, then the failure of one processor will not halt the system, only slow it down.
The most common multiple-processor systems now use symmetric multiprocessing (SMP), in which each processor runs on identical copy of the OS, and these copies communicate with one another as needed. Some systems use asymmetric multiprocessing, in which each processor is assigned a specific task. A master processor controls the system, the other processors either look to the master for instruction or have predefined tasks. This scheme defines a master-slave relationship. The master processor schedules and allocates work to the slave processors.

Figure: Symmetric multiprocessing architecture



SMP means that all processors are peers, no master-slave relationship exists between processors. Each processor concurrently runs a copy of the operating system. The benefit of this model is that many processes can run simultaneously - N processes can run if there a N CPUs- without causing a significant performance. Since the CPU are separate, one may be sitting idle while another is overloaded, resulting in inefficiencies. A multiprocessor system will allow processors and resources-such s memory to be shared among the various processors.

DISTRIBUTED SYSTEMS

A network, in the simplest terms, is a communication path between two or more systems. Distributed systems depend on networking for their functionality. Distributed systems are able to share computational tasks, and provide a rich set of features to users. Networks are typecast based on the distance between their nodes.
Local area network: exists within a room, a floor, or a building.
Wide area network: exists between building, cities, or countries. A global company may have a WAN to connect its offices, world wide.
Metropolitan are network: could link buildings within a city.

1.Client – Server Systems:



Terminals connected to centralized systems are now being supplanted by CPU. Centralized systems today act as server systems to satisfy requests generated by client systems.
Server systems can be broadly categorized as compute servers and file servers.
Compute-server systems: provide an interface to which clients can send requests to perform an action, in response to which they execute the action and send back results to the clients.
File-server systems: provide a file-system interface where clients can create, update, read and delete files.

2.Peer-to-Peer Systems

The growth of computer networks especially the Internet and WWW has a profound influence on the recent development of OS. When PCs were introduced in 1970s they were developed as stand alone systems, but with the widespread public use of the Internet in 1980s for electronic mail, ftp, PCs became connected to computer networks.
Modern PCs and workstations are capable of running a web browser for accessing hypertext documents on the web. The PCs now include software that enables a computer to access the Internet via a local area network or telephone connection. These systems consist of collection of processors that do not share memory or a clock. Instead each processor has its own local memory. The processors communicate with another through various communication lines, such as high speed buses or telephone line.
OS has taken the concept of network and distributed systems for network connectivity. A network operating systems is an OS that provides features such as file sharing across the network, and that includes a communication scheme that allows different processes on different computers to exchange messages.

CLUSTERED SYSTEMS

Clustered systems gather together multiple CPUs to accomplish computational work. Clustered systems differ from parallel system, in that they are composed of two or more individual systems coupled together. Clustering is usually performed to provide high availability. A layer of cluster software runs on the cluster nodes. Each node can monitor one or more o the others. If the monitored machine fails, the monitoring machine can take ownership of its storage, and restart the application that were running on the failed machine. The failed machine can remain down, but the users and clients of the application would only see a brief interruption of service.
In asymmetric clustering, one machine is in hot standby mode when the other is running the applications. The hot standby machine does nothing but monitor the active server. If that server fails, the hot standby host becomes the active serer.
In symmetric clustering, two or more nodes are running applications, and they are monitoring each other. This mode is more efficient, as it uses all o the available hardware.
Parallel clusters allow multiple hosts to access the same data on the shared storage. Because most of the operating systems lack support for simultaneous data access by multiple hosts, parallel clusters are usually accomplished by special versions of software. Example Oracle parallel server is a version of Oracle’s database that has been designed to run on parallel clusters.

REAL-TIME SYSTEMS

A real time system is used when rigid time requirements have been placed on the operation of a processor or the flow of data; thus it is used as a control device in a dedicated application. Sensors bring data to the computer. Computer must analyze the data and possibly adjust controls to modify the sensor inputs. Systems that control scientific experiments, medical imaging systems, industrial control systems, some automobile-engine fuel-injection systems, home appliance controllers and weapon systems are also real time systems.
A real-time system has well-defined, fixed time constraints. Processing must be done within the defined constraints, or the system will fail. A real time systems functions correctly only if it returns the correct result within its time constraints.
Real time systems if of two types:
A hard real time system guarantees that critical tasks be completed on time. This goal requires that all delays in the system be bounded, from the retrieval of stored data to the time that it takes the operating system to finish any request made of it.
A soft real time system where a critical real time task gets priority over those tasks, and retains that priority until it completes. An in hard real-time systems, the OS kernel delays need to be bounded: A real-time task cannot be kept waiting indefinitely for the kernel to run it. They are useful in several areas, including multimedia, virtual reality, and advanced scientific projects such as undersea exploration and planetary rovers. These systems needs advanced operating systems.

HANDHELD SYSTEMS

Handheld systems include personal digital assistants(PDAs), such as Palm pilots or cellular telephones with connectivity to a network such as the Internet. The handheld systems are of limited size. Example, a PDA is typically 5 inches in height and 3 inches in width, and weighs less than one-half pound. Due to its limited size, handheld systems have a small amount of memory, include slow processors, and feature small display screens. They have between 512 KB and 8 MB of memory.
The next issue is the handheld devices is the speed of the processor used in the device. Processors of handheld devices often run at a fraction of the speed of a processor in a PC. Faster processors require more power. To include a faster processor in a handheld device would require a larger battery that would have to be replaced more frequently.
The last issue for the designers for handheld devices are handheld devices is the small display screens typically available. Whereas a monitor for a home computer may measure up to 21 inches, the display for a handheld device is often no more than 3 inches square. Tasks such as reading e-mail or browsing web pages, must be condensed onto the smaller displays. One approach for displaying the content in web pages is web clipping, where only a small subset of a web page is delivered and displayed on the handheld device.
Some handheld devices may use wireless technology, such as BlueTooth, allowing remote access to e-mail and web browsing. Cellular telephones with connectivity to Internet fall into this category. To download data to these devices, first the data is downloaded to a PC or workstation, and then downloads the data to the PDA. Some PDAs allow data to be directly copied from one device to another using an infrared link.

OPERATING SYSTEM STRUCTURES

An operating system may be viewed from several points.
1. By examining the services that it provides.
2. By looking at the interface that it makes available to users and programmers.
3. By disassembling, the system into its components and their interconnections.

OPERATING SYSTEM COMPONENTS:

The various system components are:
1. Process management
2. Main-memory management
3. File management
4. I/O-system management
5. Secondary-storage management
6. Networking
7. Protection system
8. Command-Interpreter system

1. Process Management
A Process is thought as a program in execution. A program does nothing unless its instructions are executed by a CPU. Example, a compiler is a process, a word processing program run by an individual user on a PC is a process, a system task, such as sending output to a printer is also a process.
A process needs certain resources including CPU time, memory, files and I/O devices to accomplish its task. These resources are either given to the process when it is created or allocated to it while it is running. A program is a passive entity, such as the contents of the file stored on disk, whereas a process is an active entity, with a program counter specifying the next instruction to be executed. The execution of the process must be sequential. The CPU executes one instruction of the process after another, until the process completes.
A process is the unit of work in a system. Such a system consists of collection of processes, some of which are operating system processes and the rest are user processes.

The OS is responsible for the following activities in process management:
· Creating and deleting both user and system processes
· Suspending and resuming processes
· Providing mechanisms for process synchronization
· Providing mechanisms for process communication
· Providing mechanisms for deadlock handling

2. Main-Memory Management

Main memory is a repository of quickly accessible data shared by the CPU and I/O devices. The central processor reads the instructions from main memory during the instruction fetch cycle, and it reads instructions from main memory during the data fetch cycle.
The main memory is the only larger storage device the CPU able to address and access directly. For a program to be executed, it must be mapped to absolute addresses and loaded into memory. As the program executes, it accesses program instructions and data from memory by generating theses absolute addresses. To improve the CPU utilization and the speed of the computer’s response to its users, we must keep several programs in memory.

The OS is responsible for the following activities in memory management:
· Keeping track of which parts of memory are currently being used and by whom
· Deciding which processes are to be loaded into memory when memory space becomes available.
· Allocating and deallocating memory space as needed.

3. File Management

A File is a collection of related information defined by its creator. Files define programs and data. Data files can be numeric, alphabetic and alphanumeric. Files may be of free form, or may be formatted rigidly. A file consists of sequence of bits, bytes, lines or records whose meanings are defined by their creators. Files are organized into directories to ease of their use. Files can be opened in different modes to be accessed, they are : read, write, append.

The OS responsibilities for the following activities for file management :
· Creating and deleting files
· Creating and deleting directories
· Supporting primitives for manipulating files and directories
· Mapping files onto secondary storage
· Backing up files on stable, nonvolatile storage media

4. I/O System Management

One of the purposes of an operating system is to hide the attributes and characters of specific hardware devices for the user.

The I/O subsystem consists of:
· A memory-management component that includes buffering, caching, and spooling
· A general device-driver interface
· Drivers for specific hardware devices
The device drivers alone know the characteristics of the specific device to which it is assigned.

5. Secondary-Storage Management

The main purpose of the computer system is to execute the programs. These programs, with the data they access, must be in main memory, or primary memory, during execution. Because the main memory is too small to hold all the data and programs, and as the data it holds is lost when the power is lost, the computer must provide secondary storage to back up main memory. Programs such as compilers, assemblers, routines, editors and formatters are stored in the disk until loaded into main memory.

The OS responsibility for the following activities for disk management:
· Free-space management
· Storage allocation
· Disk scheduling

6. Networking

A distributed system is a collection of processors that do not share memory, peripheral devices, or a clock. Each processor has its own local memory and clock, and the processors communicate with one another through various communication lines, such as high-speed buses or networks. The processors in distributed system vary in size and function. They include small micro-processors, workstations, minicomputers and large, general purpose computer systems.
A distributed system collects physically separate, and many heterogeneous systems into a single coherent system, providing user with access to the various resources that the system maintains. The shared resources allows computation speedup, increased functionality, increased data availability, and reliability.
Different protocols are used in the network system, such as file-transfer protocol (FTP), Network file-system (NFS), hypertext transfer protocol (HTTP) , for use in communication between a web server and a web browser. A web browser then just needs to send a request for information to a remote machines web server. And the information is returned.

7. Protection System

If a computer system has multiple users and allows the concurrent execution of multiple processes, then the various processes must be protected from the other process.
Protection is any mechanism for controlling the access of programs, processes, or users to the resources defined by a computer system. This mechanism must provide means for specification of the controls to be imposed and means for enforcement.
Protection can improve reliability by detecting latent errors at the interfaces between component subsystems. Early detection of interface errors can often prevent contamination of a healthy subsystem by another subsystem. Unprotected system can be used by unauthorized users.

8. Command-Interpreter System

Command interpreter is an interface between the user and the operating system. Many commands are given to the operating system by control statements. When a new job is started in a batch system, or when a user logs on to a time-shared system, a program that reads and interprets control statement is executed automatically. This program is sometimes called the control card interpreter or command-Interpreter, and is often known as the shell. Its function is to get the next command statement and execute it.

OPERATING SYSTEM SERVICES

An operating system provides an environment for the execution of programs. It provides certain services to programs and to the users of those programs.
The various services offered by Operating system are:

· Program execution: The system may be able to load a program into memory and to run that program. The program must be able to end its execution, either normally or abnormally indicating the error.
· I/O operations: A running program may require I/O. This I/O may involve a file or an I/O device. For security and efficiency users usually cannot control I/O devices directly, operating system must be provided to do it.
· File-system manipulation: The files needs programs to read and write files. Programs also need to create and delete files by names.
· Communications: One process needs to communicate with another process. Such communication may occur in two ways:
o Communication takes place between processes that are executing on the same computer.
o Takes place between processes that are executing on different computer systems that are tied together by a computer network. Communications may be implemented via shared memory, or by the technique of message passing, in which packets of information are moved between processes by the operating system.

· Error detection: The operating system constantly needs to be aware of possible errors. Errors may occur in :
o the CPU and memory hardware-memory error or power failure.
o I/O devices-such as parity error on tape, a connection failure on network, or lack of paper in the printer.
o User program-an arithmetic overflow, an attempt to access an illegal memory location, or too great use of CPU time.

· Resource allocation: When multiple users are logged on the system, multiple jobs are running at the same time, resources must be allocated to all of them. Many different types of resources are managed by the operating system. Some are CPU cycles, main memory, and file storage may have special allocation code, and I/O devices may have general request and release code.
· Accounting: Os must keep track of which users use how many and which kinds of computer resources.
· Protection: The owners of the information stored in a multiuser computer system may want to control use of the information. When several processes are executed concurrently, one process should not interfere with the other process. Security of the system from outsiders is also important. Such security starts with each user having to authenticate himself to the system , usually by means of a password, to be allowed access to the resources.

System calls

System calls provide the interface between a process and the operating system. These calls are usually available as assembly-language instructions and they are listed in manuals for programmers. Several systems allow system calls to be available in high level languages. Several languages such as C, C++, Perl have replaced assembly language for system programming. Example, UNIX system calls may be invoked directly from a C or C++ program.

System calls can be grouped into five major categories:

1) Process Control:

A running program needs to be able to halt its execution either normally or abnormally. If a system call is made to terminate the currently running program abnormally. Either normal or abnormal , the operating system must transfer control to the command interpreter. The command interpreter then reads the next command. The command interpreter reads the next instruction.
A process or job executing one program may want to load and execute other program. An interesting question is where to return control when the loaded program terminates. Whether the existing program is lost, saved, or allowed to continue execution concurrently with the new program.
If control returns to the existing program when the new program terminates, we must save the memory image of the existing program. If both programs continue concurrently, we have created a new job or process to be multiprogrammed. System calls for this purpose is create process or submit job.
If a new job or process is created, we may need to wait for them for some time to finish their execution. We may want to wait for a certain amount of time (wait time), we may want to wait or a specific event to occur (wait event). The jobs or processes should then signal when that event has occurred (signal event).
If we create a new job or processes, we should be able to execute it. This control requires the ability to determine and reset the attributes of a job or process, including the job’s priority, its maximum allowable execution time, (get process attributes and set process attribute).
Another set of system calls is helpful in debugging a program. Many systems provide system calls to dump memory. This provision is useful for debugging. A program trace lists each instruction as it is executed; it is provided by fewer systems. The trap is usually caught by a debugger, which is a system program designed to aid the programmer in finding and correcting bugs.

2) File Management

The files must be created and deleted. Either system calls requires the name of the file and some of the attributes. Once the file is created, it must be open and used. It may also read, write and reposition (rewind or skip to the end of the file). Finally the file need to be closed.
File attributes include the file name, a file type, protection codes, accounting information and so on. The system calls for this purpose are get file attribute and set file attribute.

3) Device Management

A program running, may need additional resources to proceed. The resources may be more memory, tape drivers, access to files. If the resources are available, they can be granted and control can be returned to the user program; otherwise the program will have to wait until sufficient resource are available.
Once the device has been requested (an allocating to us), we can read, write, and reposition the device.

4) Information Maintenance

Many system calls exist simply for the purpose of transferring information between the user program and the operating system. For example, systems have a system call to return the current time and date. Other system calls may return information about the system, such as the number of current users, the version number of the operating system, the amount of free memory or disk space.
There are system calls to access these information. They are get process attributes and set process attributes.

5) Communication

There are two common models of communication. In message-passing model, information is exchanged through an interprocess communication. Before communication can take place, a connection must be opened. The name of the other communicator must be known, bit it another process on the same PU, or a process on another computer connected by networks. Each computer in the network has a host name, such as IP name. Similarly each process has a process name.
The get hosted and get processed system calls do this process. These identifiers are then passed to specific open connection and close connection system calls. The recipient process usually must give its permission for communication to take place with an accept connection call. Most processes that will be receiving connection are special purpose daemons. They execute a wait for connection call and are awakened when a connection is made. The source of the communication, known as the client, and the receiving daemon, known as server, then exchange messages by read message and write message system calls. The close connection terminates the communication.
In shared-memory model, processes may exchange information by reading and writing data in these processes and are not under the operating systems control.

SYSTEM PROGRAMS

System program provide a convenient environment for program development and execution. They can be divided into these categories:

· File Management
These programs create, delete, copy, rename, print, dump, list and generally manipulate files and directories.
· Status information
Some programs simply ask the system for the date, time, amount of available memory or disk space, number of users, or similar status information. That information is then formatted, and printed to the terminal or other output device or file.

· File modification
Several text editors may be available to create and modify the content of the files stored on disk or tape.

· Programming language support
Compilers, assemblers, and interpreters for common programming languages such a C, C++, java, Visual Basic are often provided to the user with the operating system. Some of these programs are now priced and provided separately.

· Program loading and execution
Once a program is assembled or compiled, it must be loaded into memory to be executed. Debugging systems for either higher-level languages or machine language are needed.

· Communications
These programs provide the mechanism for creating virtual connections among processes, users, and different computer systems. They allow users to send messages to one another’s screens, to browse web pages, to send e-mail messages, to log remotely, or to transfer data files from one machine to another.

SYSTEM DESIGN AND IMPLEMENTATION

1. Design Goals
The first problem in designing a system is to define the goals and specification of the system. The design of the system will be affected by the choice of hardware and type of system: batch, time shared, single user, multiuser, distributed, real time, or general purpose.

Requirement can be divided into two basic groups:
· User goals
· System goals
User desire certain properties in a system: The system should be convenient and easy to use, easy to learn, reliable, safe, and fast. Similarly a set of requirements can be defined by those people who must design, create, implement and maintain; it should be flexible, reliable, error free, and efficient.

2. Mechanisms and Policies
One important principle is the separation of policy from mechanism. Mechanism determines how to do something; policies determine what will be done. Example, the timer construct is a mechanism for ensuring CPU protection, but deciding how long the timer is to be set for a particular user is a policy decision.
Policies are likely to change across places or overtime. In worst case, each change in policy would require a change in the underlying mechanisms. A change in policy would require redefinition of only certain parameters of the system. For instance, if one computer system, a policy decision is made that I/O intensive programs should have priority over CPU intensive ones, then the opposite policy could be instituted easily on some other computer systems if the mechanism were properly separated and were policy independent.

3. Implementation
Once an operating system is designed, it must be implemented. Traditionally, OS were written in assembly language. Now they are often written in higher-level languages as C, C++.
The various operating systems not written in assembly language are:

· The Master Control Program (MCP), it was written in ALGOL.
· MULTICS, developed at MIT, was written in PL/1.
· The Primos operating system for Prime computers is written in Fortran.
· The UNIX operating system, OS/2, and Windows NT are written in C.
The advantages of writing OS in higher-level language are the code can be written faster, is more compact, and is easier to understand and debug. The OS is far easier to port to move to some other hardware if it is written in high-level language.
The disadvantage of writing OS in high-level language is the reduced speed and increased storage requirements.
OS are large, only a small amount of the code is critical to high performance, the memory manager and the CPU schedulers are probably the most critical routines.

PROCESS MANAGEMENT

A process is a program which is in execution. A batch system executes jobs, whereas a timeshared system has user programs, or tasks. The jobs and the process are used almost interchangeably. A process is more than a program code, which is sometimes known as the text section. It also includes the current activity, represented by the value of the program counter and the contents of the processor’s registers.
A program is a passive entity, such as the contents of a file stored on disk. A process is a active entity, with the program counter specifying the next instruction to execute and a set of associated resources.

Process State

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

New: The process is being created.
Running: Instructions are being executed.
Waiting: The process is waiting for some event to occur (such as an I/O completion or reception of a signal).
Ready: The process is waiting to be assigned to a processor.
Terminated: The process has finished execution.

Process Control Block

Each process is represented in the operating system by a process control block (PCB) also called as task control block. It contains many pieces of information associated with a specific process, including these:

Figure: Process control block

Process state: The state may be new, ready, running, waiting, halted and so on.
Program counter: The counter indicates the address of the next instruction to be executed.
CPU registers: The registers vary in number and type, depending upon the computer. The registers are accumulators, index register, stack pointers, and general purpose registers.
CPU scheduling information: This information includes a process priority, pointers to scheduling queues, and any other scheduling parameters.
Memory-Management information: This information includes such as information as the value of the base and limit registers, the page tables, or the segment tables, depending on the memory system used by the operating system.
Accounting information: This information includes the amount of CPU and real time used, time limits, account numbers, job or process numbers, and so on.
I/O status information: The information includes the list of I/O devices allocated to this process, a list of open files, and so on.

PROCESS SCHEDULING

Scheduling Queues:
As process enter the system, they are put into a job queue. This queue consists of all processes in system. The processes that are residing in main memory and are ready and waiting to execute are kept on a list called ready queue. This queue is generally stored as linked list. A ready-queue header contains pointers to the first and final PCBs in the list.
The OS also has other queues. When a process is allocated the CPU, it executes for a while and quits, is interrupted or waits for the occurrence of a particular event, such as the completion of an I/O request. Since the system has many process it may be busy with the I/O request of some other process. The process therefore may have to wait for the disk. The list of processes waiting for a particular I/O device is called a device queue. Each device has its own device queue.
A common representation of process scheduling is a queuing diagram. Each rectangular box represents a queue. Two types are queues are present: the ready queue and a set of device queues. The circle represent the resources that serve the queues, and the arrows indicate the flow of processes in the system.
A new process is put in the ready queue. It waits in the ready queue until it is selected for execution. Once the process is assigned to the CPU and is executing, one of the several events could occur:
· The process could issue an I/O request, and then be placed in an I/O queue.
· The process could create a new subprocess and wait for its termination.
· The process could be removed forcibly from the CPU, as a result of an interrupt, and be put back in the ready queue.

Schedulers

A process migrates between the various scheduling queues throughout its lifetime. The operating system must select, for scheduling purposes, processes from these queues in some fashion. The selection process is carried out by the appropriate scheduler. There are two types of schedulers:
Long-term schedulers or job schedulers: which selects processes from job pool and loads them into memory for execution.
Short-term scheduler or CPU scheduler: which selects among the processes that are ready to execute and allocates the CPU to one of them.
The primary difference between these two schedulers is the frequency of their execution. The short-term scheduler must select a new processes for the CPU frequently. A process may execute for only a few milliseconds therefore waiting for an I/O request. This often executes once in every 100 milliseconds.
The long-term scheduler on the other hand, executes much less frequently. There may be minutes between the creation of a new processes in the system. The long-term schedulers are need to be invoked only when the process leaves the system.
On some systems, such as time sharing systems, may introduce an additional, intermediate level of scheduling. This medium-term scheduler removes processes from memory, and thus reduces the degree of multiprogramming. At some later time, the process can be reintroduced into memory and its execution can be continued where it left off. This scheme is called swapping. The process is swapped out, and is later swapped in, by the medium-term scheduler.

Context Switch

Switching the CPU to another process requires saving the state of the old process and loading the saved state for the new process. This task is known as a context switch. The context of a process is represented in the PCB of a process; it includes the value of the PU registers, the process state and memory management information. When a context switch occurs the Kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run. Context switch is pure overhead, because the system does no useful work while switching. Its speed varies from machine to machine, depending on the memory speed, the number of registers that must be copied, and the existence of special instructions. The speed ranges from 1 to 1000 milliseconds.

OPERATIONS ON PROCESSES

The processes in the system can execute concurrently, and they must be created and deleted dynamically. Thus the operating system must provide a mechanism for process creation and termination.

Process Creation
A process may create several new processes, via create-process system call during the execution. The creating process is called a parent process, whereas the new processes are called children of that process. Each of these new processes may in turn create other processes, forming a tree structure.
A process needs certain resources such as CPU time, memory, files, I/O devices to accomplish any task. When a process creates a sub process may be able to obtain its resources directly from the operating system, or the parent may have to partition its resources among its children.
Example consider a process whose function is to display the status of a file, say F1, on the screen of the terminal. When it is created, it will get as an input from its parent process, the name of the file F1, and it will execute using that datum to obtain the desired information. It may also get the name of the output device.
When a process creates new process, two possibilities exist in terms of execution:
The parent continues to execute concurrently with its children.
The parent waits until some or all of its children have terminated.

Process Termination

A process terminates when it finishes executing its final statement and asks the operating system to delete it by using the exit system call. At that point the process may return data output to its parent process via a wait system call.
A process can cause termination of another process via an appropriate system call. When a process is newly created, the identity of the newly created process is passed to its parent.
A parent may terminate the execution of one of its children for a variety of reasons, such as:
· The child has exceeded its usage of some of the resources that it has been allocated. This requires the parent to have a mechanism to inspect the state of its children.
· The task assigned to the child is no longer required.
· The parent is exiting, and the operating system does not allow a child to continue if its parent terminates. On such systems, if a process terminates then all its children must also be terminated. This phenomenon is called as cascading termination.

COOPERATING PROCESSES

The concurrent processes executing in the operating system may either be independent processes or cooperating processes. A process is independent if it cannot affect or be affected by other processes executing in the system. The process that does not share any data with any other process is independent. A process is cooperating if it can affect or be affected by the other processes is a cooperating process.

Process cooperation is provided for several reasons:
Information sharing: Since several users may be interested in the same piece of information, we must provide an environment to allow concurrent access to these types of resources.
Computation speedup: If we want a particular task to run faster, we must break it into subtasks, each of which will be executing in parallel with the others. Such speedup can be achieved only if the computer has multiple processing elements.
Modularity: We may want to construct the system in a modular fashion, dividing the system functions into separate processes or threads.
Convenience: Even an individual user may have many tasks on which to work at one time. For instance, a user may be editing, printing, and compiling in parallel.

To illustrate the concept of cooperating processes, consider the producer-consumed problem. A producer process produces information that is consumed by a consumer process. Example, a print program produces characters that are consumed by the printer device. A compiler may produce assembly code, which is consumed by an assembler. The assembler, in turn, may produce object modules, which are consumed by the loader.
To allow producer and consumer processes to run concurrently, we must have available a buffer of items that can be filled by producer and emptied by the consumer. A producer can produce one item while the consumer is consuming another item. The producer and the customer must be synchronized so that the consumer does not try consuming an item that has not yet produced.

INTERPROCESS COMMUNICATION
IPC provides a mechanism to allow processes to communicate and to synchronize their actions without sharing the same address space. IPC is particularly useful in a distributed environment where the communicating processes may reside on different computers connected with a network. An example is the chat program used on WWW.

1. Message Passing System

The function of a message system is to allow processes to communicate with one another without the need to resort to the shared data. Communication among the user processes is accomplished through the passing of message. An IPC facility provides at least the two operations: Send(message) and receive(message).
Messages sent by7 a process can be of either fixed size or variable size. If processes P and Q want to communicate they must send messages to and receive messages from each other; a communication link must exist between them. This link can be implemented in a variety of ways. We are concerned not with physical implementation(such as shared memory, hardware, bus or network) but rather with its logical implementation. Here are several methods for logically implementing a link and the send / receive operations:

Direct or indirect communication
Symmetric or asymmetric communication
Automatic or explicit buffering
Send by copy or send by reference
Fixed-sized or variable-sized messages.

Naming

1. Direct Communication:

With direct communication, each process that wants to communicate must explicitly name the recipient or sender of the communication. In this scheme the send and the receive primitives are :

· Send(P, message) – Send a message to process P.
· Receive(Q, message) – receive a message from process Q
A communication link in this scheme has the following properties:
A link is established automatically between every pair of processes that want to communicate. The processes need to know only each other’s identity to communicate.
A link is associated with exactly two processes.
Exactly one link exists between each pair of processes.

This scheme exhibits symmetry in addressing, that is both the sender and the receiver processes must name the other to communicate. A variant of this scheme employs asymmetric in addressing. Only the sender names the recipient; the recipient is not required to name the sender. In this scheme the send and receive primitives are defined as follows:
Send (P, message) – send a message to process P
Receive(id, message) – receive a message from any process, the variable id is set to the name of the process with which communication has taken place.

2. Indirect Communication:

With indirect communication, the messages are sent to and received from mailboxes, or ports. A mailbox can be viewed abstractly as an object into which message can be placed by processes and from which messages can be removed. Each mailbox has a unique identification. In this scheme a process can communicate with some other process via a number of different mailboxes. Two processes can communicate only if they share a mailbox. The send and receive primitives are defined as follows:

Send (A, mailbox) – send a message to mailbox A
Receive(A, message) – receive a message from mailbox A

In this scheme, a communication link has the following property:
A link may be associated with more than two processes.
A number of different links may exist between each pair of communicating processes, with each link corresponding to one mailbox.

Mailbox can be owned by either by a process or by the operating system. If the mailbox is owned by a process, then each owner is distinguished (who can receive the message) and the user( who send the messages). Since each mailbox has a unique owner, there can be no confusion about who should receive the message sent to the mailbox. When a process that owns a mailbox terminates, the mailbox disappears. Any process that subsequently sends a message to this mailbox must be notified that the mailbox no longer exists.
On the other hand, a mailbox owned by the operating system is independent and is not attached to any particular process. The operating system then must provide a mechanism that allows a process to do the following:
Create a new mailbox
Send and receive messages through the mailbox
Delete a mailbox.

3. Synchronization:

Communication between processes takes place by calls to send and receive primitives. Message passing may be either blocking or non blocking also known as synchronous and asynchronous.
Blocking send: The sending process is blocked until the message is received by the receiving process or by the mailbox.
Nonblocking send: The sending process sends the message and resumes operation.
Blocking receive: The receiver blocks until a message is available.
Nonblocking receive: The receiver retrieves either a valid message or a null.

4. Buffering:

Whether the communication is direct or indirect, message exchanged by communicating processes reside in a temporary queue.

Zero capacity: The queue has maximum length 0, thus the link cannot have any message waiting in it. In this case, the sender must block until the recipient receives the message.
Bounded capacity: The queue has finite length n; thus at most n message can reside in it. If the queue is not full when a new message is sent, the latter is placed in the queue, and the sender can continue execution without waiting. The link has finite capacity. If the link is full, the sender must block until space is available in the queue.
Unbounded capacity: The queue has potentially infinite length, thus any number of messages can wait in it. The sender never blocks.







SCHEDULING ALGORITHMS

First Come First Served Scheduling:

The simplest CPU scheduling algorithm is the first come first served (FCFS) scheduling algorithm. With this scheme the process that requests the CPU first is allocated the CPU first. This is managed by the FIFO queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue.
The average waiting time under the FCFS policy, is often quite long. Consider the following set of processes that arrive at time 0, with the length of the CPU-burst time given in milliseconds:
Process Burst time
P1 24
P2 3
P3 3

If the processes arrive in the order P1, P2, P3 and are served in the FCFS order, we get the result shown in the following Gantt chart:

The waiting time is 0 milliseconds for process P1, 24 milliseconds for process p2, and 27 millisecond for process P3. Thus the average waiting time is (0+24+27)/3=17 milliseconds. If the processes arrive in the order P2, P3,P1 the results will be as shown in the following Gantt chart:

The average waiting time is now (6+0+3)/3=3 milliseconds. Thus the average waiting time under FCFS policy is generally not minimal and may vary if the process CPU-burst times vary greatly.
The FCFS scheduling algorithm is non preemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU either by termination or by requesting I/O.

2. Shortest-Job First Scheduling:

A different approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm. This algorithm associates with each process the length of the latter’s next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have same length next CPU burst, FCFS scheduling is used to break the tie. Consider the following set of processes, with the length of the CPU burst time given in milliseconds:



Process Burst time
P1 6
P2 8
P3 7
P4 3

Using SJF scheduling, we would schedule the process according to the following Gantt chart:

The waiting time is 3 milliseconds for process P1, 16 milliseconds for process P2, 9 milliseconds for process P3, and 0 milliseconds for process P4. Thus the average waiting time is (3+16+9+0)/4=7 milliseconds. If FCFS is used the average waiting time is 10.25 milliseconds.
The real difficulty with the SJF algorithm is knowing the length of the next CPU request. For long term or job scheduling in a batch system, the length of the process time limit is specified by the user when he submits the job. There is no way to know the length of the next CPU burst in short term or CPU scheduling. We may not know the length but can predict the length of the CPU burst. We expect that the next CPU burst will be similar in length to the previous ones.
The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts.
Let tn be the length of the nth CPU burst
Let Tn+1 be our predicted value for the next CPU burst.
Then for a, o£a£1, define

Tn+1 = a tn + (1 - a) Tn
This formula defines an exponential average.
The value of tn contains our most recent information;
Tn stores the past history
The parameter a controls the relative weight of recent and past history in our prediction.
If a=0 then Tn+1=Tn, recent history has no effect
If a=1 then Tn+1 = tn only the most recent CPU burst matters
If a=1/2 recent and past history are equally weighted.

SJF is preemptive or non preemptive. The choice arises when a new process arrives at the ready queue while previous process is executing. The new process may have a shorter next CPU burst than what is left of the currently executing process, whereas non preemptive SJF algorithm will preempt the currently running process to finish its CPU burst.
Consider an example, with four processes, with the length of the CPU burst time given in milliseconds:


Process Arrival time Burst time
P1 0 8
P2 1 4
P3 2 9
P4 3 5

If the processes arrive at the ready queue at the times as shown and need the indicated burst times, then the resulting preemptive SJF schedule is as depicted in the following Gantt chart:

Process P1 is started at time 0, since it is the only process in the queue. Process P2 arrives at time 1. The remaining time for process P1 (7 milliseconds) is larger than the time required by process P2 (4 milliseconds), so process P1 is preempted and process P2 is scheduled. The average waiting time for this example is 6.5 milliseconds.





















3. Priority Scheduling:

The SJF is a special case of the general priority-scheduling algorithm. A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal priority processes are scheduled in FCFS order.
As an example, consider the following set of processes, assumed to have arrived at time 0, in the order P1, P2, P3,P4,P5, with the length of the CPU burst time given in milliseconds:

Process Burst time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

The average waiting time is 8.2 milliseconds. Priorities can be defined either internally or externally. Internally defined priorities use some measurable quantity to compute the priority of a process. For example, time limits, memory requirements, the number of open files etc. External priorities are set by criteria that are external to the operating system, such as importance of the process, the type and amount of funds being paid for computer use, the department sponsoring the work, and other often political factors.
Priority scheduling can be either preemptive or non-preemptive. When process arrives at the ready queue, its priority is compared with the priority of the currently running process. A preemptive priority-scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process. A non preemptive priority scheduling algorithm will simply put the new process at the head of the ready queue.
A major problem with priority-scheduling algorithms is indefinite blocking or starvation. A process that is ready to run but lacking the CPU is considered blocked – waiting for the CPU. A priority-scheduling algorithm can leave some low-priority processes waiting indefinitely for the CPU. Generally one of the two things will happen. Either the process will eventually be run, or the computer system will eventually crash and lose all unfinished low-priority processes.
A solution to the problem of indefinite blockage of low-priority processes is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.



4. Round-Robin Scheduling:

The round-robin (RR) scheduling algorithm is designed especially for time-sharing systems. It is similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of time, called a time quantum is defined. The time quantum is generally from 10 to 100 milliseconds. The ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
To implement RR scheduling, we keep the ready queue as a FIFO queue of processes. New processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.
One of the two things will then happen. The process may have a CPU burst of less than 1 time quantum. In this case the process itself will release the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue. Otherwise, if the CPU burst of the currently running process is longer than 1 time quantum, the timer will go off and will cause an interrupt to the operating system. A context switch will be executed, and the process will be put at the tail of the ready queue. The CPU scheduler will then select the next process in the ready queue.
Consider the following set of processes that arrive at time 0, with the length of the CPU burst time given in milliseconds:
Process Burst Time
P1 24
P2 3
P3 3If the time quantum is 4 milliseconds, then process P1 gets the first 4 milliseconds. Since it requires another 20 milliseconds, it is preempted after the first time quantum, and the CPU is given to the next process in the queue, process P2. Since process p2 does not need 4 milliseconds, it quits before its time quantum expires. The CPU is then given to the next process, process P3. Once each process has received 1 time quantum, the CPU is returned to process P1 for an additional time quantum