Synchronization and Concurrency: 1. Story Time

Annabeth wants to meet Percy in camp ¹. But there’s a curfew imposed by Diosnyus, the camp director. Odds are, if both of them go out unplanned, they’ll be caught. What should they do?

If you want to drop the cool analogy, here’s the computer sciency reformulation: There are two processes A and B. A waits for you to save your work and writes it to the hard disk. B shuts down your system. If you don’t want to lose your work, what should processes A and B do?

In both cases, one should communicate to the other. Annabeth can go out, make sure things are clear, then call Percy to their spot.

This could be their schedule. The events make sure field’s clear, wait for Annabeth’s call, meet Annabeth must happen in this particular order. This is serialization – enforcing ordering on events.

The events attempt to murder Percy and capture the flag (Percy) are concurrent – we don’t know for sure if it was capture the flag or dinner that ticked Annabeth off. Concurrent does not necessarily mean things are happening in parallel at the same time.

In the second case, process B should shut down the system after process A is done saving things. So, B waits for A to tell it it’s done. This is serialization by message passing. B has a mailbox or a pipe to which A writes a message saying it’s done.

In general, concurrent events are non-deterministic. We don’t know which event will happen first before the program executes. For example,

The final output can be 12 or 22 or 21 depending on which executed last – if A1 < B1 and A2 < B1, the first printed value will be 1. This relative ordering can not be determined during compile time. Obviously, we can extract something useful out of this. I can tell you for sure that it’ll never print 11. As a quick mental exercise, determine the sequence for the other possible outputs.

Cool, so I can tell you it won’t print 11. Will this magic 11 get me placed or get me grades?

Surprisingly, yes. The list might be longer with fancier functions, but the crux remains the same.

Okay, so is this really used somewhere or just one of those things invented to annoy people in exams?

The ability to analyze different outcomes and figure out what can never happen is quite important if you’re a lazy programmer. A little effort in reasoning out will go a long way in letting you get away with simple synchronization/multithreaded constructs in production code². As opposed to 100+ lines of code or the hours you’ll put in trying to debug a more complicated solution. As an added bonus, managers love simple code and years down the line, you won’t get bad karma for torturing the other developer who’s going through your code.

Back to the land of curioisty, we know that things go haywire (and consequently more fun) when there are concurrent updates. The solution to that can be forcing things to happen in the order we want it to. But that effectively reduces the extent of parallelism of our code. And sending messages between threads and managing all that sounds like a drag.

For example, let’s say you have 10 threads counting the number of words in 10 pieces of a huge document. Each thread does something along the lines of

for word in document_piece:
	word_count += 1

The innocuous word_count += 1 has two steps – computing word_count + 1 and assigning the result to word_count. If these two steps are interleaved between threads, we’ll no longer get the right value. Luckily for us, in most modern hardware, we have atomic operations which do exactly this – the computation and assignment are done together and other instructions can not be interleaved between these two. This is for incrementing an integer variable by 1.

So, what happens when I want to do some cooler stuff? Well, there’s no easy way out of this. You’ve to resort to the idea of mutual exclusion – for a period of time that I specify, no other thread is allowed to work with the things I’m working with. In the simple words of Daffy Duck, MINE.