Dynamic storage allocation with limited compaction - complexity and some practical implications

DOI10.1016/0166-218X(85)90046-0MaRDI QIDQ1058288zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jacek Blazewicz, Jerzy R. Nawrocki

Publication date 1985

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(85)90046-0

zbMATH Keywords

approximation algorithmscomplexity of algorithmscontiguous segmentsdynamic memory allocation

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Review text

In the paper, the problem of dynamic memory allocation with limited compaction of contiguous segments, is considered. The particular question to be solved is to find, given the storage state, a free storage space of a given size by reallocating segments whose total size is minimal. The general case of this problem is proved to be NP-hard. It is, however, possible to give a linear time algorithm for solving a restricted case, involving only a few types of segment sizes. Moreover, for the general case several bounds on the storage size ensuring the possibility of finding in linear time a free space of the desired size by reallocating not more than L memory cells, are presented.

Recommendations

• Insertion and Compaction Algorithms in Sequentially Allocated Storage
• scientific article; zbMATH DE number 4043214
• Approximation algorithms for dynamic storage allocation
• Algorithms for resolving conflicts in dynamic storage allocation
• A provably efficient algorithm for dynamic storage allocation

Cites work

• A Compaction Procedure for Variable-Length Storage Elements
• A note on compacting garbage collection
• A time- and space-efficient garbage compaction algorithm
• scientific article; zbMATH DE number 3483531 (Why is no real title available?)
• scientific article; zbMATH DE number 3483532 (Why is no real title available?)
• scientific article; zbMATH DE number 3488590 (Why is no real title available?)
• scientific article; zbMATH DE number 3633691 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)

Cited in

(16)

• A constant-time dynamic storage allocator for real-time systems
• Analysis of space allocation in a generally fragmented linear store
• Fixed-sized blocks optimization
• Finite-size scaling approach to dynamic storage allocation problem
• Space defragmentation for packing problems
• scientific article; zbMATH DE number 1003306 (Why is no real title available?)
• Maintaining Arrays of Contiguous Objects
• Insertion and Compaction Algorithms in Sequentially Allocated Storage
• Algorithms for resolving conflicts in dynamic storage allocation
• scientific article; zbMATH DE number 4043214 (Why is no real title available?)
• scientific article; zbMATH DE number 1305512 (Why is no real title available?)
• Embedded minimal disks: Proper versus nonproper—global versus local
• scientific article; zbMATH DE number 6399332 (Why is no real title available?)
• Space overhead bounds for dynamic memory management with partial compaction
• Dynamic storage allocation with known durations
• Reallocation problems in scheduling

This page was built for publication: Dynamic storage allocation with limited compaction - complexity and some practical implications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1058288)