실시간 시스템을 위한 시간 결정적 메모리 할당 알고리즘12
Deterministic Memory Allocation Algorithm for Real-Time Systems
1
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
오늘날의 스마트폰, PMP, 지능형 가정기기, 자동차 엔진 컨트롤 시스템과 같은 내장형 시스템은 인간의 삶과 일, 놀이 등 살아가는 환경에 대한 전환을 가져오고 있다. 사용자가 요구하는 다양한 서비스들을 지원하기 위해 내장형 시스템 응용들의 복잡성이 증가하고 있으며, 그런 내장형 컴퓨팅 플랫폼에는 시간결정성을 갖는 실시간 운영체제를 사용해야 한다. 실시간 운영체제는 예측가능한 태스크 스케줄링과 메모리 할당 서비스를 제공해야 하지만, 실시간 시스템의 개발자는 메모리 할당 시간의 최악수행시간을 예측하기 어렵기 때문에 동적 메모리 할당 알고리즘 사용을 피한다. 결국 실시간 시스템에서는 예측가능한 최악수행시간을 갖는 시간 결정적인 메모리 할당 알고리즘이 필요하다. 본 논문에서는 다차원 비트맵을 사용한 시간 결정적 메모리 할당 기법을 소개하고, 실험결과를 통해 기존 상용 실시간 운영체제에서 사용되고 있는 메모리 할당 알고리즘과 비교분석하여 본 논문에서 제시하는 메모리 할당 기법이 우수함을 보인다.
Abstract
In recent years, embedded systems such as Smart phones, Portable Multimedia Player, intelligent appliance, automobile engine control are reshaping the way people live, work, and play. Thereby, services application to guarantee various requirements of users become increasingly sophisticated and complicated, such embedded computing platforms use real-time operating systems(RTOSs) with time determinism. These RTOSs must provide predictable task scheduling and memory allocation services. However, developers of real-time systems avoid using dynamic memory allocation(DMA) algorithms because their worst-case execution time is hard to be bounded. Consequently, it is quite necessary to devise a deterministic DMA algorithm with a bounded worst-case performance. In this paper, we introduce a novel deterministic DMA algorithm for real-time systems using a multi-dimensional bit map method, and give some experimental results to show that it outperforms DMA algorithms of Commercial RTOSs.
참고문헌 (24)
- K. G. Shin, "Real-time computing: a new discipline of computer shtcience and engineering", Proc. of the IEEE, 82(1), pp.6~24 (1994)
- P. R.Wilson, "Dynamic Storage Allocation: A Survey and Critical", Proc. of the Int. Workshop on Memory Management, 986, pp.1~116 (1995)
- Emery D. Berger, "Composing high-performance memory allocators", SIGPLAN Conference on Programming Languare Desian and Implementation, pp.114~124 (2001)
- C.Bays, "A Comparizon of Next-fit, First-fit, and Best-fit", Communications ACM, 20(3), pp.191~192 (1977)
- N.Nielsen, "Dynamic Memory Allocation in Computer Simulation", Communications ACM, 20, pp.864~873 (1977)
- G.Bozman, "The Software Lookaside Buffer Reduces Search Overhed with Linked Lists", Communications ACM, 27(3), pp.222~227 (1984)
- R.P.Brent, "Efficient Implementation of A First-Fit Strategy for Dynamic Stroage Allocation", ACM Trans. Programmning Language and Systems, 11(3), pp.388~403 (1989)
- J. L. Peterson, "Buddy systems", Communications ACM, 20, pp.421~431 (1974)
- A.Kaufman, "Tailored-List and Recombination Delaying Byddy Systems", ACM Trans. Programmning Languages and Systems, 6(1), pp.118~125 (1984)
- B.Randell, "A Note on Stroage Fragmentation and Program Segmentation", Communications ACM, 12, pp.365~372 (1969)
- D. G. Korn, "In Search of a Better Malloc", Proceeding s of the summner USENIX Conference, pp.489~506 (1985)
- B. Z. Dirk Grunwald, "Improving the Cache Locality of Memory Allocation", SIGPLAN93 Conference on Programming Language Design and Implementation, pp.177~186 (1993)
- B. Zorn, "Evaluation Models of Memory Allocation", ACM Trans.Modeling and Computer Simulations, 4(1), pp.388~403 (1994)
- D. Detlefs, "Memory Allocation Costs in Large C and C++ Programs", Software Practive and Experience, 24(6), pp.527~542 (1994)
- C. B. Weinstock, "Quickfit: An efficient algorithm for heap storage allocation", ACM SIGPLANNotices, 141~144 (1988)
- A. Diwan, "Memory system performance of programs with intensive heap allocation", ACM Trans. on Computer Systems, 244~273 (1995)
- S. Edgar, "Statistical analysis of WCET for scheduling", Proceedings of the 22ndIEE Real-Time Systems Symposium, pp.215~224 (2001)
- E. L. Lloyd, "On the worst case performance of buddy systems", Acta Informatica, 451~473 (1985)
- M. Masmano, "TLSF:a New Dynamic Memory Allocator for Real-Time Systems", Proceedings of the Euromicro Conference on Real-Time Systems, pp.79~86 (2004)
- L. M. Thompson, "Using pSOS+ for embedded real-time computing", COMPCON, 282~288 (1990)
- D. Hildebrand, "An architectural overview of QNX", Proc. Usenix Workshop on Micro-Kernels and Other Kernel Architectures (1992)
- "VxWorks & pSOS"[URL]
- "Nucleus"[URL]
- Jean J. Labrosse, "C", OS: The Real-Time Kernel, 1993