Question

Question 5 - Free Space Management Free space management involves capturing a description of the computer's using a data structure, storing this data structure in memory, and OS support to rap this structure to determine an appropriate location for implementation is very important when we scale up the number of operatior required to perform. free memory idly use new memory allocations. An efficient s the OS is Consider the use of a linked list for a free s placing th pace list where each node is represented by e following structure in the header of the memory chunk: typedef struct _node t int size; struct node_t *next; node_t; Consider the following free space list: head- NULL size-10 size-5size-8 size-32size-1 size-7 Consider the next fit allocation strategy. For this free list above, how many comparis operations must be performed to identify a free chunk of 30-bytes? on After the last free space identification, the chunk is split and the remaining free space is returned to the free space list. Now, consider the next fit allocation strategy. After findin a free space for the previous request, how many comparisons are required to identify a free chunk of 10-bytes? Now, after the last free space identification the chunk is split and the remaining free space is returned to the free space list. Now consider each of the following free space allocation strategies. How many comparisons are required on the updated free space list to find a free chunk of 2 bytes using: (a) best fit: (b) worst fit: (c) first fit:

Please explain your answer

Answer 1

Next fit allocation is same as first fit, the first free space available in the list, having a size >= n bytes which is required by the process is allocated. The only difference from first fit is, for the next memory allocation it starts from the next free space from the list instead of starting from the first free space in the list.

Therefore for 30-bytes requests, Next fit requires 4 comparisons.

Ist comparision starts from the first free space available in the list.Size of 1st free space is 10 bytes(less than 30).

2nd comparision is on the second free space of size 5 in the list which is also less than 30.

3rd comparision is on the third free space of size 8 in the list which is also less than 30.

4th comparision is on the fourth free space of size 32 in the list which is greater than 30.Hence this satisfies the requirement. The 32 bytes free space is split into 30 bytes and 2 bytes. Unused 2bytes is returned back to free space list.

With this allocation, free space list will have:

10 bytes, 5 bytes, 8 bytes, 2 bytes, 1 byte, 7 bytes

To identify the next request of 10 bytes free space in Next fit allocation, it requires 3 comparisions.

1st comparision is on the next free space in the list(i.e., after 32 bytes(30+2)) 1 byte which is less than 10 bytes.

2nd comparision is on the next free space in the list(i.e., after 1 byte) 7 bytes which is also less than 10 bytes.

3rd comparision is on the first free space in the list 10 bytes, as the last comparision is on the last free space in the list. This satisifies the request which is equal to requested 10 bytes.

Now updated free space list will be:

5 bytes, 8 bytes, 2 bytes, 1 byte, 7 bytes

Upon request for 2 bytes of memory,

a. Best fit: requires 5 comparisions.

In best fit allocation, all the free space in the list are searched to find the best(i.e., free space having a size nearer to the requested size) free space, so that it leaves very little amount of unused memory after spliting.

In this case after comparing all the free space in the list, 3rd free space having a size of 2 bytes is allocated.

Thus after allocation, the free space list will be:

5 bytes, 8 bytes, 1 byte, 7 bytes

b. Worst fit: requires 5 comparisions.

In worst fit allocation, all the free space in the list are searched to find the largest free space that is available in the list.So that after spliting, the size of unused memory will be large enough to get allocated for the future requests.

In this case after comparing all the free space in the list, 2nd free space having a size of 8 bytes is splitted into 2 bytes and 6 bytes. The unused 6 bytes of memory is returned back to free space list.

Thus after allocation, the free space list will be:

5 bytes, 6 bytes, 2 bytes, 1 byte, 7 bytes

c. First fit: required 1 comparision.

In first fit allocation, the first free space in the list which has a size >= n bytes(where n bytes is the requested bytes) is allocated to the requested process. After spliting the unused memory is returned to the free space list.

In this case after comparing the first free space in the list, having a size of 5 bytes which satisifies the requested size(> 2 bytes) is splitted into 2 bytes and 3 bytes and allocated to process. The unused 3 bytes of memory is returned back to free space list.

Thus after allocation, the free space list will be:

3 bytes, 8 bytes, 2 bytes, 1 byte, 7 bytes