link_number retlink -- index of free slot in link table link_number paramlink -- index of free slot in link table -- initialization of widget server -- distributes box 0 to potential clients set_of_boxes s add_to_set( s, 0 ) loop -- main loop of server box_number w = wait_set( s ) if w = 0 -- create widget receive(0,nil,0,nillink,retlink) w = index of free entry in widget table init_widget(w) make-box(w,paramlink) send(retlink,nil,0,paramlink,nillink) else -- manipulate widget w buffer b[size] receive(w,b,size,nil,retlink) if b = "twiddle" twiddle_widget(w) send(retlink,"ok",3,nillink,nillink) elseif b = "morph" morph_widget(w) send(retlink,"ok",3,nillink,nillink) else send(retlink,"error",6,nillink,nillink) endif endif endloopPart B: Does your code from part A work correctly under both of models of interprocess communication, or does it depend on the one that is used. If the former, is it possible to build a server that does depend on the model; if the latter, which and why?
The code for part a works equally with buffered asynchronous and non-buffered synchronous message passing. So long as we use a synchronous RPC model of client-server interaction, where the client waits for the server to reply immediately after sending a request for service, there is no way to distinguish between these models. If the client tries to do some computation between sending the outgoing message and receiving the result, observable differences between these models will begin to emerge.
Busy waiting wastes CPU time, so if a process above the level of the scheduler uses Test and Set to implement mutual exclusion, it wastes CPU time. If the process calls sleep() once per iteration, it can reduce this waste. The challenge is to figure out how long to sleep. A fixed parameter value to sleep() will work, but an exponential backoff starting with a very short delay will gain entry very quickly of the process is waiting for a short critical section, while reducing CPU usage considerably if waiting for a very long critical section.Why set a maximum delay for the sleep() call? There is nothing incorrect about pure exponential backoff -- it will work, but if we know that the average time in the critical section is s seconds, there is no point in waiting longer than than O(s) for any one sleep. The constant multiplier depends on the probability distribution of the time in critical seciton.
To figure the diameter of the k by k toroidal network in Figure 8-16 d, first note that the interior of the rectangular mesh can be ignored, since all paths through this interior are either longer than paths around the perimeter or the same length. We are left with a ring network (not unlike part b of the figure if we discount the radial lines to the actual clients), with added paths joining opposing sides.For k odd, the longest path will be from a point on the center of one edge to a point on the center of a perpendicular edge of the mesh. The links crossing the body of the mesh are of no use, and our path is therefore of length k-1, from the center of the edge around one corner to the center of the next edge.
For k even, the longest path will be from a point just beyond the center of of one edge, around the more distant corner, to just beyone the center of the next edge. Along the path just described, there are k edges, and we can also go across the graph, around the opposite corner and across the graph again in k edges.
In the above, the fact that all clients are connected to the toroidal mesh by radial links changes the answers to k+1 and k+2 (adding the link from source client to mesh and from mesh to destination client).
First, emphatically, both shared memory and distributed systems may use two different semantic models, blocking synchronous message passing and non-blocking buffered message passing. On a shared memory system, we use a programmed memory-to-memory copy from the sender's buffer to the receiver's buffer to do this, while on the distributed system, we can set up the DMA controllers on the sending and receiving network connections to do this memory-to-memory transfer over the network, assuming that there are no store-and-forward links between sender and receiver.For the remainder of this answer, assume buffered message passing. First, in the shared memory case, we copy the message to an intermediate buffer (either space in a bounded buffer or a buffer that is linked into a queue of messages for the recipient), and then signal the semaphore on that queue. The recipient, on receiving a signal indicating an available message dequeues the message and copies it into the receiver's buffer. That is all that is needed.
In a distributed system, we add layers to this, with the sender's queue connected to the sender's network interface driver, which dequeues messages and sends them over the network (possibly with intermediate storage and forwarding). At the receiver's machine, the message is enqueued for delivery to the recipient. The net effect of this is that the total buffer capacity between sender and recipient is the sum of the sending machine's buffer capacity, the receiving machine's buffer capacity and the network's buffer capacity, if any.
The second difference is in the area of fault tolerance. On the shared memory machine, it is natural to assume delivery. On the network, if we want to guarantee delivery, send must hold a copy of the message (perhaps spawning a thread to take care of this) until the receiver acknowledges correct delivery. The sender must be prepared to retransmit if the receiver reports an error or does not acknowledge reciept. There are two alternatives to this, both of which require user awareness of changed semantics. First, we can move to a synchronous send, where the sending process is blocked until the message has been received, or we can require that the user code allow, at the application level, for failures.