Compare the storage needed to keep track of free memory for

Compare the storage needed to keep track of free memory for the following three methods: bitmap, linked list and linked list with H entries stored in holes. Determine the storage needed to keep track of free space for a 1 GB memory with a bitmap (allocation unit size is n bytes), a linked list (an alternating sequence of m bytes segments and holes assumed, each node consists of a 32-bit address, 16-bit length, 16-bit next node fields), and a linked list with H entries stored in holes (H entries are not counted). Under which condition one is better than the other?

Solution

Answer

Bitmap: to keep track of free memory space bitmap maintain bit array where each cell indicate free (indicated by 0) or occupied (indicated by 1). It is a contiguous array and each cell represents contiguous memory.

Linked list: track free memory by having a node storing the address of the free space and pointer pointing to the next free space.

Linked list with H entries: it track free spaces by having each entry in the list specified as a hole (H) or a process (P). The start address, length and a pointer to the next entry is also maintained in each entry.

Therefore, the storage need for:

1. bitmap to track 1 GB memory is 1 GB

2. a linked list will need size equivalant to the free space available

LL will occupy 8 bytes for each free space and m bytes are occupied space

so size of LL needed = 1 GB/(m + 8) bytes

3. linked list with H will need size equivalant to the free space available with