Exercises

1. Consider the memory map shown in Figure . The figure suggests that smaller areas (both free and reserved) are more likely to be found at lower address than at higher addresses.
   1. Explain why this phenomenon occurs and why it is undesirable.
   2. Propose a modification to the acquire algorithm that alleviates this effect.
2.   Consider a singly-linked storage pool. Several strategies are possible when searching a free list for an area of a given size:

   first fit

     Select the first area encountered that is large enough to satisfy the request.

   next fit

     This is similar to first fit, except that the free list is treated as a circular list. Each subsequent search begins from the position where the previous search ended.

   best fit

     Select the smallest area that is large enough to satisfy the request.

   worst fit

     Select the largest area as long as it is large enough to satisfy the request.

   1. Devise a scenario which illustrates that next fit can be better than first fit.
   2. Devise a scenario which illustrates that best fit can be better than first fit.
   3. Devise a scenario which illustrates that first fit can be better than best fit.
   4. Under what conditions (if any) does the worst fit scenario make sense.
3. Show how Program  can be modified to implement the next fit storage allocation strategy described in Exercise . What is the running time of your algorithm?
4. Show how Program  can be modified to implement the best fit storage allocation. What is the running time of your algorithm?
5. Devise optimal algorithms for acquire and release given we know a priori that all the areas acquired from a storage pool will have the same size. What are the running times of your algorithms?
6. Consider the memory maps shown in Figure  and Figure . When using the SinglyLinkedPool a large block of unused memory is located at one end the pool whereas when using the DoublyLinkedPool the large free area is located at the other end. Explain why this is so.
7. Show how Program  can be modified to implement the best fit storage allocation.
   1. What effect does using the best-fit strategy have on the length of the free list in this case?
   2. What is the running time of your algorithm?
8. Consider the implementations of the SinglyLinkedPool and DoublyLinkedPool classes. In both cases, the sentinel is located immediately following the last block of the storage pool. Explain how the implementations depend on this.
9. Devise an algorithm that uses bit manipulation operations to compute

   

   where n is an integer such that .

10. It is possible to implement a buddy pool in which the size of the pool is not a power of two. What modifications to the algorithms are necessary in order to do this?

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.