View on GitHub

Computer Architecture and Operating Systems

Course taught at Faculty of Computer Science of Higher School of Economics

Lecture 5

Dynamic Memory Allocation

Lecture

Slides (PDF, PPTX).

Outline

Example

Simple malloc implementation based on an implicit list and the first-fit policy (full project is here).

Try using it to allocate memory for various programs. For example:

#include <iostream>
#include <string>
#include <vector>

int main() {
  std::string s = "Hello World!";
  std::cout << s << std::endl;
  std::vector<int> v(20, 0);
  int *pp = new int[10];
  delete pp;
  std::string text = "This is some random very long text!";
  return 0;
}

make runcpp
gcc -Wall -g -shared -fpic -o libmalloc.so malloc.c
g++ test.cpp -o testcpp
LD_PRELOAD="./libmalloc.so" ./testcpp
malloc(73728)
malloc is initialized
start=0x56f5dd354000
end=  0x56f5dd355000
head= 0x56f5dd354008
malloc(73728) = 0x56f5dd354008
malloc(1024)
malloc(1024) = 0x56f5dd366010
Hello World!
malloc(80)
malloc(80) = 0x56f5dd366418
malloc(40)
malloc(40) = 0x56f5dd366470
free(0x56f5dd366470)
malloc(36)
malloc(36) = 0x56f5dd366470
free(0x56f5dd366470)
free(0x56f5dd366418)

Tasks

To practice with memory-allocation algorithms, do the following exercises:

  1. Change the implementation to support the next-fit strategy. How will this affect memory utilization?
  2. Improve the realloc implementation in the example:
    • If the new size is smaller than the original size of the block, split the block (the remaining part becomes in empty block).
    • If the next block is empty and is sufficiently large, extend the current block instead of freeing it, allocating a new one, and copying data.
  3. Improve memory utilization: footers are used for coalescing adjacent free blocks and required only for free blocks. This means that, for allocated blocks, they can be a part of the payload. To know whether the previous block is allocated or free, we can use lower bits of the current block’s header. Block size is always multiple of 8, which means that 3 lower bits are 0. The 0th bit is already used to store the block status (allocated or free). The remaining two are vacant.
  4. Improve performance of free block search: maintain an explicit double-linked list of free nodes. This would allow skipping allocated nodes when searching. Pointers to the previous and next free node can be stored inside the body (payload) of a free block. This means that the minimal block size will be 24 bytes: 4 (header) + 8 (pointer to prev) + 8 (pointer to next) + 4 (footer). Also, it is often recommended to align blocks. So, the recommended size is 32 bytes (+8 bytes alignment padding).

Workshop

Workshop on strings in C language is here.

See the Homework in the workshop materials.

References