Real-time Garbage Collection in Software Development

Slide Note
Embed
Share

Real-time Garbage Collection (RTGC) is a crucial aspect of ensuring efficient software performance in time-constrained environments. This practice, exemplified by Boris Dogadov in a presentation, involves managing memory allocation and deallocation dynamically during program execution. The process addresses challenges like bounding mutator and collector times, along with space constraints, to maintain system responsiveness. RTGC is vital in real-time systems with strict deadline requirements for processing external input stimuli. The implementation of RTGC is not a myth; it has been seen in various technologies like .NET Micro Framework, Java Platform, and more. Understanding the significance of RTGC and its impact on software development is essential for optimizing performance and maintaining quality of service.

enae
enae Follow

Uploaded on Oct 07, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

  1. Real-time Garbage Collection Presented by Boris Dogadov 20/01/15 1

  2. Roadmap What is Real-time Garbage Collection (RTGC) Work-based Time-based Slack-based Tax and Spend Summery and Conclusion 2

  3. Is it real? ?How is real-time gc possible in production software? ?Why use gc language in the real-time software? ?What does real-time gc even mean? What is Real-time Garbage Collection (RTGC) 3

  4. It is not a myth! .NET Micro Framework Java Platform, Micro Edition Wi-Fi coffee maker Java-based Synthesizer JAviator (w/ Salzburg) NetDuino Arm What is Real-time Garbage Collection (RTGC) 4

  5. Real-time systems Introduce constrains on response time, to defined events. Any information processing system which has to respond to externally generated input stimuli within a finite and specified period Hard Deadline misses results in total failures Firm Infrequent deadline misses are tolerable (results are useless) Soft Deadline misses degrade QoS (results usefulness degrades with time) What is Real-time Garbage Collection (RTGC) 5

  6. Real-time Garbage Collection Challenges Bounding the Mutator time (minimum application time slack) Bounding the Collector time (maximum pause time) Space constrains What is Real-time Garbage Collection (RTGC) 6

  7. Roadmap What is Real-time Garbage Collection (RTGC) Work-based real-time collection Time-based Slack-based Tax and Spend Summery and Conclusion 7

  8. Copying GC - Reminder From Space To Space A B C A C Roots D E Work-based real-time collection 8

  9. Work based GC - Baker Baker (1978) Classic copying GC Introduces space and time bounds analysis Given fixed size objects The bounds are very impractical Work-based real-time collection 9

  10. Real time GC Properties The most common parameter for RT-GC was application Pause Time For example 100ms pause time is not suitable for applications with 50ms response time This is not enough, why? Work-based real-time collection 10

  11. Real time GC Properties Most common parameter for RT-GC was application Pause Time For example 100ms pause time is not suitable for applications with 50ms response time Work-based real-time collection 11

  12. Real time GC Properties Most common parameter for RT-GC was application Pause Time For example 100ms pause time is not suitable for applications with 50ms response time This is not enough, why? Very frequent short pauses not different from one long pause Work-based real-time collection 12

  13. Blelloch and Cheng Luckily of all of us, Blelloch and Cheng first introduce a new term Minimum mutator utilization (2001) Work-based real-time collection 13

  14. Blelloch and Cheng Luckily of all of us, Blelloch and Cheng first introduce a new term Minimum mutator utilization (2001) At any time window (up to some granularity t), portion of mutator work has a low- bound t is the pause time Work-based real-time collection 14

  15. Blelloch and Cheng Luckily of all of us, Blelloch and Cheng first introduce a new term Minimum mutator utilization (2001) At any time window (up to some granularity t), portion of mutator work has a low- bound t is the pause time Example Mouse tracking requires response time of 50ms Mouse tracking handling code requires 1ms Sufficient to have minimum utilization time of 2% at granularity of 50ms Work-based real-time collection 15

  16. Blelloch and Cheng Assumptions Memory accesses are sequentially consistent Work-based real-time collection 16

  17. Blelloch and Cheng Assumptions Memory accesses are sequentially consistent Every New (with n fields) is followed by n Invocations of InitSlot() Work-based real-time collection 17

  18. Blelloch and Cheng Assumptions Memory accesses are sequentially consistent Every New (with n fields) is followed by n Invocations of InitSlot() Object cannot be used before all InitSlot() were completed Work-based real-time collection 18

  19. Blelloch and Cheng Assumptions Memory accesses are sequentially consistent Every New (with n fields) is followed by n Invocations of InitSlot() Object cannot be used before all InitSlot() were completed New() cannot interfere with other New() Work-based real-time collection 19

  20. Blelloch and Cheng Assumptions Memory accesses are sequentially consistent Every New (with n fields) is followed by n Invocations of InitSlot() Object cannot be used before all InitSlot() were completed New() cannot interfere with other New() Read/Write can interfere with New Work-based real-time collection 20

  21. Blelloch and Cheng Assumptions Memory accesses are sequentially consistent Every New (with n fields) is followed by n Invocations of InitSlot() Object cannot be used before all InitSlot() were completed New() cannot interfere with other New() Read/Write can interfere with New Writes are atomic Work-based real-time collection 21

  22. Blelloch and Cheng fromBot fromTop From Space copy stack free To Space allocated toTop toBot sharedStack free Work-based real-time collection 22

  23. Mutator: Allocate(n) public void Allocate(n) { ref = FetchAndAdd(&free, n) if (ref + n > sharedStack) if (gcOn) error "Out of memory" Interrupt(collectionOn) Allocate(n) return ref } fromBot fromTop copy stack free allocated toTop toBot sharedStack free Work-based real-time collection 23

  24. Mutator: Allocate(n) public void Allocate(n) { ref = FetchAndAdd(&free, n) if (ref + n > sharedStack) if (gcOn) error "Out of memory" Interrupt(collectionOn) Allocate(n) return ref } fromBot fromTop copy stack free allocated toTop sharedStack toBot free Work-based real-time collection 24

  25. Mutator: Allocate(n) public void Allocate(n) { ref = FetchAndAdd(&free, n) if (ref + n > sharedStack) if (gcOn) error "Out of memory" Interrupt(collectionOn) Allocate(n) return ref } fromBot fromTop copy stack free allocated toTop sharedStack toBot free Work-based real-time collection 25

  26. Mutator: New(n) pointer lastA int lastL int lastC From Space To Space public void New(n) { p = Allocate(n) /* allocate primary */ r = Allocate(n) /* allocate replica */ ForwadingAddress(p) = r /* primary forwards to replica */ CopyCount(r) = 0 /* replica has no slots to copy */ lastA = p /* set last allocated */ lastC = 0 /* set count */ lastL = n /* set set length */ return p } Work-based real-time collection 26

  27. Mutator: New(n) pointer lastA int lastL int lastC From Space To Space public void New(n) { p = Allocate(n) /* allocate primary */ r = Allocate(n) /* allocate replica */ ForwadingAddress(p) = r /* primary forwards to replica */ CopyCount(r) = 0 /* replica has no slots to copy */ lastA = p /* set last allocated */ lastC = 0 /* set count */ lastL = n /* set set length */ return p } FA = null null null null null Work-based real-time collection 27

  28. Mutator: New(n) pointer lastA int lastL int lastC From Space To Space public void New(n) { p = Allocate(n) /* allocate primary */ r = Allocate(n) /* allocate replica */ ForwadingAddress(p) = r /* primary forwards to replica */ CopyCount(r) = 0 /* replica has no slots to copy */ lastA = p /* set last allocated */ lastC = 0 /* set count */ lastL = n /* set set length */ return p } FA = null CopyCount null null null null null null null null Work-based real-time collection 28

  29. Mutator: New(n) pointer lastA int lastL int lastC From Space To Space public void New(n) { p = Allocate(n) /* allocate primary */ r = Allocate(n) /* allocate replica */ ForwadingAddress(p) = r /* primary forwards to replica */ CopyCount(r) = 0 /* replica has no slots to copy */ lastA = p /* set last allocated */ lastC = 0 /* set count */ lastL = n /* set set length */ return p } FA = r CopyCount null null null null null null null null Work-based real-time collection 29

  30. Mutator: New(n) pointer lastA int lastL int lastC From Space To Space public void New(n) { p = Allocate(n) /* allocate primary */ r = Allocate(n) /* allocate replica */ ForwadingAddress(p) = r /* primary forwards to replica */ CopyCount(r) = 0 /* replica has no slots to copy */ lastA = p /* set last allocated */ lastC = 0 /* set count */ lastL = n /* set set length */ return p } FA = r CopyCount = 0 null null null null null null null null Work-based real-time collection 30

  31. Mutator: InitSlot(v) From Space To Space pointer lastA int lastL int lastC FA = r CopyCount = 0 null null public void InitSlot(v) { lastA[lastC] = v if isPointer(lastA, lastC) v = makeGrey(v) ForwadingAddress(lastA)[lastC++] = v Collect(k) } null null null null null null v Work-based real-time collection 31

  32. Mutator: InitSlot(v) From Space To Space pointer lastA int lastL int lastC FA = r CopyCount = 0 v null public void InitSlot(v) { lastA[lastC] = v if isPointer(lastA, lastC) v = makeGrey(v) ForwadingAddress(lastA)[lastC++] = v Collect(k) } null null null null null null v Work-based real-time collection 32

  33. Mutator: InitSlot(v) From Space To Space pointer lastA int lastL int lastC FA = r CopyCount = 0 v null public void InitSlot(v) { lastA[lastC] = v if isPointer(lastA, lastC) v = makeGrey(v) ForwadingAddress(lastA)[lastC++] = v Collect(k) } null null null null null null v v Work-based real-time collection 33

  34. Mutator: InitSlot(v) From Space To Space pointer lastA int lastL int lastC FA = r CopyCount = 0 v v public void InitSlot(v) { lastA[lastC] = v if isPointer(lastA, lastC) v = makeGrey(v) ForwadingAddress(lastA)[lastC++] = v Collect(k) } null null null null null null v v Work-based real-time collection 34

  35. Mutator: MakeGray From Space To Space public void* MakeGray(p) { if (TestAndSet(&ForwadingAddress(p)) != 0) { /* We lost the race */ while (ForwadingAddress(p == 1) {} } else { /* We won the race */ count = length(p) replica = Allocate(count) CopyCount(replica) = count ForwadingAddress(p) = replica localPush(p) } return ForwadingAddress(p); } FA = null X Y Z X Y Z Item1 Item2 Work Stack Work-based real-time collection 35

  36. Mutator: MakeGray From Space To Space public void* MakeGray(p) { if (TestAndSet(&ForwadingAddress(p)) != 0) { /* We lost the race */ while (ForwadingAddress(p == 1) {} } else { /* We won the race */ count = length(p) replica = Allocate(count) CopyCount(replica) = count ForwadingAddress(p) = replica localPush(p) } return ForwadingAddress(p); } FA = null TAS X Y Z X Y Z Item1 Item2 Work Stack Work-based real-time collection 36

  37. Mutator: MakeGray From Space To Space public void* MakeGray(p) { if (TestAndSet(&ForwadingAddress(p)) != 0) { /* We lost the race */ while (ForwadingAddress(p == 1) {} } else { /* We won the race */ count = length(p) replica = Allocate(count) CopyCount(replica) = count ForwadingAddress(p) = replica localPush(p) } return ForwadingAddress(p); } FA = null TAS X Y Z X Y Z Item1 Item2 Work Stack Work-based real-time collection 37

  38. Mutator: MakeGray From Space To Space public void* MakeGray(p) { if (TestAndSet(&ForwadingAddress(p)) != 0) { /* We lost the race */ while (ForwadingAddress(p == 1) {} } else { /* We won the race */ count = length(p) replica = Allocate(count) CopyCount(replica) = count ForwadingAddress(p) = replica localPush(p) } return ForwadingAddress(p); } CopyCount = 0 FA = null null X null Y null Z X Y Z Item1 Item2 Work Stack Work-based real-time collection 38

  39. Mutator: MakeGray From Space To Space public void* MakeGray(p) { if (TestAndSet(&ForwadingAddress(p)) != 0) { /* We lost the race */ while (ForwadingAddress(p == 1) {} } else { /* We won the race */ count = length(p) replica = Allocate(count) CopyCount(replica) = count ForwadingAddress(p) = replica localPush(p) } return ForwadingAddress(p); } CopyCount = 3 FA = null null X null Y null Z X Y Z Item1 Item2 Work Stack Work-based real-time collection 39

  40. Mutator: MakeGray From Space To Space public void* MakeGray(p) { if (TestAndSet(&ForwadingAddress(p)) != 0) { /* We lost the race */ while (ForwadingAddress(p == 1) {} } else { /* We won the race */ count = length(p) replica = Allocate(count) CopyCount(replica) = count ForwadingAddress(p) = replica localPush(p) } return ForwadingAddress(p); } CopyCount = 3 FA = r null X null Y null Z X Y Z Item1 Item2 Work Stack Work-based real-time collection 40

  41. Mutator: MakeGray From Space To Space public void* MakeGray(p) { if (TestAndSet(&ForwadingAddress(p)) != 0) { /* We lost the race */ while (ForwadingAddress(p == 1) {} } else { /* We won the race */ count = length(p) replica = Allocate(count) CopyCount(replica) = count ForwadingAddress(p) = replica localPush(p) } return ForwadingAddress(p); } CopyCount = 3 FA = r null X null Y null Z X Y Z Item1 P Item2 Work Stack Work-based real-time collection 41

  42. Mutator: CopyOneSlot(p) From Space To Space public void CopyOneSlot(p) { replica = ForwadingAddress(p) slotIndex = CopyCount(replica) - 1 CopyCount(replica) = -(slotIndex + 1) v = p[slotIndex] if isPointer(p, slotIndex) v = MakeGrey(v) replica[slotIndex] = v CopyCount(replica) = slotIndex if (slotIndex > 0) LocalPush(p) } CopyCount = 3 FA = r null X null Y null Z X Y Z Item1 Item2 Work Stack P Work-based real-time collection 42

  43. Mutator: CopyOneSlot(p) From Space To Space public void CopyOneSlot(p) { replica = ForwadingAddress(p) slotIndex = CopyCount(replica) - 1 CopyCount(replica) = -(slotIndex + 1) v = p[slotIndex] if isPointer(p, slotIndex) v = MakeGrey(v) replica[slotIndex] = v CopyCount(replica) = slotIndex if (slotIndex > 0) LocalPush(p) } CopyCount = -3 FA = r 3 null X null Y null Z X Y Z Item1 Item2 Work Stack P Work-based real-time collection 43

  44. Mutator: CopyOneSlot(p) From Space To Space public void CopyOneSlot(p) { replica = ForwadingAddress(p) slotIndex = CopyCount(replica) - 1 CopyCount(replica) = -(slotIndex + 1) v = p[slotIndex] if isPointer(p, slotIndex) v = MakeGrey(v) replica[slotIndex] = v CopyCount(replica) = slotIndex if (slotIndex > 0) LocalPush(p) } CopyCount = -3 FA = r 2 null X -3 z null Y null Z X Y Z Item1 Item2 Work Stack P Work-based real-time collection 44

  45. Mutator: CopyOneSlot(p) From Space To Space public void CopyOneSlot(p) { replica = ForwadingAddress(p) slotIndex = CopyCount(replica) - 1 CopyCount(replica) = -(slotIndex + 1) v = p[slotIndex] if isPointer(p, slotIndex) v = MakeGrey(v) replica[slotIndex] = v CopyCount(replica) = slotIndex if (slotIndex > 0) LocalPush(p) } CopyCount = -3 FA = r 2 null X -3 z null Y null Z Z X Y Z Item1 Item2 Work Stack P Work-based real-time collection 45

  46. Mutator: CopyOneSlot(p) From Space To Space public void CopyOneSlot(p) { replica = ForwadingAddress(p) slotIndex = CopyCount(replica) - 1 CopyCount(replica) = -(slotIndex + 1) v = p[slotIndex] if isPointer(p, slotIndex) v = MakeGrey(v) replica[slotIndex] = v CopyCount(replica) = slotIndex if (slotIndex > 0) LocalPush(p) } CopyCount = -3 FA = r 2 null X -3 z null Y Z Z Z X Y Z Item1 Item2 Work Stack P Work-based real-time collection 46

  47. Mutator: CopyOneSlot(p) From Space To Space public void CopyOneSlot(p) { replica = ForwadingAddress(p) slotIndex = CopyCount(replica) - 1 CopyCount(replica) = -(slotIndex + 1) v = p[slotIndex] if isPointer(p, slotIndex) v = MakeGrey(v) replica[slotIndex] = v CopyCount(replica) = slotIndex if (slotIndex > 0) LocalPush(p) } CopyCount = 2 FA = r 2 null X -3 z null Y Z Z Z X Y Z Item1 Item2 2 Work Stack P Work-based real-time collection 47

  48. Mutator: CopyOneSlot(p) From Space To Space public void CopyOneSlot(p) { replica = ForwadingAddress(p) slotIndex = CopyCount(replica) - 1 CopyCount(replica) = -(slotIndex + 1) v = p[slotIndex] if isPointer(p, slotIndex) v = MakeGrey(v) replica[slotIndex] = v CopyCount(replica) = slotIndex if (slotIndex > 0) LocalPush(p) } CopyCount = 2 FA = r 2 null X -3 z null Y Z Z Z X Y Z P Item1 Item2 2 2 Work Stack Work-based real-time collection 48

  49. Mutator: Write (GC is on) From Space To Space atomic void Write(p, i, v) { if isPointer(p, i) makeGrey(p[i]) p[i] = v if (ForwadingAddress(p) != 0) { while ForwadingAddress(p) == 1 {} replica = ForwadingAddress(p) while (CopyCount(replica) == -(i + 1) {} if isPointer(p, i) makeGrey(v) replica[i] = v } Collect(k) } CopyCount = 3 FA = r null X null Y null Z X Y Z V Item1 Item2 Work Stack Work-based real-time collection 49

  50. Mutator: Write (GC is on) From Space To Space atomic void Write(p, i, v) { if isPointer(p, i) makeGrey(p[i]) p[i] = v if (ForwadingAddress(p) != 0) { while ForwadingAddress(p) == 1 {} replica = ForwadingAddress(p) while (CopyCount(replica) == -(i + 1) {} if isPointer(p, i) makeGrey(v) replica[i] = v } Collect(k) } CopyCount = 3 FA = r null X null Y null Z Y X Y Z V Item1 Item2 Work Stack Work-based real-time collection 50

Related


Understanding Garbage Collection in Programming

Understanding Garbage Collection in Programming

jan_cuy
Managing Garbage: A Comprehensive Overview for Class 6 Science

Managing Garbage: A Comprehensive Overview for Class 6 Science

danica
Study of Garbage Collector Scalability on Multicores

Study of Garbage Collector Scalability on Multicores

ctan
Understanding Garbage Collection in VB.net

Understanding Garbage Collection in VB.net

evren
Impact of Data Locality on Garbage Collection in SSDs: A General Analytical Study

Impact of Data Locality on Garbage Collection in SSDs: A General Analytical Study

aubr_893
Understanding Garbage Collection in Java Programming

Understanding Garbage Collection in Java Programming

elva
The Great Pacific Garbage Patch - A Looming Environmental Crisis

The Great Pacific Garbage Patch - A Looming Environmental Crisis

solange
Improving Big Data Performance with Yak: A Hybrid Garbage Collector

Improving Big Data Performance with Yak: A Hybrid Garbage Collector

rroge
Reflecting on a Unique Garbage Tennis Activity

Reflecting on a Unique Garbage Tennis Activity

sugg_lah
Understanding the Essence of Software Development Process

Understanding the Essence of Software Development Process

katiely
Reviving Reference Counting: A Comprehensive Analysis

Reviving Reference Counting: A Comprehensive Analysis

farquhar_j
Comparison of Reference Counting vs. Tracing Garbage Collection Algorithms

Comparison of Reference Counting vs. Tracing Garbage Collection Algorithms

liv_pe
Understanding Software Processes and Models

Understanding Software Processes and Models

fatima
Software Cost Estimation in Software Engineering

Software Cost Estimation in Software Engineering

aislinn
Understanding Software Engineering and Development Processes

Understanding Software Engineering and Development Processes

benici
Understanding Software Measurement and Metrics in Software Engineering

Understanding Software Measurement and Metrics in Software Engineering

asmodeus
Insights from NATO Software Engineering Conferences and The Software Crisis of the Seventies

Insights from NATO Software Engineering Conferences and The Software Crisis of the Seventies

kush_51
Understanding Real-Time Systems and Operating Systems

Understanding Real-Time Systems and Operating Systems

liel
Comprehensive Guide to Data Cleaning and Preprocessing Techniques

Comprehensive Guide to Data Cleaning and Preprocessing Techniques

paris
Object-Oriented Programming Details: References, Overloaded Methods, and Garbage Collector

Object-Oriented Programming Details: References, Overloaded Methods, and Garbage Collector

talianal
Introduction to Real-Time Systems and Real-Time OSes

Introduction to Real-Time Systems and Real-Time OSes

azami
Challenges in Software Development: Understanding the Complexity

Challenges in Software Development: Understanding the Complexity

kyria
Understanding Software Engineering: Concepts and Characteristics

Understanding Software Engineering: Concepts and Characteristics

elle
Understanding Software Engineering: An Overview by Lecturer Sebastian Coope

Understanding Software Engineering: An Overview by Lecturer Sebastian Coope

yan_bra

More Related Content