(Webber, Modern Programming Languages [Ch 14]). In this chapter, the HeapManager implements a first-fit mechanism. It uses the first block on the free list that is at least as large as the requested size. Another fairly simple mechanism is called best-fit. The idea is to search the free list for a sufficiently large block that is as close to the requested size as possible. If there is an exact fit on the free list, the best-fit mechanism can stop the search early. Otherwise, it has to search all the way to the end of the free list. This has the advantage that it does not break up large blocks unnecessarily. For example, if there is an exact fit somewhere on the list, the best-fit mechanism will find one, so it will not have to split a block at all.

1. Implement a version of HeapManager class with a best-fit mechanism. Start with a renamed copy of the HeapManager class, and then modify the allocate method to implement a best-fit search. (The Java code for HeapManager with the coalescing version of deallocate that you should use is available at http://www.webber-labs.com/wp-content/uploads/2015/08/14c-HeapManager.java_.txt)

2. Find a simple sequence of operations in which the best-fit manager succeeds while the first-fit one fails. By extending this sequence with just two more calls to mm.allocate, you can get something that will succeed for best-fit and fail for first-fit. There is a sequence that begins like this:

mm = new HeapManager(new int[7]) int a = mm.allocate(2); int b = mm.allocate(1); int c = mm.allocate(1); mm.deallocate(a); mm.deallocate(c);

3. The best-fit is often a better placement strategy than first-fit, but there are examples which it is worse. Find a simple sequence of operations for which the first-fit manager succeeds while your best-fit one fails. There is a sequence that begins like this.

mm = new HeapManager(new int[11]) a = mm.allocate(4); b = mm.allocate(1); c = mm.allocate(3); mm.deallocate(a); mm.deallocate(c);