IT215: SYSTEM SOFTWARE Project 2: DIY allocator

Use of explicit free list :

We have used explicit free list to maintain the list of pointers to free blocks. This enhances speed wise performance of allocator as compared to implicit free list. This is because allocator has to traverse only the list of free list instead traversing the whole list of blocks.

Implemented explicit free list to maintain the list of pointers to free blocks.
-> Data structure used is doubly Linked list.
-> Each free-block contain two pointers.
-> The first points to previous free block.
-> The second points to next free block.
-> 'free_lits_header' is used as an header to this Linked list of free blocks.
-> Macros Used :
* To access previous and next free block.
#define GET_NEXT_FREEP(bp) ((char **)(bp + WSIZE))
#define GET_PREV_FREEP(bp) ((char **)(bp))
* To set previous and next free block.
#define SET_NEXT_FREEP(bp, qp) (GET_NEXT_FREEP(bp) = qp)
#define SET_PREV_FREEP(bp, qp) (GET_PREV_FREEP(bp) = qp)

-> Functions Used :
* To add insert new free block in free-list.
insert_free_blk(void *bp)
remove_free_blk(void *bp)

Improvements in realloc :

Made necessary improvements in realloc funtion to improve the efficiency.
-> The previously implemented realloc called malloc to find memory of new size and copy all contents to it. This reduced the throughput drastically.
-> Possible solution tried here:
* Check if the block needs to expand or not.
* Check the next block is free or not and the combined size of both current block and next is greater than the requested size.
=> If next block is free then only change the size of current block and set header and footer.
=> If next block is not free just go with the traditional method of calling malloc to find memory of new size and copy all contents to it.

Coalescing :

Immediate coalescing using boundary tag coalescing.

Insertion policy in free list :

-> LIFO (last-in-first-out) policy
-> Insert freed block at the beginning of the free list
ie., latest block to be freed may be next one to be allocated

Searching policy :

Searching through free list executes first fit algorithm.

Development stages:

Note: distro: Linux Mint 17.3 Cinnamon 64-bit

Trace files (short{1,2}-bal.rep) that used for initial debugging and testing. Once they started yeilding efficient performance (86/100 and 96/100), proceeded further with 9 traces. And for the last two traces made proper changes in realloc as described above.

The overall performance is:
Pref Index = 31/40 (util) + 60/60 (thru) = 91/100