Changes between Version 111 and Version 112 of LightweightConcurrency


Ignore:
Timestamp:
May 24, 2012 2:47:58 PM (3 years ago)
Author:
kc
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • LightweightConcurrency

    v111 v112  
    367367=== Black-hole Handling ===
    368368
    369 Any thunk evaluation may encounter a blackhole - a thunk under evaluation. When a thread encounters a thunk, the vanilla GHC suspends the thread until the thunk finishes evaluation. Similar to the solutions developed above, can utilize the scheduler actions to yield control to another thread from the user-level scheduler? Since the scheduler actions themselves are implemented in Haskell code, they can encounter blackholes. We might encounter situations where the user-level scheduler becomes blocked on a thread that it is scheduling, resulting in a deadlock.
    370 
    371 Since thunks (usually) represent pure computation, can we not duplicate thunk evaluation when we detect a deadlocked scheduler? Unfortunately, this is not so straightforward. The closure that represents a thunk is lost when the thunk is black-holed. Moreover, the thread evaluating the blackholed thunk (blackhole owner) might be running on the same or a different capability than the thread entering the blackhole. Correspondingly, the blackhole owner thread might either not be schedulable or running. This complicates the problem of potentially forcing a blackholed thunk's evaluation on a thread other than the blackhole owner. In addition to all of these concerns, we would like the common case - a thunk finishing evaluation without being blackholed - to be fast.
    372 
    373 When a thread enters a blackhole, there are essentially 3 parameters that we need to consider:
     369Long lived thunks may be ''blackholed'' to avoid duplication of work. A blackholed thunk is owned by the thread which blackholed it.  When a thread encounters a blackhole owned by some other thread, the vanilla GHC suspends the thread until the thunk finishes evaluation. This requires interaction with the scheduler. In general, any thunk evaluation may encounter a blackhole.
     370
     371For the LWC implementation, can we utilize the scheduler actions to yield control to another thread from the user-level scheduler, similar to the solutions above? The simple answer is no. Since the scheduler actions themselves are implemented in Haskell code, they can also encounter blackholes. Hence, we might encounter situations where the user-level scheduler becomes blocked on a thread that it is scheduling, resulting in a deadlock.
     372
     373Since thunks (usually) represent pure computation, can we not duplicate thunk evaluation when we detect a deadlocked scheduler? Unfortunately, this is not so straightforward. The closure that represents a thunk is lost when the thunk is black-holed. Moreover, the thread evaluating the blackholed thunk (blackhole owner) might be running on the same or a different capability than the thread entering the blackhole. Correspondingly, the blackhole owner thread might either not be schedulable or running. This complicates the problem of potentially forcing a blackholed thunk's evaluation on a thread other than the blackhole owner.
     374
     375In addition to all of these concerns, we would like the common case - a thunk finishing evaluation without being blackholed - to be fast. It is for these reasons we handle blackholes transparently from the programmer's perspective in the LWC implementation. When a thread enters a blackhole, there are essentially 3 parameters that we need to consider:
    374376
    375377 1. '''PTM : Is the thread manipulating a scheduler?''' since schedulers are implemented in Haskell code, there isn't a clear distinction between the scheduler and the rest of the program. As an approximation, we assume that whenever a thread is in the middle of a PTM transaction, it is potentially manipulating the scheduler.