Research And Implementation Of Page Allocator

Most of modern operating systems implement paging-based virtual memory system. Physical memory is divided into fixed-size page frames.The page allocator,which is the manager of all the pages,allocates and frees physical pages.Page level operation is a critical path of kernel code.The most important criterion for a page allocator is that it must be fast.The second important criterion is its internal and external fragmentation must be low.In this dissertation we study and improve the Linux page allocator.Based on kernel probe Kprobe,a method of collecting a large amount of data from kernel dynamically is proposed. Using the method the page allocator's behaviour is analyzed,the ratio of page allocator's operation for single page exceeds 99%,and most of used memory is allocated for single page request.To avoid external fragmentation,Linux 2.4 uses buddy allocator as its page allocator,but the main disadvantage of this algorithm is the poor performance due to repetitive coalescing and splitting.Linux 2.6 adds hot/cold page into page allocator to solve this problem.This dissertation proposes a new page allocator which optimizes single page operation and also satisfies the request for continuous page frames,and time complexity of the algorithm is O(1)approximately. The new algorithm has been implemented in kernel 2.6.9.Two benchmarks are used to measure new kernel's performance:kernel compilation time and lmbench.In the test of kernel compilation time,time spent by new kernel is shorter than original kernel's on uniprocessor machine,on dual-processor machine time spent by new kernel is almost equal to original kemel's.Lmbench test results show new kernel is better than original kernel in many aspects.Implementation of page allocator contains the choice of page placement policy.Careful page placement algorithm can reduce cache conflicts and improve cache performance.This dissertation analyzes the impact on cache performance by page allocator,then introduces several page placement algorithms.Two implementation case are investigated:page coloring algorithm in FreeBSD 5.4 and global bin hopping algorithm in NetBSD 2.0.Several implementation issues are solved,including selection of cache level,way to get cache size,the effect on page placement algorithm by SMP and hyper-threading technology.The page placement algorithm adopted by Linux is random algorithm.This dissertation researches the possibility of implementing page placement algorithm in Linux,associated technical problems are analyzed and solved.This dissertation implements global bin hopping algorithm in Linux 2.6.9,and performance tests show no gains,as cache set associativity is increasing,page placement algorithms' influence on system performance is decreasing.