Operating System

Unit-1 INTRODUCTION

Operating System
Definition:
An operating system act as an intermediary between the user of a computer and
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. An
operating system is software that manages the computer hardware.
(Or)

An Operating system is a program that controls the execution of application programs

and acts as an interface between the user of a computer and the computer hardware.

Operating System examples:

Desktop Embedded devices

Microsoft Windows Android OS

MAC OS X (BSD) iOS

LINUX Symbian

Computer System Structure

Computer system can be divided into four components
 Hardware – provides basic computing resources CPU, memory, I/O devices
 Operating System-Controls and coordinates use of hardware among various
applications and users
 Application programs – define the ways in which the system resources are used to
solve the computing problems of the users -Word processors, compilers, web
browsers, database systems, video games
 Users - People, machines, other computers
Four Components of a Computer System

1
 Operating System

Goals of Operating System

[Link]: An OS makes a computer more convenient to use.
[Link]: An OS allows the computer system resources to be used in an efficient
manner.
[Link] to Evolve: An OS should be constructed in such a way as to permit the
effective development, testing and introduction of new system functions without at the
same time interfering with service.
4. Security: To protect system resources, such as memory and files, from
unauthorized access, modification, or corruption

Operating System as user view

Every general purpose computer consists of the hardware, operating system, system
programs, and application programs. The hardware consists of memory, CPU, ALU,
I/O devices, peripheral device and storage device. System program consists of
compilers, loaders, editors, OS etc. The application program consists of business
program, database program.
Every computer must have an operating system to run other programs. The operating
system and coordinates the use of the hardware among the various system programs
and application program for a various users. It simply provides an environment within
which other programs can do useful work.
The operating system is a set of special programs that run on a computer system that
allow it to work properly. It performs basic tasks such as recognizing input from the

2
 Operating System

keyboard, keeping track of files and directories on the disk, sending output to the
display screen and controlling a peripheral devices.

Operating System as System View

 The system view emphasizes the OS's role as a resource manager and control
program.

 The OS acts as a resource allocator, managing:

 Resource Allocator - To allocate resources (software and hardware) of the

computer system and manage them efficiently.

CPU time: Scheduling processes to ensure efficient CPU utilization.

Memory: Allocating and deallocating memory to programs.

Storage: Managing file systems and storage devices.

I/O devices: Controlling input and output operations.

 Control Program
Controls execution of user programs and operation of I/O devices.
 Kernel
At the core of the system view is the kernel, which:

 Manages core OS functions.

 Operates in kernel mode, with privileged access to hardware.
 Handles system calls, which are requests from user-level programs for OS
services.

Functions of Operating System

Operating systems perform the following important functions:

1. Processor Management: It means assigning processor to different tasks which has

to be performed by the computer system.
2. Memory Management: It means allocation of main memory and secondary
storage areas to the system programmes, as well as user programmes and data.
3. Input and Output Management: It means co-ordination and assignment of the
different output and input devices while one or more programmes are being
executed.

3
 Operating System

4. File System Management: Operating system is also responsible for maintenance

of a file system, in which the users are allowed to create, delete and move files.

User and Operating System Interface – CLI

A command interpreter is the part of a computer operating system that understands
and executes commands that are entered interactively by a human being or from a
program. In some operating systems, the command interpreter is called the shell.

A command interpreter is a program which reads the instructions given by the user. It
then translates these instructions into the context of the operating system followed by
the execution. Command interpreter is also known as shell.

User Operating System Interface – GUI

 User-friendly desktop metaphor interface
 Usually mouse, keyboard, and monitor
 Icons represent files, programs, actions, etc
 Various mouse buttons over objects in the interface cause various actions (provide
information, options, execute function, open directory (known as a folder)

History of Operating System

Operating systems have been evolving through the years.

Generation Year Electronic devices used Types of OS and devices

First 1945 – 55 Vacuum tubes Plug boards

Second 1955 – 1965 Transistors Batch system
Third 1965 – 1980 Integrated Circuit (IC) Multiprogramming
Fourth since 1980 Large scale integration PC

Assembler:- Input to an assembler is an assembly language program. Output is an

object program plus information that enables the loader to prepare the object program
for execution.

Loader:- A loader is a routine that loads an object program and prepares it for
execution. There are various loading schemes: absolute, relocating and direct linking.
In general, the loader must load, relocate, and link the object program

Compilers:- A compiler is a program that accepts a source program in a high-level

language and produces a corresponding object program.

Types of Operating System

4
 Operating System

1. Batch System

Some computer systems only did one thing at a time. They had a list of the computer
system may be dedicated to a single program until its completion, or they may be
dynamically reassigned among a collection of active programs in different stages of
execution.

Batch operating system is one where programs and data are collected together in a
batch before processing starts. A job is predefined sequence of commands, programs
and data that are combined in to a single unit called job.

Batch processing is a technique in which Operating System collects one programs and
data together in a batch before processing starts. Operating system does the following
activities related to batch processing.

 OS defines a job which has predefined sequence of commands, programs

 and data as a single unit.
 OS keeps a number a jobs in memory and executes them without any
 manual information.
 Jobs are processed in the order of submission i.e first come first served
 fashion.
 When job completes its execution, its memory is released and the output
 for the job gets copied into an output spool for later printing or
 processing.

Advantages

5
 Operating System

 Batch processing takes much of the work of the operator to the computer.
 Increased performance as a new job get started as soon as the previous
job finished without any manual intervention.

Disadvantages

 Difficult to debug program.

 A job could enter an infinite loop.
 Due to lack of protection scheme, one batch job can affect pending jobs.

2. Multi-programming OS

When two or more programs are residing in memory at the same time, then sharing
the processor is referred to the multiprogramming. Multiprogramming assumes a
single shared processor. Multiprogramming increases CPU utilization by organizing
jobs so that the CPU always has one to execute.

The operating system keeps several jobs in memory at a time. This set of jobs is a
subset of the jobs kept in the job pool. The operating system picks and begins to
execute one of the job in the memory.

Multi-programmed systems provide an environment in which the various system

resources are utilized effectively, but they do not provide for user interaction with the
computer system. Jobs entering into the system are kept into the memory. Operating
system picks the job and begins to execute one of the job in the memory.

Having several programs in memory at the same time requires some form of memory
management. Multiprogramming operating system monitors the state of all active
programs and system resources. This ensures that the CPU is never idle unless there
are no jobs.

Following figure shows the memory layout for a multiprogramming system.

6
 Operating System

Operating system does the following activities related to multiprogramming.

 The operating system keeps several jobs in memory at a time.

 This set of jobs is a subset of the jobs kept in the job pool.
 The operating system picks and begins to execute one of the job in the
memory.
 Multiprogramming operating system monitors the state of all active
programs and system resources using memory management programs to
ensures that the CPU is never idle unless there are no jobs.

Advantages

 High and efficient CPU utilization.

 User feels that many programs are allotted CPU almost simultaneously.

Disadvantages

 CPU scheduling is required.

 To accommodate many jobs in memory, memory management is
required.

3. Time sharing or Multitasking system

Time sharing system is a logical extension of multiprogramming system, allow many

users to share the computer simultaneously by switching the CPU among the users.
The CPU is switched so frequently such that user can interact with each program
while it is running.

In time sharing system, the CPU will be allocated to each user for a small, fixed
period of time (Generally the timeslots are defined by the OS.) and it is switched from
one job to another either when there a natural break or when the allocated timeslot is

7
 Operating System

over. Time shared systems are much more complex than Multi-Programming
Operating System. However multiprogramming and time sharing are the central
themes of modern OS.

 The user gives instructions to the operating system or to a program

 directly, and receives an immediate response.
 Operating System handles multitasking in the way that it can handle
 multiple operations / executes multiple programs at a time.
 Multitasking Operating Systems are also known as Time-sharing systems.
 These Operating Systems were developed to provide interactive use of a
 computer system at a reasonable cost.
 A time-shared operating system uses concept of CPU scheduling and
 multiprogramming to provide each user with a small portion of a timeshared CPU.
 Each user has at least one separate program in memory

 A program that is loaded into memory and is executing is commonly

 referred to as a process.
 When a process executes, it typically executes for only a very short time
 before it either finishes or needs to perform I/O.
 Since interactive I/O typically runs at people speeds, it may take a long
 time to completed. During this time a CPU can be utilized by another
 process.
 Operating system allows the users to share the computer simultaneously.
 Since 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 CPU rapidly from one user/program to the next,
 each user is given the impression that he/she has his/her own CPU,
 whereas actually one CPU is being shared among many users.

8
 Operating System

4. Real-time Operating Systems (RTOS)

RTOS is used when rigid time requirements have been placed on the operation of a
processor or flow of data. This system is often used as a control device in dedicated
applications. RTOS has well defined, fixed time constraints. Processing must be done
within the defined constraints otherwise the system fails.

RTOS are of two types:

Hard real-time systems: They are highly stringent systems which guarantees that
critical tasks be completed on-time. Here, the time constraint dictate the facilities
available in the system.

Soft real-time systems: These are less stringent. Here, critical tasks get priority over
other tasks

and retain that priority till they complete. Thus, the prime objective of this system is to
provide quick event response.

Advantages:

 Systems that control scientific experiments, medical imaging systems , industrial

control systems, home appliance controllers , weapon systems are real-time
systems.

Disadvantages:

 Hard real-time systems are highly stringent and fails if they are unable to respond
within the defined time constraint.
 Soft real-time systems are less restrictive and do not support deadline scheduling.

5. Distributed System

Distributes computation among several physical processors. The processors do not

share memory or a clock. Instead, each processor has its own local memory. They
communicate with each other through various communication lines.

Distributed environment refers to multiple independent CPUs or processors in a

computer system. Operating system does the following activities related to distributed
environment.

 OS Distributes computation logics among several physical processors.

 The processors do not share memory or a clock.
 Instead, each processor has its own local memory.

9
 Operating System

 OS manages the communications between the processors. They communicate with

each other through various communication lines.

Operating System Components

Modern operating systems share the goal of supporting the system components.

The system components are:

1. Process Management
2. Main Memory Management
3. File Management
4. Secondary Storage Management
5. I/O System Management
6. Networking
7. Protection System
8. Command Interpreter System

1. Process Management

The operating system manages many kinds of activities ranging from user programs to
system programs like printer spooler, name servers, file server etc. Each of these
activities is encapsulated in a process. A process includes the complete execution
context (code, data, PC, registers, OS resources in use etc.).

It is important to note that a process is not a program. A process is only ONE instant
of a program in execution. There are many processes can be running the same
program.

The five major activities of an operating system in regard to process management are

 Creation and deletion of user and system processes.

 Suspension and resumption of processes.
 A mechanism for process synchronization.
 A mechanism for process communication.
 A mechanism for deadlock handling.

2. Main-Memory Management

Primary-Memory or Main-Memory is a large array of words or bytes. Each word or

byte has its own address. Main-memory provides storage that can be access directly
by the CPU. That is to say for a program to be executed, it must in the main memory.

10
 Operating System

The major activities of an operating in regard to memory-management are:

 Keep track of which part of memory are currently being used and by whom.
 Decide which process is loaded into memory when memory space becomes
available.
 Allocate and deallocate memory space as needed.

3. File Management

A file is a collected of related information defined by its creator. Computer can store
files on the disk (secondary storage), which provide long term storage. Some
examples of storage media are magnetic tape, magnetic disk and optical disk. Each of
these media has its own properties like speed, capacity, data transfer rate and access
methods.

File systems normally organized into directories to ease their use. These directories
may contain files and other directions.

The five main major activities of an operating system in regard to file management are

1. The creation and deletion of files.

2. The creation and deletion of directions.
3. The support of primitives for manipulating files and directions.
4. The mapping of files onto secondary storage.
5. The backup of files on stable storage media.

4. I/O System Management

I/O subsystem hides the peculiarities of specific hardware devices from the user. Only
the device driver knows the peculiarities of the specific device to which it is assigned.

5. Secondary-Storage Management

Generally speaking, systems have several levels of storage, including primary storage,
secondary storage and cache storage. Instructions and data must be placed in primary
storage or cache to be referenced by a running program. Because main memory is too
small to accommodate all data and programs, and its data are lost when power is lost,
the computer system must provide secondary storage to back up main memory.

Secondary storage consists of tapes, disks, and other media designed to hold
information that will eventually be accessed in primary storage (primary, secondary,
cache) is ordinarily divided into bytes or words consisting of a fixed number of bytes.
Each location in storage has an address; the set of all addresses available to a program
is called an address space.

11
 Operating System

The three major activities of an operating system in regard to secondary storage

management are:

1. Managing the free space available on the secondary-storage device.

2. Allocation of storage space when new files have to be written.
3. Scheduling the requests for memory access.

6. Networking

A distributed system is a collection of processors that do not share memory, peripheral

devices, or a clock. The processors communicate with one another through
communication lines called network. The communication-network design must
consider routing and connection strategies, and the problems of contention and
security.

7. Protection System

If computer systems has multiple users and allows the concurrent execution of
multiple processes, then the various processes must be protected from one another's
activities. Protection refers to mechanism for controlling the access of programs,
processes, or users to the resources defined by computer systems.

8. Command Interpreter System

A command interpreter is an interface of the operating system with the user. The user
gives commands with are executed by operating system (usually by turning them into
system calls). The main function of a command interpreter is to get and execute the
next user specified command.

Command-Interpreter is usually not part of the kernel, since multiple command

interpreters (shell, in UNIX terminology) may be support by an operating system, and
they do not really need to run in kernel mode. There are two main advantages to
separating the command interpreter from the kernel.

1. If we want to change the way the command interpreter looks, i.e., I want to
change the interface of command interpreter, I am able to do that if the
command interpreter is separate from the kernel. I cannot change the code of
the kernel so I cannot modify the interface.

2. If the command interpreter is a part of the kernel it is possible for a malicious

process to gain access to certain part of the kernel that it showed not have to
avoid this ugly scenario it is advantageous to have the command interpreter
separate from kernel.

12
 Operating System

Operating System Services

An operating system provides services to programs and to the users of those programs.

The common service provided by the operating system is listed below.

1. Program execution
2. I/O operation
3. File system manipulation
4. Communications
5. Error detection
6. Resource Allocation
7. Accounting
8. Protection

1. Program execution: Operating system loads a program into memory and executes
the program. The program must be able to end its execution, either normally or
abnormally.

2. I/O Operation: I/O means any file or any specific I/O device. Program may require
any I/O device while running. So operating system must provide the required I/O.

3. File system manipulation: Program needs to read a file or write a file. The
operating system gives the permission to the program for operation on file.

4. Communication: Data transfer between two processes is required for some time.
The both processes are on the one computer or on different computer but connected
through computer network. Communication may be implemented by two methods:

a. Shared memory
b. Message passing.

5. Error detection: error may occur in CPU, in I/O devices or in the memory
hardware. The operating system constantly needs to be aware of possible errors. It
should take the appropriate action to ensure correct and consistent computing.

6. Resource Allocation: If there is more than one user or jobs running at the same
time, then resources must be allocated to each of them. Operating system manages
different types of resources require special allocation code, i.e. main memory, CPU
cycles and file storage.

13
 Operating System

There are some resources which require only general request and release code. For
allocating CPU, CPU scheduling algorithms are used for better utilization of CPU.
CPU scheduling algorithms are used for better utilization of CPU. CPU scheduling
routines consider the speed of the CPU, number of available registers and other
required factors.

7. Accounting: Logs of each user must be kept. It is also necessary to keep record of
which user how much and what kinds of computer resources. This log is used for
accounting purposes. The accounting data may be used for statistics or for the billing.
It also used to improve system efficiency.

8. Protection: Protection involves ensuring that all access to system resources is

controlled. Security starts with each user having to authenticate to the system, usually
by means of a password. External I/O devices must be also protected from invalid
access attempts.

In protection, all the access to the resources is controlled. In multiprocess

environment, it is possible that, one process to interface with the other, or with the
operating system, so protection is required.

System Calls

The system call provides an interface to the operating system services. Application
developers often do not have direct access to the system calls, but can access them
through an application programming interface (API). The functions that are included
in the API invoke the actual system calls. By using the API, certain benefits can be
gained:

14
 Operating System

 Portability: as long a system supports an API, any program using that API can
compile and run.
 Ease of Use: using the API can be significantly easier then using the actual system
call.

Types of System Calls

Linux System Calls
Task Commands

Process Control fork (); exit(); wait();

File Manipulation open(); read(); write();

Device Manipulation ioctl(); read(); write();

Information Maintenance getpid(); alarm(); sleep();

Communication pipe(); shmget(); mmap();

Protection chmod(); umask(); chown();

1. Process Control: A running program needs to be able to stop execution either

normally or abnormally. When execution is stopped abnormally, often a dump of
memory is taken and can be examined with a debugger.

2. File Management: Some common system calls are create, delete, read, write,
reposition, or close. Also, there is a need to determine the file attributes – get and set
file attribute. Many times the OS provides an API to make these system calls.

3. Device Management: Process usually require several resources to execute, if these

resources are available, they will be granted and control returned to the user process.
These resources are also thought of as devices. Some are physical, such as a video
card, and others are abstract, such as a file. User programs request the device, and
when finished they release the device. Similar to files, we can read, write, and
reposition the device.

4. Information Management: Some system calls exist purely for transferring

information between the user program and the operating system. An example of this is
time, or date. The OS also keeps information about all its processes and provides
system calls to report this information.

15
 Operating System

5. Communication: There are two models of inter-process communication, the

message-passing model and the shared memory model.

 Message-passing uses a common mailbox to pass messages between processes.

 Shared memory use certain system calls to create and gain access to create and
gain access to regions of memory owned by other processes. The two processes
exchange information by reading and writing in the shared data.

Process Management
Concept of Process
A process is sequential program in execution. A process defines the fundamental unit
of computation for the computer.

Process is a dynamic entity that is a program in execution. A process is a sequence of

information executions. Process exists in a limited span of time. Two or more
processes could be executing the same program, each using their own data and
resources.

Structure of a process

A process is a program in execution. A process is more than the program code, which
is sometimes known as the text section.

It also includes the current activity, as represented by the value of the program counter
and the contents of the processor's registers.

A process generally also includes the process stack, which contains temporary data
(such as function parameters, return addresses, and local variables), and a data
section, which contains global variables.

A process may also include a heap, which is memory that is dynamically allocated
during process run time.

16
 Operating System

Process State
When process executes, it changes state. Process state is defined as the current activity
of the process.

Process state contains five states. Each process is in one of the states.

The states are listed below.

1. New
2. Ready
3. Running
4. Waiting
5. Terminated (exist)
1. New: A process that just been created.
2. Ready: Ready processes are waiting to have the processor allocated to them
by the operating system so that they can run.
3. Running: The process that is currently being executed. A running process
possesses all the resources needed for its execution, including the processor.
4. Waiting: A process that cannot execute until some event occurs such as the
completion of an I/O operation. The running process may become suspended by
invoking an I/O module.
5. Terminated: A process that has been released from the pool of executable

17
 Operating System

processes by the operating system.

Whenever processes changes state, the operating system reacts by placing the process
PCB in the list that corresponds to its new state. Only one process can be running on
any processor at any instant and many processes may be ready and waiting state.

Process Control Block (PCB)

Each process contains the process control block (PCB). PCB is the data structure used
by the operating system. Operating system groups all information that needs about
particular process.

18
 Operating System

1. Pointer: Pointer points to another process control block. Pointer is used for
maintaining the scheduling list.

2. Process State: Process state may be new, ready, running, waiting and so on.

3. Program Counter: It indicates the address of the next instruction to be executed

for this process.

4. Event information: For a process in the blocked state this field contains
information concerning the event for which the process is waiting.

5. CPU register: It indicates general purpose register, stack pointers, index registers
and accumulator’s etc. number of register and type of register totally depends upon the
computer architecture.

6. Memory Management Information: This information may include the value of

base and limit register. This information is useful for deallocating the memory when
the process terminates.

7. Accounting Information: This information includes the amount of CPU and real
time used, time limits, job or process numbers, account numbers etc. Process control
block also includes the information about CPU scheduling, I/O resource management,
file management information, priority and so on. The PCB simply serves as the
repository for any information that may vary from process to process.

Process Management / Process Scheduling

The process scheduling is the activity of the process manager that handles the removal
of the running process from the CPU and the selection of another process on the basis
of a particular strategy.

Process scheduling is an essential part of a Multiprogramming operating system. Such

operating systems allow more than one process to be loaded into the executable
memory at a time and loaded process shares the CPU using time multiplexing.

The scheduling mechanism is the part of the process manager that handles the removal
of the running process from the CPU and the selection of another process on the basis
of particular strategy.

19
 Operating System

Scheduling Queues

When the process enters into the system, they are put into a job queue. This queue
consists of all processes in the system. The operating system also has other queues.

The processes that are residing in main memory and are ready and waiting to execute
are kept on a list called the ready queue

Device queue is a queue for which a list of processes waiting for a particular I/O
device. Each device has its own device queue.

Fig. shows the queuing diagram of process scheduling. In the fig , queue is
represented by rectangular box.

The circles represent the resources that serve the queues.

The arrows indicate the flow of processes in the system.

Queues are of two types: ready queue and set of device queues. A newly arrived
process is put in the ready queue. Processes are waiting in ready queue for allocating
the CPU. Once the CPU is assigned to the process, then process will execute. While
executing the process, one of the several events could occur.

1. The process could issue an I/O request and then place in an I/O queue.
2. The process could create new sub process and waits for its termination.

20
 Operating System

3. The process could be removed forcibly from the CPU, as a result of interrupt
and put back in the ready queue.

Schedules

Schedulers are of three types.

1. Long Term Scheduler or Job Scheduler

2. Short Term Scheduler or CPU Scheduler
3. Medium Term Scheduler

1. Long Term Scheduler

It is also called job scheduler. Long term scheduler determines which programs are
admitted to the system for processing. Job scheduler selects processes from the queue
and loads them into memory for execution. Process loads into the memory for CPU
scheduler. The primary objective of the job scheduler is to provide a balanced mix of
jobs, such as I/O bound and processor bound.

It also controls the degree of multiprogramming. If the degree of multiprogramming is

stable, then the average rate of process creation must be equal to the average departure
rate of processes leaving the system. On same systems, the long term scheduler may
be absent or minimal.

Timesharing operating systems have no long term scheduler. When process changes
the state from new to ready, then there is a long term scheduler.

2. Short Term Scheduler

It is also called CPU scheduler. Main objective is increasing system performance in

accordance with the chosen set of criteria. It is the change of ready state to running
state of the process. CPU scheduler selects from among the processes that are ready to
execute and allocates the CPU to one of them. Short term scheduler also known as
dispatcher, execute most frequently and makes the fine grained decision of which
process to execute next. Short term scheduler is faster than long tern scheduler.

21
 Operating System

3. Medium Term Scheduler

Medium term scheduling is part of the swapping function. It removes the processes
from the memory. It reduces the degree of multiprogramming. The medium term
scheduler is in charge of handling the swapped out-processes.

Fig: Queueing diagram with medium term scheduler

CPU Scheduling

CPU scheduling is a process which allows one process to use the CPU while the
execution of another process is on hold (in waiting state) due to unavailability of any
resource like I/O etc, thereby making full use of CPU. The aim of CPU scheduling is
to make the system efficient, fast and fair.

CPU Scheduler

Whenever the CPU becomes idle, the operating system must select one of the
processes in the ready queue to be executed. The selection process is carried out by
the short-term scheduler (or CPU scheduler). The scheduler selects a process from the
processes in memory that are ready to execute and allocates the CPU to that process.

CPU-scheduling decisions may take place under the following four circumstances:

1. When a process switches from the running state to the waiting state (for example, as
the result of an I/O request or an invocation of wait for the termination of one of the
child processes)

22
 Operating System

2. When a process switches from the running state to the ready state (example, when
an interrupt occurs)

3. When a process switches from the waiting state to the ready state (for example, at
completion of I/O)

4. When a process terminates.

For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one
exists in the ready queue) must be selected for execution. There is a choice, however,
for situations 2 and 3.

When scheduling takes place only under circumstances 1 and 4, we say that the
scheduling scheme is non pre-emptive or cooperative; otherwise, it is pre-emptive.
Under non pre-emptive scheduling, once the CPU has been allocated to a process, the
process keeps the CPU until it releases the CPU either by terminating or by switching
to the waiting state.

1. Pre-emptive Scheduling

In preemptive scheduling, the tasks are assigned based on their priorities. For
example, a low-priority task is running. After some time, a high-priority task comes
into the system for execution, and then since the new task is of high priority, the
operating system will keep the low priority task on hold and allocate the CPU to the
high priority task. As the high-priority task will finish its execution, the CPU will be
reallocated to the low-priority task. This is known as preemptive scheduling.

Preemptive scheduling also occurs when a process switches from the running state to
the ready state and switches from the waiting state to the ready state.

2. Non-Preemptive Scheduling

In non-preemptive scheduling, once the CPU has been allocated to a process, the
process keeps the CPU until it releases the CPU either by terminating or by switching
to the waiting state. New processes are executed only after the current process has
completed its execution. The process holds the resources of the CPU (CPU time) till
its state changes to terminated or is pushed to the process waiting state. If a process is
currently being executed by the CPU, it is not interrupted till it is completed.

23
 Operating System

Once the process has completed its execution, the processer picks the next process
from the ready queue (the queue in which all processes that are ready for execution are
stored).

Scheduling Criteria

Different CPU scheduling algorithms have different properties, and the choice of a
particular algorithm may favour one class of processes over another. In choosing
which algorithm to use in a particular situation, we must consider the properties of the
various algorithms.

Many criteria have been suggested for comparing CPU scheduling algorithms. Which
characteristics are used for comparison can make a substantial difference in which
algorithm is judged to be best. The criteria include the following:

1. CPU utilization.

We want to keep the CPU as busy as possible. Conceptually, CPU utilization can
range from 0 to 100 percent. In a real system, it should range from 40 percent (for a
lightly loaded system) to 90 percent (for a heavily used system).

2. Throughput.

If the CPU is busy executing processes, then work is being done. One measure of
work is the number of processes that are completed per time unit, called throughput.
For long processes, this rate may be one process per hour; for short transactions, it
may be 10 processes per second.

3. Turnaround time.

From the point of view of a particular process, the important criterion is how long it
takes to execute that process. The interval from the time of submission of a process to
the time of completion is the turnaround time. Turnaround time is the sum of the
periods spent waiting to get into memory, waiting in the ready queue, executing on the
CPU, and doing I/O.

4. Waiting time.

24
 Operating System

The CPU scheduling algorithm does not affect the amount of time during which a
process executes or does I/O; it affects only the amount of time that a process spends
waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the
ready queue.

5. Response time.

In an interactive system, turnaround time may not be the best criterion. Often, a
process can produce some output fairly early and can continue computing new results
while previous results are being output to the user. Thus, another measure is the time
from the submission of a request until the first response is produced. This measure,
called response time, is the time it takes to start responding, not the time it takes to
output the response. The turnaround time is generally limited by the speed of the
output device.

It is desirable to maximize CPU utilization and throughput and to minimize

turnaround time, waiting time, and response time.

Scheduling Algorithms

1. First-Come, First-Served Scheduling (FCFS)

2. Shortest-Job-First Scheduling
3. Priority Scheduling
4. Round-Robin Scheduling

Multiple Processors Scheduling in Operating System

A multi-processor is a system that has more than one processor but shares the same
memory, bus, and input/output devices. The bus connects the processor to the RAM,
to the I/O devices, and to all the other components of the computer.

The system is a tightly coupled system. This type of system works even if a processor
goes down. The rest of the system keeps working. In multi-processor scheduling, more
than one processors(CPUs) share the load to handle the execution of processes
smoothly.

25
 Operating System

The scheduling process of a multi-processor is more complex than that of a single

processor system because of the following reasons.

 Load balancing is a problem since more than one processors are present.
 Processes executing simultaneously may require access to shared data.
 Cache affinity should be considered in scheduling.

Approaches to Multiple processor scheduling:

There are two approaches: Symmetric Multiprocessing and Asymmetric

Multiprocessing.

 Symmetric Multiprocessing: In Symmetric Multiprocessing, all processors are

self-
scheduling.
 Asymmetric Multiprocessing: In Asymmetric Multiprocessing, scheduling
decisions and I\O processes are handled by a single processor known as the Master
Server.

Thread Scheduling

The scheduling of thread involves two boundary scheduling:

 Scheduling of Kernel-Level Threads by the system scheduler.

 Scheduling of User-Level Threads or ULT to Kernel-Level Threads or KLT by
using Lightweight process or LWP.

Lightweight process (LWP):

The Lightweight process is threads that act as an interface for the User-Level Threads
to access the physical CPU resources.

The number of the lightweight processes depends on the type of application, for an I\O
bound application the number of LWP depends on the user level threads, and for CPU
bound application each thread is connected to a separate kernel-level thread.

26
 Operating System

In real-time, the first boundary of thread scheduling is beyond specifying the

scheduling policy and the priority, therefore, it requires two controls to be specified
for the User level threads:

 Contention scope – Control scope defines the extent to which contention takes
place.
 Contention refers to the competition among the ULTs to access the KLTs.
 Contention scope can be further classified into Process Contention Scope (PCS)
and System Contention Scope (SCS).
 Process Contention Scope: Process Contention Scope is when the contention takes
place in the same process.
 System contention scope (SCS): System Contention Scope refers to the contention
that takes place among all the threads in the system.
 Allocation domain – The allocation domain is a set of multiple (or single)
resources for which a thread is competing.

Advantages of PCS over SCS:

 It is cheaper.
 It helps reduce system calls and achieve better performance.
 If the SCS thread is a part of more than one allocation domain, the system will
have to handle multiple interfaces.
 PCS thread can share one or multiple available LWPs, while every SCS thread
needs a separate LWP. Therefore, for every system call, a separate KLT will be
create

Real-Time Scheduling

Systems that carry real-time tasks are known as real-time systems. These tasks can be
divided into two categories:

 Soft real-time tasks: The task can be rescheduled.

 Hard real-time tasks: The tasks need to be performed within a certain time
period. In this system, the scheduler is considered the most important component.

The scheduler aims to reduce the response time for each process.

27
 Operating System

Real-time scheduling algorithms:

In a simple real-time system, there might be no need for a scheduler, one task can
simply call the next. But for more complex real-time systems, that have a large but
fixed number of tasks that do not function in pipeline function, one may need static
scheduling.

And for real-time systems where the workload keeps changing, one may need
dynamic scheduling.

In dynamic scheduling two important question arises:

1) How to handle the overload?

To handle the overload these processes can be used:

 Best efforts
 Work shedding

2) How to choose which process to execute first?

To decide which process to execute first from the ready queue these methods may be
used:

 SJF
 Static priority
 Slack time.

Context Switch

When the scheduler switches the CPU from executing one process to executing
another, the context switcher saves the content of all processor registers for the
process being removed from the CPU in its process being removed from the CPU in
its process descriptor. The context of a process is represented in the process control
block of a process.

28
 Operating System

 One process does not directly switch to another within the system. Context
switching makes it easier for the operating system to use the CPU’s resources to
carry out its tasks and store its context while switching between multiple
processes.
 Context switching enables all processes to share a single CPU to finish their
execution and store the status of the system’s tasks. The execution of the process
begins at the same place where there is a conflict when the process is reloaded
into the system.

State Diagram of Context Switching

Working Process Context Switching

1. The state of the current process must be saved for rescheduling.

2. The process state contains records, credentials, and operating system-specific
information stored on the PCB or switch.
3. The PCB can be stored in a single layer in kernel memory or in a custom OS
file.
4. A handle has been added to the PCB to have the system ready to run.
5. The operating system aborts the execution of the current process and selects a
process from the waiting list by tuning its PCB.
6. Load the PCB’s program counter and continue execution in the selected
process.

29
 Operating System

Operations On Processes

1) Process Creation

A process can create several new processes through create process system call during
the process execution. The process which creates a another process is called as parent
process and the new process is a child process.

Every new process creates another process forming a tree-like structure. It can be
identified with a unique process identifier that usually represents it as Pid which is
typically an integer number. Every process needs some resources like CPU time,
memory, file, I/O devices to accomplish. Whenever a process creates a sub process,
and may be each sub process is able to obtain its resources directly from the operating
system or from the resources of the parent process. The parent process needs to
partition its resources among all its children or it may be able to share some resources
to several children.

Restricting a child process to a subset of the parent’s resources prevents any process
from overloading the system by creating too many sub-processes. A process is going
to obtain its resources whenever it is created.

Whenever a process creates a new process, there are two possibilities in terms of
execution, which are as follows –

 The parent continues to execute concurrently with its children.

 The parent waits till some or all its children have terminated.

There are two more possibilities in terms of address space of the new process, which
are as follows-

 The child process is a duplicate of the parent process.

 The child process has a new program loaded into it.

2) Process Termination

A process terminates when it finishes executing its last statement and request the
operating system to delete it by issuing the “exit system call”. And the process may
return data, output to its parent

30
 Operating System

process when it exits using fork system call. And when a process exits all the
resources of that process including physical, virtual memory, open files, and
input/output buffers are de – allocated by the operating system.

Reasons for process termination

The reasons that the process may terminate the execution of one of its children are as
follows −

 The child exceeds its usage of resources that it has been allocated.
 The task that is 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.

INTER PROCESS COMMUNICATION [IPC]

Inter-process communication is communication between two processes that may be on

the same system or on a different system.

The process in the operating system is of two types:

1) Independent Process

2) Cooperating Process

An Independent process is one that doesn’t get affected by the other processes running
in the system. It doesn’t even affect the processing of any other process in the system.
This is because the independent process doesn’t share any data with the other process.

The cooperating process is one that shares data with the other processes in the system.
Thus, it can get affected by the other processes of the system. And even it can affect
the working of other processes. So, among these two processes, the cooperating
process requires inter-process communication.

Methods of Inter-Process Communication

31
 Operating System

There are two methods or two models that operating systems can implement to
achieve IPC. Some operating systems implement both of these models.

 Shared Memory
 Message Passing

1) Shared Memory System

In shared memory system a cooperating process creates a shared memory segment in

its address space. Now, if there occurs another process that wants to communicate
with this process. Then it must attach itself to the created shared memory segment.
The processes share data by reading and writing the data in the shared segment of the
processes.

Consider two cooperating processes P1 and P2. Both the processes P1 and P2 have
their different address spaces. Now let us assume, P1 wants to share some data with
P2. So, P1 and P2 will have to perform the following steps:

Step 1 − Process P1 has some data to share with process P2. First P1 takes initiative
and establishes a shared memory region in its own address space and stores the data or
information to be shared in its shared memory region.

Step 2 − Now, P2 requires the information stored in the shared segment of P1. So,
process P2 needs to attach itself to the shared address space of P1. Now, P2 can read
out the data from there.

32
 Operating System

Step 3 − The two processes can exchange information by reading and writing data in
the shared segment of the process.

2) Message Passing System

Message Passing provides a mechanism to allow processes to communicate and to

synchronize their actions without sharing the same address space. An IPC facility
generally provides two operations

 Send
 Receive

Message sent by processes can be either fixed or variable size. In order to send and
receive message from each other, the processes must have a communication link
existing between them. The link can be implemented in many ways.

Logically a link can be implemented using the following methods:

1. Direct or Indirect
2. Synchronous and Asynchronous Communication
3. Automatic and Explicit Buffering

For processes which want to communicate there must be a way in order to refer to
each other. They can be either direct or indirect communication.

33
 Operating System

1. Direct Communication:

In this method each processes which wants to communicate must explicitly name the
sender or recipient of the communication.

In this method the send and receive primitives are defined as follows

 Send (P, message) – means send a message to process P

 Receive (Q, message) – means receive a message from process Q

Addressing in this scheme is symmetric, that is both receiver and sender processes
have to name each other to communicate.

In asymmetric type, only the sender names the recipient, but recipient need not name
the sender so,

the send and receive primitive in this scheme is defined as,

 Send (P, message) – means send a message to process P

 Receive (id, message) – means receives message from any process

Where the variable id is set to the process name with which communication takes
place.

2. Indirect Communication:

In this scheme, the sending and receiving of message is done using a mail box (called
as ports). A mail box abstractly can be viewed as an object, where the processes place
their message and removes the messages from it. Each mail box will have a unique
identification and a process can communicate with some other process, through
number of different mailbox. Communication between two processes is possible, only
if they have a shared mailbox. The send, receive primitives are defined as,

 Send (B, message) – means send a message to mailbox B

 Receive (B, message) – means receive a message from mailbox B
 Synchronous and Asynchronous Communication

34
 Operating System

Communication happens using send() and receive(). There are many options for these
two primitives.

Message passing may be blocking or non-blocking also known asynchronous and

asynchronous.

 Blocking send – sending is blocked, until a message is received by receiving

process or mailbox.
 Non-blocking send – sending process sends the message and resumes operation.
 Blocking receive – receiver blocks until a message is available.
 Non-blocking receive – the receiver retrieves either a valid message or a null.

3. Automatic and Explicit Buffering

The number of messages that can be present is determined by a link and is considered
as queue of messages to the link. This queue can be implemented using the following
3 methods

1) Zero Capacity Queue:

This has maximum length zero, so a link cannot maintain any message waiting in it.
Thus sender must wait until the recipient receives the message. And also the two
processes communicating must be synchronized for a message transfer to happen.
This queue type is also called as message system with no buffering.

2) Bounded Capacity Queue:

This type will have a finite length say ‘n’. So at the most ‘n’ messages can be stored in
it. The new messages sent can be placed in queue, if it is not full. And sender can
continue execution. When the link is full, the sender must wait, until the queue space
becomes free. This queue provides automatic buffering.

3) Unbounded Capacity Queue:

35
 Operating System

This has a infinite length and hence any number of messages can wait in it. So, the
sender will not be delayed anytime. This queue type also provides automatic
buffering.

36