The Research And Implementation Of Mutual Exclusion Mechanism Under Shared Memory Heterogeneous Multi-Processor System On Chip

With the increasing of the chip integrity and the users' increasing demand for electronic products function, heterogeneous shared memory Multi-Processor System on Chip has gradually become the mainstream in the high-end embedded applications market. For a complex MPSoC system, the mutual exclusion between parallel tasks has already become the core issue that must resolve effectively. On the other hand, In Digital Video Server project, Davinci TMS320DM6446 is used, and the platform is a typical shared memory heterogeneous MPSoC, which integrates the two different architectures, ARM and DSP. In this platform, in order to ensure the accuracy of tasks accessing shared resources between processors and to increase parallelism, mutual exclusion has become an unavoidable problem that must solve the efficiently. Thus the research has a certain theoretical and practical significance.This paper makes an in-depth investigation into the mutual exclusion model, algorithms, and implementation, and the main work is summarized as follows.1. Propose a mutual exclusion model based on shared memory Multi- Processor System.General mutual exclusion model can not describe a mutual exclusion algorithm that distinguishes the source of the tasks well, so this paper proposes a mutual exclusion model which is based on a Shared Memory MultiProcessor system. The mutual exclusion model expands the definition and theorem of the original model; can accurately quantify the performance indexes and the attributes of the mutual exclusion algorithms. In a word, it can better adapt to the demand for description, demonstration and performance measure of mutual exclusion algorithm.2. Three mutual exclusion software algorithms under shared memory heterogeneous MPSoC are proposed and demonstrated based on the AK algorithm.In order to overcome the O(n) shared memory space shortcomings of the AK algorithm, this paper presents the Priority Tree Back-off (PTB for short) algorithm which considers the trade-off between real-time and fairness, enables real-time tasks of accessing critical section preferentially , and the shared space complexity is only O(1) and the algorithm is easier to implement.In the fierce critical section competition, either the AK algorithm or the PTB algorithm will cause a great of network on-chip or bus traffic. In view of this problem, this paper presents a Twice Competition PTB algorithm (TCPTB for short) that not only can make full use of single-processor resources such as Cache Consistency, but also can reduce the shared memory space and the volume of traffic, and reduce the overall complexity of mutual exclusion algorithm design.In some database systems and real-time systems, there is such demand for tasks that can not enter the critical section in a certain period, and then give up the critical section to perform other task instead. To meet such a request, the Abortable PTB algorithm (APTB for short) is proposed in this paper, if a real-time task has not yet entered the critical section before the deadline, it will give up.3. Design and implement a mutual exclusion middleware under Davinci DM6446 platform.In order to achieve efficient mutual exclusion between tasks in ARM and DSP, and to truly compare algorithm performance with the original algorithm, the mutual exclusion algorithm needs to be implemented under Davinci DM6446 (simulation tool is not mature enough and not opening to the outside world). To enhance the scalability and versatility, this article designs and implements a mutual exclusion middleware mechanism under DM6446. The mechanism integrates the dynamic shared memory management, implementing of a variety of mutual exclusion algorithm, and the application programming interface together.4. Experiment and analysis for comparison of algorithm performance under Davinci DM6446.As a measure of algorithm performance, the evaluation is carried out by doing experiments under the real platform (Davinci DM6446), and the performance index use quantifying index in mutual exclusion model.Experiments show that, in the middle and small-scale critical section competition, the PTB algorithm is better than AK algorithm; in the middle and large-scale competition the TCPTB algorithm is more efficient than the AK algorithm; and APTB considers the demand for tasks in the database and real-time systems that can not enter the critical section in a certain period, then give up the critical section. Compared with the AK algorithm, these three algorithms not only need a very small shared storage space but also enable real-time task of accessing critical section preferentially.