Research On Dynamic Memory Allocation Of Heterogeneous Multi-core Processor Based On Markov Chain

Intelligent embedded products have penetrated into all aspects of social life.The processing performance of single-core and homogeneous multi-core processors has been difficult to meet the diverse needs of applications.The world's major processor manufacturers have token heterogeneous multi-core processors as an important research direction to improve the processing power of today's computers.The problem of processing speed mismatch between heterogeneous multi-core processors and memory is an important issue for processor designers,including memory allocation,memory reclamation and memory fragmentation rate in dynamic memory.This paper starts from the heterogeneous multi-core processor,researches and designs the dynamic memory allocation and reclamation algorithm in the real-time operating system,speeds up the allocation and reclamation of memory blocks under the premise of ensuring low memory fragmentation rate,and makes the processor play higher performance.The main research work of this paper is as follows:(1)Aiming at the problem that the heterogeneous multi-core multi-task parallel operation requires fast allocation of free memory blocks,a dynamic memory allocation algorithm based on Markov chain is designed.This algorithm records the process and the number of times of the applied memory block firstly,then constructs a transition probability matrix between memory blocks of different sizes according to the number of times of applications.In this case,the memory block size of the next maximum allocation probability of the current state can be found and pre-allocated when the system allocates this memory block.When the pre-allocation is successful,the time for the processor to wait for the next memory block to be allocated is reduced.When the pre-allocation is unsuccessful,the bitmap and two-level linked list data structure of the Two Level Segregated Fit(TLSF)algorithm are used to locate free memory blocks rapidly so that the worst seek time is predictable.This dynamic memory allocation algorithm is designed to reduce the time that the processor core waits for the free memory block to be allocated during the lookup process.As a result,the performance of the heterogeneous multi-core processors is fully utilized to achieve system real-time requirements.(2)Aiming at the problem that the heterogeneous multi-core memory reclamation speed need balance with the memory allocation speed to maintain the real-time and stability of the system,a memory reclamation algorithm which combining the memory block usage frequency and the Markov chain is designed.The algorithm utilize usage frequency of different size of memory blocks and compares it with the next possible allocated memory block size which calculated by the Markov chain transition probability matrix.If this frequently used memory block is to be applied with a high probability next time,it is not immediately merged with the adjacent free memory block which can ensure frequently used memory blocks can be reused without being merged.This memory reclamation method is mainly based on reducing the merge time in the memory reclamation process,and also reduces the number of times of cutting large memory blocks to ensuring high real-time performance and low memory fragmentation rate of the system.Finally,the heterogeneous multi-core processor experimental simulation platform is built by software parallel platform MPICH2,and the embedded real-time operating system ?C/OS-II equipped with the TLSF algorithm is transplanted to this platform for experimental verification.The comparison test results show that the dynamic memory allocation strategy designed in this paper has a higher improvement in both real-time performance and memory utilization.