A Dynamic Storage Allocation Algorithm with Predictable Execution Time


KIPS Transactions on Computer and Communication Systems, Vol. 7, No. 7, pp. 2204-2218, Jul. 2000
10.3745/KIPSTE.2000.7.7.2204, Full Text:

Abstract

This paper proposes a dynamic storage allocation algorithm, QHF(quick-half-fit) for real-time systems. The proposed algorithm manages a free block list per each word size for memory requests of small size, and a free block list per each power of 2 size for memory requests of large size. This algorithm uses the exact-fit policy for small size requests and provides high memory utilization. The proposed algorithm also has the time complexity O(1) and enables us to easily estimate the worst case execution time (WCET). In order to confirm efficiency of the proposed algorithm, we compare the memory utilization of proposed algorithm with that of half-fit and binary buddy system that have also time complexity O(1). The simulation result shows that the proposed algorithm guarantees the constant WCET regardless of the system memory size and provides lower fragmentation ratio and allocation failure ratio than other two algorithms.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. M. Jung, H. Y. Yoo, J. H. Shim, H. J. Kimn, K. H. Choi and G. H. Jung, "A Dynamic Storage Allocation Algorithm with Predictable Execution Time," KIPS Journal (1994 ~ 2000), vol. 7, no. 7, pp. 2204-2218, 2000. DOI: 10.3745/KIPSTE.2000.7.7.2204.

[ACM Style]
Sung Moo Jung, Hae Young Yoo, Jae Hong Shim, Ha Jine Kimn, Kyung Hee Choi, and Gi Hyun Jung. 2000. A Dynamic Storage Allocation Algorithm with Predictable Execution Time. KIPS Journal (1994 ~ 2000), 7, 7, (2000), 2204-2218. DOI: 10.3745/KIPSTE.2000.7.7.2204.