Any problems with a lot of critical sections?

Question

I have a large array of structures, for example:

typedef struct { int a; int b; int c; etc... } data_type; data_type data[100000]; 

I have a bunch of separate threads, each of which wants to make changes to the elements in the data []. I need to make sure that none of the threads is trying to access one data item at a time. To be precise: one thread executing data [475] .a = 3; and another thread executing data [475] .b = 7; at the same time, it is not allowed, but one thread executes data [475] .a = 3; and the other thread executes the data [476] .a = 7; allowed. The program has a very high speed. My plan is to make a separate critical section for each data item as follows:

 typedef struct { CRITICAL_SECTION critsec; int a; int b; int c; etc... } data_type; 

In one case, I think that everything should work, and I should not have any real questions, but I did not have much experience in multi-threaded programming. I'm just a little embarrassed that I have so many critical sections. I wonder if their number of them can create any kind of inefficiency. I am also wondering if there could be some other multithreading technology faster? Should I just relax and continue Plan A?

Answer 1

With this set of objects, most of their critical sections will be unlocked, and there will be almost no debate. As you already know (other comments), critical sections do not require transition in kernel mode if they are not registered. This makes critical sections effective for this situation.

The only other consideration will be whether you want critical sections inside your objects or in another array. Link locality is a good reason to place critical sections within an object. When you enter the critical section, there will be a whole cache in memory (for example, 16 or 32 bytes). With a few additions, you can make sure that every object starts with a pin. As a result, the object will be (partially) in the cache as soon as its critical section is entered.

Answer 2

Your plan is worth a try, but I think you will find that Windows is not happy with creating many critical partitions. Each CS contains some kernel descriptors, and you use precious kernel space. I think, depending on your version of Windows, you will run out of descriptor memory, and InitializeCriticalSection () or some other function will crash.

What you may need is to have a CS pool to use and keep a pointer to the “used” CS inside your structure. But then it becomes quite complicated, and you will need to use Atomic operations to set / clear the CS pointer (to atomically designate an array record as "in use"). It may also require some reference counting, etc.

It turns out complicated.

So first try your way and see what happens. Once we faced a similar situation, and we had to go with the pool, but perhaps the situation has changed since then.

Answer 3

Depending on the types of data elements in the data_type structure (and also depending on the operations you want to perform for these members), you can refuse to use a separate synchronization object, instead using the lock functions.

In your code example, all data members are integers, and all operations are assignments (and apparently counted), so you can use InterlockedExchange () to set values ​​atomically and InterlockedCompareExchange () to read values ​​atomically.

If you need to use non-integer types of data elements or if you need to perform more complex operations or you need to coordinate atomic access to several operations at a time (for example, read data [1]. A, and then write data [1] .b), then you have to use a synchronization object like CRITICAL_SECTION.

If you must use a synchronization object, I recommend that you split your dataset into subsets and use one synchronization object for each subset. For example, you can use one CRITICAL_SECTION for each range of 1000 elements in a data array.

Answer 4

You can also consider MUTEX. This is a good method. Each client can reserve a resource on its own using mutual exclusion (mutex).

This is more common, some libraries also support this in streams. Read about boost :: thread and mutexes

With your approach:

 data_type data[100000]; 

I would be afraid if you do not select it in a heap.

EDIT:

Enhancement :: MUTEX uses critical win32 partitions

Answer 5

As others pointed out, yes, there is a problem, and it is called too fine-grained blocking. This resource is wasteful, and although the chances are small, you will begin to create a lot of supporting primitives and data, when things go get random, call it longer than usual or something else, discord. In addition, you spend resources, because this is not a trivial data structure, as, for example, in VM impls ..

If I remember correctly, you will have more chances to exclude SEH from now on to Win32 or only to higher memory. Separating and combining them is probably the way to go, but it is a more complex implementation. Parasitizing on something else (repeated action) and expecting some short-lived rivalry is another way to deal with this.

In any case, this is a resource management problem with what you have right now.