[Shootout-list] ringmsg, text description

Bengt Kleberg bengt.kleberg@ericsson.com
Thu, 07 Oct 2004 13:19:49 +0200


greetings,

this is a ''about this test'' text description of what the ringmsg test 
should do. what is unclear? what can be better? what is wrong/inconsistent?


bengt


About this test

For this test, each program should be implemented to do the same thing.

This is a test of interprocess communication using message passing. The 
model for message passing is a simplifed version of UNIX SysV IPC. On 
the sender side message passing should not block the sender. For the 
receiver messages should arrive in one piece and they should be possible 
to receive selectivly.

Each test program should spawn N execution contexts (processes, though 
languages with limited concurrency can use threads). N will be the first 
argument to the test program. The number of messages between these 
processes will be 128 * N. This number (128) comes from a study of 
erlang. The cost of creating a process was compared to the cost of 
sending a message. At 128 messages to each process the time spent in 
process creation was less than 10% of the total run time (excluding 
start/stop). When your favorite language is added we will change 128 to 
something that matches the relative performance of process 
creation/message passing in the new language. To make it simple to 
change we have 128 as the second argument to the test program.

The test program should spawn N execution contexts. One execution 
context should be the master/controller. It will behave differently from 
the others. The others (N-1) should all do the same thing. When the 
master stops it should return the payload of the last message passed 
around the ring. This payload shall be displayed, and should normally be 
the only thing printed by the test. If at any time an unknown sender is 
found to have sent a high priority message, the test program must report 
this in its output. Since this is a failure the test may stop right there.

The algorithm for the first process (master/controller) shall be as follows:

    1. The first process will send two messages to the second in the 
ring. The first message will be low priority, the second will be high 
priority. The payload of the high priority message must be something 
that will display as ''the_ring''.
    2. When the high priority message has made it all the way around the 
ring of processes back to the first process, it must come from the last 
process. Increment the message counter with one.
    3. If we have reached 128*N, stop.
    4. Otherwise, the controller should now send a low priority message 
followed by a high priority message. This time they should be sent to 
the last process in the ring, ie in the other direction.
    5. When we now receive the high priority message it has made it all 
the way around the ring of processes. It must come from the second 
process. Increment the message counter with one.
    6. If we have reached 128*N, stop.
    7. Otherwise, repeat from the beginning
    8. If we receive low priority messages, increment the message 
counter with one.
    9. If we have reached 128*N, stop.
   10. Otherwise, just wait for more messages. Nothing is sent from the 
process.

The algorithm for all the other processes shall be as follows:

    1. The process starts in a state of "Hard Work". This state is 
defined as one where we only receive high priority messages.
    2. This process shall receive high priority messages from any 
process before or behind itself.
    3. Check the sender of the message. If it is from the process 
infront of us, send to to the process after. If it is from the process 
after of us, send to to the process infront. Always send first a low 
priority message, then a high priority message with the same payload as 
in the message we received.
    4. When four (4) high priority messages have been received, the 
process is no longer doing "Hard Work". It shall enter a new state, 
"Resting". In this state it should also be possible to receive low 
priority messages.
    5. As long as we only receive low priority messages we stay in 
"Resting". Nothing is sent from the process while "Resting".
    6. When the first high priority message arrives while "Resting" we 
stop receiving low priority messages. Another period of hard "Hard Work" 
starts. Repeat from 3.