CS201 Study Guide

Unit 4: Dynamic Memory Allocation

4a. Construct and deconstruct memory-based CDTs

  1. What are the various approaches to runtime memory allocations?
  2. For each approach to runtime memory allocation, what is the appropriate approach to deallocation?
  3. Why is it important to deallocate runtime-allocated memory as soon as it is no longer needed?
  4. Is memory allocated at runtime for a given ADT always contiguous?
  5. Is a single deallocation statement always sufficient to deallocate an ADT's runtime memory?
  6. Is setting a pointer's value to NULL sufficient to deallocate the memory referenced by the pointer?

We often do not know how many variables or which variable types will be needed while an application is running. C/C++ provides various native types, and we can create compound data types (CDTs) as needed. The application will give us a global view of the limits on types. For instance, if the application never operates on an "unsigned long int", then we know that type will never be needed. But, if the application operates on "long int", then we know that type is needed – but not always how many. This is how dynamic (runtime) memory allocation and deallocation comes into play. We can allocate memory to variables of different data types as needed and deallocate that memory (that is, return it for other uses) when it is no longer needed. Memory allocation is introduced in slide 13 of these notes. This page extends that discussion to ADTs in general. Keep in mind that allocating memory is not sufficient; you have to also manage it. Pay special attention to the methods, terminology, and exercises on this page.


4b. Choose appropriate means of making the best use of available memory in dynamic applications

  1. What are the two major issues that can arise when a program employs dynamic memory?
  2. How is it possible for a program to run out of memory even though the OS reports plenty of memory?
  3. How can a program fail a dynamic allocation when there is more than enough free memory available?
  4. How can the memory of one data type be converted into the memory of another data type?
  5. Why is it not a good idea to interleave allocations of large and small blocks of memory?
  6. What is a good way of calculating the amount of memory to allocate? Why do we do that?

Memory fragmentation is an interesting problem, and is important to consider when employing dynamic memory. There are ways to deal with this issue that are described in this article. Some even go so far as to write the own allocation routines. All of this is part of managing dynamic memory, which is discussed as part of learning outcome 4a. Interestingly, it is possible to reuse memory without deallocation or reallocation. Variables in C/C++ can be recast as long as both variable types employ exactly the same amount of memory. This is an important approach and is not unsafe as long as you are careful.


Unit 4 Vocabulary

This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.

Try to think of the reason why each term is included.

  • "unsafe" variable
  • casting
  • allocation
  • deallocation
  • fragmentation
  • orphaned memory
  • NULL pointer
  • ADT destructor
  • ADT constructor
  • scope
  • memory leak
  • dynamic memory
  • static memory
  • memory lifetime
  • memory reuse