Real-time Garbage Collection in Software Development

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.

• Real-time Garbage Collection
• Software Development
• Memory Management
• Real-time Systems
• Performance Optimization

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.

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

Load More ...