Chapter 3b: Interprocess Communiation
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
Chapter 3: Processes
■ Interprocess Communication
■ Examples of IPC Systems
■ Communication in Client-Server Systems
Operating System Concepts – 9th Edition 3.2 Silberschatz, Galvin and Gagne ©2013
Interprocess Communication
■ Processes within a system may be independent or cooperating
■ Cooperating process can affect or be affected by other processes,
including sharing data
■ Reasons for cooperating processes:
● Informationsharing
● Computationspeedup ● Modularity
● Convenience
■ Cooperating processes need interprocess communication (IPC)
■ Two models of IPC
● Sharedmemory ● Messagepassing
Operating System Concepts – 9th Edition 3.3 Silberschatz, Galvin and Gagne ©2013
Communications Models
(a) Message passing. (b) shared memory.
process A
process B
message queue
m0
m1
m2
m3
…
mn
kernel
process A
shared memory
process B
kernel
(a) (b)
These are both shared memory techniques
Operating System Concepts – 9th Edition 3.4 Silberschatz, Galvin and Gagne ©2013
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 ● Informationsharing
● Computationspeed-up
● Modularity
● Convenience
Operating System Concepts – 9th Edition 3.5 Silberschatz, Galvin and Gagne ©2013
1: Start with the Basics
Two applications communicating in the same system.
Port-id
Application Processes
B
11/01/06
© JohnDay, 6 All Rights Reserved, 2009
IPC-Facility
11/01/06
InterProcess Communication in a Single System
• The Application invokes System Calls to talk to another Application
– port-id := Allocate (dest-appl-name, ipc characteristics)
– Read (port-id, buffer-ptr)
– Write(port-id, buffer-ptr)
– Deallocate (port-id, reason)
• IPC creates a channel between the two applications, identified by
“port-ids” of local scope.
– Port-ids are not only a short identifier for the end of the channel, but also
allow an application to distinguish multiple IPC channels. • Servesthesamepurposeasafiledescriptor.
• IPC is generally constructed with a shared state mechanism.
– Allocates buffers, if sender tries to send too much it is blocked.
– A characteristic of IPC is it requires a “test and set” instruction or
equivalent.
© JohnDay, 7 All Rights Reserved, 2009
Port-id a
Port-id b
How Does It Work?
Application Processes
B
11/01/06
1) A invokes the IPC Facility to allocate a channel to B; a <- Allocate(B, x);
2) IPC determines whether it has the resources to honor the request.
3) If so, IPC uses “search rules” to find B and determine whether A has access to it. 4) IPC may cause B to be instantiated. B is notified of the IPC request from A and
given a port-id, b.
5) If B responds positively, and IPC notifies A using port-id, a.
6) Thru n) Then using system calls A may send PDUs to B by calling Write(a, buf),
which B receives by invoking Read(b, read_buffer)
7) When they are done one or both invoke Deallocate with the appropriate parameters
© JohnDay, 8 All Rights Reserved, 2009
IPC-Facility
Write(port-id, buffer) Links Buffer
Read(port-id, buffer)
What Happens Inside
11/01/06
All Rights Reserved, 2009
• A FIFO queue head is allocated for each port-id pair.
– Memory allocation keeps links (user can’t see) so buffers can be passed from queue to
queue
– Lots of ways to Implement this.
– But manipulating the queue requires a critical section, i.e. synchronization.
• Each Write causes a buffer to be linked to the end of the queue.
• Each Read causes buffer at head of the queue to be dequeued and passed
to the application.
IPC Facility
Queue
© John Day,
9
Producer-Consumer Problem
■ Paradigm* for cooperating processes, producer process produces information that is consumed by a consumer process
● unbounded-bufferplacesnopracticallimitonthesize of the buffer
● bounded-bufferassumesthatthereisafixedbuffer size
* Paradigm is a bit of exaggeration here (term inflation), model is more appropriate.
Operating System Concepts – 9th Edition 3.10
Silberschatz, Galvin and Gagne ©2013
Bounded-Buffer – Shared-Memory Solution
■ Shared data
#define BUFFER_SIZE 10
typedef struct { ...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
■ Solution is correct, but can only use BUFFER_SIZE-1 elements
● Otherwise, Can’t distinguish empty from full.
Operating System Concepts – 9th Edition 3.11 Silberschatz, Galvin and Gagne ©2013
Bounded-Buffer – Producer
item next_produced; while (true) {
}
/* produce an item in next produced */
while (((in + 1) % BUFFER_SIZE) == out); /* while full do nothing */ buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
CircleQ (see Knuth) a single large
buffer used as a queue with pointers
advanced in increments amount In produced or consumed modulo the
BUFFERSIZE. Here amount
produced and consumed is fixed but
could just as easily be variable.
Out
Operating System Concepts – 9th Edition 3.12
Silberschatz, Galvin and Gagne ©2013
Bounded Buffer – Consumer
item next_consumed;
while (true) {
while (in == out); /*while empty do nothing */
next_consumed = buffer[out];
}
out = (out + 1) % BUFFER_SIZE;
/* consume the item in next consumed */
Out In
Operating System Concepts – 9th Edition 3.13
Silberschatz, Galvin and Gagne ©2013
Interprocess Communication – Shared Memory
■ An area of memory shared among the processes that wish to communicate
■ The communication is under the control of the users processes not the operating system.
■ Major issues is to provide mechanism that will allow the user processes to synchronize their actions when they access shared memory.
■ Synchronization is discussed in great details in Chapter 5.
Operating System Concepts – 9th Edition 3.14 Silberschatz, Galvin and Gagne ©2013
Interprocess Communication – Message Passing
■ Mechanism for processes to communicate and to synchronize their actions
■ Message system – processes communicate with each other without resorting to shared variables
■ IPC facility provides two operations:
● Allocate(application-name, port-id, capacity) ● send(message)
● receive(message)
● Deallocate(port-id)
■ The message size is either fixed or variable
Operating System Concepts – 9th Edition 3.15 Silberschatz, Galvin and Gagne ©2013
Message Passing (Cont.)
■ If processes P and Q wish to communicate, they need to: ● Establishacommunicationlinkbetweenthem
● Exchangemessagesviasend/receive
■ Implementation issues:
● How are links established? Allocating port-ids (file descriptors)
● Canalinkbeassociatedwithmorethantwoprocesses?Noteasily
● Howmanylinkscantherebebetweeneverypairof communicating processes? one
● What is the capacity of a link? n,
● Isthesizeofamessagethatthelinkcanaccommodatefixedor
variable?
● Is a link unidirectional or bi-directional? Better be bi-directional
Operating System Concepts – 9th Edition 3.16 Silberschatz, Galvin and Gagne ©2013
Message Passing (Cont.)
■ Implementation of communication link ● Physical:
! Shared memory ! Hardware bus ! Network
● Logical:
! Direct or indirect
! Synchronous or asynchronous ! Automatic or explicit buffering
Operating System Concepts – 9th Edition 3.17 Silberschatz, Galvin and Gagne ©2013
Direct Communication
■ Processes must name each other explicitly: ● send(P,message)–sendamessagetoprocessP
● receive(Q, message) – receive a message from process Q
■ Properties of communication link
● Linksareestablishedautomatically
● Alinkisassociatedwithexactlyonepairofcommunicating processes
● Betweeneachpairthereexistsexactlyonelink
● Thelinkmaybeunidirectional,butisusuallybi-directional
■ A symmetrical model is always best. Asymmetric, unidirectional models,
such as mailboxes, quickly become cumbersome.
Operating System Concepts – 9th Edition 3.18 Silberschatz, Galvin and Gagne ©2013
Indirect Communication
■ Messages are directed and received from mailboxes (also referred to as ports)
● Eachmailboxhasauniqueid
● Processescancommunicateonlyiftheyshareamailbox
■ Properties of communication link
● Linkestablishedonlyifprocessesshareacommonmailbox
● Alinkmaybeassociatedwithmanyprocesses
● Eachpairofprocessesmayshareseveralcommunicationlinks ● Linkmaybeunidirectionalorbi-directional
Operating System Concepts – 9th Edition 3.19 Silberschatz, Galvin and Gagne ©2013
Indirect Communication
■ Operations
● createanewmailbox(port)
● sendandreceivemessagesthroughmailbox ● destroyamailbox
■ Primitives are defined as:
send(A, message) – send a message to mailbox A receive(A, message) – receive a message from mailbox A
Operating System Concepts – 9th Edition 3.20 Silberschatz, Galvin and Gagne ©2013
Indirect Communication
■ Mailbox sharing
● P1, P2, and P3 share mailbox A ● P1, sends; P2 and P3 receive ● Whogetsthemessage?
■ Solutions
● Allowalinktobeassociatedwithatmosttwoprocesses
● Allowonlyoneprocessatatimetoexecuteareceive operation
● Allowthesystemtoselectarbitrarilythereceiver. Sender is notified who the receiver was.
■ Too fancy by half. Keep it simple.
Operating System Concepts – 9th Edition 3.21 Silberschatz, Galvin and Gagne ©2013
Synchronization
■ 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 ● Then need flow control at the API
● Non-blocking receive -- the receiver receives:
● A valid message, or
● Null message
■ Different combinations possible
● Ifbothsendandreceiveareblocking,wehavearendezvous
Operating System Concepts – 9th Edition 3.22 Silberschatz, Galvin and Gagne ©2013
Synchronization (Cont.)
■ Producer-consumer becomes trivial
message next_produced;
while (true) {
/* produce an item in next produced */
send(next_produced);
}
message next_consumed; while (true) {
receive(next_consumed);
/* consume the item in next consumed */ }
Operating System Concepts – 9th Edition 3.23 Silberschatz, Galvin and Gagne ©2013
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 (rendezvous)
2. Bounded capacity – finite length of n messages
Sender must wait if link full
3. Unbounded capacity – infinite length
Sender never waits
3. (only seems like it is infinite)
Operating System Concepts – 9th Edition 3.24 Silberschatz, Galvin and Gagne ©2013
Examples of IPC Systems - POSIX
■ POSIX Shared Memory
● Processfirstcreatessharedmemorysegment
shm_fd = shm_open(name, O CREAT | O RDWR, 0666);
● Alsousedtoopenanexistingsegmenttoshareit ● Setthesizeoftheobject
ftruncate(shm fd, 4096);
● Nowtheprocesscouldwritetothesharedmemory sprintf(shared memory, "Writing to shared
memory");
Operating System Concepts – 9th Edition 3.25 Silberschatz, Galvin and Gagne ©2013
IPC POSIX Producer
Operating System Concepts – 9th Edition 3.26 Silberschatz, Galvin and Gagne ©2013
IPC POSIX Consumer
Operating System Concepts – 9th Edition 3.27 Silberschatz, Galvin and Gagne ©2013
Examples of IPC Systems - Mach
■ Mach communication is message based
● Evensystemcallsaremessages
● Eachtaskgetstwomailboxesatcreation-KernelandNotify
● Onlythreesystemcallsneededformessagetransfer
msg_send(), msg_receive(), msg_rpc()
● Mailboxesneededforcommuication,createdvia port_allocate()
● Sendandreceiveareflexible,forexamplefouroptionsifmailboxfull: ! Wait indefinitely
! Wait at most n milliseconds
! Return immediately
! Temporarily cache a message
Operating System Concepts – 9th Edition 3.28 Silberschatz, Galvin and Gagne ©2013
Examples of IPC Systems – Windows
■ Message-passing centric via advanced local procedure call (LPC) facility
● Onlyworksbetweenprocessesonthesamesystem ● Usesports(likemailboxes)toestablishandmaintain
communication channels
● Communicationworksasfollows:
! The client opens a handle to the subsystem’s connection port object.
! The client sends a connection request.
! The server creates two private communication ports
and returns the handle to one of them to the client.
! The client and server use the corresponding port handle to send messages or callbacks and to listen for replies.
Operating System Concepts – 9th Edition 3.29 Silberschatz, Galvin and Gagne ©2013
Local Procedure Calls in Windows
Operating System Concepts – 9th Edition 3.30 Silberschatz, Galvin and Gagne ©2013
Communications in Client-Server Systems
■ Sockets
■ Remote Procedure Calls
■ Pipes
■ Remote Method Invocation (Java)
Operating System Concepts – 9th Edition 3.31 Silberschatz, Galvin and Gagne ©2013
Sockets
■ Sockets are intended as IPC between systems, but is very limited.
■ A socket is defined as an endpoint for communication
■ Concatenation of IP address and port – a number included at start of message packet to differentiate network services on a host
! This last is only partially true. It has been overloaded for this purpose.
■ The socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8 ! Not true. It refers to port 1625 on interface 161.25.19.8.
! The IP address does not name the host.
■ Communication consists between a pair of sockets
■ All ports below 1024 are well known, used for standard services
● Echoes of early OSs, where apps were accessed by a jump through a low
memory address that points to the code for the app.
■ Special IP address 127.0.0.1 (loopback) to refer to system on which process is running
Operating System Concepts – 9th Edition 3.32 Silberschatz, Galvin and Gagne ©2013
There is Much to Clarify Here
■ Sockets exposes too much to the application, no abstraction.
● There is no reason for the application to see the address.
● The port
■ The original Network Unix API was simply file_io.
● open, close, send, receive,
● where the file name had the form
! e.g.
■ Port-ids are more complicated. The same identifier is overloaded to be:
! a file-descriptor or “handle”
! a connection-endpoint-identifier (its primary purpose)
! an application-identifier (This is analogous to an early OS practice of accessing
applications by having jump points in low memory locations.)
■ It has been shown that there are major advantages to having distinct identifiers for all three. But that is for another course.
■ But to see what Sockets (and TCP) are doing, let go back to the IPC Model
● What happens when we extend it to IPC between two applications in two systems?
Operating System Concepts – 9th Edition 3.33 Silberschatz, Galvin and Gagne ©2013
2: Two Application Communicating in Distinct Systems
Systems
Application Processes
IPC-Facility
© John Day,
34
All Rights Reserved, 2009
How Does It Work Now?
Application Processes
Port Ids
1) A invokes the IPC Facility to allocate a channel to B; a <- Allocate (B, x); 2) IPC determines whether it has the resources to honor the request.
3) If so, IPC uses “search rules” to find B.
- Management of name space is no longer under the control of a single system. - Each system no longer knows all available applications.
- Need to tell the other side what to do with the stuff being sent to it!
- Local Access Control can no longer be relied on to provide adequate authorization and
Protocol
Protocol
authentication.
- And we no longer have shared memory.
• Need a protocol between the two systems.
© John Day,
35
All Rights Reserved, 2009
What Happens Inside Now
System A
Write(port-id, buffer) Links Buffer
IPC Facility
Read(port-id, buffer)
System B
Queue
Protocol-Data-Unit (PDU)
Queue
• Now we have real problems! We need a queue at each end and
• What needs to be in the PDU?
– Detect lost or corrupt PDUs, delimit and pack SDUs as User Data, and
• We need synchronization locally for the queues but we also need synchronization between the systems for flow and retransmission control
– Tell the sender how much it can send, and what needs to be retransmitted.
© John Day,
36
All Rights Reserved, 2009
What Does an EFCP Look Like? • Symmetric Protocol to provide error and flow control
• Transfer PDU
Keeping order Catches errors or detect a missing one
• Ack and Flow Control PDU types Got those!
These can have errors too!
Don’t send more than this many
Xfr
Seq #
CRC
User-Data
Ack
Seq #
CRC
Ack Seq#
Flow Seq #
CRC
Credit
Might combine these Curious, no user data here either.
© John Day,
37
All Rights Reserved, 2009
What Happens Inside Now
System A
Write(port-id, buffer) Links Buffer
IPC Facility
Read(port-id, buffer)
System B
Queue
Re-xmsn Queue
Protocol-Data-Unit (PDU)
Queue
Re-xmsn Queue
• We need a queue at each end for both data to send and for retransmissions, if data sent is not ack’ed
• The PCI tells the other end what to do with the data and to maintain the synchronization, i.e. the state
• We will go into greater detail later on exactly how this works.
© John Day,
38
All Rights Reserved, 2009
3: Simultaneous Communication
Between Two Systems i.e. multiple applications at the same time
• To support this we have multiple instances of the EFCP.
EFCP EFCP
EFCP EFCP
EFCP
EFCP
Will have to add the ability in EFCP to distinguish one flow from another.
Dest-port
Src-port
Op
Seq #
CRC
Data
11/01/06
Connection-id
Typically use the port-ids of the source and destination.
Also include the port-ids in the information sent in IAP to be used in EFCP
synchronization (establishment).
© JohnDay, 39 All Rights Reserved, 2009
11/01/06
All Rights Reserved, 2009
What Does This Tell Us?
• Basically, Sockets exposes the details of the protocol to the application. There is no black box, no abstraction.
• What about addresses?
– They come later when there are more than 2 members of a layer.
• We saw that the ‘port-id’ fields in TCP and UDP are really there as a connection or flow identifier.
• If the “flow” is the shared state between the protocol machines, then the identifier in the protocol is really a connection-endpoint-id.
• Port-id is the handle for application
• Then how come they are used to identify applications as well?
– A 1970 short term kludge to demonstrate the ARPANET.
• Be careful about kludges you may have to live with them a long time
• But no application-name. A domain name is a macro for an IP address,
and a URL names a path to the application, not the application.
© John Day,
40
Socket Communication
Operating System Concepts – 9th Edition 3.41 Silberschatz, Galvin and Gagne ©2013
Sockets in Java
■ Three types of sockets
● Connection-oriented
(TCP)
● Connectionless(UDP)
● MulticastSocket class– data can be sent to multiple recipients
■ Consider this “Date” server:
Operating System Concepts – 9th Edition 3.42
Silberschatz, Galvin and Gagne ©2013
Remote Procedure Calls
■ Remote procedure call (RPC) abstracts procedure calls between processes on networked systems
● Againusesportsforservicedifferentiation
■ Stubs – client-side proxy for the actual procedure on the
server
■ The client-side stub locates the server and marshalls the parameters
■ The server-side stub receives this message, unpacks the marshalled parameters, and performs the procedure on the server
■ On Windows, stub code compile from specification written in Microsoft Interface Definition Language (MIDL)
Operating System Concepts – 9th Edition 3.43 Silberschatz, Galvin and Gagne ©2013
Remote Procedure Calls (Cont.)
■ Data representation handled via External Data Representation (XDL) format to account for different architectures
● Big-endian and little-endian
■ Remote communication has more failure scenarios than local
● Messagescanbedeliveredexactlyonceratherthanatmost once
● These distinctions are based on a misunderstanding of how it works.
● Semantics are exactly once or maybe once or more
■ OS typically provides a rendezvous (or matchmaker) service to
connect client and server
■ Problems are worse: Many OSs map these request/response services to UDP. If the request and response don’t fit in one UDP packet, there is no guarantee of delivery of everything.
Operating System Concepts – 9th Edition 3.44 Silberschatz, Galvin and Gagne ©2013
Execution of RPC
Operating System Concepts – 9th Edition 3.45 Silberschatz, Galvin and Gagne ©2013
Pipes
■ Acts as a conduit allowing two processes to communicate
■ Issues:
● Iscommunicationunidirectionalorbidirectional?
● Inthecaseoftwo-waycommunication,isithalforfull-
duplex?
● Mustthereexistarelationship(i.e.,parent-child)between the communicating processes?
● Canthepipesbeusedoveranetwork?
■ Ordinary pipes – cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it created.
● Pipes are blocking and not good for bi-directional uses. ■ Named pipes – can be accessed without a parent-child
relationship.
Operating System Concepts – 9th Edition 3.46 Silberschatz, Galvin and Gagne ©2013
Ordinary Pipes
■ Ordinary Pipes allow communication in standard producer-consumer style
■ Producer writes to one end (the write-end of the pipe)
■ Consumer reads from the other end (the read-end of the pipe)
■ Ordinary pipes are therefore unidirectional
■ Require parent-child relationship between communicating processes
■ Windows calls these anonymous pipes
■ See Unix and Windows code samples in textbook
Operating System Concepts – 9th Edition 3.47 Silberschatz, Galvin and Gagne ©2013
Named Pipes
■ Named Pipes are more powerful than ordinary pipes
■ Communication is bidirectional
■ No parent-child relationship is necessary between the communicating processes
■ Several processes can use the named pipe for communication
■ Provided on both UNIX and Windows systems
Operating System Concepts – 9th Edition 3.48 Silberschatz, Galvin and Gagne ©2013
End of Chapter 3b
Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013