Changes between Version 17 and Version 18 of Concurrency


Ignore:
Timestamp:
Mar 31, 2006 8:03:16 AM (8 years ago)
Author:
john@…
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Concurrency

    v17 v18  
    11= Concurrency = 
    2 [[PageOutline]] 
     2 
    33== References == 
    44 
     
    1616 * [http://www.haskell.org/~simonmar/papers/conc-ffi.pdf Extending the Haskell FFI with Concurrency] (a specification of the interaction between concurrency and the FFI, with a semantics) 
    1717 * [http://www.haskell.org/ghc/docs/papers/threads.ps.gz A Draft report addendum] (a shorter version of the above paper). 
    18  * [http://www.cs.chalmers.se/~koen/pubs/jfp99-monad.ps A Poor Man's Concurrency Monad] (Hugs' implementation of Concurrency)  
    1918 * [http://research.microsoft.com/~simonpj/papers/stm/ Software Transactional Memory] 
    2019 
     
    2827 * Things like the 'poor man's concurrency monad' can achieve some of the benefits 
    2928 
     29== Proposal ==           
    3030 
    31 ---------------------- 
    32 = Proposals =           
     31 * Standardise on Concurrent Haskell without STM.  It is our view that even in the presence of STM, {{{MVar}}}s offer 
     32   functionality that is distinct from STM and separately useful, so this leaves room for growth. 
     33  
     34 * Use the semantics from [http://www.haskell.org/~simonmar/papers/conc-ffi.pdf Extending the Haskell FFI with Concurrency]  
    3335 
    34 == Proposal 1 == 
     36Questions: 
    3537 
    36  * The Haskell' standard does not include concurrency, but includes enough to allow portable thread-safe 
    37    libraries to be written.  (see "thread safe", below). 
     38 * Decide how much pre-emption is acceptable, and figure out how to specify this. 
    3839 
    39  * A separate addendum specifies concurrency according to the ''fairness'' requirements (see below). 
    40  
    41 == Proposal 2 == 
    42  
    43  * The Haskell' standard includes concurrency with the ''fairness'' requirements. 
    44  
    45  * A separate addendum specifies how implementations that do not provide concurrency behave: at the least, 
    46    it should include enough to allow portable thread-safe libraries. 
    47  
    48 == Proposal 3 == 
    49  
    50  * The Haskell' standard includes concurrency with a weaker version of ''fairness'', that is enough 
    51    to admit implementations with ''cooperative scheduling''. 
    52  
    53  * A separate addendum specifies concurrency with the full ''fairness'' requirements. 
    54  
    55 == Open questions == 
     40 * Should we specify what an implementation that doesn't provide concurrency should do? (e.g. provide an implementation 
     41   of MVars in terms of IORefs, so that concurrency-safe libraries can be written portably). 
    5642 
    5743 * Require bound thread support, or make it optional?  (YHC has concurrency with non-blocking foreign calls, but doesn't 
    5844   have bound threads as yet.) 
    5945 
    60  * Do we require ForeignBlocking? 
    61  
    62 == Thread-safety == 
    63  
    64 In order to write library code that is thread-safe when run in a multi-threaded environment, two things are needed: 
    65  
    66  1. a way to protect mutable state against race conditions 
    67  2. a way to declare that foreign calls are blocking 
    68  
    69 For (1), we have two choices: 
    70  
    71  * Provide {{{MVar}}}s.  A non-concurrent implementation might implement them in terms of {{{IORef}}}, 
    72    for example. 
    73  
    74  * Provide STM.  Not entirely trivial to implement, even in a single-threaded implementation, because 
    75    exceptions have to abort a transaction.  Ross Paterson provided an [http://www.haskell.org//pipermail/haskell-prime/2006-March/001108.html implementation]. 
    76  
    77 For (2), one option is ForeignBlocking. 
    78  
    79 ---------- 
    80 = Terminology = 
    81  
    82 '''Pre-emption''' means that (1) threads have priority levels, and (2) that a 
    83 higher priority thread can steal the processor from a currently-running 
    84 lower priority thread, and (3) it can do so "immediately" it needs to, 
    85 without waiting for some "safe" synchronisation point. 
    86 By these criteria, none of the current Haskell implementations are 
    87 pre-emptive, because no API assigns priorities to threads.  So let's try 
    88 to avoid using the term. 
    89  
    90 '''Fairness''' can be defined by two main criteria: 
    91  * No runnable process will be indefinitely delayed. 
    92  * No thread can be blocked indefinitely on an MVar unless another thread holds the MVar indefinitely. 
    93  
    94 '''Cooperative scheduling''' describes an implementation in which it is the programmer's responsibility to insert context switch points in the code.  An implementation that only provides cooperative scheduling cannot satisfy the fairness properties given above.  A programmer who has access to all the code ''may'' be able to insert enough context switch points to satisfy fairness, but this isn't always possible. 
    95  
    96 '''Concurrent foreign call''' means a foreign call that should run concurrently with other Haskell threads.  It is a requirement of "fairness" (above) that a foreign call should not prevent other threads from making progress indefinitely.  Note that we used to use the term '''non-blocking foreign call''' here, but that lead to confusion with "foreign calls that block", which are foreign calls that may wait indefinitely for some resource, such as reading data from a socket.  "foreign calls that block" are the main reason for wanting support for concurrent foreign calls. 
    9746 
    9847 
    99 '''Scheduling.''' 
    100 Most current implementations of 
    101 concurrency in Haskell use non-preemptive scheduling.  That is, there are 
    102 explicit time points at which any one thread can ''yield'', allowing other threads to run. 
    103 The only differences between implementations are in the granularity and positioning of the yield. 
     48-------------- 
    10449 
    105   * For Hugs, yield is inserted at certain I/O actions. 
    106   * For ghc in non-SMP mode,  yield is inserted after some count of allocations. 
    107   * For yhc,  yield is inserted after some count of bytecode instructions. 
    108  
    109 Arguably, Hugs has made the wrong choice from a fairness point of view.  It would be possible to make Hugs yield more often, such as in IO-monad's bind operator, but even this wouldn't be quite enough for fairness, because a thread might hang indefinitely performing a non-IO computation.  Yielding outside of the IO monad in Hugs doesn't seem possible without overhauling the concurrency implementation completely. 
    110  
    111 The notable exception to the above is GHC in SMP mode, which can run multiple Haskell threads simultaneously in separate OS threads, and hence simultaneously on multiple CPUs if available.  This implementation is truly preemptive. 
    112  
    113 ---------- 
    114 = Levels = 
    115  
    116 There are several levels of concurrency support which require sucessivly more 
    117 implementation support and imply more implementation overhead. 
    118  
    119 == No Concurrency == 
    120  
    121 The report says nothing about concurrency at all 
    122  
    123 == Concurrent Friendly == 
    124  
    125 Enough is specified to allow people to write completley portable programs and 
    126 libraries that while they may not depend on concurrency, will not break in the 
    127 presence of it. See "Thread-safety" above. 
    128  
    129 == Concurrent Capabale == 
    130  
    131 This would allow concurrency needing programs to be written, but perhaps not 
    132 as transparently as it curently is with GHC. This would include everything 
    133 needed to write concurrent programs without anything that would imply a 
    134 run-time or implementation overhead in the non-concurrent case.  
    135  
    136 == Concurrent Built-in == 
     50= Proposal =  
    13751 
    13852 
    139 == Concurrent Preemptive/SMP == 
     53== what is provided == 
     54 
     55At least the following interface will be provided 
     56 
     57 * Control.Concurrent.MVar - everything except addMVarFinalizer 
     58 * Control.Concurrent - ThreadId,myThreadId,forkIO,yield,threadWaitRead[1],threadWaitWrite[1],threadDelay,threadSetPriority[2],threadGetPriority[2] 
     59 
     60the FFI must be able to handle 'concurrent nonrentrant' imports, but not 
     61necessarily 'concurrent reentrant' ones. 
     62 
     63== Progress Guarentee == 
     64 
     65 * if any haskell thread is runnable then at least one thread will be running. 
     66 * foreign calls marked 'concurrent' will not interfere will the above rule. 
     67 
     68== MVar Guarentees == 
     69 
     70initial proposal is here: 
     71 
     72 http://www.haskell.org//pipermail/haskell-prime/2006-March/001168.html 
     73 
     74== Misc library stuff == 
     75 
     76yield is guarenteed to choose an alternate thread if another one exists and is 
     77runnable. 
     78 
     79[2] priorities are advisory, but higher priority threads should be run in 
     80preference to lower priority ones. 
     81 
     82threadDelay guarentees the thread will wait as long as its argument at a 
     83minimum. it may be blocked for longer. 
     84 
     85== notes == 
     86 
     87[1] may be moved to another module, routines working on Handles should be 
     88added too. 
     89 
     90[2] possibly, if we decide to go with priorities 
     91 
     92 
     93= Optional extensions to basic standard = 
     94 
     95These are optional extensions a compiler may implement. In some 
     96implementations they may entail a run-time cost to non-concurrent code or a 
     97compiler might need a special option to enable them. However, A compiler is 
     98not required to provide more than one concurrency model as long as it can meet 
     99the requirements of the standard and any options it claims to support. 
     100 
     101If a compiler documents that it supports one of the following options, then it 
     102must adhere to the rules of that option as well. 
     103 
     104== Optional Feature 1 - Preemption == 
     105 
     106 
     107The standard only requires a progress guarentee, that a thread is always 
     108running, making progress. If an implementation supports context switching 
     109during arbitrary, perhaps even pure, computations and meets the stronger 
     110fairness guarentees, then it can be said to support the 'Preemption' option.  
     111 
     112Fairness Guarentee  
     113 * no starvation 
     114 
     115new library calls provided 
     116 * mergeIO, nmergeIO 
     117 
     118== Optional Feature 2 - OS threads == 
     119 
     120The implementation allows multiple haskell threads to run at once via the 
     121operating systems threading service. May take advantange of SMP architectures. 
     122 
     123 * forkOS,isCurrentThreadBound,runInBoundThread,runInUnboundThread 
     124 * bound threads 
     125 * concurrent reentrant supported 
    140126 
    141127