Producer processes cause process starvation when only sending on async_chans

[samgiles]

Because multi-tasking is achieved through the co-operative, synchronising, nature of channel communication on a single thread rather than using N operating system threads, to ensure progress, when a producer process begins and its only operation is sending on a async_chan in an infinite loop, the system locks, forever sending on the unbounded buffer:

let generate = fn(channel) {
    let i = 0
    while true {
        channel <- i
        i = i + 1
    }
}

let x = async_chan()
async generate(x)
print <: x

Potential remedies:

1. Pre-empt tasks if we can statically determine that only send operations are performed and at runtime an async_chan is used, or, if no channel operation occur and a hot loop is detected.
   • Pros
     • In the case where no channel operations occur, instead an infinite loop is executing in an async task, pre-emption would ensure other tasks get time to run without the use of 'task migration', the concept of stealing tasks from a thread's run queue to run on a separate thread (relies on multi-threading which is not supported in the RPython version for reasons). This method is the only way of ensuring tasks are not starved in this case without multi-threading.
   • Cons
     • Unbounded, unbuffered channels can be created and the programmer need not think about task starvation. This could lead to memory issues if the number of writes per unit of time is greater than the number of reads.
     • Added runtime complexity, pre-emption would add extra guards into generated JIT traces and the possibility of controlling these could be troublesome (let alone frequent de-optimisation if consistently pre-empting while in a hot loop). This would be something to test.
2. Insist that async_chans are always bounded and when the buffer is full it behaves like a synchronous channel where a sender must wait for space and consequently a reader.
   • Pros
     • The number of items in the channel is guaranteed to be bounded, therefore memory leaks due to the sender sending more items per unit time than the reader can read are eliminated.
     • No added runtime complexity for async_chans.
   • Cons
     • Does not solve the case where an async task performs no channel operations but is in an infinite loop.

Neither of these approaches entirely solve the problem on their own. However some mixture of these approaches is needed.

An unbounded channel doesn't seem to offer any benefits beyond simplicity, therefore a bounded async channel should be supported. However bounded buffered channels do not solve the problem of a non-communicating processes starving other processes and in the single threaded case pre-emption strategies should be investigated.

Action: Issue #3 (Implement bounded, buffered channels), Issue #4 (Investigate pre-emption strategies)