Debugging Scheme Fair Threads

Damien Ciabrini

INRIA Sophia Antipolis

Damien.Ciabrini@sophia.inria.fr

Outline

Motivations

Fair threads, fair scheduling

Scheduler inspectors

Traces of executions

Example

Implementation

Conclusion

Motivations

Threads

Independent flows of control

Shared memory

Cooperative or preemptive scheduling

Debugging threads is difficult

Preemptive scheduling

non determinism, data races, synchronization losses

Cooperative scheduling

cooperations missed, scheduling interactivity

The Fair Threads Model

Bigloo's multi threading framework

Cooperative and deterministic scheduling

Based on synchronous reactive programming

Ability to do asynchronous I/Os (+ SMP)

Bugloo: debugger for Bigloo programs

Compiled into JVM bytecode

Support for Fair Threads debugging

Fair Threads, Fair Scheduling

Fair threads run inside a fair scheduler

Execution decomposed into instants

Communication by broadcast signals

a signal is seen by all threads

a signal is visible until the end of instant

await

emit

instants

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Instant 2:

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Instant 2:

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Instant 2:

sig3

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Instant 2:

sig3

Example

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Instant 1:

sig1

sig2

Instant 2:

sig3

Debugging Support

Two types of tools:

debugging threads during a single instant

enhanced single stepper

scheduler and fair threads inspector

debugging threads across many instants

trace of scheduler execution

Debugging a Single Instant

(define (funA)

(thread-await! 'sig1)

(thread-await! 'sig2)

(thread-yield!)

(thread-await! 'sig1))

(define (funB)

(thread-emit! 'sig1)

(thread-yield!)

(thread-emit! 'sig3))

(define (funC)

(thread-await! 'sig1)

(thread-emit! 'sig2)

(thread-await! 'sig3))

Debugging a Single Instant

Debugging Across Many Instants

Example II

Producers/Consumers

Fair threads accessing a shared buffer

Asynchronous I/Os

Producers/Consumers

(define (make-producer val name)

(make-thread

(lambda ()

(let loop ((n val))

(put n)

(thread-yield!)

(loop (+ 1 n))))

name))

Producers/consumers = fair threads

(define (make-consumer name)

(make-thread

(lambda ()

(let loop ()

(print (thread-id) (get))

(thread-yield!)

(loop)))

name))

get and put access the shared buffer

Producers/Consumers

(define (wait)

(thread-await! 'data))

Simple access to shared buffer

All consumer awaken at a time

One instant to consume a datum

(define (put val)

(buffer-put! val)

(notify))

(define (get)

(if (buffer-empty?)

(begin

(wait)

(thread-yield!)

(get))

(buffer-fetch)))

(define (notify)

(thread-emit! 'data))

Producers/Consumers

Improving notification:

Only one fair thread awaken at a time

Fair threads wait in a FIFO

(define (wait)

(thread-await! 'data))

(define (notify)

(thread-emit! 'data))

Producers/Consumers

Improving notification:

Only one fair thread awaken at a time

Fair threads wait in a FIFO

(define (wait)

(let ((self (thread-id)))

(queue-push! self)

(thread-await! self)))

(define (notify)

(if (not (queue-empty? sig))

(thread-emit! (queue-pop! sig))))

Producers/Consumers

Adding asynchronous I/Os

I/O does not block the scheduler

A signal is broadcast on I/O termination

(define (make-consumer name)

(make-thread

(lambda ()

(let loop ()

(print (thread-id) (get))

(thread-yield!)

(loop)))

name))

Producers/Consumers

Adding asynchronous I/Os

I/O does not block the scheduler

A signal is broadcast on I/O termination

(define (make-consumer name)

(make-thread

(lambda ()

(let loop ()

(thread-await!

(make-output-signal

(current-output-port)

(concat (thread-id) (get))))

(loop)))

name))

Producers/Consumers

(define (start)

(thread-start! (make-consumer "cons1"))

(thread-start! (make-consumer "cons2"))

(thread-start! (make-consumer "cons3"))

(thread-start! (make-consumer "cons4"))

(thread-start! (make-producer 1000 "prod1"))

(thread-start! (make-producer 0 "prod2")))

Starting the fair threads...

Producers/Consumers

(define (get)

(if (buffer-empty?)

(begin

(wait 'available)

(thread-yield!)

(get))

(buffer-fetch)))

Producers/Consumers

(let loop ()

(thread-await!

(make-output-signal

(current-output-port)

(concat (thread-id) (get))))

(thread-yield!)

(loop)))

Implementation

JVM Debugging Architecture

Debuggee instrumentation

No source code modification, no special runtime

Breakpoint trickery in the Fair Threads runtime

Scheduling not modified by the debugger

debugger

debuggee

events

JVM

JVM

Conclusion

Bugloo supports Fair Threads debugging

Track bugs in a single instant

enhanced single stepper, scheduler inspector

Track bugs across many instants

traces of scheduler execution

Benefits of the tool

Used to debug Bugloo itself !

Can be used a a simple profiler

Effective way to understand Fair Threads

2004-09-05T18:42:38