Dynamic Memory Allocation I - UNT Computer Science

Dynamic Memory Allocation I - UNT Computer Science

Consider Starting with 160 k of memory do: Allocate p1 (50 k) Allocate p2 (30 k) Allocate p3 (40 k)

Free p2 Allocate p4 (40 k) Free p3 Allocate p5 (60 k) Free p1 Allocate p6 (30k) Memory Allocation Algorithms Design YOUR algorithm for allocation and deallocation of memory Memory Management

Dynamic (heap) Significant issues Significant execution time (16%) Memory performance not uniform Allocation policies Bugs Dereference problems Memory leaks Memory Allocation

Strategies Explicit vs. Implicit Memory Allocator General purpose vs. custom allocator Software vs. hardware Allocation Examples p1 = malloc(4)

p2 = malloc(5) p3 = malloc(6) free(p2) p4 = malloc(2) Goals of Good malloc/free Good execution-time performance

Good space utilization Good locality properties Fragmentation Poor memory utilization --fragmentation Internal overhead associated with a block of memory External have enough blocks of memory for a request, but not contiguous Internal fragmentation

Space in use External Fragmentation p1 = malloc(4) p2 = malloc(5) p3 = malloc(6) free(p2) p4 = malloc(6) External fragmentation depends on future requests; thus difficult to anticipate

Bidirectional Coalescing Boundary tags [Knuth73] Replicate size/allocated word at bottom of free blocks Allows us to traverse the list backwards, but requires extra space Important and general technique! Boundary Tags

1 word Header Format of allocated and free blocks a Application Memory (and padding?) Boundary tag (footer) 4

size 4 4 size 4 6 a a = 1: allocated block a = 0: free block size: total block size Application memory (allocated blocks only)

6 4 4 Your turn Using boundary tag data structure, define algorithms for: Allocation Free

Key Allocator Policies Placement policy: Splitting policy: First fit, worst fit, best fit, etc.

Trades off lower throughput for less fragmentation When do we go ahead and split free blocks? How much internal fragmentation are we willing to tolerate? Coalescing policy: Immediate coalescing: coalesce adjacent blocks each time free is called Deferred coalescing: try to improve performance of free by deferring coalescing

Refinements Separate lists Binary buddy Lea allocator Custom allocators Lea Allocator An approximate best-fit allocator with different behavior based on object size

Small Objects (<64 bytes) allocated by exactsize quicklists Medium Objects (<128K) coalesce quicklists Large Objects allocate and free by mmap Generally considered the best allocator known (as of 2000, anyway) http://g.oswego.edu/dl/html/malloc.html

Why programmers use Custom Allocators? Improving runtime performance Reducing memory consumption Improving software engineering (?) Alternative Memory Management Region (arenas)

Reserve memory blocks for program parts Deallocate entire regions, not per allocation Garbage collection

Programmer allocates but doesnt free System keeps track of memory pointed to locations, removes the rest Java Why Garbage Collect at All? Safety

Memory leaks Continued use of freed pointers Simplicity Correctness Programming ease The Two-Phase Abstraction 1. Detection 2. Reclamation

Liveness and Garbage There is a root set which is defined as live. Anything reachable from a live pointer is also live Everything else is garbage The Root Set

The Root Set Static global and module variables Local Variables Variables on any activation stack(s) Everyone else

Anything Reachable From a live value Reference Counting Each allocated chunk has reference count that shows how many locations point (refer) to this one. Advantages ??? Disadvantages ??? Mark-Sweep Collection

Starting from the root set traverse all pointers via depth/breadth first search. Free everything that is not marked. More Information/Detail If you wish to know more: https://www.mpi-inf.mpg.de/ departments/rg1/teaching/ advancedc-ws08/script/lecture09.pdf

Recently Viewed Presentations

  • Object Oriented Analyis &amp; Design Training Agenda

    Object Oriented Analyis & Design Training Agenda

    272-273 Figure 7.6 Data-to-Location-CRUD Matrix The decision to include or not include attributes is based on whether locations need to be restricted as to which attributes they can access. 273-274 Purists argue that every business event's trigger (a data or...
  • 2013 PCI Data Security Awareness Training What is

    2013 PCI Data Security Awareness Training What is

    Today's card processing environment is much more sophisticated and complex than just swiping a card at the point of sale. Example: ecommerce, mobile payments, gateway (API's and Hosted Pages) Consumers are increasingly expecting an integrated buying experience that is personalized,...
  • Verbos reflexivos y recprocos (parte II) Describe las

    Verbos reflexivos y recprocos (parte II) Describe las

    Se visten. Recíproco. Describe las escenas y decide si los verbos son reflexivos, Recíprocos, o de cambio de estado. Se afeitan. Reflexivo
  • PowerPoint Template - POSTECH

    PowerPoint Template - POSTECH

    A word such as establishment may be decomposed into a "stem" establish and a suffix -ment. Should a system attempt to further decompose the stem establish into establ and -ish? Since a difference that makes no difference is no difference,...
  • Running a Conversation Partner Scheme - GALA

    Running a Conversation Partner Scheme - GALA

    Running a Conversation Partner Scheme Introductions Setting the scene Who used the scheme? 11 people with aphasia Varied in age from 20's to 90's White British, except 1 Irish and I Asian lady 6 men and 5 women Variety of...
  • Preoperative Assesment &amp; Premedication

    Preoperative Assesment & Premedication

    or if thyroid replacement therapy has been recently changed • Results from within the last year for patients stable on thyroid replacement therapy. Pregnancy test • if there is any doubt that a female patient may be pregnant (with her...
  • Principles of ecology

    Principles of ecology

    Example: gray wolf. Food chains and food webs. Trophic levels. Levels of nourishment in a food chain. Primary consumers. Secondary consumers. ... Hydrologic/water cycle. Pathway of water from the atmosphere to Earth's surface, below ground, and back.
  • What is an Evolutionary Algorithm? - ULB Sibiu

    What is an Evolutionary Algorithm? - ULB Sibiu

    What is an Evolutionary Algorithm? Chapter 2 * * Knapsack Problem: Implementation question From the viewpoint of programming language, how can you create/represent individuals and the population to manipulate them?