Changes between Version 112 and Version 113 of LightweightConcurrency


Ignore:
Timestamp:
May 24, 2012 10:35:30 PM (2 years ago)
Author:
kc
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • LightweightConcurrency

    v112 v113  
    371371For 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.  
    372372 
    373 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.  
    374  
    375 In 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: 
     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. It is for these reasons we handle blackholes transparently from the programmer's perspective in the LWC implementation.  
     374 
     375When a thread enters a blackhole, there are essentially 3 parameters that we need to consider: 
    376376 
    377377 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. 
     
    381381Since each of these conditions can either be true or false, we have 8 cases to consider.  
    382382 
    383  * '''(1, 2) PTM(F)   UPT(F)   CCAP(T/F)''' - This is the typical case when a thread blocks on a black hole. Here, we enque the thread on the blackhole and perform the yieldControlAction to switch to another thread. When the thunk finishes evaluation, we examine the blocked threads. If a blocked thread is not an upcall thread, we know it has a scheduleSContAction, which is executed to resume the blocked thread. 
     383 * '''(1, 2) PTM(F)   UPT(F)   CCAP(T/F)''' - This is the typical case when a thread blocks on a black hole. Here, we enque the thread on the blackhole's blocked thread queue and perform the yieldControlAction to switch to another thread. When the thunk finishes evaluation, we examine the blocked thread queue. If a blocked thread is not an upcall thread, we know it has a scheduleSContAction, which is executed to resume the blocked thread. 
    384384 * '''(3, 4) PTM(F)   UPT(T)   CCAP(T/F)''' - This case cannot happen. Upcall threads only execute PTM actions. 
    385385 * '''(5, 6) PTM(T)   UPT(T/F) CCAP(T)'''   - We are under PTM and potentially manipulating the scheduler. The blackhole is owned by a thread on current capability and is suspended. Hence, the only option is to force evaluation of the thunk. This is achieved by creating a closure (AP_STACK) that contains all of the frames from the blackhole owner thread until the update frame that corresponds to the blackholed thunk. Blackhole owner's stack is modified such that when it resumes, it evaluates the newly created closure instead of resuming the original thunk evaluation. Current thread evaluates the newly created thunk to force evaluation of the thunk. Here, the current thread is said to have `inherited` the thunk. 
    386386 * '''(7)    PTM(T)   UPT(F)   CCAP(F)'''   - A user-level thread under PTM has blocked on a blackhole owned by a thread on a different capability. We cannot inherit the computation. The solution is similar to (1).  
    387  * '''(8)    PTM(T)   UPT(T)   CCAP(F)'''   - This is a tricky case. Upcall thread blocks on a blackhole, which is owned by a thread on a different capability. We need to put the capability to sleep and wake-up when the black-holed thunk finishes evaluation. Here, we enque the upcall thread on the blackhole. Now, the current capability does not have any runnable threads. Hence, it goes to sleep. When the thunk finishes evaluation, we examine the blocked thread. Since the thread is an upcall thread, we push it on its owning capability. This implicitly wakes up the capability, which resumes execution.   
     387 * '''(8)    PTM(T)   UPT(T)   CCAP(F)'''   - This is a tricky case. Upcall thread blocks on a blackhole, which is owned by a thread on a different capability. We need to put the capability to sleep and wake-up when the black-holed thunk finishes evaluation. Here, we enque the upcall thread on the blackhole's blocked thread queue. Now, the current capability does not have any runnable threads. Hence, it goes to sleep. When the thunk finishes evaluation, we examine the blocked thread queue. If a blocked thread is an upcall thread, we push it on its owning capability. This implicitly wakes up the capability, which resumes execution.   
     388 
     389==== RTS Messaging Layer ==== 
     390 
     391Since thunk evaluation and blackholing is a critical for good performance, we would like the common case - thunk finishes evaluation without being blackholed - to be fast. Hence, we retain the RTS messaging layer between the capabilities for blocking on a blackhole. When a thread enters a blackhole whose owner thread resides on another capability, a block request message is sent to the corresponding capability. Notice that the [#SContAffinity association] between SConts (threads) and capabilities is essential for identifying which capability to send the block request message to. During every iteration of the RTS Schedule loop, a capability checks its inbox for pending messages, and if any, processes the messages. Hence, no synchronization is necessary for replacing a thunk with a value.  
    388392 
    389393=== Asynchronous Exceptions ===