Register

GO Classes DPP | GATE CS | Operating System | Allocation with Deallocation

237 views
2 2 votes

A contiguous $\textbf{16}$ KB memory region is initially completely free. Memory is allocated from lower to higher addresses.

The following operations occur in order:

  1. Allocate $4$ KB to $P_1$
  2. Allocate $2$ KB to $P_2$
  3. Allocate $2$ KB to $P_3$
  4. Allocate $3$ KB to $P_4$
  5. Allocate $5$ KB to $P_5$
  6. Deallocate $P_1$
  7. Deallocate $P_3$
  8. Deallocate $P_5$

Adjacent free blocks are coalesced whenever possible.

After these operations, four new allocation requests arrive in this order:

$1$ KB, $3$ KB, $2$ KB, $5$ KB

Consider First Fit, Best Fit, and Worst Fit independently, starting from the same memory state after Step $8$.

Which of the following statements are correct?

  1. First Fit can satisfy all four new requests.
     
  2. Best Fit fails to satisfy the final $5$ KB request.
     
  3. Worst Fit fails to satisfy the final $5$ KB request.
     
  4. Immediately before the final $5$ KB request, the largest free hole is $5$ KB under all three policies.

3 Answers

1 1 vote

After the first five allocations, memory is completely occupied:

$[P_1:4][P_2:2][P_3:2][P_4:3][P_5:5]$

After freeing $P_1$, $P_3$, and $P_5$:

$[\text{Free }4][P_2:2][\text{Free }2][P_4:3][\text{Free }5]$

So the initial free holes are:

$\boxed{4,\ 2,\ 5}$


First Fit

Request $1$ KB uses the first $4$ KB hole:

$4\rightarrow3$

Free holes: $3,\ 2,\ 5$

Request $3$ KB uses the first hole exactly: $2,\ 5$

Request $2$ KB uses the $2$ KB hole: $5$

Finally, the $5$ KB request fits exactly.

Therefore, First Fit satisfies all four requests.

So A is true.


Best Fit

Start with:

$4,\ 2,\ 5$

Request $1$ KB uses the smallest suitable hole, $2$ KB:

$4,\ 1,\ 5$

Request $3$ KB uses the $4$ KB hole:

$1,\ 1,\ 5$

Request $2$ KB uses the $5$ KB hole:

$1,\ 1,\ 3$

Now the final request is $5$ KB.

Total free memory is still

$1+1+3=5$ KB,

but the largest individual hole is only $3$ KB.

Hence the request fails due to external fragmentation.

So B is true.


Worst Fit

Start with:

$4,\ 2,\ 5$

Request $1$ KB uses the $5$ KB hole:

$4,\ 2,\ 4$

Request $3$ KB uses one of the $4$ KB holes:

$1,\ 2,\ 4$

Request $2$ KB uses the largest $4$ KB hole:

$1,\ 2,\ 2$

Now the final $5$ KB request cannot be allocated.

Again, total free memory is

$1+2+2=5$ KB,

but there is no contiguous $5$ KB hole.

So C is true.
 

D is false because immediately before the final request, the largest holes are:

  • First Fit: $5$ KB
     
  • Best Fit: $3$ KB
     
  • Worst Fit: $2$ KB
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · Modified version of ...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

1 1 vote
2 2 answers
136
136 views
GO Classes asked Aug 17
136 views
GO Classes DPP | GATE CS | Operating System | Dynamic Memory Allocation
Memory contains free holes, in order:$100,\ 500,\ 200,\ 300,\ 600$ KBProcesses arrive, in order, requiring:$212,\ 417,\ 122,\ 426$ KBFor each policy, allocations stop if ...
2 2 votes
1 1 answer
136
136 views
GO Classes asked Aug 17
136 views
GO Classes DPP | GATE CS | Operating System | Memory Placement Policies
Free holes, in increasing memory-address order, are:$10,\ 4,\ 20,\ 18,\ 7,\ 9,\ 12,\ 15$ KBThree segment requests arrive:$12,\ 10,\ 9$ KBFor Next Fit, searching for the n...
2 2 votes
1 1 answer
97
97 views
GO Classes asked Aug 17
97 views
GO Classes DPP | GATE CS | Operating System | Fragmentation
The free memory contains three holes, in increasing address order:$300,\ 200,\ 250$ KiBThe following allocation requests arrive in order:$100,\ 150,\ 200,\ 200,\ 100$ KiB...
1 1 vote
1 1 answer
102
102 views
GO Classes asked Aug 17
102 views
GO Classes DPP | GATE CS | Operating System | First vs Best Fit
Assume the free-list initially contains, in this order:$1300,\ 1200$Memory requests are allocated by splitting holes exactly to the requested size.We want two sequences:$...