2013: Advent Computing: Atomics and locks

by on December 14, 2013

When writing a simple program, you will normally only have a single “thread of execution”. That means that you’ll write a series of instructions for the computer, and the computer will follow them one-after-another. There might be jumps and loops (“do this five times” or “if this is the case, start doing some different set of instructions”), but there is only one thing going on at any one time.

As mentioned yesterday, though, that’s often not the way to get the fastest program. By having multiple threads of execution, you can have one thread doing some calculations while another is “blocked” waiting for something slow to happen. With “multi-core” computers, you can even have multiple threads doing different calculations and instructions at the same time.

Sadly writing programs that do this is quite hard. In general, each thread of a program won’t know what the other threads are doing, so we need ways to allow each thread to check it’s not going to prevent some other thread doing what it’s supposed to, just as our train network needs ways to ensure two trains don’t try and travel on the same section of track.

A specific example may help: my program has one thread writing a list of names to disk. Another thread is adding and removing names from that list depending on some alogrithm I wrote. If the second thread updates a name that’s in the middle of being written by the first thread, what actually gets written to disk is likely to be half of each name and entirely useless.

The basic method we have of dealing with this is of “locks”, although the name is a bit of a misnomer. Essentially, you assign a lock to everything that multiple threads might want to access, and if a thread wants to access that thing, it must hold the lock. If another thread holds the lock, the first can decide to do something else, or it can sit and wait for the lock to become available.

Of course, you need to make sure you don’t hit exactly the same problem with grabbing the lock. Consider a simple lock: if a bit of memory is “0”, the lock is available, if it’s “1” it’s in use. If a thread wants the lock, it’ll check the memory is “0”, and if it is it’ll write a “1” and then it holds the lock, when it’s finished it’ll write “0” to that bit of memory again. But if two threads both check the memory and see it’s “0” before either of them write a “1”, they’ll both think the lock is free, both write a “1” to that bit of memory, and both think they have the lock. That’s exactly the sort of problem we’re trying to avoid!

There are a bunch of possible solutions. One would be for the instruction for taking the lock to be “add one to whatever’s there”, then to check the lock memory again. If it’s “2”, the thread knows something else has also managed to pick up the lock and it should release it again. Another is to use “atomic operations”. These have nothing to do with nuclear structures, but rather refer to the classical meaning of “atomic”, that is “indivisible”. An atomic operation means the computer will do whatever it needs to do (and different processors have different tricks for this) to make sure that nothing can happen between the steps of “read 0” and “write 1”; specifically, no other thread can also read that memory between this thread reading the 0 and marking the thread as taken by writing the 1.

Leave a Reply