Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Garbage collection for reactive real-time systems
Luleå tekniska universitet, Institutionen för system- och rymdteknik, Datavetenskap.
2010 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Predictable use of resources, such as processor time and memory, is a desirable property for virtually any computer system. In real-time computing, static predictability is of particular concern. A real-time system typically maintains an ongoing interaction with its environment, concurrently executing tasks at predefined intervals or as responses to sporadic external events. Its purpose is often safety-critical, where failures to meet deadlines may have severe consequences - even loss of life. The substantial body of research in real-time scheduling theory has demonstrated that a priori guarantees on schedulability are achievable. What is needed is some carefully chosen restrictions on how tasks may interact and what timing behavior external events may exhibit. Safe use of shared resources in real-time systems are enabled by protocols for preserving mutually exclusive access to critical sections, free of deadlocks and priority inversions. The ability to achieve a priori schedulability guarantees can be preserved by taking the imposed restrictions into account. Nonetheless, allowing real-time tasks to share heap allocated data has far more complex consequences than just being a schedulability issue concerning shared resources. In order to guarantee failure free operation, the system must be free of memory related errors, such as memory leaks and dangling pointers. It is well-known that garbage collection can solve these problems. However, incorporating a garbage collector in a real-time system imposes a set of other requirements related to schedulability. This includes provably safe upper-bounds on required execution time and memory of the garbage collector in the presence of concurrently executing tasks, as well as preserved ability to achieve static schedulability guarantees of the real-time tasks. The body of research work towards establishing a priori schedulability guarantees of garbage collected real-time systems has been growing for the past decade. However, most of the existing work lacks a clear identification of the parameters required for and their impact on establishing a provably safe upper-bound on garbage collection execution time. The lack thereof has often imposed overly simplistic models for the cost of garbage collection; and - probably even more alarming - tractability of finding safe bounds of the involved parameters has not been established. Furthermore, most existing approaches require specialized scheduling policies and schedulability tests, as well as intrusive restrictions on the task model.In this dissertation, we propose the following theses: (1) the key to successful realtime garbage collection is to preserve as much as possible of previous advances in realtime scheduling theory by imposing minimal restrictions on the task model, scheduler, and schedulability test; and (2) the keys to enabling a priori schedulability guarantees are clear identification and tractable analysis of the sources of execution time for the garbage collector. Proofs of our theses are based on the run-time behavior of the real-time programming language Timber and an incremental copying garbage collector running as the lowest priority (idle) process.We identify all parameters needed for establishing a safe and tight upper bound on execution time of our collector, where the major ones (not surprisingly for a copying collector) are related to the amount of live heap space. We present a novel technique for establishing safe upper bounds of live heap space parameters for real-time systems. We rely on existing techniques for finding safe upper-bounds of parameters related to heap allocation of each task. Finally, we present the garbage collection demand analysis, decoupled from the schedulability analysis used for the real-time tasks, which determines if our collector is schedulable in the system.

Ort, förlag, år, upplaga, sidor
Luleå: Luleå tekniska universitet, 2010. , s. 171
Serie
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
URN: urn:nbn:se:ltu:diva-16886Lokalt ID: 0764e640-c1a2-11df-a707-000ea68e967bISBN: 978-91-7439-144-2 (tryckt)OAI: oai:DiVA.org:ltu-16886DiVA, id: diva2:989873
Anmärkning

Godkänd; 2010; 20100916 (keero); DISPUTATION Ämnesområde: Datalogi/Computer Science Opponent: Associate Professor/Senior Lecturer Roger Henriksson, Lunds universitet Ordförande: Chaired Professor Per Lindgren, Luleå tekniska universitet Tid: Tisdag den 26 oktober 2010, kl 09.30 Plats: D770, Luleå tekniska universitet

Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-01-10Bibliografiskt granskad

Open Access i DiVA

fulltext(4882 kB)121 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 4882 kBChecksumma SHA-512
95ae517cd3d55767b6ffa1e1434c524870d2e8914bceb80697eb4079108831d775358976989c4b111461d97f952c9c17ccc804702eb0a1cf74770df728fa4848
Typ fulltextMimetyp application/pdf

Personposter BETA

Kero, Martin

Sök vidare i DiVA

Av författaren/redaktören
Kero, Martin
Av organisationen
Datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 121 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 267 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf