snetdev/snet-rts — pull request #31 by nguyenvuthiennga (2013-01-30 17:00:03+00:00)
Title: fix GC behavior (see the GC report for more detail)

The old implementation enforces the star operation to unroll in the deterministic manner:
• After a synchrocell gets all its patterns (i.e. synchronised), it sends a REC sync with a special property called ”out-type”.
• All SNet entities when receive a REC sync will replace the stream (based on the info inside the record). Only parallel entities detect REC sync with out-type.
• A parallel entity will check if its output streams (branches) still accept this out-type. If not, it sends a REC terminate (for garbage collection). Otherwise, it sends a REC sort end.
• A collector entity holds two lists of input streams (branches): waiting-list from which it will not get the data; and ready-list from which git get data.
• A collector entity when receives REC sort end from a stream moves the stream to the waiting-list. When receiving a REC terminate from a stream, it removes the stream from the ready-list.
• Streams in the waiting-list are restored to the ready-list only when the ready-list becomes empty.
• If there is only one stream in the ready-list and no stream in waiting-list, the collector terminates itself.

When a parallel entity receives a REC sync from the previous syncro-cell, it sends REC sort end to all branches which are still active, i.e. accept the out- type after the syncro-cell terminates. As the collector entity receives REC sort end from the parallel entity and blocks active branches until other branches termi- nate, it forces data records to wait and therefore forces the star operation to unroll after the first instance finished.

This is how it is fixed:
• The parallel entity after receiving the REC sync, it sends to REC terminate to inactive branches. If it has more than one branches left, it operates as normal. Incoming data records will be still sent and eventually reach the collector and continues as normal.
• If the parallel entity has one branch left, it will terminate itself. The paired continues receives records from all branches. Until all the inactive branches terminate, the collector has only one branch left and will terminate itself.
• When the parallel entity terminates, it should notify its paired collector. It is done by sending a special REC sort end with level = 0, counter = −1. Here we reuse the REC sort end mechanism so that if it has to pass a hierarchy of parallel/collector or star/collector or split/collector, its level will be modified. And only when it reaches the paired collector, its level remains 0.
• A collector entity when receiving this special REC sort end from one branch, it learns that all other branches will terminate soon. It marks this branch as last.
• After last has been set, if a collector receives a REC sort end, it knows that this record’s level has not been increased as it should be. It then increased the level by 1 as process as normal. This means the last will be blocked.
• When a collector terminates and its last is blocked, it should behave as if it had received the REC sort end from all other branches. It then send out a REC sort end if required (i.e. the REC sort end level is higher than 0).