Concurrent Data Structures With Applications In Dynamic Memory Management

With the far spreading utilization of modern multicore processors, softwareindustry finds itself been posed with quickly growing pressure to transform its usualsequential methodology so as to meet with this new concurrency challenge and a newera of computing. In order to achieve better speed up, we need high performanceconcurrent data structures so that concurrent threads’ execution time spent oninteracting through shared objects (data structure) can be reduced. Unfortunately,concurrent data structures are difficult to design. There is a kind of tension betweencorrectness and performance: the more one tries to improve performance, the moredifficult it becomes to reason about the resulting algorithm as being correct. Also, it’shard to strike a balance between single performance under single thread and scalabilitywith the growing number of threads enabled by more and more available processorcores.One pressing issue that is borthering high performance concurrent data structues,especially lock-free ones, is dynamic memory management---the larger amount ofcontending threads enabled by the multicore processor induce a huge amount of rise inthreads consumption of dynamic memory related to the shared lock-free data structures,and as a result, more frequent interaction with the runtime dynamic memory allocator,which will become a bottle neck under high level of contention.This paper tries to look at lock-free data structures’ dynamic memory managementfrom a load balancing point of view and treats it as “backward” load balancing, so thatwe can use the technicals in the field of load balancing to solve lock-free datastructures’ dynamic memory management problem. Based on load balancing, wepropose two concurrent queues and upon them, two memory pools that can distributedynamic memory more equally between threads’ local buffers.Firstly, we analysed the history and current status of researches in the field ofconcurrent data structures, we investigated the common used technical and constructs inthis field and pointed out their relative adavatages and shortenings to each other, and thechallenge they are facing in the multicore age.Secondly, we investigated dynamic memory management with shared memorymulticore processors, studied typical concurrent dynamic memory allocators, pointedout that researchers ignored the special cases related to lock-free data structures’ dynamic memory management, and proposed memory pools as a supplement.Thirdly, we looked into the problem of load balancing, particularly task schedulingin modern computing systems. We studied the two major technicals—work stealing andwork dealing, and modeled lock-free data structures’ dynamic memory management as"backward" load balancing.Then two concurrent queues that supports steal and/or return operations wereproposed along with two memory pools built upon them which can achieve moreequally distribution of dynamic memory among threads’ local buffer by performingsteal and/or return operations during runtime, so that lock-free data structures’ dynamicmemory consumption can be reduced.We also performed detailed experiments to investigate the performance of the twomemory pools we proposed compared to regularly used conventional memory pools.Experiments show that our implementations out performed the conventional memorypools under a wide range of contention level, they achieve much less dynamic memoryconsumption and as a result, considerably less average operation execution time of thetarget lock-free data structures. Our experiments also showed that the two proposedbalancing operations i.e. steal and return did help to achieve far better balancing resultscompared to the conventional memory pool.