Homework 12

22C:116, Fall 1995

Due Friday Nov. 17, 1995, in class

1. Background: The Charm system is the result of a research project at Purdue, Illinois and Iowa; it is, in many ways, akin to a user level thread package, but it also relates closely to the pop-up threads discussed in section 12.1.5. As is traditional in all too-much of computer science, the developers of Charm invented new terminology for many of the operations of their package. Recast in traditional terms, here is how Charm works:

   All message receipt on Charm is by pop-up threads. The Charm objects that receive messages are procecure-like objects called Chars; an activation of a Char is created for each message addressed to that Char, and that activation is deallocated when the Char exits. The formal parameters of a Char define the format of all messages addressed to that Char, and a Char may pass messages to other Chars using a procedure-call-like syntax. The different instances of a Char may share static variables with each other in addition to using their dynamically allocated temporary variables.

   Consider the following example Char that passes a message to H and R each time it receives a message:

   char C(A,B)
   {
           H(A + B);
           R(A - B);
   }
   

   Typically, each Char is implemented as a procedure, called by a main server process that receives messages and disburses them to the Chars it is in charge of. Each call to one Char from another is replaced by a message passed to the server in charge of that Char. Thus, the above code is implemented as:

   void C(A,B)
   {
   	struct message msg;
   	msg.dst = server(H);
   	msg.tag = H;
           msg.body = A + B;
           send(msg);
   	msg.dst = server(R);
   	msg.tag = R;
           msg.body = A - B;
           send(msg);
   }
   

   Part A: Translate the above code for the Char C to equivalent code for a conventional thread that uses blocking buffered message passing with the primitives send and receive. This problem should be solved without reference to the char implementation outlined above!

   Part B: Write the code for a Charm server supporting the implementation outlined above. This server should accept messages addressed to any of a number of Chars. Given one CPU per server and a good computer network, your server should yield a reasonable performance! Assume blocking buffered message passing, as above.

2. Background: Consider the problem of load balancing on a Charm system on a multiprocessor, where each charm server communicated with the others using the UNIX socket mechanism, and where the Charm servers have access to all of the UNIX kernel services to monitor their own performance. In addition, assume that all code for all Chars is replicated on every machine, and that the data structures in each machine record which Chars are currently being served by which machine. The answers to this question should be given as high level descriptions, not code!

   Part A: How would you detect that the load on such a system was unbalanced?

   Part B: How would you determine which machine in the system should shed part of its load and which machine would accept that excess work?

   Part C: How would you actually move the processing of a Char from one machine to another?