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.
Explain why this phenomenon occurs
and why it is undesirable.
Propose a modification to the acquire algorithm
that alleviates this effect.
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.
Devise a scenario which illustrates that next fit
can be better than first fit.
Devise a scenario which illustrates that best fit
can be better than first fit.
Devise a scenario which illustrates that first fit
can be better than best fit.
Under what conditions (if any) does the worst fit
scenario make sense.
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?
Show how Program can be modified
to implement the best fit storage allocation.
What is the running time of your algorithm?
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?
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.
Show how Program can be modified
to implement the best fit storage allocation.
What effect does using the best-fit strategy have
on the length of the free list in this case?
What is the running time of your algorithm?
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.
Devise an algorithm that uses bit manipulation operations to compute
where n is an integer such that .
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?