NDLI: Upper bound for defragmenting buddy heaps

Please wait, while we are loading the content...

Energy-efficient policies for embedded clusters

Software design patterns for TinyOS

ACME: adaptive compilation made efficient

System-wide compaction and specialization of the linux kernel

Static strands: safely collapsing dependence chains for increasing embedded power efficiency

Scalable precision cache analysis for preemptive scheduling

Syncopation: generational real-time garbage collection in the metronome

Compiling for memory emergency

Efficient application migration under compiler guidance

Preventing interrupt overload

Probabilistic source-level optimisation of embedded programs

A dictionary construction technique for code compression systems with echo instructions

Complementing software pipelining with software thread integration

A sample-based cache mapping scheme

Static determination of allocation rates to support real-time garbage collection

Upper bound for defragmenting buddy heaps

Composable code generation for distributed giotto

Nonintrusive precision instrumentation of microcontroller software

On the design of the local variable cache in a hardware translation-based java virtual machine

Cache aware optimization of stream programs

Generation of permutations for SIMD processors

WCRT analysis for a uniprocessor with a unified prioritized cache

Feedback EDF scheduling exploiting hardware-assisted asynchronous dynamic voltage scaling

An energy efficient garbage collector for java embedded devices

Transparent distribution of real-time components based on logical execution time

Upper bound for defragmenting buddy heaps

Content Provider	ACM Digital Library
Author	Defoe, Delvin C. Cholleti, Sharath R. Cytron, Ron K.
Abstract	Knuth's buddy system is an attractive algorithm for managing storage allocation, and it can be made to operate in real-time. At some point, storage-management systems must either over-provide storage or else confront the issue of defragmentation. Because storage conservation is important to embedded systems, we investigate the issue of defragmentation for heaps that are managed by the buddy system. In this paper, we present tight bounds for the amount of storage necessary to avoid defragmentation. These bounds turn out to be too high for embedded systems, so defragmentation becomes necessary.We then present an algorithm for defragmenting buddy heaps and present experiments from applying that algorithm to real and synthetic benchmarks. Our algorithm relocates less than twice the space relocated by an optimal algorithm to defragment the heap so as to respond to a single allocation request. Our experiments show our algorithm to be much more efficient than extant defragmentation algorithms.
Starting Page	222
Ending Page	229
Page Count	8
File Format	PDF
ISBN	1595930183
DOI	10.1145/1065910.1065942
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-06-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Defragmentation Memory management Buddy system Compaction Storage allocation
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Upper bound for defragmenting buddy heaps

Upper bound for defragmenting buddy heaps (2005).

Variations on the binary buddy system for dynamic memory management

Space overhead bounds for dynamic memory management with partial compaction

Fast Allocation and Deallocation with an Improved Buddy System (1999)

A weighted buddy method for dynamic storage allocation

Fast allocation and deallocation with an improved buddy system (2005)

Space overhead bounds for dynamic memory management with partial compaction

Fast Allocation and Deallocation with an Improved Buddy System (1999)

Upper bound for defragmenting buddy heaps

Similar Documents

Upper bound for defragmenting buddy heaps

Upper bound for defragmenting buddy heaps (2005).

Variations on the binary buddy system for dynamic memory management

Space overhead bounds for dynamic memory management with partial compaction

Fast Allocation and Deallocation with an Improved Buddy System (1999)

A weighted buddy method for dynamic storage allocation

Fast allocation and deallocation with an improved buddy system (2005)

Space overhead bounds for dynamic memory management with partial compaction

Fast Allocation and Deallocation with an Improved Buddy System (1999)

Upper bound for defragmenting buddy heaps