As a followup, since I'm not sure anyone actually here actually tried a fair GIL on Linux, I incorporated your suggested fairness patch to the condition-variable version of the GIL (using this pseudocode you wrote as a guide):

with gil.cond:
  if gil.n_waiting or gil.locked:
    gil.n_waiting += 1
    while True:
      gil.cond.wait() #always wait at least once
      if not gil.locked:
        break
    gil.n_waiting -= 1
  gil.locked = True

I did some tests on this and it does appear to exhibit fairness. Here are the results of running the 'fair.py' test with a fair GIL on my Linux system:

[ Fair GIL Linux ]
Sequential execution
slow: 6.246764 (0 left)
fast: 0.465102 (0 left)
Threaded execution
slow: 7.534725 (0 left)
fast: 7.674448 (0 left)
Treaded, balanced execution:
fast A: 10.415756 (0 left)
fast B: 10.456502 (0 left)
fast C: 10.520457 (0 left)
Treaded, balanced execution, with quickstop:
fast B: 8.423304 (0 left)
fast A: 8.409794 (16016 left)
fast C: 8.381977 (9162 left)
beazley@ubuntu:~/Desktop/Python-2.6.4$ 

If I switch back to the unfair GIL, this is the result:

[ Unfair GIL, original implementation, Linux]
Sequential execution
slow: 6.164739 (0 left)
fast: 0.422626 (0 left)
Threaded execution
slow: 6.570084 (0 left)
fast: 6.690927 (0 left)
Treaded, balanced execution:
fast A: 1.994143 (0 left)
fast C: 2.014925 (0 left)
fast B: 2.073212 (0 left)
Treaded, balanced execution, with quickstop:
fast A: 1.614533 (0 left)
fast C: 1.607324 (377323 left)
fast B: 1.625987 (111451 left)

Probably the main thing to notice is the huge increase in performance over the fair GIL.  For instance, the balance execution test runs about 5 times faster.

Here are the two tests repeated with checkinterval = 1000.

[ Fair GIL, checkinterval = 1000]
Sequential execution
slow: 6.175320 (0 left)
fast: 0.424410 (0 left)
Threaded execution
slow: 6.505094 (0 left)
fast: 6.746649 (0 left)
Treaded, balanced execution:
fast A: 2.243123 (0 left)
fast B: 2.416043 (0 left)
fast C: 2.442475 (0 left)
Treaded, balanced execution, with quickstop:
fast A: 1.565914 (0 left)
fast C: 1.514024 (81254 left)
fast B: 1.531937 (63740 left)

[ Unfair GIL, checkinterval = 1000]

Sequential execution
slow: 6.258882 (0 left)
fast: 0.411590 (0 left)
Threaded execution
slow: 6.255027 (0 left)
fast: 0.409412 (0 left)
Treaded, balanced execution:
fast A: 1.291007 (0 left)
fast C: 1.135373 (0 left)
fast B: 1.437205 (0 left)
Treaded, balanced execution, with quickstop:
fast C: 1.331775 (0 left)
fast A: 1.418670 (54841 left)
fast B: 1.403853 (208732 left)

Here, the unfair GIL is still quite a bit faster on raw performance.  I tried kicking the check interval up to 10000 and the unfair GIL still won by a pretty significant margin on raw speed of completing the different tasks.

I've attached a copy of the thread_pthread.h file I modified for this test.  It's from Python-2.6.4.