Imagine you wrote a new Web server that didn't support concurrency and couldn't do multiple things at the same time. Consequently, each new Web request would run serially. Sure, it would be simple to implement, but a single, long-running request could block the entire Web server! A request involving a query against the database that takes two minutes to complete would mean that no one else could access the Web server during those two minutes.
When thinking of concurrency, it's useful to distinguish between I/O throughput and CPU throughput. Does the problem involve lots of concurrent requests, or does it involve lots of data to crunch? This distinction is important because some techniques work better for one than the other. However, sometimes this distinction is blurred. Threads try to address both of these problems. In this article, I focus on I/O throughput.
Approaches to Multitasking
Let's start with some basics. The kernel clearly needs to support concurrency in order to run multiple applications at the same time. Operating systems use time slicing to share one CPU among many programs. If each program gets a small slice of the CPU's time, the question is, how do they take turns?
In non-preemptive schedulers, each program must explicitly "yield" the CPU to the other programs. This is called "cooperative multitasking" because the programs have to cooperate with each other by yielding the CPU. Macintosh OS 9 used a non-preemptive scheduler. These days, most GUI libraries and JavaScript use this same technique to share the CPU among many "things" competing for it. One downside to this technique is that if one program gets wedged in an infinite loop, the whole system goes down. On the other hand, because the programs yield to each other in predictable ways, it's easier to reason about cooperative multitasking; that is, it's more deterministic.
Kernels that use preemptive schedulers simply interrupt (I'm mostly using the English meaning of the term "interrupt", not the computer science meaning) when it's time for one program to be replaced by another. The interruption is caused by a hardware timer. By and large, the program can be completely unaware that it was even interrupted. UNIX and Windows NT use this technique. Hence, so do Linux, OS X, and Windows XP. Unlike non-preemptive schedulers, preemptive schedulers can interrupt a program even if it's wedged in an infinite loop. Consequently, a wedged program can't bring down the whole system.
Locking
Imagine some ancient banking software with multiple programs trying to write data to a single file. Example 1 is what I like to call the canonical "race" condition.
Process A sees that John's balance is $25 Process B sees that John's balance is $25 Process A deducts $25 and sets balance to $0 Process B deducts $25 and sets balance to $0 John gets a free $25 .... which he promptly loses on a horse race ;)
Clearly, when you have multiple programs accessing the same data, some additional cooperation is required. This is done via locking. In the pre-Python 2.5 days, using a lock required a try/finally statement to acquire and release the lock. These days, Python 2.5's with syntax makes this task really convenient; see Example 2.
with lock:
if balance > amt:
deduct(amt)
else:
raise ValueError('Insufficient funds')
By the way, it's easy to wrap this technique in a function decorator called synchronized to write Java-esque code; see Example 3.
@synchronized
def update_account(...):
...
Once you introduce locks to protect shared data, the question becomes: What should you protect, and how many locks do you need? If you use a single lock that wraps everything, then no concurrency is possible. Clearly, it can get better than that.
Using a single lock to protect all the critical sections is called "coarse-grained locking." FreeBSD 4 and Python both use this technique. In FreeBSD 4, the lock was called "giant", and in Python it's called the "global interpreter lock" (the "GIL").
Using multiple locks that each protect a specific resource during critical sections is called "fine-grained locking." FreeBSD 5 and up use fine-grained locking. BeOS was famous for how fine-grained its locking was. Thanks to its careful fine-grained locking, BeOS was well suited to high concurrency. It was far better than other operating systems of its time at doing things such as playing multiple videos concurrently. While fine-grained locking has some real benefits, it's harder to implement. Furthermore, it can be more expensive to constantly acquire and release a bunch of small locks than to simply acquire and release a single large lock.
By the way, there has been research done on "lockless data structures". Usually, if you wish to update a hash atomically, you need to use a lock or else a race condition can lead to malformed data. However, there exists a hash implementation that can be updated atomically without the use of a lock. It's possible that these techniques may be increasingly important in the future.
