Allocation Data Structure
We will discuss two allocation data
structures:
• Stacks
• heaps
Stacks
• A stack is a linear data structure which satisfies
the following properties:
– Allocations and deallocations are performed in a last-
in-first-out (LIFO) manner
– Only the last entry is accessible at any time
• Being a linear data structure, an area of memory is
reserved for the stack
• A pointer called the stack base (SB) points to the
first word of the stack area
• The stack grows in size as entries are created i.e.,
as they are allocated memory
Stacks
• A pointer called as top of stack (TOS) points to the
last entry allocated in the stack
• When an entry is pushed (allocated) on the stack,
TOS is incremented by l, the size of the entry
(assume l = 1)
• When an entry is popped (deallocated), TOS is
decremented by l
• To start with, the stack is empty i.e TOS = SB - 1
Extended Stack Model
• To allocate an entry, a record is created in
the stack, where the record consists of a set
of consecutive stack entries
• In addition to SB and TOS, two new
pointers exist in the model:
– A record base pointer (RB) pointing to the first
word of the last record in stack
– The first word of each record is a reserved
pointer
Allocation Time Actions
1. TOS := TOS + 1
2. TOS* := RB;
3. RB := TOS
4. TOS := TOS + n
• Step 1 increments TOS by 1. It now points at the
reserved pointer of the new record
• Step 2 deposits the address of the previous record base
into the reserved pointer
• Step 3 sets RB to point at the first stack entry in the new
record
• Step 4 performs allocation of n stack entries to the new
entity. The newly created entity now occupies the
address <RB> + l to <RB> + l × n
Deallocation Time Actions
1. TOS := RB – 1
2. RB := RB*
• Step 1 pops a record off the stack by
resetting TOS to the value it had before
the record was allocated
• RB is then made to point at the base of the
previous record
Example
Program sample (input, output)
var
x, y : real;
i : integer;
procedure calc (var a, b : real)
var
sum : real;
begin
sum := a + b;
…
end
begin {Main Program}
…..
end
Heaps
• A heap is a nonlinear data structure which permits
allocation and deallocation of entities in a random
order
• An allocation request returns a pointer to the
allocated area in the heap
• A deallocation request must present a pointer to
the area to be deallocated
• The heap data structure does not provide any
specific means to access an allocated entity
• It is assumed that each user of an allocated entity
maintains a pointer to the memory area allocated
to the entity
Heaps-Example
float *floatptr1, *floatptr2;
int *intptr;
floatptr1 = (float *) calloc (5, sizeof(float));
floatptr2 = (float *) calloc (2, sizeof(float));
intptr = (int *) calloc (5, sizeof(int));
free (floatptr2)
Memory Management
• Consists of identifying the free memory
areas and reusing them while making fresh
allocations
• Speed of allocation/deallocation, and
efficiency of memory utilization are the
performance criteria of memory
management
Identifying Free Memory Areas
Two popular techniques used to identify
free memory areas are:
1. Reference Counts
2. Garbage Collection
Reference Count Technique
• The system associates a reference count with each
memory area to indicate the number of its active
users
• The number is incremented when a new user gains
access to that area and is decremented when a user
finishes using it
• The area is known to be free when its reference
count drops to zero
• It is simple to implement and incurs incremental
overheads i.e., overheads at every allocation and
deallocation
Garbage Collection Technique
• System performs garbage collection when it runs out
of memory
• It makes two passes over the memory to identify
unused areas
• Pass I: traverses all pointers pointing to allocated
areas and marks the memory area which are in use
• Pass II: finds all the unmarked areas and declares
them to be free
• Overheads are not incremental. They are incurred
every time the system runs out of free memory to
allocate to fresh requests
Reuse of Memory
• To manage the reuse of free memory, the system can
enter the free memory areas into a free list and service
allocation requests out of the free list
• Alternatively, it can perform memory compaction to
combine these areas into single free area
• When memory compaction is used, fresh allocations
are made from the block of free memory
• The free area descriptor and the count of words in the
free area are updated appropriately
Reuse of Memory
When a free list is used, two techniques
can be used to perform a fresh allocation
1. First fit technique
2. Best fit technique
First Fit Technique
• The first fit technique selects the first free
area whose size ≥ n words, where n is the
number of words to be allocated.
• The remaining part of the area is put-back
into the free list
• Suffers from the problem that memory areas
become successively smaller, hence
requests for larger memory areas may have
to be rejected
Best Fit Technique
• Finds the smallest free area whose size ≥ n
• This enables more allocation requests to be
satisfied
• However, in the long run it, too, may suffer
from the problem of numerous small free
areas
