The first-fit allocation technique uses a list of free blocks. When an item is required to be placed in a block, the first free block in the list that is large enough to accommodate the item is chosen. If adding the item leaves a large free space, the block is split and the remainder is added as a new block to the list.
For bins of capacity 10, the given items of size 6, 5, 3, 6, 4, 2, 5, 1 can be placed as follows. The free block list is 10, 10, 10, 10...
The first item of size 6 is placed in the first free bin on the list, the remainder 4 is added as a separate bin in the free bock list. The list is now 4, 10, 10, 10...
As 5 cannot be accommodated in a bin with size 4, it is placed in the next free bin and a new block of size 5 added to the list. The new list is 4, 5, 10, 10... The next item of size 3 is placed in the first bin of size 4, the remainder 1 is added to the free list which changes to 1, 5, 10, 10...
The next item of size 6 is placed in the third free bin on the list which then changes to 1, 5, 4, 10, 10...
The next item of size 4 is added to the second bin on the list which changes to 1, 1, 4, 10, 10... The next item is added to the third bin and the list changed to 1, 1, 2, 10, 10... The next item is placed in the fourth bin and the list changed to 1, 1, 2, 5, 10, 10...
The last item is placed in the first bin as it can accommodate the item.
No comments:
Post a Comment