Analysis of space allocation in a generally fragmented linear store
type: Item
instance of: scholarly article
title: Analysis of space allocation in a generally fragmented linear store
zbMATH Open document ID: 0608.68018
DOI: 10.1007/BF00290708
published in: Acta Informatica
publication date: 1987-01-01T00:00:00Z
review text: The space allocation process in a fragmented linear store with general fragmentation characteristics is analysed. For a given allocation requirement t, exact expression for the n-th moment of the allocation penalty for single block contiguous allocation is obtained, which for large t is shown to be \(O(\bar F(t)^{-n})\), where \(\bar F(\cdot)\) is the complementary distribution function of the free block sizes. For multiple block non-contiguous allocation, it is shown that the corresponding penalty can be approximated by an n-th degree polynomial and is \(O(t^ n)\) for large t. Compared with experimental values, the model results are able to achieve good agreement.
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 3984556
zbMATH Keywords: file management
zbMATH Keywords: performance analysis
zbMATH Keywords: storage fragmentation
author: Clement H. C. Leung
MaRDI profile type: Publication
cites work: Q5558293
cites work: Q5624436
cites work: Q5629004
cites work: Q4101255
cites work: Q3243274
full work available at URL: https://doi.org/10.1007/bf00290708
OpenAlex ID: W2016218270
Recommended article: A Stochastic Model of Fragmentation in Dynamic Storage Allocation
Recommended article: Approximation algorithms for dynamic storage allocation
Recommended article: Dynamic storage allocation with limited compaction - complexity and some practical implications
Recommended article: Q4035274
Recommended article: A provably efficient algorithm for dynamic storage allocation
Recommended article: A polynomial time approximation algorithm for dynamic storage allocation
Recommended article: Tight Bounds for Dynamic Storage Allocation
Recommended article: Q3128936
Recommended article: A simple direct solution to a storage allocation model
Recommended article: A constant factor approximation algorithm for the storage allocation problem
description: scientific article; zbMATH DE number 3984556