Entrez dans le monde du FORTH/Enter in world of FORTH

Technical pages
Dynamic allocation of the memory

Instructions
Use
Example

Principle

If language FORTH is little greedy in memory occupation as regards the code, it goes away otherwise when it is a question of treating data of important sizes the graphic files for example (this is moreover valid about is programming language).

It is so indispensable to optimize the use of the memory containing data knowing that, on one hand, the size of the memory will be never infinite and that, on the other hand, all the applications are never activated simultaneously.

Language FORTH allows the base only the static allocation of memory in the help mainly of the instruction " ALLOT ". This instruction reserves the number of 16 bits words spent as argument on the data stack. These words are directly taken in the vocabulary space and can not be freed for another application.

In contrast, the dynamic allocation of the memory gives means to every application to assign some memory according to its need and to restore it when program is ended. So, another application will be able to get back this space memory.

The driver whom I created organizes memory under the shape of a chained list with blocks size of which depends on requests of every application:

HERE+50000	Limit of the available memory
...	...
Block 1	Block 2 address + busy state
	0
	Block 1 content
Block 2	Block 3 address + free or busy state
	Block 1 address
	Block 2 content
...	...
Block n	Block n+1 address + busy or free state
	Block n-1 address
	Block n content
...	...
End of the list	0
End of the list	Last block address

A block, an element of the chained list, is consisted of 3 left:

The first 4 bytes contain size in bytes of the third part of the block (multiple of 8 bytes). The 3 lower significant bits indicate that the block is free if they are all the 3 with zero. If bit 0 is 1, the block is reserved by an application. Bits 1 and 2 are reserved for a future evolution and have to be at present always in zero.
4 following bytes are constituted by the complement in 1 (inversion bit with bit) to first 4 bytes. It allow so the system to verify the coherence of the chained list.
The following bytes correspond to data reserved by the application. The address of the first of these bytes must be remembered by the application using them.

The last 8 bytes of the memory contain a size zero to mark the end of the chained list which corresponds to the end of the memory.

Instructions

- MEMOIRE_ADRESSE address

Address of the beginning of the memory allouable dynamically.
This variable is reserved for the system

- MEMOIRE_PROBLEME -

Procedure of system stop after detection of an abnormality in the chained list.
This instruction is reserved for the system

- T_MEMOIRE_CONTROLE address

Task of control of the chained list.
This task is administered by the system

size MEMOIRE_ALLOUE address

Allocation of a block memory having clarified size.
Address is nobody if allocation is impossible

address MEMOIRE_LIBERE b

Liberation of a block memory.
b is zero if operation was made correctly

- MLIST -

Listing of size, address and occupation state of memory blocks.

Use

An application needs to use only 2 of first defined instructions: " MEMOIRE_ALLOUE " and " MEMOIRE_LIBERE ".

The first allows to reserve a memory block size of which is sent as input parameter. The output parameter is the beginning address of the assigned block unless lack of room does not cause a value zero. In the first case, application should remember this address and to work with this one. In the second, application should administer error by indicating it if need be.

The second allows to restore the assigned memory block when it does not need it any more. This block will be then available for another application. The neighboring free blocks are systematically assembled so that applications can arrange sizes of block the biggest possible.

The control task watches regularly (about all the 5 seconds) the coherence of the blocks chained list . If an application exceeds size memory which it reserved, it can then destroy the following block header, what will be discovered by this task. This last one will launch then the system stop procedure by indicating it to the operator by means of the instruction " MEMOIRE_PROBLEME ".

Instruction " MLIST " gives to the developer a means to show the parameters of the various memory blocks.

Example

Let us suppose that your application requires the use of a plug of 100 kilos Bytes ( text editor for example). Instead of reserving this plug in the vocabulary zone by means of the instruction " ALLOT " ( static allocation), you go to assign this space when application will be activated by satisfying you with creating variable one intended to be remembered the address of the plug:

0 VARIABLE TAMPON_100K

: APPLICATION
100000 MEMOIRE_ALLOUE ?DUP
IF
TAMPON_100K 2!
... program corresponding to the application ...
TAMPON_100K 2@ MEMOIRE_LIBERE DROP
ELSE
... indicating procedure that there is no available memory ...
THEN
;

Cet exemple relativement simple démontre que seules 2 instructions sont nécessaires.

Prenons maintenant un cas plus concre prenant avantage du noyau temps réel. Celui-ci permet de mettre en attente l'application lorsqu'il n'y a pas de mémoire disponible et de la lancer dès que possible:

0 VARIABLE TAMPON_100K

TACHE: T_APPLICATION
100000 MEMOIRE_ALLOUE ?DUP
IF
TAMPON_100K 2!
... program corresponding to the application ...
TAMPON_100K 2@ MEMOIRE_LIBERE DROP
T_APPLICATION T_RETIRE
ELSE
100 T_APPLICATION T_ACTIVE
THEN
;

: APPLICATION
... initialization of the application ...
32768 T_APPLICATION T_AJOUTE 10 T_APPLICATION T_ACTIVE
;

This second example shows the advantage to use a real-time kernel combined in the memory dynamic allocation. You can so initialize several applications sharing the same memory space at the different moments. These moments will be automatically administered with the real-time kernel.