3
$\begingroup$

So I have a problem understanding how the worst-fit protocol for memory allocation reacts to contiguous blocks of empty memory. None of the examples I have found address this possibility.

For example, say you have the following blocks (where 'O' stands for occupied block and 'E' stands for empty block) and are to allocate 10 MB via the worst-fit algorithm:

------------------------------------------------------------
|10 MB O | 40 MB E | 10 MB O | 20 MB E | 30 MB E | 10 MB O |
------------------------------------------------------------
----0---------1---------2---------3---------4---------5-----

My question is does the worst-fit algorithm select block one leaving behind a 30 MB hole in block 1, or does it select block 3 leaving behind a cumulative 40 MB hole between blocks 3 and 4?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ I think the answer to this depends on implementation particulars of the system you're looking at, rather than computer science considerations. In any case, I would have thought that the worst-fit algorithm would simply consider the blocks as it is aware of them, and the issue is when memory is freed whether now-contiguous blocks of empty memory are merged into one. $\endgroup$
    – Ben
    Commented Jun 29, 2012 at 1:26
  • 2
    $\begingroup$ I agree with Ben. On an abstract level, blocks three and four should be one block, which would then be chosen. If they are presented to the (naive) worst-fit algorithm like this, it will not detect them. But then again, you may implement is to check for neigbouring empty blocks, although I think that would not be efficient. $\endgroup$
    – Raphael
    Commented Jun 29, 2012 at 13:30

3 Answers 3

Reset to default
1
$\begingroup$

You have to assume that the blocks are what they are; if they can be coalesced into larger blocks, then this has already happened (ergo, perhaps the blocks that you have before you are not in fact adjacent in memory; they are an abstract list!) So, in short, there is no cumulative hole which spans multiple blocks.

So worst fit just walks the list of free blocks that it knows about and finds the largest block and takes from there.

Improve this answer
$\endgroup$
0
$\begingroup$

I think as per definition of Worst-Fit Algorithm : It will directly go to select the largest block and i.e. Block 1 of 40 MB.

As Worst Fit Algorithm says that the largest memory block will be occupied first and leaving behind the remaining vacated space.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ FYI, a minor tip on formatting: It's not necessary to use so much bold. It would be better to avoid using bold at all, than to put most of your answer in bold. Bold and italics should be used very sparingly, otherwise it looks jarring. $\endgroup$
    – D.W. ♦
    Commented Oct 23, 2013 at 0:24
  • $\begingroup$ @D.W. Thanks... I ll follow it in future.... $\endgroup$
    – Shubham
    Commented Oct 23, 2013 at 12:04
0
$\begingroup$

There are two strategies one could use when allocating/deallocating memory. Let's concentrate on deallocating memory. One could simply add a previously used block to the list of free blocks. As in your example, that leads eventually to perhaps having plenty of space to allocate another block, which the OS simply wouldn't see. The other strategy, known as coalescing, is to modify the deallocation routine so that when a block is to be freed, to check its left and right neighbors and make a single larger free block by merging it with any free neighbors. In this strategy, it's often useful to include pointers in each block, pointing to the left and right neighbors. Any good operating systems text will have further details.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.