11/5/2021

M 317:
Operating Systems
Chapter 4: IPC

Dr. Rashad A. A. Ragb

[email protected]

Interprocess Communication

Interprocess communication

Deadlocks

Classic IPC Problems

1
 11/5/2021

Producer - Consumer Problem

Producer Consumer
Process Process
Produce Get from
buffer
Put in buffer Consume

BUFFER

Buffer is shared (ie., it is a shared variable)

Progress in time…..
Producer
p1 1 p2 2 p3 3 p4 4

Buffer
3 instead of 2!
Consume
r 1 c1 2 c2
t

Both processes are started at the same

time and consumer uses some old value
initially
4

2
 11/5/2021

A Race Condition

Because of the timing and which process

starts first

There is a chance that different executions
may end up with different results

Critical Sections

Critical Section
 A section of code in which the process
accesses and modifies shared variables

Mutual Exclusion
 A method of preventing for ensuring that one
(or a specified number) of processes are in a
critical section

3
 11/5/2021

Why Processes Need to

Communicate?

To synchronize their executions

To exchange data and information

Rules to Form
Critical Sections
1. No two processes may be simultaneously
inside their CS (mutual exclusion)
2. No assumptions are made about relative
process speeds or number of CPUs
3. A process outside a CS should not block
other processes
4. No process should wait forever before
entering its CS

4
 11/5/2021

Mutual Exclusion Problem Starvation

Definition
 Indefinitely delaying the scheduling of a process in favor
of other processes

Cause
 Usually a bias in a systems scheduling policies (a bad
scheduling algorithm)

Solution
 Implement some form of aging

Deadlocks (Another Problem )

 Two (or more) processes are blocked waiting for an

event that will never occur

 Generally, A waits for B to do something and B is

waiting for A

 Both are not doing anything so both events never

occur

10

5
 11/5/2021

How to Implement
Mutual Exclusion

Three possibilities
 Application: programmer builds some method
into the program
 Hardware: special h/w instructions provided
to implement ME
 OS: provides some services that can be used
by the programmer

All schemes rely on some code for
 enter_critical_section, and
 exit_critical_section

11

Application
Mutual Exclusion

Application Mutual Exclusion is
 implemented by the programmer
 hard to get correct, and very inefficient

All rely on some form of busy waiting
(process tests a condition, set a flag, and
loops while the condition remains the
same)

12

6
 11/5/2021

Example

Producer
produce
If lock = 1 loop until lock = 0
lock=1
put in buffer
lock=0

Consumer
If lock = 1 loop until lock = 0
lock=1
get from buffer
lock=0
consume

13

Hardware ME :
Test and Set Instruction

Perform an x:=r and r:=1

x is a local variable

r is a global register set to 0 initially

repeat (test-set(x)) until x = 0;

< critical section >
r:= 0;

14

7
 11/5/2021

Hardware ME :
Exchange Instruction

Exchange: swap the values of x and r

x is a local variable

r is a global register set to 1 initially

x:= 0;
repeat exchange(r, x) until x = 1;
< critical section >
exchange(r, x);

Note: r:= 0 and x:= 1 when the process is

in CS
15

Hardware ME Characteristics

Advantages
 can be used by a single or multiple processes
(with shared memory)
 simple and therefore easy to verify
 can support multiple critical sections

Disadvantages
 busy waiting is used
 starvation is possible
 deadlock is possible (especially with priorities)

16

8
 11/5/2021

Another Hardware ME :
Disabling Interrupts

On a single CPU only one process is executed

Concurrency is achieved by interleaving execution
(usually done using interrupts)

If you disable interrupts then you can be sure only
one process will ever execute

One process can lock a system or degrade
performance greatly

17

Mutual Exclusion
Through OS

Semaphores

Message passing

18

9
 11/5/2021

Semaphores

Major advance incorporated into many

modern operating systems (Unix, OS/2)

A semaphore is
 a non-negative integer
 that has two valid operations

19

Semaphore Operations

Wait(s)
If s > 0 then s:= s - 1
else block this process

Signal(s)
If there is a blocked process on this
semaphore then wake it up
else s:= s + 1

20

10
 11/5/2021

More on Semaphores

Two types of semaphores

 binary semaphores can only be 0 or 1
 counting semaphores can be any non-negative
integer

Semaphores are an OS service implemented
using one of the methods shown already
 usually by disabling interrupts for a very short time

21

Producer - Consumer Problem: Solution by

Semaphores

Produce Wait(mutex)
CS
Get from buffer
Wait(mutex) Signal(mutex)
Put in buffer
Signal(mutex) Consume

Initially semaphore mutex is 1

22

11
 11/5/2021

Another Example
• Three processes all share a resource on which
– one draws an A
– one draws a B
– one draws a C
• Implement a form of synchronization so that the output appears
ABC

Process Process Process

A B C
think(); think(); think();

draw_A(); draw_B(); draw_C();

23

Semaphore b = 0, c = 0;

Process A Process B Process C

wait(b);
think(); wait(c);
think();
draw_A(); think();
draw_B();
signal(b); draw_C();
signal(c);

24

12
 11/5/2021

Bounded-Buffer Problem

We need 3 semaphores:

1. we need a semaphore mutex to have mutual

exclusion on buffer access.
2. we need a semaphore full to synchronize producer
and consumer on the number of consumable
items.
3. we need a semaphore empty to synchronize
producer and consumer on the number of empty
spaces.

25

Bounded-Buffer - Semaphores

Shared data

semaphore full, empty, mutex;

Initially:

full = 0, empty = n, mutex = 1

26

13
 11/5/2021

Bounded-Buffer - Producer Process

do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);

27

Bounded-Buffer - Consumer Process

do {
wait(full)
wait(mutex);
…
remove item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);

28

14
 11/5/2021

Notes on Bounded-Buffer Solution

Remarks (from consumer point of view):

 Putting signal(empty) inside the CS of the
consumer (instead of outside) has no effect since
the producer must always wait for both semaphores
before proceeding.
 The consumer must perform wait(full) before
wait(mutex), otherwise deadlock occurs if
consumer enters CS while the buffer is empty.

Conclusion: using semaphores is a difficult art ...
☺

29

What is Deadlock?

Process Deadlock
 A process is deadlocked when it is
waiting on an event which will never
happen

System Deadlock
 A system is deadlocked when one or
more processes are deadlocked

30

15
 11/5/2021

Necessary Conditions for a Deadlock

Mutual Exclusion
 Shared resources are used in a
mutually exclusive manner

Hold & Wait
 Processes hold onto resources they
already have while waiting for the
allocation of other resources
31

Necessary Conditions for a Deadlock

(Cont.)

No Preemption
 Resources can not be preempted
until the process releases them

Circular Wait
 A circular chain of processes exists
in which each process holds
resources wanted by the next
process in the chain
32

16
 11/5/2021

No Deadlock Situation

If you can prevent at least one

of the necessary deadlock
conditions then you won’t
have a DEADLOCK

33

The Ostrich Algorithm

Pretend there is no problem

Reasonable if
 deadlocks occur very rarely
 cost of prevention is high

UNIX and Windows takes this approach

It is a trade off between
 convenience
 correctness

34

17
 11/5/2021

Ways of Handling Deadlock

Deadlock Prevention

Deadlock Detection

Deadlock Avoidance

Deadlock Recovery

35

Deadlock Prevention

Remove the possibility of deadlock

occurring by denying one of the four
necessary conditions:
 Mutual Exclusion (Can we share
everything?)
 Hold & Wait
 No preemption

 Circular Wait

36

18
 11/5/2021

Denying the
“Hold & Wait”

Implementation
 A process is given its resources on a
"ALL or NONE" basis
 Either a process gets ALL its required
resources and proceeds or it gets NONE
of them and waits until it can

37

Denying the
“Hold & Wait”

Advantages
 It works
 Reasonably easy to code

Problems
 Resource wastage
 Possibility of starvation

38

19
 11/5/2021

Denying “No preemption”

Implementation
 When a process is refused a resource
request, it MUST release all other
resources it holds
 Resources can be removed from a
process before it is finished with them

39

Denying “No preemption”

Advantages
 It works
 Possibly better resource utilization

Problems
 The cost of removing a process's
resources
 The process is likely to lose work it has
done. (How often does this occur?)
 Possibility of starvation

40

20
 11/5/2021

Denying “Circular Wait”

Implementation
 Resources are uniquely numbered
 Processes can only request
resources in linear ascending order
 Thus preventing the circular wait from
occurring

41

Denying “Circular Wait”

Advantages
 It works

Problems
 Resources must be requested in ascending order
of resource number rather than as needed
 Resource numbering must be maintained by
someone and must reflect every addition to the OS
 Difficult to sit down and just write code

42

21
 11/5/2021

Deadlock Avoidance

Allow the chance of deadlock occur

But avoid it happening..

Check whether the next state (change in

system) may end up in a deadlock situation

43

Banker's Algorithm

Definitions
 Each process has a LOAN, CLAIM,
MAXIMUM NEED

LOAN: current number of resources held

MAXIMUM NEED: total number resources
needed to complete

CLAIM: = (MAXIMUM - LOAN)

44

22
 11/5/2021

Banker’s Problem

Customer Max. Need Present Loan Claim

c1 800 410 390

c2 600 210 390

Suppose total bank capital is $1000

Current cash: 1000-(410+210)=380

45

Assumptions

Establish a LOAN ceiling (MAXIMUM NEED)
for each process
 MAXIMUM NEED < total number of resources available
(ie., capital)

Total loans for a process must be less than or
equal to MAXIMUM NEED

Loaned resources must be returned back in
finite time

46

23
 11/5/2021

Algorithm
1. Search for a process with a claim that can be
satisfied using the current number of remaining
resources (ie., tentatively grant the claim)
2. If such a process is found then assume that it will
return the loaned resources.
3. Update the number of remaining resources
4. Repeat steps 1-3 for all processes and mark
them

47

Algorithm

DO NOT GRANT THE CLAIM if at least one

process can not be marked.

Implementation
 A resource request is only allowed if it results in a
SAFE state
 The system is always maintained in a SAFE state
so eventually all requests will be filled

48

24
 11/5/2021

Algorithm

Advantages
 Allows jobs to proceed when a prevention algorithm
wouldn't

Problems
 Requires there to be a fixed number of resources
 What happens if a resource goes down?
 Does not allow the process to change its Maximum
need while processing

49

Classical IPC Problems

Readers and writers problem
 Models access to a database (both read and
write)

Dining philosophers problem
 Models processes competing for exclusive access
to a limited number of resources such as I/O
devices

Sleeping barber problem
 Models queuing situations such as a multi-person
helpdesk with a computerized call waiting system
for holding a limited number of incoming calls
50

25
 11/5/2021

Readers-Writers Problem

Any number of reader activities and writer
activities are running.

At any time, a reader activity may wish to read
data.

At any time, a writer activity may want to
modify the data.

Any number of readers may access the data
simultaneously.

During the time a writer is writing, no other
reader or writer may access the shared data.

51

Readers-Writers with active readers

52

26
 11/5/2021

Readers-Writers with an active writer

53

Should readers wait for waiting writer?

54

27
 11/5/2021

Readers-Writers problem
1. The first readers-writers problem, requires that
no reader will be kept waiting unless a writer
has obtained access to the shared data.
2. The second readers-writers problem, requires
that once a writer is ready, no new readers may
start reading.
3. In a solution to the first case writers may
starve; In a solution to the second case readers
may starve.

55

First Readers-Writers Solution

readcount counter keeps track of how many

processes are currently reading.

mutex semaphore provides mutual exclusion
for updating readcount.

wrt semaphore provides mutual exclusion for
the writers; it is also used by the first or last
reader that enters or exits the CS.

56

28
 11/5/2021

Dining Philosophers Problem

Five philosophers are seated
around a circular table.

In front of each one is a bowl
of rice.

Between each pair of people
there is a chopstick (fork), so
there are five chopsticks.

It takes two chopsticks
(forks?) to eat rice, so while n
is eating neither n+1 nor n-1
can be eating.

57

Dining Philosophers Problem

Each one thinks for a while, gets the

chopsticks needed, eats, and puts the
chopsticks down again, in an endless
cycle.

Illustrates the difficulty of allocating
resources among process without
deadlock and starvation.

58

29
 11/5/2021

Dining Philosophers Problem

The challenge is to grant requests for

chopsticks while avoiding deadlock and
starvation.

Deadlock can occur if everyone tries to get
their chopsticks at once. Each gets a left
chopstick, and is stuck, because each right
chopstick is someone else’s left chopstick.

59

Dining Philosophers Solution

Each philosopher Process Pi:
is a process. repeat

One semaphore think;
per fork: wait(fork[i]);
 fork: array[0..4]
wait(fork[i+1 mod 5]);
of semaphores eat;
signal(fork[i+1 mod 5]);
 Initialization:
signal(fork[i]);
fork[i].count := 1 forever
for i := 0..4

First attempt: deadlock if each philosopher starts by

picking up his left fork (chopstick)!
60

30
 11/5/2021

Dining Philosophers Solution

Possible solutions to avoid deadlock:

• Allow at most four philosophers to be
sitting at the table at same time.
• Odd numbered philosopher picks up
left fork first, even one picks up right
fork.

61

Weakness of the Semaphore

 The user is expected to write wait and signal in the right
order.
 The user must remember to execute signal for each exit
 Calls may be spread throughout the program
 The logic may demand that a process must check and
signal his peers.

Review the logic for the Dining Philosophers solution.

There have been a wide number of alternatives
proposed.

Monitors are one common approach

62

31
 11/5/2021

Monitors

A new language construct that includes
synchronization

Implemented in Java via synchronized keyword

Only one process can enter a Monitor (use the
entry points) at a time.

For example, compiler might generate a call to a
common semaphore on entry: signal on exit.

If process P makes a monitor call, and process Q
is in the monitor, P will block until Q exits

63

Java Example
class Account {
private double balance;
public Account(double deposit) { }
balance = deposit;
public synchronized double getBalance() {
return balance;
}
public synchronized void deposit(double amount) {
balance += amount;
}
public synchronized void withdraw(double amount) {
balance -= amount;
}
}

64

32
 11/5/2021

Equivalence

Monitors and semaphores have equivalent
power

Anything you can do with Monitors, you can do
with semaphores.
 Proof: we can implement a monitor with a
semaphore

Anything that you can do with Semaphores,
you can do with Monitors
 Proof: we can implement a semaphore with a
monitor

65

Summary

We have seen two problems
 Critical Sections - cannot both be modifying
variable
 Synchronization - must define ordering

Often, our problems are a combination of the two

 Readers/writers share storage, and readers should

wait if there are writers waiting

It is difficult to use semaphores correctly.

While there has been language support for Monitors
for some time, standard UNIX still only supports
semaphore (man sem_open)

66

33