Register

GO Classes DPP | GATE CS | Operating System | Fragmentation

112 views
2 2 votes

The free memory contains three holes, in increasing address order:

$300,\ 200,\ 250$ KiB

The following allocation requests arrive in order:

$100,\ 150,\ 200,\ 200,\ 100$ KiB

Whenever a hole is split, the remaining portion stays at the same position in the free-list.

Which of the following statements are correct?

  1. Under First Fit, the first four requests are satisfied, but the last $100$ KiB request fails.
     
  2. Under Best Fit, all five requests are successfully allocated.
     
  3. Under Worst Fit, all five requests are successfully allocated.
     
  4. Under First Fit, when the final request fails, exactly $100$ KiB of free memory still exists.

1 Answer

0 0 votes

First Fit

Start:

$[300,\ 200,\ 250]$

Request $100$:

$[200,\ 200,\ 250]$

Request $150$ uses the first $200$:

$[50,\ 200,\ 250]$

Request $200$:

$[50,\ 250]$

Next request $200$ uses $250$:

$[50,\ 50]$

Now the final request is $100$ KiB.

Total free memory:

$50+50=100$ KiB

But neither individual hole is $100$ KiB.

So the request fails because of external fragmentation.

Hence A and D are correct.

 

Best Fit

Start:

$[300,\ 200,\ 250]$

$100$ goes into $200$:

$[300,\ 100,\ 250]$

$150$ goes into $250$:

$[300,\ 100,\ 100]$

$200$ goes into $300$:

$[100,\ 100,\ 100]$

The next $200$ request cannot be satisfied.

So B is false.

 

Worst Fit

$100$ uses $300$, leaving $200$.

$150$ uses $250$, leaving $100$.

The two $200$ requests consume the two $200$ holes.

The final $100$ request consumes the remaining $100$ hole.

So all five requests succeed.

Therefore C is correct.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
3 3 answers
254
254 views
GO Classes asked Aug 17
254 views
GO Classes DPP | GATE CS | Operating System | Allocation with Deallocation
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:Alloc...
2 2 votes
1 1 answer
148
148 views
GO Classes asked Aug 17
148 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...
1 1 vote
2 2 answers
148
148 views
GO Classes asked Aug 17
148 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 ...
1 1 vote
1 1 answer
111
111 views
GO Classes asked Aug 17
111 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:$...