Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    lecture_slides_10_102-memallocation-examples

    Uploaded by

    yihuangece
    The document discusses dynamic memory allocation, including the need for allocating and deallocating memory on the heap, and various implementation strategies such as implicit and explicit free lists. It also covers performance goals related to throughput and peak memory utilization, as well as issues of fragmentation in memory allocation. Key concepts include internal and external fragmentation, and the constraints faced by allocators in managing memory requests.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    lecture_slides_10_102-memallocation-examples

    Uploaded by

    yihuangece
    2 views9 pages
    The document discusses dynamic memory allocation, including the need for allocating and deallocating memory on the heap, and various implementation strategies such as implicit and explicit free lists. It also covers performance goals related to throughput and peak memory utilization, as well as issues of fragmentation in memory allocation. Key concepts include internal and external fragmentation, and the constraints faced by allocators in managing memory requests.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses dynamic memory allocation, including the need for allocating and deallocating memory on the heap, and various implementation strategies such as implicit and explicit free lists. It also covers performance goals related to throughput and peak memory utilization, as well as issues of fragmentation in memory allocation. Key concepts include internal and external fragmentation, and the constraints faced by allocators in managing memory requests.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views9 pages

    lecture_slides_10_102-memallocation-examples

    Uploaded by

    yihuangece
    The document discusses dynamic memory allocation, including the need for allocating and deallocating memory on the heap, and various implementation strategies such as implicit and explicit free lists. It also covers performance goals related to throughput and peak memory utilization, as well as issues of fragmentation in memory allocation. Key concepts include internal and external fragmentation, and the constraints faced by allocators in managing memory requests.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 9

    University

     of  Washington  

    Sec3on  10:  Memory  Alloca3on  Topics  


    ¢ Dynamic  memory  alloca3on  
    § Size/number  of  data  structures  may  only  be  known  at  run  7me  
    § Need  to  allocate  space  on  the  heap  
    § Need  to  de-­‐allocate  (free)  unused  memory  so  it  can  be  re-­‐allocated  
    ¢ Implementa3on    
    § Implicit  free  lists  
    § Explicit  free  lists  –  subject  of  next  programming  assignment  
    § Segregated  free  lists  
    ¢ Garbage  collec3on  
    ¢ Common  memory-­‐related  bugs  in  C  programs  

    Memory  Alloca3on  
    University  of  Washington  

    Assump3ons  Made  in  This  Sec3on  


    ¢ Memory  is  word  addressed  (each  word  can  hold  a  pointer)  
    § block  size  is  a  mul7ple  of  words  

    Allocated  block   Free  block  


    (4  words)   (3  words)   Free  word  
    Allocated  word  

    Memory  Alloca3on  
    University  of  Washington  

    Alloca3on  Example  
    p1 = malloc(4)

    p2 = malloc(5)

    p3 = malloc(6)

    free(p2)

    p4 = malloc(2)

    What information does the allocator need to keep track of?


    Memory  Alloca3on  
    University  of  Washington  

    Constraints  
    ¢ Applica3ons  
    § Can  issue  arbitrary  sequence  of  malloc()  and  free()  requests  
    § free()  requests  must  be  made  only  for  a  previously  malloc()’d  block  

    ¢ Allocators  
    § Can’t  control  number  or  size  of  allocated  blocks  
    § Must  respond  immediately  to  malloc()  requests  
    i.e.,  can’t  reorder  or  buffer  requests  
    §
    § Must  allocate  blocks  from  free  memory  
    § i.e.,  blocks  can’t  overlap  
    § Must  align  blocks  so  they  sa7sfy  all  alignment  requirements  
    § 8  byte  alignment  for  GNU  malloc  (libc  malloc)  on  Linux  boxes  
    § Can’t  move  the  allocated  blocks  once  they  are  malloc()’d  
    § i.e.,  compac7on  is  not  allowed.  Why  not?  

    Memory  Alloca3on  
    University  of  Washington  

    Performance  Goal:  Throughput  


    ¢ Given  some  sequence  of  malloc  and  free  requests:  
    §  R0,  R1,  ...,  Rk,  ...  ,  Rn-­‐1  

    ¢ Goals:  maximize  throughput  and  peak  memory  u3liza3on  


    § These  goals  are  oQen  conflic7ng  

    ¢ Throughput:  
    § Number  of  completed  requests  per  unit  7me  
    § Example:  
    § 5,000    malloc()  calls  and  5,000  free()  calls  in  10  seconds    
    § Throughput  is  1,000  opera7ons/second  

    Memory  Alloca3on  
    University  of  Washington  

    Performance  Goal:  Peak  Memory  U3liza3on  


    ¢ Given  some  sequence  of  malloc  and  free  requests:  
    §  R0,  R1,  ...,  Rk,  ...  ,  Rn-­‐1  
    ¢ Def:  Aggregate  payload  Pk    
    §  malloc(p)  results  in  a  block  with  a  payload  of  p  bytes  
    § AQer  request  Rk  has  completed,  the  aggregate  payload  Pk    is  the  sum  of  
    currently  allocated  payloads  

    ¢ Def:  Current  heap  size  =  Hk  


    § Assume  Hk  is  monotonically  nondecreasing  
    § Allocator  can  increase  size  of  heap  using  sbrk()

    ¢ Def:  Peak  memory  u<liza<on  a=er  k  requests    


    § Uk  =  (  maxi<k  Pi  )    /    Hk  
    § Goal:  maximize  u7liza7on  for  a  sequence  of  requests.  
    § Why  is  this  hard?  And  what  happens  to  throughput?  

    Memory  Alloca3on  
    University  of  Washington  

    Fragmenta3on  
    ¢ Poor  memory  u3liza3on  is  caused  by  fragmenta<on  
    § internal  fragmenta7on  
    § external  fragmenta7on  

    Memory  Alloca3on  
    University  of  Washington  

    Internal  Fragmenta3on  
    ¢ For  a  given  block,  internal  fragmenta<on  occurs  if  payload  is  smaller  than  
    block  size  

    block  

    Internal     Internal    
    payload  
    fragmenta3on   fragmenta3on  
     
    ¢ Caused  by    
    § overhead  of  maintaining  heap  data  structures  (inside  block,  outside  payload)  
    § padding  for  alignment  purposes  
    § explicit  policy  decisions  (e.g.,  to  return  a  big  block  to  sa7sfy  a  small  request)    
               why  would  anyone  do  that?  

    ¢ Depends  only  on  the  paRern  of  previous  requests  


    § thus,  easy  to  measure  

    Memory  Alloca3on  
    University  of  Washington  

    External  Fragmenta3on  
    ¢ Occurs  when  there  is  enough  aggregate  heap  memory,  but  no  
    single  free  block  is  large  enough  

    p1 = malloc(4)

    p2 = malloc(5)

    p3 = malloc(6)

    free(p2)

    p4 = malloc(6) Oops!  (what  would  happen  now?)  

    ¢ Depends  on  the  paRern  of  future  requests  


    § Thus,  difficult  to  measure  
      Memory  Alloca3on  

    You might also like