Concurrency and

Process Synchronization
 Process Synchronization Cooperating Processes

• Independent process cannot affect or be affected by

the execution of another process.
• Cooperating process can affect or be affected by the
execution of another process
• Advantages of process cooperation
✓Information sharing
❑Allow concurrent access to data sources
✓Computation speed-up
❑Sub-tasks can be executed in parallel
✓Modularity
❑System functions can be divided into separate processes or threads
• Convenience

Operating System: Process Synchronization 2

 Process Synchronization Process Interaction and Concurrency

• Concurrency can be viewed at different levels:

✓ multiprogramming — interaction between multiple processes running on one CPU
(pseudo-parallelism)
Software
view

✓ multithreading — interaction between multiple threads running in one process

✓ multiprocessors — interaction between multiple CPUs running multiple

Hardware

processes/threads (real parallelism)

view

✓ multicomputers — interaction between multiple computers running distributed

processes/threads

→ the principles of concurrency are basically the same in all of these categories

Operating System: Process Synchronization 3

 Process Synchronization Process Interaction

• Whether processes or threads: three basic interactions

o Competition-processes unaware of each other -
✓ they must use shared resources P1 P2

independently, without interfering, and leave

them intact for the others
resource

o Cooperation by sharing-processes indirectly aware

of each other P1 P2

✓ they work on common data and build some result

together via the data
data

o Cooperation by communication-processes directly

aware of each other
✓ they cooperate by communicating, e.g., exchanging P1 P2

messages
messages

Operating System: Process Synchronization 4

 Process Synchronization Context Switches can Happen at Any time

• A process switch (full context switch) can happen at

any time there is a mode switch into the kernel
• This could be because of a:
✓System call (semi-predictable)
✓Timer (round robin, etc.)
✓I/O interrupt (unblock some other process)
✓Other interrupt, etc.
• The programmer generally cannot predict at what
point in a program this might happen

Operating System: Process Synchronization 5

 Process Synchronization Preemption is Unpredictable

• This means that the program’s work can be interrupted at any

time (I.e. just after the completion of any instruction):
✓Some other program gets to run for a while
✓And the interrupted program eventually gets restarted
exactly where it left off.
✓After the other program (process) executes other
instructions that we have no control over
• This can lead to trouble if processes are not independent

Operating System: Process Synchronization 6

 Process Synchronization Problems with Concurrent Execution

• Concurrent processes (or threads) often need to

share data (maintained either in shared memory or
files) and resources
• If there is no controlled access to shared data,
execution of the processes on these data can
interleave.
• The results will then depend on the order in which
data were modified
• i.e. the results are non-deterministic.

Operating System: Process Synchronization 7

 Process Synchronization Bounded-Buffer

• Producer process Consumer process

item nextProduced; item nextConsumed;

while (1) while (1)

{ {
while (counter == BUFFER_SIZE); /* do while (counter == 0); /* do nothing
nothing nextConsumed = buffer[out];
buffer[in] = nextProduced; out = (out + 1) % BUFFER_SIZE;
in = (in + 1) % BUFFER_SIZE; counter--;
counter++;
}
}

The statements
counter++;
counter--;
must be performed atomic
Atomic operation means an operation that completes in its entirety without
interruption.

Operating System: Process Synchronization 8

 Process Synchronization Bounded-Buffer

• Although “P” and “C” routines are logically correct in themselves,

they may not work correctly running concurrently.
• The counter variable is shared between the two processes
• When ++counter and --count are done concurrently, the results are
unpredictable because the operations are not atomic
• Assume ++counter, --counter compiles as follows:
• ++counter --counter
register1 = counter register2 = counter
register1 = register1 + 1 register2 = register2 - 1
counter = register1 counter = register2

• If both the producer and consumer attempt to update the buffer

concurrently, the assembly language statements may get interleaved.
• Interleaving depends upon how the producer and consumer
processes are scheduled
.
• P and C get unpredictable access to CPU due to time slicing

Operating System: Process Synchronization 9

 Process Synchronization Bounded Buffer Analysis

• Assume counter is initially 5. One interleaving of statements

is:
producer: register1 = counter (register1 = 5)
producer: register1 = register1 + 1 (register1 = 6)
consumer: register2 = counter (register2 = 5)
consumer: register2 = register2 – 1 (register2 = 4)
producer: counter = register1 (counter = 6)
consumer: counter = register2 (counter = 4)

• The value of count may be either 4 or 6, where the correct

result should be 5.

• A situation such as this, where processes “race” against each

other, causing possible errors, is called a race condition.

Operating System: Process Synchronization 10

 Process Synchronization Bounded Buffer Analysis-Example(Bank Account)

A joint account. Each account holder accesses money at the same time – one
deposits, the other withdraws.

The bank’s computer is executing the routine below simultaneously as two

processes running the same transaction processing program

void update(acct,amount)
{
temp = getbalance(acct);
temp += amount;
putbalance(acct,temp);
}

Operating System: Process Synchronization 11

 Process Synchronization Bounded Buffer Analysis-Example(Bank Account)

void update(acct,amount)
Initial balance = Rs.60 {
B’s deposit = Rs.100 temp = getbalance(acct);
A’s withdrawal = Rs.50 temp += amount;
Net balance = Rs.110 putbalance(acct,amount);
}

A’s process: B’s process:

temp = 60
Process Switch!
temp = 60
temp = 60 + 100
putbalance (160)
Process Switch!
temp = 60 - 50
putbalance (10)
What is the final bank balance?
Operating System: Process Synchronization 12
 Process Synchronization Race Conditions

• Race condition: The situation where several processes access –

and manipulate shared data concurrently. The final value of
the shared data depends upon which process finishes last.
• Definition: a timing dependent error involving shared state
• Can be very bad
✓ “non-deterministic:” don’t know what the output will be, and it is likely
to be different across runs
✓ Hard to detect: too many possible schedules
✓ Hard to debug: “heisenbug,” debugging changes timing so hides bugs
(vs “bohr bug”)
• 2 or more processes are reading/writing shared data and the
final result depends on the order the processes have run
• To prevent race conditions, concurrent processes must be
synchronized.

Operating System: Process Synchronization 13

 Process Synchronization Critical Section

• That part of the program where shared resources are

accessed

• When a process executes code that manipulates

shared data (or resource), we say that the process is
in a critical section (CS) (for that resource)

• Entry and exit sections (small pieces of code) guard

the critical section

Operating System: Process Synchronization 14

 Process Synchronization The Critical Section Problem

• CS’s can be thought of as sequences of instructions

that are ‘tightly bound’ so no other process should
interfere via interleaving or parallel execution.

• The execution of CS’s must be mutually exclusive: At

any time, only one process should be allowed to
execute in a CS (even with multiple CPUs)

• Therefore we need a system where each process

must request permission to enter its CS, and we
need a means to “administer” this

Operating System: Process Synchronization 15

 Process Synchronization The Critical Section Problem

• The section of code implementing this request is

called the entry section
• The critical section (CS) will be followed by an
exit section, which opens the possibility of other
processes entering their CS.
• The remaining code is the remainder section RS
• The critical section problem is to design the
processes so that their results will not depend
on the order in which their execution is
interleaved.
• We must also prevent deadlock and starvation.

Operating System: Process Synchronization 16

 Process Synchronization Framework for analysis of solutions

• Each process executes at • Several CPUs may be

nonzero speed but no present but memory
assumption on the relative hardware prevents
speed of n processes simultaneous access to the
• General structure of a same memory location
process: • No assumptions about
order of interleaved
execution

repeat
• The central problem is to
entry section
design the entry and exit
critical section sections
exit section
remainder section
forever
Operating System: Process Synchronization 17
 Requirements for Valid solution to Critical Section
Process Synchronization Problem

• Mutual Exclusion: At any time, at most one process

can be executing critical section (CS) code
• Progress: If no process is in its CS and there are one
or more processes that wish to enter their CS, this
selection cannot be postponed indefinitely
✓no process in its remainder section can participate in this
decision
• Bounded Waiting: After a process P has made a
request to enter its CS, there is a limit on the
number of times that the other processes are
allowed to enter their CS, before P’s request is
granted
✓(otherwise the process could suffer from starvation)

Operating System: Process Synchronization 18

 Process Synchronization Solution to Critical Section problem

• Mutual exclusion must be enforced: Only one process at a time is allowed into the
critical section (CS)
• A process that halts in its noncritical section must do so without interfering with
other processes
• It must not be possible for a process requiring access to a CS to be delayed
indefinitely: no deadlock or starvation.
• When no process is in a critical section, any process that requests entry to its CS
must be permitted to enter without delay.
• No assumptions are made about relative process speeds or number of processors.
• A process remains inside its CS for a finite time only.
• No two processes may be simultaneously inside their critical sections.
• No assumptions may be made about speeds or the numbers of CPUs
• No process running outside its CS may block other processes from entering their
CS’s
• No process should have to wait forever to enter its CS

Operating System: Process Synchronization 19

 Process Synchronization Layered approach to synchronization

• Hardware provides simple low-level atomic operations,

upon which we can build high-level, synchronization
primitives, upon which we can implement critical sections
and build correct multi-threaded/multi-process programs

Operating System: Process Synchronization 20

 Process Synchronization Types of Solutions

• No special OS mechanisms (software approach.)

✓ algorithms whose correctness relies only on the assumption that only
one process at a time can access a memory location
• Hardware solutions
✓ Low-level atomic operations
✓ On uniprocessor, disable/enable interrupt
✓ x86 load and store of words
✓ Special instructions:
❑ test-and-set, compare-and-swap
• Operating System and Programming Language solutions (e.g.
Java)
✓ provide specific functions and data structures for the programmer to use
for synchronization
✓ High-level synchronization primitives
❑ Lock
❑ Semaphore
❑ Monitor

Operating System: Process Synchronization 21

 Bibliography
❖ Silberschatz, A, Galvin, P.B, and Gagne, G., Operating System
Principles, 9e, John Wiley & Sons, 2013.
❖ Stallings W., Operating Systems-Internals and Design Principles, 7e,
Pearson Education, 2014.
❖ Harvey M. Deital, “Operating System”, Third Edition, Pearson
Education, 2013.
❖ Andrew S. Tanenbaum, “Modern Operating Systems”, Second
Edition, Pearson Education, 2004.
❖ Gary Nutt, “Operating Systems”, Third Edition, Pearson Education,
2004.
 Acknowledgements
❖I have drawn materials from various sources such as mentioned in
bibliography or resources publicly available on Internet to prepare this
presentation.
❖I sincerely acknowledge all sources, their contributions and extend my
courtesy to use their contribution and knowledge for educational purpose.
Thank You!!
?