Short Notes: Process Management - Concurrency | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


A sequential program has a single thread of control. Its execution is called a 
process. A concurrent program has multiple threads of control. They may be 
executed as parallel processes. This lesson presents main principles of concurrent 
programming. A concurrent program can be executed by
• Multiprogramming: processes share one or more processors
• Multiprocessing: each process runs on its own processor but with shared 
memory
• Distributed processing: each process runs on its own processor connected by 
a network to others
Properties of Concurrent Processes
Concurrent programs are governed by two key principles. These are the principles 
of "safety" and "liveness".
• The "safety" principle states "nothing bad can happen".
• The "liveness" principle states "eventually, something good happens".
Safety
Safety in general means that only one thread can access the data at a time, and 
ensures that the data remain in a consistent state during and after the operation. 
Supopose, functions "A" and "B" below run concurrently. What is a resultant value of 
"x"? var x = 0; function A() {x = x + 1;} function B() {x = x + 2;} •
• x = 3 if operations x = x + 1 and x = x + 2 are atomic, i.e. cannot be 
interrupted.
• x = 1,2 or 3 if operations x = x + 1 and x = x + 2 can interrupt one another.
Page 2


A sequential program has a single thread of control. Its execution is called a 
process. A concurrent program has multiple threads of control. They may be 
executed as parallel processes. This lesson presents main principles of concurrent 
programming. A concurrent program can be executed by
• Multiprogramming: processes share one or more processors
• Multiprocessing: each process runs on its own processor but with shared 
memory
• Distributed processing: each process runs on its own processor connected by 
a network to others
Properties of Concurrent Processes
Concurrent programs are governed by two key principles. These are the principles 
of "safety" and "liveness".
• The "safety" principle states "nothing bad can happen".
• The "liveness" principle states "eventually, something good happens".
Safety
Safety in general means that only one thread can access the data at a time, and 
ensures that the data remain in a consistent state during and after the operation. 
Supopose, functions "A" and "B" below run concurrently. What is a resultant value of 
"x"? var x = 0; function A() {x = x + 1;} function B() {x = x + 2;} •
• x = 3 if operations x = x + 1 and x = x + 2 are atomic, i.e. cannot be 
interrupted.
• x = 1,2 or 3 if operations x = x + 1 and x = x + 2 can interrupt one another.
If we read/modify/write a file and allow operations to interrupt one annother, the 
file might be easily corrupted. Safety is ensured by implementing
• "mutual exclusion" and
• "condition synchronization"
when operating on shared data. "Mutual exclusion" means that that only one thread 
can access the data at a time, and ensures that the data remain in a consistent 
state during and after the operation, (atomic update). "Condition synchronization" 
means that operations may be delayed if shared resources are in the wrong state 
(e.g., read from empty buffer).
Liveness
Mutual exclusion solves many safety issues, but gives rise to other problems, in 
particular deadlock and starvation. The problem of deadlock arises when a thread 
holds a lock on one object and blocks attempting to gain a lock on another object, 
because the second object is already locked by a different thread, which is blocked 
by the lock the original thread currently holds.
Both threads settle down to wait for the other to release the necessary lock, but 
neither thread will ever release their own lock because they are both blocked 
waiting for the other lock to be released first. Stated like this, it may seem an 
unlikely occurrence, but in fact, deadlock is one of the most common concurrent 
programming bugs. The trouble is that deadlock spreads out through more than 
two threads and can involve complex interdependencies. Deadlock is an extreme 
form of starvation. Starvation occurs when a thread cannot proceed because it 
cannot gain access to a resource it requires.
e m p ty b u ffe r IN .
W a it ! ^
if (e m p ty b u ffer) w a it;
No processes
to fill b u ffe r I
The problems of deadlock and starvation bring us to the next big topic in
Page 3


A sequential program has a single thread of control. Its execution is called a 
process. A concurrent program has multiple threads of control. They may be 
executed as parallel processes. This lesson presents main principles of concurrent 
programming. A concurrent program can be executed by
• Multiprogramming: processes share one or more processors
• Multiprocessing: each process runs on its own processor but with shared 
memory
• Distributed processing: each process runs on its own processor connected by 
a network to others
Properties of Concurrent Processes
Concurrent programs are governed by two key principles. These are the principles 
of "safety" and "liveness".
• The "safety" principle states "nothing bad can happen".
• The "liveness" principle states "eventually, something good happens".
Safety
Safety in general means that only one thread can access the data at a time, and 
ensures that the data remain in a consistent state during and after the operation. 
Supopose, functions "A" and "B" below run concurrently. What is a resultant value of 
"x"? var x = 0; function A() {x = x + 1;} function B() {x = x + 2;} •
• x = 3 if operations x = x + 1 and x = x + 2 are atomic, i.e. cannot be 
interrupted.
• x = 1,2 or 3 if operations x = x + 1 and x = x + 2 can interrupt one another.
If we read/modify/write a file and allow operations to interrupt one annother, the 
file might be easily corrupted. Safety is ensured by implementing
• "mutual exclusion" and
• "condition synchronization"
when operating on shared data. "Mutual exclusion" means that that only one thread 
can access the data at a time, and ensures that the data remain in a consistent 
state during and after the operation, (atomic update). "Condition synchronization" 
means that operations may be delayed if shared resources are in the wrong state 
(e.g., read from empty buffer).
Liveness
Mutual exclusion solves many safety issues, but gives rise to other problems, in 
particular deadlock and starvation. The problem of deadlock arises when a thread 
holds a lock on one object and blocks attempting to gain a lock on another object, 
because the second object is already locked by a different thread, which is blocked 
by the lock the original thread currently holds.
Both threads settle down to wait for the other to release the necessary lock, but 
neither thread will ever release their own lock because they are both blocked 
waiting for the other lock to be released first. Stated like this, it may seem an 
unlikely occurrence, but in fact, deadlock is one of the most common concurrent 
programming bugs. The trouble is that deadlock spreads out through more than 
two threads and can involve complex interdependencies. Deadlock is an extreme 
form of starvation. Starvation occurs when a thread cannot proceed because it 
cannot gain access to a resource it requires.
e m p ty b u ffe r IN .
W a it ! ^
if (e m p ty b u ffer) w a it;
No processes
to fill b u ffe r I
The problems of deadlock and starvation bring us to the next big topic in
concurrent programming - liveness. Concurrent programs are also described as 
having a 'liveness’ property if there are:
• No Deadlock: some process can always access a shared resource
• No Starvation: all processes can eventually access shared resources
The liveness property states that eventually something good happens. Deadlocked 
programs don’t meet this requirement. Liveness is gradational. Programs can be 
'nearly' dead or 'not very’ live. Every time you use a synchronized method, you force 
sequential access to an object. If you have a lot of threads calling a lot of 
synchronized methods on the same object, your program will slow down a lot. A 
programming language must provide mechanisms for Expressing Concurrency:
• Process creation how do you specify concurrent processes?
• Communication: how do processes exchange information?
• Synchronization: how do processes maintain consistency?
Process creation
Most concurrent languages offer some variant of the following Process Creation 
mechanisms:
• Co-routines how do you specify concurrent processes?
• Fork and Join: how do processes exchange information?
• Cobegin/coend: how do processes maintain consistency?
Co-routines are only pseudo-concurrent and require explicit transfers of control:
Co-routines can be used to implement most higher-level concurrent mechanisms. 
Fork can be used to create any number of processes:
K
f u n c t i o n A ( )
h -
l f o i k ( B ( ) ) ; 
j j o i n [ B [ ] ] ;
f u n c t i o n B ( ) 
V o i k ( C j J );
r->®
f u n c t i o n C [ ] 
{ ¦ ¦ ¦
-V
J L
c
B
A
^ --------------------------------------M
1 2 (t3)
Join waits for another process to terminate. Fork and join are unstructured, so
Page 4


A sequential program has a single thread of control. Its execution is called a 
process. A concurrent program has multiple threads of control. They may be 
executed as parallel processes. This lesson presents main principles of concurrent 
programming. A concurrent program can be executed by
• Multiprogramming: processes share one or more processors
• Multiprocessing: each process runs on its own processor but with shared 
memory
• Distributed processing: each process runs on its own processor connected by 
a network to others
Properties of Concurrent Processes
Concurrent programs are governed by two key principles. These are the principles 
of "safety" and "liveness".
• The "safety" principle states "nothing bad can happen".
• The "liveness" principle states "eventually, something good happens".
Safety
Safety in general means that only one thread can access the data at a time, and 
ensures that the data remain in a consistent state during and after the operation. 
Supopose, functions "A" and "B" below run concurrently. What is a resultant value of 
"x"? var x = 0; function A() {x = x + 1;} function B() {x = x + 2;} •
• x = 3 if operations x = x + 1 and x = x + 2 are atomic, i.e. cannot be 
interrupted.
• x = 1,2 or 3 if operations x = x + 1 and x = x + 2 can interrupt one another.
If we read/modify/write a file and allow operations to interrupt one annother, the 
file might be easily corrupted. Safety is ensured by implementing
• "mutual exclusion" and
• "condition synchronization"
when operating on shared data. "Mutual exclusion" means that that only one thread 
can access the data at a time, and ensures that the data remain in a consistent 
state during and after the operation, (atomic update). "Condition synchronization" 
means that operations may be delayed if shared resources are in the wrong state 
(e.g., read from empty buffer).
Liveness
Mutual exclusion solves many safety issues, but gives rise to other problems, in 
particular deadlock and starvation. The problem of deadlock arises when a thread 
holds a lock on one object and blocks attempting to gain a lock on another object, 
because the second object is already locked by a different thread, which is blocked 
by the lock the original thread currently holds.
Both threads settle down to wait for the other to release the necessary lock, but 
neither thread will ever release their own lock because they are both blocked 
waiting for the other lock to be released first. Stated like this, it may seem an 
unlikely occurrence, but in fact, deadlock is one of the most common concurrent 
programming bugs. The trouble is that deadlock spreads out through more than 
two threads and can involve complex interdependencies. Deadlock is an extreme 
form of starvation. Starvation occurs when a thread cannot proceed because it 
cannot gain access to a resource it requires.
e m p ty b u ffe r IN .
W a it ! ^
if (e m p ty b u ffer) w a it;
No processes
to fill b u ffe r I
The problems of deadlock and starvation bring us to the next big topic in
concurrent programming - liveness. Concurrent programs are also described as 
having a 'liveness’ property if there are:
• No Deadlock: some process can always access a shared resource
• No Starvation: all processes can eventually access shared resources
The liveness property states that eventually something good happens. Deadlocked 
programs don’t meet this requirement. Liveness is gradational. Programs can be 
'nearly' dead or 'not very’ live. Every time you use a synchronized method, you force 
sequential access to an object. If you have a lot of threads calling a lot of 
synchronized methods on the same object, your program will slow down a lot. A 
programming language must provide mechanisms for Expressing Concurrency:
• Process creation how do you specify concurrent processes?
• Communication: how do processes exchange information?
• Synchronization: how do processes maintain consistency?
Process creation
Most concurrent languages offer some variant of the following Process Creation 
mechanisms:
• Co-routines how do you specify concurrent processes?
• Fork and Join: how do processes exchange information?
• Cobegin/coend: how do processes maintain consistency?
Co-routines are only pseudo-concurrent and require explicit transfers of control:
Co-routines can be used to implement most higher-level concurrent mechanisms. 
Fork can be used to create any number of processes:
K
f u n c t i o n A ( )
h -
l f o i k ( B ( ) ) ; 
j j o i n [ B [ ] ] ;
f u n c t i o n B ( ) 
V o i k ( C j J );
r->®
f u n c t i o n C [ ] 
{ ¦ ¦ ¦
-V
J L
c
B
A
^ --------------------------------------M
1 2 (t3)
Join waits for another process to terminate. Fork and join are unstructured, so
require care and discipline. Cobegin/coend blocks are better structured, but they 
can only create a fixed number of processes.
function A [ ] 
(tf)cobegin{B [ ] II C[ ]};
T -> ___
K K
function B[ ) function C ( )
{¦¦¦ {
ftzi
L
^---------------Kt
[13]
The caller continues when all of the co-blocks have terminated.