CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 6 of 7 · 4 min read

Choosing

Choosing a tool

Think of it this way. A craftsperson picks a tool by the job: a hammer for a nail and a screwdriver for a screw. The tools of Level 4 likewise fit different jobs. The table summarises the level in the order of the questions to ask.

The situation The tool Page
One shared number that must be exact, updated often Atomic add 2
A short critical section; threads at most the number of processors; holder never preempted Spinlock (mainly inside kernels) 2
Any other critical section Mutex 3
Wait until a condition on shared data is true Condition variable, in a while loop 4
Limit the number of threads in a region; count resources; order two events Semaphore 5
A queue between producers and consumers Bounded buffer (semaphores or condition variables) 6
Data read often and written rarely Read-write lock (measure first) 7
Several locks needed at once One global lock order 7
A counter that does not need to be exact at every moment Sloppy counter 9
A big shared table Lock striping 9
Not sure it is right ThreadSanitizer, stress tests, injected delays 8

In plain words: A last rule joins them: the best synchronisation is none. Give each thread its own data (page 4 of Level 2), combine results at the end, and use a shared structure only where sharing is unavoidable. The sloppy counter is that rule in action: most of the time, threads do not share.

The level also built the tools that Level 5 will need. A deadlock showed up twice (pages 6 and 7), and Level 5 gives it a full treatment: the four conditions, how to prevent, avoid and detect it, and how an operating system can recover.

Synchronisation primitive

A synchronisation primitive is a basic building block for coordinating threads, such as an atomic instruction, a lock, a semaphore or a condition variable, from which higher-level structures like queues and tables are made.

Example: the mutex is built from an atomic instruction and a futex, and the bounded buffer is built from a mutex and two condition variables.

Common mistake

Optimising locking before measuring. A coarse lock is often fast enough, and fine-grained locking adds memory, complexity and deadlock risk. Add locks only where a profile shows threads waiting.

Interview angle

Answer in your head first, then open it.

How would you make a shared counter scale?

Give each thread a local count and add to the global one only now and then (a sloppy counter), or use atomics.

Why can adding threads make a program slower?

Contention on a lock, cache-line bouncing and sleeping and waking cost more than the work.

How do you make a hash table concurrent?

One lock, then a lock per bucket (lock striping); take all locks in order for whole-table operations.

What do you give up with a sloppy counter?

Exactness of the global value at any moment, by at most threads times threshold.

What is the first thing to try when a threaded program is slow?

Measure where threads wait, and reduce sharing.

Check yourself: 1. Which tool fits "limit to 10 concurrent connections"? 2. Which tool fits a statistics counter that is read once a minute? 3. What is the first rule of synchronisation design?

Words you will meet

Word Meaning
Scalability Work done grows as threads are added
Sloppy counter Local counts added to a global one at a threshold
Threshold The local count at which it moves to the global one
Hash table Keys placed in buckets by a hash function
Chaining Each bucket holds a list of its keys
Concurrent data structure Safe for several threads at once
Lock striping One lock for each part of a structure
Synchronisation primitive A basic building block for coordination

Quick notes

  • Scalability is the ability of a program or data structure to do more work per unit time as the number of threads (up to the number of processors) increases, with.
  • A sloppy counter (approximate counter) is a counter in which each thread increments a private count without locking and adds it to a shared global count, under a lock, only.
  • A concurrent data structure is a data structure whose operations may be called by several threads at the same time and still leave it in a consistent state, usually by means of locks or atomic operations inside the operations.
  • Lock striping is a technique in which a shared structure is split into parts, each guarded by its own lock, so that operations on different parts run in parallel and only operations on the same part exclude each other.
  • A synchronisation primitive is a basic building block for coordinating threads, such as an atomic instruction, a lock, a semaphore or a condition variable, from which higher-level structures like queues and tables are made.