Re. your second paragraph, it is again not inherent to the algorithm, but it does greatly simplify things. In particular, pretty much all tracing algorithms require at least some kind of stop the world event, though some can make this event very limited in duration.

It is much much easier (and results in greater throughput) to stop the world if only one thread is running at a time, because you just do your collection when that one thread triggers a heap mutation.

If you have multiple threads running at once you need to coordinate when you stop the world, which means waiting for the threads to all wind up in a state where they can be stopped (which gets a lot harder if, say, one of the threads never allocates because it's in a tight loop). If it takes too long to do this coordination, your heap might explode on you.

Again, what I'm saying is that a GIL is not an inherent feature of either garbage collection mechanism. This is really pretty obvious when you consider that there's an abundance of implementations of all combinations of (RC, tracing)(GIL, no GIL). Python and Ruby's main implementations both chose a GIL for simplicity's sake (and an at the time safe assumption that single-core performance was more important than multi-core), but most C++ refcounting code uses interlocked counters and the JVM has obviously never used a GIL.