Changes between Version 122 and Version 123 of LightweightConcurrency


Ignore:
Timestamp:
May 31, 2012 6:08:50 PM (3 years ago)
Author:
kc
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • LightweightConcurrency

    v122 v123  
    2525== Concurrency Substrate == 
    2626 
    27 The idea of the concurrency substrate is to provide a minimal set of primitives over which a variety of user-level concurrency libraries can be implemented. As such, the concurrency substrate must provide a way to create threads, a way to schedule them, and a synchronization mechanism in a multiprocessor context. Whereas, the Creation and maintenance of schedulers and concurrent data structures is the task of the concurrency library. Concurrency substrate resides at [source:libraries/base/LwConc/Substrate.hs@646ec91db34c4309555fd7dd3bfe3930a4c5c55f libraries/base/LwConc/Substrate.hs]. 
     27The idea of the concurrency substrate is to provide a minimal set of primitives over which a variety of user-level concurrency libraries can be implemented. As such, the concurrency substrate must provide a way to create threads, a way to schedule them, and a synchronization mechanism in a multiprocessor context. Whereas, the Creation and maintenance of schedulers and concurrent data structures is the task of the concurrency library. Concurrency substrate resides at [source:libraries/base/LwConc/Substrate.hs@76dc667761e38fec47e7b1aba27bb4c499fd7636 libraries/base/LwConc/Substrate.hs]. 
    2828 
    2929=== PTM === 
     
    215215 
    216216Here, the thread that invokes forkIO initializes the new SCont (`ns`) with its own scheduler actions, and appends it to the scheduler. After the newly created SCont finishes execution, the control must switch to another thread in the scheduler. This is captured by the `epilogue`. 
     217 
     218A full implementation of a round-robin scheduler can be found [source:libraries/lwconc/LwConc/Concurrent.hs?rev=76dc667761e38fec47e7b1aba27bb4c499fd7636 here]. This scheduler has one queue per capability. Work is shared among the capabilities by spawning threads in a round-robin fashion on the capabilities. 
    217219 
    218220=== MVars === 
     
    255257If the MVar is full with a pending writer, we first fill the hole with the value. Then, MVar's status is updated with the enqueued value and the rest of the writers. Finally, we execute the dequeued PTM action to place the writer into its corresponding scheduler. 
    256258 
    257 Notice that just like yield and forkIO, takeMVar is scheduler agnostic; the MVar implementation is cleanly separated from the scheduler implementation. Moreover, the same MVar might be shared between threads from different schedulers since they utilize the uniform scheduler interface. Since the scheduler actions are PTM actions, actions from different schedulers can be composed together elegantly and simplifies reasoning about synchronization.  
     259Notice that just like yield and forkIO, takeMVar is scheduler agnostic; the MVar implementation is cleanly separated from the scheduler implementation. Moreover, the same MVar might be shared between threads from different schedulers since they utilize the uniform scheduler interface. Since the scheduler actions are PTM actions, actions from different schedulers can be composed together elegantly and simplifies reasoning about synchronization. An implementation of a MVar can be found [source:libraries/lwconc/LwConc/MVar.hs?rev=76dc667761e38fec47e7b1aba27bb4c499fd7636 here]. 
    258260 
    259261As an aside, the race condition in [http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Control-Concurrent-MVar.html#v%3AswapMVar swapMVar] can be eliminated with the help of PTM abstraction. TODO: show example. Thus, PTM abstraction makes it easy to construct correct concurrent data-structures.