Question

A one Megabytes block of memory is allocated using the buddy system. Show the results of the following sequence of requests and returns in a figure that is similar to Figure 7.6: Request A: 200 Kilobytes;

Request B: 80 Kilobytes;

Request C: 380 Kilobytes;

Return A;

Request D: 120 Kilobytes;

Return B;

Return D;

Return C.

Also, find the internal fragmentation at each stage of allocation/de-allocation.

Answer 1

• Request A: 200 kilobytes
  No such block found, so we traverse up and split the 0-1024 block into 0-511, 512-1024; we add 512-1024 to list tracking 512 Kilobyte blocks and pass 0-511 downwards; again it is split into 0-255 and 255-512; since we have found the required block size, we add 512-1024 to list tracking
  We have 56 kb internal fragmentation here.
• Request B: 80 kilobytes
  No such block found, so we traverse up and split the 256-512 block into 256-383, 384-512; since we have found the required block size, we add 384-512 to list tracking
  We have 48kb internal fragmentation here.
• Request C: 380 kilobytes
  we have found the required block size 512-1024
  We have 132kb internal fragmentation here.
• Deallocation Request A: 200 kilobytes
  Deallocation will be done,no coalesscing possible  and 0-255 block is free.
• Request D: 120 kilobytes
  No such block found, so we traverse up and split the 0-255 block into 0-127, 128-255; we have found the required block size. we have 8kb internal fragmentation here.
• Deallocation Request B: 80 kilobytes
  Deallocation will be done, no coalesscing possible  and 256-383 block is free.
• Deallocation Request D: 120 kilobytes
  Deallocation will be done, coalesscing of the blocks 0-127,128-255 ,256-512 will also be done and 0-127 block is free.
• Deallocation Request C: 380 kilobytes
  Deallocation will be done,coalesscing of the blocks 0-511, 512-1024 will also be done and 512-1024 block is free.