CS 208 s21 — Dynamic Memory Allocation: malloc and free

Here is a video lecture for the material outlined below. It covers CSPP section 9.9 through to 9.9.6 (p. 839–848). It contains sections on

1. introduction, memory layout refresher (0:00)
2. key questions (9:02)
3. why dynamic memory allocation? (14:57)
4. types of allocators (19:02)
5. the malloc package (24:36)
6. spreadsheet example (30:43)
7. memory allocator requirements (36:28)
8. memory allocator goals (39:49)
9. fragmentation (44:04)
10. allocator implementation issues (49:15)

The Panopto viewer has table of contents entries for these sections. Link to the Panopto viewer: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=7b62a760-8ea4-4ed7-8e75-ac59010dd3ae

// static global data, size fixed at compile time, exists for the lifetime of the program
int array[1024]; 
void foo(int n) {
    // stack-allocated data, known lifetime (deallocated on return)
    int tmp;
    int local_array[n]; // some versions of C allow dynamically-sized stack allocation

    // dynamic (heap) data, size and lifetime known only at runtime
    int* dyn = (int*) malloc(n * sizeof(int));
    // good practices:
    //    sizeof makes code more portable
    //    void* is implicitly cast into any pointer type; explicit typecast will help you
    //      catch coding errors when pointer types don’t match
}

Two big questions we'll focus on for the next two weeks:

1. how do we manage the scarce resource of physical memory while providing all processes as much virtual memory as they need?
   • implemented by the operating system kernel and hardware
2. how do we handle malloc and free quickly and efficiently?
   • implemented by the C library

Lab 5 will task you with doing 2., so we will start there.

We don't always know how much space we will need for certain data structures, etc. ahead of time. Hardcoded sizes everywhere can lead to problems and become a maintenance nightmare. Hence, we wany the ability to allocate memory as we go along (dynamically)