BRIEF

COMMUNICATIONS

A SIMPLE

SINGLE-LEVEL

STORAGE

ALLOCATION

MECHANISM V. V.

Gusev

and

L.

Go K a m i n s k i i

UDC 681.3.06:51

By c o n t r a s t with p r o g r a m m i n g languages such as ALGOL 60, which can be implemented by means of the pushdown storage allocation principle (as long as internal a r r a y s are d i s r e g a r d e d ) , the well-developed simulation languages require a storage allocation m e c h a n i s m of the m o s t general type: 1) T h e p r o g r a m can fill and c l e a r p r e v i o u s l y filled a r r a y s of storage words at any time of execution. 2) There is no relationship between the o r d e r in which the p r o g r a m fills the a r r a y s and the o r d e r in which they are subsequently c l e a r e d . 3) In general, the lengths of the filled a r r a y s cannot be determined s t a t i c a l l y p r i o r to execution of the program_ (i.e., so-called dynamic a r r a y s are used). The conventional approach to the indicated p r o b l e m is to a s s e m b l e the free portions of the store in a list of homogeneous a r r a y s , i.e., a r r a y s of equal length, and to provide a m e c h a n i s m f o r the partitioning and m e r g i n g of a r r a y s (see, e.g., [1, 2]). The main s h o r t c o m i n g of this approach is that during the e x e c u tion of a task the s t o r e is divided up into alternating filled and c l e a r portions, so that when the p r o g r a m r e q u i r e s a new a r r a y the store b e c o m e s "overfilled" due to its inability to m e r g e s h o r t c l e a r f r a g m e n t s into one~ Moreover, it is exceedingly difficult for the p r o g r a m to s e p a r a t e l y distinguish dynamic a r r a y s . The m o s t effective solution is to reduce all file lengths to just a few admissible multiples of an integer power of two [3, 4]. However, this is a c r i t i c a l l y e x t r a v a g a n t method in t e r m s of s t o r a g e utilization. In the p r e s e n t note we d e s c r i b e a dynamic single-level storage allocation m e c h a n i s m that meets the r e q u i r e m e n t s set forth above and is devoid of the indicated s h o r t c o m i n g s . The m e c h a n i s m is based on notions p r e s e n t e d in [5] and c o m p r i s e s a modification of the dynamic storage m e c h a n i s m described in [6]~ Under the conditions attending the use of the given m e c h a n i s m , c o n s i d e r i n g the two main tasks confronting the p r o g r a m , namely the r e s e r v i n g of space f o r new a r r a y s and the c l e a r i n g of a r r a y s , the f i r s t task at any rate is expedited with tremendous speed. The given storage allocation m e c h a n i s m might a p p r o p r i a t e l y be called a pushdown-oriented m e c h a nism, because, as will be apparent f r o m its description, the more nearly a task utilizes the store in the pushdown reg-[me, the more efficient will be the operation of the m e c h a n i s m . This is an important c o n s i d e r a t i o n , in that even under the indicated general r e q u i r e m e n t s imposed by simulation p r o b l e m s on the s t o r age allocation the pushdown storage utilization regime is c l e a r l y dominant. Description

of the

Mechanism

Any word array of length two or more that can be distinguished by the program is equipped with a so-called flag, ioe., a word containing a reference to that array. The array length is also indicated in the flag. Any references to arrays in the program must be indirect, through the flags. Consequently, the location of the array flags can be constant, and the arrays can be free to relocate. By the same token, the arrays must always include references to "their own" flags. The s t o r e is partitioned into two zones: the zone of flags and the zone of a r r a y s (Fig. 1). The indic a t o r s F and A m a r k , r e s p e c t i v e l y , the last word to be used in the flag zone and the f i r s t word to be used Translated f r o m Kibernetika, No. 6, pp~ 146-147, N o v e m b e r - D e c e m b e r , 1971. Original article submitred June 17, 1971o

9 197-t Consultants t~urea,~ a division of Plenum Publistling Corporation, 227 lf'est ]Tth Street, Xew York, V. Y. ]O0]]. :\'o part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any .form or b) an)" means, electronic, mechanical, photocopying, microfilming~ recording, or otherwise, witltottt written permission of the pltblish~r, .t copy of this article is avoilable from tile pz~blisher for $1J.O0.

1107

0000l aF~ i ~ -

zone

Fig. 1. Storage organization d u r ing p r o g r a m e x e eu rio n.

in the array zone. The memory overfilling condition is F -> A. All arrays distinguishable by the program are close-packed in the array zone~ The flags are concentrated in the flag zone. The flag zone is not "close-packed" and can contain unused words. Words of the latter type are assembled in a list of free flags. Whenever it is discovered that the indicator F has been referred to a word in the free-flag list, that word is deleted from the list, and the value of the indicator F is decremented by one.

READ,

The storage allocation mechanism comprises four routines: READ WORD, RETURN WORD, AND RETURN.

READ WORD Routine. The routine does not come of its execution is the address of a flag-zone The word is extracted from the free-flag list if the word located immediately below the flag zone is selected, and the value by one.

have any parameters~ The outword extracted by the program. latter is nonempty; otherwise the of the indicator F is incremented

READ Routine. The p a r a m e t e r of the routine is the length of the a r r a y required by the p r o g r a m . The outcome of the execution of this routine is the a d d r e s s of the flag of an a r r a y of the given length e x tracted by the p r o g r a m . The a r r a y is extracted immediately above the a r r a y zone; in this event the value of the indicator A is decreased by the length of the a r r a y . Then, r e f e r r i n g to the READ WORD routine, this routine f o r m s a flag for the new a r r a y and organizes the n e c e s s a r y r e f e r e n c e s . RETURN WORD Routine. The p a r a m e t e r of the routine is the a d d r e s s of a flag-zone word to be r e turned to storage by the p r o g r a m . The word to be returned is either inserted into the list of free flags if it is not the last one in the flag zone o r , otherwise, the value of the indicator F is decremented by one. RETURN Routine. The p a r a m e t e r of the routine is the a d d r e s s of the flag of an a r r a y to be returned by the p r o g r a m . After r e f e r r i n g to the RETURN WORD routine, this routine returns the a r r a y flag to available storage and shifts all a r r a y s located above the eliminated a r r a y downward by the value of its length. The r e f e r e n c e s to the shifted a r r a y s and their flags and the value of the indicator A are adjusted accord ingly. A possible alternative to the r a t h e r slow RETURN routine would be a somewhat modified v e r s i o n of the a l g o r i t h m whereby a r r a y s located in the upper part of the a r r a y zone would not be "pushed down" e v e r y time that the p r o g r a m returns an a r r a y located below them, but would instead compile a list of free portions of the store with the idea of c o m p r e s s i n g the a r r a y zone upon the fulfillment of, say, the condit i o n F -> A. The authors e x p r e s s their appreciation to S. D. Mikhnovskii for s o m e v e r y valuable suggestions. LITERATURE 1.

2.

3.

4. 5. 6.

1108

CITED

V. M. Glushkov, L. A. Kalinichenko, T. P. M a r ' y a n o v i c h , V. M. Moskalenko, and IV[. A. Sakhnyuk, SLANG: A P r o g r a m m i n g System f o r the Simulation of Discrete Systems [in Russian], Izd. IK Akad. Nauk Ukr. SSSR, Kiev (1969). R. J. P a r e n t e , "A simulation-oriented m e m o r y - a l l . c a t i o n a l g o r i t h m , " Simulation P r o g r a m m i n g Languages: P r o e . I F I P Working Conf., North-Holland, A m s t e r d a m (1968). H. M. Markowitz, B. Hausner, and H. W. K a r r , SIMSCRIPT: A Simulation P r o g r a m m i n g Language, P r e n t i c e - H a l l , Englewood Cliffs, N. J. (1963). K. C. Knowlton, "A fast storage a l l o c a t o r , " Commun. A s s o c . Computing Mach., 8, No. 10 (1965). P. Z. I n g e r m a n , "Dynamic declarations," Commun. A s s o c . Computing Mach., 4, No. 1 (1961)0 J. K. Iliffe and J. G. Jodeit, "A dynamic storage allocation s c h e m e , " Computer J., 5, No. 3 (1962).