Semantics of Send and Receive
• Can be blocking (“synchronous”) or nonblocking (“asynchronous”)
– remember:
• procedure call is synchronous • thread fork is asynchronous
– send, receive both have synchronous and asynchronous implementations
P1
send
(blocked) proceed
Data
“Go ahead”
P2
receive
(blocked)
consume message
Picture of Synchronous Send, Blocking Receive
Sieve of Eratosthenes: Find primes <= N 1. Add the number 2 to the set of primes 2. Create a list of consecutive odd integers 3. Let p = 3, the first prime number (besides 2) 4. Count up from p and cross out all multiples of p 5. Add p to the set of primes 6. Set p = the smallest number not crossed out 7. If p <= N, goto step 4; else quit Picture of Sieve of Eratosthenes Sieve of Eratosthenes Using Synchronous Message Passing process Sieve[1] { for j = 3 to N by 2 Sieve[2]!j } • Uses CSP notation: ? (receive) and ! (send) } if (num mod p != 0) Sieve[i+1]!num • Terminates in deadlock, but this could be fixed • MAX must be large enough to guarantee all primes generated } process Sieve[i = 2 to Max] { Sieve[i-1]?p print “found a prime”, p while (Sieve[i-1]?num) { P1 send proceed Data P2 receive (blocked) consume message Picture of Asynchronous Send, Blocking Receive Implementation of Asynch. Send/ Blocking Receive • Library must keep track of all channels – one buffer and one semaphore per channel at receiver • On Send(channel, userSpecifiedData) – copy userSpecifiedData into sender-side buffer – (buffer eventually put onto network) • On Receive(channel, userSpecifiedData) – P(thisQueue); copy buffer into userSpecifiedData • On incoming message (specifies channel) – copy message into receiver-side buffer; V(thisQueue) Tradeoffs in Message Passing • Advantages of blocking send – won’t overwrite message, less buffering • Advantages of nonblocking send – can continue after send (can do other work) – but what if the buffer is full? Block? Fail? • Advantages of blocking receive – know message is received, avoid polling • Advantages of nonblocking receive – can result in fewer copies (buffer posted in advance)