Operating System Components

From the virtual machine point of view (also resource management)

These components reflect the services made available by the O.S.
1. Process Management
o Process is a program in execution --- numerous processes to choose from
in a multiprogrammed system,
o Process creation/deletion (bookkeeping)
o Process suspension/resumption (scheduling, system vs. user)
o Process synchronization
o Process communication
o Deadlock handling
2. Memory Management
o Maintain bookkeeping information
o Map processes to memory locations
o Allocate/deallocate memory space as requested/required
2. I/O Device Management
o Disk management functions such as free space management, storage
allocation, fragmentation removal, head scheduling
o Consistent, convenient software to I/O device interface through
buffering/caching, custom drivers for each device.
3. File System
Built on top of disk management

o File creation/deletion.
o Support for hierarchical file systems
o Update/retrieval operations: read, write, append, seek
o Mapping of files to secondary storage
4. Protection
Controlling access to the system
o Resources --- CPU cycles, memory, files, devices
o Users --- authentication, communication
o Mechanisms, not policies
5. Network Management
Often built on top of file system
o TCP/IP, IPX, IPng
o Connection/Routing strategies
o ``Circuit'' management --- circuit, message, packet switching
o Communication mechanism
o Data/Process migration
6. Network Services (Distributed Computing)
Built on top of networking
o Email, messaging (GroupWise)
o FTP
o gopher, www

o Distributed file systems --- NFS, AFS, LAN Manager

o Name service --- DNS, YP, NIS
o Replication --- gossip, ISIS
o Security --- kerberos
7. User Interface
o Character-Oriented shell --- sh, csh, command.com ( User replaceable)
o GUI --- X, Windows 95
User interface. Almost all systems have a user interface
This interface can take several forms. One is a command-line interface which uses text
commands and a method for entering them (say, a program to allow entering and editing of
commands). Another is a batch interface, in which commands and directives to control those
commands are entered into files, and those files are executed. Most commonly/ a graphical
user interface (GUI) is used. Here, the interface is a window system with a pointing device to
direct choose from menus, and make selections and a keyboard to enter text. Some systems
provide two or all
three of these variations.
Program execution. The system must be able to load a program into memory and
to run that program. The program must be able to end its execution, either
normally or abnormally (indicating error).
operations. A running program may require which may involve a file or an
device. For specific devices, special functions may be desired (such as recording
to a CD or DVD drive or blanking a CRT screen). For efficiency and protection,
users usually cannot control devices directly. Therefore, the operating system
must provide a means to do
File-system manipulation. The file system is of particular interest. Obvi- ously,
programs need to read and write files and directories. They also need to
create and delete them by name, search for a given file, and list file information.
Finally, some programs include permissions management to allow or deny
access to files or directories based on file ownership.
Communications. There are many circumstances in which one process needs to
exchange information with another process. Such communication may occur
between processes that are executing on the same computer or between
processes that are executing on different computer systems tied together by a
computer network. Communications may be imple- mented via shared memory
or through passing, in which packets of information are moved between
processes by the operating system.
Error detection. The operating system needs to be constantly aware of possible
errors. Errors may occur in the CPU and memory hardware (such as a memory
error or a power failure), in devices (such as a parity error on tape, a connection
failure on a network, or lack of paper in the printer), and in the user program

(such as an arithmetic overflow, an attempt to access an illegal memory location,

or a too-great use of CPU time). For each type of error, the operating system
should take the appropriate action to ensure correct and consistent computing.
Debugging facilities can greatly enhance the user's and programmer's abilities to
use the system efficiently.
Another set of operating-system functions exists not for helping the user but rather for ensuring
the efficient operation of the system itself. Systems with multiple users can gain efficiency by
sharing the computer resources among the users.
Resource allocation. When there are multiple users or multiple jobs
running at the same time, resources must be allocated to each of them.
Many different types of resources are managed by the operating system.
Some (such as CPU cycles, main memory, and file storage) may have special
allocation code, whereas others (such as I/O devices) may have much more
general request and release code. For instance, in determining how best to
use the CPU, operating systems have CPU-scheduling routines that take into
account the speed of the CPU, the jobs that must be executed, the number of
registers available, and other factors. There may also be routines to allocate
printers, modems, USB storage drives, and other peripheral devices.
Accounting. We want to keep track of which users use how much and
what kinds of computer resources. This record keeping may be used for
accounting (so that users can be billed) or simply for accumulating usage
statistics. Usage statistics may be a valuable tool for researchers who wish
to reconfigiire the system to improve computing services.
Protection and security. The owners of information stored in a multiuser or
networked computer system may want to control use of that information.
When several separate processes execute concurrently, it should not be
possible for one process to interfere with the others or with the operating
system itself. Protection involves ensuring that all access to system
resources is controlled. Security of the system from outsiders is also
important. Such security starts with requiring each user to authenticate
himself or herself to the system, usually by means of a password, to gain
access to system resources. It extends to defending external I/O devices,
including modems and network adapters, from invalid access attempts
and to recording all such connections for detection of break-ins. If a system
is to be protected and secure, precautions must be instituted throughout
it. A chain is only as strong as its weakest link.

There are Many Operating Systems those have be Developed for Performing the
Operations those are requested by the user. There are Many Operating Systems which
have the Capability to Perform the Requests those are received from the System. The
Operating system can perform a Single Operation and also Multiple Operations at a
Time. So there are many types of Operating systems those are organized by using their
Working Techniques.
1) Serial Processing: The Serial Processing Operating Systems are those which
Performs all the instructions into a Sequence Manner or the Instructions those are

given by the user will be executed by using the FIFO Manner means First in First
Out. All the Instructions those are Entered First in the System will be Executed First and
the Instructions those are Entered Later Will be Executed Later. For Running the
Instructions the Program Counter is used which is used for Executing all
the Instructions.
In this the Program Counter will determines which instruction is going to Execute and
the which instruction will be Execute after this. Mainly thePunch Cards are used for
this. In this all the Jobs are firstly Prepared and Stored on the Card and after that
card will be entered in the System and after that all the Instructions will be executed one
by One. But the Main Problem is that a user doesnt interact with the
System while he is working on the System, means the user cant be able to enter the
data for Execution.
2) Batch Processing: The Batch Processing is same as the Serial Processing
Technique. But in the Batch Processing Similar Types of jobs are Firstly
Prepared and they are Stored on the Card. and that card will be Submit to the System
for the Processing. The System then Perform all the Operations on the Instructions one
by one. And a user cant be Able to specify any input. And Operating System wills
increments his Program Counter for Executing the Next Instruction.
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. And Many Time will be wasted for Preparing the Batch. The Batch Contains
the Jobs and all those jobs will be executed without the user Intervention.
And Operating System will use the LOAD and RUN Operation. This will first
LOAD the Job from the Card and after that he will execute the instructions.
By using the RUN Command.
The Speed of the Processing the Job will be Depend on the Jobs and the Results those
are produced by the System in difference of Time which is used for giving or submit the
Job and the Time which is used for Displaying the Results on the Screen.
3) Multi-Programming: As we know that in the Batch Processing System there are
multiple jobs Execute by the System. The System first prepare a batch and after that he
will Execute all the jobs those are Stored into the Batch. But the Main Problem is that if
a process or job requires an Input and Output Operation, then it is not possible and
second there will be the wastage of the 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 in the Multi-programming the CPU will never get idle,
because with the help of Multi-Programming we can Execute Many Programs on the
System and When we are Working with the Program then we can also Submit the

Second or Another Program for Running and the CPU will then Execute the Second
Program after the completion of the First Program. And in this we can also specify our
Input means a user can also interact with the System.
The Multi-programming Operating Systems never use any cards because the Process is
entered on the Spot by the user. But the Operating System also uses the Process
of Allocation and De-allocation of the Memory Means he 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.
4) Real Time System: There is also an Operating System which is known as Real Time
Processing 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 higher and Timely Response. These Types of
Systems are used in Reservation. So when we specify the Request, the CPU will perform
at that Time. There are two Types of Real Time System
1) Hard Real Time System: In the Hard Real Time System, Time is fixed and we
cant Change any Moments of the Time of Processing. Means CPU will Process the data
as we Enters the Data.
2) 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.
5) Distributed Operating System. - Distributed Means Data is Stored and Processed
on Multiple Locations. When a Data is stored on to the Multiple Computers, those are
placed in Different Locations. Distributed means In the Network, Network Collections of
Computers are connected with Each other.
Then if we want to Take Some Data From other Computer, Then we uses the Distributed
Processing System. And we can also Insert and Remove the Data from out Location to
another Location. In this Data is shared between many users. And we can also Access all
the Input and Output Devices are also accessed by Multiple Users.
6) Multiprocessing: Generally a Computer has a Single Processor means a Computer
have a just one CPU for Processing the instructions. But if we are Running multiple jobs,
then this will decrease the Speed of CPU. For Increasing the Speed of Processing then
we uses the Multiprocessing, in the Multi Processing there are two or More CPU in a
Single Operating System if one CPU will fail, then other CPU is used for providing
backup to the first CPU. With the help of Multi-processing, we can Execute Many Jobs
at a Time. All the Operations are divided into the Number of CPUs. if first CPU
Completed his Work before the Second CPU, then the Work of Second CPU will be
divided into the First and Second.

7) Parallel operating systems are

used
to interface
multiple
networked computers to complete tasks in parallel. The architecture of the
software is often a UNIX-based platform, which allows it to coordinate distributed
loads between multiple computers in a network. 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.
Parallel operating systems also allow a user to directly interface with all of the
computers in the network.
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 operating system to run very quickly, but it is usually not as
powerful. When using distributed shared memory, processors have access to both their
own local memory and the memory of other processors; this distribution may slow
the operating system, but it is often more flexible and efficient.

What is Process ? Explain Process Scheduling

A Single Process may also contain sub Processes those are also known as the Child
Process. So that we can say that a Process which is given to the System is also known as
the Parent Process and all the other Parts of the Single Process are known as the Child
Process. So that Every Process may also Contains Some Child process.
For Example if we are giving a Command to Print the File, and if a Single File Contains 8
pages to print. Then there are 8 small or child processes to print; and the Whole Process
will be over when all of the 8 pages will be printed.

When a user Request for a Service from the System, then the System Automatically
initializes the Process by using the initial State and the System also provides the various
types of input and output Resources to the Process, Provides also Some Memory and
also Control the Execution and Also Controls the State of the Process. So that in the
Execution of Process, we doesnt implement only the Process creation but we also use
the various Controlling Mechanism for the Process.

There are Many Types of Operating Systems which executed the Process either Single
or Multiple Processes are executed at a Single time. And For Executing the
Multiple Processes we must have to use Some Controlling Mechanisms.
Process Scheduling
As we know that we can perform many Programs at a Tim e on the Computer. But there
is a Single CPU. So for running all the Programs concurrently or simultaneously. Then
we use the Scheduling. Processes are the Small Programs those are executed by the user
according to their Request. CPU Executes all the Process according to Some Rules or
Some Schedule. Scheduling ist hat in which each process have Some Amount of Time of
CPU. Scheduling Provides Time of CPU to the Each Process.
There are Two Types of Scheduling

1) Preemptive: In this all the Processes are executed by using some Amount of Time
of CPU. The Time of CPU is divided into the Number of Minutes and Time of CPU
divided into the Process by using Some Rules. if the time is divided into equal interval
than it is called Quantum Time. in the Preemptive Scheduling
Jobs are Executed one by one according to the Scheduling Techniques, But in this when
the Higher Priority will Request for a Service. To the CPU, then CPU will transfer the
Control to the Request Job, Means the Running job will wait for Some Time.
2) NON-Primitive: In this No Time Scheduling is used and in this CPU will be
automatically free after Executing the Whole Process Means When the Execution of the
Process will Completed then the CPU will be Free. When two or more Process are given
then this will first Complete the Process and after Completing the First Process, this will
Automatically start the Second Process.
Non-Preemptive Scheduling means No scheduling then all the Jobs are
Executed One by One. And in this when the First Job will be Completed, after that
second Job will Started.
Preemptive Scheduling: We have various Techniques of Scheduling.
1) First Come First Serve: As the name Suggest, the Processes those are Coming
first, will be Executed first and Means CPU Will Creates a Queue, means all the Process
are Inserted into the Queue and the CPU will Perform all the Process by using their
Coming Order.. In this all the Process are arranged by the CPU and After Executing a

Single Process, then this will Automatically Execute second Process by Picking up the
next Process.
2) Shortest Job first: In this Scheduling, All the Process are Arranged into their Size
Means How Many Time a Process require, of CPU for Executing. CPU Arrange all the
Processes according to the Requirement Time. CPU Executes the Processes by
Examining the Time Required by Process. CPU Prepare a queue in which all the
Processes are arranged by using the Number of Time Units Requires by the Process.
For Example if we want to Print a Page and move a Mouse on the Screen. So that CPU
will first Move the Mouse on the Screen. Then after that he will print a Page. Because
Job of printing Require a Lots of Time and Moving a Mouse is just requires little Time of
CPU.
3) Priority Scheduling: When the Process are Given, then Each Process have a
Priority means Some Preference issue. Which Job will be executed first, is determined
by the CPU. After Examining the Priority of the CPU. Each Process takes different Time
of CPU and also the Number of Inputs those are needed by the CPU. So CPU Maintains
the Priority Level after Examining the Total time which a Process will consume. All the
Processes are Arranged by using Some Priority,. Then CPU Executes the Process by
using the Process Priority.
4) Round Robin: In this Scheduling the Time of CPU is divided into the Equal Parts
and Assign to various Processes. In this Time of CPU is also known as Quantum Time.
In the Round Robin, when the time of First Process has finished, then the CPU will
execute the Second Process. But there also be possibility that the Process doesnt End,
up to The Time. So that if process doesnt end at the End of Time. Then CPU uses the
Context Switching, Means CPU Record the State of Process. After executing the other
Processes, he will execute the First Process Again until the Process never ends.
5) Multilevel Queue Scheduling: In this The Time of CPU is divided by using Some
Process Categories. In this the Process those are executed on the Foreground or on the
Screen, have a higher Priority and the Process those are running in the Background to
fill the Request the user. When we Input the data into the Computer. Then the Data is
displayed on the Screen after Processing.

What is the difference between threads and processes?

The major differences between threads and processes are:
1.

Threads share the address space of the process that created it; processes have their
own address space.

2.

Threads have direct access to the data segment of its process; processes have their
own copy of the data segment of the parent process.

3.

Threads can directly communicate with other threads of its process; processes must
use interprocess communication to communicate with sibling processes.

4.

Threads have almost no overhead; processes have considerable overhead.

5.

New threads are easily created; new processes require duplication of the parent
process.

6.

Threads can exercise considerable control over threads of the same process;
processes can only exercise control over child processes.

7.

Changes to the main thread (cancellation, priority change, etc.) may affect the
behavior of the other threads of the process; changes to the parent process do not
affect child processes.

Types of Threads
There are two types of threads to be managed in a modern system: User threads
and kernel threads.
User threads are supported above the kernel, without kernel support. These are
the threads that application programmers would put into their programs.
Kernel threads are supported within the kernel of the OS itself. All modern
OSes support kernel level threads, allowing the kernel to perform multiple
simultaneous tasks and/or to service multiple kernel system calls
simultaneously.
In a specific implementation, the user threads must be mapped to kernel
threads, using one of the following strategies.

Process Synchronization
Process Synchronization means sharing system resources by processes in a such a way that,
Concurrent access to shared data is handled thereby minimizing the chance of inconsistent data.
Maintaining data consistency demands mechanisms to ensure synchronized execution of
cooperating processes.
Process Synchronization was introduced to handle problems that arose while multiple process
executions.

we used the producer-consumer cooperating processes:

Producer code from chapter 3:

item nextProduced;
while( true ) {
/* Produce an item and store it in nextProduced */
nextProduced = makeNewItem( . . . );
/* Wait for space to become available */
while( ( ( in + 1 ) % BUFFER_SIZE ) == out )
; /* Do nothing */
/* And then store the item and repeat the loop. */
buffer[ in ] = nextProduced;
in = ( in + 1 ) % BUFFER_SIZE;
}
Consumer code from chapter 3:
item nextConsumed;
while( true ) {
/* Wait for an item to become available */
while( in == out )
; /* Do nothing */
/* Get the next available item */
nextConsumed = buffer[ out ];
out = ( out + 1 ) % BUFFER_SIZE;
/* Consume the item in nextConsumed
( Do something with it ) */
}
The only problem with the above code is that the maximum
number of items which can be placed into the buffer is

BUFFER_SIZE - 1. One slot is unavailable because there always

has to be a gap between the producer and the consumer.
We could try to overcome this deficiency by introducing a
counter variable, as shown in the following code segments:

Unfortunately we have now introduced a new problem,

because both the producer and the consumer are adjusting the
value of the variable counter, which can lead to a condition
known as a race condition. In this condition a piece of code
may or may not work correctly, depending on which of two
simultaneous processes executes first, and more importantly if

one of the processes gets interrupted such that the other

process runs between important steps of the first process.
( Bank balance example discussed in class. )
The particular problem above comes from the producer
executing "counter++" at the same time the consumer is
executing "counter--". If one process gets part way through
making the update and then the other process butts in, the
value of counter can get left in an incorrect state.
But, you might say, "Each of those are single instructions - How
can they get interrupted halfway through?" The answer is that
although they are single instructions in C++, they are actually
three steps each at the hardware level: (1) Fetch counter from
memory into a register, (2) increment or decrement the
register, and (3) Store the new value of counter back to
memory. If the instructions from the two processes get
interleaved, there could be serious problems, such as
illustrated by the following:

 Exercise: What would be the resulting value of counter if the

order of statements T4 and T5 were reversed?
( What should the value of counter be after one producer and
one consumer, assuming the original value was 5? )
Note that race conditions are notoriously difficult to identify
and debug, because by their very nature they only occur on
rare occasions, and only when the timing is just exactly right.
( or wrong! :-) ) Race conditions are also very difficult to
reproduce. :-(
Obviously the solution is to only allow one process at a time to
manipulate the value "counter". This is a very common
occurrence among cooperating processes, so lets look at some
ways in which this is done, as well as some classic problems in
this area.

5.2 The Critical-Section Problem

The producer-consumer problem described above is a specific

example of a more general situation known as the critical
section problem. The general idea is that in a number of
cooperating processes, each has a critical section of code, with
the following conditions and terminologies:
o Only one process in the group can be allowed to execute
in their critical section at any one time. If one process is
already executing their critical section and another
process wishes to do so, then the second process must be
made to wait until the first process has completed their
critical section work.
o The code preceding the critical section, and which
controls access to the critical section, is termed the entry
section. It acts like a carefully controlled locking door.
o The code following the critical section is termed the exit
section. It generally releases the lock on someone else's
door, or at least lets the world know that they are no
longer in their critical section.
o The rest of the code not included in either the critical
section or the entry or exit sections is termed the
remainder section.

Figure 5.1 - General structure of a typical process Pi

A solution to the critical section problem must satisfy the
following three conditions:
1. Mutual Exclusion - Only one process at a time can be
executing in their critical section.
2. Progress - If no process is currently executing in their
critical section, and one or more processes want to
execute their critical section, then only the processes not
in their remainder sections can participate in the decision,
and the decision cannot be postponed indefinitely. ( I.e.
processes cannot be blocked forever waiting to get into
their critical sections. )
3. Bounded Waiting - There exists a limit as to how many
other processes can get into their critical sections after a
process requests entry into their critical section and
before that request is granted. ( I.e. a process requesting
entry into their critical section will get a turn eventually,
and there is a limit as to how many other processes get to
go first. )

 We assume that all processes proceed at a non-zero speed, but

no assumptions can be made regarding the relative speed of
one process versus another.
Kernel processes can also be subject to race conditions, which
can be especially problematic when updating commonly
shared kernel data structures such as open file tables or virtual
memory management. Accordingly kernels can take on one of
two forms:
1. Non-preemptive kernels do not allow processes to be
interrupted while in kernel mode. This eliminates the
possibility of kernel-mode race conditions, but requires
kernel mode operations to complete very quickly, and can
be problematic for real-time systems, because timing
cannot be guaranteed.
2. Preemptive kernels allow for real-time operations, but
must be carefully written to avoid race conditions. This
can be especially tricky on SMP systems, in which
multiple kernel processes may be running simultaneously
on different processors.
o Non-preemptive kernels include Windows XP, 2000,
traditional UNIX, and Linux prior to 2.6; Preemptive
kernels include Linux 2.6 and later, and some commercial
UNIXes such as Solaris and IRIX.
5.3 Peterson's Solution

Peterson's Solution is a classic software-based solution to the

critical section problem. It is unfortunately not guaranteed to
work on modern hardware, due to vagaries of load and store
operations, but it illustrates a number of important concepts.
Peterson's solution is based on two processes, P0 and P1,
which alternate between their critical sections and remainder
sections. For convenience of discussion, "this" process is Pi,
and the "other" process is Pj. ( I.e. j = 1 - i )
Peterson's solution requires two shared data items:

o int turn - Indicates whose turn it is to enter into the

critical section. If turn = = i, then process i is allowed into
their critical section.
o boolean flag[ 2 ] - Indicates when a process wants
to enter into their critical section. When process i wants
to enter their critical section, it sets flag[ i ] to true.
In the following diagram, the entry and exit sections are
enclosed in boxes.
o In the entry section, process i first raises a flag indicating
a desire to enter the critical section.
o Then turn is set to j to allow the other process to enter
their critical section if process j so desires.
o The while loop is a busy loop ( notice the semicolon at the
end ), which makes process i wait as long as process j has
the turn and wants to enter the critical section.
o Process i lowers the flag[ i ] in the exit section, allowing
process j to continue if it has been waiting.

Figure 5.2 - The structure of process Pi in Peterson's solution.

Criteria for valid solution for process synchronization

To prove that the solution is correct, we must examine the
three conditions listed above:
1. Mutual exclusion - If one process is executing their
critical section when the other wishes to do so, the
second process will become blocked by the flag of the
first process. If both processes attempt to enter at the
same time, the last process to execute "turn = j" will be
blocked.
2. Progress - Each process can only be blocked at the while
if the other process wants to use the critical section ( flag[
j ] = = true ), AND it is the other process's turn to use the
critical section ( turn = = j ). If both of those conditions
are true, then the other process ( j ) will be allowed to
enter the critical section, and upon exiting the critical
section, will set flag[ j ] to false, releasing process i. The
shared variable turn assures that only one process at a

time can be blocked, and the flag variable allows one

process to release the other when exiting their critical
section.
3. Bounded Waiting - As each process enters their entry
section, they set the turn variable to be the other
processes turn. Since no process ever sets it back to their
own turn, this ensures that each process will have to let
the other process go first at most one time before it
becomes their turn again.
Note that the instruction "turn = j" is atomic, that is it is a
single machine instruction which cannot be interrupted.

Mutual exclusion by Test and Set Lock (TSL) instruction: TSL instruction is used for reading
from a location or writing to a location in the memory and then saving a non zero value at an
address in memory. It is implemented in the hardware and is used in a system with multiple
processors. When one processor is accessing the memory, no other processor can access the
same memory location until TSL instruction is finished. Locking of the memory bus in this way is
done in the hardware.

What is spin lock?

- In a loop a thread waits simply ('spins') checks repeatedly until the lock becomes available.
- This type of lock is a spin lock. The lock is a kind of busy waiting, as the threads remains
active by not performing a useful task.
- The spin locks are to release explicitly, although some locks are released automatically
when the tread blocks.
- They are efficient as they are blocked only for a short periods.
- They can be wasteful if they are held for a longer duration.

- By implementing the spin locks correctly as they offer challenges as the programmers
must take into account the possibility of simultaneous access to the lock, which could cause
race conditions.

Semaphores

A more robust alternative to simple mutexes is to

use semaphores, which are integer variables for which only
two ( atomic ) operations are defined, the wait and signal
operations, as shown in the following figure.
Note that not only must the variable-changing steps ( S-- and
S++ ) be indivisible, it is also necessary that for the wait
operation when the test proves false that there be no
interruptions before S gets decremented. It IS okay, however,
for the busy loop to be interrupted when the test is true, which
prevents the system from hanging forever.

Dead-Lock

is occurred in multiple users Computing Environment. As we know

that there is Many Number of users those are going to perform their Transactions.
Dead-Lock has occurred when two or More Users are requesting for data item or for a

Resource of System for example two or more users Request for the Printers at a Same
Time and When Dead-Lock has occurred.
All the users will be on Wait State Means, No user can get the resource of the System. Or
Dead-Lock is occurred when two or More Requests are waiting for Some Operation
Which is not possible. There is also Some Situation When the Problem of Dead Lock has
occurred. There are Following Conditions

for a Deadlock has Occur:-

1) Circular Wait:- When two or More Requests are Waiting For a Long Period of
Time and no one can Access the Resource from the System Resources , Then this is
called as Circular Wait For Example if two or more users Request for a Printer, at a
Same Time , they Request to Print a Page. Then they will be on the Circular Wait. Means
System Will Display Busy Sign of Sign.
2) Partial Allocation: - After Processing the Request, if a user doesnt leave the
Resource of the System, then we cant use the Resource of the System. Then in this
Situation when the other users, Request for the Resource then the other users, will also
be on the Waiting State. Then this will create the Deadlock.
3) Mutual Exclusive:- When a Single Process is used by two or more Processes,
Means a Single Resource if used for performing the two or more activities as a Shared
Based. But this is will Also Create a Problem because when a Second user Request for
the System Resource which is being used by the user.
4) HOLD and Wait:- A Single Process may need two or more System Resources.
And suppose if a Process have a Single Resource, and he is waiting the Second Resource.
Then Process cant Leave the first Resource and waiting for the Second Resource. So
that there will also be the Condition of Deadlock.

5) No Preemption:- if there is no Rule to use the System Resources. Means if all the
System Resources are not allocated in the Manner of Scheduling. Then this will also
create a Problem for a Deadlock because there is no surety that a Process will Release
the System Resources after the Completion. So Preemption and Transaction
Rollback prevents Deadlock situation.
For Avoiding a Dead Lock First of all we have to detect Dead-Lock Means
Firstly we have to detect why and how a Deadlock has occurred and Then Avoid or Solve
the Problems those are Occurred due to Occurrence of Deadlock.

Deadlocks

References:

1. Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin,

"Operating System Concepts, Ninth Edition ", Chapter 7

7.1 System Model

For the purposes of deadlock discussion, a system can be

modeled as a collection of limited resources, which can be
partitioned into different categories, to be allocated to a
number of processes, each having different needs.
Resource categories may include memory, printers, CPUs, open
files, tape drives, CD-ROMS, etc.
By definition, all the resources within a category are
equivalent, and a request of this category can be equally
satisfied by any one of the resources in that category. If this is
not the case ( i.e. if there is some difference between the
resources within a category ), then that category needs to be
further divided into separate categories. For example,
"printers" may need to be separated into "laser printers" and
"color inkjet printers".
Some categories may have a single resource.
In normal operation a process must request a resource before
using it, and release it when it is done, in the following
sequence:
1. Request - If the request cannot be immediately granted,
then the process must wait until the resource(s) it needs
become available. For example the system calls open( ),
malloc( ), new( ), and request( ).
2. Use - The process uses the resource, e.g. prints to the
printer or reads from the file.
3. Release - The process relinquishes the resource. so that it
becomes available for other processes. For example,
close( ), free( ), delete( ), and release( ).
For all kernel-managed resources, the kernel keeps track of
what resources are free and which are allocated, to which
process they are allocated, and a queue of processes waiting
for this resource to become available. Application-managed

resources can be controlled using mutexes or wait( ) and

signal( ) calls, ( i.e. binary or counting semaphores. )
A set of processes is deadlocked when every process in the set
is waiting for a resource that is currently allocated to another
process in the set ( and which can only be released when that
other waiting process makes progress. )
7.2 Deadlock Characterization

7.2.1 Necessary Conditions

There are four conditions that are necessary to achieve

deadlock:
1. Mutual Exclusion - At least one resource must be held in
a non-sharable mode; If any other process requests this
resource, then that process must wait for the resource to
be released.
2. Hold and Wait - A process must be simultaneously
holding at least one resource and waiting for at least one
resource that is currently being held by some other
process.
3. No preemption - Once a process is holding a resource
( i.e. once its request has been granted ), then that
resource cannot be taken away from that process until
the process voluntarily releases it.
4. Circular Wait - A set of processes { P0, P1, P2, . . ., PN }
must exist such that every P[ i ] is waiting for P[ ( i + 1 )
% ( N + 1 ) ]. ( Note that this condition implies the holdand-wait condition, but it is easier to deal with the
conditions if the four are considered separately. )
7.2.2 Resource-Allocation Graph

In some cases deadlocks can be understood more clearly

through the use of Resource-Allocation Graphs, having the
following properties:
o A set of resource categories, { R1, R2, R3, . . ., RN },
which appear as square nodes on the graph. Dots inside
the resource nodes indicate specific instances of the
resource. ( E.g. two dots might represent two laser
printers. )
o A set of processes, { P1, P2, P3, . . ., PN }

o Request Edges - A set of directed arcs from Pi to Rj,

indicating that process Pi has requested Rj, and is
currently waiting for that resource to become available.
o Assignment Edges - A set of directed arcs from Rj to Pi
indicating that resource Rj has been allocated to process
Pi, and that Pi is currently holding resource Rj.
o Note that a request edge can be converted into
an assignment edge by reversing the direction of the
arc when the request is granted. ( However note also that
request edges point to the category box, whereas
assignment edges emanate from a particular instance dot
within the box. )
o For example:

Figure 7.1 - Resource allocation graph

If a resource-allocation graph contains no cycles, then the
system is not deadlocked. ( When looking for cycles, remember
that these are directed graphs. ) See the example in Figure
7.2 above.

 If a resource-allocation graph does contain cycles AND each

resource category contains only a single instance, then a
deadlock exists.
If a resource category contains more than one instance, then
the presence of a cycle in the resource-allocation graph
indicates the possibility of a deadlock, but does not guarantee
one. Consider, for example, Figures 7.3 and 7.4 below:

Figure 7.2 - Resource allocation graph with a deadlock

Figure 7.3 - Resource allocation graph with a cycle but no deadlock

7.3 Methods for Handling Deadlocks

Generally speaking there are three ways of handling deadlocks:

1. Deadlock prevention or avoidance - Do not allow the
system to get into a deadlocked state.
2. Deadlock detection and recovery - Abort a process or
preempt some resources when deadlocks are detected.
3. Ignore the problem all together - If deadlocks only occur
once a year or so, it may be better to simply let them
happen and reboot as necessary than to incur the
constant overhead and system performance penalties
associated with deadlock prevention or detection. This is
the approach that both Windows and UNIX take.
In order to avoid deadlocks, the system must have additional
information about all processes. In particular, the system must
know what resources a process will or may request in the
future. ( Ranging from a simple worst-case maximum to a
complete resource request and release plan for each process,
depending on the particular algorithm. )

 Deadlock detection is fairly straightforward, but deadlock

recovery requires either aborting processes or preempting
resources, neither of which is an attractive alternative.
If deadlocks are neither prevented nor detected, then when a
deadlock occurs the system will gradually slow down, as more
and more processes become stuck waiting for resources
currently held by the deadlock and by other waiting processes.
Unfortunately this slowdown can be indistinguishable from a
general system slowdown when a real-time process has heavy
computing needs.
7.4 Deadlock Prevention

Deadlocks can be prevented by preventing at least one of the

four required conditions:
7.4.1 Mutual Exclusion

Shared resources such as read-only files do not lead to

deadlocks.
Unfortunately some resources, such as printers and tape
drives, require exclusive access by a single process.
7.4.2 Hold and Wait

To prevent this condition processes must be prevented from

holding one or more resources while simultaneously waiting for
one or more others. There are several possibilities for this:
o Require that all processes request all resources at one
time. This can be wasteful of system resources if a
process needs one resource early in its execution and
doesn't need some other resource until much later.
o Require that processes holding resources must release
them before requesting new resources, and then reacquire the released resources along with the new ones in
a single new request. This can be a problem if a process

has partially completed an operation using a resource and

then fails to get it re-allocated after releasing it.
o Either of the methods described above can lead to
starvation if a process requires one or more popular
resources.
7.4.3 No Preemption

Preemption of process resource allocations can prevent this

condition of deadlocks, when it is possible.
o One approach is that if a process is forced to wait when
requesting a new resource, then all other resources
previously held by this process are implicitly released,
( preempted ), forcing this process to re-acquire the old
resources along with the new resources in a single
request, similar to the previous discussion.
o Another approach is that when a resource is requested
and not available, then the system looks to see what
other processes currently have those resources and are
themselves blocked waiting for some other resource. If
such a process is found, then some of their resources may
get preempted and added to the list of resources for
which the process is waiting.
o Either of these approaches may be applicable for
resources whose states are easily saved and restored,
such as registers and memory, but are generally not
applicable to other devices such as printers and tape
drives.
7.4.4 Circular Wait

One way to avoid circular wait is to number all resources, and

to require that processes request resources only in strictly
increasing ( or decreasing ) order.
In other words, in order to request resource Rj, a process must
first release all Ri such that i >= j.

 One big challenge in this scheme is determining the relative

ordering of the different resources
7.5 Deadlock Avoidance

The general idea behind deadlock avoidance is to prevent

deadlocks from ever happening, by preventing at least one of
the aforementioned conditions.
This requires more information about each process, AND tends
to lead to low device utilization. ( I.e. it is a conservative
approach. )
In some algorithms the scheduler only needs to know
the maximum number of each resource that a process might
potentially use. In more complex algorithms the scheduler can
also take advantage of the schedule of exactly what resources
may be needed in what order.
When a scheduler sees that starting a process or granting
resource requests may lead to future deadlocks, then that
process is just not started or the request is not granted.
A resource allocation state is defined by the number of
available and allocated resources, and the maximum
requirements of all processes in the system.
7.5.1 Safe State

A state is safe if the system can allocate all resources

requested by all processes ( up to their stated maximums )
without entering a deadlock state.
More formally, a state is safe if there exists a safe
sequence of processes { P0, P1, P2, ..., PN } such that all of
the resource requests for Pi can be granted using the resources
currently allocated to Pi and all processes Pj where j < i. ( I.e. if
all the processes prior to Pi finish and free up their resources,
then Pi will be able to finish also, using the resources that they
have freed up. )

 If a safe sequence does not exist, then the system is in an

unsafe state, which MAY lead to deadlock. ( All safe states are
deadlock free, but not all unsafe states lead to deadlocks. )

Figure 7.6 - Safe, unsafe, and deadlocked state spaces.

For example, consider a system with 12 tape drives, allocated
as follows. Is this a safe state? What is the safe sequence?
Maximum
Needs

Current
Allocation

P0

10

P1

P2

What happens to the above table if process P2 requests and is

granted one more tape drive?
Key to the safe state approach is that when a request is made
for resources, the request is granted only if the resulting
allocation state is a safe one.

7.5.2 Resource-Allocation Graph Algorithm

If resource categories have only single instances of their

resources, then deadlock states can be detected by cycles in
the resource-allocation graphs.
In this case, unsafe states can be recognized and avoided by
augmenting the resource-allocation graph with claim edges,
noted by dashed lines, which point from a process to a
resource that it may request in the future.
In order for this technique to work, all claim edges must be
added to the graph for any particular process before that
process is allowed to request any resources. ( Alternatively,
processes may only make requests for resources for which they
have already established claim edges, and claim edges cannot
be added to any process that is currently holding resources. )
When a process makes a request, the claim edge Pi->Rj is
converted to a request edge. Similarly when a resource is
released, the assignment reverts back to a claim edge.
This approach works by denying requests that would produce
cycles in the resource-allocation graph, taking claim edges into
effect.
Consider for example what happens when process P2 requests
resource R2:

Figure 7.7 - Resource allocation graph for deadlock avoidance

The resulting resource-allocation graph would have a cycle in
it, and so the request cannot be granted.

Figure 7.8 - An unsafe state in a resource allocation graph

7.5.3 Banker's Algorithm

For resource categories that contain more than one instance

the resource-allocation graph method does not work, and more
complex ( and less efficient ) methods must be chosen.
The Banker's Algorithm gets its name because it is a method
that bankers could use to assure that when they lend out
resources they will still be able to satisfy all their clients. ( A

banker won't loan out a little money to start building a house

unless they are assured that they will later be able to loan out
the rest of the money to finish the house. )
When a process starts up, it must state in advance the
maximum allocation of resources it may request, up to the
amount available on the system.
When a request is made, the scheduler determines whether
granting the request would leave the system in a safe state. If
not, then the process must wait until the request can be
granted safely.
The banker's algorithm relies on several key data structures:
( where n is the number of processes and m is the number of
resource categories. )
o Available[ m ] indicates how many resources are currently
available of each type.
o Max[ n ][ m ] indicates the maximum demand of each
process of each resource.
o Allocation[ n ][ m ] indicates the number of each resource
category allocated to each process.
o Need[ n ][ m ] indicates the remaining resources needed
of each type for each process. ( Note that Need[ i ][ j ] =
Max[ i ][ j ] - Allocation[ i ][ j ] for all i, j. )
For simplification of discussions, we make the following
notations / observations:
o One row of the Need vector, Need[ i ], can be treated as a
vector corresponding to the needs of process i, and
similarly for Allocation and Max.
o A vector X is considered to be <= a vector Y if X[ i ] <=
Y[ i ] for all i.

7.5.3.1 Safety Algorithm

In order to apply the Banker's algorithm, we first need an

algorithm for determining whether or not a particular state is
safe.
This algorithm determines if the current state of a system is
safe, according to the following steps:
1. Let Work and Finish be vectors of length m and n
respectively.
Work is a working copy of the available resources,
which will be modified during the analysis.
Finish is a vector of booleans indicating whether a
particular process can finish. ( or has finished so far
in the analysis. )
Initialize Work to Available, and Finish to false for all
elements.
2. Find an i such that both (A) Finish[ i ] == false, and (B)
Need[ i ] < Work. This process has not finished, but could
with the given available working set. If no such i exists, go
to step 4.
3. Set Work = Work + Allocation[ i ], and set Finish[ i ] to
true. This corresponds to process i finishing up and
releasing its resources back into the work pool. Then loop
back to step 2.
4. If finish[ i ] == true for all i, then the state is a safe state,
because a safe sequence has been found.
( JTB's Modification:
1. In step 1. instead of making Finish an array of booleans
initialized to false, make it an array of ints initialized to 0.
Also initialize an int s = 0 as a step counter.
2. In step 2, look for Finish[ i ] == 0.

3. In step 3, set Finish[ i ] to ++s. S is counting the number

of finished processes.
4. For step 4, the test can be either Finish[ i ] > 0 for all i, or
s >= n. The benefit of this method is that if a safe state
exists, then Finish[ ] indicates one safe sequence ( of
possibly many. ) )
7.5.3.2 Resource-Request Algorithm ( The Bankers Algorithm )

Now that we have a tool for determining if a particular state is

safe or not, we are now ready to look at the Banker's algorithm
itself.
This algorithm determines if a new request is safe, and grants
it only if it is safe to do so.
When a request is made ( that does not exceed currently
available resources ), pretend it has been granted, and then
see if the resulting state is a safe one. If so, grant the request,
and if not, deny the request, as follows:
1. Let Request[ n ][ m ] indicate the number of resources of
each type currently requested by processes. If Request[ i ]
> Need[ i ] for any process i, raise an error condition.
2. If Request[ i ] > Available for any process i, then that
process must wait for resources to become available.
Otherwise the process can continue to step 3.
3. Check to see if the request can be granted safely, by
pretending it has been granted and then seeing if the
resulting state is safe. If so, grant the request, and if not,
then the process must wait until its request can be
granted safely.The procedure for granting a request ( or
pretending to for testing purposes ) is:
Available = Available - Request
Allocation = Allocation + Request

 Need = Need - Request

7.5.3.3 An Illustrative Example

Consider the following situation:

And now consider what happens if process P1 requests 1

instance of A and 2 instances of C. ( Request[ 1 ] = ( 1, 0, 2 ) )

What about requests of ( 3, 3,0 ) by P4? or ( 0, 2, 0 ) by P0?

Can these be safely granted? Why or why not?
7.6 Deadlock Detection

If deadlocks are not avoided, then another approach is to

detect when they have occurred and recover somehow.

 In addition to the performance hit of constantly checking for

deadlocks, a policy / algorithm must be in place for recovering
from deadlocks, and there is potential for lost work when
processes must be aborted or have their resources preempted.
7.6.1 Single Instance of Each Resource Type

If each resource category has a single instance, then we can

use a variation of the resource-allocation graph known as
a wait-for graph.
A wait-for graph can be constructed from a resource-allocation
graph by eliminating the resources and collapsing the
associated edges, as shown in the figure below.
An arc from Pi to Pj in a wait-for graph indicates that process Pi
is waiting for a resource that process Pj is currently holding.

Figure 7.9 - (a) Resource allocation graph. (b) Corresponding wait-for graph

 As before, cycles in the wait-for graph indicate deadlocks.

This algorithm must maintain the wait-for graph, and
periodically search it for cycles.
7.6.2 Several Instances of a Resource Type

The detection algorithm outlined here is essentially the same

as the Banker's algorithm, with two subtle differences:
o In step 1, the Banker's Algorithm sets Finish[ i ] to false
for all i. The algorithm presented here sets Finish[ i ] to
false only if Allocation[ i ] is not zero. If the currently
allocated resources for this process are zero, the
algorithm sets Finish[ i ] to true. This is essentially
assuming that IF all of the other processes can finish,
then this process can finish also. Furthermore, this
algorithm is specifically looking for which processes are
involved in a deadlock situation, and a process that does
not have any resources allocated cannot be involved in a
deadlock, and so can be removed from any further
consideration.
o Steps 2 and 3 are unchanged
o In step 4, the basic Banker's Algorithm says that if
Finish[ i ] == true for all i, that there is no deadlock. This
algorithm is more specific, by stating that if Finish[ i ] ==
false for any process Pi, then that process is specifically
involved in the deadlock which has been detected.
( Note: An alternative method was presented above, in which
Finish held integers instead of booleans. This vector would be
initialized to all zeros, and then filled with increasing integers
as processes are detected which can finish. If any processes
are left at zero when the algorithm completes, then there is a
deadlock, and if not, then the integers in finish describe a safe
sequence. To modify this algorithm to match this section of the
text, processes with allocation = zero could be filled in with N,
N - 1, N - 2, etc. in step 1, and any processes left with Finish =
0 in step 4 are the deadlocked processes. )

 Consider, for example, the following state, and determine if it

is currently deadlocked:

Now suppose that process P2 makes a request for an additional

instance of type C, yielding the state shown below. Is the
system now deadlocked?

7.6.3 Detection-Algorithm Usage

When should the deadlock detection be done? Frequently, or

infrequently?
The answer may depend on how frequently deadlocks are
expected to occur, as well as the possible consequences of not
catching them immediately. ( If deadlocks are not removed
immediately when they occur, then more and more processes
can "back up" behind the deadlock, making the eventual task

of unblocking the system more difficult and possibly damaging

to more processes. )
There are two obvious approaches, each with trade-offs:
1. Do deadlock detection after every resource allocation
which cannot be immediately granted. This has the
advantage of detecting the deadlock right away, while the
minimum number of processes are involved in the
deadlock. ( One might consider that the process whose
request triggered the deadlock condition is the "cause" of
the deadlock, but realistically all of the processes in the
cycle are equally responsible for the resulting deadlock. )
The down side of this approach is the extensive overhead
and performance hit caused by checking for deadlocks so
frequently.
2. Do deadlock detection only when there is some clue that
a deadlock may have occurred, such as when CPU
utilization reduces to 40% or some other magic number.
The advantage is that deadlock detection is done much
less frequently, but the down side is that it becomes
impossible to detect the processes involved in the original
deadlock, and so deadlock recovery can be more
complicated and damaging to more processes.
3. ( As I write this, a third alternative comes to mind: Keep a
historical log of resource allocations, since that last known
time of no deadlocks. Do deadlock checks periodically
( once an hour or when CPU usage is low?), and then use
the historical log to trace through and determine when
the deadlock occurred and what processes caused the
initial deadlock. Unfortunately I'm not certain that
breaking the original deadlock would then free up the
resulting log jam. )
7.7 Recovery From Deadlock

There are three basic approaches to recovery from deadlock:

1. Inform the system operator, and allow him/her to take

manual intervention.
2. Terminate one or more processes involved in the deadlock
3. Preempt resources.
7.7.1 Process Termination

Two basic approaches, both of which recover resources

allocated to terminated processes:
o Terminate all processes involved in the deadlock. This
definitely solves the deadlock, but at the expense of
terminating more processes than would be absolutely
necessary.
o Terminate processes one by one until the deadlock is
broken. This is more conservative, but requires doing
deadlock detection after each step.
In the latter case there are many factors that can go into
deciding which processes to terminate next:
o Process priorities.
o How long the process has been running, and how close it
is to finishing.
o How many and what type of resources is the process
holding. ( Are they easy to preempt and restore? )
o How many more resources does the process need to
complete.
o How many processes will need to be terminated
o Whether the process is interactive or batch.
o ( Whether or not the process has made non-restorable
changes to any resource. )

7.7.2 Resource Preemption

When preempting resources to relieve deadlock, there are

three important issues to be addressed:
1. Selecting a victim - Deciding which resources to
preempt from which processes involves many of the same
decision criteria outlined above.
2. Rollback - Ideally one would like to roll back a preempted
process to a safe state prior to the point at which that
resource was originally allocated to the process.
Unfortunately it can be difficult or impossible to
determine what such a safe state is, and so the only safe
rollback is to roll back all the way back to the beginning. (
I.e. abort the process and make it start over. )
3.

Starvation - How do you guarantee that a process won't

starve because its resources are constantly being
preempted? One option would be to use a priority system,
and increase the priority of a process every time its
resources get preempted. Eventually it should get a high
enough priority that it won't get preempted any more.