Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

#204 Deadlock in debugger/listeners

closed-fixed
Charles Reis
Debugger (51)
7
2003-07-17
2003-07-15
Charles Reis
No

There is currently a race condition which can cause
deadlock in the debugger, because one thread has a lock
on the debugger and is trying to notify listeners, and
another thread has a lock on the EventNotifier and is
trying to call a synchronized method on the debugger.
(The debugger is synchronized for obvious threading
reasons, and the EventNotifier is synchronized so that
listeners cannot be added or removed while a
notification is in progress.)

This illustrates a much more serious problem. Any code
in a listener that calls a synchronized method on an
object can potentially cause deadlock, since a
different thread could already have the lock on that
object and could be attempting to notify listeners of
an event (thus attempting to acquire the EventNotifier
lock).

Discussion

  • Charles Reis
    Charles Reis
    2003-07-15

    Logged In: YES
    user_id=429731

    There are a few ways we can address this:

    1) Any listener that needs to call a synchronized method
    must do so from a newly created thread. This prevents the
    original thread from holding onto the EventNotifier lock
    while potential waiting for the synchronized method to
    complete. However, it may cause certain operations to
    happen at unexpected times (possibly breaking invariants),
    and it's also a difficult convention to enforce, since all
    developers must be aware of it when writing listener methods.

    2) Redesign EventNotifier's synchronization.
    EventNotifier is synchronized to prevent listeners from
    being added or removed while a notification is in process.
    But it's really more of a readers/writers problem, since we
    don't care if multiple notifications happen simultaneously.
    Semaphores would be useful here, but Java doesn't have
    them. We could attempt to rewrite EventNotifier to prevent
    addListener or removeListener from being called while a
    notification is in process. Unfortunately, this is quite
    complicated, because we also have to prevent starvation on
    the "writers" (add/remove).

     
  • Charles Reis
    Charles Reis
    2003-07-16

    Logged In: YES
    user_id=429731

    We're planning on option 2, since it's both safer for future
    development and it more correctly enforces the invariant that the
    list of listeners cannot be modified while a notification is in
    progess. (It's also more flexible than our current setup, since it
    allows multiple simultaneous notifications.)

    Note that the current code (with each method in EventNotifier
    being synchronized) actually allows a listener to be added by a
    listener method, since the thread performing the notification
    already has the lock on EventNotifier. Even though there could be
    cases where this is reasonable (eg. when a JUnit test starts, add a
    new listener for interpreterExited so we know if the JVM resets),
    we should still consider this a bug, since it violates the constraints
    of EventNotifier by modifying the list of listeners while iterating
    through it. (This could cause unexpected behavior or worse, since
    we use an unsynchronized ArrayList to hold the listeners.)

    Therefore, we choose to enforce that no one can add/remove
    listeners while a notify is in progress. If a listener method needs
    to add a new listener, it must do so in a new thread.

     
  • Charles Reis
    Charles Reis
    2003-07-16

    Logged In: YES
    user_id=429731

    We've been evaluating possible solutions to the readers/writers
    problem, since it's easy to get it wrong. There's a simple
    implementation at the link below, but it doesn't protect against
    starvation (the writers never get to go if there is a continuous
    stream of readers).
    http://devcentral.iftech.com/articles/Java/thread_sync/code.html

    A better solution is at the following link, which prevents against
    general starvation:
    http://www.mcs.drexel.edu/~shartley/ConcProgJava/
    monitors.html
    However, this solution does not appear to guarantee progress for
    each writer. That is, multiple waiting writers have no guarantees
    on which one goes first, so one with "bad luck" could keep getting
    skipped over. (Lack of order is bad for us anyway-- a remove
    before an add doesn't make sense.)

    After discussing it, we've decided to write our own solution slightly
    based on the second link. However, we're using a queue of
    waiting threads and allowing them to proceed in order. We still
    allow multiple readers access, but only those that show up before
    the next writer. Not quite as much benefit from synchronous
    execution, but it matches the expected behavior for interacting
    with listeners. (ie. You can add a listener and notify it in two
    sequential steps, and you are guaranteed that your listener will
    hear the event, regardless of other interactions with
    EventNotifier.)

    This solution will be implemented with startRead, endRead,
    startWrite, and endWrite primitives in a ReaderWriterLock class in
    the util package. (Unfortunately, unit testing it is extremely
    difficult, since it's hard to assert things at just the right time, let
    alone specify the exact schedule we want.)

     
  • Charles Reis
    Charles Reis
    2003-07-17

    Logged In: YES
    user_id=429731

    Our solution to the readers/writers problem has been committed to the
    util package as ReaderWriterLock, along with a unit test. The test
    can't enforce much about the exact schedules of multiple readers and
    writers, but it does check that the output of a particular writer is
    never interspersed with the output of another thread (and that simple
    deadlocks don't occur).

    The solution uses a queue of waiting threads, and each time a reader
    or writer finishes, it wakes up the next "group" at the front of the
    queue. (A group consists of several readers which arrived in
    sequential order before a writer, or a single writer at the front.) We
    also proactively check for deadlock by preventing a reading thread
    from calling startWrite, or a writing thread from calling either startRead
    or startWrite again. Note that a reading thread *can* begin another
    read operation safely, without having to wait.

    The ReaderWriterLock class is now used in EventNotifier, where adding
    and removing listeners are treated as writes and notifying listeners are
    treated as reads. This new synchronization technique resolves the
    deadlock issue orginally described in this bug.

    The changes are committed as of drjava-20030717-0204.

     
  • Charles Reis
    Charles Reis
    2003-07-17

    • status: open --> closed-fixed