ECE2035 Exam3

Procedural Abstraction, Data Structures, Heaps

First Fit

The Malloc function finds the first entry in the free list that will hold the value even if there is slack

Best Fit

Searches whole free list to find out what the fit with the least slack is and uses that for mallocing

Fast Free

Only pushes free pointers on the head of the free list it also requires Best Fit for use

Increasing Sorted List Properties

First Fit is Best Fit

Decreasing Sorted List Properties

First Fit is worst Fit but allocates in O(n) and simply pops head off free list

Increasing Address Sorted List

Makes concatenation easier

Internal Fragmentation

Allocation of a block of memory that's too big

External Fragmentation

Lots of small memory blocks that can't satisfy the malloc

Which has the fastest average speed malloc?

B - First fit w/ free list sorted
by decreasing size

Which has the slowest average speed malloc?

C - Best fit w/ unsorted free list

Which has fastest avg speed of free?

C - Best fit w/ unsorted free list

Which has worst internal fragmentation?

B - First fit w/ free list sorted
by decreasing size

What ADT achieves dynamic allocation for memory without using a heap?

Stack

What ADT achieves dynamic allocation for memory without using a stack?

Heap

What functions do you use to dynamically allocate on a stack?

Push() and Pop()

What functions do you use to dynamically allocate on a heap?

Malloc() and Free()