Is blocking multi-threaded programming any easier?

Question

I only read a little about this topic, but it seems that the only advantage is to overcome conflicting problems, but this will not have any significant impact on the deadlock problem, since the code that is locked is so small and fundamental (fifos, lifos, hash), that there never was a problem with a dead end.

So, all about performance - is that right?

Answer 1

Free programming (as far as I can see) is always about performance, otherwise using a lock in most cases is much simpler and therefore preferable.

Please note that when programming without locking, you can end the trading deadlock for live-lock, which is much more difficult to diagnose, since no tools that I know about are designed for diagnostics (although I could be wrong there).

I would say just go down the lock path if you need to; those. you have a scenario in which you have a hard lock that impinges on your performance. (If it does not break, do not correct it).

Answer 2

A couple of problems.

Soon we will encounter desktop systems with 64, 128 and 256 cores. Paralism in this area is different from our current experience of 2, 4, 8 cores; algorithms that run successfully on such small systems will run slower on highly parallel systems due to competition.

In this sense, locking is important because it makes a significant contribution to scalability.

There are also very specific areas where locking is extremely convenient, such as the Windows kernel, where there are execution methods, where sleep of any type (for example, waiting) is prohibited, which is obviously very restrictive to data structures, but where lock-free provides a good solution.

In addition, failure-free structures often lack failure modes; they cannot actually fail when the locked data may, of course, not get its locks. No need to worry about crashes, simplifies the code.

I have written a library of lock-free data structures that I will release soon. I think that if a developer can master a well-established API, then he can simply use it - no matter if he is free or not, he does not need to worry about the complexity of the basic implementation - and that is the way to go.

Answer 3

It is also about scalability. To achieve increased productivity these days, you will have to simultaneously solve the problems you are working on so that you can scale them across multiple cores - the more, the more fun.

The traditional way to do this is to block data structures that require concurrent access, but the more threads you can run truly in parallel, the bigger this bottleneck will be.

So yes, it's about performance ...

Answer 4

For preventive threads, threads suspended during a lock can block threads that might otherwise move forward. Lock-free does not have this problem, because by Herlihy's definition, some other thread can always move forward.

For unmanaged threads, this is not a big deal, since even lock-based solutions are blocked by Herlihy's definition.

Answer 5

This applies to characteristics, but also about the ability to accept multi-threaded loads:

• locks provide exclusive access to part of the code : while a thread has a lock, other threads rotate (looping when trying to get a lock) or lock, sleeping until the lock is released (which usually happens if the spinning takes too long) ;

  Operations

• atomic provides exclusive access to a resource (usually a word-size variable or pointer) using non-interruptive internal CPU instructions.

As BLOCK blocks other threads, the program slows down. Since atomic operations are performed sequentially (one after the other), blocking does not occur.

(*) if the number of simultaneous processors trying to access the same resource does not create a bottleneck - but we do not have enough processor cores to make this a problem.

I worked on writing without waiting (without locking without waiting states). The keystore for the server I'm working on.

Libraries such as Tokyo Cabinet (even TC-FIXED, a simple array) rely on locks to maintain database integrity:

"while the flow of letters works with the database, other threads of reading and writing flows are blocked" (documentation of the Tokyo cabinet)

Test results without concurrency (single-threaded test):

SQLite time: 56.4 ms (a B-tree) TC time: 10.7 ms (a hash table) TC-FIXED time: 1.3 ms (an array) G-WAN KV time: 0.4 ms (something new which works, but I am not sure a name is needed) 

Using concurrency (multiple threads are written and read in the same database), only the G-WAN KV survived the same test, because (unlike others) it never blocks.

So, yes, this KV store simplifies development as they don’t need to worry about threading issues. To do so, but it was not trivial.

Answer 6

I believe that I saw an article that mathematically proved that any algorithm can be written in standby mode (which basically means that you can be sure that each thread is always moving towards its goal). This means that it can be applied to any large-scale application (after all, a program is just an algorithm with many and many parameters), and because wait free ensures that there is no dead / live lock in it (until it’s " t there are errors that do not allow him to be really free from waiting), he simplifies this side of the program.On the other hand, the mathematical proof is far from the fact that he himself implements the code itself (AFAIK, there is not even a completely blocked linked list that can work On a PC, I saw those that cover most parts, but they usually either cannot handle some common functions, or some functions require a structure lock).

On the side of the note, I also found another evidence that showed that any algorithm without blocking can actually be considered without waiting due to the laws of probability and various other factors.

Answer 7

• Scalability is a really important issue in efficient multi / manicore programming. The biggest limiting factor is actually the code section, which must be executed in sequential order (see Amdahl Law ). However, statements about locks are also very problematic.

• The non-locking algorithm solves the scalability problem, which has an obsolete lock. That way, I could say that locking is mainly for performance , without reducing the possibility of a deadlock.

• However, keep in mind that with the current x86 architecture, writing a general locking algorithm is not possible . This is due to the fact that we cannot atomically exchange arbitrary data size in the current x86 (as well as true for other architectures except Sun ROCK). Thus, current locked data structures are quite limited and very specialized for specific purposes.

• I think that existing locked data structures will no longer be used for a decade. I strongly expect that within a decade a common locking mechanism with hardware will be implemented (yes, this is transactional memory, TM). If any TM is implemented, although it cannot completely solve the blocking problems, many problems (including priority inversion and deadlock) will be fixed. However, implementing TM in hardware is still very difficult, and only the project was proposed in x86.

It is too long: 2 sentences.

A data structure without locking is not a panacea for locking-based multithreading programming (even if it is not. If you seriously need scalability and problems with a lock conflict, consider a data structure without locking.