Operating Systems
Mona Farouk Ph.D.
Principles of Process Management
2. Inter Process Communication
1
Areas of OS Responsibility
Hardware
CPU (managed by processes)
Memory
I/O Devices
File Systems
Security
Networking
2
Inter-Process Communication
Processes executing concurrently in the operating
system may be either independent processes or
cooperating processes
Processes frequently need to communicate with other
processes.
In general, data is Shared between processes to be
able to communicate with each other.
In this case, we need to apply mutual exclusion to
avoid Race Conditions.
Can processes communicate in a different way?
Yes, through Message Passing
But, not always efficient.
3
Race Conditions
Issue arises when more than one process
share some resource. Correct outcome
depends on relative ordering of events.
If one process is updating a data structure
and another process is allowed to run
before the update is complete
Results may be inconsistent.
4
Critical Sections
Code containing a Race Condition
It is a code section where processes change common
variables, tables, write to files, etc.
Example:
Consider process A & B that increment a shared variable
x++;
This maps to:
Ld R1, x
Addi R1, 1 Non-atomic operation
St x , R1
5
Critical Sections
Non-Atomic operations Can be Interrupted
Example:
Inserting an element in a linked-list
if (head == NULL)
head = new_elem ;
else
tail next = new_elem ;
tail = new_elem ;
6
Mutual Exclusion
The critical-section problem is to design a protocol that
the processes can use to cooperate.
If interrupted between test and assignments, elements
can get lost
Need to make test and assignments atomic
Use Mutual Exclusion (Mutex) locks
Lock resources by putting lock/unlock operations around
critical sections
Example:
mutex_lock(&lock);
if (head == NULL)
head = new_elem ;
else
tail next = new_elem ;
tail = new_elem ;
mutex_unlock(&lock);
7
Requirements for efficient
solution of Race Conditions
No two process simultaneously in their
critical section.
No assumption about speeds or the
number of CPUs.
No process running outside its critical
section may block other processes.
No process should have to wait forever to
enter its critical section.
8
Mutual Exclusion
Interrupt Control
Disable interrupts prior to entering critical
section/ Enable on leaving
No other thread of control can execute this
code while interrupts are disabled on a single
processor
Limitations:
Can’t be allowed for user processes security
Can’t work for multiple processors
9
Mutual Exclusion with Busy Waiting
1. Test and Set (TSL) instruction
Atomically tests a variable and sets it
Example:
enter_region:
Tsl register, flag
Cmp register, #0
Atomic This type of lock is called a
instruction Jnz enter_region Spin Lock
ret
Tests the previous value of the
leave_region: lock
move flag, #0
ret
Works on multiple processors
Busy waiting (consumes CPU time)
10
Mutual Exclusion
Notes:
InterruptControl and TSL instructions require
special hardware features.
They don’t have a corresponding high-level
language feature.
11
Solution to Critical-Section
Problem
Mutual Exclusion
Progress
Bounded Waiting
12
Mutual Exclusion with Busy Waiting
2. Software-based lock: 1st attempt
// 0: lock is available, 1: lock is held by a process
int flag = 0;
mutex_lock() mutex_unlock()
{ {
while (flag == 1) flag = 0;
; // spin wait }
flag = 1;
}
Idea: use one flag, test then set, if unavailable,
spin-wait (or busy-wait)
Why it doesn’t work?
Not safe: both processes can be in critical section
13
Mutual Exclusion with Busy Waiting
2. Software-based locks: 2nd attempt
// 1: a process wants to enter critical section, 0: it
doesn’t
int flag[2] = {0, 0};
mutex_lock() mutex_unlock()
{ {
flag[self] = 1; // I need lock // not any more
while (flag[1- self] == 1) flag[self] = 0;
; // spin wait }
}
Idea: use per process flags, set then test,
to achieve mutual exclusion
Why it doesn’t work?
Deadlock
14
Mutual Exclusion with Busy Waiting
2. Software-based locks: 3rd attempt (Strict alternation)
// whose turn is it?
int turn = 0;
mutex_lock() mutex_unlock()
{ {
// wait for my turn // I’m done. your turn
while (turn == 1 – self) turn = 1 – self;
; // spin wait }
}
Idea: strict alternation to achieve mutual
exclusion
Why it doesn’t work?
Depends on processes outside critical section
15
Mutual Exclusion with Busy Waiting
4. Peterson’s Algorithm
Does not need special hardware features
int turn;
int want [2] I would like to enter
void mutex_lock ( int who ) the critical section
{ Set the flag
other = 1 – who ;
want [who] = 1 ;
turn = who ;
while( want [other] && turn == who ) ; As long as:
} The other process is
void mutex_unlock ( int who ) interested
{ &&
want [who] = 0 ; It is my turn
} Then keep waiting
Busy waiting
16
Mutual Exclusion with Busy Waiting
4. Peterson’s Algorithm
void mutex_lock ( int who )
{
void mutex_unlock ( int who )
other = 1 – who ;
{
want [who] = 1 ;
want [who] = 0 ;
turn = who ;
}
while( want [other] && turn == who ) ;
}
1. mutex_lock(0) 2. mutex_lock(1) 3. mutex_unlock(0)
other = 1 other =0 want[0] = 0
want[0] = 1 want[1] = 1 Process 1 enters
turn = 0 turn = 1 Critical Section
Enters Critical Section Busy waits
17
Mutual Exclusion without Busy Waiting
1. Wakeup and Sleep
Previous techniques
waste CPU time
Unexpected effects (Priority Inversion
Problem)
System calls that have the process as a
Parameter
Wakeup waiting bit
18
Mutual Exclusion without Busy Waiting
2. Semaphores
A semaphore is a variable with a value that
indicates the status of a common resource
Semaphore s – integer variable
A process checks the semaphore to determine
the resource's status and then decides how to
proceed.
Higher level technique, suitable for applications
Blocks: No Busy Waiting
19
Mutual Exclusion without Busy Waiting
2. Semaphores
Defined by two operations on semaphore s:
down (Semaphore S) // Acquire Resource , atomic operation
{ S--;
if (S < 0) {add this process to waiting list;
block();
}
}
up (Semaphore S) // Release Resource , atomic operation
{ S++;
if (S<= 0) {remove a process P from waiting list;
wakeup(P); } }
20
Semaphore Types
Counting semaphore – integer value can
range over an unrestricted domain
Used for synchronization
Binary semaphore – integer value can
range only between 0 and 1; can be
simpler to implement
Used for mutual exclusion:
21
Producer-Consumer Problem
Bounded buffer: size ‘N’
Access entry 0… N-1, then “wrap around” to 0 again
Producer process writes data to buffer
Must not write more than ‘N’ items more than consumer
“ate”
Consumer process reads data from buffer
Should not try to consume if there is no data
0 1 N-1
Producer Consumer
22
Unconstrained
Access!!
Eventually buffer fills producer
Consumer is NOT Asleep yet.
sleeps, consumer sleeps
forever!!! Wakeup Signal Lost!
Consumer
sleeps
Anyway!!
23
Mutual exclusion on
shared buffer
System
calls
Ensures producer
blocks if buffer full
Ensures consumer
blocks if buffer empty
24
Mutual Exclusion without Busy Waiting
3. Monitors
Semaphores may seem to be easy to implement
but you can end up with a piece of code with lots
of downs & ups functions embedded within your
code.
This is error prone.
To make it easier to write correct programs, a
higher level synchronization primitive called a
Monitor was proposed.
A Monitor hides mutual exclusion.
25
Mutual Exclusion without Busy Waiting
3. Monitors
A Monitor:
is a collection of procedures, variables, and data
structures that are all grouped together in a special
kind of module or package.
Processes may call the procedures in a
monitor whenever they want to,
but they cannot directly access the monitor's
internal data structures from procedures declared
outside the monitor. 26
Mutual Exclusion without Busy Waiting
3. Monitors
Only one process can be active in a monitor at
any instant.
Monitors are a programming language construct,
so the compiler knows they are special and can
handle calls to monitor procedures differently from
other procedure calls.
When a process calls a monitor procedure,
check to see if any other process is currently
active within the monitor.
If so, the calling process will be suspended
If no other process is using the monitor, the
calling process may enter.
27
Mutual Exclusion without Busy Waiting
3. Monitors
It is up to the compiler to implement the mutual
exclusion on monitor entries.
Because the compiler, not the programmer,
arranges for the mutual exclusion
it is much less likely that something will go wrong.
Just turn a critical region into a monitor
procedure
no two processes will ever execute their critical
regions at the same time.
28
Language
Construct
Less Error-Prone
29
Problems of Monitors:
Not supported by most languages
Can’t work for distributed systems with multiple
CPUs each having its private memory.
30
Recall: Inter-Process Communication
Processes frequently need to communicate
with other processes.
In general, data is Shared between
processes to be able to communicate with
each other.
Inthis case, we need to apply mutual exclusion to
avoid race conditions.
Can processes communicate in a different
way?
Yes, through Message Passing
But, not always efficient.
31
Message Passing
Can be used for synchronization
Based on send and receive operations
send and receive are system calls.
For messages with large data:
Canbe very slow and inefficient than shared
memory.
32
Message Passing
Move data between processes p: dest process id
m: message
Sending a message:
send(p,m);
p: src process id
Receiving a message m: message
receive(p,m);
33
May block if there are
no empty messages
available
May block if there are
no full messages to
process
34
