💾 Archived View for yujiri.xyz › software › guide › concurrency.gmi captured on 2023-06-16 at 16:56:26. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Learn programming for good instead of profit

How concurrency works

Concurrency or parallelism means doing multiple things at once. Normally, programs execute their whole code sequentially, only ever one thing at a time. There are a few different ways you can make it run concurrently.

Ways to implement concurrency

Multiple processes

Let's get this out of the way because it sort of only halfway counts but it is the most basic. Just spawn multiple processes. Like a command shell does when you pipe (`ls | wc` spawns `ls` and `wc` as separate processes, so they run at the same time), you can spawn new processes to do the things you want to be done at the same time. Disadvantages:

Separate processes don't, by default, share any memory or anything. So for every single piece of information you want to share (such as the app's settings, or the account the user is logged into), you have to arrange for it and any updates to it to be passed between the "parent" process and the "child" process (the one getting spawned) - maybe with pipes. That processes don't share memory also means that this approach to concurrency will use much more memory than any of the others.

Every time a processor switches from running one process to another, it has to do a "context switch", which takes time - not individually noticeable to humans, of course, but if the computer is doing this constantly, the overhead can be significant.

When you spawn a process, you only tell the kernel what executable file it should run and what its command-line arguments and environment should be, and it always starts at the beginning of that executable. You can't say "start this program and jump right to this part of the code". You would have to either split your program into many different executable files, one for each place you might want to spawn a new process at; or use the command-line arguments or environment variables to signal your process what to do, and add convoluted code in your `main` function to interpret these signals and jump to the right part of the program. Nasty.

Multiple threads

This is pretty similar to multiple processes but a lot better. A thread is like a part of a process that can run at the same time as another part. Compared with separate processes:

Threads, by default, share most of their memory with each other (specifically the text segment (instructions), heap, and data segment, but not stack), so you don't have to worry about passing every little piece of information between different threads. This also means they are much more memory-efficient.

The processor still has to do a context switch to switch between threads, but it's a less expensive kind of context switch, because there's less context it has to switch out.

When you spawn a new thread, you control where in your code it starts executing, so you don't have to arrange some kludgy out-of-band signal to tell it which function you want to run concurrently.

Green threads

"Green" threads are similar to "real", OS-managed threads, but they're managed by the process itself instead of by the operating system.

To use green threads, a program sets up a small number of OS threads that actually run things, and any number of green threads which represent all the things it wants to do concurrently, and then it shares the OS threads across the green threads so every green thread gets a turn to run, just like how the kernel shares a few CPU cores across all the running processes (or OS threads).

The point of doing this is that switching between green threads is cheaper than switching between OS threads, since it doesn't involve the kernel.

And before you ask: you don't have to implement this scheduling complexity yourself to use green threads. Usually if you're using green threads it's because you're using a language or library that provides them for you, such as the Go language. In Go, you just use the `go` keyword to spawn a new green thread. The compiler will automatically insert the code for managing these green threads into every executable.

Asynchronous programming and event loops

Asynchronous programming is a style of programming meant for when all the things you want to do concurrently are *IO-bound* rather than *CPU-bound* (that is, you want to listen for incoming data on two sockets at the same time and respond to whichever comes in first, but don't need to do two math problems at the same time). Asynchronous programming doesn't necessarily rely on threads at all.

Generally, asynchronous programming involves an event loop, which is a data structure that keeps track of all the tasks that are running concurrently and runs whichever of them is not stuck waiting on IO.

Asynchronous programming is a natural way to write certain kinds of applications, like network servers or GUI programs.

Synchronization

Threads generally introduce the need for synchronization. I touched on this in the chapter on inter-process communication, but now I'll explain it in more detail.

Writing to memory is a volatile thing. If you have one thread trying to read from a memory address, and another thread trying to write to it at the same time, what happens? Does the reader get the old value, the new value, or some corrupted mixture of the two? Does the write succeed at all? Does the program crash? There is no reliable answer. This situation is called a "data race", and the actual outcome can depend on the hardware and such. So, for software purposes, it's called "undefined behavior", because it's not defined what will happen in this situation.

So, when you have two threads or two processes sharing memory, you generally have to take steps to ensure that access is synchronized: that even if the threads are running at the same time, they won't both touch the same memory location at the same time. Specifically:

Multiple threads *reading* from the same memory location is okay, you don't need to synchronize them.

Multiple threads *writing* to the same memory location is not okay, you need to synchronize them.

One thread writing while another thread is reading from the same memory location is also not okay, you need to synchronize them.

I'll talk about two programming techniques used to accomplish this synchronization:

Atomic instructions

Processors support instructions for *atomically* reading or writing memory, which guarantees the read or write happens all at once and not at the same time as anything else, and no bizarre corrupted value appears. These aren't the default ways of reading and writing memory because they have more overhead and aren't needed for most cases (anything where only one thread is accessing it at a time).

Different programming languages have various ways of offering you this functionality. For example, in Zig there is a special thing called `@atomicStore` (store meaning write) which atomically stores a value in a variable, unlike the normal `variable = value` syntax which is not atomic.

Atomic reads/writes have a limitation though: they only work with primitive operations like reading or writing a number to memory. If you need to synchronize something more complex, you need to use locks.

Locks

Locks are a feature provided by operating system kernels meant for ensuring that only one thread is accessing something at the same time. Two threads can share a lock, and before each one tries to access the shared memory, they request to acquire the lock, and:

If the lock is available (no other thread is holding it), the kernel will give it out and mark it as held.

If the lock is already held, the kernel will suspend (pause) the thread asking for it until it's released.

It's important for a thread that uses the lock to release it when it's done, otherwise no other thread will be able to access the memory afterward.

Locks are very difficult to work with in most languages because there's so many ways you can go wrong with them:

You can accidentally access the shared memory without acquiring a lock, causing a data race.

You can forget to release the lock when you're done, which will prevent any thread from ever acquiring the lock again because the kernel thinks it's still held, causing a deadlock (the program freezes as all of its threads are stuck waiting for the lock).

In a complex situation with multiple locks involved, you can have one thread acquire lock A and then try to acquire lock B (in order to do something that involves two different pieces of shared memory), while another thread already acquired lock B and is now trying to acquire lock A. Neither thread can ever get the lock it needs because the other thread will never release it, because it's also waiting on a lock. This is another way to cause a deadlock.

Deadlocks are hard to debug because instead of any error message, the program just freezes, leaving you to search your entire source code for the problem.

Data races are even nastier because they're non-deterministic, so they might for example happen on a user's machine while the program works fine on the developer's machine, or they might happen on the developer's machine but only sporadically, with no reliable way to reproduce the bug, and thus even less information about where the problem might be.

Rust is the only language where locks are actually easy to work with, because it exposes their functionality in such a way that you *can't* access lock-protected data without acquiring the lock, and also can't forget to release the lock when you're done.

There are also multiple kinds of locking: there's exclusive locking, which excludes all other threads from having the lock at the same time, and there's shared locking, which allow other threads to have it at the same time as long as none of them need to have it exclusively. If a thread is only going to be reading from the shared memory, it can just acquire a shared lock so it doesn't needlessly block other readers.

Exclusive locks are also called mutexes (MUTual EXclusion).

contact

subscribe via RSS