Comp111: Operating Systems
Classroom Exercise 10 Answers
Memory Management
Fall 2017

In class we have studied the buddy system for memory resource management. Let's do some simulation to make sure we understand it. In your simulations, please assume that:

  1. no less than 16 bytes can be allocated via malloc.
  2. the 16-byte block storage descriptor is physically located before the bytes to be used, so that the usable memory starts at the descriptor address+16.
  3. the block descriptor has two 8-byte fields: E.g., if size is 5, then
  4. malloc only calls sbrk in units of 8192 bytes, i.e., the call is of the form sbrk(n*8192) for n a positive integer.
(This is roughly the implementation of "BSD malloc".)
  1. Exactly how much memory is allocated to me if I ask for 800 bytes from malloc? Exactly how much memory is added to the heap?
    Answer: The allocator fits 800 bytes into 2p-16 for the smallest p. That is p=10, allocating 1024-16=1008 bytes. A total of 8192 bytes = 1 page is added to the heap (presuming that this is the first allocation).
  2. Describe exactly what happens when one calls
     
    int *foo = (int *)malloc(100*sizeof(int)); 
    
    as the first malloc of a program. Assume that sizeof(int) is 8 (e.g., on comp111.cs.tufts.edu).
    Answer: First note that this is related to the first problem, because 100*sizeof(int)==800!
    1. First malloc calls sbrk(8192);
    2. The block of 8192 is subdivided into two 4096-byte blocks.
    3. One block of 4096 is subdivided into two 2048-byte blocks.
    4. One block of 2048 is subdivided into two 1024-byte blocks.
    5. A pointer to the 16th byte of one of these 1024-byte blocks is returned to the process.
    At the end, there is one element in the free lists for 212, 211, and 210 bytes, respectively.
  3. Describe exactly what happens when one (subsequently) calls free(foo).
    Answer: foo points to 16 bytes beyond the descriptor, so a pointer to the descriptor can be recovered via the code
    struct descriptor *p=(struct descriptor *)((char *)foo-16);
    . We link p into the free list for 210 (10==p->size). foo is not changed.
  4. Describe exactly what happens when one subsequently calls
    int *bar = (int *)malloc(10*sizeof(int)); 
    
    Is foo's memory reused? Why or why not?
    Answer: Note that foo's memory is at the head of the 210 list, and we want 80 bytes, and thus want to allocate a 128-byte block.
    1. We split foo's memory in half to get two 512-byte blocks,
    2. and then split one 512-byte block into two 256-byte blocks,
    3. and then split one 256-byte block into two 128-byte blocks,
    4. and then use one of these for bar.
    Thus a small part (1/16) of the memory allocated for foo gets reused.
  5. (Advanced) A very common programming error is to write something equivalent to:
    int *cat = (int *) malloc(sizeof(int)); 
    int *dog = (int *) malloc(sizeof(int)); 
    cat[3]=0; 
    free(dog); // segmentation fault: core dumped
    
    Assuming that ints are 8 bytes, why might this cause a segmentation fault when calling free(dog)?
    Answer: Depending upon how malloc is implemented, memory can look like this:
     
    <cat descriptor>                <dog descriptor>
    +-------+-------+-------+-------+-------+-------+-------+-------+
    | next  | size  | cat[0]| cat[1]| next  | size  | dog[0]| dog[1]|
    +-------+-------+-------+-------+-------+-------+-------+-------+
    
    Thus:
    1. cat[3]=0 writes over the next or size field of the descriptor for dog (depending upon implementation), which is unused while the memory is in use. This does nothing.
    2. cat[3]=0 causes a segmentation fault when we try to free dog, because it writes garbage into the next or size field and misdirects the block to the wrong linked list or an invalid location (NULL) for the list element. But since we are concerned with speed, free does not check whether the size field is sane!

    In other words, "real programmers don't write out of bounds" and those unreal programmers that do are in for a lot of pain.








  • (Advanced) Malloc doesn't use the buddy system for things larger than a page (8192 bytes = 213). So why do we allocate 8 bytes to store a number between 5 and 13? It would seem that this number would take a total of 4 bits = 1/2 of a byte.
    Answer: Remember that in an IA64 architecture, the alignment requirements for malloc are at 16 byte boundaries. Thus, if we used only 9 bytes for the descriptor, the resulting address of the allocated memory would be misaligned!