Dynamic Resource Allocation

JMP $FCE2
MarcWalters
Member
Member
Posts: 55
Joined: Wed Jun 11, 2014 2:33 pm
Location: Lake Macquarie, NSW, Australia
Contact:

Dynamic Resource Allocation

Post by MarcWalters »

The C64's RAM is limited: first by the stock architecture and further by restrictions of individual program requirements.

Subroutines may require chunks of RAM for temporary use. The usual machine language technique is to reserve a chunk of contiguous memory for that particular routine, and/or reserve a common area of memory to be shared. This works fine for most cases, but sometimes too much of this reserved memory is wasted by being rarely or never used.

A problem can arise when:
* there are a lot of subroutines requiring memory for temporary use (eg a library of related subroutines)
* when the subroutines can be called recursively and each instance of that routine requires a separate chunk of memory (eg functions)
* large chunks of memory may be required temporarily but not necessarily for the lifetime of any single subroutine (eg a WIMP system)

There are various approaches to the problem, but on the C64 and other small computers these are applied (at least in my own experience) on an ad hoc basis whenever a refactor is required.

I've had success using an allocation pool of Handles with reserved memory, similar to that concept as used in MS Windows programming.

It works like this:
1) Reserve an area of memory and break it up into equal sized sections. The size of the sections is the maximum amount of memory that any code using it may require.

2) restrict access to each memory section through the use of an Allocate subroutine that returns an index (which I'll refer to as a Handle from now on) and internally marks that Handle as "allocated". An allocated Handle cannot be handed out again until it is returned (deallocated).

3) The program that received the Handle either stores it in a spare byte of memory or carries it in a Register. To access the memory section it uses the Handle as an addressing index (but think of it as a unique key). The implementation should also allow the absolute address of the memory section to be obtained for more flexible operations using Zero-Page Indirect modes and self-modifying code.

4) Once the program is done using the memory section it calls a DeAllocate subroutine, passing in the Handle value as its parameter. The subroutine internally marks the Handle (and by implication, the memory section) as once again available.

Under The Hood
There are many ways to implement this, but it's really just the management of a set of indices.

A pool of handles could be arranged like this:
Maximum_Available, Current_Available, Handle_1, Handle_2,...

Example:
For a reserved memory pool 100 bytes in size and comprising 5 sections the Handle Pool would be set up as:
.BYTE 5, 5, 0, 19, 39, 59, 79

If three Handles were allocated then the Current_Available would reflect this:
.BYTE 5, 2, 0, 19, 39, 59, 79

When a Handle is deallocated, two things happen:
1) The Current_Available is incremented
2) Handle value being deallocated is swapped with the Handle value of the next available position + 1 (to avoid gaps in the unallocated range of Handles)

For example, if the first Handle allocated (with value 79) is returned to the pool it is swapped with Handle with value 39. It doesn't matter if the handle values get unsorted, because they are maintained only as a set of unallocated values immediately followed by a set of allocated values, with the Current_Available indicating their boundary.
.BYTE 5, 3, 0, 19, 79 , 59, 39

The Handle values don't have to be actual indices used to directly access the reserved memory. They could point to entries in a table for example, which has the addresses of each memory section. The implementation of such a system will vary.

Summary
This technique is of most use to larger, complex programs where memory becomes an issue if statically assigned. It's main benefits being that it moves some of the more problematic memory management responsibilities from individual subroutines to a single central scheme, and provides a safe way to share memory.


Prime

Re: Dynamic Resource Allocation

Post by Prime »

Were testing code at this time and completely open to ideas
I thought it would be faster for tables but Bert wants callbacks we need to test
Very much appreciate the suggestions Marc Walters
Post Reply Previous topicNext topic

Who is online

Users browsing this forum: No registered users and 4 guests