5.2 Rules for List Maintenance

(a)

Each available area is defined by its size and relative address (reckoned in the units appropriate to the resource);

(b)

The elements of each list are arranged at all times in order of increasing relative address. Care is taken that no two list elements represent contiguous areas – the alternative course, to merge the two areas into a single larger area is always taken;

(c)

The whole list can be scanned by looking at successive elements of the array, starting with the first, until an element with a zero size is encountered. This last element is a “sentinel” which is not part of the list proper.

The above rules provide a complete specification for “mfree”, and a specification for “malloc” which is complete except in one respect: We need to specify how the resource allocation is actually made when there exists more than one way of performing it.

The method adopted in “malloc” is one known as “First Fit” for reasons which should become obvious.

As an illustration of how the resource “map” is maintained, suppose the following three resource areas were available:

• an area of size 15 beginning at location 47 and ending at location 61;

• an area of size 13 spanning addresses 27 to 39 inclusive;

• an area of size 7 beginning at location 65.

Then the “map” would contain:

If a request for a space of size 7 were received, the area would be allocated starting at location 27, and the “map” would become:

If the area spanning addresses 40 to 46 inclusive is returned to the available list, the “map” would become:

Note how the number of elements has actually decreased by one because of amalgamation though the total available resources have of course increased.

Let us now turn to a consideration of the actual source code.