Dynamic Storage Allocation: A Survey and Critical Review
Dynamic Storage Allocation: A Survey and Critical Review
复制标题
DOI：
10.1007/3-540-60368-9_19
复制
发表时间：
1995-09
期刊：
影响因子：
--
通讯作者：
P. Wilson;Mark S. Johnstone;M. Neely;D. Boles
中科院分区：
文献类型：
--
作者：
P. Wilson;Mark S. Johnstone;M. Neely;D. Boles
大约自1960年以来，动态内存分配一直是大多数计算机系统的基本组成部分，内存分配被广泛认为是一个已解决或无法解决的问题。在这个调查中，我们描述了各种各样的内存分配器设计，并指出了与它们的设计和评估相关的问题。然后，我们按时间顺序调查了1961年至1995年间关于分配器的大多数文献。（本书讨论了数十篇论文，细节各不相同，并提供了150多篇参考文献。）我们认为，分配器的设计受到了强调机制而不是政策的过度限制，而后者更为重要；更高层次的战略问题更加重要，但没有得到足够重视。迄今为止，大多数理论分析和经验分配程序评估都依赖于非常强的随机性和独立性假设，但实际的程序行为显示出重要的规律，如果分配程序要在实践中表现良好，就必须利用这些规律。
Dynamic memory allocation has been a fundamental part of most computer systems since roughly 1960, and memory allocation is widely considered to be either a solved problem or an insoluble one. In this survey, we describe a variety of memory allocator designs and point out issues relevant to their design and evaluation. We then chronologically survey most of the literature on allocators between 1961 and 1995. (Scores of papers are discussed, in varying detail, and over 150 references are given.)We argue that allocator designs have been unduly restricted by an emphasis on mechanism, rather than policy, while the latter is more important; higher-levelstrategicissues are still more important, but have not been given much attention.Most theoretical analyses and empirical allocator evaluations to date have relied on very strong assumptions of randomness and independence, but real program behavior exhibits important regularities that must be exploited if allocators are to perform well in practice.