1

BCA6B12- Operating Systems

Course Number: 31

Contact Hours per Week: 5 (4T + 1L)

Number of Credits: 3
Number of Contact Hours: 80 Hrs.

Course Evaluation: Internal – 15 Marks + External – 60 Marks

Objectives
● To learn objectives & functions of Operating Systems.
● To understand processes and its life cycle.
● To learn and understand various Memory and Scheduling Algorithms.
● To have an overall idea about the latest developments in Operating Systems

Prerequisites

● Knowledge in Data structures.

Course Outcomes
● CO1 To understand the objectives, functions and types of Operating System
● CO2 To have a basic knowledge about process, Threads, Deadlock
● CO3 To understand the knowledge of Linux shell programming
● CO4 To learn about CPU scheduling and memory management
Course Outline
Unit I [12T + 4P]

Operating System - Objectives and functions - The Evolution of Operating Systems: Serial Processing,
Simple batch Systems, Multi Programmed batch Systems, Time Sharing Systems, Parallel Systems,
Distributed Systems, Real time systems. Definition of Process, Process States, Process Control Block,
Operations on Process, Process Communication, Communication in Client server System, Basic concepts
of threads, Concurrency, Principles of Concurrency, Mutual exclusion, Semaphores, Messages, Dead lock:
Prevention, Detection, Avoidance.

Unit II [13T + 3P]

Linux Shell Programming: Introduction – Shells available in Unix: Bourne shell (sh), C shell (csh), TC shell
(tcsh), Korn shell (ksh), Bourne Again SHell (bash). Bash: special characters – getting help – man pages –
Linux Directory Layout – Command for Navigating the Linux Filesystems: pwd, cd, ls, file, cat, cp, mv,
mkdir, rmdir, whereis – Piping and Redirection - Informational Commands: ps, w, id, free – clear, echo,
more. File permissions – Setting Permissions – Making a file executable. Creating shell programs:
comments, variables, operators (arithmetic, relational, logical) – single and double quotes - read – echo –
test - conditional commands, iterative commands – break – continue - evaluating expressions using expr, bc
– strings – grep – arrays.
 2
Unit III [13T + 3P]

CPU Scheduling: Scheduling Criteria, Scheduling algorithms: FCFS, SJF, Priority, RR, Multilevel,
Feedback Queue - Process synchronization, The Critical Section Problem, Synchronization Hardware,
Classical Problems of Synchronization: Reader Writer, Dining Philosopher. File and Database System, File
System, Functions of organization, Allocation and Free Space Management.

Unit IV [13T + 3P]

Memory Management, Address Binding, Logical Vs Physical Address Space, Dynamic Loading, Dynamic
Linking and Shared Libraries, Overlays, Swapping, Contiguous Memory allocation, Paging, Segmentation,
Virtual memory, Demand Paging, Page Replacement, Thrashing.

Unit V [13 T + 3 P]
Protection and security: policy and mechanism, authentication, authorization. Mobile OS: Concepts, history,
features, architecture, future scope. Case studies: Android, UNIX kernel and Microsoft Windows NT
(concepts only).

Text Books

1. Silberschatz, Galvin and Gagne, Operating System Concepts, John Willey & Sons
2. William Stallings, Operating Systems, Internals and Design Principles, PHI
3. Mendel Cooper, Advanced Bash-Scripting Guide, Available at
[Link]

Reference Book:
1. Nutt G.J, Operating Systems: A Modern Perspective, Addison Wesley
 3
MODULE I
OPERATING SYSTEM - INTRODUCTION
The Operating System is a program with the following features −
● An operating system is a program that acts as an interface between the software and the computer
hardware.
● It is an integrated set of specialized programs used to manage overall resources and operations of
the computer.
● It is a specialized software that controls and monitors the execution of all other programs that
reside in the computer, including application programs and other system software.
OBJECTIVES
The objectives of the operating system are −
● To make the computer system convenient to use in an efficient manner.
● To hide the details of the hardware resources from the users.
● To provide users a convenient interface to use the computer system.
● To act as an intermediary between the hardware and its users, making it easier for the users to
access and use other resources.
● To manage the resources of a computer system.
● To keep track of who is using which resource, granting resource requests, and mediating
conflicting requests from different programs and users.
● To provide efficient and fair sharing of resources among users and programs.
FUNCTIONS OF OPERATING SYSTEMS
Following are some of important functions of an operating System.
1. Memory Management
2. Processor Management
3. Device Management
4. File Management
5. Security
6. Control over system performance
7. Job accounting
8. Error detecting aids
9. Coordination between other software and users
1. Memory Management
Memory management refers to management of Primary Memory or Main Memory. Main memory is a
large array of words or bytes where each word or byte has its own address. Main memory provides a
fast storage that can be accessed directly by the CPU. For a program to be executed, it must in the main
memory. An Operating System does the following activities for memory management. The operating
system manages the Primary Memory or Main Memory. Main memory is made up of a large array of
bytes or words where each byte or word is assigned a certain address. Main memory is a fast storage
and it can be accessed directly by the CPU. For a program to be executed, it should be first loaded in
the main memory.
An Operating System performs the following activities for memory management:
It keeps tracks of primary memory, i.e., which bytes of memory are used by which user program. The
memory addresses that have already been allocated and the memory addresses of the memory that has
not yet been used. In multi programming, the OS decides the order in which process are granted access
to memory, and for how long. It allocates the memory to a process when the process requests it and
deallocates the memory when the process has terminated or is performing an I/O operation.
● Keeps tracks of primary memory, i.e., what part of it are in use by whom, what part is not in
use?
● In multiprogramming, the OS decides which process will get memory when and how
much.
● Allocates the memory when a process requests it to do so.
 4
● De-allocates the memory when a process no longer needs it or has been exterminated.
2. Processor Management
In multiprogramming environment, the OS decides which process gets the processor when and for
how much time. This function is called process scheduling. An Operating System does the following
activities for processor management. In a multi programming environment, the OS decides the order
in which processes have access to the processor, and how much processing time each process has.
This function of OS is called process scheduling. An Operating System performs the following
activities for processor management.
It keeps tracks of the status of processes. The program which performs this task is known as traffic
controller. Allocates the CPU that is processor to a process. De-allocates processor when a process is
no more required.
● Keeps tracks of processor and status of process. The program responsible for this task is known
as traffic controller.
● Allocates the processor (CPU) to a process.
● De-allocates processor when a process is no longer required.
3. Device Management
An Operating System manages device communication via their respective drivers. An OS manages
device communication via their respective drivers. It performs the following activities for device
management. Keeps tracks of all devices connected to system. Designates a program responsible for
every device known as the Input/Output controller. Decides which process gets access to a certain
device and for how long. Allocates devices in an effective and efficient way. Deallocates devices when
they are no longer required. It does the following activities for device management:
● Keeps tracks of all devices. Program responsible for this task is known as the I/O controller.
● Decides which process gets the device when and for how much time.
● Allocates the device in the efficient way.
● De-allocates devices.
4. File Management
A file system is normally organized into directories for easy navigation and usage. These directories
may contain files and other directions. A file system is organized into directories for efficient or easy
navigation and usage. These directories may contain other directories and other files. An Operating
System carries out the following file management activities. It keeps track of where information is
stored, user access settings and status of every file and more… These facilities are collectively known
as the file system.
Moreover, Operating System also provides certain services to the computer system in one form or the
other.
An Operating System does the following activities for file management.
● Keeps track of information, location, uses, status etc. The collective facilities are often known
as file system.
● Decides who gets the resources.
● Allocates the resources.
● De-allocates the resources.
5. Security
By means of password and similar other techniques, it prevents unauthorized access to programs and
data. The operating system uses password protection to protect user data and similar other techniques.
It also prevents unauthorized access to programs and user data.
6. Control over system performance
Recording delays between request for a service and response from the system. It monitors overall
system health to help improve performance records the response time between service requests and
system response to have a complete view of the system health. This can help improve performance
by providing important information needed to troubleshoot problems.
7. Job accounting
Keeping track of time and resources used by various jobs and users. Operating system keeps track of
 5
time and resources used by various tasks and users, this information can be used to track resource
usage for a particular user or group of user.
8. Error detecting aids
Production of dumps, traces, error messages, and other debugging and error detecting aids. Operating
system constantly monitors the system to detect errors and avoid the malfunctioning of computer
system.
9. Coordination between other soft wares and users
Coordination and assignment of compilers, interpreters, assemblers and other software to the various
users of the computer systems. Operating systems also coordinate and assign interpreters, compilers,
assemblers and other software to the various users of the computer systems.

THE EVOLUTION OF OPERATING SYSTEMS

The First Generation (1945-1955): The earliest electronic digital computers of 1940's had no
operating systems. All programming was done in machine language. 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. During this generation computers were generally used to solve simple math
calculations, operating systems were not necessarily needed.
The Second Generation (1955-1965). The General Motors Research Laboratories implemented the
first operating systems, called GMOS, in early 1950's for their IBM 701. The system of the 50's
generally ran one job at a time. These were called single-stream batch processing systems because
programs and data were submitted in groups or batches. These new machines were called
mainframes, and they were used by professional operators in large computer rooms.
The Third Generation (1965-1980): 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 with the introduction of multiprogramming and time-sharing techniques.
The Fourth Generation (1980-Present Day): The fourth generation of operating systems saw the
creation of personal computing. An interesting development that began taking place during the mid-
1980s is the growth of networks of personal computers running Network Operating Systems and
Distributed Operating Systems. In a Network Operating System, the users are aware of the existence
of multiple computers and can log on to remote machines and copy files from one machine to
another. Each machine runs its own local operating system and has its own local user (or users).
Basically, the machines are independent of one another.
 6
TYPES OF OPERATING SYSTEM
1. Serial Processing System
⮚ The Serial Processing Operating Systems are those which Performs all the instructions in a
Sequence Manner
⮚ The Instructions those are given by the user will be executed by using the FIFO Manner means
First in First Out.
⮚ For Running the Instructions the Program Counter is used. Program Counter will determines
which instruction is going to Execute and which instruction will be Execute after this.
⮚ All the Jobs are firstly Prepared and Stored on the Card and after that card will be entered in the
System. But the Main Problem is that a user doesn’t interact with the System while he is working
on the System, means the user can’t be able to enter the data for Execution.

2. Simple Batch Processing System

⮚ In the Batch Processing Similar Types of jobs are Firstly Prepared and they are Stored as a batch
on the Card.
⮚ The batches will be Submit to the System for the Processing. The System then Perform all the
Instructions one by one.
⮚ User can’t be Able to specify any input, operating System wills increments its Program Counter
for Executing the Next Instruction.
⮚ It can handle huge amount of data
⮚ Batch processing systems work anywhere, any time. That means they continue to work outside
regular business hours in an offline background (eg: Payroll preparation).
⮚ The Main Problem is that the Jobs those are prepared for Execution must be the Same Type and
if a job requires for any type of Input then this will not be Possible for the user.
⮚ Many Time will be wasted for Preparing the Batch

3. Multiprogrammed Batch Processing System

⮚ In simple batch processing system there will be wastage of time when we are preparing the batch
and the CPU will remain idle at that Time.
⮚ But With the help of Multi programming we can Execute Multiple Programs on the System at a
Time and the CPU will never get idle.
⮚ When we are Working with a Program then we can also Submit the Second or Another Program
for Running.
⮚ In this we can also specify our Input, that is, a user can also interact with the System.
⮚ The Operating System also uses the Process of Allocation and De-allocation of the Memory. That
is OS will provide the Memory Space to all the Running and all the Waiting Processes. There
must be the Proper Management of all the Running Jobs.
 7

[Link]. Simple Batched Systems Multi-programmed Batched Systems

1 In this system, processes are processed In this system, multiple processes can be
one after another executed at a time.

As one process gets processed at a time, Processes are executed in a parallel fashion,
2
it performs low. thus it is faster.

3 CPU remains in idle states for long

CPU do not need to remain in idle state.
times.

4 Example: CP/M, MS DOS, PC DOS

Example: Windows 95, MaxOS etc.
etc.

4. Time sharing systems

⮚ Time sharing refers to the allocation of computer resources in time slots to several programs
simultaneously.
⮚ For example a mainframe computer that has many users logged on to it. Each user uses the
resources such as memory, CPU etc. The users feel that they are exclusive user of the CPU, even
though this is not possible with one CPU i.e. shared among different users.
⮚ The time sharing system provides the direct access to a large number of users where CPU time is
divided among all the users on scheduled basis.
⮚ The OS allocates a set of time to each user. When this time is expired, it passes control to the next
user on the system. The time allowed is extremely small and the users are given the impression
that they each have their own CPU and they are the sole owner of the CPU.
⮚ In time-shared systems multiple processes are managed simultaneously which requires an
adequate management of main memory so that the processes can be swapped in or swapped out
within a short time.

5. Parallel systems
⮚ These are used to interface multiple networked computers to complete tasks in parallel.
⮚ Parallel operating systems are able to use software to manage all of the different resources of the
computers running in parallel, such as memory, caches, storage space, and processing power.
⮚ A parallel operating system works by dividing sets of calculations into smaller parts and
distributing them between the machines on a network.
⮚ To facilitate communication between the processor cores and memory arrays, routing software
has to either share its memory by assigning the same address space to all of the networked
computers, or distribute its memory by assigning a different address space to each processing
core.
⮚ Sharing memory allows the operatingsystem to run very quickly, but it is not efficient. The
distribution may slow the operatingsystem, but it is often more flexible and efficient.

6. Distributed Systems
⮚ Distributed Means Data is Stored and Processed on Multiple Locations.
⮚ If we want to Take Some Data from other Computer, Then we uses the Distributed Processing
System. We can Insert and Remove the Data from one Location to another Location.
 8
⮚ A distributed operating system is an extension of the network operating system that supports
higher levels of communication and integration of the machines on the network.
⮚ These systems are referred as loosely coupled systems where each processor has its own local
memory and each processors communicate with one another through various communication
lines, such as high speed buses or telephone lines.
⮚ By loosely coupled systems, we mean that such computers are connected by external interfaces
that run under the control of software.
⮚ The Distributed OS involves a collection of autonomous computer systems, capable of
communicating and cooperating with each other through a LAN / WAN.
⮚ The users of a true distributed system should not know, on which machine their programs are
running and where their files are stored.
7. Real Time System
⮚ In this Response Time is already fixed. Means time to Display the Results after Possessing
has fixed by the Processor or CPU.
⮚ Real Time System is used at those Places in which we Requires Timely Response. So when
we specify the Request, the CPU will perform it at that Time.
⮚ These Types of Systems are used in Reservation, control machinery, scientific applications
etc.
⮚ There are two Types of Real Time System.
Real time system is defined as a system in which job has deadline, job has to be finished by
the deadline (strictly finished). If a result is delayed, huge loss may happen.

o Hard Real Time System: In the Hard Real Time System, Time is fixed and we can’t
Change any Moments of the Time of Processing. Means CPU will Process the data as
we Enters the Data.
Hard real time is a system whose operation is incorrect whose result is not produce
according to time constraint.
For example,

1. Air Traffic Control

2. Medical System

o Soft Real Time System: In the Soft Real Time System, some Moments can be Change.
Means after giving the Command to the CPU, CPU Performs the Operation after a
Microsecond.
Soft real time system is a system whose operation is degrades if results are not produce
according to the specified timing requirement.
For example

1. Multimedia Transmission and Reception

2. Computer Games
 9
Difference between Multiprogramming and Time sharing systems

Multiprogramming OS Timesharing OS
Allows several programs to use the CPU at Supports interactive users and
the same time and do not support provides a quick response time
user interaction
Maximize the CPU utilization by Minimize the response time by
organizing programs such that the CPU sharing the computing resources
has always one to execute among several users
A context switch occurs only when A context switch occurs each time
the currently running process blocked after the time slice expired
and the CPU is to be allocated to some
other process
Less complex than time sharing systems More complex than multi
programming system

DEFINITION OF PROCESS
A program in Execution is called process. A process is an instance of a computer program that is
being executed. It contains the program code and its current activity. Depending on the operating
system (OS), a process may be made up of multiple threads of execution that execute instructions
concurrently. A program is a passive entity while a process is an active entity.

PROCESS STATES
As a process executes, it changes state
⮚ New: The process is being created
⮚ Running: Instructions are being executed
⮚ Waiting: The process is waiting for some event to occur
⮚ Ready: The process is waiting to be assigned to a processor
⮚ Terminated: The process has finished execution
Only one process is running and all other processes are in ready or waiting.
 10
State Transitions:
1. New→Ready : Takes place if a new process has been loaded into the main memory and it is waiting
for the CPU to be allocated to it.
2. Ready→ Running : Takes place if the CPU has been allocated to a ready process and it has started
its execution
3. Running→ Ready: Occurs if
● Time slice has expired
● Higher priority process gets ready for execution
4. Running→ Waiting : Takes place if the currently running process :
● Needs to perform I/O operation
● Has to wait for a message from another process
● Requests for some other process
5. Running→Terminated: Occurs when currently running process:
● Has completed its task and rtequests to os for its termination
● Terminated by its parent
● Terminated by the kernel
6. Waiting→Ready : Occurs if an event for which the process was waiting has occurred.

PROCESS CONTROL BLOCK

PCB is a data structure in the operating system kernel containing the information needed
to manage a particular process. The PCB is a certain store that allows the operating systems to locate key
information about a process. Thus, the PCB is the data structure that defines a process to the operating
systems.

The PCB contains important information about the specific process including
⮚ Process State: The current state of the process i.e., whether it is ready, running, waiting, or
whatever.
⮚ Process Number: Unique identification of the process in order to track "which is which"
information.
⮚ Program Counter: This register stores the next instruction to be executed.
⮚ CPU Registers: MAR, MBR, PC, IR, GPR
⮚ Memory limits: process stored location in memory
⮚ List of files:
⮚ The priority of process
⮚ A pointer to parent process.
⮚ A pointer to child process (if it exists).

OPERATIONS ON PROCESS
1. Process creation: A user requests and already running process can creates new processes.
Parent process creates children processes using a system call, which, in turn create other
processes, forming a tree ofprocesses.
2. Process preempting: A process preempted if I/O event or timeout occurs. Then process moves
from running state to ready state and CPU loads another process from ready state to running
state, if available.
3. Process blocking: When a process needs I/O event during its execution, then process moves
from running state to waiting state and dispatches another process toCPU.
4. Process termination: A process terminated if when a process completes its execution. Also,
these events: OS, Hardware interrupt, and Software interrupt can cause termination of a
process.
 11
Process Creation
Process ceation is a task of creating new processes. There are different situations in which a new process
is created. There are different ways to create new process. A new process can be created at the time of
initialization of operating system or when system calls such as fork () are initiated by other processes.
The process, which creates a new process using system calls, is called parent process while the new
process that is created is called child process. The child processes can create new processes using system
calls. A new process can also create by an operating system based on the request received from theuser.
The process creation is very common in running computer system because corresponding to every task
that is performed there is a process associated with it. For instance, a new process is created every time
a user logs on to a computer system, an application program such a MS Word is initiated, or when a
document printed.
Process Preemption
Tasks are usually assigned with priorities. At times it is necessary to run a certain task that has a higher
priority before another task although it is running. Therefore, the running task is interrupted for some
time and resumed later when the priority task has finished its execution. This is called preemption.
Process Blocking
A blocking process is usually waiting for an event such as a semaphore being released or a message
arriving in its message queue. In multitasking systems, such processes are expected to notify the
scheduler with a system call that it is to wait, so that they can be removed from the active scheduling
queue until the event occurs. A process that continues to run while waiting (i.e., continuously polling for
the event in a tight loop) is said to be busy-waiting, which is undesirable as it wastes clock cycles which
could be used for other processes.
Process Termination
Process termination is an operation in which a process is terminated after the execution of its last
instruction. This operation is used to terminate or end any process. When a process is terminated, the
resources that were being utilized by the process are released by the operating system. When a child
process terminates, it sends the status information back to the parent process before terminating. The
child process can also be terminated by the parent process if the task performed by the child process is
no longer needed. In addition, when a parent process terminates, it has to terminate the child process as
well became a child process cannot run when its parent process has been terminated. The termination of
a process when all its instruction has been executed successfully is called normal termination. However,
there are instances when a process terminates due to some error. This termination is called as abnormal
termination of a process.
PROCESS COMMUNICATION
Inter-process communication (IPC) is a set of programming interfaces that allows a programmer to
coordinate activities among different program processes that can run concurrently in an operating system.
This allows a program to handle many user requests at the same time. Since even a single user request
may result in multiple processes running in the operating system on the user's behalf, the processes need
to communicate with each other. The IPC interfaces make this possible. Each IPC method has its own
advantages and limitations so it is not unusual for a single program to use all of the IPC methods. A
mechanism through which data is shared among the process in the system is referred to as Inter-process
communication. Multiple processes communicate with each other to share data and resources. A set of
functions is required for the communication of process with each other. In multiprogramming systems,
some common storage is used where process can share data. The shared storage may be the main memory
or it may be a shared file. Files are the most commonly used mechanism for data sharing between
processes. One process can write in the file while another process cam read the data for the same file.
Various techniques can be used to implement the Inter- Process Communication. There are two
fundamental models of Inter- Process communication that are commonly used, these are:
1. Shared Memory Model
2. Message Passing Model
 12
Shared Memory Model
In shared memory model. The co operating process shares a region of memory for sharing of
information. Some operating systems use the supervisor call to create a share memory space. Similarly,
Some operating system use file system to create RAM disk, which is a virtual disk created in the RAM.
The shared files are stored in RAM disk to share the information between processes. The shared files in
RAM disk are actually stored in the memory. The Process can share information by writing and reading
data to the shared memory location or RAM disk.
Message Passing Model
In this model, data is shared between process by passing and receiving messages between co-
operating process. Message passing mechanism is easier to implement than shared memory but it is
useful for exchanging smaller amount of data.
In message passing mechanism data is exchange between processes through kernel of operating system
using system calls. Message passing mechanism is particularly useful in a distributed environment where
the communicating processes may reside on different components connected by the network. For
example, A data program used on the internet could be designed so that chat participants communicate
with each other by exchanging messages. It must be noted that passing message technique is slower than
shared memory technique.
A message contains the following information:
⮚ Header of message that identifies the sending and receiving processes.
⮚ Block of data
⮚ Pointer to block of data
⮚ Some control information about the process
Typically Inter-Process Communication is based on the ports associated with process. A port represents
a queue of processes. Ports are controlled and managed by the kernel. The processes communicate with
each other through kernel. In message passing mechanism, two operations are performed. These are
sending message and receiving message. The function send () and receive() are used to implement these
operations. Suppose P1 and P2 want to communicate with each other. A communication link must be
created between them to send and receive messages. The communication link can be created using
different ways. The most important methods are:
⮚ Direct model
⮚ Indirect model

COMMUNICATION IN CLIENT SERVER SYSTEM

Client-server concept underpins distributed systems over a couple of decades. There are two counterparts
in the concept: a client and a server. In practice there are often multiple clients and single server.
Clients start communication by sending requests to the server; the server handles them and usually returns
responses back. Client processes often do not live long, while server process, which is sometimes called
daemon, live till OS shutdown.
Sockets
IPC with sockets is very common in distributed systems. In nutshell, a socket is a pair of an IP address
and a port number. For two processes to communicate, each of them needs a socket. When server daemon
is running on a host, it is listening to its port and handles all requests sent by clients to the port on the
host (server socket). A client must know IP and port of the server (server socket) to send a request to it.
Client's port is often provided by OS kernel when client starts communication with the server and is freed
when communication [Link] communication using sockets is common and efficient, it is
considered low level, because sockets only allow to transfer unstructured stream of bytes between
processes. It is up to client and server applications to impose a structure on the data passed as byte stream.
 13
Remote Procedure Calls
RPC is a higher level communication method. It was designed to mimic procedure call mechanism, but
execute it over network. RPC is conceptually similar to message passing IPC and is usually built on top
of socket communication. In contrast to IPC messages, RPC messages are well structured. Each message
includes information about function to be executed and the parameters to be passed to that function.
When the function is executed, a response with output is sent back to the requester in a separate message.
RPC hides the details of communication by providing a stub on the client side. When client needs to
invoke a remote procedure, it invokes the stub and pass it the parameters. The stub marshals the
parameters and sends a message to RPC daemon running on the server. RPC daemon (a similar stub on
the server side) receives the message and invokes the procedure on the server. Return values are passed
back to the client using the same technique.
Pipes
Pipe is one of the oldest and simplest IPC methods that appeared in early UNIX systems. A pipe is an
IPC abstraction with two endpoints, similar to a physical pipe. Usually one process puts data to one end
of the pipe and another process consumes them from the other one.
Ordinary pipes
Ordinary pipes are unidirectional, i.e. allow only one-way communication. They implement standard
producer-consumer mechanism, where one process writes to the pipe and another one reads from it. For
two-way communication two pipes are needed. Ordinary pipes require a parent–child relationship
between communicating processes, because a pipe can only be accessed from process that created or
inherited it. Parent process creates a pipe and uses it to communicate with a child created via fork(). Once
communication is over and processes terminated, the ordinary pipe ceases to exist.
Named pipes
Named pipes are more powerful. They do not require parent– child relationship and can be bidirectional.
Once a named pipe is created, multiple non related processes can communicate over it. Named pipe
continues to exist after communicating processes have terminated. It must be explicitly deleted when not
required any more.

BASIC CONCEPTS OF THREADS

A thread is a flow of execution through the process code, with its own program counter that keeps track
of which instruction to execute next, system registers which hold its current working variables, and a
stack which contains the execution history. A thread shares with its peer threads few information like
code segment, data segment and open files. When one thread alters a code segment memory item, all
other threads see that.
A thread is also called a lightweight process. Threads provide a way to improve application performance
through parallelism. Threads represent a software approach to improving performance of operating
system by reducing the overhead thread is equivalent to a classical process. Each thread belongs to
exactly one process and no thread can exist outside a process. Each thread represents a separate flow of
control. Threads have been successfully used in implementing network servers and web server. They
also provide a suitable foundation for parallel execution of applications on shared memory
multiprocessors.
 14

Difference between Process and Thread

[Link] Process Thread

.
1 Process is heavy weight or resource Thread is light weight, taking lesser resources
intensive than a process.
2 Process switching needs interaction Thread switching does not need to interact with
with operating system. operating system.

3 In multiple processing environments, All threads can share same set of open files, child
each process executes the same code but has processes.
its
own memory and file resources.
4 If one process is blocked, then no other While one thread is blocked and
process can execute until the first process is waiting, a second thread in thesame
unblocked. task can run.
5 Multiple processes without using threads Multiple threaded processes use few resources.
use more resources.
6 In multiple processes each One thread can read, write or change another
process operates independentlyof thread's data.
the others.
 15
Advantages of Thread
⮚ Threads minimize the context switching time.
⮚ Use of threads provides concurrency within a process.
⮚ Efficient communication.
⮚ It is more economical to create and context switch threads.
⮚ Threads allow utilization of multiprocess or architectures to a greater scale and efficiency.

Types of Thread
Threads are implemented in following two ways −
1. User Level Threads −User managed threads.
2. Kernel Level Threads−Operating System managed threads acting on kernel, an operating
system core.

User Level Threads

In this case, the thread management kernel is not aware of the existence of threads. The thread library
contains code for creating and destroying threads, for passing message and data between threads, for
scheduling thread execution and for saving and restoring thread contexts. The application starts with a
single thread.
Advantages
⮚ Thread switching does not require Kernel mode privileges.
⮚ User level thread can run on any operating system.
⮚ Scheduling can be application specific in the user level thread.
⮚ User level threads are fast to create and manage.
Disadvantages
⮚ In a typical operating system, most system calls are blocking.
⮚ Multithreaded application cannot take advantage of multiprocessing.

Kernel Level Threads

In this case, thread management is done by the Kernel. There is no thread management code in the
application area. Kernel threads are supported directly by the operating system. Any application can be
programmed to be multithreaded. All of the threads within an application are supported within a single
process. The Kernel maintains context information for the process as a whole and for individual threads
within the process. Scheduling by the Kernel is done on a thread basis. The Kernel performs thread
creation, scheduling and management in Kernel space. Kernel threads are generally slower to create and
manage than the user threads.
Advantages
⮚ Kernel can simultaneously schedule multiple threads from the same process on multiple
processes.
⮚ If one thread in a process is blocked, the Kernel can schedule another thread of the same
process.
⮚ Kernel routines themselves can be multithreaded.
Disadvantages
⮚ Kernel threads are generally slower to create and manage than the user threads.
⮚ Transfer of control from one thread to another within the same process requires a mode switch
to the Kernel.
Multithreading Models
Some operating system provides a combined user level thread and Kernel level thread facility. Solaris is
a good example of this combined approach. In a combined system, multiple threads within the same
 16
application can run in parallel on multiple processors and a blocking system call need not block the entire
process. Multithreading models are three types:
⮚ Many to many relationship.
⮚ Many to one relationship.
⮚ One to one relationship.

Many to Many Model

The many-to-many model multiplexes any number of user threads onto an equal or smaller
number of kernel threads.
The following diagram shows the many-to-many threading model where 6 user level threads are
multiplexing with 6 kernel level threads. In this model, developers can create as many user threads as
necessary and the corresponding Kernel threads can run in parallel on a multiprocessor machine. This
model provides the best accuracy on concurrency and when a thread performs a blocking system call,
the kernel can schedule another thread for execution.

Many to One Model

Many-to-one model maps many user level threads to one Kernel-level thread. Thread
management is done in user space by the thread library. When thread makes a blocking system call,
the entire process will be blocked. Only one thread can access the Kernel at a time, so multiple threads
are unable to run in parallel on multiprocessors. If the user- level thread libraries are implemented in
the operating system in such a way that the system does not support them, then the Kernel threads use
the many-to-one relationship modes.

One to One Model

There is one-to-one relationship of user-level thread to the kernel-level thread. This
model provides more concurrency than the many-to-one model. It also allows another thread to run
when a thread makes a blocking system call. It supports multiple threads to execute in parallel on
microprocessors. Disadvantage of this model is that creating user thread requires the corresponding
Kernel thread. OS/2, Windows NT and windows 2000 use one to one relationship model.
 17

Difference between User-Level & Kernel-Level Thread

[Link]. User-Level Threads Kernel-Level Thread

1 User-level threads are faster Kernel-level threads are slower
to create and manage. to create and manage.
2 Implementation is by a thread Operating system supports
library at the user level. creation of Kernel threads.

3 User-level thread is generic Kernel-level thread is specific to the

and can run on any operating system.
Operating system.
4 Multi-threaded applications Kernel routines themselves can be
cannot take advantage of multithreaded.
Multiprocessing.

CONCURRENCY
Concurrent processing is a computing model in which multiple processors execute instructions
simultaneously for better performance. Concurrent means something that happens at the same time as
something else. Tasks are broken down into subtasks that are then assigned to separate processors to
perform simultaneously. Concurrent processing is sometimes said to be synonymous with parallel
processing.
Concurrency is the tendency for things to happen at the same time in a system. Concurrency is a natural
phenomenon, of course. In the real world, at any given time, many things are happening simultaneously.
When we design software to monitor and control real- world systems, we must deal with this natural
concurrency. When dealing with concurrency issues in software systems, there are generally two aspects
that are important: being able to detect and respond to external events occurring in a random order, and
ensuring that these events are responded to in some minimum required interval. Concurrency cannot be
avoided because:
⮚ Users are concurrent-a person can handle several tasks at once and expects the same from a
computer.
⮚ Multiprocessors are becoming more prevalent.
⮚ The Internet is perhaps a huge multiprocessor.
⮚ A distributed system (client/server system) is naturally concurrent.
⮚ A windowing system is naturally concurrent.
I/O is often slow because it involves slow devices such as disks, printers; many network operations are
essentially (slow) I/O operations. When doing I/O it is helpful to handle the I/O concurrently with other
 18
work. Whenever concurrency is involved certain issues, discussed below, arise. An understanding of
these issues is important when:
⮚ Writing an operating system.
⮚ When interacting with the kernel, for example, when performing I/O.
⮚ When generating multiple processes, for example, with forks and pipelines.
⮚ When using multiple threads.
Concurrency issues:
⮚ Atomic. An operation is atomic if the steps are done as a unit. Operations that are not atomic,
but interruptible and done by multiple processes can cause problems. For example, a seek
followed by a write is not atomic. A process is likely to lose its time quantum between the seek
(a slow operation if the distance seeked is large!) and the write. If another process has the file
open and does a write then the result is not what is intended.
⮚ Race conditions. A race condition occurs if the outcome depends on which of several
processes gets to a point first. For example, fork( ) can generate a race condition if the result
depends on whether the parent or the child process runs first. Other race conditions can occur
if two processes are updating a global variable.
⮚ Blocking and starvation. While neither of these problems is unique to concurrent processes,
their effects must be carefully considered. Processes can block waiting for resources. A process
could be blocked for a long period of time waiting for input from a terminal. If the process is
required to periodically update some data, this would be very undesirable. Starvation occurs
when a process does not obtain sufficient CPU time to make meaningful progress.
⮚ Deadlock. Deadlock occurs when two processes are blocked in such a way that neither can
proceed. The typical occurrence is where two processes need two non-shareable resources to
proceed but one process has acquired one resource and the other has acquired the other
resource. Acquiring resources in a specific order can resolve some deadlocks.
PRINCIPLES OF CONCURRENCY
Concurrency is the tendency for things to happen at the same time in a system. It also refers to techniques
that make program more usable. Concurrency can be implemented and is used a lot on single processing
units, nonetheless it may benefit from multiple processing units with respect to speed. If an operating
system is called a multi-tasking operating system, this is a synonym for supporting concurrency. If we
can load multiple documents simultaneously in the tabs of our browser and we can still open menus and
perform more actions, this is concurrency. If we run distributed-net computations in the background, that
is concurrency.
MUTUAL EXCLUSION AND CRITICAL SECTION
Consider a system consisting of n processes {P0, P1, …, Pn-1}. Each process has a segment of code,
called a critical section, in which the process may be changing common variables, updating a table,
writing a file, and so on. When one process is executing in its critical section, no other process is to be
allowed to execute in its critical section. Thus, the execution of critical sections by the processes is
mutually exclusive in time. Each process must request permission to enter its critical section. The section
of code implementing this request is the entry section. The critical section may be followed by an exit
section. The remaining code is the remainder section. A picture showing general structure of a process
Pi.
 19
A solution to the critical-section problem must satisfy the following three requirements:
⮚ Mutual Exclusion: If process Pi is executing in its critical section, then no other processes can
be executing in their critical sections.
⮚ Progress: If no process is executing in its critical section and some processes wish to enter
their critical sections, then only those processes that are not executing in their remainder section
can participate in the decision on which will enter its critical section next, and this selection
cannot be postponed indefinitely.
⮚ Bounded Waiting: There exists a bound on the number of times that other processes are
allowed to enter their critical sections after a process has made a request to enter its critical
section and before that request is granted.
SEMAPHORE
To generalize to more complex problems the solutions to the critical-section problem are not easy. To
overcome this difficulty, we can use a synchronization tool called a semaphore. A semaphore S is an
integer variable that, apart from initialization, is accessed only through two standard atomic operations:
wait and signal. These operations were originally termed P (for wait, to test) and V (for signal, to
increment). The classical definition of wait in pseudo code is:
Wait(S) {
while (S < 0)// no-op
s--;
}
The classical definitions of signal in pseudo code are:
Signal (S) {
S++;
}
Modifications to the integer value of the semaphore in the wait and signal operations must be executed
indivisibly. That is, when one process modifies the semaphore value, no other process can simultaneously
modify that same semaphore value. In addition, in the case of the wait (S), the testing of the integer value
of S (S <0), and its possible modification (S--), must also be executed without interruption.

DEAD LOCK
In a multiprogramming environment, several processes may compete for a finite number of resources. A
process requests resources if the resources are not available at that time, and the process enters a wait
state. Waiting processes may never again change state, because the resources they have requested are
held by other waiting processes. This situation is called a deadlock.
Necessary Conditions for Deadlock
A deadlock situation can arise if the following four conditions hold simultaneously in a system:
⮚ Mutual exclusion: At least one resource must be held in a non- sharable mode; that is, only
one process at a time can use the resource. If another process requests that resource, the
requesting process must be delayed until the resource has been released.
⮚ Hold and wait: A process must be holding at least one resource and waiting to acquire
additional resources that are currently being held by other processes.
⮚ No preemption: Resources cannot be preempted; that is, resources can be released only
voluntarily by the process holding it, after that process has completed its task.
⮚ Circular wait: A set {P0, P1, ..., Pn) of waiting processes must exist such that P0 is waiting
for a resource that is held by PI, PI is waiting for a resource that is held by P2, ..., Pn-1 is
waiting for a resource that is held by P,, and P, is waiting for a resource that is held byP0.

Resource-Allocation Graph (RAG)

Deadlocks can be described more precisely in terms of a directed graph called a system resource-
allocation graph. This graph consists of a set of vertices V and a set of edges E. The set of vertices V
 20
is partitioned into two different types of nodes P = {P1, P2, ...,Pn}, the set consisting of all the active
processes in the system, and R = {R1, R2, ..., Rm), the set consisting of all resource types in the system.

The sets P, R, and E:

P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1 R1, P2 R3, R1 P2, R2 P2, R2 P1, R3P3}
if a resource-allocation graph does not have a cycle, then the system is not in a deadlock state. On the
other hand, if there is a cycle, then the system may or may not be in a deadlock state.
HANDLING DEADLOCK
We can deal with the deadlock problem in one of three ways:
⮚ We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter
a deadlock state.
⮚ We can allow the system to enter a deadlock state, detect it, and recover.
⮚ We can ignore the problem altogether, and pretend that deadlocks never occur in the system.
This solution is used by most operating systems, including UNIX.
DEAD LOCK PREVENTION
Prevent deadlocks by restraining how requests can be made. For a deadlock to occur, each of the four
necessary conditions must hold. By ensuring that at least one of these conditions cannot hold, we can
prevent the occurrence of a deadlock.
Mutual Exclusion
The mutual-exclusion condition must hold for non-sharable resources. For example, a printer cannot be
simultaneously shared by several processes. Sharable resources, do not require mutually exclusive
access, and thus cannot be involved in a deadlock. Read-only files are a good example of a sharable
resource. If several processes attempt to open a read-only file at the same time, they can be granted
simultaneous access to the file. A process never needs to wait for a sharable resource. In general,
however, we cannot prevent deadlocks by denying the mutual-exclusion condition: Some resources are
intrinsically non-sharable.
Hold and Wait
To ensure that the hold-and-wait condition never occurs in the system, we must guarantee that, whenever
a process requests a resource, it does not hold any other resources. One protocol that can be used requires
each process to request and be allocated all its resources before it begins execution.
An alternative protocol allows a process to request resources only when the process has none. A process
may request some resources and use them. Before it can request any additional resources, however, it
must release all the resources that it is currently allocated.
No Preemption
The third necessary condition is that there is no preemption of resources that have already been allocated.
If a process is holding some resources and requests another resource that cannot be immediately allocated
 21
to it (that is, the process must wait), then all resources currently being held are preempted. If a process
requests some resources, we first check whether they are available. If they are, we allocate them. If they
are not available, we check whether they are allocated to some other process that is waiting for additional
resources. If so, we preempt the desired resources from the waiting process and allocate them to the
requesting process.
Circular Wait
The fourth for deadlocks is the circular-wait condition. One way to ensure that this condition never holds
is to impose a total ordering of all resource types, and to require that each process requests resources in
an increasing order of enumeration. We can require that, whenever a process requests an instance of
resource type Rj, it has released any resources Ri such that F(Ri) →F(Rj). Possible side effects of
preventing deadlocks by this method, however, are low device utilization and reduced system throughput.
DEAD LOCK DETECTION
If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a
deadlock situation may occur. In this environment, the system must provide:
⮚ An algorithm that examines the state of the system to determine whether a deadlock has
occurred
⮚ An algorithm to recover from the deadlock
The deadlock detection methods are:
1. Single Instance of Each Resource Type
If all resources have only a single instance, then we can define a deadlock detection algorithm that uses
a variant of the resource-allocation graph, called a wait-for graph. We obtain this graph from the resource-
allocation graph by removing the nodes of type resource and collapsing the appropriate edges.
More clearly, an edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj
to release a resource that Pi needs. An edge Pi→Pj exists in a wait-for graph if and only if the
corresponding resource allocation graph contains two edges Pi →Rq and Rq→Pj for some resource Rq.
For example, in Figure
(a) Resource-allocation graph.
(b) Corresponding wait-for graph, we present a resource-allocation graph and the corresponding wait-
for graph. As before, a deadlock exists in the system if and only if the wait-for graph contains a
cycle. To detect deadlocks, the system needs to maintain the wait-for graph and periodically to
invoke an algorithm that searches for a cycle in the graph.

If deadlocks occur frequently, then the detection algorithm should be invoked frequently. Resources
allocated to deadlocked processes will be idle until the deadlock can be broken. In addition, the number
of processes involved in the deadlock cycle may grow. Deadlocks occur only when some process makes
a request that cannot be granted immediately.
 22
2. Multiple Instance of A Resource Type
When multiple instances of a resource type exist, the wait-for graph becomes inefficient. The data
structures used for the new algorithm are:
Available resources, A: A vector of size q stores information about the [Link] available resources of each
type.
Current allocation, C: A matrix of order p*q stores information about the [Link] resources allocated to
each process.
Request, Req: A matrix of order p*q stores information about the [Link] resources currently requested
by each process.
Algorithm:
1. Initialize Complete[i]=false for all i=1,2,3,…,p. It indicates that the ith process is still not
completed.
2. Search for I, such that Complete[i]=false and (Req<=A), that is, resources currently requested by
this process is less than the available resources. If no such process exists, then go to step 4.
3. Allocate the requested resources and let the process finish its execution. Set A=A+C and
Complete[i]=true for that process. Go to step 2.
4. If Complete[i]=false for some I, then the system is in deadlock.
DEAD LOCK AVOIDANCE
The method for avoiding deadlocks is to require additional information about how resources are to be
requested. Each process declares the maximum number of resources of each type that it may need.
Given a priori information about the maximum number of resources of each type that may be requested
for each process, it is possible to construct an algorithm that ensures that the system will never enter a
deadlock state. This algorithm defines the deadlock- avoidance approach.
A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that a
circular wait condition can never exist. The resource-allocation state is defined by the number of
available and allocated resources, and the maximum demands of the processes.
Safe State
A state is safe if the system can allocate resources to each process (up to its maximum) in some order
and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence.
The Safe, unsafe, and deadlock state spaces are shows in the figure. A safe state is not a deadlock state.
Conversely, a deadlock state is an unsafe state. Not all unsafe states are deadlocks. An unsafe state
may lead to a deadlock.
Resource-Allocation Graph Algorithm
If we have a resource-allocation system with only one instance of each resource type, a variant of the
resource-allocation graph defined in previous section can be used for deadlock avoidance. In addition
to the request and assignment edges, we introduce a new type of edge, called a claim edge. A claim
edge Pi→Rj indicates that process Pi may request resource Rj at some time in the future. This edge
resembles a request edge in direction.

But is represented by a dashed line. When process Pi requests resource Rj,the claim edge Pi→Rj is
converted to a request edge. Similarly, ource Rj iswhen released by Pi the assignment edge Rj→Pi
is cis onverted to a claim edge Pi → Rj. We note that the resources must be claimed a priori in the
 23
system. That is, before process Pi starts executing, all its claim edges must already appear in the
resource-allocation graph. We can relax this condition by allowing a claim edge Pi→Rj to be added
to the graph only if all the edges associated when process Pi are claim edges.
Suppose that process Pi requests resource Rj. The request can be granted only if converting the request
edge Pi→Rj to aaannassignment edge Rj→ Pi does not result in the formation of a cycle in the resource-
allocation graph. Note that we check for safety by using a cycle-detection algorithm. An algorithm for
detecting a cycle in this graph requires an order of n2 operations, where n is the number of processes in
the system.
If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is
found, then the allocation will put the system in an unsafe state. Therefore, process Pi will have to wait
for its requests to be satisfied.
Banker's Algorithm
The resource-allocation graph algorithm is not applicable to a resource allocation system with multiple
instances of each resource type. The next is applicable to such a system, but is less efficient than the
resource-allocation graph scheme. This algorithm is commonly known as the banker's algorithm. The
name was chosen because this algorithm could be used in a banking system to ensure that the bank never
allocates its available cash such that it can no longer satisfy the needs of all its customers.
When a new process enters the system, it must declare the maximum number of instances of each
resource type that it may need. This number may not exceed the total number of resources in the system.
When a user requests a set of resources, the system must determine whether the allocation of these
resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process
must wait until some other process releases enough resources.
We need the following data structures:
⮚ Available: A vector of length m indicates the number of available resources of each type. If
Available[j] = k, there are k instances of resource type Rjavailable.
⮚ Max: An n, x m matrix defines the maximum demand of each process. If Max[i,j] = k, then
process Pi may request at most k instances of resource typeRi.
⮚ Allocation: An n x m matrix defines the number of resources of each type currently allocated
to each process. If Allocation[i,j] = k, then process Pi is currently allocated k instances of
resource type Rj.
⮚ Need: An n x m matrix indicates the remaining resource need of each process. If Need[i,j] = k,
then process Pi may need k more instances of resource type Ri to complete its task. Note that
Need[i,j] = Max[i,j] -Allocafion[i,j].
Safety Algorithm
1. Let Work and Finish be vectors of length m and n,respectively.
Initialize Work:=Available and Finish[i] :=false for i = 1,2, ...,n.
2. Find an i such that both
a. Finish[i]=false
b. Needi=Work.
If no such i exists, go to step 4.
3. Work := Work +Allocation
Finish[i] := true go to step 2.
4. If Finish[i] = true for all i, then the system is in a safe state. This algorithm may require an
order of m x n2 operations to decide whether a state is safe.
Resource-Request Algorithm
Let Request i be the request vector for process Pi. If Request;[j] = k, then process Pi wants k instances
of resource type Rj. When a request for resources is made by process Pi, the following actions are
taken:
 24

1. If Request 5 Need i, go to step 2. Otherwise, raise an Error condition, since the

process has exceeded its maximum claim.
2. If Request 5 Available, go to step 3. Otherwise, Pi must wait, since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the
state as follows:
Available := Available - Request,;
Allocation i := Allocation; + Request;;
Need i := Need i – Request i;
If the resulting resource-allocation state is safe, the transaction is completed and process Pi is allocated
its resources. However, if the new state is unsafe, then Pi must wait for Requesti and the old resource-
allocation state is restored.
RECOVERY FROM DEADLOCK
When a detection algorithm determines that a deadlock exists, one possibility is to inform the operator
that a deadlock has occurred, and to let the operator deal with the deadlock manually. The other
possibility is to let the system recover from the deadlock automatically. There are two options for
breaking a deadlock. One solution is simply to abort one or more processes to break the circular wait.
The second option is to preempt some resources from one or more of the deadlocked processes.
Process Termination
To eliminate deadlocks by aborting a process, we use one of two methods. In both methods, the system
reclaims all resources allocated to the terminated processes.
⮚ Abort all deadlocked processes: This method clearly will break the deadlock cycle, but at a great
expense; these processes may have computed for a long time, and the results of these partial
computations must be discarded and probably recomputedlater.
⮚ Abort one process at a time until the deadlock cycle is eliminated: This method incurs considerable
overhead, since, after each process is aborted, a deadlock-detection algorithm must be invoked to
determine whether any processes are still deadlocked.
Resource Preemption
To eliminate deadlocks using resource pre-emption, we successively preempt some resources from
processes and give these resources to other processes until the deadlock cycle is broken. If pre-emption
is required to deal with deadlocks, then three issues need to be addressed:
⮚ Selecting a victim: Which resources and which processes are to be preempted? As in process
termination, we must determine the order of pre-emption to minimize cost. Cost factors may include
such parameters as the number of resources a deadlock process is holding, and the amount of time a
deadlocked process has thus far consumed during itsexecution.
⮚ Rollback: If we preempt a resource from a process, what should be done with that process? Clearly,
it cannot continue with its normal execution; it is missing some needed resource. We must roll back the
process to some safe state, and restart it from that state.
Since, in general, it is difficult to determine what a safe state is, the simplest solution is a total rollback:
Abort the process and then restart it. However, it is more effective to roll back the process only as far
as necessary to break the deadlock. On the other hand, this method requires the system to keep more
information about the state of all the running processes.
⮚ Starvation: How do we ensure that starvation will not occur? That is, how can we guarantee that
resources will not always be pre-empted from the same process?
In a system where victim selection is based primarily on cost factors, it may happen that the same process
is always picked as a victim. As a result, this process never completes its designated task, a starvation
situation that needs to be dealt with in any practical system. Clearly, we must ensure that a process can
be picked as a victim only a (small) finite number of times. The most common solution is to include the
number of rollbacks in the cost factor.

**********************