Last Tech Tuesday, I introduced the problem of concurrency: multiple programs executing at the same time. I used an example of a naive program for updating a vote count that could lose votes if multiple instances run concurrently. So how do we deal with this problem? There are many different approaches that people have taken over time and I will only try to cover some of them. Since I am still traveling and keeping my posts short, today I will only cover the idea of atomic actions.
An atomic action is guaranteed to be completed in one go as if it were instantaneous. How does that help with concurrency? Well imagine that the database we are using provides for an atomic increment and decrement operation. Then we could rewrite our code as:
if upvote:
atomic_increment(votecount)
else:
atomic_decrement(votecount)
Now we don’t care how many copies of this program are running concurrently. We are guaranteed that every change in vote count is properly recorded in the database.
Do atomic actions solve all our problems with concurrency? No, as the following example illustrates. Consider a naive program for dispensing money from an ATM machine
if (get_balance() > amount):
atomic_decrement_balance(amount)
dispense(amount)
What is the problem? If you cloned your ATM card (don’t do this) and lined up a concurrent withdrawal at many different ATM machines you might be able to withdraw much more money than is in the account! Why? Because the balance check is performed separately from the atomic decrement of the balance.
So if many of these programs run concurrently because we hit the withdraw button on thousands of ATMs at the same time, they might all show the account as containing the balance and hence all dispense money after which the account would be massively overdrawn – but as a crook we would have our money and run.
How could we fix this problem? Well, one answer is to have a larger atomic action. If we had
if (atomic_decrement_balance_if_amount_available(amount)):
dispense(amount)
there would be no concurrency problem that someone could exploit. That solution of course has a problem: for any but the easiest cases (like this one), we would need the operating system to provide us with ever more complicated atomic actions.
There is also a question that should be nagging you right now? How can the operating system provide atomic actions in the first place? In other words, using atomic actions to solve the concurrency problem is really just relying on someone else having figured it out for us. Which is perfectly fine from the perspective of the application layer program, but does beg the all important question: how does the operating system solve the concurrency problem? This seems like a case of “it’s turtles all the way down.” Next week we’ll look at some of those turtles …
