[ruby-core:30170] [Feature #3176] Thread#priority= should actually do something

Issue #3176 has been updated by caleb clausen.


Here's a patch which makes thread priorities work. This was made against the current trunk (1.9.3dev as of 11-may-2010).

Please consider this a preview to show where I want to go with this rather than a final product. Before this can be accepted, the following things should happen:

1) More testing. this passes make test and make test-all, but I haven't tried rubyspecs yet. (what else?)

2) Testing on more platforms. This appears to work on x86-linux, but multicore and 64bit machines should be tested, as well as other posix systems, and PARTICULARLY windows, which is rather more likely to have some kind of problem.

3) Most tests, for both thread priorities, and ffs implementation that I had to add to support platforms where ffs isn't present (windows).

4) Benchmarking. Yusuke was concerned about performance of this feature. I think speed will only be a tiny bit less with this patch, but that has yet to be proven.

5) Review for style, appropriateness, correctness, etc.

6) Patch should be split up into several chunks, for easier digestion. 


Some notes on the implementation:

I've added a priority queue using the multi-level queue data structure, with bitmap scanned by ffs to quickly find the levels actually in use on dequeue. This data structure features O(1) insertion and deletion times, but has a moderately high fixed memory cost for even an empty queue versus tree-based priority queues. (33 words vs 1 word. BFD, I say.) And it only allows 32 different priority levels. 
See http://en.wikipedia.org/wiki/Multilevel_queue

Ffs is a bit-scanning routine present on most (all?) unix systems. On most processors, there is an instruction to do this, making this operation nice and fast. Windows does not have ffs, so I wrote a (rather slower) version of it in c as a backup. (The x86 does have this instruction (it's called BSF, I think), but windows just doesn't make a nice programmer interface to it like unix does. If anyone wants to help me write the appropriate inline assembler to make this fast on windows too, I'd appreciate it.) I've made an ffs method available on Fixnum and Bignum at the ruby level as well.
See http://linux.die.net/man/3/ffs

Ruby traditionally has had fair thread priorities, meaning low priority threads still get a little time even when higher priority threads are trying to hog the processor. I've tried (I think successfully) to preserve this fairness by occasionally and temporarily boosting the priority of low-priority threads. But I'm not entirely certain that part of the algorithm works perfectly. The ratios of time given to low vs high priority threads in 1.8 are not preserved. A lowest priority thread may have to wait several seconds before it will get access to the cpu, if a highest priority thread is also running. (Actually, there's no upper limit on how long it will have to wait, given enough other threads contending for the cpu. Not sure it's possible to fix that.)


I'm going to take a break from this for a few days, then get back and finish it off after that.

----------------------------------------
http://redmine.ruby-lang.org/issues/show/3176

----------------------------------------
http://redmine.ruby-lang.org