I've attached a test "fair.py" that gives an example of the fair CPU scheduling issue.  In this test, there are two threads, one of which has fast-running ticks, one of which has slow-running ticks.  

Here is their sequential performance (OS-X, Python 2.6):

slow: 5.71
fast: 0.32

Here is their threaded performance (OS-X, Python 2.6.4):

slow : 5.99
fast : 6.04    (Notice : Huge jump in execution, unfair CPU)

Here is their threaded performance using the Py3K New GIL:

slow : 5.96
fast : 0.67    (Notice : Fair CPU use--time only doubled)

Using Linux with semaphores gives no benefit here.  The fast code is stalled in the same way.   For example: here are my Linux results (Ubuntu 8.10, Python-2.6.4, dual-core, using semaphores):

Sequential:
    slow : 6.24
    fast : 0.59
Threaded:
    slow : 6.40
    fast : 6.69    (even slower than the slow code!)