Message PassingWhat is it?Asyn. vs. Syn.Fully Asyn., FIFO and CausalChannelChannel (cont’d)Logical TimestampsSlide 8OO Definitionclass Mailbox (syn.)class Port (syn.)class Link (syn.)class Mailbox (asyn.)class Port and Link (asyn.)Revisit BB problemSocketsSockets (cont’d)TCP vs. UDPTCP sockets in Java (client)TCP Sockets in Java (server)TCP Comm. ModelSlide 22Event orderTime-space DiagramIncorrect & Arbitrary orderingLogical ClockHappen-before RelationHappen-before Relation (cont’d)Integer TimestampsInteger Timestamps (cont’d)Slide 31Slide 32Vector TimestampsVector Timestamps (cont’d)Slide 35Slide 36Slide 37Slide 38Slide 39Distributed MEPermission-based AlgorithmPriority SchemePriority Scheme (cont’d)Distributed R==W.2Distributed R==W.2 (cont’d)Advanced Topics in Software Engineering 1Message Passing Introduction Comm. Channels Logical Timestamps Message-Based SolutionsAdvanced Topics in Software Engineering 2What is it?Message passing is a method for threads to communicate/synchronize with each other by sending and receiving messages. In a distributed environment, message passing is often the only option that is available for thread communication.Advanced Topics in Software Engineering 3Asyn. vs. Syn.Message passing can be asynchronous or synchronous, depending on the types of send and receive operations used.Asynchronous communication uses non-blocking send and blocking receive. With synchronous communication, both send and receive are blocking.Advanced Topics in Software Engineering 4Fully Asyn., FIFO and CausalFor asyn. comm., different comm. schemes can be further identified: Fully Asyn.: Messages are not necessarily received in the same order as they are sent. FIFO: Messages sent from the same sender to the same receiver must be received in the same order as they are sent. Causal: Messages sent to the same destination must be received in the same order as they are sent.Advanced Topics in Software Engineering 5ChannelA communication path between threads is often referred to as a channel, which can be a mailbox, port or link. mailbox: many senders and many receivers may access a mailbox object. port: many senders but only one receiver may access a port object. link: only one sender and one receiver may access a link object.Advanced Topics in Software Engineering 6Channel (cont’d)If shared memory is available, then a channel can be implemented as a shared object.Otherwise, a channel needs to be built on top of a network connection such that messages can be transported across the network.Advanced Topics in Software Engineering 7Logical TimestampsMany distributed solutions require the ability to determine the order of events, i.e., which one happens first.Because of the problem of clock synchronization, events are often stamped with logical time, instead of wall clock time.Common types of timestamps include integer timestamp, vector timestamp and matrix timestamp.Advanced Topics in Software Engineering 8Message Passing Introduction Comm. Channels Logical Timestamps Message-Based SolutionsAdvanced Topics in Software Engineering 9OO Definitionpublic abstract class Channel {public abstract void send (Object m);public abstract void send ();public abstract Object receive ();}Advanced Topics in Software Engineering 10class Mailbox (syn.)public class Mailbox extends Channel {private Object msg = null;private final Object sending = new Object ();private final Object receiving = new Object ();private final BinarySemaphore sent = new BinarySemaphore (0);private final BinarySemaphore received = new BinarySemaphore (0);public final void send (Object msg) {if (msg == null) throw new NullPointerException (“Null message passed to send ()”); }synchronized (sending) {this.msg = msg;sent.V ();received.P ();}}public final void send () {synchronized (sending) {msg = new Object ();sent.V ();received.P ();}}public final Object receive () {Object rval = null;synchronized (receiving) {sent.P ();rval = msg;received.V ();}return rval;}}Advanced Topics in Software Engineering 11class Port (syn.)public final Object receive () {synchronized (receiving) {if (receiver == null) {receiver = Thread.currentThread ();}if (Thread.currentThread () != receiver) {throw new InvalidPortUsage (“Attempted to use port with multiple receivers”);}Object rval = null;sent.P ();rval = msg;received.V ();}return rval;}The send methods for classes Port and Mailbox are the same. As only one thread can receive from a port, the receive method is modified as follows.Advanced Topics in Software Engineering 12class Link (syn.)The receive methods for class Link and Port are the same. As only one sender can send to a link object, the send method needs to check for multiple senders.Advanced Topics in Software Engineering 13class Mailbox (asyn.)public class Mailbox extends Channel {private final int capacity = 100;private Object msgs [] = new Object [capacity];private CountingSemaphore msgAvail = new CountingSemaphore (0);private CountingSemaphore slotAvail = new CountingSemaphore (capacity);private final BinarySemaphore senderMutex = new BinarySemaphore (1);private final BinarySemaphore receiverMutex = new BinarySemaphore (1);private int in = 0, out = 0;public final void send (Object msg) {if (msg == null) throw new NullPointerException (“Null message passed to send ()”); }slotAvail.P ();senderMutex.P ();msgs [in] = msg;in = (in + 1) % capacity;senderMutex.V ();msgAvail.V ();}}public final void send () {// same as send(Object msg) except that “msgs[in] = msg;” becomes “msgs[in] = new Object ();}public final Object receive () {msgAvail.P ();receiverMutex.P ();Object rval = msgs [out];out = (out + 1) % capacity;receiverMutex.V ();slotAvail.V ();return rval;}}Advanced Topics in Software Engineering 14class Port and Link (asyn.)In the Port class, method receive must check for multiple receivers. In addition, receiverMutex is not needed. (Why?)In the Link class, methods send and receive must check for multiple senders and receivers. In addition, both senderMutex and receiverMutex are not needed. (Why?)Advanced Topics in Software Engineering 15Revisit BB problempublic final class BoundedBuffer {public static void main (String args []) {Link deposit = new Link ();Link withdraw = new Link ();Producer producer = new Producer (deposit);Consumer consumer = new Consumer (withdraw);Buffer buffer = new Buffer (deposit, withdraw);buffer.setDaemon