Lecture notes for CSC 2/456, 10 April 2000ff MESSAGE PASSING (review for many of you, I know) sending no-wait send maximal concurrency buffering and flow control a problem error reporting a BIG problem -- the most common approach for OSes synchronization send fixes above problem requires high-level acks (inefficient on many substrates) -- used in CSP/Occam; not much elsewhere remote invocation send matches common algorithms no more expensive than synchronization send on most substrates (cheaper than pair of synchronization sends) -- used in RPC packages; occasionally supported directly by the kernel (see below) broadcast and multicast -- esp. important for group communication; more on this later Each of the three main options can implement the others, albeit with different efficiencies. The best performance for client-server communication (the most common case) uses a protocol devised for the V-kernel (Cheriton & Zwaenepoel) for use on local-area networks client server ------------------> request (timer started) <----------------- reply (timer started) copy of reply discarded If timeout, client re-sends. If server hasn't seen message before (original was lost), things just start over. If it has already sent a reply (lost), it re-sends it (it has to hang onto replies for possible resending, until the timer is known to have elapsed) If it has seen the message, but doesn't have a reply yet, it sends a "I got it; hold your horses" message. If that doesn't get through, the client will just re-send again. Usually, however, RPC is built on top of no-wait send, necessitating extra messages. connecting naming, ordering, buffering, and flow control can be thought of as being associated with a "communication path". Think of a "communication path" as the thing that you name when saying where to send a message to, or where to receive it from. arity of connections one-one, one-many, many-one, many-many communication paths (bound, output, input, and free ports) many-many introduces storage problems -- where do we keep information? connection-based v. connectionless: /\ topology / \ (physical layer) / \ fully connected point-to-point /\ resource allocation technique / \ (data link layer) / \ circuit switched packet switched /\ routing / \ (network layer) / \ virtual circuit datagram By far the most common strategy is that provided by Internet standards: IP address plus port number (ports 1024-4999 are typically available to arbitrary users; lower and higher numbers are reserved for super-user installed servers) TCP is virtual circuit based. UDP is datagram based. To send UDP messages you specify the address and port number of the recipient in every send operation. To send TCP messages you need a *connection*. Typically a TCP server "listens" on a well-known port number for a connection request. In Unix, this takes a series of four calls socket () -- create a new communication endpoint (like a file descriptor) bind () -- associate socket with a port number listen () -- specifies queue length for pending connection requests accept () -- accept a connection request on the socket; creates a new socket on which to communicate with client The TCP client for its part makes two calls: socket () -- create endpoint connect () -- establish connection with (new socket at) server Once connected, both the server and the client can send and receive. Java has a reasonably nice interface to this stuff in its standard library. receiving explicit and implicit receipt selectivity source local state availability (rarely) message content asynchronous receipt asynchronous and implicit often go together, but don't have to independence of sending and receiving choices --------------- RPC remote procedure call -- combination of remote-invocation send and implicit receipt (this is not a universally-accepted definition; some people use the term simply to mean r.i. send, but I think imp. rec. is crucial). implementation mechanisms built into programming language SR, Lynx, Hermes, Emerald, etc. *stub generator* -- tool that takes a .h file (or equivalent) and builds two hunks of custom code: one that preserves the .h-defined interface, but sends messages inside instead of performing the desired operation, and another for the remote end that receives the messages from the sending end and calls the desired procedure. Sending stub "marshalls" the parameters. explicit *binding* (connection creation) a key concept -- amortize authentication, error-checking, and initialization of data structures. This is in addition to TCP-style binding. exactly how the code works on the receiving end (who receives the message, and when) is tricky; see below Threads and RPC what happens on the receiving end of an RPC (implicit receipt)? options interrupt a running thread create new "lightweight" kernel thread, if OS supports RPC -- yuk have one or more kernel threads waiting. An awoken thread can serve the request itself (limits concurrency), fork a new thread, or (probably best) create a new thread iff there aren't enough left (adaptive) note that having multiple threads in the same task, e.g. in response to incoming RPCs, may *introduce* the need for synchronization. --------------- End-to-End Arguments (see Saltzer et al in TOCS 2,4, Nov 1984) Motivation: I want to move a file from one disk to another over the network. It is very important that the new copy be verified before I remove the old one. This verification requires me to check that the file is correctly written on the new disk (ie, I try to read it back and maybe compute a file-based checksum.) Since this verification is application dependent, NO lower layer can be expected to provide it. Therefore, any errors caught in lower layers would have been caught by my check => low level error handling isn't needed! End-to-end argument: Functions placed at a low level in the system may be redundant or of little value when compared with the costs of placing them at that level. Most functions can only be completely implemented with the help of the client. Attempts to provide partial implementation by lower levels are only performance optimizations. Example: Retransmitting packets that are mangled avoids retransmitting the whole file in the above scenario. Where a single packet is mangled, this is a big performance win. However, in terms of error detection the checksum for the file is the ultimate error check. --------------- low latency user-level messaging bypass kernel protocol stack 2-3 decimal orders of magnitude speed improvement use virtual memory for protection -- advance setup requires OS intervention Memory Channel, VIA, Scheduled Transfer, Myrinet, SCI, ... Usually memory-based: remote put. Requires either wire-down of memory or coordination between kernel and NIC, with shadow page tables in NIC. Sometimes remote get (harder: deadlock concerns). --------------- active messages Message indicates handler to be executed on remote end. Sort of a low-level, low-overhead RPC. Usually but not necessarily implemented in conjunction with user-level messaging. Without special HW, processor polls for requests at obvious places. If not handled within pre-determined time frame, sender or receiving NIC generates interrupt to force handling. --------------- group communication what for? data replication, consistency ISIS symmetric, distributed vector timestamps Amoeba simple, centralized potentially higher latency (2-hop)