Lines Matching +full:high +full:- +full:dynamic +full:- +full:range

68 pp. 295-303, June 1988.
96 This paper describes a general purpose dynamic memory allocator
99 patterns in the UNIX kernel and a hybrid strategy that is time-efficient
100 for small allocations and space-efficient for large allocations.
102 with a single easy-to-program interface,
120 In a user process such short-term
121 memory would be allocated on the run-time stack.
122 Because the kernel has a limited run-time stack,
124 Consequently, such memory must be allocated through a more dynamic mechanism.
129 and really have to be allocated from dynamic memory.
133 Demands for dynamic memory allocation in the kernel have increased
151 First, the new allocator can only handle a limited range of sizes.
159 Rather than providing many semi-specialized ways of allocating memory,
170 of the well-known memory allocator provided for
178 The range of sizes for memory requests should not be constrained.
223 To keep the kernel utilization percentage as high as possible,
236 processes can allocate cheaply on their run-time stack.
243 of frequently-used kernel interfaces will feel that they
261 .H 1 "Existing User-level Implementations
264 implementations of user-level memory allocators.
275 The 4.2BSD user-level memory allocator works by maintaining a set of lists
283 a block from the 64-sized list.
327 .FI "One day memory usage on a Berkeley time-sharing machine"
332 all of the different uses of dynamic memory are known in advance.
333 Each one of these uses of dynamic memory can be assigned a type.
334 For each type of dynamic memory that is allocated,
353 the ``High Use'' field is the maximum value of 
358 and are typically for long-lived objects
369 and a slower but more-memory-efficient first-fit allocator.
371 Small allocations are done using the 4.2BSD power-of-two list strategy;
391 Because of the inefficiency of power-of-two allocation strategies
406 observes that the power-of-two algorithm yields sizes of 1, 2, 4, 8, \&...
412 that a difference emerges where the power-of-two algorithm will use
419 The allocator then uses a first-fit algorithm to find space in the
420 kernel address arena set aside for dynamic allocations.
423 the power-of-two allocation strategy.
431 is to cluster same-sized small allocations on a page.
432 When a list for a power-of-two allocation is empty,
442 The 4.2BSD user-level allocator stores the size of each block
445 require a power-of-two-sized block.
457 These requests would be nearly doubled if the user-level strategy were used.
518 of the running time of the multi-purpose routines that could
537 significant new run-time costs.
540 on a per-page basis.
552 Making these tables dynamic will have two benefits.
589 most allocations are short-lived, lasting only for the duration of
609 it manages the constant-sized buffer pool.
628 David Korn, Kiem-Phong Vo,
631 pp 489-506, June 1985.
636 pp 519-531, June 1985.
639 ``A Dynamic UNIX Operating System''
646 pp 1931-1946, 1978.