Sung Moo Jung, Hae Young Yoo, Jae Hong Shim, Ha Jine Kimn, Kyung Hee Choi, Gi Hyun Jung

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 7, No. 7, pp. 2204-2218, Jul. 2000
10.3745/KIPSTE.2000.7.7.2204,   PDF Download:

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