Module 4
Concurrency
Inter process Communication
• Communication between the processes
• Data exchange between multiple threads of different processes
• 2 types of processes in any OS:
a. independent processes
b. cooperating processes
• Independent processes – these processes can not affect the other
processes and can not be affected by other processes
• Cooperating processes – these processes may affect the other
processes and may be affected by other processes
Inter process Communication
• Cooperating processes need interprocess communication (IPC)
• 2 models of IPC are:
a. shared memory model
b. message passing model
• Shared memory model - exchanging of the data (read and write
operations) between two processes is done through shared region
• Message passing model – communication between the processes is
done through messages
Communication Models
Message Passing Shared Memory
Advantages of process cooperation
• Information sharing - Several processes may need to access the
same data.
• Modularity - dividing the system functions into separate processes
or threads.
• Computation speedup - A task can often be run faster if it is broken
into subtasks and distributed among different processes.
• Convenience - Even an individual user may work on many tasks at
the same time.
Message Passing
• Processes communicate with each other without resorting to
shared variables
• IPC facility provides two operations:
• send(message)
• receive(message)
• The message size is either fixed or variable
• If processes P and Q wish to communicate, they need to:
• Establish a communication link between them
• Exchange messages via send/receive
Logical implementation of communication link
• Direct or indirect
• Synchronous or asynchronous
• Automatic or explicit buffering
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
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
• Operations
• Create a new mailbox (port)
• Send and receive messages through mailbox
• Delete a mailbox
• Primitives are defined as:
• send(A, message) – send a message to mailbox A
• receive(A, message) – receive a message from mailbox A
Indirect Communication-contd.
• Mailbox sharing
Consider P1, P2, and P3 share mailbox A
Let P1, sends; P2 and P3 receive
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.
Synchronous and Asynchronous
• Message passing may be either blocking or non-blocking
• Blocking is considered synchronous
• Blocking send -- the sender is blocked until the message is received
• Blocking receive -- the receiver is blocked until a message is available
• Non-blocking is considered asynchronous
• Non-blocking send -- the sender sends the message and continue
• Non-blocking receive -- the receiver receives:
• A valid message, or
• Null message
Buffering
• Queue of messages attached to the link.
• Implemented in one of three ways
1. Zero capacity – no messages are queued on a link.
Sender must wait for receiver
2. Bounded capacity – finite length of n messages
Sender must wait if link full
3. Unbounded capacity – infinite length
Sender never waits
Shared memory model
• Producer – Consumer problem is a common illustration of cooperating
processes in IPC
• Shared memory model is one solution to the producer – consumer problem
• Producer and consumer processes uses buffer for communication
• Producer: fills the items in the buffer
• Consumer: picks the items from the buffer
• The buffer will reside in the shared region of producer and consumer
processes
Types of buffer
• unbounded-buffer
places no practical limit on the size of the buffer
• bounded-buffer
assumes that there is a fixed buffer size
Code for producer and Consumer
Producer Consumer
If the producer and consumer processes concurrently execute the statements “count++” and “count-- with
“count = 5” initially, the value of the variable count may be 4, 5, or 6!
The statement “count++” may be implemented in machine language
The statement “count--” may be implemented in machine language
Concurrent execution of producer and consumer with count=5 initially:
Race condition
We arrive at this incorrect state because we allowed both processes to
manipulate the variable count concurrently. A situation like this, where
several processes access and manipulate the same data concurrently and
the outcome of the execution depends on the particular order in which the
access takes place, is called a race condition.
To guard against the race condition, we need to ensure that only one
process at a time can be manipulating the variable count. To make such a
guarantee, we require that the processes be synchronized in some way.
Race condition
• Processes P0 and P1 are creating child processes
using the fork() system call
• Race condition on kernel variable
next_available_pid which represents the next
available process identifier (pid)
• Unless there is a mechanism to prevent P0 and P1
from accessing the variable
next_available_pid the same pid could be
assigned to two different processes!
The Critical-Section Problem
Consider a system consisting of n processes {P0, P1, ..., Pn−1}. Each process has a
segment of code, called a critical section, in which the process may be accessing —
and updating — data that is shared with at least one other process.
No two processes are executing in their critical sections at the same time.
• critical-section problem is to design a protocol that the processes can use to
synchronize their activity so as to cooperatively share data.
Solution to Critical Section Problem
Solution to the critical-section problem must satisfy the following three
requirements:
• Mutual exclusion: If a process is running in the critical section, no other
process should be allowed to run in that section at that time.
• Progress: If no process is still in the critical section and other processes
are waiting outside the critical section to execute, then any one of the
processes must be permitted to enter the critical section.
• Bounded Waiting (No starvation): It ensures that no process has to wait
indefinitely to access the critical section. There's a limit to how long a
process can be delayed.
(Starvation means a process keeps waiting forever to access the critical
section but never gets a chance. A process should not wait forever to enter
the critical section)
Peterson’s Solution
A classic software-based solution to the critical-section problem is
known as Peterson’s solution.
Most modern computer architectures perform basic machine-language
instructions, such as load and store, and there are no guarantees that
Peterson’s solution will work correctly on such architectures.
However, a solution is presented because it provides a good algorithmic
description of solving the critical-section problem and illustrates some of
the complexities involved in designing software that addresses the
requirements of mutual exclusion, progress, and bounded waiting.
Peterson’s solution is restricted to two processes that alternate execution
between their critical sections and remainder sections.
The processes are numbered P0 and P1.
For convenience, when presenting Pi , we use Pj to denote the other process;
Peterson’s Solution-contd.
Peterson’s solution requires the two processes to share two data items.
The variable turn indicates whose turn it is to enter its critical section.
That is, if turn == i, then process Pi is allowed to execute in its critical section.
The flag array is used to indicate if a process is ready to enter its critical section.
For example, if flag[i] is true, Pi is ready to enter its critical section.
while(true) {
while(true) {
flag[i] = true;
flag[j] = true;
turn = j;
turn = i;
while (flag[j] && turn== j);
while (flag[i] && turn== i);
/* critical section*/
/* critical section*/
flag[i] = false;
flag[j] = false;
/* remainder
/* remainder
section*/
section*/
}
}
Process Pi Process Pj
Bakery Algorithm
• A bakery with a numbering machine, which allocates a unique number to the
customer.
• Numbers increase by one as customers enter into the bakery.
• Global counter displays the number of customers currently being served and all
others has to wait inline
• After the baker is finished serving the customer, the following number is
displayed and served customer leaves
• Each process is assigned a unique number (a ticket) in a lexicographical order.
Before entering the critical section, a process receives a ticket number, and the
process with the smallest ticket number enters the critical section.
• If two processes receive the same ticket number, the process with the lower
process ID is given priority.
Simplified Bakery Algorithm
lock(i){
num[i] = MAX(num[0], num[1], ...., num[N-1]) + 1;
for(p = 0; p < N; ++p){
while (num[p] != 0 and num[p] < num[i]);
}
}
//Critical Section
unlock(i){
num[i] = 0;
}
//Reminder Section
Bakery Algorithm
lock(i){
choosing[i] = True
num[i] = MAX(num[0], num[1], ...., num[N-1]) + 1
choosing[i] = False
for(p = 0; p < N; ++p){
while (choosing[p]);
while (num[p] != 0 and (num[p], p) < (num[i], i)); // (a, b) < (c, d) which is equivalent to:
// (a < c) or ((a == c) and (b < d))
}
}
//Critical Section
unlock(i){
num[i] = 0;
}
//Reminder Section
Test and set
Definition of the atomic
test and set()
Mutual-exclusion implementation with
test and set()
Compare and swap
Mutual exclusion with the
compare and swap()
instruction.
Definition of the atomic
compare and swap()
instruction
Bounded-waiting mutual exclusion with compare and swap().
Mutex Locks
• The hardware-based solutions to the critical-section problem are
complicated as well as generally inaccessible to application
programmers.
• Operating-system designers build higher-level software tools to
solve the critical-section problem. The simplest of these tools is
the mutex lock.
• mutex lock protects the critical sections and thus prevent race
conditions.
• acquire() function acquires the lock, and the release() function
releases the lock.
• mutex lock has a boolean variable available whose value indicates
if the lock is available or not.
Solution to the critical-section
problem using mutex locks
Semaphores
• A semaphore is a synchronization tool.
• A semaphore S is an integer variable that, apart from initialization, is
accessed only through two standard atomic operations: wait () and signal ().
• The wait () operation was originally termed P (Proberan) ("to test"); signal()
was originally called V (Verhogen) ("to increment").
• The definition of wait () is as follows:
wait(S) {
while S <= 0;
s--; }
The definition of signal() is as follows:
signal(S)
{
S++;
}
Semaphores-contd.
• All modifications to the integer value of the semaphore in the wait()
and signal() operations must be executed indivisibly.
• That is, when one process modifies the semaphore value, no other
process can simultaneously modify that same semaphore value.
• In addition, in the case of wait (S), the testing of the integer value of S
(S<=0), as well as its possible modification (S--), must be executed
without interruption.
Semaphores-contd.
• Counting semaphore – integer value can range over an unrestricted domain
• Binary semaphore – integer value can range only between 0
and 1; can be simpler to implement
• Also known as mutex locks
• Can implement a counting semaphore S as a binary semaphore
• Provides mutual exclusion
Semaphore mutex; // initialized to 1
do {
wait (mutex);
// Critical Section
signal (mutex);
// remainder section
} while (TRUE);
Semaphores-contd.
• Must guarantee that no two processes can execute wait () and signal () on the
same semaphore at the same time
• Thus, implementation becomes the critical section problem where the wait and
signal code are placed in the critical section.
• Could now have busy waiting in critical section implementation
• But implementation code is short
• Little busy waiting if critical section rarely occupied
• Note that applications may spend lots of time in critical sections and therefore
this is not a good solution.
Semaphore Implementation with no Busy waiting
• With each semaphore there is an associated waiting queue. Each
entry in a waiting queue has two data items:
• value (of type integer)
• pointer to next record in the list
• Two operations:
• block – place the process invoking the operation on the
appropriate waiting queue.
• wakeup – remove one of processes in the waiting queue and
place it in the ready queue.
Semaphore Implementation with no Busy waiting
• Implementation of wait:
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}
• Implementation of signal:
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
Deadlock and Starvation
• Deadlock – two or more processes are waiting indefinitely for an event that can be
caused by only one of the waiting processes
• Let S and Q be two semaphores initialized to 1
P0 P1
wait (S); wait (Q);
wait (Q); wait (S);
. .
. .
. .
signal (S); signal (Q);
signal (Q); signal (S);
• Starvation – indefinite blocking. A process may never be removed from the
semaphore queue in which it is suspended
• Priority Inversion – Scheduling problem when lower-priority process holds a lock
needed by higher-priority process
Classical Problems of Synchronization
• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem
Bounded-Buffer Problem
• N buffers, each can hold one item
• Semaphore mutex initialized to the value 1
• Semaphore full initialized to the value 0
• Semaphore empty initialized to the value N.
The structure of the producer process The structure of the consumer process
do { do {
// produce an item in nextp wait (full);
wait (empty); wait (mutex);
wait (mutex); // remove an item from buffer to nextc
// add the item to the buffer signal (mutex);
signal (mutex); signal (empty);
signal (full); // consume the item in nextc
} while (TRUE); } while (TRUE);
Readers-Writers Problem
• A data set is shared among a number of concurrent processes.
• Readers – only read the data set; they do not perform any updates
• Writers – can both read and write
• Problem – allow multiple readers to read at the same time. Only one
single writer can access the shared data at the same time.
• Shared Data
• Data set
• Semaphore mutex initialized to 1 (controls access to readcount)
• Semaphore wrt initialized to 1 (writer access)
• Integer readcount initialized to 0 (how many processes are reading
object)
Readers-Writers Problem-Contd.
The structure of a reader process
do {
wait (mutex) ;
The structure of a writer process
readcount ++ ;
do { if (readcount == 1)
wait (wrt) ; wait (wrt) ;
// writing is performed signal (mutex);
// reading is performed
signal (wrt) ;
wait (mutex) ;
} while (TRUE); readcount - - ;
if (readcount == 0)
signal (wrt) ;
signal (mutex) ;
} while (TRUE);
Dining-Philosophers Problem
Shared data
Bowl of rice (data set)
Semaphore chopstick [5] initialized to 1
Dining-Philosophers Problem-contd.
The structure of Philosopher i:
do {
wait ( chopstick[i] );
wait ( chopstick[ (i + 1) % 5] );
// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
} while (TRUE);
What is the problem with this algorithm?
• From the given pseudocode, simultaneous access to the chopstick was
avoided but what if all the philosopher gets hungry at same time and picks
up their left chopstick?
• Deadlock occurs because each one will have only one chopstick and will
be waiting for the another one.
• Adjacent philosophers cannot eat simultaneously.
Deadlock Handling
• Allow at most n-1 philosophers to be sitting simultaneously at the
table.
• Allow a philosopher to pick up the chopsticks only if both are
available (picking must be done in a critical section).
• Use an asymmetric solution -- an odd-numbered philosopher picks
up first the left chopstick and then the right chopstick. Even-
numbered philosopher picks up first the right chopstick and then the
left chopstick.
Monitors
Although semaphores provide an effective mechanism for process
synchronization, using them incorrectly can result in timing errors that
are difficult to detect, since these errors happen only if some wrong
execution sequences take place.
All processes share a semaphore variable mutex, which is initialized to
1. Each process must execute wait (mutex) before entering the critical
section and signal (mutex) afterward.
If this sequence is not observed, two processes may be in their critical
sections simultaneously.
Monitors
❖Suppose that a process interchanges the order in which the wait() and signal()
operations on the semaphore mutex are executed, resulting in the following execution:
In this situation, several processes may be executing in their critical sections
simultaneously, violating the mutual-exclusion requirement. This error may be discovered
only if several processes are simultaneously active in their critical sections.
❖Suppose that a process replaces signal (mutex) with wait (mutex). That is, it executes:
In this case, a deadlock will occur.
❖Suppose that a process omits the wait (mutex), or the signal (mutex), or both. In this
case, either mutual exclusion is violated or a deadlock will occur.
Monitors
• A monitor type is an ADT which presents a set of
programmer-defined operations that are provided
mutual exclusion within the monitor. A abstract data
type- or ADT- encapsulates private data with public
methods to operate on that data.
• The monitor type also contains the declaration of
variables whose values define the state of an instance
of that type, along with the bodies of procedures or
functions that operate on those variables.
• The representation of a monitor type cannot be used
directly by the various processes.
• Thus, a procedure defined within a monitor can access
only those variables declared locally within the monitor
and its formal parameters. Similarly, the local variables
of a monitor can be accessed by only the local
procedures.
Monitors
• The monitor construct ensures that only one
process at a time is active within the
monitor.
• Consequently, the programmer does not
need to code this synchronization constraint
explicitly.
• However, the monitor construct, is not
sufficiently powerful for modeling some
synchronization schemes. For this purpose,
we need to define additional synchronization
mechanisms.
• These mechanisms are provided by the
condition construct.
Monitors
A programmer who needs to write a tailor-made
synchronization scheme can define one or more variables
of type condition:
condition x, y;
The only operations that can be invoked on a condition
variable are wait () and signal(). The operation
x. wait();
means that the process invoking this operation is
suspended until another process invokes
x. signal();
The x. signal() operation resumes exactly one suspended
process. If no process is suspended, then the signal()
operation has no effect; that is, the state of x is the same as
if the operation had never been executed. Contrast this
operation with the signal() operation associated with
semaphores, which always affects the state of the
semaphore.
Monitors
• Now suppose that, when the x. signal () operation is invoked by a process P, there exists a
suspended process Q associated with condition x.
• Clearly, if the suspended process Q is allowed to resume its execution, the signaling process P
must wait.
• Otherwise, both P and Q would be active simultaneously within the monitor. Note, however, that
both processes can conceptually continue with their execution.
• Two possibilities exist:
1. Signal and wait: P either waits until Q leaves the monitor or waits for another condition.
2. Signal and continue: Q either waits until P leaves the monitor or waits for another condition.
There are reasonable arguments in favor of adopting either option.
On the one hand, since P was already executing in the monitor, the signal-and-continue method
seems more reasonable.
On the other hand, if we allow thread P to continue, then by the time Q is resumed, the logical
condition for which Q was waiting may no longer hold.
Dining Philosopher Solution using Monitors
The solution imposes the restriction that a philosopher may pick up her chopsticks
only if both of them are available.
To code this solution, we need to distinguish among three states in which we may
find a philosopher.
For this purpose, we introduce the following data structure:
enum {THINKING, HUNGRY, EATING}state[5];
Philosopher i can set the variable state [i] = EATING only if her two neighbors are not
eating: (state [ (i +4) % 5] ! = EATING) and (state [ (i +1) % 5] ! = EATING).
We also need to declare condition self[5];
in which philosopher i can delay herself when she is hungry but is unable to obtain
the chopsticks she needs.
Dining Philosopher Solution using Monitors
The distribution of the chopsticks is controlled
by the monitor and the Dining Philosophers
definition. Each philosopher, before starting to
eat, must invoke the operation pickup(). This act
may result in the suspension of the philosopher
process. After the successful completion of the
operation, the philosopher may eat. Following
this, the philosopher invokes the put down()
operation.
Dining Philosopher Solution using Monitors
Thus, philosopher i must invoke the operations pickup() and put down() in the
following sequence:
[Link](i);
eat
[Link](i);
It is easy to show that this solution ensures that no two neighbors are eating
simultaneously and that no deadlocks will occur.