Input

Your program will read its input from stdin.  The input format is the same as in Assignment 3 with the addition of two primitives: SEND and RECV.

The Address is a positive integer that encodes the node and the process ID of the process using the fol- lowing formula:

Address = (Node ID) * 100 + (Process ID)

For example, process address 314 means the process is on node 3 and has process ID 14.  Both Node IDs and Process IDs are positive values.

Processing

Processing is the same as in Assignment 3 along with the following additions.

Clock Synchronization

The clocks need to be synchronized across all nodes. The standard solution is to invoke a barrier operation immediately before incrementing the clock variable.  While some pthread libraries do provide a barrier operation, it is recommended that you implement your own.  The reason is that the provided implemen- tation does not support decreasing the number of threads when a thread finishes its simulation.

Implement your own barrier as a monitor, using a mutex lock and condition variables.   The recommended approach is to implement a monitor with three functions:

.    barrier init(n) : initialize barrier with initial number of threads

.    barrier wait() : perform barrier operation

.    barrier_done() : called by thread that is done its simulation (decrements number of threads that need to synchronize)

Note: the above is pseudo code and does not show the lock you will need to protect the monitor or the condition variable(s).  Also, this implementation suffers from a small bug where a thread may clear the barrier, increment the clock, loop around and try to perform the barrier again before all the other threads have left. Hint: To avoid this, use two condition variables (instead of one) and alternate between them, so that all the odd barrier synchronizations use one condition variable and all the even barrier synchroni- zations use the other condition variable.

Main Simulation Loop

A SEND and RECV are special forms of DOOP.  If a process’s next primitive it a SEND or RECV, it should be treated exactly as a process about to perform a DOOP and be inserted into the ready queue.  In the clock tick after the process transition from ready to running, it performs a send to or receive from the process specified by the address and transitions from running to blocked (send) or blocked (recv) state.

The send or receive is done by calling the send() and recv() functions provided by the message passing facility that you will implement.  Thus, these primitives take at minimum two clock ticks to execute.

The main simulation loop (in each node) should be adjusted as follows:

1. Unblock processes:

a.    Unblock processes that have completed their SEND or RECV

b.    Remove processes from the blocked queue that are ready to be unblocked.

For each unblocked process handle them in the same way as in Assignment 3

Note: treat a SEND or a RECV like a DOOP in terms of deciding which queue to insert processes into. 2. Update Running process, if a process is currently in a Running state,

a.    If a process is performing a SEND or RECV call the send() or recv() functions provided by the mes- sage passing facility and transition the processes to blocked (send) or blocked (recv) states.

b.    Otherwise, treat the process in the same way as in Assignment 3.

3. Select next process to run, same way as in Assignment 3

4. Increment clock, be sure to use a barrier before the increment.

Once all nodes have completed the simulation, the main thread prints out a summary of all processes in the order that the finished.  (See Output section.)

The Message Passing Facility

A message passing facility should be implemented to model the message passing between processes. There is no need to copy any data between processes, but the facility should model the synchronization between a sender and a receiver during a synchronous send.  Only two operations need to be modeled:

. Synchronous Send: process sends a message to a specified receiver and blocks if the receiver is not waiting to receive.

. Synchronous Receive: process receives a message from a specified sender and blocks if the sender is not waiting to send.

Note: “Receive Any” is not required, and hence your facility will not need message queues.

It is recommended that the message passing facility provide (at least) the following two operations with the following semantics:

Note that the sender and receivers may be on different nodes or the same node.

An additional function that returns a list of all processes (on the current node) that have completed their SEND or RECV will be useful to implement Step 1(a) of the simulation loop.   If two or more processes complete their communication at the same time, then they should be ordered according to their process IDs.  I.e., processes with lower IDs come first.

Summary Statistics

The simulator should keep the same summary statistics as before, as well as the number of SENDs and RECVs that are performed.

Output

The output for this assignment is the same as that of Assignment 3, except that there are two additional blocked states:

.    blocked (send) : when a process calls the send() function of the message passing facility

.    blocked (recv) : when a process calls the recv() function of the message passing facility

The output summary for each process is extended from Assignment 3 and should be of the form:

where

. Time is the finish time of the process.

. Node is the node on which the process was simulated.

. PID is the process id of the process.

. run_time is the sum ticks of all DOOPs performed by the process.

. block_time is the sum ticks of all BLOCKs performed by the process.

. wait_time is the sum ticks that the process spent in the ready queue.

. send_cont is the number of sends performed by the process

. recv_count is the number of receives perfomed by the process

All conditions from Assignment 3 apply.

Example: