We present a new buddy system for memory allocation that we call the lazy iBuddy system. This system is motivated by two observations of the widely used lazy buddy system on multi-core systems. First, most memory requests are for single page frames. However, the lazy buddy algorithm used in Linux continuously splits and coalesces memory blocks for single page frame requests even though the lazy layer is employed. Second, on multi-core systems, responses to bursty memory requests are delayed by lock contention caused by concurrent accesses of the multi-cores. The lazy iBuddy system overcomes the first problem by managing each page frame individually and coalescing pages only when an allocation of multiple page frames is requested. We devise the lazy iBuddy algorithm so that single page frame allocation can be done in O(1). The second problem is alleviated by dividing main memory into multiple buddy spaces and applying a fine-grained locking mechanism. Performance evaluation results based on various workloads on the XEON 16core with 32 GB main memory show that the lazy iBuddy system can improve memory allocation/deallocation time by up to 47 percent with an average of 35 percent compared with the lazy buddy system for the various configurations that we considered.

We propose a novel kernel-level memory allocator, called M3 (M-cube, Multi-core Multi-bank Memory allocator), that has the following two features. First, it introduces and makes use of a notion of a memory container, which is defined as a unit of memory that comprises the minimum number of page frames that can cover all the banks of the memory organization, by exclusively assigning a container to a core so that each core achieves bank parallelism as much as possible. Second, it orchestrates page frame allocation so that pages that threads access are dispersed randomly across multiple banks so that each thread's access pattern is randomized. The development of M3 is based on a tool that we develop to fully understand the architectural characteristics of the underlying memory organization. Using an extension of this tool, we observe that the same application that accesses pages in a random manner outperforms one that accesses pages in a regular pattern such as sequential or same ordered accesses. This is because such randomized accesses reduces inter-thread access interference on the row-buffer in memory banks. We implement M3 in the Linux kernel version 2.6.32 on the Intel Xeon system that has 16 cores and 32GB DRAM. Performance evaluation with various workloads show that M3 improves the overall performance for memory intensive benchmarks by up to 85% with an average of about 40%.