Because of the latency on the LOCKed CMPXCHG opcode in the concurrent stack I think the task list would probably outperform it until around 16+ entries. Which means as long as you have more GETters than SETters you could probably get away with a small fast implementation like the task list.

Sorry, there was an error in a comment.

I also forgot to explain what is this program testing... It is simulating the scenario in which a low priority thread makes to update qEnqu pointer but gets immediately preempted by higher priority threads. The higher priority threads will succeed in queuing their own data, but when all of them will try to dequeue an element they will continually fail because the low priority thread haven't set the element on the array yet so the value of the first element is still zero. Since the high priority threads are still consuming lots of CPU time, the lower priority thread takes a lot of time to execute "mov [eax], ecx" (it is below ".putElement:"). Once the lower priority thread makes into setting its queue slot the other threads are able to complete their work inmedatelly and the simulation finishes. It takes in average 5 seconds on my computer. By uncommenting "THREAD_PRIORITY_TIME_CRITICAL=THREAD_PRIORITY_LOWEST" the average time is reported to be "0 ms" instead of around "5200 ms".

What I was trying to prove with all this? Only that if threads of heterogeneous priorities exists in the process, the queue can be mistakenly reported as empty when it is not (supposing than a failed dequeue means "empty queue") and/or the program could stall for a while. And in the case of homogeneous priorities the problem of having a failed dequeue even though when there are several slots with data is still possible, but the problem should last considerably less time than in the simulated case.

I'm planning to port the pseudo-codes of the paper into fasm too, so we can study the pros and cons of the three versions and conduct some benchmarks (probably made by someone else ).

[edit]Something perhaps not so obvious till you download the attachment, I ported the code to 32-bit because I don't have a 64-bit Windows and 32-bit is better for the sake of testing since more people can see this working on their own computers[/edit]

I'm planning to port the pseudo-codes of the paper into fasm too, so we can study the pros and cons of the three versions and conduct some benchmarks (probably made by someone else ).

When using the OS provided synchronization features some actions can be taken, but in this case the OS should be smart enough to know what the program is doing. We humans know the program is wasting a lot of CPU time because it is waiting for a low priority thread to finish executing a single instruction, but from the OS perspective it can't know much further than "this process consumes a lot of time doing an unknown (but yet user requested) task".

@@:  pause
       cmp     [$],12345678
jne     @b    

Every few million clock cycles or so, couldn't it just check EIP and see if it's changed or not? That should only add like 20 cycles overhead at the most, every million cycles or so.

Then, if it is the same, take a little look at the code to see if it's a spinlock, and if it is, let other threads have priority until the data it's spinlocking on is changed, then give it back priority.

What is hard about this?

Azu wrote:

Every few million clock cycles or so, couldn't it just check EIP and see if it's changed or not? That should only add like 20 cycles overhead at the most, every million cycles or so.

Then, if it is the same, take a little look at the code to see if it's a spinlock, and if it is, let other threads have priority until the data it's spinlocking on is changed, then give it back priority.

What is hard about this?

1. There is no instruction to "check the EIP" of another thread.

Typically the thread has to be interrupted to retrieve its context information. That is way more than 20 cycles of overhead.

Orthogonal to all of this, is a question of sample rate. One would have to be sampling at Nyquist rate to accurately infer whether the EIP is changing or not. This would require one thread to run at double the frequency of another - which is impractical in how SMPs are designed.

2. How do you propose the OS "takes a look at the code", as well as then infer whether "the data it's spinlocking on is changed" ?