COSC 354 EXAM 2 REVIEW STUDY GUIDE

COSC 354 EXAM 2 REVIEW STUDY GUIDE

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)