Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A correct and useful incremental copying garbage collector
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
2007 (English)In: Proceedings of the the 2007 International Symposium on Memory Management: Québec, Canada, October 21 - 22, 2007, New York: ACM Digital Library, 2007, 129-140 p.Conference paper, Published paper (Refereed)
Abstract [en]

Designing a garbage collector with real-time properties is a particularly difficult task, involving the construction of both an incremental run-time algorithm as well as methods enabling a priori reasoning about schedulability in two dimensions (time and memory usage in conjunction). In order to comply with such ambitious goals with any amount of formal rigor, a comprehensive understanding of the actual algorithm used is of course a fundamental requirement. In this paper we present a formal model of an incremental copying garbage collector, where each atomic increment is modeled as a transition between states of a heap process. Soundness of the algorithm is shown by proving that the garbage collecting heap process is weakly bisimilar to a non-collecting heap with infinite storage space. In addition, we show that our collector is both terminating and useful, in the sense that it actually recovers the unreachable parts of any given heap in a finite number of steps.

Place, publisher, year, edition, pages
New York: ACM Digital Library, 2007. 129-140 p.
National Category
Computer Sciences Embedded Systems
Research subject
Dependable Communication and Computation Systems; Embedded System
Identifiers
URN: urn:nbn:se:ltu:diva-39218DOI: 10.1145/1296907.1296924Local ID: dddc6810-546d-11dc-8e15-000ea68e967bISBN: 978-1-59593-893-0 (print)OAI: oai:DiVA.org:ltu-39218DiVA: diva2:1012727
Conference
International Symposium on Memory Management : 21/10/2007 - 22/10/2007
Note
Godkänd; 2007; 20070827 (keero)Available from: 2016-10-03 Created: 2016-10-03 Last updated: 2017-11-25Bibliographically approved

Open Access in DiVA

fulltext(287 kB)57 downloads
File information
File name FULLTEXT01.pdfFile size 287 kBChecksum SHA-512
a523b4ab62cd6fabaff27655134cc98f52ac21016dd1a1938018eda8c5c4fd937c6cc1e4eeb482ff528f50b0d2fdc5dbb9bf8ce14a561f22a93379053018725b
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Kero, MartinNordlander, JohanLindgren, Per
By organisation
Department of Computer Science, Electrical and Space EngineeringComputer ScienceEmbedded Internet Systems Lab
Computer SciencesEmbedded Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 57 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 112 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf