Single-threaded work packets

[qinsoon]

We should introduce a new type of work buckets (work queue) that only one thread can execute packets from it at the same time. If no worker is working on a work packet from a single threaded work bucket, we allow popping 1 work packet from the bucket. Otherwise, the bucket is (logically) considered as 'not active' and the scheduler will not pop work from it. To implement this, we would need a worker to inform the scheduler that a packet is done.

We will introduce single threaded work packets. This allows us to implement certain packets without the need and the cost for synchronization.

Types that implements Work (work packet type) need to specify if this type is single threaded. For single threaded work packet types, the scheduler will allow only 1 packet from each single threaded packet type being worked on simultaneously. The scheduler may maintain a map between single threaded packet types and a flag to indicate if there is an active packet for them. If the flag is false, a packet can be scheduled, and the flag will be set. Otherwise, the packets of the same type need to be skipped. Once a single threaded packet is done, the flag needs to be unset.

[steveblackburn]

This should be generalized to allow N single-threaded workpacket instances of the same type. The simple case (above) has N=1, however we can make N > 1 to match the number of GC threads. Work can then be statically partitioned among the N threads.

For example, if we had N GC threads, then we might make a work packet for tracing that had N single threaded queues. Work could be added to the queues according to addresses (eg by indexing based on some bits of the address) in such a way that each address or range of addresses could strictly and deterministically be in exactly one of the N queues. For example, if we were using side metadata mark bits, we could implement an invariant that ensured that all addresses that share a single byte of metadata (for example 8 words whose addresses map to a given metadata byte) are all deterministically enqueued in exactly one of the N single-threaded work packets. This creates an invariant that allows the workpacket to ignore races to set a metadata mark bit since all metadata mark bits are guaranteed to be dealt with by mutually exclusive threads.