Language-level Guarantees and Region Serializability

This study delves into the concepts of language-level guarantees for programs with races and and region serializability for all. It explores the potential optimizations and the reduction in possible program behaviors offered by these guarantees. The research delves into the implications of DRF0, SC, RS, and other order guarantees in ensuring the correctness of concurrent programs.

• Guarantees
• Serializability
• Optimizations
• Concurrent Programming
• Program Behaviors

sely Follow

Uploaded on Feb 22, 2025 | 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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

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.

Presentation Transcript

1. and region serializability for all JESSICA OUYANG, PETER CHEN, JASON FLINN & SATISH NARAYANASAMY UNIVERSITY OF MICHIGAN

2. Language-level guarantees for programs with races More potential optimizations Fewer possible program behaviors DRF0 DRF0 SC SC RS RS No Global, serial order of all instructions Global, serial order of regions regions guarantees 2

3. a = 0 b = 0 lock(B) ... lock(A) lock(A) a = 1 a = a + 1 unlock(A) b = a unlock(A) ... unlock(B) 3 JESSICA OUYANG

4. a = 0 b = 0 lock(B) ... lock(A) lock(A) a = 1 a = a + 1 unlock(A) b = a unlock(A) ... unlock(B) 4 JESSICA OUYANG

5. a = 0 b = 0 lock(B) ... lock(A) lock(A) a = 1 a = a + 1 unlock(A) b = a unlock(A) ... unlock(B) 5 JESSICA OUYANG

6. a = 0 b = 0 lock(B) ... lock(A) lock(A) a = 1 a = a + 1 unlock(A) b = a unlock(A) ... unlock(B) 6 JESSICA OUYANG

7. a = 0 b = 0 lock(B) ... lock(A) lock(A) a = 1 a = a + 1 unlock(A) b = a unlock(A) ... unlock(B) 7 JESSICA OUYANG

8. a = 0 b = 0 lock(B) ... lock(A) a = 1 a = a + 1 unlock(A) b = a ... unlock(B) 8 JESSICA OUYANG

9. a = 0 b = 0 lock(B) ... lock(A) a = 1 a = a + 1 unlock(A) b = a ... unlock(B) 9 JESSICA OUYANG

10. a = 0 b = 0 lock(B) ... lock(A) a = 1 a = a + 1 unlock(A) b = a ... unlock(B) 10 JESSICA OUYANG

11. CPU 1 CPU 2 lock(A) lock(B) a = 1 ... unlock(A) a = a + 1 b = a ... unlock(B) time 11 JESSICA OUYANG

12. CPU 1 CPU 2 lock(A) lock(B) a = 1 ... unlock(A) a = a + 1 b = a ... unlock(B) time 12 JESSICA OUYANG

13. CPU 1 CPU 2 lock(A) lock(B) a = 1 ... unlock(A) a = a + 1 b = a ... unlock(B) time 13 JESSICA OUYANG

14. CPU 1 CPU 2 lock(A) lock(B) a = 1 ... unlock(A) a =NaN b =yourPassword ... unlock(B) time 14 JESSICA OUYANG

15. 15 JESSICA OUYANG

16. 16 JESSICA OUYANG

17. 17 JESSICA OUYANG

18. 18 JESSICA OUYANG

19. a = 0 b = 0 lock(B) ... lock(A) a = 1 a = a + 1 unlock(A) b = a ... unlock(B) 19 JESSICA OUYANG

20. a = 0 b = 0 lock(B) ... lock(A) a = 1 a = a + 1 unlock(A) b = a ... unlock(B) 20 JESSICA OUYANG

21. Region serializability for all programs Guarantees Atomic synchronization-free regions Global, serial order of all regions Benefits Easy for programmers & tools to reason about Compilers can reorder freely within regions 21 JESSICA OUYANG

22. How to provide region serializability Compiler Preserve regions from source code Runtime Run one thread at a time Only preempt at synchronization boundaries 22 JESSICA OUYANG

23. CPU 1 CPU 2 CPU 3 CPU 4 lock(A) lock(B) lock(A) a = 1 ... a = 1 unlock(A) unlock(A) a = a + 1 lock(B) a:1 b = a ... ... a = a + 1 unlock(B) b = a ... unlock(B) time 23 JESSICA OUYANG

24. CPU 1 CPU 2 CPU 3 CPU 4 E0 E0 time 24 JESSICA OUYANG

25. CPU 1 CPU 2 CPU 3 CPU 4 Thread-parallel execution Epoch- parallel execution time 25 JESSICA OUYANG

26. Uniparallel execution [Veeraraghavan 11] E0 E0 E1 E1 E1 E2 ==? ==? != != E3 E3 1. Checkpoint state E2 E2 2. Start epoch 3. Check state 4. Roll back & Re-execute E3 time E3 E3 26 JESSICA OUYANG

27. 27 JESSICA OUYANG

28. 28 JESSICA OUYANG

29. Conclusion Strong guarantees for all programs Region serializability One way of providing region serializability Uniparallelism 29 JESSICA OUYANG