TAOCP 2.5 Exercise 18
With first-fit, Algorithm A always takes the first available block large enough to satisfy a request.
Section 2.5: Dynamic Storage Allocation
Exercise 18. [**] [20] Figures 42 and 43 were obtained using the same data, and essentially the same algorithms (Algorithms A and B), except that Fig. 43 was prepared by modifying Algorithm A to choose best-fit instead of first-fit. Why did this cause Fig. 42 to have a large available area in the higher locations of memory, while in Fig. 43 there is a large available area in the lower locations?
Verified: yes
Solve time: 1m33s
With first-fit, Algorithm A always takes the first available block large enough to satisfy a request. Since allocation begins near the lower addresses and proceeds upward through the available list, free space tends to be consumed in low memory. When blocks are later returned and coalesced by Algorithm B, much of the unused space accumulates toward the higher addresses. This explains the large available region at the high end of memory in Fig. 42.
With best-fit, Algorithm A chooses the smallest available block that can satisfy the request. Small requests therefore tend to consume the small fragments scattered throughout memory, while the largest free blocks are preserved. Since the largest free areas are often produced by coalescence and tend to occur near the upper addresses, they remain intact longer. Consequently the remaining free space is concentrated toward the lower addresses, producing the large available region at the low end of memory seen in Fig. 43.