Refactor Schedule Many

[mjp41]

The code in schedule many has been extended by two features:

• @marioskogias's https://github.com/microsoft/verona-rt/pull/24
• @vishalgupta97's https://github.com/microsoft/verona-rt/pull/45

Both of these lead to some complexity, and the schedule_many code now does a lot of work. It was originally factored into two phases

• acquire phase
• release phase

This effectively replicates the 2PL of enqueue that occurs. However, now in the acquire phase there is a lot of work, and that both complicates the readability, and potentially makes the time taken in the 2PL longer reducing potential throughput.

I propose we split the schedule_many into four phases

• prepare phase - create all the chains that should be added to the DAG, and effectively all calculation that can be done before the first exchange
• acquire phase - Exchange in the set of segments, and track any segments that had no predecessor
• release phase - Mark slots as completed to enable subsequent work to enqueue.
• process phase - Any segments that had no predecessor can be resolved in this phase.

I believe this factoring will help with both readability and performance as it moves work before or after the critical acquire/release phases reducing the time spent blocking other scheduler threads.

I believe this factoring would make it easier to address missing features interaction between the two PRs mentioned above.

@vishalgupta97 @marioskogias as you have both recently touched/reviewed this code. Do you have any thoughts on if this refactoring makes sense to you?

[mjp41]

After discussing with @marioskogias, we should probably call the last phase, "resolve phase".

[vishalgupta97]

Yeah, the refactoring looks good. Small points:

• Optimisation opportunity: Maybe free the extra references on cown in the prepare phase (if any). Limited opportunity though as we can't know the exact ref count until after the exchange.
• Maybe cown's reference counting can be removed from schedule_many/release functions and move into separate functions. For reads (it can be done in add_rcount and del_rcount). Similarly there can be a wrapper around xchg (in schedule_many) / CAS (in release) to do the ref counting. This will reduce possible bug surface which occurs due to incorrect ref counting.
• acquiring read/write cowns across bodies(using + operator) is not implemented yet.