theses

Public defence in computer and information science: Erik Österlund

Title: Going beyond on-the-fly garbage collection and improving self-adaption with enhanced interfaces
Subject: Computer and information science
Faculty: Faculty of technology
Date: Friday 18 October 2019 at 1.00 pm
Place: Room Weber, building K, Växjö
External reviewer: Professor Richard Jones, University of Kent, England
Examining committee: Professor Peter Fritzson, Linköping University, Sweden; professor Uwe Aßman, Technische Universität Dresden, Germany; professor Wolf Zimmermann, Martin-Luther-Universität Halle-Wittenberg, Germany
Chairperson: Senior lecturer Jesper Andersson, Department of computer science and media technology, Linnaeus University
Supervisor: Professor Welf Löwe, Department of computer science and media technology, Linnaeus University
Examiner: Professor Andreas Kerren, Department of computer science and media technology, Linnaeus University
Spikning: Friday 27 September 2019 at 9.30 am at the University library in Växjö

Abstract

Freeing memory of a lock-free data structure is tedious work. There are solutions, but they require lots of manual work and careful thinking. Automatic approaches like garbage collection are therefore desirable, but impede the progress guarantees of the algorithm.

Choosing the right data structure based on time complexity and varying levels of unexpected concurrency, in third party libraies, is also tedious work, and would also benefit from an automatic approach.

A block-free garbage collection (GC) algorithm was invented that automates concurrent memory reclamation, and concurrent memory defragmentation, without impeding the non-blocking progress guarantees of the algorithm. The algorithm builds on a tighter integration between GC and the operating system (OS) as well as just-in-time (JIT) compilers.

A general solution for creating self-adaptive components was created, allowing an automatic selection of appropriate underlying data structure based on operations performed and level of contention exposed to. The algorithm builds on a tighter integration between the library code and managed runtime.

It shows that these solutions benefit from a revision of the otherwise strict boundaries between the tasks of garbage collection, compilers, operating systems (OS), and runtime environment. These boundaries/interfaces are pragmatic engineering decisions that can be adapted for good engineering purposes.