CS 240 Lab 12

Learning Goals & Reflection

CS 240 Lab 12

• Lab slides
• Malloc assignment
• There is no notebook for today’s lab

Learning Goals

Core Goals

Students can:

1. Explain how allocated memory blocks are tracked in the heap:
   1. Explain the minimum block size as well as the sizes of headers and footers.
   2. Explain what is stored in headers/footers and the purpose of storing this information in relation to the allocation algorithm.
   3. Explain how the requested size in bytes is related to the actually allocated block size.
   4. Explain how the free and previous-free flags are stored “on top of” the size, and why this is possible without corrupting the size information.
2. Simulate the behavior of various heap allocation algorithms:
   1. Draw heap diagrams showing free/allocated blocks along with appropriate meta-information, given a description of the heap state.
   2. Draw heap diagrams that result from a specific sequence of allocate and/or free operations, for the provided starter code.
   3. Draw heap diagrams based on allocation sequences for the correct solution code (without having implemented that code yet).
3. Read C code to understand what it does:
   1. Recognize code for rounding and alignment of values.
   2. Explain how the | operator in C can be used to combine multiple “flag bits” into a single value, what a “flag bit” can represent, and what numerical values “flag bits” have.
   3. Explain how allocated bits and block sizes are combined into a single value, and how they can be split apart again.
   4. Explain the operation of helper functions that abstract common memory manipulation tasks.
4. Explain the mechanics of allocating and freeing memory on the heap:
   1. Explain what changes are necessary to allocate part or all of a free block.
   2. Explain what changes are necessary to free an allocated block.
   3. Explain how fragmentation can occur and why different allocation strategies might affect how bad it gets.

Stretch goals

1. Explain how allocated memory blocks are tracked in the heap:
   1. Explain why alignment requirements cause us to skip 8 bytes at the start of the heap.
   2. Explain how the restrictions on heap block sizes are related to the alignment requirement.
2. Read C code to understand what it does:
   1. Explain why we did not use a C struct to describe a heap entry.
3. Write pseudocode comments to design an algorithm before implementing it:
   1. Concisely describe memory changes at an abstract level referring to heap blocks and allocated/free statuses.
   2. Plan out the steps needed to implement malloc, free, and the allocate & coalesce helper functions.

Extra goals

1. Understand how memory allocation connects to higher-level languages:
   1. Explain why writing Java code that uses primitive types instead of Object types can be faster in some cases.
   2. Explain why one creating one large object/array to store data and using math to compute offsets within it can be faster than creating many small objects (e.g., using a 1-D list in Python for 2- or 3D information rather than a list-of-lists).
   3. Explain the dangers of premature optimization in terms of both development time/effort and code correctness.

Reflection