Analysis of Disc Fragmentation Using Markov Chains

Clement H C LEUNG*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


The fragmented storage map is represented by a Markov model which incorporates correlation between locations not necessarily adjacent to one another. Formulae for the average access distance for contiguous and non-contiguous allocations are given. For large storage requirements, the performance penalty of the former can be substantially higher than that of the latter: they are shown to be O(k**n) and O(n), respectively, where n is the storage requirement and k greater than 1. The Markov model is also able to achieve close agreement with published measurements.

Original languageEnglish
Pages (from-to)113-116
Number of pages4
JournalComputer Journal
Issue number2
Publication statusPublished - 1983

Scopus Subject Areas

  • Computer Science(all)


Dive into the research topics of 'Analysis of Disc Fragmentation Using Markov Chains'. Together they form a unique fingerprint.

Cite this