Probability Analysis of Thread Random Competition Mode in Multi-Core programming

This article mainly explains "probability analysis of thread random competition mode in multi-core programming". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's study and learn the probability analysis of thread random competition mode in multi-core programming.

Not any shared data can be designed into a pattern of grouping competition, such as the most commonly used data structure that needs to be used for lookup. When the data structure is divided into multiple sub-data structures, each search cannot be specified to find a specific sub-data structure. Instead, a secondary search must be carried out. First, the corresponding sub-data structure is found within the whole data structure (unlocked). Then look for (lock) in the sub-data structure. If multiple threads are searching at the same time, it is possible that the data found is distributed in different sub-data structures, or in the same sub-data structure. When the search is distributed in the same sub-data structure, lock contention may occur, which will lead to CPU hunger.

In this random lock competition of distributed data structures, what we need to know is that on a k-core CPU, the number of threads m and the number of partitioned sub-data structures n are needed to ensure that the probability of at least k threads running at the same time is not lower than the given probability P.

The first m must be greater than or equal to k, otherwise there is no guarantee that at least k tasks are running. The number of sub-data structures N must also be greater than K, otherwise the number of competing task groups will be less than k, so there is no guarantee that at least k tasks are running. Of course, the larger n is, the smaller the probability of task competition is. The more threads running at the same time, you might as well set n greater than or equal to m. In practice, n is not as large as possible. when n is too large, the number of locks is equal to n, which will cause locks to occupy too much system resources.

Let's calculate the probability that at least k threads are running at the same time, and consider a worst-case scenario: if two threads are accessing the same subdata structure, lock contention must occur. In this worst-case scenario, ensuring that at least k threads are running at the same time is actually equivalent to m threads accessing at least k different sub-data structures.

Assume that the number of threads accessing each child data structure is Xi (0