[동적할당] Dynamic Memory Allocation

동적 할당과 malloc-lab

번역된 CS:APP는 난해한 부분들이 꽤 있었는데 운 좋게 영어로 된 책과 저자의 강의를 봐 이해에 도움이 많이 되었다. 말록랩에서는 여러가지 정책들(placement, splitting, coalescing 에 관련된)과 가용 블럭 정리방법들을 통해 명시적 할당기를 구현 해 볼 수 있었다.

Why Dynamic Memory Allocation?

• We often do not know the sizes of certain data structures until the program actually runs.
• Hard coded bounds such as #define MAXN 15313 can become a maintenance nightmare for large software products with millions of lines of code and tons of users.
• A better approach is to allocate memory dynamically at run time, after the value of n becomes known.
  c++에서 벡터와 배열의 차이를 생각해보면 될 것 같았다. 런타임에 입력값에 따라 동적으로 메모리를 할당해서 쓰면 메모리를 더 효율적으로 쓸 수 있고, 한정된 스택 메모리에 엄청나게 큰 용량을 넣지 않고 힙영역을 사용함으로써 크래시를 방지할 수도 있다.

Dynamic Memory Allocation

• A dynamic memory allocator maintains an area of a process's virtual memory known as the heap
• For each process, the krenel maintains a variable brk(pronounced 'break') that points to the top of the heap.
• An allocator maintains the heap as a collection of various-size blocks. Each block is a contiguous chunk of virtual memory that is either allocated or free.
• Allocators come in two basic styles:
• Explicit allocator
  • Requires the application to explicitly free any allocated blocks. (ex. the malloc package provided by C standard library)
• Implicit allocator
  • Requires the allocator to detect when an allocated block is no longer used by the program and then frees the block.
  • Also known as garbage collectors
  • Higher-level languages such as Lisp, ML, and Java rely on garbage collection to free allocated blocks.

---

Allocator Requirements

Explicit allocators must operate within these constraints:

• Handling arbitrary request sequences : An application can make an arbitrary sequence of allocate and free requests, subject to the constraint that each free request must correspond to a currently allocated block obtained from a previous allocate request - the allocator cannot make any assumptions about the ordering of allocate and free requests.

• Making immediate responses to requests: The allocator must respond immediately to allocate requests.

• Using only the heap: Any nonscalar data structures used by the allocator must be stored in the heap itself.

• Aligning blocks : The allocator must align blocks in a way that they can hold any type of data object.

• Not modifying allocated blocks: Allocators can only manipulate or change free blocks.

Fragmentation (단편화)

Occurs when otherwise unused memory is not available to satisfy allocate requests.

• Internal Fragmentation :
  • Occurs when an allocated block is larger than the payload.
    • A requested payload could be smaller than the allocator's minimum block size.
    • The allocator might increase the block size in order to satisfy alignment constraints.
  • Straightforward to quantify - it is simply the sum of the differences between sizes of the allocated blocks and their payloads.
• External Fragmentation :
  • Occurs when there is enough aggregate free memory to satisfy an allocate request, but no single free block is large enough to handle it.
  • Difficult to quantify because it depends on the pattern of future requests, as well as previous ones and the allocator implementation.

---

Blocks

• A typical heap block consists of a one-word header, the payload, and possibly some additional padding

  

  • Header
    • If we impose a double-word alignment constraint, then the block size is always a multiple of 8 and it is guaranteed that the 3 lower-order bits of the block size are always zero -> We can take advantage of this by storing only the 29 high-order bits of the block size, and using the last 3 bits to encode other information.
  • Padding
    • Could be any size.
    • Can be used to combat external fragmentation.
    • Can be needed to satisfy the alignment requirement.
  • Minimum Block Size
    • System's alignment requirement & the allocator's choice of block format impose a minimum block size -> No block can be smaller than this minimum.

Placing Allocated Blocks

When an application requests a block of memory, the allocator searches the free list for a free block that is sufficient. The manner in which the allocator performs this search is determined by the placement policy.

• First fit : chooses the first free block that fits.
• Next fit : similar to first fit, but starts each search where the previous search left off.
• Best fit : examines every free block and chooses the free block with the smallest size that fits.

Splitting Free Blocks

Once the allocator has located a free block that fits, it must make another policy decision about how much of the free block to allocate.

• Using the entire block can be simple and fast but it could cause internal fragmentation.
• The allocator splits the free block into two parts, and allocates one.

Coalescing Free Blocks

The allocator merges adjacent free blocks to combat false fragmentation - a phenomenon in which available free memory is chopped up into small unusable free blocks.

• Immediate coalescing - merging any adjecent blocks each time a block is freed.
• Deferred coalescing - waiting to coalesce free blocks at some later time, such as when an allocation request fails.

Boundary Tags

A technique developed by Knuth, allows for constant-time coalescing of the previous block.

• The allocator can determine the starting location and status of the previous block by inspecting its footer - a replica of the header placed at the end of each block.
• Requiring each block to contain both a header and a footer can cause significant memory overhead if an application manipulates many small blocks.
• Can be optimized - the size field in the footer of the previous block is only needed if the previous block is free, hence no need to to put footers in allocated blocks.

---

Implicit Free Lists

• A sequence of contiguous allocated and free blocks.
• Called an implicit free list because the free blocks are linked implicitly by the size fields in the headers.
• The allocator can traverse the entire set of free blocks by traversing all the blocks in the heap.
• PROs - Simple
• CONs - Cost of any operation that requires a search will be linear in the total number of allocated & free blocks in the heap.

모든 블럭을 다 본다

• O(n) malloc; n = 모든 블럭의 수
• O(1) free; (with immediate coalescing)
• O(n+m) realloc; n driven by malloc, m payload size

---

Explicit Free Lists

We can use some form of explicit data structure to organize free blocks. One method is to implement the free list using a doubly linked list.

• The heap can be organized as a doubly linked list by including a predecessor and a successor pointer in each free block.

• Free blocks must be large enough to contain all of the necessary pointers. This results in a larger minimum block size and increases the potential for internal fragmentation.

• Using a doubly linked list instead of an implicit free list reduces first-fit allocation time from 'linear in the total number of blocks' to 'linear in the number of free blocks'.

• The allocation time can be either linear or constant depending on the policy we choose for ordering the blocks in the free list.

  • LIFO(last-in-first-out) - The allocator inspects the most recently used blocks first; freeing a block can be done in constant time.
  • Address Order - Address of each block in the list is less than the address of its successor; freeing a block requires a linear-time search to find the appropriate predecessor.

---

Segregated Free Lists

We can use multiple free lists, known as segregated storage , where each list holds blocks that are roughly the same size. The set of all possible block sizes are segregated into size classes.

Segregated Fits

• The allocator maintains an array of free lists, each of them associated with a size class and organized as some kind of explicit or implicit list.
• Search for the next larger size class if fails to allocate.
• If none of the free lists yields a block that fits, requests additional heap memory from the OS.
• Fast and memory efficient
  • Searches are limited to particular parts of the heap instead of the entire heap.
  • Simple first-fit search of a segregated free list approximates a best-fit search of the entire heap.

Buddy Systems

• A special case of segregated fits where each size class is a power of 2.
• It is easy to compute the address of a block and its "buddy". The addresses of a block and its buddy differ in exactly one bit position.
• Fast in searching and coalescing
• The power-of-2 requirement on the block size can cause significant internal fragmentation

Simple segregated Storage

• Allocator divides a chunk of memory into equal-size blocks and links them to form a new free list.
• Allocate and free operations insert and delete blocks at the beginning of the free list
  • The list need only be singly linked.
• Free blocks are not coalesced & not split to satisfy allocation requests.
  • No need for headers, footers - The only required field in any block is a one-word successor pointer in each free block.
  • Makes it susceptible to internal and external fragmentation.