Download Systematic Concurrency Testing using CHESS PowerPoint Presentation

Iframe embed code :

Unable to generate embed code for this presentation.request for embed code @ mail[at]slidesfinder.com

Presentation url :

Home / Sports & Recreation / Sports & Recreation Presentations / Systematic Concurrency Testing using CHESS PowerPoint Presentation

Systematic Concurrency Testing using CHESS PowerPoint Presentation

PowerPoint is the world's most popular presentation software which can let you create professional Systematic Concurrency Testing using CHESS powerpoint presentation easily and in no time. This helps you give your presentation on Systematic Concurrency Testing using CHESS in a conference, a school lecture, a business proposal, in a webinar and business and professional representations.

The uploader spent his/her valuable time to create this Systematic Concurrency Testing using CHESS powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by onlinesearch in Sports & Recreation ppt presentation category is available for free download,and can be used according to your industries like finance, marketing, education, health and many more.

About This Presentation

onlinesearch

Description : Available Systematic Concurrency Testing using CHESS powerpoint presentation for free download which is uploaded by search an active user in belonging ppt presentation Sports & Recreation category.

Tags : Systematic Concurrency Testing using CHESS

Published on : Feb 10, 2014
Views : 1685 | Downloads : 1

Download Now

Share on Social Media

Slide 1 -

CHESS: Systematic Concurrency Testing Tom Ball, Sebastian Burckhardt, Madan Musuvathi, Shaz Qadeer Microsoft Research http://research.microsoft.com/CHESS/

Slide 2 -

Testing concurrent programs is HARD Rare thread interleavings expose bugs Coverage problem Testing misses thread interleavings that expose errors Reproducibility problem Concurrency bugs == Heisenbugs Not reproducible  hard to debug Crash dumps don’t help

Slide 3 -

Thread interleavings x++; x++; x*=2; x*=2; 4 1 0 2 8 4 3 2 5 6 Thread 1 Thread 2 1 0 0 2 2 2 1 4 3

Slide 4 -

Concurrency testing today Concurrency testing == stress testing Example: testing a concurrent queue Create 100 threads performing queue operations Run for days/weeks Stress increases the interleaving variety, but Not systematic: might miss interleavings Not predictable: cannot find the same error again Makes any error found hard to debug

Slide 5 -

1 Why stress is not sufficient

Slide 6 -

Concurrency testing : what we need Methodology and tools to systematically and predictably test thread interleavings

Slide 7 -

CHESS in a nutshell Replace the OS scheduler with a demonic scheduler Systematically explore all scheduling choices ConcurrentProgram Win32 API Kernel Scheduler Demonic Scheduler

Slide 8 -

CHESS will run this program 6 times exploring all the different interleavings x++; x++; x*=2; x*=2; 4 1 0 2 8 4 3 2 5 6 Thread 1 Thread 2 1 0 0 2 2 2 1 4 3

Slide 9 -

2 Don’t stress, use CHESS

Slide 10 -

CHESS architecture Kernel: Threads, Scheduler, Synchronization Objects While(not done) { TestScenario() } TestScenario() { … } Program CHESS CHESS runs the scenario in a loop Every run takes a different interleaving Every run is repeatable Win32 API Intercept synch. & threading calls To control and introduce nondeterminism Detect Assertion violations Deadlocks Dataraces Livelocks

Slide 11 -

CHESS methodology generalizes Need wrappers for every concurrency API CHESS has wrappers for Win32, .NET, Singularity Wrappers understand the semantics of the API Expose nondeterminism in the API Looking for volunteers to build wrappers for Linux and Java

Slide 12 -

CHESS clients PCP = Parallel Computing Platform (for multi/many-cores) PLINQ: Parallel LINQ CDS: Concurrent Data Structures STM: Software Transactional Memory TPL: Task Parallel Library ConcRT: Concurrency RunTime CCR: Concurrency Coordination Runtime Dryad Part of COSMOS Singularity/Midori CHESS can systematically test the boot and shutdown process

Slide 13 -

Stateless model checking [Verisoft ‘97] Systematically enumerate all paths in a state-space graph Don’t capture program states Capturing states is extremely hard for large programs Effective for message-passing programs CHESS applies stateless model checking for shared-memory multithreaded programs

Slide 14 -

Outline Preemption bounding [PLDI ‘07] Fair stateless model checking [PLDI ‘08] Sober [CAV ’08, EC2 ‘08] FeatherLite Concurrency Explorer [EC2 ‘08]

Slide 15 -

Outline Preemption bounding Makes CHESS effective on deep state spaces Fair stateless model checking Sober FeatherLite Concurrency Explorer

Slide 16 -

x = 1; … … … … … y = k; State space explosion Thread 1 Thread n x = 1; … … … … … y = k; … n threads k steps each Number of executions = O( nnk ) Exponential in both n and k Typically: n < 10 k > 100 Limits scalability to large programs Goal: Scale CHESS to large programs (large k)

Slide 17 -

x = 1; if (p != 0) { x = p->f; } Preemption bounding Prioritize executions with small number of preemptions Two kinds of context switches: Preemptions – forced by the scheduler e.g. Time-slice expiration Non-preemptions – a thread voluntarily yields e.g. Blocking on an unavailable lock, thread end x = p->f; } x = 1; if (p != 0) { p = 0; Thread 1 Thread 2 preemption non-preemption

Slide 18 -

Polynomial state space Terminating program with fixed inputs and deterministic threads n threads, k steps each, c preemptions Number of executions <= nkCc . (n+c)! = O( (n2k)c. n! ) Exponential in n and c, but not in k x = 1; … … … … … y = k; x = 1; … … … … … y = k; Thread 1 Thread 2 x = 1; … … … … x = 1; … … … … y = k; … … y = k; Choose c preemption points Permute n+c atomic blocks

Slide 19 -

3 Preemption bounding

Slide 20 -

Find lots of bugs with 2 preemptions Acknowledgement: testers from PCP team

Slide 21 -

So, is CHESS is unsound? Soundness: prove that the program is correct for a given input test harness Need to exhaustively explore all interleavings For small programs, CHESS is sound Iteratively increase the preemption bound Preemption bounding helps scale to large programs A good “knob” to trade resources for coverage Better search algorithms  more coverage faster Partial-order reduction Modular testing of loosely-coupled programs

Slide 22 -

Slide 23 -

Concurrent programs have cyclic state spaces Spinlocks Non-blocking algorithms Implementations of synchronization primitives Periodic timers … L1: while( ! done) { L2: Sleep(); } M1: done = 1; Thread 1 Thread 2 ! done L2 ! done L1 done L2 done L1

Slide 24 -

A demonic scheduler unrolls any cycle ad-infinitum ! done done ! done done ! done done while( ! done) { Sleep(); } done = 1; Thread 1 Thread 2 ! done

Slide 25 -

Depth bounding ! done done ! done done ! done done ! done Prune executions beyond a bounded number of steps Depth bound

Slide 26 -

Problem 1: Ineffective state coverage ! done ! done ! done ! done Bound has to be large enough to reach the deepest bug Typically, greater than 100 synchronization operations Every unrolling of a cycle redundantly explores reachable state space Depth bound

Slide 27 -

Problem 2: Cannot find livelocks Livelocks : lack of progress in a program temp = done; while( ! temp) { Sleep(); } done = 1; Thread 1 Thread 2

Slide 28 -

Key idea This test terminates only when the scheduler is fair Fairness is assumed by programmers All cycles in correct programs are unfair A fair cycle is a livelock while( ! done) { Sleep(); } done = 1; Thread 1 Thread 2 ! done ! done done done

Slide 29 -

We need a fair demonic scheduler Avoid unrolling unfair cycles Effective state coverage Detect fair cycles Find livelocks (violations of fair termination) ConcurrentProgram Test Harness Win32 API Demonic Scheduler Fair Demonic Scheduler

Slide 30 -

Fair termination allows CHESS to check for arbitrary liveness properties Example: Good Samaritan assumption Forall threads t : GF scheduled(t)  GF yield(t) A thread when scheduled infinitely often yields the processor infinitely often Examples of yield: Sleep(), ScheduleThread(), asm {rep nop;} Thread completion while( ! done) { Sleep(); } done = 1; Thread 1 Thread 2

Slide 31 -

Outline Preemption bounding Makes CHESS effective on deep state spaces Fair stateless model checking Makes CHESS effective on cyclic state spaces Enables CHESS to find liveness violations (livelocks) Sober Detect relaxed-memory model errors Do not miss behaviors only possible in a relaxed memory model FeatherLite Concurrency Explorer

Slide 32 -

C# Example volatile bool isIdling; volatile bool hasWork; //Consumer thread void BlockOnIdle(){ lock (condVariable){ isIdling = true; if (!hasWork) Monitor.Wait(condVariable); isIdling = false; } } //Producer thread void NotifyPotentialWork(){ hasWork = true; if (isIdling) lock (condVariable) { Monitor.Pulse(condVariable); } } 32

Slide 33 -

Key pieces of code on previous slide: On x86, hardware may perform store late Bug: Producer thread does not notice waiting Consumer, does not send signal Store ii, 1 Example: Store Buffer Vulnerability Store ii, 1 volatile int ii = 0; volatile int hw = 0; Load hw, 0 Load ii, 1 Store hw, 1 Consumer Producer 0 33

Slide 34 -

Sober algorithm Programmers assume sequential-consistency (SC) Insert synchronizations & fences to counter memory-model relaxations Sober checks if a program is memory-model safe i.e., program has only SC executions in a memory model Reports any such violation as an error Sober is a dynamic monitor that checks if any SC execution can be extended to a non-SC execution Theorem: CHESS + Sober guarantees memory-model safety

Slide 35 -

Slide 36 -

Slide 37 -

Conclusion Don’t stress, use CHESS CHESS binary and papers available at http://research.microsoft.com/CHESS Stateless model checking is very effective Preemption bounding to scale to deep state spaces Fair demonic scheduler to handle nonterminating programs Need better testing and debugging methodologies for concurrent programs

Slide 38 -

Questions

Frequently Asked Questions

> About SlidesFinder?

Slidesfinder is a website that allows users to upload and share their PowerPoint presentations online. It provides a platform for individuals and businesses to share their ideas and knowledge through presentations, and for others to view and download these presentations for educational or professional purposes.
Slidesfinder offers a wide range of presentation topics and categories, including business, education, science, technology, health, and more. Users can also search for presentations using keywords, tags, or by category. The website provides tools to create professional presentations with rich media, animations, and graphics.

One of the key features of Slidesfinder is its user-friendly interface, which allows users to easily upload, view, and share presentations. Users can also embed their presentations in their websites or blogs using the website's embed code feature.
Slidesfinder also offers premium services, such as the ability to create private presentations and to download presentations in high-quality formats. However, the basic features of Slidesfinder are free to use, making it accessible to anyone who wants to share their ideas and knowledge through presentations.

> How do I register with SlidesFinder?

Go to registration page (you can see signup link on top of website page) https://www.slidesfinder.com/signup . If you have facebook/gmail account them just click on SIGN IN WITH FACEBOOK OR SIGN IN WITH GOOGLE button, by this you will be a registered member of slidesfinder without filling any form, required detail automatically will be fatch from your account. If you do not a Facebook account, then click on "Signup". Fill all required fields and you will be a registered member of slidesfinder.

> Is slidesfinder account confirmation is mandatory?

Yes it is mandetory to active your account to login.

> Do I need to signup/login on SlidesFinder before uploading a PowerPoint presentation?

Yes, you need to login with your account before uploading presentation. Your username will be displayed on your uploaded presentation. Your registered email id is needed for sending your stats of uploaded presentation.

Slidesfinder is a sharing website for PowerPoint presentations search and share. Find your interest in the form of powerpoint presentations on slidesfinder and save your valuable time . On Slidesfinder you get presentations from our huge library of professional ppt presentations. We believe in making your search INFORMATIVE and FUN. Find your best ppt presentation from a pool of PowerPoint presentations stacked under important industry categories like business & management, heath & Wellness,eduction & training etc. We provide unique informative PowerPoint presentation for marketers, presenters and educationists. These professional PowerPoint presentations are uploaded by professionals from across numerous industry segments.These ppt presentations are available for FREE download.

Not just finding your interest, but facilitate you broadcast your interest. We have created this platform for easy sharing of PowerPoint presentations, ensuring that these presentations get maximum exposure. Create your slidesfinder account and upload PowerPoint presentations for free, share on social media platforms and BUILD YOUR CROWD WITH PRESENTATION !!

The Great Buddha says, "Share your knowledge.It’s a way to achieve immortality"! So, start sharing knowledge and we are here to make that immortal !!

Re-productivity of content are not allowed. Without prior written permission from author, commercial use of any content is illegal.