OPERATING SYSTEM -UNIT 2.pptdeadlock detection – recovery from deadlock.
abinayaraghavan1
58 views
108 slides
Jun 21, 2024
Slide 1 of 108
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
About This Presentation
Process concept – Process Scheduling – Operations on Processes – Inter Process Communication – CPU scheduling – Scheduling criteria – Scheduling algorithms – multi processor scheduling – real time scheduling – Threads overview – multithreading models – threading issues – wind...
Slide Content
Processes
Processconcept–ProcessScheduling–Operationson
Processes–InterProcessCommunication–CPUscheduling–
Schedulingcriteria–Schedulingalgorithms–multiprocessor
scheduling–realtimescheduling–Threadsoverview–
multithreadingmodels–threadingissues–windows,solaris,
linux,androidprocessandthreadmanagement–process
synchronization–thecriticalsectionproblem–
synchronizationhardware–mutexlocks–semaphores–
classicproblemsofsynchronization–criticalregions–
monitors-deadlock–systemmodel–deadlock
characterization–methodsforhandlingdeadlocks–
deadlockprevention–deadlockavoidance–deadlock
detection–recoveryfromdeadlock.
ABINAYA.R / AP / CSE / SRIT
Processconcept–ProcessScheduling–Operationson
Processes–InterProcessCommunication–CPUscheduling–
Schedulingcriteria–Schedulingalgorithms–multiprocessor
scheduling–realtimescheduling–Threadsoverview–
multithreadingmodels–threadingissues–windows,solaris,
linux,androidprocessandthreadmanagement–process
synchronization–thecriticalsectionproblem–
synchronizationhardware–mutexlocks–semaphores–
classicproblemsofsynchronization–criticalregions–
monitors-deadlock–systemmodel–deadlock
characterization–methodsforhandlingdeadlocks–
deadlockprevention–deadlockavoidance–deadlock
detection–recoveryfromdeadlock.
ABINAYA.R / AP / CSE / SRIT
Process Concept
An operating system executes a variety of programs:
Batch system –jobs
Time-shared systems –user programs or tasks
Textbook uses the terms joband processalmost interchangeably
Process–a program in execution; process execution must
progress in sequential fashion
Multiple parts
The program code, also called text section
Current activity includingprogramcounter, processor registers
Stackcontaining temporary data
Function parameters, return addresses, local variables
Data sectioncontaining global variables
Heapcontaining memory dynamically allocated during run time
ABINAYA.R / AP / CSE / SRIT
An operating system executes a variety of programs:
Batch system –jobs
Time-shared systems –user programs or tasks
Textbook uses the terms joband processalmost interchangeably
Process–a program in execution; process execution must
progress in sequential fashion
Multiple parts
The program code, also called text section
Current activity includingprogramcounter, processor registers
Stackcontaining temporary data
Function parameters, return addresses, local variables
Data sectioncontaining global variables
Heapcontaining memory dynamically allocated during run time
ABINAYA.R / AP / CSE / SRIT
A process is an instance of a program running in a computer.
It is close in meaning to task, a term used in some OS.
In UNIX and some other OS, a process is started when a program is initiated
(either by a user entering a shell command or by another program).
A program by itself is not a process; a program is a passive entity, such as a file
containing a list of instructions stored on disks. (often called an executable file)
A program becomes a process when an executable file is loaded into memory and
executed.
ABINAYA.R / AP / CSE / SRIT
It is close in meaning to task, a term used in some OS.
In UNIX and some other OS, a process is started when a program is initiated
(either by a user entering a shell command or by another program).
A program by itself is not a process; a program is a passive entity, such as a file
containing a list of instructions stored on disks. (often called an executable file)
A program becomes a process when an executable file is loaded into memory and
executed.
ABINAYA.R / AP / CSE / SRIT
Process..
When a program is loaded into a memory and it
become a process , it can be divided into four
sections :
1.Stack
The process Stack contains the temporary data such as
method/function parameters, return address and local variables.
2.Heap
This is dynamically allocated memory to a process during its run
time.
3.Text
This includes the current activity represented by the value of
Program Counter and the contents of the processor's registers.
4.Data
This section contains the global and static variables.
ABINAYA.R / AP / CSE / SRIT
When a program is loaded into a memory and it
become a process , it can be divided into four
sections :
1.Stack
The process Stack contains the temporary data such as
method/function parameters, return address and local variables.
2.Heap
This is dynamically allocated memory to a process during its run
time.
3.Text
This includes the current activity represented by the value of
Program Counter and the contents of the processor's registers.
4.Data
This section contains the global and static variables.
ABINAYA.R / AP / CSE / SRIT
Process in Memory
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
Process State
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
ABINAYA.R / AP / CSE / SRIT
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
ABINAYA.R / AP / CSE / SRIT
Diagram of Process State
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
Process Control Block (PCB)
Process Control Block (PCB, also called Task Controlling Block, Entry of
the Process Table, Task Struct, or Switchframe) is a data structure in
the operating system kernel containing the information needed to
manage the scheduling of a particular process.
The PCB is "the manifestation(expression) of a process in an operating
system."
ABINAYA.R / AP / CSE / SRIT
Process Control Block (PCB, also called Task Controlling Block, Entry of
the Process Table, Task Struct, or Switchframe) is a data structure in
the operating system kernel containing the information needed to
manage the scheduling of a particular process.
The PCB is "the manifestation(expression) of a process in an operating
system."
ABINAYA.R / AP / CSE / SRIT
Process Control Block (PCB)
Information associated with each process
(also called task control block)
Process state –running, waiting, etc
Program counter –location of instruction
to next execute
CPU registers –contents of all process-
centric registers
CPU scheduling information-priorities,
scheduling queue pointers
Memory-management information –
memory allocated to the process
Accounting information –CPU used, clock
time elapsed since start, time limits
I/O status information –I/O devices
allocated to process, list of open files
ABINAYA.R / AP / CSE / SRIT
Information associated with each process
(also called task control block)
Process state –running, waiting, etc
Program counter –location of instruction
to next execute
CPU registers –contents of all process-
centric registers
CPU scheduling information-priorities,
scheduling queue pointers
Memory-management information –
memory allocated to the process
Accounting information –CPU used, clock
time elapsed since start, time limits
I/O status information –I/O devices
allocated to process, list of open files
ABINAYA.R / AP / CSE / SRIT
CPU Switch From Process to Process
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
Processscheduling
ProcessschedulingisanessentialpartofaMultiprogrammingoperating
systems.Suchoperatingsystemsallowmorethanoneprocesstobe
loadedintotheexecutablememoryatatimeandtheloadedprocess
sharestheCPUusingtimemultiplexing.
Categories of Scheduling
Therearetwocategoriesofscheduling:
1.Non-preemptive:Here the resource can’t be taken from a process
until the process completes execution. The switching of resources occurs
when the running process terminates and moves to a waiting state.
2.Preemptive:Here the OS allocates the resources to a process for a
fixed amount of time. During resource allocation, the process switches
from running state to ready state or from waiting state to ready state.
This switching occurs as the CPU may give priority to other processes
and replace the process with higher priority with the running process.
ABINAYA.R / AP / CSE / SRIT
ProcessschedulingisanessentialpartofaMultiprogrammingoperating
systems.Suchoperatingsystemsallowmorethanoneprocesstobe
loadedintotheexecutablememoryatatimeandtheloadedprocess
sharestheCPUusingtimemultiplexing.
Categories of Scheduling
Therearetwocategoriesofscheduling:
1.Non-preemptive:Here the resource can’t be taken from a process
until the process completes execution. The switching of resources occurs
when the running process terminates and moves to a waiting state.
2.Preemptive:Here the OS allocates the resources to a process for a
fixed amount of time. During resource allocation, the process switches
from running state to ready state or from waiting state to ready state.
This switching occurs as the CPU may give priority to other processes
and replace the process with higher priority with the running process.
ABINAYA.R / AP / CSE / SRIT
Schedulers
ABINAYA.R / AP / CSE / SRIT
Schedulersarespecialsystemsoftwarewhichhandleprocessschedulingin
variousways.Theirmaintaskistoselectthejobstobesubmittedintothe
systemandtodecidewhichprocesstorun.Schedulersareofthreetypes
•Long-Term Scheduler
•Short-Term Scheduler
•Medium-Term Scheduler
ABINAYA.R / AP / CSE / SRIT
Schedulersarespecialsystemsoftwarewhichhandleprocessschedulingin
variousways.Theirmaintaskistoselectthejobstobesubmittedintothe
systemandtodecidewhichprocesstorun.Schedulersareofthreetypes
•Long-Term Scheduler
•Short-Term Scheduler
•Medium-Term Scheduler
Long Term Scheduler
It is also called ajob scheduler. A long-term scheduler determines which
programs are admitted to the system for processing. It selects processes from the
queue and loads them into memory for execution. Process loads into the memory
for CPU scheduling.
Short Term Scheduler
It is also called asCPU scheduler. Its main objective is to increase system
performance in accordance with the chosen set of criteria. It is the change of
ready state to running state of the process. CPU scheduler selects a process
among the processes that are ready to execute and allocates CPU to one of them.
Medium Term Scheduler
Medium-termschedulingisapartofswapping.Itremovestheprocessesfrom
thememory.Itreducesthedegreeofmultiprogramming.Themedium-term
schedulerisin-chargeofhandlingtheswappedout-processes.
ABINAYA.R / AP / CSE / SRIT
It is also called ajob scheduler. A long-term scheduler determines which
programs are admitted to the system for processing. It selects processes from the
queue and loads them into memory for execution. Process loads into the memory
for CPU scheduling.
Short Term Scheduler
It is also called asCPU scheduler. Its main objective is to increase system
performance in accordance with the chosen set of criteria. It is the change of
ready state to running state of the process. CPU scheduler selects a process
among the processes that are ready to execute and allocates CPU to one of them.
Medium Term Scheduler
Medium-termschedulingisapartofswapping.Itremovestheprocessesfrom
thememory.Itreducesthedegreeofmultiprogramming.Themedium-term
schedulerisin-chargeofhandlingtheswappedout-processes.
ABINAYA.R / AP / CSE / SRIT
S.N.Long-Term SchedulerShort-Term SchedulerMedium-Term Scheduler
1 It is a job schedulerIt is a CPU schedulerIt is a process swapping
scheduler.
2 Speed is lesser than
short term scheduler
Speed is fastest among
other two
Speed is in between
both short and long term
scheduler.
3 It controls the degree
of multiprogramming
It provides lesser control
over degree of
multiprogramming
It reduces the degree of
multiprogramming.
4 It is almost absent or
minimal in time
sharing system
It is also minimal in time
sharing system
It is a part of Time
sharing systems.
5 It selects processes
from pool and loads
them into memory for
execution
It selects those
processes which are
ready to execute
It can re-introduce the
process into memory
and execution can be
continued.
ABINAYA.R / AP / CSE / SRIT
1 It is a job schedulerIt is a CPU schedulerIt is a process swapping
scheduler.
2 Speed is lesser than
short term scheduler
Speed is fastest among
other two
Speed is in between
both short and long term
scheduler.
3 It controls the degree
of multiprogramming
It provides lesser control
over degree of
multiprogramming
It reduces the degree of
multiprogramming.
4 It is almost absent or
minimal in time
sharing system
It is also minimal in time
sharing system
It is a part of Time
sharing systems.
5 It selects processes
from pool and loads
them into memory for
execution
It selects those
processes which are
ready to execute
It can re-introduce the
process into memory
and execution can be
continued.
ABINAYA.R / AP / CSE / SRIT
Operation on Process
ABINAYA.R / AP / CSE / SRIT
Process Creation
Thereshouldbefourprincipleeventswhichcauseprocessestobecreated.
System initialization
Numerousprocessesarecreatedwhenanoperatingsystemisbooted.Someofthem
are−
•Foregroundprocesses−Processesthatinteractwithusersandperformworkfor
them.
•Backgroundprocesses−Itisalsocalledasdaemonsandnotassociatedwith
particularusers,butinsteadhassomespecificfunction.
Process Termination
ProcessisgoingtobeterminatedbyacalltokillinUNIXorTerminateProcessin
windows.
Processisterminatedduetofollowingreason−
•Normalexit−Mostprocessesterminatewhentheyhavecompletedtheirworkand
executeasystemcalltoexit.
•Errorexit−Thethirdtypeoferroroccursduetoprogrambugslikeexecutingan
illegalinstruction,referencing,ordividingbyzero.
•Fatalexit−Aterminationofaprocessoccurswhenitdiscoversafatalerror.
•Killedbyanotherprocess−Aprocessexecutesasystemcalltokillsomeother
process.
ABINAYA.R / AP / CSE / SRIT
Process Creation
Thereshouldbefourprincipleeventswhichcauseprocessestobecreated.
System initialization
Numerousprocessesarecreatedwhenanoperatingsystemisbooted.Someofthem
are−
•Foregroundprocesses−Processesthatinteractwithusersandperformworkfor
them.
•Backgroundprocesses−Itisalsocalledasdaemonsandnotassociatedwith
particularusers,butinsteadhassomespecificfunction.
Process Termination
ProcessisgoingtobeterminatedbyacalltokillinUNIXorTerminateProcessin
windows.
Processisterminatedduetofollowingreason−
•Normalexit−Mostprocessesterminatewhentheyhavecompletedtheirworkand
executeasystemcalltoexit.
•Errorexit−Thethirdtypeoferroroccursduetoprogrambugslikeexecutingan
illegalinstruction,referencing,ordividingbyzero.
•Fatalexit−Aterminationofaprocessoccurswhenitdiscoversafatalerror.
•Killedbyanotherprocess−Aprocessexecutesasystemcalltokillsomeother
process.
Process Representation in Linux
Represented by the C structure task_struct
pid t_pid; /* process identifier */
long state; /* state of the process */
unsigned int time_slice /* scheduling
information */
struct task_struct *parent; /* this process ’s
parent */
struct list_head children; /* this process ’s
children */
struct files_struct *files; /* list of open
files */
struct mm_struct *mm; /* address space of this
process */
ABINAYA.R / AP / CSE / SRIT
Represented by the C structure task_struct
pid t_pid; /* process identifier */
long state; /* state of the process */
unsigned int time_slice /* scheduling
information */
struct task_struct *parent; /* this process ’s
parent */
struct list_head children; /* this process ’s
children */
struct files_struct *files; /* list of open
files */
struct mm_struct *mm; /* address space of this
process */
ABINAYA.R / AP / CSE / SRIT
Process Scheduling
Maximize CPU use, quickly switch processes onto CPU for time
sharing
Process scheduler selects among available processes for next
execution on CPU
Maintains scheduling queues of processes
Job queue –set of all processes in the system
Ready queue –set of all processes residing in main memory,
ready and waiting to execute
Device queues –set of processes waiting for an I/O device
Processes migrate among the various queues
ABINAYA.R / AP / CSE / SRIT
Maximize CPU use, quickly switch processes onto CPU for time
sharing
Process scheduler selects among available processes for next
execution on CPU
Maintains scheduling queues of processes
Job queue –set of all processes in the system
Ready queue –set of all processes residing in main memory,
ready and waiting to execute
Device queues –set of processes waiting for an I/O device
Processes migrate among the various queues
ABINAYA.R / AP / CSE / SRIT
Ready Queue And Various I/O Device Queues
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
Representation of Process Scheduling
ABINAYA.R / AP / CSE / SRIT
Queueing diagram represents queues, resources, flows
ABINAYA.R / AP / CSE / SRIT
Queueing diagram represents queues, resources, flows
Schedulers
Short-term scheduler (or CPU scheduler) –selects which process should
be executed next and allocates CPU
Sometimes the only scheduler in a system
Short-term scheduler is invoked frequently (milliseconds) (must be
fast)
Long-term scheduler (or job scheduler) –selects which processes should
be brought into the ready queue
Long-term scheduler is invoked infrequently (seconds, minutes)
(may be slow)
The long-term scheduler controls the degree of multiprogramming
Processes can be described as either:
I/O-bound process–spends more time doing I/O than computations,
many short CPU bursts
CPU-bound process –spends more time doing computations; few very
long CPU bursts
Long-term scheduler strives for good process mix
ABINAYA.R / AP / CSE / SRIT
Short-term scheduler (or CPU scheduler) –selects which process should
be executed next and allocates CPU
Sometimes the only scheduler in a system
Short-term scheduler is invoked frequently (milliseconds) (must be
fast)
Long-term scheduler (or job scheduler) –selects which processes should
be brought into the ready queue
Long-term scheduler is invoked infrequently (seconds, minutes)
(may be slow)
The long-term scheduler controls the degree of multiprogramming
Processes can be described as either:
I/O-bound process–spends more time doing I/O than computations,
many short CPU bursts
CPU-bound process –spends more time doing computations; few very
long CPU bursts
Long-term scheduler strives for good process mix
ABINAYA.R / AP / CSE / SRIT
Addition of Medium Term Scheduling
ABINAYA.R / AP / CSE / SRIT
Medium-term scheduler can be added if degree of multiple
programming needs to decrease
Remove process from memory, store on disk, bring back in
from disk to continue execution: swapping
ABINAYA.R / AP / CSE / SRIT
Medium-term scheduler can be added if degree of multiple
programming needs to decrease
Remove process from memory, store on disk, bring back in
from disk to continue execution: swapping
Operations on Processes
System must provide mechanisms for:
process creation,
process termination,
ABINAYA.R / AP / CSE / SRIT
System must provide mechanisms for:
process creation,
process termination,
ABINAYA.R / AP / CSE / SRIT
Process Creation
Parentprocess create childrenprocesses, which, in turn
create other processes, forming a treeof processes
Generally, process identified and managed via aprocess
identifier (pid)
Resource sharing options
Parent and children share all resources
Children share subset of parent’s resources
Parent and child share no resources
Execution options
Parent and children execute concurrently
Parent waits until children terminate
ABINAYA.R / AP / CSE / SRIT
Parentprocess create childrenprocesses, which, in turn
create other processes, forming a treeof processes
Generally, process identified and managed via aprocess
identifier (pid)
Resource sharing options
Parent and children share all resources
Children share subset of parent’s resources
Parent and child share no resources
Execution options
Parent and children execute concurrently
Parent waits until children terminate
ABINAYA.R / AP / CSE / SRIT
A Tree of Processes in Linux
ABINAYA.R / AP / CSE / SRITinit
pid = 1
sshd
pid = 3028
login
pid = 8415
kthreadd
pid = 2
sshd
pid = 3610
pdflush
pid = 200
khelper
pid = 6
tcsch
pid = 4005
emacs
pid = 9204
bash
pid = 8416
ps
pid = 9298
ABINAYA.R / AP / CSE / SRITinit
pid = 1
sshd
pid = 3028
login
pid = 8415
kthreadd
pid = 2
sshd
pid = 3610
pdflush
pid = 200
khelper
pid = 6
tcsch
pid = 4005
emacs
pid = 9204
bash
pid = 8416
ps
pid = 9298
Process Creation (Cont.)
Address space
Child duplicate of parent
Child has a program loaded into it
UNIX examples
fork()system call creates new process
exec()system call used after a fork()to replace the process’
memory space with a new program
ABINAYA.R / AP / CSE / SRIT
Address space
Child duplicate of parent
Child has a program loaded into it
UNIX examples
fork()system call creates new process
exec()system call used after a fork()to replace the process’
memory space with a new program
ABINAYA.R / AP / CSE / SRIT
Process Termination
Process executes last statement and then asks the operating
system to delete it using the exit()system call.
Returns status data from child to parent (via wait())
Process’resources are deallocated by operating system
Parent may terminate the execution of children processes using
the abort()system call. Some reasons for doing so:
Child has exceeded allocated resources
Task assigned to child is no longer required
The parent is exiting and the operating systems does not allow a
child to continue if its parent terminates
ABINAYA.R / AP / CSE / SRIT
Process executes last statement and then asks the operating
system to delete it using the exit()system call.
Returns status data from child to parent (via wait())
Process’resources are deallocated by operating system
Parent may terminate the execution of children processes using
the abort()system call. Some reasons for doing so:
Child has exceeded allocated resources
Task assigned to child is no longer required
The parent is exiting and the operating systems does not allow a
child to continue if its parent terminates
ABINAYA.R / AP / CSE / SRIT
Process Termination
Some operating systems do not allow child to exists if its parent
has terminated. If a process terminates, then all its children
must also be terminated.
cascading termination. All children, grandchildren, etc. are
terminated.
The termination is initiated by the operating system.
The parent process may wait for termination of a child process by
using the wait()system call. The call returns status information
and the pid of the terminated process
pid = wait(&status);
If no parent waiting (did not invoke wait()) process is a zombie
If parent terminated without invokingwait, process is an
orphan
ABINAYA.R / AP / CSE / SRIT
Some operating systems do not allow child to exists if its parent
has terminated. If a process terminates, then all its children
must also be terminated.
cascading termination. All children, grandchildren, etc. are
terminated.
The termination is initiated by the operating system.
The parent process may wait for termination of a child process by
using the wait()system call. The call returns status information
and the pid of the terminated process
pid = wait(&status);
If no parent waiting (did not invoke wait()) process is a zombie
If parent terminated without invokingwait, process is an
orphan
ABINAYA.R / AP / CSE / SRIT
Interprocess Communication
Processes within a system may be independentor cooperating
Cooperating process can affect or be affected by other processes,
including sharing data
Reasons for cooperating processes:
Information sharing
Computational speedup
Modularity
Convenience
Cooperating esses need interprocess communication (IPC)
Two models of IPC
Shared memory
Message passing
ABINAYA.R / AP / CSE / SRIT
Processes within a system may be independentor cooperating
Cooperating process can affect or be affected by other processes,
including sharing data
Reasons for cooperating processes:
Information sharing
Computational speedup
Modularity
Convenience
Cooperating esses need interprocess communication (IPC)
Two models of IPC
Shared memory
Message passing
ABINAYA.R / AP / CSE / SRIT
Communications Models
ABINAYA.R / AP / CSE / SRIT
(a) Message passing. (b) shared memory.
ABINAYA.R / AP / CSE / SRIT
(a) Message passing. (b) shared memory.
Cooperating Processes
Independentprocess cannot affect or be affected by the execution
of another process
Cooperatingprocess can affect or be affected by the execution of
another process
Advantages of process cooperation
Information sharing
Computation speed-up
Modularity
Convenience
ABINAYA.R / AP / CSE / SRIT
Independentprocess cannot affect or be affected by the execution
of another process
Cooperatingprocess can affect or be affected by the execution of
another process
Advantages of process cooperation
Information sharing
Computation speed-up
Modularity
Convenience
ABINAYA.R / AP / CSE / SRIT
Interprocess Communication –Shared Memory
Anareaofmemorysharedamongtheprocesses
thatwishtocommunicate
Thecommunicationisunderthecontrolofthe
usersprocessesnottheoperatingsystem.
Majorissuesistoprovidemechanismthatwill
allowtheuserprocessestosynchronizetheir
actionswhentheyaccesssharedmemory.
ABINAYA.R / AP / CSE / SRIT
Anareaofmemorysharedamongtheprocesses
thatwishtocommunicate
Thecommunicationisunderthecontrolofthe
usersprocessesnottheoperatingsystem.
Majorissuesistoprovidemechanismthatwill
allowtheuserprocessestosynchronizetheir
actionswhentheyaccesssharedmemory.
ABINAYA.R / AP / CSE / SRIT
Interprocess Communication –Message Passing
Mechanismforprocessestocommunicateandtosynchronizetheir
actions
Messagesystem–processescommunicatewitheachotherwithout
resortingtosharedvariables
IPCfacilityprovidestwooperations:
send(message)
receive(message)
Themessagesizeiseitherfixedorvariable
ABINAYA.R / AP / CSE / SRIT
Mechanismforprocessestocommunicateandtosynchronizetheir
actions
Messagesystem–processescommunicatewitheachotherwithout
resortingtosharedvariables
IPCfacilityprovidestwooperations:
send(message)
receive(message)
Themessagesizeiseitherfixedorvariable
ABINAYA.R / AP / CSE / SRIT
Message Passing (Cont.)
If processes Pand Qwish to communicate, they need to:
Establish a communicationlinkbetween them
Exchange messages via send/receive
Implementation issues:
How are links established?
Can a link be associated with more than two processes?
How many links can there be between every pair of communicating
processes?
What is the capacity of a link?
Is the size of a message that the link can accommodate fixed or variable?
Is a link unidirectional or bi-directional?
ABINAYA.R / AP / CSE / SRIT
If processes Pand Qwish to communicate, they need to:
Establish a communicationlinkbetween them
Exchange messages via send/receive
Implementation issues:
How are links established?
Can a link be associated with more than two processes?
How many links can there be between every pair of communicating
processes?
What is the capacity of a link?
Is the size of a message that the link can accommodate fixed or variable?
Is a link unidirectional or bi-directional?
ABINAYA.R / AP / CSE / SRIT
Message Passing (Cont.)
Implementation of communication link
Physical:
Shared memory
Hardware bus
Network
Logical:
Direct or indirect
Synchronous or asynchronous
Automatic or explicit buffering
ABINAYA.R / AP / CSE / SRIT
Implementation of communication link
Physical:
Shared memory
Hardware bus
Network
Logical:
Direct or indirect
Synchronous or asynchronous
Automatic or explicit buffering
ABINAYA.R / AP / CSE / SRIT
Direct Communication
Processes must name each other explicitly:
send(P, message) –send a message to process P
receive(Q, message) –receive a message from process Q
Properties of communication link
Links are established automatically
A link is associated with exactly one pair of communicating processes
Between each pair there exists exactly one link
The link may be unidirectional, but is usually bi-directional
ABINAYA.R / AP / CSE / SRIT
Processes must name each other explicitly:
send(P, message) –send a message to process P
receive(Q, message) –receive a message from process Q
Properties of communication link
Links are established automatically
A link is associated with exactly one pair of communicating processes
Between each pair there exists exactly one link
The link may be unidirectional, but is usually bi-directional
ABINAYA.R / AP / CSE / SRIT
Indirect Communication
Messages are directed and received from mailboxes (also referred
to as ports)
Each mailbox has a unique id
Processes can communicate only if they share a mailbox
Properties of communication link
Link established only if processes share a common mailbox
A link may be associated with many processes
Each pair of processes may share several communication links
Link may be unidirectional or bi-directional
ABINAYA.R / AP / CSE / SRIT
Messages are directed and received from mailboxes (also referred
to as ports)
Each mailbox has a unique id
Processes can communicate only if they share a mailbox
Properties of communication link
Link established only if processes share a common mailbox
A link may be associated with many processes
Each pair of processes may share several communication links
Link may be unidirectional or bi-directional
ABINAYA.R / AP / CSE / SRIT
Indirect Communication
Operations
create a new mailbox (port)
send and receive messages through mailbox
destroy a mailbox
Primitives are defined as:
send(A, message) –send a message to mailbox A
receive(A, message) –receive a message from mailbox A
ABINAYA.R / AP / CSE / SRIT
Operations
create a new mailbox (port)
send and receive messages through mailbox
destroy a mailbox
Primitives are defined as:
send(A, message) –send a message to mailbox A
receive(A, message) –receive a message from mailbox A
ABINAYA.R / AP / CSE / SRIT
Indirect Communication
Mailbox sharing
P
1, P
2,andP
3share mailbox A
P
1, sends; P
2andP
3receive
Who gets the message?
Solutions
Allow a link to be associated with at most two processes
Allow only one process at a time to execute a receive
operation
Allow the system to select arbitrarily the receiver. Sender is
notified who the receiver was.
ABINAYA.R / AP / CSE / SRIT
Mailbox sharing
P
1, P
2,andP
3share mailbox A
P
1, sends; P
2andP
3receive
Who gets the message?
Solutions
Allow a link to be associated with at most two processes
Allow only one process at a time to execute a receive
operation
Allow the system to select arbitrarily the receiver. Sender is
notified who the receiver was.
ABINAYA.R / AP / CSE / SRIT
Threads
So far, process has a single thread of execution
Consider having multiple program counters per process
Multiple locations can execute at once
Multiple threads of control -> threads
Must then have storage for thread details, multiple program
counters in PCB
See next chapter
ABINAYA.R / AP / CSE / SRIT
So far, process has a single thread of execution
Consider having multiple program counters per process
Multiple locations can execute at once
Multiple threads of control -> threads
Must then have storage for thread details, multiple program
counters in PCB
See next chapter
ABINAYA.R / AP / CSE / SRIT
Threads
Overview
Multicore Programming
Multithreading Models
Thread and SMP Management
ABINAYA.R / AP / CSE / SRIT
Overview
Multicore Programming
Multithreading Models
Thread and SMP Management
ABINAYA.R / AP / CSE / SRIT
Thread Overview
Threads are mechanisms that permit an application to perform
multiple tasks concurrently.
Thread is a basic unit of CPU utilization
Thread ID
Program counter
Register set
Stack
A single program can contain multiple threads
Threads share with other threads belonging to the same process
Code, data, open files…….
ABINAYA.R / AP / CSE / SRIT
Threads are mechanisms that permit an application to perform
multiple tasks concurrently.
Thread is a basic unit of CPU utilization
Thread ID
Program counter
Register set
Stack
A single program can contain multiple threads
Threads share with other threads belonging to the same process
Code, data, open files…….
ABINAYA.R / AP / CSE / SRIT
Single and Multithreaded Processes
ABINAYA.R / AP / CSE / SRIT
Traditional
(heavyweight)
process has a
single thread of
control
heavyweight process lightweightprocess
ABINAYA.R / AP / CSE / SRIT
Traditional
(heavyweight)
process has a
single thread of
control
heavyweight process lightweightprocess
Threads
Global memory
Process ID and parent process ID
Controlling terminal
Process credentials (user )
Open file information
Timers
………
ABINAYA.R / AP / CSE / SRIT
Threads share….
Threads specific
Attributes….
Thread ID
Thread specific data
CPU affinity
Stack (local variables and function
call linkage information)
……
Global memory
Process ID and parent process ID
Controlling terminal
Process credentials (user )
Open file information
Timers
………
ABINAYA.R / AP / CSE / SRIT
Threads share….
Threads specific
Attributes….
Thread ID
Thread specific data
CPU affinity
Stack (local variables and function
call linkage information)
……
Benefits
Responsiveness
Interactive application can delegate background functions to a
thread and keep running
Resource Sharing
Several different threads can access the same address space
Economy
Allocating memory and new processes is costly. Threads are much
‘cheaper’ to initiate.
Scalability
Use threads to take advantage of multiprocessor architecture
ABINAYA.R / AP / CSE / SRIT
Responsiveness
Interactive application can delegate background functions to a
thread and keep running
Resource Sharing
Several different threads can access the same address space
Economy
Allocating memory and new processes is costly. Threads are much
‘cheaper’ to initiate.
Scalability
Use threads to take advantage of multiprocessor architecture
ABINAYA.R / AP / CSE / SRIT
Multithreaded Server Architecture
ABINAYA.R / AP / CSE / SRIT
thread
thread
thread
thread
ABINAYA.R / AP / CSE / SRIT
thread
thread
thread
thread
Multithreading Models
Support provided at either
User level -> user threads
Supported above the kernel and managed without kernel
support
Kernel level -> kernel threads
Supported and managed directly by the operating system
What is the relationship between user and kernel threads?
ABINAYA.R / AP / CSE / SRIT
Support provided at either
User level -> user threads
Supported above the kernel and managed without kernel
support
Kernel level -> kernel threads
Supported and managed directly by the operating system
What is the relationship between user and kernel threads?
ABINAYA.R / AP / CSE / SRIT
User Threads
Thread management done by user-level threads library
Three primary thread libraries:
POSIX Pthreads
Win32 threads
Java threads
ABINAYA.R / AP / CSE / SRIT
Thread management done by user-level threads library
Three primary thread libraries:
POSIX Pthreads
Win32 threads
Java threads
ABINAYA.R / AP / CSE / SRIT
Kernel Threads
Supported by the Kernel
Examples
Windows XP/2000
Solaris
Linux
Tru64 UNIX
Mac OS X
ABINAYA.R / AP / CSE / SRIT
Supported by the Kernel
Examples
Windows XP/2000
Solaris
Linux
Tru64 UNIX
Mac OS X
ABINAYA.R / AP / CSE / SRIT
Multithreading Models
Many-to-One
One-to-One
Many-to-Many
ABINAYA.R / AP / CSE / SRIT
User Thread –to -Kernel Thread
Many-to-One
One-to-One
Many-to-Many
ABINAYA.R / AP / CSE / SRIT
User Thread –to -Kernel Thread
Many-to-One
Many user-level
threads mapped to
single kernel thread
ABINAYA.R / AP / CSE / SRIT
Many user-level
threads mapped to
single kernel thread
ABINAYA.R / AP / CSE / SRIT
One-to-One
Each user-level thread maps to kernel
thread
Examples
Windows NT/XP/2000
Linux
ABINAYA.R / AP / CSE / SRIT
Each user-level thread maps to kernel
thread
Examples
Windows NT/XP/2000
Linux
ABINAYA.R / AP / CSE / SRIT
Many-to-Many Model
Allows many user level
threads to be mapped
to many kernel threads
Allows the operating
system to create a
sufficient number of
kernel threads
Example
Windows NT/2000 with
the ThreadFiberpackage
ABINAYA.R / AP / CSE / SRIT
Allows many user level
threads to be mapped
to many kernel threads
Allows the operating
system to create a
sufficient number of
kernel threads
Example
Windows NT/2000 with
the ThreadFiberpackage
ABINAYA.R / AP / CSE / SRIT
Process and Thread Objects
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
Windows Operating System:
Windows is an operating system designed by Microsoft to
be used on a standard x86 Intel and AMD processors. It
provides an interface, known as a graphical user
interface(GUI) which eliminates the need to memorize
commands for the command line by using a mouse to
navigate through menus, dialog boxes, buttons, tabs,
and icons. The operating system was named windows
since the programs are displayed in the shape of a
square. This Windows operating system has been
designed for both a novice user just using at home as
well as for professionals who are into development.
ABINAYA.R / AP / CSE / SRIT
Windows is an operating system designed by Microsoft to
be used on a standard x86 Intel and AMD processors. It
provides an interface, known as a graphical user
interface(GUI) which eliminates the need to memorize
commands for the command line by using a mouse to
navigate through menus, dialog boxes, buttons, tabs,
and icons. The operating system was named windows
since the programs are displayed in the shape of a
square. This Windows operating system has been
designed for both a novice user just using at home as
well as for professionals who are into development.
ABINAYA.R / AP / CSE / SRIT
Features:
ABINAYA.R / AP / CSE / SRIT
It is designed to run on any standard x86 Intel and AMD hence most of the hardware vendors
make drivers for windows like Dell, HP, etc.
It supports enhanced performance by utilizing multi-core processors.
It comes preloaded with many productivity tools which helps to complete all types of everyday
tasks on your computer.
Windows has a very large user base so there is a much larger selection of available software
programs, utilities.
Windows is backward compatible meaning old programs can run on newer versions.
Hardware is automatically detected eliminating need of manually installing any device drivers
ABINAYA.R / AP / CSE / SRIT
It is designed to run on any standard x86 Intel and AMD hence most of the hardware vendors
make drivers for windows like Dell, HP, etc.
It supports enhanced performance by utilizing multi-core processors.
It comes preloaded with many productivity tools which helps to complete all types of everyday
tasks on your computer.
Windows has a very large user base so there is a much larger selection of available software
programs, utilities.
Windows is backward compatible meaning old programs can run on newer versions.
Hardware is automatically detected eliminating need of manually installing any device drivers
Drawbacks:
Windows can be expensive since the OS is paid license and
majority of its applications are paid products.
Windows has high computer resource requirement like it
should have high ram capacity, a lot of hard drive space
and good graphics card.
Windows slows and hangs up if the user loads up many
programs at the same time.
Windows includes network sharing that can be useful if user
has a network with many PCs.
Windows is vulnerable to virus attacks since it has a huge
user base and users have to update OS to keep up-to-date
with security patches.
ABINAYA.R / AP / CSE / SRIT
Windows can be expensive since the OS is paid license and
majority of its applications are paid products.
Windows has high computer resource requirement like it
should have high ram capacity, a lot of hard drive space
and good graphics card.
Windows slows and hangs up if the user loads up many
programs at the same time.
Windows includes network sharing that can be useful if user
has a network with many PCs.
Windows is vulnerable to virus attacks since it has a huge
user base and users have to update OS to keep up-to-date
with security patches.
ABINAYA.R / AP / CSE / SRIT
LINUX Operating System:
The Linux OS is an open source operating system project
that is a freely distributed, cross-platform operating
system developed based on UNIX. This operating system
is developed by Linus Torvalds. The name Linux comes
from the Linux kernel. It is basically the system
software on a computer that allows apps and users to
perform some specific task on the computer. The
development of Linux operating system pioneered the
open source development and became the symbol of
software collaboration.
ABINAYA.R / AP / CSE / SRIT
The Linux OS is an open source operating system project
that is a freely distributed, cross-platform operating
system developed based on UNIX. This operating system
is developed by Linus Torvalds. The name Linux comes
from the Linux kernel. It is basically the system
software on a computer that allows apps and users to
perform some specific task on the computer. The
development of Linux operating system pioneered the
open source development and became the symbol of
software collaboration.
ABINAYA.R / AP / CSE / SRIT
Linux is free can be downloaded from the Internet or
redistribute it under GNU licenses and has the best
community support.
Linux OS is easily portable which means it can be installed
on various types of devices like mobile, tablet computers.
It is a multi-user, multitasking operating system.
BASH is the Linux interpreter program which can be used to
execute commands.
Linux provides multiple levels of file structures i.e.
hierarchical structure in which all the files required by the
system and those that are created by the user are
arranged.
Linux provides user security using authentication features
and also threat detection and solution is very fast because
Linux is mainly community driven.
ABINAYA.R / AP / CSE / SRIT
Features:
redistribute it under GNU licenses and has the best
community support.
Linux OS is easily portable which means it can be installed
on various types of devices like mobile, tablet computers.
It is a multi-user, multitasking operating system.
BASH is the Linux interpreter program which can be used to
execute commands.
Linux provides multiple levels of file structures i.e.
hierarchical structure in which all the files required by the
system and those that are created by the user are
arranged.
Linux provides user security using authentication features
and also threat detection and solution is very fast because
Linux is mainly community driven.
ABINAYA.R / AP / CSE / SRIT
Features:
Drawbacks:
There’s no standard edition of Linux hence confusing for users and also
becoming familiar with the Linux may be a problem for new users.
More difficult to find applications to support user needs since Linux
does not dominate the market.
Since some applications are developed specifically for Windows and
Mac, those might not be compatible with linuxand sometimes users
might not have much of a choice to choose between different
applications like in Windows or Mac since most apps are developed
for operating systems that have a huge user base.
Some hardware may not be incompatible with Linux since it has
patchier support for drivers which may result in malfunction.
There are plenty of forums to resolve Linux issues, but it may not
always match the user’s own level of technical understanding.
ABINAYA.R / AP / CSE / SRIT
There’s no standard edition of Linux hence confusing for users and also
becoming familiar with the Linux may be a problem for new users.
More difficult to find applications to support user needs since Linux
does not dominate the market.
Since some applications are developed specifically for Windows and
Mac, those might not be compatible with linuxand sometimes users
might not have much of a choice to choose between different
applications like in Windows or Mac since most apps are developed
for operating systems that have a huge user base.
Some hardware may not be incompatible with Linux since it has
patchier support for drivers which may result in malfunction.
There are plenty of forums to resolve Linux issues, but it may not
always match the user’s own level of technical understanding.
ABINAYA.R / AP / CSE / SRIT
Solaris Operating System:
Solaris or SunOS is the name of the Sun company’s Unix
variant operating system that was originally developed
for its family of Scalable Processor Architecture-based
processors (SPARC) as well as for Intel-based processors.
The UNIX workstation market had been largely
dominated by this operating system during its time. As
the Internet grew Sun’s Solaris systems became the
most widely installed servers for Web sites. Oracle
purchased Sun and later renamed to Oracle Solaris.
ABINAYA.R / AP / CSE / SRIT
Solaris or SunOS is the name of the Sun company’s Unix
variant operating system that was originally developed
for its family of Scalable Processor Architecture-based
processors (SPARC) as well as for Intel-based processors.
The UNIX workstation market had been largely
dominated by this operating system during its time. As
the Internet grew Sun’s Solaris systems became the
most widely installed servers for Web sites. Oracle
purchased Sun and later renamed to Oracle Solaris.
ABINAYA.R / AP / CSE / SRIT
Features:
Solaris is known for its scalability. It can handle a large workload and still
delivers indisputable performance advantages for database, Web, and
Java technology-based services.
Solaris systems were known to their availability meaning that these
operating systems hardly crashes at anytime and because of its
internet networking oriented design and broad scope of features it
makes the job of adding new features or fixing any problems easy.
It is built for network computing as it provides optimized network
stack and support for advanced network computing protocols that
delivers high-performance networking to most applications.
Solaris has advanced, unique security capabilities which includes some
of the world’s most advanced security features, such as user rights
management, cryptographic Framework and secure by default
networking that allows users to safely deliver new solutions.
Provides tools to enable seamless interoperability, test new software
and efficiently consolidate application workloads.
ABINAYA.R / AP / CSE / SRIT
Solaris is known for its scalability. It can handle a large workload and still
delivers indisputable performance advantages for database, Web, and
Java technology-based services.
Solaris systems were known to their availability meaning that these
operating systems hardly crashes at anytime and because of its
internet networking oriented design and broad scope of features it
makes the job of adding new features or fixing any problems easy.
It is built for network computing as it provides optimized network
stack and support for advanced network computing protocols that
delivers high-performance networking to most applications.
Solaris has advanced, unique security capabilities which includes some
of the world’s most advanced security features, such as user rights
management, cryptographic Framework and secure by default
networking that allows users to safely deliver new solutions.
Provides tools to enable seamless interoperability, test new software
and efficiently consolidate application workloads.
ABINAYA.R / AP / CSE / SRIT
Drawbacks:
Solaris is quite expensive since it’s an enterprise
operating system. Also, Solaris doesn’t provide updates
for free.
Solaris lacks a good graphical user interface support and
is not user friendly.
Hardware support is not nearly as good as many other
operating systems.
Performance would degrade considerably since Solaris
cannot make use of different hardware that efficiently.
Solaris sometimes becomes unstable and crashes due to
total consumption of CPU and memory.
ABINAYA.R / AP / CSE / SRIT
Solaris is quite expensive since it’s an enterprise
operating system. Also, Solaris doesn’t provide updates
for free.
Solaris lacks a good graphical user interface support and
is not user friendly.
Hardware support is not nearly as good as many other
operating systems.
Performance would degrade considerably since Solaris
cannot make use of different hardware that efficiently.
Solaris sometimes becomes unstable and crashes due to
total consumption of CPU and memory.
ABINAYA.R / AP / CSE / SRIT
Android Mobile Operating
System:
Android is a Google’s Linux based operating system it is
designed primarily for touch screen mobile devices such
as smart phones and tablet computers. The hardware
which can be used to support android is based on three
architectures namely ARM, Intel and MIPS design lets
users manipulate the mobile devices intuitively, with
finger movements that mirror common motions, such as
pinching, swiping, and tapping making these
applications comfortable for the users.
ABINAYA.R / AP / CSE / SRIT
System:
Android is a Google’s Linux based operating system it is
designed primarily for touch screen mobile devices such
as smart phones and tablet computers. The hardware
which can be used to support android is based on three
architectures namely ARM, Intel and MIPS design lets
users manipulate the mobile devices intuitively, with
finger movements that mirror common motions, such as
pinching, swiping, and tapping making these
applications comfortable for the users.
ABINAYA.R / AP / CSE / SRIT
Features:
ABINAYA.R / AP / CSE / SRIT
The android operating system is an open source operating system means that it’s
free and any one can use it.
Android offers optimized 2D and 3D graphics, multimedia, GSM connectivity, multi-
tasking.
Android OS is known for its friendly user interface and exceptional customizable
according to the user’s taste.
Huge choice of applications for its users since Playstore offer over one million apps.
Software developers who want to create applications for the Android OS can
download the Android Software Development Kit(SDK) to easily develop apps for
android.
Android would consume very little power but deliver extreme performance since its
hardware is based on ARM architecture.
ABINAYA.R / AP / CSE / SRIT
The android operating system is an open source operating system means that it’s
free and any one can use it.
Android offers optimized 2D and 3D graphics, multimedia, GSM connectivity, multi-
tasking.
Android OS is known for its friendly user interface and exceptional customizable
according to the user’s taste.
Huge choice of applications for its users since Playstore offer over one million apps.
Software developers who want to create applications for the Android OS can
download the Android Software Development Kit(SDK) to easily develop apps for
android.
Android would consume very little power but deliver extreme performance since its
hardware is based on ARM architecture.
Drawbacks:
The design and coding of intuitive modern user
experiences and interfaces poses a difficulty because of
its dependency on Java.
Most apps tend to run in the background even when
closed by the user draining the battery.
Performance is bound to take a hit as multiple programs
run simultaneously in the background at any given time.
Android phones overheat especially when indulged in
hardcore productivity tasks or heavy graphics.
Apps have lower security profiles and make users more
susceptible to data breaches.
ABINAYA.R / AP / CSE / SRIT
The design and coding of intuitive modern user
experiences and interfaces poses a difficulty because of
its dependency on Java.
Most apps tend to run in the background even when
closed by the user draining the battery.
Performance is bound to take a hit as multiple programs
run simultaneously in the background at any given time.
Android phones overheat especially when indulged in
hardcore productivity tasks or heavy graphics.
Apps have lower security profiles and make users more
susceptible to data breaches.
ABINAYA.R / AP / CSE / SRIT
Process Synchronization was introduced to handle problems
that arose while multiple process executions.
Process is categorized into two types on the basis of
synchronization and these are given below:
•Independent Process
•Cooperative Process
Independent Processes
Two processes are said to be independent if the execution of one
process does not affect the execution of another process.
ABINAYA.R / AP / CSE / SRIT
that arose while multiple process executions.
Process is categorized into two types on the basis of
synchronization and these are given below:
•Independent Process
•Cooperative Process
Independent Processes
Two processes are said to be independent if the execution of one
process does not affect the execution of another process.
ABINAYA.R / AP / CSE / SRIT
Process Synchronization is the coordination of execution of multiple
processes in a multi-process system to ensure that they access shared
resources in a controlled and predictable manner. It aims to resolve
the problem of race conditions and other synchronization issues in a
concurrent system.
The main objective of process synchronization is to ensure that
multiple processes access shared resources without interfering with
each other, and to prevent the possibility of inconsistent data due to
concurrent access. To achieve this, various synchronization techniques
such as semaphores, monitors, and critical sections are used.
ABINAYA.R / AP / CSE / SRIT
processes in a multi-process system to ensure that they access shared
resources in a controlled and predictable manner. It aims to resolve
the problem of race conditions and other synchronization issues in a
concurrent system.
The main objective of process synchronization is to ensure that
multiple processes access shared resources without interfering with
each other, and to prevent the possibility of inconsistent data due to
concurrent access. To achieve this, various synchronization techniques
such as semaphores, monitors, and critical sections are used.
ABINAYA.R / AP / CSE / SRIT
Race Condition:
When more than one process is executing the same code
or accessing the same memory or any shared variable in
that condition there is a possibility that the output or
the value of the shared variable is wrong so for that all
the processes doing the race to say that my output is
correct this condition known as a race condition.
ABINAYA.R / AP / CSE / SRIT
When more than one process is executing the same code
or accessing the same memory or any shared variable in
that condition there is a possibility that the output or
the value of the shared variable is wrong so for that all
the processes doing the race to say that my output is
correct this condition known as a race condition.
ABINAYA.R / AP / CSE / SRIT
Critical Section Problem:
A critical section is a code segment that can be accessed by only one
process at a time. The critical section contains shared variables that
need to be synchronized to maintain the consistency of data variables.
So the critical section problem means designing a way for cooperative
processes to access shared resources without creating data
inconsistencies.
ABINAYA.R / AP / CSE / SRIT
A critical section is a code segment that can be accessed by only one
process at a time. The critical section contains shared variables that
need to be synchronized to maintain the consistency of data variables.
So the critical section problem means designing a way for cooperative
processes to access shared resources without creating data
inconsistencies.
ABINAYA.R / AP / CSE / SRIT
Mutual Exclusion: If a process is executing in its critical
section, then no other process is allowed to execute in
the critical section.
Progress:If no process is executing in the critical
section and other processes are waiting outside the
critical section, then only those processes that are not
executing in their remainder section can participate in
deciding which will enter in the critical section next,
and the selection can not be postponed indefinitely.
Bounded Waiting: A bound must exist 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.
ABINAYA.R / AP / CSE / SRIT
section, then no other process is allowed to execute in
the critical section.
Progress:If no process is executing in the critical
section and other processes are waiting outside the
critical section, then only those processes that are not
executing in their remainder section can participate in
deciding which will enter in the critical section next,
and the selection can not be postponed indefinitely.
Bounded Waiting: A bound must exist 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.
ABINAYA.R / AP / CSE / SRIT
Semaphores
Semaphoresareintegervariablesthatareusedtosolvethecriticalsection
problembyusingtwoatomicoperations,waitandsignalthatareused
forprocesssynchronization.
WaitThewaitoperationdecrementsthevalueofitsargumentS,ifitis
positive.IfSisnegativeorzero,thennooperationisperformed.(ENTRY
OPERATION)
wait(S)
{
while(S<=0);
S--;
}
ABINAYA.R / AP / CSE / SRIT
Semaphoresareintegervariablesthatareusedtosolvethecriticalsection
problembyusingtwoatomicoperations,waitandsignalthatareused
forprocesssynchronization.
WaitThewaitoperationdecrementsthevalueofitsargumentS,ifitis
positive.IfSisnegativeorzero,thennooperationisperformed.(ENTRY
OPERATION)
wait(S)
{
while(S<=0);
S--;
}
ABINAYA.R / AP / CSE / SRIT
Signal
The signal operation incrementsthe value of its
argument S.(EXIT OPERATION)
signal(S)
{
S++;
}
ABINAYA.R / AP / CSE / SRIT
The signal operation incrementsthe value of its
argument S.(EXIT OPERATION)
signal(S)
{
S++;
}
ABINAYA.R / AP / CSE / SRIT
Types of Semaphores
Therearetwomaintypesofsemaphoresi.e.counting
semaphoresandbinarysemaphores.
CountingSemaphores
BinarySemaphores
ABINAYA.R / AP / CSE / SRIT
Therearetwomaintypesofsemaphoresi.e.counting
semaphoresandbinarysemaphores.
CountingSemaphores
BinarySemaphores
ABINAYA.R / AP / CSE / SRIT
Counting Semaphores
Counting semaphoresare signaling integers that can
take on any integer value. Using theseSemaphoreswe
can coordinate access to resources and here
theSemaphorecount is the number of resources
available. If the value of theSemaphoreis anywhere
above0, processes can access the critical section, or the
shared resources. However, if the value is0, it means
that there aren't any resources that are available or
thecritical sectionis already being accessed by a
number of processes and cannot be accessed by more
processes.Counting semaphores are generally used
when the number of instances of a resource are more
than1, and multiple processes can access the
resource.
ABINAYA.R / AP / CSE / SRIT
Counting semaphoresare signaling integers that can
take on any integer value. Using theseSemaphoreswe
can coordinate access to resources and here
theSemaphorecount is the number of resources
available. If the value of theSemaphoreis anywhere
above0, processes can access the critical section, or the
shared resources. However, if the value is0, it means
that there aren't any resources that are available or
thecritical sectionis already being accessed by a
number of processes and cannot be accessed by more
processes.Counting semaphores are generally used
when the number of instances of a resource are more
than1, and multiple processes can access the
resource.
ABINAYA.R / AP / CSE / SRIT
Binary Semaphores
In these type ofSemaphoresthe integer value of the
semaphore can only be either0or1. If the value of
theSemaphoreis1, it means that the process can
proceed to thecritical section(the common section that
the processes need to access). However,if the value of
binary semaphore is0, then the process cannot
continue to thecritical sectionof the code. When a
process is using thecritical sectionof the code, we
change theSemaphorevalue to0, and when a process
is not using it, or we can allow a process to access
thecritical section, we change the value of semaphore
to1.Binary semaphore is also calledmutex lock.
ABINAYA.R / AP / CSE / SRIT
In these type ofSemaphoresthe integer value of the
semaphore can only be either0or1. If the value of
theSemaphoreis1, it means that the process can
proceed to thecritical section(the common section that
the processes need to access). However,if the value of
binary semaphore is0, then the process cannot
continue to thecritical sectionof the code. When a
process is using thecritical sectionof the code, we
change theSemaphorevalue to0, and when a process
is not using it, or we can allow a process to access
thecritical section, we change the value of semaphore
to1.Binary semaphore is also calledmutex lock.
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
Advantages of Semaphores
Semaphores allow only one process into the critical section. They follow
the mutual exclusion principle strictly and are much more efficient than
some other methods of synchronization.
There is no resource wastage because of busy waiting in semaphores as
processor time is not wasted unnecessarily to check if a condition is
fulfilled to allow a process to access the critical section.
Semaphores are implemented in the machine independent code of the
microkernel. So they are machine independent.
Disadvantages of Semaphores
Someofthedisadvantagesofsemaphoresareasfollows−
Semaphores are complicated so the wait and signal operations must be
implemented in the correct order to prevent deadlocks.
ABINAYA.R / AP / CSE / SRIT
Semaphores allow only one process into the critical section. They follow
the mutual exclusion principle strictly and are much more efficient than
some other methods of synchronization.
There is no resource wastage because of busy waiting in semaphores as
processor time is not wasted unnecessarily to check if a condition is
fulfilled to allow a process to access the critical section.
Semaphores are implemented in the machine independent code of the
microkernel. So they are machine independent.
Disadvantages of Semaphores
Someofthedisadvantagesofsemaphoresareasfollows−
Semaphores are complicated so the wait and signal operations must be
implemented in the correct order to prevent deadlocks.
ABINAYA.R / AP / CSE / SRIT
Classical Problems of Synchronization
1.Bounded Buffer (Producer-Consumer) Problem
2.Dining Philosophers Problem
3.The Readers Writers Problem
ABINAYA.R / AP / CSE / SRIT
1.Bounded Buffer (Producer-Consumer) Problem
2.Dining Philosophers Problem
3.The Readers Writers Problem
ABINAYA.R / AP / CSE / SRIT
Bounded Buffer Problem
There is a buffer of n slots and each slot is capable of
storing one unit of data. There are two processes
running, namely, producer and consumer, which are
operating on the buffer.
A producer tries to insert data into an empty slot of the
buffer. A consumer tries to remove data from a filled slot
in the buffer. As you might have guessed by now, those
two processes won't produce the expected output if they
are being executed concurrently.
There needs to be a way to make the producer and
consumer work in an independent manner.
ABINAYA.R / AP / CSE / SRIT
There is a buffer of n slots and each slot is capable of
storing one unit of data. There are two processes
running, namely, producer and consumer, which are
operating on the buffer.
A producer tries to insert data into an empty slot of the
buffer. A consumer tries to remove data from a filled slot
in the buffer. As you might have guessed by now, those
two processes won't produce the expected output if they
are being executed concurrently.
There needs to be a way to make the producer and
consumer work in an independent manner.
ABINAYA.R / AP / CSE / SRIT
Bounded Buffer Problem
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
One solution of this problem is to use semaphores. The
semaphores which will be used here are:
m, a binary semaphore which is used to acquire and
release the lock.
empty, a counting semaphore whose initial value is the
number of slots in the buffer, since, initially all slots are
empty.
full, a counting semaphore whose initial value is 0.
At any instant, the current value of empty represents
the number of empty slots in the buffer and full
represents the number of occupied slots in the buffer.
ABINAYA.R / AP / CSE / SRIT
semaphores which will be used here are:
m, a binary semaphore which is used to acquire and
release the lock.
empty, a counting semaphore whose initial value is the
number of slots in the buffer, since, initially all slots are
empty.
full, a counting semaphore whose initial value is 0.
At any instant, the current value of empty represents
the number of empty slots in the buffer and full
represents the number of occupied slots in the buffer.
ABINAYA.R / AP / CSE / SRIT
The Producer Operation
ABINAYA.R / AP / CSE / SRIT
do
{
// wait until empty > 0 and then decrement 'empty'
wait(empty);
// acquire lock
wait(mutex);
/* perform the insert operation in a slot */
// release lock
signal(mutex);
// increment 'full'
signal(full);
}
while(TRUE)
ABINAYA.R / AP / CSE / SRIT
do
{
// wait until empty > 0 and then decrement 'empty'
wait(empty);
// acquire lock
wait(mutex);
/* perform the insert operation in a slot */
// release lock
signal(mutex);
// increment 'full'
signal(full);
}
while(TRUE)
Looking at the above code for a producer, we can see
that a producer first waits until there is atleast one empty
slot.
Then it decrements theemptysemaphore because,
there will now be one less empty slot, since the producer
is going to insert data in one of those slots.
Then, it acquires lock on the buffer, so that the consumer
cannot access the buffer until producer completes its
operation.
After performing the insert operation, the lock is released
and the value offullis incremented because the
producer has just filled a slot in the buffer.
ABINAYA.R / AP / CSE / SRIT
that a producer first waits until there is atleast one empty
slot.
Then it decrements theemptysemaphore because,
there will now be one less empty slot, since the producer
is going to insert data in one of those slots.
Then, it acquires lock on the buffer, so that the consumer
cannot access the buffer until producer completes its
operation.
After performing the insert operation, the lock is released
and the value offullis incremented because the
producer has just filled a slot in the buffer.
ABINAYA.R / AP / CSE / SRIT
The Consumer Operation
do
{
// wait until full > 0 and then decrement 'full'
wait(full);
// acquire the lock
wait(mutex);
/* perform the remove operation in a slot */
// release the lock
signal(mutex);
// increment 'empty'
signal(empty);
}
while(TRUE);
ABINAYA.R / AP / CSE / SRIT
do
{
// wait until full > 0 and then decrement 'full'
wait(full);
// acquire the lock
wait(mutex);
/* perform the remove operation in a slot */
// release the lock
signal(mutex);
// increment 'empty'
signal(empty);
}
while(TRUE);
ABINAYA.R / AP / CSE / SRIT
The consumer waits until there is atleast one full slot in the
buffer.
Then it decrements thefullsemaphore because the number
of occupied slots will be decreased by one, after the
consumer completes its operation.
After that, the consumer acquires lock on the buffer.
Following that, the consumer completes the removal
operation so that the data from one of the full slots is
removed.
Then, the consumer releases the lock.
Finally, theemptysemaphore is incremented by 1, because
the consumer has just removed data from an occupied slot,
thus making it empty.
ABINAYA.R / AP / CSE / SRIT
buffer.
Then it decrements thefullsemaphore because the number
of occupied slots will be decreased by one, after the
consumer completes its operation.
After that, the consumer acquires lock on the buffer.
Following that, the consumer completes the removal
operation so that the data from one of the full slots is
removed.
Then, the consumer releases the lock.
Finally, theemptysemaphore is incremented by 1, because
the consumer has just removed data from an occupied slot,
thus making it empty.
ABINAYA.R / AP / CSE / SRIT
Dining Philosophers Problem
The dining philosophers problem is another classic
synchronization problem which is used to evaluate
situations where there is a need of allocating multiple
resources to multiple processes.
Consider there are five philosophers sitting around a
circular dining table. The dining table has five chopsticks
and a bowl of rice in the middle as shown in the below
figure.
ABINAYA.R / AP / CSE / SRIT
The dining philosophers problem is another classic
synchronization problem which is used to evaluate
situations where there is a need of allocating multiple
resources to multiple processes.
Consider there are five philosophers sitting around a
circular dining table. The dining table has five chopsticks
and a bowl of rice in the middle as shown in the below
figure.
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
At any instant, a philosopher is either eating or thinking.
When a philosopher wants to eat, he uses two chopsticks
-one from their left and one from their right. When a
philosopher wants to think, he keeps down both
chopsticks at their original place.
An array of five semaphores, stick[5], for each of the five
chopsticks.
ABINAYA.R / AP / CSE / SRIT
When a philosopher wants to eat, he uses two chopsticks
-one from their left and one from their right. When a
philosopher wants to think, he keeps down both
chopsticks at their original place.
An array of five semaphores, stick[5], for each of the five
chopsticks.
ABINAYA.R / AP / CSE / SRIT
while(TRUE)
{
wait(stick[i]);
/*
mod is used because if i=5, next
chopstick is 1 (dining table is circular)
*/
wait(stick[(i+1) % 5]);
/* eat */
signal(stick[i]);
signal(stick[(i+1) % 5]);
/* think */
}
ABINAYA.R / AP / CSE / SRIT
{
wait(stick[i]);
/*
mod is used because if i=5, next
chopstick is 1 (dining table is circular)
*/
wait(stick[(i+1) % 5]);
/* eat */
signal(stick[i]);
signal(stick[(i+1) % 5]);
/* think */
}
ABINAYA.R / AP / CSE / SRIT
When a philosopher wants to eat the rice, he will wait for the chopstick at
his left and picks up that chopstick. Then he waits for the right chopstick
to be available, and then picks it too. After eating, he puts both the
chopsticks down.
But if all five philosophers are hungry simultaneously, and each of them
pickup one chopstick, then a deadlock situation occurs because they will
be waiting for another chopstick forever. The possible solutions for this
are:
A philosopher must be allowed to pick up the chopsticks only if both the
left and right chopsticks are available.
Allow only four philosophers to sit at the table. That way, if all the four
philosophers pick up four chopsticks, there will be one chopstick left on
the table. So, one philosopher can start eating and eventually, two
chopsticks will be available. In this way, deadlocks can be avoided.
ABINAYA.R / AP / CSE / SRIT
his left and picks up that chopstick. Then he waits for the right chopstick
to be available, and then picks it too. After eating, he puts both the
chopsticks down.
But if all five philosophers are hungry simultaneously, and each of them
pickup one chopstick, then a deadlock situation occurs because they will
be waiting for another chopstick forever. The possible solutions for this
are:
A philosopher must be allowed to pick up the chopsticks only if both the
left and right chopsticks are available.
Allow only four philosophers to sit at the table. That way, if all the four
philosophers pick up four chopsticks, there will be one chopstick left on
the table. So, one philosopher can start eating and eventually, two
chopsticks will be available. In this way, deadlocks can be avoided.
ABINAYA.R / AP / CSE / SRIT
The Readers Writers Problem
In this problem there are some
processes(calledreaders) that only read the shared
data, and never change it, and there are other
processes(calledwriters) who may change the data in
addition to reading, or instead of reading it.
There are various type of readers-writers problem, most
centred on relative priorities of readers and writers.
The main complexity with this problem occurs from
allowing more than one reader to access the data at the
same time.
ABINAYA.R / AP / CSE / SRIT
In this problem there are some
processes(calledreaders) that only read the shared
data, and never change it, and there are other
processes(calledwriters) who may change the data in
addition to reading, or instead of reading it.
There are various type of readers-writers problem, most
centred on relative priorities of readers and writers.
The main complexity with this problem occurs from
allowing more than one reader to access the data at the
same time.
ABINAYA.R / AP / CSE / SRIT
There is a shared resource which should be accessed by
multiple processes. There are two types of processes in
this context. They arereaderandwriter. Any number
ofreaderscan read from the shared resource
simultaneously, but only onewritercan write to the
shared resource. When awriteris writing data to the
resource, no other process can access the resource.
Awritercannot write to the resource if there are non zero
number of readers accessing the resource at that time.
ABINAYA.R / AP / CSE / SRIT
multiple processes. There are two types of processes in
this context. They arereaderandwriter. Any number
ofreaderscan read from the shared resource
simultaneously, but only onewritercan write to the
shared resource. When awriteris writing data to the
resource, no other process can access the resource.
Awritercannot write to the resource if there are non zero
number of readers accessing the resource at that time.
ABINAYA.R / AP / CSE / SRIT
Here, we use one mutex m and a semaphore w. An
integer variable read_count is used to maintain the
number of readers currently accessing the resource. The
variable read_count is initialized to 0. A value of 1 is
given initially to m and w.
ABINAYA.R / AP / CSE / SRIT
integer variable read_count is used to maintain the
number of readers currently accessing the resource. The
variable read_count is initialized to 0. A value of 1 is
given initially to m and w.
ABINAYA.R / AP / CSE / SRIT
writerprocess
while(TRUE)
{
wait(w);
/* perform the write operation */
signal(w);
}
ABINAYA.R / AP / CSE / SRIT
while(TRUE)
{
wait(w);
/* perform the write operation */
signal(w);
}
ABINAYA.R / AP / CSE / SRIT
readerprocess
while(TRUE)
{
//acquire lock
wait(m);
read_count++;
if(read_count== 1)
wait(w);
//release lock
signal(m);
/* perform the reading operation */
// acquire lock
wait(m);
read_count--;
if(read_count== 0)
signal(w);
ABINAYA.R / AP / CSE / SRIT
while(TRUE)
{
//acquire lock
wait(m);
read_count++;
if(read_count== 1)
wait(w);
//release lock
signal(m);
/* perform the reading operation */
// acquire lock
wait(m);
read_count--;
if(read_count== 0)
signal(w);
ABINAYA.R / AP / CSE / SRIT
On the other hand, in the code for the reader, the lock is acquired
whenever theread_countis updated by a process.
When a reader wants to access the resource, first it increments
theread_countvalue, then accesses the resource and then decrements
theread_countvalue.
The semaphorewis used by the first reader which enters the critical
section and the last reader which exits the critical section.
The reason for this is, when the first readers enters the critical section,
the writer is blocked from the resource. Only new readers can access
the resource now.
Similarly, when the last reader exits the critical section, it signals the
writer using thewsemaphore because there are zero readers now and
a writer can have the chance to access the resource.
ABINAYA.R / AP / CSE / SRIT
whenever theread_countis updated by a process.
When a reader wants to access the resource, first it increments
theread_countvalue, then accesses the resource and then decrements
theread_countvalue.
The semaphorewis used by the first reader which enters the critical
section and the last reader which exits the critical section.
The reason for this is, when the first readers enters the critical section,
the writer is blocked from the resource. Only new readers can access
the resource now.
Similarly, when the last reader exits the critical section, it signals the
writer using thewsemaphore because there are zero readers now and
a writer can have the chance to access the resource.
ABINAYA.R / AP / CSE / SRIT
Monitor
Monitor in an operating systemis one method for
achieving process synchronization. Programming
languages help the monitor to accomplish mutual
exclusion between different activities in a
system.wait()andnotify()constructs are synchronization
functions that are available in the Java programming
language.
Monitors are a synchronization construct that were
created to overcome the problems caused by
semaphores such as timing errors.
ABINAYA.R / AP / CSE / SRIT
Monitor in an operating systemis one method for
achieving process synchronization. Programming
languages help the monitor to accomplish mutual
exclusion between different activities in a
system.wait()andnotify()constructs are synchronization
functions that are available in the Java programming
language.
Monitors are a synchronization construct that were
created to overcome the problems caused by
semaphores such as timing errors.
ABINAYA.R / AP / CSE / SRIT
Advantages of Monitor in OS
Monitors offer the benefit of making concurrent or parallel
programming easier and less error-prone than semaphore-
based solutions.
It helps in process synchronization in the operating system.
Monitors have built-in mutual exclusion.
Monitors are easier to set up than semaphores.
Monitors may be able to correct for the timing faults
thatsemaphores cause.
Disadvantages of Monitor in OS
Monitors must beimplementedwith the programming
language.
Monitor increases the compiler's workload.
ABINAYA.R / AP / CSE / SRIT
Monitors offer the benefit of making concurrent or parallel
programming easier and less error-prone than semaphore-
based solutions.
It helps in process synchronization in the operating system.
Monitors have built-in mutual exclusion.
Monitors are easier to set up than semaphores.
Monitors may be able to correct for the timing faults
thatsemaphores cause.
Disadvantages of Monitor in OS
Monitors must beimplementedwith the programming
language.
Monitor increases the compiler's workload.
ABINAYA.R / AP / CSE / SRIT
Deadlock in Operating
System
Everyprocessneedssomeresourcestocompleteits
execution.However,theresourceisgrantedina
sequentialorder.
1.Theprocessrequestsforsomeresource.
2.OSgranttheresourceifitisavailableotherwiseletthe
processwaits.
3.Theprocessusesitandreleaseonthecompletion.
ABINAYA.R / AP / CSE / SRIT
System
Everyprocessneedssomeresourcestocompleteits
execution.However,theresourceisgrantedina
sequentialorder.
1.Theprocessrequestsforsomeresource.
2.OSgranttheresourceifitisavailableotherwiseletthe
processwaits.
3.Theprocessusesitandreleaseonthecompletion.
ABINAYA.R / AP / CSE / SRIT
Deadlock
ADeadlockisasituationwhereeachofthecomputer
processwaitsforaresourcewhichisbeingassignedto
someanotherprocess.Inthissituation,noneofthe
processgetsexecutedsincetheresourceitneeds,is
heldbysomeotherprocesswhichisalsowaitingfor
someotherresourcetobereleased.
LetusassumethattherearethreeprocessesP1,P2and
P3.TherearethreedifferentresourcesR1,R2andR3.
R1isassignedtoP1,R2isassignedtoP2andR3is
assignedtoP3.
Aftersometime,P1demandsforR1whichisbeingused
byP2.P1haltsitsexecutionsinceitcan'tcomplete
withoutR2.P2alsodemandsforR3whichisbeingused
byP3.P2alsostopsitsexecutionbecauseitcan't
continuewithoutR3.P3alsodemandsforR1whichis
beingusedbyP1thereforeP3alsostopsitsexecution.
ABINAYA.R / AP / CSE / SRIT
ADeadlockisasituationwhereeachofthecomputer
processwaitsforaresourcewhichisbeingassignedto
someanotherprocess.Inthissituation,noneofthe
processgetsexecutedsincetheresourceitneeds,is
heldbysomeotherprocesswhichisalsowaitingfor
someotherresourcetobereleased.
LetusassumethattherearethreeprocessesP1,P2and
P3.TherearethreedifferentresourcesR1,R2andR3.
R1isassignedtoP1,R2isassignedtoP2andR3is
assignedtoP3.
Aftersometime,P1demandsforR1whichisbeingused
byP2.P1haltsitsexecutionsinceitcan'tcomplete
withoutR2.P2alsodemandsforR3whichisbeingused
byP3.P2alsostopsitsexecutionbecauseitcan't
continuewithoutR3.P3alsodemandsforR1whichis
beingusedbyP1thereforeP3alsostopsitsexecution.
ABINAYA.R / AP / CSE / SRIT
Necessary conditions for
Deadlocks
1.MutualExclusion
Aresourcecanonlybesharedinmutuallyexclusivemanner.It
implies,iftwoprocesscannotusethesameresourceatthesame
time.
1.HoldandWait
Aprocesswaitsforsomeresourceswhileholdinganotherresource
atthesametime.
1.Nopreemption
Theprocesswhichoncescheduledwillbeexecutedtillthe
completion.Nootherprocesscanbescheduledbythescheduler
meanwhile.
1.CircularWait
Alltheprocessesmustbewaitingfortheresourcesinacyclic
mannersothatthelastprocessiswaitingfortheresourcewhichis
beingheldbythefirstprocess.
ABINAYA.R / AP / CSE / SRIT
Deadlocks
1.MutualExclusion
Aresourcecanonlybesharedinmutuallyexclusivemanner.It
implies,iftwoprocesscannotusethesameresourceatthesame
time.
1.HoldandWait
Aprocesswaitsforsomeresourceswhileholdinganotherresource
atthesametime.
1.Nopreemption
Theprocesswhichoncescheduledwillbeexecutedtillthe
completion.Nootherprocesscanbescheduledbythescheduler
meanwhile.
1.CircularWait
Alltheprocessesmustbewaitingfortheresourcesinacyclic
mannersothatthelastprocessiswaitingfortheresourcewhichis
beingheldbythefirstprocess.
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
Methods of Handling Deadlocks in
Operating System
The first two methods are used to ensure the system never enters a deadlock.
Deadlock Prevention
This is done by restraining the ways a request can be made. Since deadlock occurs when all
the above four conditions are met, we try to prevent any one of them, thus preventing a
deadlock.
Deadlock Avoidance
When a process requests a resource, the deadlock avoidance algorithm examines the
resource-allocation state. If allocating that resource sends the system into an unsafe state,
the request is not granted.
Therefore, it requires additional information such as how many resources of each type is
required by a process. If the system enters into an unsafe state, it has to take a step back
to avoid deadlock.
ABINAYA.R / AP / CSE / SRIT
Operating System
The first two methods are used to ensure the system never enters a deadlock.
Deadlock Prevention
This is done by restraining the ways a request can be made. Since deadlock occurs when all
the above four conditions are met, we try to prevent any one of them, thus preventing a
deadlock.
Deadlock Avoidance
When a process requests a resource, the deadlock avoidance algorithm examines the
resource-allocation state. If allocating that resource sends the system into an unsafe state,
the request is not granted.
Therefore, it requires additional information such as how many resources of each type is
required by a process. If the system enters into an unsafe state, it has to take a step back
to avoid deadlock.
ABINAYA.R / AP / CSE / SRIT
Deadlock Detection and Recovery
We let the system fall into a deadlock and if it happens, we detect it
using a detection algorithm and try to recover.
Some ways of recovery are as follows.
Aborting all the deadlocked processes.
Abort one process at a time until the system recovers from the
deadlock.
Resource Preemption: Resources are taken one by one from a process
and assigned to higher priority processes until the deadlock is
resolved.
Deadlock Ignorance
In the method, the system assumes that deadlock never occurs. Since
the problem of deadlock situation is not frequent, some systems
simply ignore it. Operating systems such as UNIX and Windows follow
this approach. However, if a deadlock occurs we can reboot our
and the deadlock is resolved automatically.
ABINAYA.R / AP / CSE / SRIT
We let the system fall into a deadlock and if it happens, we detect it
using a detection algorithm and try to recover.
Some ways of recovery are as follows.
Aborting all the deadlocked processes.
Abort one process at a time until the system recovers from the
deadlock.
Resource Preemption: Resources are taken one by one from a process
and assigned to higher priority processes until the deadlock is
resolved.
Deadlock Ignorance
In the method, the system assumes that deadlock never occurs. Since
the problem of deadlock situation is not frequent, some systems
simply ignore it. Operating systems such as UNIX and Windows follow
this approach. However, if a deadlock occurs we can reboot our
and the deadlock is resolved automatically.
ABINAYA.R / AP / CSE / SRIT
Detection and Recovery:
If deadlocks do occur, the operating system must detect
and resolve them. Deadlock detection algorithms, such
as the Wait-For Graph, are used to identify deadlocks,
and recovery algorithms, such as the Rollback and Abort
algorithm, are used to resolve them. The recovery
algorithm releases the resources held by one or more
processes, allowing the system to continue to make
progress.
ABINAYA.R / AP / CSE / SRIT
If deadlocks do occur, the operating system must detect
and resolve them. Deadlock detection algorithms, such
as the Wait-For Graph, are used to identify deadlocks,
and recovery algorithms, such as the Rollback and Abort
algorithm, are used to resolve them. The recovery
algorithm releases the resources held by one or more
processes, allowing the system to continue to make
progress.
ABINAYA.R / AP / CSE / SRIT
1. If resources have a single instance –
In this case for Deadlock detection, we can run an algorithm to check for the cycle in the
Resource Allocation Graph. The presence of a cycle in the graph is a sufficient condition for
deadlock.
In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1 →
P1 → R2 → P2. So, Deadlock is Confirmed.
ABINAYA.R / AP / CSE / SRIT
In this case for Deadlock detection, we can run an algorithm to check for the cycle in the
Resource Allocation Graph. The presence of a cycle in the graph is a sufficient condition for
deadlock.
In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1 →
P1 → R2 → P2. So, Deadlock is Confirmed.
ABINAYA.R / AP / CSE / SRIT
2. If there are multiple instances of resources –
Detection of the cycle is necessary but not sufficient condition for deadlock detection, in
this case, the system may or may not be in deadlock varies according to different
situations.
Deadlock Recovery :
A traditional operating system such as Windows doesn’t deal with deadlock recovery as it is
a time and space-consuming process. Real-time operating systems use Deadlock recovery.
Killing the process –
Killing all the processes involved in the deadlock. Killing process one by one. After killing
each process check for deadlock again keep repeating the process till the system recovers
from deadlock. Killing all the processes one by one helps a system to break circular wait
condition.
Resource Preemption –
Resources are preempted from the processes involved in the deadlock, preempted
resources are allocated to other processes so that there is a possibility of recovering the
system from deadlock. In this case, the system goes into starvation.
ABINAYA.R / AP / CSE / SRIT
Detection of the cycle is necessary but not sufficient condition for deadlock detection, in
this case, the system may or may not be in deadlock varies according to different
situations.
Deadlock Recovery :
A traditional operating system such as Windows doesn’t deal with deadlock recovery as it is
a time and space-consuming process. Real-time operating systems use Deadlock recovery.
Killing the process –
Killing all the processes involved in the deadlock. Killing process one by one. After killing
each process check for deadlock again keep repeating the process till the system recovers
from deadlock. Killing all the processes one by one helps a system to break circular wait
condition.
Resource Preemption –
Resources are preempted from the processes involved in the deadlock, preempted
resources are allocated to other processes so that there is a possibility of recovering the
system from deadlock. In this case, the system goes into starvation.
ABINAYA.R / AP / CSE / SRIT
Thank you
ABINAYA.R / AP / CSE / SRIT
ABINAYA.R / AP / CSE / SRIT
Tags
Categories
BusinessDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 58
- Slides 108
- Age 527 days
Related Slideshows
1
DTI BPI Pivot Small Business - BUSINESS START UP PLAN
MeljunCortes
28 views
1
CATHOLIC EDUCATIONAL Corporate Responsibilities
MeljunCortes
30 views
11
Karin Schaupp – Evocation; lançamento: 2000
alfeuRIO
28 views
10
Pillars of Biblical Oneness in the Book of Acts
JanParon
26 views
31
7-10. STP + Branding and Product & Services Strategies.pptx
itsyash298
27 views
44
Business Legislation PPT - UNIT 1 jimllpkggg
slogeshk98
29 views