COSC 354 EXAM 2 REVIEW QUESTIONS
Heap definition - Answer -a segment of a processes virtual address space used for
dynamically allocated memory
When is dynamically mem allocated? - Answer -at runtime
Dynamically allocated memory definition - Answer -a collection of various sized mem
blocks that are managed by an allocator
Block definition - Answer -a continuous chunk of memory containing a payload and
overhead
Payload definition - Answer -part of the block usable by the program requesting heap
memory
Overhead definition - Answer -part of the block used by the allocator to manage the
heaps internal structure.
Allocator - Answer -code that allocs and frees heap blocks (as well as splits and
merges them)
How allocator works: Java - Answer -garbage collector, 'new' implicitly determines
bytes needed
How allocators work: C - Answer -malloc must be told how many bytes needed
Free must explicitly be called
Name of C's heap allocator - Answer -stdlib.h
Contains a collection of commonly used C functions
C's heap allocator has functions (4) - Answer -malloc, calloc, realloc, and free
Malloc function
Void *malloc (size_t size) - Answer -allocates and returns generic ptr to block of heap
memory of size bytes, or returns null is allocation fails
Calloc function
Void * calloc(size_t nitems, size_t size) - Answer -allocates, clears to 0, returns a block
of heap memory of nitems * size bytes, or returns null upon failure
Realloc function
Void * realloc(void *ptr, size_t size) - Answer -reallocates to size bytes a previously
allocd block of heap memory pointed to by ptr, or returns null if realloc fails
,Realloc example
Realloc to size bytes a previously alloc'd block of heap mem pointed to by ptr, or return
null if failure occurs. - Answer -if(ptr == null){
Return malloc(size)
}
Else if (size == 0){
Free(ptr);
Return null;
}
Else // attempts to reallloc
See l8-4
Posix definition - Answer -portable os interface
Standard for maintaining compatibility among unix operating systems
What is unistd.h? - Answer -has functions to access posix API
Brk definition - Answer -program break
End point of program in VAS
Brk usage
Int brk(void *addr) - Answer -int brk(void *addr)
Sets top of heap to the specified address addr
Returns 0 if successful, else returns -1 and sets errno
Errno definition - Answer -error number
Set by OS function call (brk or sbrk)
Allocator design:
Goals: throughput - Answer -measure operations/second (how many mallocs you can
do per second)
Higher throughput is better, more operations per second is better
Allocator design:
Goals: memory utilization - Answer -taking memory requested and divide it among the
heap that's been allocated
Higher is better
Tradeoff in allocator design - Answer -increasing throughput decreases memory
utilization and vice versa
List of requirements of a heap allocator - Answer -1) must handle arbitrary sequence of
requests
2) provide an immediate response
3) Doesn't move or change alloc'd blocks
, 4) Allocs should use the heap, keep on heap memory segment
5) Follow alignment requirements of system
Design Considerations for Allocator - Answer --Free block organization
-placement policy
-splitting free blocks to create a better fit
-coalescing free blocks to create larger free blocks
Double word alignment - Answer -block size must be a multiple of 8
Payload address must be a multiple of 8
See heap run 1 l9 -3 - Answer -See heap run 1 l9 -3
External fragmentation definition - Answer -when there's enough free memory in the
heap, but it's divided into smaller noncontinuous blocks
Internal fragmentation - Answer -memory inside a block that is not used for the
payload, instead its overhead
This is also known as padding
Explicit free list definition - Answer -a structure is used to store just the free blocks and
their sizes
Explicit free list con - Answer -space needed for the separate structure
Explicit free list pro - Answer -allocation is linear with respect to the number of free
blocks
Implicit free list definition - Answer -has no separate structure, instead the structure is
part of the block itself
It's overhead is in each block
Implicit free list pros - Answer -uses up less mem space
Makes code simpler
Implicit free list con - Answer -allocator now has to look through both freed and used
mem blocks
Implicit free list
Each block maintains a header with info about... - Answer -...block size and status
Implicit free list
Size defintiion - Answer -total number of bytes in block (including overhead)
Heap definition - Answer -a segment of a processes virtual address space used for
dynamically allocated memory
When is dynamically mem allocated? - Answer -at runtime
Dynamically allocated memory definition - Answer -a collection of various sized mem
blocks that are managed by an allocator
Block definition - Answer -a continuous chunk of memory containing a payload and
overhead
Payload definition - Answer -part of the block usable by the program requesting heap
memory
Overhead definition - Answer -part of the block used by the allocator to manage the
heaps internal structure.
Allocator - Answer -code that allocs and frees heap blocks (as well as splits and
merges them)
How allocator works: Java - Answer -garbage collector, 'new' implicitly determines
bytes needed
How allocators work: C - Answer -malloc must be told how many bytes needed
Free must explicitly be called
Name of C's heap allocator - Answer -stdlib.h
Contains a collection of commonly used C functions
C's heap allocator has functions (4) - Answer -malloc, calloc, realloc, and free
Malloc function
Void *malloc (size_t size) - Answer -allocates and returns generic ptr to block of heap
memory of size bytes, or returns null is allocation fails
Calloc function
Void * calloc(size_t nitems, size_t size) - Answer -allocates, clears to 0, returns a block
of heap memory of nitems * size bytes, or returns null upon failure
Realloc function
Void * realloc(void *ptr, size_t size) - Answer -reallocates to size bytes a previously
allocd block of heap memory pointed to by ptr, or returns null if realloc fails
,Realloc example
Realloc to size bytes a previously alloc'd block of heap mem pointed to by ptr, or return
null if failure occurs. - Answer -if(ptr == null){
Return malloc(size)
}
Else if (size == 0){
Free(ptr);
Return null;
}
Else // attempts to reallloc
See l8-4
Posix definition - Answer -portable os interface
Standard for maintaining compatibility among unix operating systems
What is unistd.h? - Answer -has functions to access posix API
Brk definition - Answer -program break
End point of program in VAS
Brk usage
Int brk(void *addr) - Answer -int brk(void *addr)
Sets top of heap to the specified address addr
Returns 0 if successful, else returns -1 and sets errno
Errno definition - Answer -error number
Set by OS function call (brk or sbrk)
Allocator design:
Goals: throughput - Answer -measure operations/second (how many mallocs you can
do per second)
Higher throughput is better, more operations per second is better
Allocator design:
Goals: memory utilization - Answer -taking memory requested and divide it among the
heap that's been allocated
Higher is better
Tradeoff in allocator design - Answer -increasing throughput decreases memory
utilization and vice versa
List of requirements of a heap allocator - Answer -1) must handle arbitrary sequence of
requests
2) provide an immediate response
3) Doesn't move or change alloc'd blocks
, 4) Allocs should use the heap, keep on heap memory segment
5) Follow alignment requirements of system
Design Considerations for Allocator - Answer --Free block organization
-placement policy
-splitting free blocks to create a better fit
-coalescing free blocks to create larger free blocks
Double word alignment - Answer -block size must be a multiple of 8
Payload address must be a multiple of 8
See heap run 1 l9 -3 - Answer -See heap run 1 l9 -3
External fragmentation definition - Answer -when there's enough free memory in the
heap, but it's divided into smaller noncontinuous blocks
Internal fragmentation - Answer -memory inside a block that is not used for the
payload, instead its overhead
This is also known as padding
Explicit free list definition - Answer -a structure is used to store just the free blocks and
their sizes
Explicit free list con - Answer -space needed for the separate structure
Explicit free list pro - Answer -allocation is linear with respect to the number of free
blocks
Implicit free list definition - Answer -has no separate structure, instead the structure is
part of the block itself
It's overhead is in each block
Implicit free list pros - Answer -uses up less mem space
Makes code simpler
Implicit free list con - Answer -allocator now has to look through both freed and used
mem blocks
Implicit free list
Each block maintains a header with info about... - Answer -...block size and status
Implicit free list
Size defintiion - Answer -total number of bytes in block (including overhead)
