A Dynamic Storage Allocation Algorithm with Predictable Execution Time 


Vol. 7,  No. 7, pp. 2204-2218, Jul.  2000
10.3745/KIPSTE.2000.7.7.2204


PDF
  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
  Cite this article

[IEEE Style]

S. M. Jung, H. Y. Yoo, J. H. Shim, H. J. Kimn, K. H. Choi, G. H. Jung, "A Dynamic Storage Allocation Algorithm with Predictable Execution Time," The Transactions of the Korea Information Processing Society (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. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 7, 7, (2000), 2204-2218. DOI: 10.3745/KIPSTE.2000.7.7.2204.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals