DICT Module 1 Operating System

September 15, 2017

INTRODUCTION TO OPERATING SYSTEMS

DEFINITION OF OPERATING SYSTEM

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

DEFINITION OF TERMS IN OPERATING SYSTEM

(a) System Calls and System Programs

System calls/monitor call

System call provide an interface between the process and the operating system. It is a request made by
any program to the operating system for performing task. It is used whenever a program needs to
access a restricted source e.g. a file on the hard disc, any hardware device.

Type of system calls:

i. Process control (e.g., create and terminate processes* load ,execute* end abort* wait signal
event etc.)

ii. File management (e.g., open and close files,* create file, delete file* read , write)

iii. Device management (e.g., read and write operations* request or release a device)

iv. Information maintenance (e.g., get time or date* set process, file or device attributes* get
system data)

v. Communication (e.g., send and receive messages)

System calls allow user-level processes to request some services from the operating system which
process itself is not allowed to do. In handling the trap, the operating system will enter in the kernel
mode, where it has access to privileged instructions, and can perform the desired service on the behalf
of user-level process. It is because of the critical nature of operations that the operating system itself
does them every time they are needed. For example, for an I/O a process involves a system call telling
the OS to read or write particular area and this request is satisfied by the operating system.

System programs

Provide a convenient environment for program development (editors, compilers) and execution (shells).
Some of them are simply user interfaces to system calls; others are considerably more complex. They
can be divided into these categories:

Types of System Programs

Page 1 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

i. File management: These programs create, delete, copy, rename, print, dump, list, and generally
manipulate files and directories.
ii. Status information/management: 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.
iii. File modification: Several text editors may be available to create and modify the content of files
stored on disk or tape.
iv. Programming-language support: Compilers, assemblers, and interpreters for common
programming languages (such as C, C++, Java, Visual Basic, and PERL) are often provided to the
user with the operating system, although some of these programs are now priced and provided
separately.
v. Program loading and execution: Once a program is assembled or compiled, it must be loaded
into memory to be executed. The system may provide absolute loaders, re-locatable loaders,
linkage editors, and overlay loaders. Debugging systems for either higher-level languages or
machine language are needed also.
vi. Communications: These programs provide the mechanism for creating virtual connections
among processes, users, and computer systems. They allow users to send messages to one
another's screens, to browse web pages, to send electronic mail messages, to log in remotely, or
to transfer files from one machine to another.

(b) THE Shell

The shell is the software program that interprets commands from the user so that the operating system
can understand them and perform the appropriate functions. Therefore, the shell is the outermost part
of an operating system that interacts with user commands and after verifying that the commands are
valid, the shell sends them to another part of the command processor to be executed.

Operating system shells generally fall into one of two categories:

i) Command-line shells provide a command-line interface (CLI) to the operating system

ii) Graphical shells provide a graphical user interface (GUI).

In either category the primary purpose of the shell is to invoke or "launch" another program; however,
shells frequently have additional capabilities such as viewing the contents of directories.

The best choice is often determined by the way in which a computer will be used. On a server mainly
used for data transfers and processing with expert administration, a CLI is likely to be the best choice.
On the other hand, a GUI would be more appropriate for a computer to be used for image or video
editing and the development of the above data.

(c) The Kernel

The kernel is the central part of an operating system that directly controls the computer hardware. It is
the only way through which the programs (all programs including shell) can access the hardware. It is a

Page 2 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

layer between the application programs and hardware. It manages everything including the
communication between the hardware and software.

Operating system kernels are specific to the hardware on which they are running, thus most operating
systems are distributed with different kernel options that are configured when the system is installed.
Changing major hardware components such as the motherboard, processor, or memory, often requires
a kernel update.

Functions of the kernel's

Managing the system's resources i.e. the communication between hardware and software components
Usually as a basic component of an operating system, a kernel can provide the lowest-level abstraction
layer for the resources (especially processors and I/O devices) that application software must control to
perform its function. It typically makes these facilities available to application processes through inter-
process communication mechanisms and system calls.

Operating system tasks are done differently by different kernels, depending on their design and
implementation. While monolithic kernels will try to achieve these goals by executing all the operating
system code in the same address space to increase the performance of the system, microkernels run
most of the operating system services in user space as servers, aiming to improve maintainability and
modularity of the operating system.[2] A range of possibilities exists between these two extremes.

Kernel Basic Facilities

The kernel's primary purpose is to manage the computer's resources and allow other programs
to run and use these resources. Typically, the resources consist of:

i. The Central Processing Unit (CPU, the processor). This is the most central part of a
computer system, responsible for running or executing programs on it. The kernel takes
responsibility for deciding at any time which of the many running programs should be
allocated to the processor or processors (each of which can usually run only one program at
a time)
ii. The computer's memory. Memory is used to store both program instructions and data.
Typically, both need to be present in memory in order for a program to execute. Often
multiple programs will want access to memory, frequently demanding more memory than
the computer has available. The kernel is responsible for deciding which memory each
process can use, and determining what to do when not enough is available.
iii. Any Input/output (I/O) devices present in the computer, such as keyboard, mouse, disk
drives, printers, displays, etc. The kernel allocates requests from applications to perform I/O
to an appropriate device and provides convenient methods for using the device (typically
abstracted to the point where the application does not need to know implementation
details of the device).

Page 3 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Kernels also usually provide methods for synchronization and communication between
processes (called inter-process communication or IPC).

A kernel may implement these features itself, or rely on some of the processes it runs to
provide the facilities to other processes, although in this case it must provide some means of
IPC to allow processes to access the facilities provided by each other.

Finally, a kernel must provide running programs with a method to make requests to access
these facilities.

What is the difference between kernel and shell?

The Shell is a program which allows the user to access the computer system and it act as an
interface between the user and the computer system. It acts as an interface between the user
and the kernel

The Kernel is the only way through which the programs (all programs including shell) can access
the hardware. It’s a layer between the application programs and hardware. It is the core of most
of the operating systems and manages everything including the communication between the
hardware and software.

Decomposition of Linux System into Major Subsystems

(d) Virtual Machines (VM)

A virtual machine, VM, is a software between the kernel and hardware.

Thus, a VM provides all functionalities of a CPU with software simulation. A
user has the illusion that he/she has a real processor that can run a kernel.

Page 4 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

(e) A process

A process is a program in execution. A process is more than a program, because it’s associated with
resources such as registers (program counter, stack pointer) list of open files etc. Moreover, multiple
processes may be associated with one program (e.g., run the same program, a web browser, twice).

(f) Virtual Memory

Virtual memory is a computer system technique which gives an application program the impression that
it has contiguous working memory (an address space), while in fact it may be physically fragmented and
may even overflow on to disk storage.

Systems that use this technique make programming of large applications easier and use real physical
memory (e.g. RAM) more efficiently than those without virtual memory

g) File

Hides away the peculiarities of disk and input/output device and provides the programmers with an easy
way to create, retrieve and modify files.

Page 5 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

HISTORY OF OPERATING SYSTEM

Since operating system has historically been closely tied to the architecture of the computer on which
they run we will look at successive generation of computer to see what their operations were like.

1. First generation computers (1945 - 1955) Vacuum tube

The earliest electronic digital computers had no operating systems. Machines of the time were so
primitive that programs were often entered one bit at time on rows of mechanical switches (plug
boards). Programming languages were unknown (not even assembly languages). Operating systems
were unheard of.

In these early days a single group of people (usually engineers) designed, built, programmed, operated
and maintained each machine.

2. Second generation computer (1955 1965) Transistor and batch systems

This computer had improved with the introduction of punch cards. The General Motors Research
Laboratories implemented the first operating systems in early 1950's for their IBM 701. This system ran
one job at a time. They were called single-stream batch processing systems because programs and data
were submitted in groups or batches.
These computers were mostly used for scientific and engineering calculation, such as partial
differentiation equations that often occur in physics and engineering. They were largely programmed in
FORTRAN and assembly language. Typically the OS were FMS ( the Fortran Monitor System) and IBSYS,
IBMS OS for the 7094

3. Third generation computers (1965 1980) Integrated Circuits (ICs) and multiprogramming
The systems of the 1960's were also batch processing systems, but they were able to take better
advantage of the computer's resources by running several jobs at once.

Main features of this operating system

i) Multiprogramming
So operating systems designers developed the concept of multiprogramming in which
several jobs are in main memory at once; a processor is switched from job to job as needed
to keep several jobs advancing while keeping the peripheral devices in use. While one job
was waiting for I/O to complete, another job could be using the CPU.
ii) Spooling (simultaneous peripheral operations on line).
In spooling, a high-speed device like a disk interposed between a running program and a
low-speed device involved with the program in input/output. Instead of writing directly to a
printer, for example, outputs are written to the disk. Programs can run to completion faster,

Page 6 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

and other programs can be initiated sooner when the printer becomes available, the
outputs may be printed.
iii) Time-sharing technique

Timesharing systems were developed to multiprogram large number of simultaneous

interactive users.

4. Fourth generation computers (1980 1989)

With the development of LSI (Large Scale Integration) circuits, chips, operating system entered in the
personal computer and the workstation age. Microprocessor technology evolved to the point that it
become possible to build desktop computers as powerful as the mainframes of the 1970s.

Two operating systems dominated the personal computer scene: MS-DOS, written by Microsoft, Inc. for
the IBM PC and other machines using the Intel 8088 CPU and its successors, and UNIX, which is
dominant on the large personal computers using the Motorola 6899 CPU family.

5. Fifth generation computers (1990 Present)

This generation is characterized by the emerging of telecommunication with computer technology.

Scientists are working on this generation to bring machines with genuine IQ the ability to reason
logically and with real knowledge of the world. The anticipated computer will have the following
characteristics

 It is expected to do parallel processing

 It will be based on logical inference operations
 It's expected to make use of artificial intelligence (AI)

STRUCTURE OF OPERATING SYSTEMS

As modern operating systems are large and complex careful engineering is required. There are four
different structures that have shown in this document in order to get some idea of the spectrum of
possibilities. These are by no mean s exhaustive, but they give an idea of some designs that have been
tried in practice.

(a) Monolithic Systems:

In this approach the entire operating system runs as a single program in the kernel node. The operating
system is written as a collection of thousands of procedures, each of which can call any of the other
ones whenever it needs to without restriction making it difficult to understand the system.

To constructing the actual object program of the operating system when this approach is used, one
compiles all the individual procedures, or files containing the procedures, and then binds them all
together into a single executable file using the system linker. In terms of information hiding, there is
essentially none- every procedure is visible to every other one i.e. opposed to a structure containing

Page 7 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

modules or packages, in which much of the information is local to module, and only officially designated
entry points can be called from outside the module.

Even in Monolithic systems, it is possible to have at least a little structure. The services like system calls
provided by the operating system are requested by putting the parameters in well-defined places, such
as in registers or on the stack, and then executing a special trap instruction known as a kernel call or
supervisor call.

Main Main
procedure
procedure

Service procedures

Utility procedure

A simple structuring model for a monolithic system

Problems with monolithic structure

i. Difficult to maintain
ii. Difficult to take care of concurrency due to multiple users/jobs

(b) Layered System:

The operating system is broken up into a number of layers (or levels), each on top of lower layers. Each
layer is an implementation of an abstract object that is the encapsulation of data and operations that
can manipulate these data. The operating system is organized as a hierarchy of layers, each one
constructed upon the one below it.

This operating system structure has 6 layers.

Layer Function
5 The operator
4 User program
3 i/o management
2 Operator-process communication
1 Memory and drum management
0 Process allocation and multiprogramming

Page 8 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Layer 0 was responsible for the multiprogramming aspects of the operating system. It decided which
process was allocated to the CPU. It dealt with interrupts and performed the context switches when a
process change was required.

Layer 1 was concerned with allocating memory to processes. It allocated space for processes in main
memory and on a 512k word drum used for holding parts of processes (pages) for which there was no
room in main memory. Above layer 1, processes did not have to worry about whether they were in
memory or on the drum; the layer 1 software took care of making sure pages were brought into
memory whenever they were needed.

Layer 2 deals with inter-process communication and communication between the operating system and
the console.

Layer 3 managed all I/O between the devices attached to the computer. This included buffering
information from the various devices. It also dealt with abstract I/O devices with nice properties, instead
of real devices with many peculiarities.

Layer 4 was where the user programs were found. They did not have to worry about process, memory,
console, or I/O management.

Layer 5 was the overall control of the system (called the system operator)

(c) Virtual Machines:

The heart of the system, known as the virtual machine monitor, runs on the bare hardware and does the
multiprogramming, providing not one, but several virtual machines to the next layer up. However, unlike
all other operating systems, these virtual machines are not extended machines, with files and other nice
features. Instead, they are exact copies of the bare hardware, including kernel/user mod, I/O, interrupts,
and everything else the real machine has.

For reason of each virtual machine is identical to the true hardware, each one can run any operating
system that will run directly on the hard ware. Different virtual machines can, and usually do, run
different operating systems. Some run one of the descendants of OF/360 for batch processing, while
other ones run a single-user, interactive system called CMS (conversational Monitor System) from
timesharing users.

(d) Client-server Model:

In this model computers share the processing and storage within a central server. Server provides
services to any client that requests it. Model is heavily used in distributed systems e.g. print server or
database.Operating systems can be designed as a client/server

Page 9 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

To request a service, such as reading a block of a file, a user process (presently known as the client
process) sends the request to a server process, which then does the work and sends back the answer.

In client-Server Model, all the kernel does is handle the communication between clients and servers. By
splitting the operating system up into parts, each of which only handles one fact of the system, such as
file service, process service,

Terminal service, or memory service, each part becomes small and manageable; furthermore, because
all the servers run as user-mode processes, and not in kernel mode, they do not have direct access to
the hardware. As a consequence, if a bug in the file server is triggered, the file service may crash, but
this will not usually bring the whole machine down.

Client Client Process File Memory ……… User Mode

Process Process Server Server Server Server
Kernel Kernel Mode

Message sent
from client to
server
Benefits include

i. Can result in a minimal kernel

ii. As each server is managing one part of the operating system, the procedures can be better
structured and more easily maintained.
iii. If a server crashes it is less likely to bring the entire machine down as it won’t be running in
kernel mode. Only the service that has crashed will be affected.
iv. Adaptability to use in distributed system. If a client communicates with a server by sending it
messages, the client need not know whether the message is handled locally in its own machine,
or whether it was sent across a network to a server on a remote machine. As far as the client is
concerned, the same thing happens in both cases: a request was sent and a reply came back.

NB in client server model OS is divided into modules instead of layers. Modules are treated more or less
equal. Instead of calling each other like procedures they communicate through sending messages via
external message handler

Page 10 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

TYPES OF OPERATING SYSTEM

1. Traditional OS / batch systems (single user)

It’s the earliest OS to be develops. It refers to a single processor OS that controls a single microprocessor
which is centralized. They allow one job to run at a time e.g. an OS of the 2nd generation whereby the job
are processed serially. Programs and data are submitted to the computer in form of a “Job”. The job has
to be completed for the next to be loaded and processed.

In batch systems several jobs are collected and processed once as a group then the next is processed.
The processes are is in sequential one job after another. Consequently many support one user at a time
there is little or no interaction between the user and the executing program. Thus the OS is not user
friendly and is tedious

2. Multiprocessor operating system (Multiprocessing OS)

Multiprocessing - An operating system capable of supporting and utilizing more than one computer
processor at a time.

Advantages

i. Reduces CPU idle time

ii. Reduces incidences of peripheral bound operations
iii. Increases productivity of the computer

Disadvantages

i. Requires expensive CPU

ii. Its complex and difficult to operate

3. Distributed operating system

Distributed operating system is an operating system which manages a number of computers and
hardware devices which make up a distributed system.

With the advent of computer networks, in which many computers are linked together and are able to
communicate with one another, distributed computing became feasible. A distributed computation is
one that is carried out on more than one machine in a cooperative manner. A group of linked computers
working cooperatively on tasks

Such an operating system has a number of functions:

i. It manages the communication between entities on the system

ii. It imposes a security policy on the users of the system

Page 11 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

iii. It manages a distributed file system

iv. It monitors problems with hardware and software
v. It manages the connections between application programs and itself
vi. It allocates resources such as file storage to the individual users of the system.

NB A good distributed operating system should give the user the impression that they are interacting
with a single computer.

Advantages

i. Reduction of load of the host computer

ii. Requires low cost mini computers
iii. Reduction in delay
iv. Better service to customers

Disadvantages

i. Expensive because of the extra cost of communication devices

ii. Data duplication is high
iii. Programming problem
iv. Extra training needed for the users

Others

4. Interactive OS

a) Single-user operating system?

In essence, a single-user operating system provides access to the computer system by a single user at a
time. If another user needs access to the computer system, they must wait till the current user finishes
what they are doing and leaves. In this instance there is one keyboard and one monitor that you interact
with. There may also be a printer for the printing of documents and images.

Operating systems such as Windows 95, Windows NT Workstation and Windows 2000 professional are
essentially single user operating systems.

b) Multi-User Operating System

A multi-user operating system lets more than one user access the computer system at one time. Access
to the computer system is normally provided via a network, so that users access the computer remotely
using a terminal or other computer.

Today, these terminals are generally personal computers and use a network to send and receive
information to the multi-user computer system. Examples of multi-user operating systems are UNIX,
Linux (a UNIX clone) and mainframes such as the IBM AS400.

Page 12 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Multi-user operating system must manage and run all user requests, ensuring they do not interfere with
each other. Devices that are serial in nature (devices which can only be used by one user at a time, like
printers and disks) must be shared amongst all those requesting them (so that all the output documents
are not jumbled up).

If each user tried to send their document to the printer at the same time, the end result would be
garbage. Instead, documents are sent to a queue, and each document is printed in its entirety before
the next document to be printed is retrieved from the queue. When you wait in-line at the cafeteria to
be served you are in a queue. Imagine that all the people in the queue are documents waiting to be
printed and the cashier at the end of the queue is the printer.

5. Networking operating system (NOS)

A networking operating system is an operating system that contains components and programs that
allow a computer on a network to serve requests from other computers for data and provide access to
other resources such as printer and file systems.

Features

 Add, remove and manage users who wish to use resources on the network.
 Allow users to have access to the data on the network. This data commonly resides on the
server.
 Allow users to access data found on other network such as the internet.
 Allow users to access hardware connected to the network.
 Protect data and services located on the network.
 Enables the user to pass documents on the attached network.

Page 13 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

JOB CONTROL
Job control in computing refers to the control of multiple tasks or Jobs on a computer system, ensuring
that they each have access to adequate resources to perform correctly, that competition for limited
resources does not cause a deadlock where two or more jobs are unable to complete, resolving such
situations where they do occur, and terminating jobs that, for any reason, are not performing as
expected.

i. Job control language (JCL)

Job Control Language is a means of communicating with the IBM 3090 MVS Operating System. JCL
statements provide information that the operating system needs to execute a job. A job is
something that you want to accomplish with the aid of a mainframe computer (e.g. copy a data set,
execute a program, or process multiple job steps).

You need to supply the information that the job requires and instruct the computer what to do with
this information. You do this with JCL statements. A job step consists of statements that control the
execution of a program or procedure, request resources, and define input and/or output.

ii. Command languages

The shell is a command language or it’s a layer or a software that separate the user from the rest of
the machine. The user expresses commands to the shell which intern invokes low level and kernel
services as appropriate to implement the command. It creates processes pipes and connects them
with files and devices as needed to carry out the command.

Command language interfaces uses artificial language much like programming language. They
usually permits a user to combine constructs in a new and complex ways hence more powerful for
advance users. For then command language provides a strong feeling that they are in charge and
that they are taking the initiative rather than responding to the computer.

Command language users must learn the syntax but they can often express complex possibilities
without having distracting prompts. Command language interfaces are also the style most enabled
to programming that is writing programs or scripts of user input command

iii. System messages

System Message is a utilitiy for looking up the descriptive text that corresponds to a Windows
system error number. System Message can be used either as a desktop application or as a simple
out-of-process Object Linking and Embedding (OLE) Automation server.

Page 14 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

PROCESS MANAGEMENT

Process Management
A program does nothing unless its instructions are executed by a CPU. Process management is an
integral part of any modern day operating system (OS). In multiprogramming systems the OS must
allocate resources to processes, enable processes to share and exchange information, protect the
resources of each process from other processes and enable synchronization among processes. To meet
these requirements, the OS must maintain a data structure for each process, which describes the state
and resource ownership of that process, and which enables the OS to exert control over each process

What is a process?
A process is a sequential program in execution. The components of a process are the following:

i. The object program to be executed ( called the program text in UNIX)

ii. The data on which the program will execute (obtained from a file or interactively from the
process's user)
iii. Resources required by the program ( for example, files containing requisite information)
iv. The status of the process's execution

Two concepts emerge:

 Uni-programming: - case whereby a system allows one process at a time.

 Multi-programming: - system that allows more than one process, multiple processes at a time.

A process comes into being or is created in response to a user command to the OS. Processes may also
be created by other processes e.g. in response to exception conditions such as errors or interrupts.

DESCRIPTION OF THE PROCESS MODEL / STATES

PROCESS STATES

As a process executes, it changes state. The state of a process is defined in part by the current activity of
that process. Process state determines the effect of the instructions i.e. everything that can affect, or be
affected by the process. It usually includes code, particular data values, open files, registers, memory,
signal management information etc. We can characterize the behavior of an individual process by listing
the sequence of instruction that execute for that process. Such listing is call the trace of processes

Each process may be in one of the following states

i. New: The process is being created

ii. Running: The process is being executed i.e. actually using the CPU at that instant
iii. Waiting/blocked: The process is waiting for some event to occur (e.g., waiting for I/O
completion) such as completion of another process that provides the first process with
necessary data, for a synchronistic signal from another process, I/O or timer interrupt etc.

Page 15 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

iv. Ready: The process is waiting to be assigned to a processor i.e. It can execute as soon as CPU is
allocated to it.
v. Terminated: The process has finished execution

A transition from one process state to another is triggered by various conditions as interrupts and user
instructions to the OS. Execution of a program involves creating & running to completion a set of
programs which require varying amounts of CPU, I/O and memory resources.

Process Control Block (PCB)

If the OS supports multiprogramming, then it needs to keep track of all the processes. For each process,
its process control block (PCB) is used to track the process's execution status, including the following:

i. Its current processor register contents

ii. Its processor state (if it is blocked or ready)
iii. Its memory state
iv. A pointer to its stack
v. Which resources have been allocated to it
vi. Which resources it needs
vii. Execution state (saved registers etc.)
viii. Scheduling info
ix. Accounting & other miscellaneous info.

OS must make sure that processes don’t interfere with each other, this means

i. Making sure each gets a chance to run (scheduling).

ii. Making sure they don’t modify each other’s state (protection).

The dispatcher (short term scheduler) is the inner most portion of the OS that runs processes:

- Run processes for a while.

- Save state
- Load state of another process.
- Run it etc.

Page 16 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

It only run processes but the decision on which process to run next is prioritized by a separate scheduler.

When a process is not running, its state must be saved in its process control block. Items saved include:

i. Program counter
ii. Process status word (condition codes etc.).
iii. General purpose registers
iv. Floating - point registers etc.

When no longer needed, a process (but not the underlying program) can be deleted via the OS, which
means that all record of the process is obliterated and any resources currently allocated to it are
released.

THERE ARE VARIOUS MODELS THAT CAN BE USED

i. Two state process model

ii. Three state process model
iii. Five state model

1. Two state process model

The principal responsibility of the OS is to control the execution of a process; this will include the
determination of interleaving patters for execution and allocation of resources to processes. We can
contrast the simplest model by observing that a process can either executed or not i.e. running or not
running

Each process must be presented in some way so that the OS can keep track of it i.e. the process control
block. Processes that are not running must be kept in some sort of a queue waiting their turn to execute.
There is a single queue in which each entry is a pointer to the PCB of a particular block.

Dispatch

Enter Exit
Not Running Running

Pause

Two State transition diagram

Page 17 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

2. Three state
Completion

Running (Active)

Delay Suspend
Dispatch
Submit
Resume
Ready
Blocked
(Wake up)

Three State transition diagram

i. Ready: The process is waiting to be assigned to a processor i.e. It can execute as soon as CPU is
allocated to it.
ii. Running: The process is being executed i.e. actually using the CPU at that instant
iii. Waiting/blocked: The process is waiting for some event to occur (e.g., waiting for I/O
completion) such as completion of another process that provides the first process with
necessary data, for a synchronistic signal from another process, I/O or timer interrupt etc.

3. Five State

In this model two states have been added to the three state model i.e. the new and exit state. The new
state correspond to a process that has just been defined e.g. a new user trying to log onto a time sharing
system. In this instance, any tables needed to manage the process are allocated and built.

In the new state the OS has performed the necessary action to create the process but has not
committed itself to the execution of the process i.e. the process is not in the main memory.

In exit state a process may exit due to two reasons

i. Termination when it reaches a natural completion point

ii. When its aborted due to an unrecoverable error or when another process with appropriate
authority causes it to stop

Page 18 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Dispatch
Admit Release
New Ready Running Exit

Time out

Event Event
occurs wait

Blocked

Five State transition diagram

i. Running: The process is currently being executed i.e. actually using the CPU at that instant
ii. Ready: The process is waiting to be assigned to a processor i.e. It can execute as soon as CPU is
allocated to it.
iii. Waiting/blocked: The process is waiting for some event to occur (e.g., waiting for I/O
completion) such as completion of another process that provides the first process with
necessary data, for a synchronistic signal from another process, I/O or timer interrupt etc.
iv. New: The process has just been created but has not yet being admitted to the pool of
executable processes by the OS i.e. the new process has not been loaded into the main memory
although its PBC has been created.
v. Terminated/exit: The process has finished execution or the process has been released from the
pool of executable processes by the OS either because it halted or because it was aborted for
some reasons.

In a five state model the state transition are as follows

i. Null ----- New

A new process is created to execute a program
ii. New ---- Ready
The OS will move the process from new state to ready state when its prepared to take on an
additional process.
iii. Ready ----- Running
When it’s time to select a new process to run the OS chooses one of the processes in ready state
iv. Running ---- Exit
The currently running process is terminated by the OS if the process indicate that it has
completed or its aborted.
v. Running ----- Ready
The common reason for this condition is that the running process has reached the maximum
allowable time for uninterruptible execution

Page 19 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

vi. Running ---- Blocked

A process is put into a blocked state if it request something for which must wait e.g. when
process communicate with each other, process may be blocked when its waiting for another
process to provide an input or waiting for a message from another process

vii. Blocked ---- Ready

A process is in the blocked state is moved to the ready state when the event for which it has
been waiting occurs
viii. Ready ---- Exit
A parent may terminate a child process at any time if a parent associates with that.
ix. Blocked ---- Exit

Creation and termination of process

When a new process is to be added to those concurrently being managed the OS builds the data
structures that are used to manage the process and allocates address space to the processor

Reasons for process creation

i. New batch job

The OS is provided with a batch job control stream usually on tape or disk. When the OS is
prepared to take on a new work it will load the next job sequence of job control command
ii. Interactive log on
A user at a terminal logs on to the system
iii. Created by OS provider service
The OS can create a process to perform functions on behalf of a user program without the user
having to wait
iv. Sprung by existing process
For purpose of modularity or to exploit parallelism a user program can declare creation of a
number of processes

Reasons for process termination

i. Normal completion
The process executes an OS service call to indicate that it has completed running
ii. Time limit exceeded
The process has run longer than the specified total time limit
iii. Memory unavailable
The process requires more memory than the system can provide
iv. Bound variation
The process tries to access memory location that it is not allowed to access
v. Protection error

Page 20 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

The process attempts to use a resource or a file that is not allowed to use or it tries to use it in
an improper version such as writing to read only file
vi. Arithmetic error
The process tries to prohibit computation e.g. division by zero or tries to state number larger
than the hardware can accommodate
vii. Time overrun
The process has waited longer than a specified maximum time for a certain event to occur
viii. I/O failure
An error occurs during I/O such as inability to find a file. Failure to read or write or write after a
specified number of times
ix. Invalid instruction
The process attempts to execute a non-existing instruction
x. Data misuse
A piece of data is of the wrong type or is not initialized
xi. Operator / OS intervention
For some reasons the operator or OS has terminated the process e.g. if a deadlock existed

Criteria For Performance Evaluation

i. Utilization: The fraction of time a device is in use. ( ratio of in-use time / total Observation time )
ii. Throughput: The number of job completions in a period of time. (jobs / second )
iii. Service time the time required by a device to handle a request. (Seconds)
iv. Queuing time: Time on a queue waiting for service from the device. (Seconds)
v. Residence time: The time spent by a request at a device.
vi. Residence time = service time + queuing time.
vii. Response time: Time used by a system to respond to a user job. (Seconds)
viii. Think time: The time spent by the user of an interactive system to figure out the next request.
(Seconds)
ix. The goal is to optimize both the average and the amount of variation. (But beware the ogre
Predictability)

Page 21 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

INTER PROCESS COMMUNICATION (IPC )

A capability supported by some operating systems that allows one process to communicate with another
process. The processes can be running on the same computer or on different computers connected
through a network.

IPC enables one application to control another application, and for several applications to share the
same data without interfering with one another. IPC is required in all multiprocessing systems.

Definitions of Terms

1. Race Conditions

The race condition is the situation where several processes access and manipulate shared data
concurrently. The final value of the shared data depends upon which process finishes last. To prevent
race conditions, concurrent processes must be synchronized.

Example:

Consider the following simple procedure:

void deposit (int amount)

balance = balance + amount;

Where we assume that balance is a shared variable, suppose process PI calls deposit (10) and process P2
calls deposit (20). If one completes before the other starts, the combined effect is to add 30 to the
balance. However, the calls may happen at exactly the same time. Suppose the initial balance is 100, and
the two processes run on different CPUs. One possible result is

P1 loads 100 into its register

P2 loads 100 into its register

P1 adds 10 to its register, giving 110

P2 adds 20 to its register, giving 120

P1 stores 110 in balance

P2 stores 120 in balance

and the final effect is to add only 20 to the balance.

This kind of bug is called a race condition. It only occurs under certain timing conditions. It is very
difficult to track down it since it may disappear when you try to debug it. It may be nearly impossible to

Page 22 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

detect from testing since it may occur very rarely. The only way to deal with race conditions is through
very careful coding. The systems that support processes contain constructs called synchronization
primitives to avoid these problems

2. Critical Sections

Are sections in a process during which the process must not be interrupted, especially when the
resource it requires is shared. It is necessary to protect critical sections with interlocks which allow only
one thread (process) at a time to transverse them.

3. Sleep & Wakeup

This is an inter-process communication primitive that block instead of wasting CPU time when they
(processes) are not allowed to enter their critical sections. One of the simplest is the pair SLEEP and
WAKEUP.

SLEEP is a system call that causes the caller to block, that is, be suspended until another process wakes it
up. The WAKEUP call has one parameter, the process to be awakened.

E.g. the case of producer-consumer problem – where the producer, puts information into a buffer and
on the other hand, the consumer, takes it out. The producer will go to sleep if the buffer is already full,
to be awakened when the consumer has removed one or more items. Similarly, if the consumer wants
to remove an item from the buffer and sees the buffer is empty, it goes to sleep until the producer puts
something in the buffer and wakes it up.

4. Event counters

An event counter is another data structure that can be used for process synchronization. Like a
semaphore, it has an integer count and a set of waiting process identifications. Un-like semaphores, the
count variable only increases. This uses a special kind of variable called an Event Counter.

An event counter E has the following three operations defined;

i. read(E): return the count associated with event counter E.

ii. advance(E): atomically increment the count associated with event counter E.
iii. await(E,v): if E.count ≥ v, then continue. Otherwise, block until E. count ≥ v.

Before a process can have access to a resource, it first reads E, if value good, advance E otherwise await
until v reached.

Page 23 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

5. Message Passing

When processes interact with one another, two fundamental requirements must be satisfied:
synchronization and communication. One approach to providing both of this function is message
passing. A case where a processor (is a combination of a processing element (PE) and a local main
memory, it may include some external communication (I/O) facilities) when processing elements
communicate via messages transmitted between their local memories. A process will transmit a
message to other processes to indicate state and resources it is using.

In Message Passing two primitives SEND and RECEIVE, which are system calls, are used. The SEND sends
a message to a given destination and RECEIVE receives a message from a given source.

Synchronization

Definition: Means the coordination of simultaneous threads or processes to complete a task in order to
get correct runtime order and avoid unexpected race conditions

The communication of a message between two processing will demand some level of synchronization.
Since there is need to know what happens after a send or receive primitive is issued.

The sender and the receiver can be blocking or non-blocking. Three combinations are common but only
one can be applied in any particular system

i. Blocking send, blocking receive. Both the sender and the receiver are blocked until the message
is delivered. this allows for tight synchronization
ii. Non-blocking send, blocking receive. Although the sender may continue on, the receiver is
blocked until the requested message arrives. This method is effective since it allows a process to
send more than one message to a variety of destination as quickly as possible.
iii. Non-blocking send, non-blocking receive. Neither party is required to wait. Useful for
concurrent programming.

Addressing

When a message is to send it is necessary to specify the in the send primitive which process is to receive
the message. This can be either direct addressing or indirect addressing

Direct addressing

The send primitive include a specific identifier of the destination process. There are two ways to
handle the receiving primitive.

i. Require that the process explicitly designate a sending process. i.e. a process must know a
head of time from which process a message is expected

Page 24 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

ii. Use of implicit addressing where the source parameter of the receive primitive possesses a
value returned when a receive operation has been performed.

Indirect addressing

This case instead of sending a message directly to the receiver the message is sent to a shared data
structure consisting of a queue that can temporarily hold messages. Such queues are often referred to
as mailboxes.

General Message format

Message type
Destination ID
Header Source ID
Message length
Control information

Body Message content

6. Equivalence of primitives

Many new IPC’s have been proposed like sequencers, path expressions and serializers but are similar to
other ones. One can be able to build new methods or schemes from the four different inter-process
communication primitives – semaphores, monitors, messages & event counters. The following are the
essential equivalence of semaphores, monitors, and messages.

i. Using semaphores to implement monitors and messages

ii. Using monitors to implement semaphores and messages
iii. Using messages to implement semaphores and monitors

FUNDAMENTALS OF CONCURRENT PROCESSES

1. Mutual Exclusion

The mutual exclusion is a way of making sure that if one process is using a shared modifiable data, the
other processes will be excluded from doing the same thing. It’s a way of making sure that processes are
not in their critical sections at the same time

There are essentially three approaches to implementing mutual exclusion.

i. Leave the responsibility with the processes themselves: this is the basis of most software
approaches. These approaches are usually highly error-prone and carry high overheads.

Page 25 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

ii. Allow access to shared resources only through special-purpose machine instructions: i.e. a
hardware approach. These approaches are faster but still do not offer a complete solution to the
problem, e.g. they cannot guarantee the absence of deadlock and starvation.
iii. Provide support through the operating system, or through the programming language. We shall
outline three approaches in this category: semaphores, monitors, and message passing.

Requirement for mutual exclusion

i. Mutual exclusion must be enforced. Only one process is allowed into its critical section,
among all processes that have critical section for the same resources or shared objects
ii. A process that halts in its noncritical section must do so without interfering with other
processes
iii. It must be possible for a process requiring access to a critical section to be delayed
indefinitely: no deadlock no starvation
iv. When no process is in a critical section, any process that request entry to its critical section
must be permitted to enter without delay
v. No assumptions are made about relative process speeds or number of processors.
vi. A process remains inside its critical section for a finite time only

2. Semaphores

Semaphores are integer variables used by processes to send signals to other processes. Semaphores
can only be accessed by two operations:

P (Wait or Down)

V (Signal or Up)

A semaphore is a control or synchronization variable (that takes on positive integer values) that is
associated with each critical resource R, which indicates when the resource is being used. e.g. Each
process must first read S, if S = 1 (busy) it doesn’t take control of resource R, if S = 0, it takes control &
sets S to 1 and proceeds to use R.

Semaphores aren’t provided by hardware but have the following properties:

i. Machine independent.
ii. Simple
iii. Powerful (embody both exclusion and waiting).
iv. Correctness is easy to determine.
v. Work with many processes.
vi. Can have many different critical sections with different semaphores.
vii. Can acquire many resources simultaneously.
viii. Can permit multiple processes into the critical section at once, if that is desirable.
They do a lot more than just mutual exclusion.

Page 26 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Problems with Semaphores

i. Semaphores do not completely eliminate race conditions and other problems (like deadlock).
ii. Incorrect formulation of solutions, even those using semaphores, can result in problems.

3. Monitors

A high-level data abstraction tool that automatically generates atomic operations on a given data
structure. It has a collection of procedures, variables and data structures that are all grouped together
in a special kind of module or package. Thus a monitor has: - shared data, a set of atomic (tiny)
operations on the data and a set of condition variables. Monitors can be imbedded in a programming
language thus mostly the compiler implements the monitors.

Typical implementation: each monitor has a lock. Acquire lock when begin a monitor operation, and
release lock when operation finishes.

The execution of a monitor obeys the following constrains:

i. Only one process can be active within a monitor at a time

ii. Procedure of a monitor can only access data local to the monitor, they cannot access an outside
variable
iii. The variables or data local to a monitor cannot be directly accessed from outside the monitor

Advantages:

i. Reduces probability of error, biases programmer to think about the system in a certain way

Disadvantages:

ii. Absence of concurrency: if a monitor encapsulate the source since only one process can be
active within a monitor at a time thus possibility of a deadlocks in case of nested monitors call

4. Deadlock

A deadlock is a situation in which two or more processes sharing the same resource are effectively
preventing each other from accessing the resource, resulting in those processes ceasing to function.

Resources come in two flavors/types

i. A preemptable resource is one that can be taken away from the process with no ill effects.
Memory is an example of a preemptable resource. On the other hand,
ii. A nonpreemptable resource is one that cannot be taken away from process (without causing ill
effect). For example, CD resources are not preemptable at an arbitrary moment.
Reallocating resources can resolve deadlocks that involve preemptable resources.

Page 27 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Page 28 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Conditions Necessary for a Deadlock

i. Mutual Exclusion Condition

The resources involved are non-shareable. At least one resource (thread) must be held in a non-
shareable mode, that is, only one process at a time claims exclusive control of the resource. If
another process requests that resource, the requesting process must be delayed until the
resource has been released

ii. Hold and Wait Condition

Requesting process hold already, resources while waiting for requested resources. There must
exist a process that is holding a resource already allocated to it while waiting for additional
resource that are currently being held by other processes.
iii. No-Preemptive Condition
Resources already allocated to a process cannot be preempted. Resources cannot be removed
from the processes are used to completion or released voluntarily by the process holding it.
iv. Circular Wait Condition

The processes in the system form a circular list or chain where each process in the list is waiting
for a resource held by the next process in the list.

As an example, consider the traffic deadlock in the following figure

Page 29 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Dealing with Deadlock Problem

In general, there are four strategies of dealing with deadlock problem:

i. The Ostrich Approach

Just ignore the deadlock problem altogether.
ii. Deadlock Detection and Recovery
Detect deadlock and, when it occurs, take steps to recover.
iii. Deadlock Avoidance
Avoid deadlock by careful resource scheduling.
iv. Deadlock Prevention
Prevent deadlock by resource scheduling so as to negate at least one of the four conditions.

Deadlock Prevention

Havender in his pioneering work showed that since all four of the conditions are necessary for deadlock
to occur, it follows that deadlock might be prevented by denying any one of the conditions.

 Elimination of “Mutual Exclusion” Condition

The mutual exclusion condition must hold for non-sharable resources. That is, several processes
cannot simultaneously share a single resource. This condition is difficult to eliminate because
some resources, such as the tap drive and printer, are inherently non-shareable. Note that
shareable resources like read-only-file do not require mutually exclusive access and thus cannot
be involved in deadlock.

 Elimination of “Hold and Wait” Condition

There are two possibilities for elimination of the second condition. The first alternative is that a
process request be granted all of the resources it needs at once, prior to execution. The second
alternative is to disallow a process from requesting resources whenever it has previously
allocated resources. This strategy requires that all of the resources a process will need must be
requested at once. The system must grant resources on “all or none” basis. If the complete set
of resources needed by a process is not currently available, then the process must wait until the
complete set is available. While the process waits, however, it may not hold any resources. Thus
the “wait for” condition is denied and deadlocks simply cannot occur. This strategy can lead to
serious waste of resources. For example, a program requiring ten tap drives must request and
receive all ten derives before it begins executing. If the program needs only one tap drive to
begin execution and then does not need the remaining tap drives for several hours. Then
substantial computer resources (9 tape drives) will sit idle for several hours. This strategy can
cause indefinite postponement (starvation). Since not all the required resources may become
available at once.

Page 30 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

 Elimination of “No-preemption” Condition

The nonpreemption condition can be alleviated by forcing a process waiting for a resource that
cannot immediately be allocated to relinquish all of its currently held resources, so that other
processes may use them to finish. Suppose a system does allow processes to hold resources
while requesting additional resources. Consider what happens when a request cannot be
satisfied. A process holds resources a second process may need in order to proceed while
second process may hold the resources needed by the first process. This is a deadlock. This
strategy require that when a process that is holding some resources is denied a request for
additional resources. The process must release its held resources and, if necessary, request
them again together with additional resources. Implementation of this strategy denies the “no-
preemptive” condition effectively.
High Cost When a process release resources the process may lose all its work to that point.
One serious consequence of this strategy is the possibility of indefinite postponement
(starvation). A process might be held off indefinitely as it repeatedly requests and releases the
same resources.

 Elimination of “Circular Wait” Condition

The last condition, the circular wait, can be denied by imposing a total ordering on all of the
resource types and then forcing, all processes to request the resources in order (increasing or
decreasing). This strategy impose a total ordering of all resources types, and to require that each
process requests resources in a numerical order (increasing or decreasing) of enumeration. With
this rule, the resource allocation graph can never have a cycle.
For example, provide a global numbering of all the resources, as shown

1 ≡ Card reader

2 ≡ Printer

3 ≡ Plotter

4 ≡ Tape drive

5 ≡ Card punch

Now the rule is this: processes can request resources whenever they want to, but all requests
must be made in numerical order. A process may request first printer and then a tape drive
(order: 2, 4), but it may not request first a plotter and then a printer (order: 3, 2). The problem
with this strategy is that it may be impossible to find an ordering that satisfies everyone.

Page 31 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Deadlock Avoidance
Either : Each process provides the maximum number of resources of each type it needs. With these
information, there are algorithms that can ensure the system will never enter a deadlock state. This is
deadlock avoidance.

A sequence of processes <P1, P2, …, Pn> is a safe sequence if for each process Pi in the sequence, its
resource requests can be satisfied by the remaining resources and the sum of all resources that are
being held by P1, P2, …, Pi-1. This means we can suspend Pi and run P1, P2, …, Pi-1 until they complete.
Then, Pi will have all resources to run.

A state is safe if the system can allocate resources to each process (up to its maximum, of course) in
some order and still avoid a deadlock. In other word, a state is safe if there is a safe sequence.
Otherwise, if no safe sequence exists, the system state is unsafe. An unsafe state is not necessarily a
deadlock state. On the other hand, a deadlock state is an unsafe state

A system has 12 tapes and three processes A, B, C. At time t0, we have:

Maximum need Current holding Will need

A 10 5 5
B 4 2 2
C 9 2 7

Then, <B, A, C> is a safe sequence (safe state). The system has 12-(5+2+2)=3 free tapes.

Since B needs 2 tapes, it can take 2, run, and return 4. Then, the system has (3-2)+4=5 tapes. A now can
take all 5 tapes and run. Finally, A returns 10 tapes for C to take 7 of them

A system has 12 tapes and three processes A, B, C. At time t1, C has one more tape:

Maximum need Current holding Will need

A 10 5 5
B 4 2 2
C 9 3 6

The system has 12-(5+2+3)=2 free tapes.

At this point, only B can take these 2 and run. It returns 4, making 4 free tapes available.

But, none of A and C can run, and a deadlock occurs.

The problem is due to granting C one more tape.

Page 32 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

OR

A deadlock avoidance algorithm ensures that the system is always in a safe state. Therefore, no
deadlock can occur. Resource requests are granted only if in doing so the system is still in a safe state.

Consequently, resource utilization may be lower than those systems without using a deadlock avoidance
algorithm.

Deadlock Detection

Deadlock detection is the process of actually determining that a deadlock exists and identifying the
processes and resources involved in the deadlock. The basic idea is to check allocation against resource
availability for all possible allocation sequences to determine if the system is in deadlocked state . Of
course, the deadlock detection algorithm is only half of this strategy. Once a deadlock is detected, there
needs to be a way to recover several alternatives exists:

 Temporarily prevent resources from deadlocked processes.

 Back off a process to some check point allowing preemption of a needed resource and restarting
the process at the checkpoint later.
 Successively kill processes until the system is deadlock free.

These methods are expensive in the sense that each iteration calls the detection algorithm until the
system proves to be deadlock free. The complexity of algorithm is O(N2) where N is the number of
proceeds. Another potential problem is starvation; same process killed repeatedly.

Page 33 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

PROCESS SCHEDULING

Introduction

In a multiprogramming computer, several processes will be competing for use of the processor. The OS
has the task of determining the optimum sequence and timing of assigning processes to the processor.
This activity is called scheduling.

The part of the OS that makes this decision (which process come first) is called the scheduler; the
algorithm it uses is called the scheduling algorithm

Scheduling is exercised at three distinct levels – High-level, Medium-level and Low-level.

i. High-level scheduling (Long-term or Job scheduling) deals with the decision as to whether to
admit another new job to the system.
ii. Medium-level scheduling (Intermediate scheduling) is concerned with the decision to
temporarily remove a process from the system (in order to reduce the system load) or to re-
introduce a process.
iii. Low-level scheduling (Short-term or Processor scheduling) handles the decision of which ready
process is to be assigned to the processor. This level is often called the dispatcher.

Objectives of Scheduling:

These objectives are in term of the system’s performance and behavior: the objectives are:

Page 34 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

i. Maximize the system throughput. The number of processes completed per time unit is
called throughput. Higher throughput means more jobs get done.
ii. Be ‘fair’ to all users. This does not mean all users to be treated equally, but consequently,
relative to the importance of the work being done.
iii. Provide tolerable response (for on-line users) or turn-around time (for batch users).
Minimize the time batch users must wait for output. (Turnaround time is the total time
taken between the submission of a program for execution and the return of the complete
output to the customer.)
iv. Degrade performance gracefully. If the system becomes overloaded, it should not
‘collapse’, but avoid further loading (e.g. by inhibiting any new jobs or users) and/or
temporarily reduce the launch of service (e.g. response time).
v. Be consistent and predictable. The response and turn-around time should be relatively
stable from day to day.
vi. Maximize efficiency/ CPU utilization: keep the CPU busy 100% of the time

A CPU scheduling algorithm should try to minimize the following:

i. Turnaround time
ii. Waiting time
iii. Response time Anonymous

Page 35 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

CPU Scheduling Criteria:

There are many scheduling algorithms and various criteria to judge their performance. Different
algorithms may favor different types of processes. Some criteria are as follows:

i. CPU utilization: CPU must be as busy as possible in performing different tasks. CPU utilization is
more important in real-time system and multi-programmed systems.
ii. Throughput: The number of processes executed in a specified time period is called throughput.
The throughput increases .for short processes. It decreases if the size of processes is huge.
iii. Turnaround Time: The amount of time that is needed to execute a process is called turnaround
time. It is the actual job time plus the waiting time.
iv. Waiting Time: The amount of time the process has waited is called waiting time. It is the
turnaround time minus actual job time.
v. Response Time: The amount of time between a request is Submitted and the first response is
produced is called response time.

N.B Priority: This is the value which can be assigned to each process and indicates the relative
‘importance’ of the process such that a high priority process will be selected for execution in preference
to a timer priority one.

Low-level Scheduling (LLS)

This is the most complex and significant of the scheduling levels. The HLS and MLS operate over time
scales of seconds or minutes, the LLS make critical decisions many times every second.

The LLS invoke whenever the current process relinquishes control, which, will occurs when the process
calls for an I/O transfer or some other interrupt occurs.

The following are policies used in Low-Level Scheduling:

i. Pre-emptic/ Non-pre-emptic policies.

In a pre-emptic scheme, the LLS may remove a process from the RUNNING state in order to allow
another process to run. In a non-preemptic scheme, a process, once given the processor, will be allowed
to run until it terminates or incurs an I/O wait, i.e., it cannot ‘forcibly’ lose the processor.

In a non-preemptic scheme the running process retains the processor until it ‘voluntarily’ gives it up; it is
not affected by external events.

A preemptic scheme will occur greater overheads since it will generate more context switches but is
often desirable in order to avoid one (possibly long) processes from monopolizing the processor and to
guarantee a reasonable level of service for all processes. A pre-emptic scheme is generally necessary in
an on-line environment and essential in a real-time one.

Page 36 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

ii. Cooperative Scheduling.

This is where the responsibility of releasing control is placed in the hands of the application programs
and is not managed by the OS. That is, each application, when executing and therefore holding the
processor is expected to periodically to relinquish control back to say the windows scheduler. This
operation is generally incorporated into the event processing loop of each application.

Disadvantage of cooperate scheduling: that the OS does not have overall control of the solution and it is
possible for an application to incur an error situation that prevents It from relinquishing the processor,
thereby, ‘freezing’ the whole computer.

Common Low-level scheduling algorithms (policies) are listed below:

1. Shortest Jobs First (SJF).

2. First-Come-First-Served (FCFS).
3. Round Robin (RR).
4. Shortest Remaining Time (SRT).
5. Highest Response Ratio Next (HRN).
6. Multi-level Feedback Queues (MFQ).

1. Shortest Job First (SJF) / Shortest Job Next.

This non-preemptic policy reverses the biases against short jobs found in FCFS scheme by selecting the
process from the READY queue which has the shortest estimated run time. A job of expected short
duration will jump the longer jobs in the queue. This is a priority scheme, where the priority is the
inverse of the estimated run time

Illustration of SJF Policy

This process appears to be more equitable with no process having a large wait to run-time ratio.

Page 37 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Problem with SJF policy

i. That a long job in the queue will be delayed indefinitely by a succession of smaller jobs arriving
in the queue.
ii. The scheduling sketched above assumes that the job list is constant however, in practice, before
process A is reached when process C is done, another job say length 9 minutes could arrive and
this be placed in front of A. Thus, this queue jumping could occur many times, effectively
preventing job A from starting at all. This situation is known as starving.
iii. SJF is more applicable to batch processing since it requires that an estimate of run-time be
available, which could be supplied in the JCL commands for the job.

2. First-Come-First-Served (FCFS)

Also known as FIFO (First In First Out). The process that requests the CPU first is allocated the CPU first.
This can easily be implemented using a queue. FCFS is not preemptive. Once a process has the CPU, it
will occupy the CPU until the process completes or voluntarily enters the wait state.

FCFS is a non-preemptic scheme, since it is activated only when the current process relinquishes control.
FCFS favors long jobs over short ones. E.g. if we assume the annual in the ready queue of four processes
in the sequence numbered, one can calculate how long each process has to wait.

FCFS Policy Illustration

Advantages of FCFS

i. It’s a fair scheme in that processes are served in the order of arrival

Page 38 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Disadvantages of FCFS

i. It is easy to have the convoy effect: all the processes wait for the one big process to get off the
CPU. CPU utilization may be low. Consider a CPU-bound process running with many I/O-bound
process
ii. It is in favor of long processes and may not be fair to those short ones. What if your 1-minute
job is behind a 10-hour job?
iii. It is troublesome for time-sharing systems, where each user needs to get a share of the CPU at
regular intervals.

FCFS is rarely used on its own but often used in conjunction with other methods.

3. Round-Robin (RR)

In the round-robin scheme, a process is selected for running from the READY queue in FIFO sequence.
However, if the process runs beyond a certain fixed length of time, called the time quantum, it is
interrupted and returned to the end of the READY queue. That is, each active process is a given a ‘time-
slice’ in rotation.

Round Robin Scheduling

The timing required by this scheme is obtained by using a hardware timer which generates an interrupt
at pre-set intervals. RR is effective in time-sharing environment, where it is desirable to provide an
acceptable response time for every user and where the processing demands of each user will often be
relatively low and sporadic.

The RR scheme is preemptive, but preemption occurs only by expiry of the time quantum.

Page 39 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

4. Priority Scheduling

Each process is assigned a priority and the process with the highest priority is allowed to run first. To
prevent high priority process from running indefinitely, the scheduler decreases the priority of the
current running process at each clock tick i.e. clock

Priority may be determined internally or externally:

 Internal priority: determined by time limits, memory requirement, # of files, and so on.
 External priority: not controlled by the OS (e.g., importance of the process)

The scheduler always picks the process (in ready queue) with the highest priority to run. FCFS and SJF
are special cases of priority scheduling.

Priority scheduling can be non-preemptive or preemptive. With preemptive priority scheduling, if the
newly arrived process has a higher priority than the running one, the latter is preempted. Indefinite
block (or starvation) may occur: a low priority process may never have a chance to run.

Aging is a technique to overcome the starvation problem. Aging: gradually increases the priority of
processes that wait in the system for a long time. Example: If 0 is the highest (resp., lowest) priority,
then we could decrease (resp., increase) the priority of a waiting process by 1 every fixed period (e.g.,
every minute).

Advantage

i. Effective in timesharing systems

Disadvantage

i. A high priority process may keep a lower priority process waiting indefinitely (starving)

5. Shortest Remaining Time (SRT)

SRT is a preemptive version of SJF. At the time of dispatching, the shortest queue process, say, job A,
will be started however, if during running of this process, another job arrives whose run-time is shorter
than job’s A remaining run-time, then job A will be preempted to allow the new job to start.

SRT favors shorter jobs even more than SJF since a currently running long job could be ousted by a new
shorter one.

The danger of starvation of long jobs still exists in this scheme. Implementation of SRT requires an
estimate of total run-time and measurements of elapsed run-time.

Page 40 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

6. Highest Response Ratio Next (HRN)

The scheme is designed from the SJF method, modified to reduce SJF’s bias against long jobs and to
avoid the danger of starvation.

HRN derives a dynamic priority values based in the estimated run-time and the incurred waiting time.
The priority for each process is calculated from the formula:

Priority, P = time waiting + run-time

Run-time

The process with the highest priority value will be selected for running. When processes first appear in
the ‘READY’ queue the ‘time waiting’ will be zero and thus P, will be equal to 1 for all processes.

After a short period of waiting, the shorter jobs will be favored e.g. consider jobs A and B with run times
of 10 and 50 minutes. After each has waited for 5 minutes, their priorities are:

5+ 10 5+50
A : P= =1. 5 B : P= =1 . 1
10 50

On this basis Job A with a higher priority will be selected.

Note: If A has first started (wait time = 0), job B could be chosen in preference to A. As time passes, the
wait time will become more significant. If B has been waiting for say 30 minutes then its priority would
be

30+50
B: P= =1. 6
50

In this technique a job cannot be starved since the effect of the wait time is the numerator of the
priority expression will predominate over short jobs with a smaller wait time.

7. Multiple queues

Mean to assign a large quantum once in a while rather than giving processes small quantum frequency
(to reduce swapping)

8. Guarantee scheduling

The system keeps track of how much CPU each process has had since its creation. If there are n users
logged in while working, then each user receives 1/n of the CPU power. The algorithm is used to run the
process with the lowest ratio between the actual time the CPU has entitled each process should run

Page 41 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

Page 42 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

9. Lottery scheduling

Processes are given lottery tickets for various system resources such as CPU time. Whenever a
scheduling decision has to be made, a lottery ticket is chosen at random and the process holding the
ticket gets the resource.

10. Real-Time Scheduling

A real time system is where one or more physical devices external to the computer generate stimuli and
the computer react appropriately to them within a fixed amount of time e.g. a computer gets bits from
the drive of a CD player and converts them into music within a very tight time interval

There are two types of real-time systems, hard and soft:

i. Hard Real Time:

Critical tasks must be completed within a guaranteed amount of time. The scheduler either
admits a process and guarantees that the process will complete on-time, or reject the request
(resource reservation). This is almost impossible if the system has secondary storage and virtual
memory because these subsystems can cause unavoidable delay. Hard real-time systems usually
have special software running on special hardware.
ii. Soft Real-Time
Critical tasks receive higher priority over other processes. It is easily doable within a general
system. It could cause long delay (starvation) for noncritical tasks. The CPU scheduler must
prevent aging to occur. Otherwise, critical tasks may have lower priority. Aging can be applied to
non-critical tasks. The dispatch latency must be small.

A program is divided into a number of processes. The external events that a real time system may have
to respond to may be categorized into

i. Periodic: occurring at regular interval

ii. Aperiodic: occurring unpredictably

The scheduler assigns to each process a priority proportional to the frequency of occurrence. Earliest
deadline first scheduling runs the first process on the list within the closest deadline

Page 43 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

11. Multilevel Queue Scheduling

A multilevel queue scheduling algorithm partitions the ready queue into a number of separate queues
(e.g., foreground and background). Each process is assigned permanently to one queue based on some
properties of the process (e.g., memory usage, priority, process type)

Each queue has its own scheduling algorithm (e.g., RR for foreground and FCFS for background). A
priority is assigned to each queue. A higher priority process may preempt a lower priority process.

A process P can run only if all queues above the queue

that contains P are empty. When a process is running and
a process in a higher priority queue comes in, the running
process is preempted.

12. Multilevel Queue with Feedback

Multilevel queue with feedback scheduling is similar to multilevel queue; however, it allows processes to
move between queues. If a process uses more (less) CPU time, it is moved to a queue of lower (higher)
priority. As a result, I/O-bound (CPU-bound) processes will be in higher (lower) priority queues

Processes in queue i have time quantum 2i. When a process’

behavior changes, it may be placed (i.e., promoted or demoted)
into a difference queue. Thus, when an I/O-bound (resp., CPU-
bound) process starts to use more CPU (more I/O), it may be
demoted (promoted) to a lower (resp., higher) queue.

NB: CPU-bound and I/O-bound

A process is CPU-bound if it generates I/O requests infrequently, using

more of its time doing computation.

A process is I/O-bound if it spends more of its time to do I/O than it

spends doing computation. A CPU-bound process might have a few very
long CPU bursts. An I/O-bound process typically has many short CPU
bursts.

Page 44 of 45 By J. K
 DICT Module 1 Operating System
September 15, 2017

13. Two level scheduling

All run-able are in main memory. If the memory is insufficient, some of the run-able processes are kept
on the disk in whole or in part.

Duties/objectives of high level scheduling / process scheduling

i. Introduction of new processes

In batch systems jobs waiting execution are stored in a job pool held in secondary memory. The
choice of which job to start next depends on the resources that each job requires
ii. Assignment of processes
The order in which processes are run either by order of processor queue or by the order in
which the dispatcher selects processes from the queue
iii. Implementation of resource allocation policies
The policies implied here are those concerned with deadlock avoidance and system balance .i.e.
ensuring that no resource is either over or under committed.
NB: since the behavior of the system is largely determined by the activity of the scheduler it is
important that the scheduler should have a high priority relative to other processes. Locations
on which the scheduler might be activated are:
 A resource is requested (implement resources allocation policy to avoid deadlock)
 A resource is released
 A process is terminated
 A new job arrives in the job pool

When the scheduler has finished its work it suspends itself by executing a wait operation on
semaphore. This semaphore is signaled whenever a scheduling event occurs. However in an OS
which neither prevents or avoid deadlock its possible no scheduling event does in fact occurs

Page 45 of 45 By J. K