Competitiveness: Concurrency

In this article, I would like to document everything that I know about what tools can be used to effectively use the computing resources of systems and / or development convenience.

And I hope this can be useful to someone, because someone may not know something, or, on the contrary, it will be useful to me if someone shows something else / points out flaws in my knowledge.

• Concurrency (part 1, current)
  
  
  • Threads: scheduling, sleep
  • Synchronization : Spinlock, semaphores , memory barriers
  • Atomicity: TAS, CAS
  
  
• Cooperativity (part 2)
  
  
  • Coroutines
  • Actors
  
  
• Asynchrony (part 3)
  
  • Event loop
    • select
  • Callbacks
  • Async monad
  • Promises (promises, promises)
  • async / await - promises + coroutines
  
  

Parallelism

Once the processors were single-core (until 2001) , and in the systems there was only one processor (until 1966) . And then the instructions began to be executed simultaneously in the framework of one system.

Streams

Threads are an abstraction of the operating system that allows you to execute certain pieces of code in parallel. Each thread has a “context”, which includes a piece of memory for the stack and a copy of the processor registers. Obviously, there can be more threads running in the system than we have processors and cores, so the operating system is committed to schedule it (scheduling, scheduling) the execution of processes, restoring the registers in the processor cores for some thread to work for some time , then saves back and lets the next one execute.

Planning should be good, so that each thread works for approximately the same time (but at the same time is small enough, i.e. we will not be satisfied if each thread will work for several seconds), as well as the planning itself takes as little time as possible. Here we, traditionally, come to the latency / throughput balance: if you let the threads work at very small intervals, the delays will be minimal, but the ratio of useful work to time for switching contexts will decrease, and as a result of useful work will be done less, and if too much - Delays will become noticeable, which may appear on the user interface / IO.

Immediately I would like to note a rather important thing, which we will refer to later. Streams can be immersed in sleep. We can ask the operating system to put the thread to sleep for a while. Then she can take this into account when planning, excluding this thread from the queue for obtaining processor time, which will give more resources to other threads, or reduce energy consumption. In addition, in theory, you can set priorities so that some threads work longer, or more often than others.

Synchronization

We got a lot of cores, but the memory as one was solid, it remained (although in the modern organization of memory one can break one’s leg, both physical and virtual, and pages go back and forth, something is cached somewhere, checked for errors, it is strange that all this still works in general).

And when we start changing the same memory from several threads, everything can go completely wrong as we wanted it. There may be "races" when, depending on the order in which the operations are performed, a different result awaits you, which can lead to data loss. And, even worse - the data can be completely corrupted in some cases. For example, if we write a certain value to an unaligned memory address, we need to write it in two memory cells, and it may happen that one stream writes to one cell and the other to the other. And if you wrote down a pointer, or an array index, then most likely you will receive a program crash after some time when you try to access someone else's memory.

To avoid this, you need to use synchronization primitives in order to get guarantees that some blocks of code will be executed in strict order with respect to some other blocks of code.

Spinlock

The simplest primitive: we have a boolean variable, if true means blocking by someone else, false is free. And two methods: Lock , Unlock . Unlock sets the value to false . Lock in the loop does either TAS or CAS (more on that later) in order to atomically change false to true , and try until it succeeds.

Having such a thing, we can make blocks of code that will be executed exclusively (i.e. while one is executed, the other cannot start). At the beginning of the block, it executes the Lock method , at the end of Unlock . It is important that he does not try to make Lock a second time, otherwise there will be no one to unlock and get deadlock .

Hanging buns is possible. For example, saving the identifier of the thread who captured the lock so that no one except the captured thread could make Unlock , and if we did Lock the second time, it would not loop, such an implementation is called a “mutex” . And if instead of boolean we have an unsigned number, and Lock waits for a number greater than zero, decreasing it by one, we get a “semaphore” that allows some given number of blocks to work simultaneously, but no more.

Since locking works in an infinite loop, it simply “burns” resources without doing anything useful. There are implementations that, when unsuccessful, tell the planner, "I am everything, pass the rest of my time to other threads . " Or, for example, there are “adaptive mutexes” that, when trying to get a lock that is held by the thread that is currently executing, uses spinlock, and if it does not, it passes execution to other threads. This is logical, because if the thread that can free the resource is working now, then we have a chance that it is about to free. And if it is not executed, it makes sense to wait a little longer and transfer the execution to another thread, perhaps even to the one we are waiting for.

If possible, you should avoid using spinlocks, they can be used only if the blocks of code that they protect are executed incredibly quickly, so that the chances of collisions are extremely small. Otherwise, we can spend quite a large amount of resources simply on heating the room.

The best alternative to blocking is to put the thread to sleep, so that the scheduler excludes it from the candidates for processor time, and then request from the other thread to wake the first thread back so that it processes new data that is already in place. But this is true only for very long expectations, but if the release rates of the locks are commensurate with one "beat" of the thread execution, it is more efficient to use spinlocks.

Memory barrier

In pursuit of speed, processor architects have created a lot of dark magic that tries to predict the future and can rearrange processor instructions in places if they are independent of each other. If each processor works only with its own memory, you will never notice that the instructions a = 5 and b = 8 were executed in a different order, not the way you wrote in the code.

But with parallel execution, this can lead to interesting cases. Wikipedia example:

// Processor #1:
while (f == 0);
// Memory fence required here
print(x);

// Processor #2:
x = 42;
// Memory fence required here
f = 1;

It would seem that what could go wrong here? The cycle will end when f is assigned a unit, at the time of which the variable x seems to be equal to 42 . But no, the processor can arbitrarily swap such instructions, and as a result, it can first be executed f = 1, and then x = 42not 42 , but something else can be displayed . And even more than that. If everything is normal with the writing order, the reading order can be changed, where the value x is read before we enter the loop.

To counteract this, memory barriers are used, special instructions that prevent instructions from moving through them. On a habr there is an excellent translation on this subject.

Atomicity

Since some operations with memory may be thread-safe (for example, add another number to a number and save it back), there are operations for atomic operations for which there are special processor instructions.

Most commonly used:

• Test-and-Set - writes the value, returns the previous one.
• Compare-and-Swap - writes the value only if the current value of the variable matches the expected one, returns the success of the recording.

Returning to our spinlock, the operation of obtaining a lock can be implemented as using TAS :

void lock() {
  // Мы будем записывать 1 до тех пор, пока между нашими выполнениям кто-то не запишет в неё 0
  while (test_and_set(&isLocked, 1) == 0);
}

So with CAS :

void lock() {
  // Пытаемся записать 1, ожидая 0
  while (!compare_and_swap(&isLocked, 0, 1))
}

... as I said, I would like to document everything, but ... it turned out quite a lot, so I will divide this case into three articles. Stay tuned.

UPD: The second part .