CS 354 Exam 2 Questions and Answers Already Passed Latest Update 2025-2026
Heap - Answers A segment of process VAS used for dynamically allocated memory
Dynamically Allocated Memory - Answers Memory requested while proc is running to satisfy
newly known memory needs and a collection of various size memory blocks managed by
allocator
Block - Answers A contiguous chunk of memory that contains
Payload - Answers Part of a block useable by process
Overhead - Answers Part of block used by allocator to keep track of it's id and to manage the
heap
Allocator - Answers Code that allocated and frees memory blocks
Two Allocator Approaches - Answers Implicit and Explicit
1. Implicit Allocation
2. Explicit Allocation - Answers 1. (JAVA uses this) "New" operator determines the number of
bytes needed and the Garbage Collector implicitly frees memory not being used
2. (C uses this) Malloc must explicitly be told the number of bytes and free must be explicitly
called to recycle heap blocks
Two Goals of Allocator Design
Tradeoff - Answers 1. Maximize Throughput
free should be O(1) and alloc should be O(n) where n
is number of heap blocks
2. Maximize Memory Utilization
Higher utilization is better in this method and memory
requested/heap allocated (Payloads and Overhead)
Typically, increasing once will decrease the other
,1. Throughput
2. Memory Utilization - Answers 1. Number of malloc and frees requests
2. The percent of memory used for payload
5 Heap Allocator Requirements - Answers 1. Allocators required use heap space
2. Provide an immediate response
3. Must handle arbitrary sequence of requests
4. MUST NOT move or change previously allocated memory
5. MUST FOLLOW MEMORY ALIGNMENT REQUIREMENTS
4 Heap Design Considerations - Answers 1. Free blocks organization
2. Placement policy
3. Splitting free blocks
4. Coalescing (Merge) free blocks
Double Word Alignment - Answers 1. Block sizes must be multiples of 8 (Double word aligned)
2. Payload Addresses must be double word aligned (Multiples of 8)
1. External Fragmentation
2. Internal Fragmentation - Answers 1. When there is enough heap memory but it is divided into
blocks that are too small to satisfy requests
2. When heap memory is used for overhead (padding) instead of payload
Why does it make sense that JAVA doesn't allow primitives on the heap? - Answers It wastes
space needlessly
1. Size of a Block
2. Status of a Block - Answers 1. Number of bytes in a block
2. Whether the block is allocated or freed
Explicit Free List - Answers Allocator uses a data structure to contain just free blocks
Code: Only track the size of each free block
, Space: Potentially more space
Time: A bit faster only search free list
Implicit Free List - Answers Allocator uses heap blocks as data structure
Code: Must track size and status of each block
Space: Potentially less memory required
Time: More time to skip the allocated blocks
What part of the block is the header? - Answers The first four bytes of a block
Placement Policies for Heap - Answers The algorithms that are used to search heap for free
blocks
First Fit Placement Policy - Answers Steps:
1. Start from beginning
2. Stop at first free block that is big enough
3. Fail if we reach the END MARK
Memory Utilization: Likely to choose blocks close to desired size (Good mem util)
Throughput: Required many skips to set to large free block (Bad throughput)
Next Fit Placement Policy - Answers Steps:
1. Start from the most recently allocated block
2. Stop at the first free block that is big enough
3. Fail if you reach the start block, must wrap around
to beginning
Memory Utilization: May choose block that is too big (Bad mem util)
Heap - Answers A segment of process VAS used for dynamically allocated memory
Dynamically Allocated Memory - Answers Memory requested while proc is running to satisfy
newly known memory needs and a collection of various size memory blocks managed by
allocator
Block - Answers A contiguous chunk of memory that contains
Payload - Answers Part of a block useable by process
Overhead - Answers Part of block used by allocator to keep track of it's id and to manage the
heap
Allocator - Answers Code that allocated and frees memory blocks
Two Allocator Approaches - Answers Implicit and Explicit
1. Implicit Allocation
2. Explicit Allocation - Answers 1. (JAVA uses this) "New" operator determines the number of
bytes needed and the Garbage Collector implicitly frees memory not being used
2. (C uses this) Malloc must explicitly be told the number of bytes and free must be explicitly
called to recycle heap blocks
Two Goals of Allocator Design
Tradeoff - Answers 1. Maximize Throughput
free should be O(1) and alloc should be O(n) where n
is number of heap blocks
2. Maximize Memory Utilization
Higher utilization is better in this method and memory
requested/heap allocated (Payloads and Overhead)
Typically, increasing once will decrease the other
,1. Throughput
2. Memory Utilization - Answers 1. Number of malloc and frees requests
2. The percent of memory used for payload
5 Heap Allocator Requirements - Answers 1. Allocators required use heap space
2. Provide an immediate response
3. Must handle arbitrary sequence of requests
4. MUST NOT move or change previously allocated memory
5. MUST FOLLOW MEMORY ALIGNMENT REQUIREMENTS
4 Heap Design Considerations - Answers 1. Free blocks organization
2. Placement policy
3. Splitting free blocks
4. Coalescing (Merge) free blocks
Double Word Alignment - Answers 1. Block sizes must be multiples of 8 (Double word aligned)
2. Payload Addresses must be double word aligned (Multiples of 8)
1. External Fragmentation
2. Internal Fragmentation - Answers 1. When there is enough heap memory but it is divided into
blocks that are too small to satisfy requests
2. When heap memory is used for overhead (padding) instead of payload
Why does it make sense that JAVA doesn't allow primitives on the heap? - Answers It wastes
space needlessly
1. Size of a Block
2. Status of a Block - Answers 1. Number of bytes in a block
2. Whether the block is allocated or freed
Explicit Free List - Answers Allocator uses a data structure to contain just free blocks
Code: Only track the size of each free block
, Space: Potentially more space
Time: A bit faster only search free list
Implicit Free List - Answers Allocator uses heap blocks as data structure
Code: Must track size and status of each block
Space: Potentially less memory required
Time: More time to skip the allocated blocks
What part of the block is the header? - Answers The first four bytes of a block
Placement Policies for Heap - Answers The algorithms that are used to search heap for free
blocks
First Fit Placement Policy - Answers Steps:
1. Start from beginning
2. Stop at first free block that is big enough
3. Fail if we reach the END MARK
Memory Utilization: Likely to choose blocks close to desired size (Good mem util)
Throughput: Required many skips to set to large free block (Bad throughput)
Next Fit Placement Policy - Answers Steps:
1. Start from the most recently allocated block
2. Stop at the first free block that is big enough
3. Fail if you reach the start block, must wrap around
to beginning
Memory Utilization: May choose block that is too big (Bad mem util)
