CS 133 Discussion: Week 4

• Homework Clarification
• Parsec Example

  P(S);
  items--;
  V(S);
  return buffers[items];

  P(S);
  BufferItem item = buffers[items-1];
  items--;
  V(S);
  return item;

Homework Clarification

• Due date is Monday at 11:59pm.
• You do have to handle the case where a philosopher has more than two neighbors. I won't test any cases where the philosopher has no neighbors, but you should be able to handle it anyway.
• The program must terminate shortly after 60 seconds, not exactly.
• Its shows me you care if you can avoid using pc_exit(), but I won't take off credit if you don't.
• The purpose of the hold(0) is to allow non-adjacent philosophers to eat at the same time. Interpret "hold(0)" to mean "yield()"

Fairness Problem

MPC is optimized to process local messages first. If there's an enabling message from another entity on the same processor, that message will be executed in favor of a message from a remote processor. This leads to the unfortunate possibility of an infinite loop.

#include 

message Ping{int id; ename reply_to;};
message Die{};

entity Remote (ename target1, ename target2) {
  send Die{} to target1;
  send Die{} to target2;
}

entity Local (int myno) {

  int i = 0;

  while (1) {
    receive (Die d) {
        break;
    }
    or receive (Ping p) {
      i++;
      printf("\n Entity No %d: message %d, number = %d", myno, p1.id, i); 
      send Ping{p.id, self} to p.reply_to;
    }
  }
}

entity driver (int argc, char** argv) {
  ename e1, e2, e3;
  e1 = new Local(1) at 0;
  e2 = new Local(2) at 0;
  e3 = new Remote(e1, e2) at 1;
  send Ping{1, e2} to e1;
}

If we run this program on a single processor, the sequence of events is roughly as follows:

1. The driver runs to completion.
2. Entity e1 is created, receives a Ping message sent by the driver, and sends it to e2.
3. Entity e2 is created, receives a Ping message sent by e1, and sends it back to e1.
4. Entity e3 is created, and sends Die messages to both e1 and e2, then terminates.
5. Entities e1 and e2 receive the Die messages and terminate.

1. same
2. same
3. same
4. Entity e3 is created on a remote processor, sends Die messages to e1 and e2, and terminates. Because of the transmission delay, this may take some time.
5. In the meantime, e1 and e2 Ping each other mercilessly.
6. Eventually, the Die messages arrive at processor 0 and are temporarily placed in a special queue of remote messages.
7. Entity e1 (or e2) is activated. It has a message waiting from another local entity e2 (respectively e1), therefore it accepts this message without checking the remote queue.
8. Repeat step 7.

In some sense, the program behavior is still legal. Parsec/MPC semantics state that if two enabling messages of different types (i.e. Die and Ping) are available, a non-deterministic choice will be made between them. However, suppose we change the code to read:

or receive (Ping p) when (qempty(Die)) {