Transcript Interprocess Communication (IPC)

Interprocess Communication
(IPC)
There are three issues to be considered
• how one process can pass information to another.
• How to make sure two or more processes do not get into each
other’s way when engaging in critical activities (suppose two
processes each try to grab the last l00K of memory).
• proper sequencing when dependencies are present:
• if process A produces data and process B prints it, B has to
wait until A has produced some data before starting to print.
• Independent processes – cannot be affected
by other processes
• Cooperating processes – can be affected i.e.
shares data
Reasons for Interprocess communication
• Information sharing
• Computation speedup – parallel processes
• Modularity – system functions into separate
processes
• Convenience – many tasks simultaneously
e.g printing, editing compiling
Race Conditions
• A race condition is an undesirable situation that occurs when a
device or system attempts to perform two or more operations at the
same time
• The term originates with the idea of two signals racing each other to
influence the output first.
• An example of a race condition is when two threads access a
shared variable at the same time. The first thread reads the variable,
and the second thread reads the same value from the variable. Then
the first thread and second thread perform their operations on the
value, and they race to see which thread can write the value last to
the shared variable. The value of the thread that writes its value last
is preserved, because the thread is writing over the value that the
previous thread wrote.
Fig 1 Two processes competing for memory at the same time
Spooler
Directory
.
.
.
Process A
Process B
4
abc
5
Prog.c
6
Prog.n
7
out = 4
in = 7
Process A searches spooler and finds location 7 free. It saves 7 in variable called
nextfreeslot.
Process A is swapped out
Process B runs and searches spooler and also finds location 7 free. It saves variable and
places file in location7 . Process B completes
Process A returns, and saves it’s file into location 7 as indicated by nextfreeslot. It
overwrites current file and increments file pointer in to location 8.
Critical Sections
Mutual exclusion
• For satisfactory mutual exclusion
–
–
–
–
no two processes in critical region at any time
no assumptions are to be made about speed or number of CPU’s
no process outside critical region may be blocked
no process to wait forever to enter critical region
Solutions
• Disable interrupts
– unwise to allow processes to disable interrupts
– may not turn them on again
– more than one processor disabling interrupts affects only one CPU
– hence can still access shared memory
– kernel may disable interrupts
Lock Variables
• Initially 0
process enters critical region
if lock = 0
(i)
process sets lock = 1
enter critical region
else if lock = 1
wait until lock = 0
• if process gets to (i) and is interrupted
then 2nd process sets lock = 1
now if process 2 swapped out while in critical region
process 1 restarts it will now also be in critical
region
Strict Alternation
•
while (TRUE)
{
while (turn = 0) ;
critical region();
turn = 0;
noncritical_region()
}
Process0
•
turn is initially 1, hence process0 enters critical region meanwhile process1
sits in loop. As process0 leaves critical region , sets turn = 0 to allow process1
to enter critical region .
•
If one process0 much slower than process1, then process will not be able to reenter critical region .
while (TRUE)
{
while (turn = 1);
critical region();
turn = 1;
noncritical_region()
}
Process1
Test and Set Lock(TSL)
•
Hardware solution
copies the old value of lock from memory to CCR - sets lock = 1
compare the old value with 0
if = 1
loop
else
enter critical region
•
Note The tsl command is indivisible therefore cannot be interrupted part way
through copying old value to CCR and setting lock to 1
On leaving the critical region reset lock to 0.
enter_region:
tsl register,lock
/*copy lock to register and set lock to 1 */
cmp register,#0
/* was lock zero? */
jne enter_region /*if it was non zero, lock was set, so loop*/
ret
/*return to caller; critical region entered*/
leave_region:
move lock,#0 /* store a 0 in lock */
ret
/* return to caller */
•
This solution works!
IPC mechanisms found in most UNIX systems:
•
•
•
•
•
•
•
Pipes
FIFO’s (named pipes)
Signals
Message Queues
Semaphores
Shared Memory
Sockets
Pipes
•A
pipe is a section of shared memory that processes use for communication.
• In Windows terms the process that creates a pipe is the pipe server. A process that
connects to a pipe is a pipe client.
• One process writes information to the pipe, then the other process reads the information
from the pipe.
Pipes
There are two types of pipes:
•
Unnamed pipes in UNIX or anonymous pipes in Windows, offer limited
services and can only be used with processes that share a common
ancestry (parent and child). With unnamed pipes, there's one reader and
one writer and are not permanent, they must be created and destroyed
each time they are needed.
•
Named pipes provide a way for processes running on different computer
systems to communicate over the network. They provide a one-way or
duplex pipe for communication between the pipe server and one or more
pipe clients.
Pipes
• A pipe is a mechanism whereby the output of one process is
directed into the input of another.
• For example, the output from the who command is piped into
the wc -l command, the vertical bar character specifying the
pipe operation:
$who | wc –l
• A pipe file is created by using the pipe system call, which
returns a pair of file descriptors, one for the read operation and
one for writing.
• The system actually manages it as a FIFO queue, and the
maximum amount of data in the queue is constrained to a
system defined limit, typically 5120 bytes.
• The read and write operations may become blocked if, for
example, the queue is empty (on a read) or is full ( on a write).
Note that when the pipe is closed, the pipe file is destroyed.
Named Pipes
•A “named” pipe, which is sometimes called a FIFO. The “name” of a
named pipe is actually a filename within the file system.
•An application is to allow totally unrelated programs to communicate
with each other. For example, a program that services requests of
some sort (print files, access a database) could open the pipe for
reading. Then, another process could make a request by opening the
pipe and writing a command. That is, the “server” can perform a task on
behalf of the “client”.
•Blocking can also happen if the client isn't writing, or the server isn't
reading.
Signals
• Signals are a relatively low level inter-process
communication method which is used in UNIX. The
signal arranges for a user defined function to be
called, when a particular event occurs.
• Synchronous signals
– These are signals frequently generated by the hardware
when an internal error has occurred such as - divide by
zero, illegal instruction, memory access violation etc. These
always happen at the same place each time a program is run
– hence the term synchronous.
• Asynchronous signals
– These signals cannot be predicted, their occurrence is
normally random. There are three main sources of such
signals:
– Another process. The system call used to send a signal is
kill(). A process can send any signal to any other process
which has the same owner as itself.
Signals
•
A terminal driver sends a signal when a special key is pressed. e.g the
panic key combination in UNIX is CTRL-C. This sends the SIGINT
which generates an interrupt.
•
The alarm() library call which resets any previous setting of a timer.
The kernel sends SIGALARM to the calling process when the time
expires. The default action terminates the process. These are often
called software interrupts.
•
Example
#!/bin/bash
trap “echo Ouch” INT
sleep 10
echo slept for ten seconds
sleep 10
echo slept for twenty seconds
sleep 10
echo slept for thirty seconds and finish
Name
Description
SIGHUP
hang up-sent to processes when terminal logs out
SIGINT
terminal initiated interrupt
SIGQUIT
another terminal interrupt which forces a memory dump
SIGILL
illegal instruction execution
SIGTRAP
trace trap-used by certain UNIX debuggers
SIGFPE
floating point exception
SIGKILL
sent by one process to terminate another
SIGSEGV
segment violation-memory addressing error
SIGSYS
irrecoverable error in system call
SIGPPE
write to a pipe with no reader process
SIGALARM
sent to a process from kernel after time expires
SIGTERM
sent by user process to terminate a process
SIGUSR1,2
user defined signals sent by user processes
16
Shared Memory
•
Shared memory is a segment of memory that is shared between processes.
It enables you to connect to the shared memory segment, and get a pointer
to the memory.
•
You can read and write to this pointer and all changes you make will be
visible to everyone else connected to the segment.
•
This is the fastest form of IPC because data does not need to be copied
between processes.
Shared Memory
Shared Memory, Pros and Cons
• Pros
– Fast bidirectional communication among any number of
processes
– Saves Resources
• Cons
– Needs concurrency control (leads to data inconsistencies like
‘Lost update’)
– Lack of data protection from Operating System (OS)
Shared Memory
•
The main problem with using shared memory is that of race conditions.
•
Because shared memory is a shared resource there has to be some way of
letting the processes that have access to it know if it’s safe to read and write
to it.
•
This problem arises because these systems use preemptive multitasking,
where the operating system can swap processes in and out.
•
One simple way of solving this problem is semaphores.
Message Queues
• Operating system supplies send() and receive() primitives.
• A message queue works kind of like a FIFO, but supports some
additional functionality. In general messages are taken off the queue
in the order they are put on.
• However, there are ways to pull certain messages out of the queue
before they reach the front. It's like cutting in on somebody’s
telephone conversation
• A receiver process must have a mailbox to buffer messages that
have been sent, but not accepted by the receiver.
• Can be synchronous – waits until message safely received.
• Can be asynchronous – doesn’t waits until message safely received.
Message Passing
Problems
• Messages lost in network - can use acknowledge signal.
– If no ack signal re-transmits. However message may have been
received ok but ack signal failed – gets 2 messages
• How are processes named – how can a client tell if communicating
with real server or an imposter?
Sockets
• A socket is a bidirectional communication device that can be used to
communicate with another process on the same machine or with a
process running on other ma
• Unix sockets are just like two-way FIFOs.
• However, all data communication will be taking place through the
sockets interface, instead of through the file interface.
• When programming with sockets, you'll usually create server and
client programs. The server will sit listening for incoming
connections from clients and handle them.
• This is very similar to the situation that exists with Internet sockets,
but with some fine differences
End
Interprocess Communication
There are two basic schemes for interprocess communication:
• Shared memory
– Communication rests with the programmer
– Operating system provides the shared memory
– Application orientated
• Message passing
– Responsibility rests with the operating system
– The operating system provides 2 operations, namely
• SEND (message)
• RECEIVE (message)
Indirect Communication
Messages are sent to and received from mailboxes
(sometimes called ports) Each mailbox has a unique
I.D. A process may communicate with another
process by a number of different mailboxes
• Properties of indirect communication
–
–
–
–
Link is established if there is a shared mailbox
Can link more than 2 processes
May be several links to mailboxes
May be uni-directional or bi-directional
• Mailboxes owned by process
– The owner can only receive messages while the user can
only send
– When the owner process finishes the mailbox dies – must
tell all users
Types of communication
• Direct
– SEND (P, message) – send message to process P
– RECEIVE (Q, message) – receive message from process Q
These are system calls
• Properties of direct communication
• Symmetrical
– A link is established between every pair of processes – they
need to know each others identity
– A link is established between exactly 2 processes
– The link is bi-directional
• Asymmetric
– SEND (P, message) – send message to process P
– RECEIVE (ID, message) – receives a message from any
process i.e. sender attaches ID
Degree of
awareness
Relationship
Influence that one
process has on the other
Potential control
problems
Processes unaware
of each other
Competition
Results of one process
independent of the action of
others
Timing of process may be
affected
Mutual exclusion
Deadlock
Starvation
Processes indirectly
aware of each other
(e.g. shared object)
Cooperation
by sharing
Results of one process may
depend on information
obtained from others
Timing of process may be
affected
Mutual exclusion
Deadlock
Starvation
Data coherence
Processes directly
aware of each other
Cooperation
Results of one process may
by
depend on information
communication obtained from others
Timing of process may be
affected
Deadlock
Starvation
Semaphores
• Binary semaphore –
1 = raised semaphore, lets train pass
0 = lowered semaphore, blocks train
• Associated with semaphore is a list of processes
wishing to pass through critical region (cr)
• The operating system can:
– dispatch a process
– block a running process + place in list associated
with a particular semaphore
– wake a blocked process – place in ready state
•
There are two routines
P(s) if s = 1
then
s0
/*lower semaphore*/
else
BLOCK calling process
dispatch a ready process
•
V(s) if the list of processes waiting on s is non-empty
then
WAKE UP a process waiting on s
else
s1
/* raise semaphore*/
Effect of P and V Operations
Invoking
process
Invoked
operation
Running in
critical region
Blocked on s
1
Value of s
1
2
A
P(s)
A
0
3
A
V(s)
4
B
P(s)
B
5
C
P(s)
B
C
0
6
D
P(s)
B
C, D
0
7
E
P(s)
B
C, D, E
0
8
B
V(s)
D
C, E
0
9
F
P(s)
D
C, E, F
0
10
D
V(s)
C, F
0
11
None of A - F
E
C, F
0
12
E
V(s)
F
C
0
13
F
V(s)
C
14
C
V(s)
1
0
0
1
•
•
•
•
signals
shared files, i.e. pipes
semaphores
message passing
Mailboxes
• Mailboxes owned by the operating system
• The operating system provides a mechanism that
allows a process to:
– Create a new mailbox
– Send and receive messages through mailboxes
– Destroy a mailbox
• The process that creates a mailbox owns it and is
the owner process that can receive messages.
• However ownership and receive privileges may be
passed to other processes.
e.g. A process creates a mailbox A, then spawns a new
process Q, then P & Q may share mailbox A
Capacity
• Zero capacity
– If a send occurs before the receive, the sending process is blocked
until a receive occurs – this is known as a rendezvous
• Bounded Capacity
– Queue has a finite length. If the buffer is full the sender will be
delayed
• Unbounded capacity
– Sender is never delayed
• Summary
– Mailboxes are effectively the same as pipes. However, pipes do not
retain message boundaries. i.e. if 10 messages are sent the
process will read 1,000 bytes from a pipe, whereas a mailbox will
send only one message at a time.
Race Conditions
• Spooler has large number of slots
• 2 shared variables out and in
• out points to next file to be printed, in points to next free slot
• Now if slots 0 and 3 are empty and slots 4 to 6 are full
simultaneously processes A and B decide to queue a file for
printing
• process A reads in and stores the value 7 in next_free_slot
• interrupt occurs and switches to process B, reads in and also
gets a 7
• Stores file in 7 and updates to 8
• Process A restarts and also stores its file in 7 and updates to 8