Changes in / [73edfe9:f52ce6e]


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Paper.tex

    r73edfe9 rf52ce6e  
    16361636For this reason, \CFA requires programmers to identify the kind of parameter with the @mutex@ keyword and uses no keyword to mean \lstinline[morekeywords=nomutex]@nomutex@.
    16371637
    1638 \newpage
    16391638The next semantic decision is establishing which parameter \emph{types} may be qualified with @mutex@.
    16401639The following has monitor parameter types that are composed of multiple objects.
     
    17351734
    17361735Users can still force the acquiring order by using @mutex@/\lstinline[morekeywords=nomutex]@nomutex@.
    1737 \newpage
    17381736\begin{cfa}
    17391737void foo( M & mutex m1, M & mutex m2 ); $\C{// acquire m1 and m2}$
     
    17461744\end{cfa}
    17471745The bulk-acquire semantics allow @bar@ or @baz@ to acquire a monitor lock and reacquire it in @foo@.
    1748 In the calls to @bar@ and @baz@, the monitors are acquired in opposite order, possibly resulting in deadlock.
     1746The calls to @bar@ and @baz@ acquired the monitors in opposite order, possibly resulting in deadlock.
    17491747However, this case is the simplest instance of the \emph{nested-monitor problem}~\cite{Lister77}, where monitors are acquired in sequence versus bulk.
    17501748Detecting the nested-monitor problem requires dynamic tracking of monitor calls, and dealing with it requires rollback semantics~\cite{Dice10}.
     
    17971795% It is only in this way that a waiting program has an absolute guarantee that it can acquire the resource just released by the signalling program without any danger that a third program will interpose a monitor entry and seize the resource instead.~\cite[p.~550]{Hoare74}
    17981796% \end{cquote}
    1799 Furthermore, \CFA concurrency has no spurious wakeup~\cite[\S~9]{Buhr05a}, which eliminates an implicit form of barging.
     1797Furthermore, \CFA concurrency has no spurious wakeup~\cite[\S~9]{Buhr05a}, which eliminates an implicit form of self barging.
    18001798Hence, a \CFA @wait@ statement is not enclosed in a @while@ loop retesting a blocking predicate, which can cause thread starvation due to barging.
    18011799
    1802 Figure~\ref{f:MonitorScheduling} shows internal/external scheduling (for the bounded-buffer example in Figure~\ref{f:InternalExternalScheduling}).
     1800Figure~\ref{f:MonitorScheduling} shows general internal/external scheduling (for the bounded-buffer example in Figure~\ref{f:InternalExternalScheduling}).
    18031801External calling threads block on the calling queue, if the monitor is occupied, otherwise they enter in FIFO order.
    1804 Internal threads block on condition queues via @wait@ and they reenter from the condition in FIFO order.
     1802Internal threads block on condition queues via @wait@ and they reenter from the condition in FIFO order, or they block on urgent via @signal_block@ or @waitfor@ and reenter implicit when the monitor becomes empty, \ie, the thread in the monitor exits or waits.
    18051803
    18061804There are three signalling mechanisms to unblock waiting threads to enter the monitor.
    1807 Note, signalling cannot have the signaller and signalled thread in the monitor simultaneously because of the mutual exclusion so only can proceed.
     1805Note, signalling cannot have the signaller and signalled thread in the monitor simultaneously because of the mutual exclusion so only one can proceed.
    18081806For internal scheduling, threads are unblocked from condition queues using @signal@, where the signallee is moved to urgent and the signaller continues (solid line).
    18091807Multiple signals move multiple signallees to urgent, until the condition is empty.
     
    18181816Executing multiple @waitfor@s from different signalled functions causes the calling threads to move to urgent.
    18191817External scheduling requires urgent to be a stack, because the signaller excepts to execute immediately after the specified monitor call has exited or waited.
    1820 Internal scheduling behaves the same for an urgent stack or queue, except for signalling multiple threads, where the threads unblock from urgent in reverse order from signalling.
    1821 If the restart order is important, multiple signalling by a signal thread can be transformed into shared signalling among threads, where each thread signals the next thread.
    1822 Hence, \CFA uses an urgent stack.
     1818Internal scheduling behaves the same for an urgent stack or queue, except for multiple signalling, where the threads unblock from urgent in reverse order from signalling.
     1819If the restart order is important, multiple signalling by a signal thread can be transformed into daisy-chain signalling among threads, where each thread signals the next thread.
     1820We tried both a stack for @waitfor@ and queue for signalling, but that resulted in complex semantics about which thread enters next.
     1821Hence, \CFA uses a single urgent stack to correctly handle @waitfor@ and adequately support both forms of signalling.
    18231822
    18241823\begin{figure}
     
    18381837\end{figure}
    18391838
    1840 Figure~\ref{f:BBInt} shows a \CFA generic bounded-buffer with internal scheduling, where producers/consumers enter the monitor, see the buffer is full/empty, and block on an appropriate condition variable, @full@/@empty@.
     1839Figure~\ref{f:BBInt} shows a \CFA generic bounded-buffer with internal scheduling, where producers/consumers enter the monitor, detect the buffer is full/empty, and block on an appropriate condition variable, @full@/@empty@.
    18411840The @wait@ function atomically blocks the calling thread and implicitly releases the monitor lock(s) for all monitors in the function's parameter list.
    18421841The appropriate condition variable is signalled to unblock an opposite kind of thread after an element is inserted/removed from the buffer.
     
    19621961External scheduling is controlled by the @waitfor@ statement, which atomically blocks the calling thread, releases the monitor lock, and restricts the function calls that can next acquire mutual exclusion.
    19631962If the buffer is full, only calls to @remove@ can acquire the buffer, and if the buffer is empty, only calls to @insert@ can acquire the buffer.
    1964 Threads making calls to functions that are currently excluded block outside of (external to) the monitor on the calling queue, versus blocking on condition queues inside of (internal to) the monitor.
     1963Calls threads to functions that are currently excluded block outside of (external to) the monitor on the calling queue, versus blocking on condition queues inside of (internal to) the monitor.
    19651964Figure~\ref{f:RWExt} shows a readers/writer lock written using external scheduling, where a waiting reader detects a writer using the resource and restricts further calls until the writer exits by calling @EndWrite@.
    19661965The writer does a similar action for each reader or writer using the resource.
    19671966Note, no new calls to @StarRead@/@StartWrite@ may occur when waiting for the call to @EndRead@/@EndWrite@.
    1968 External scheduling allows waiting for events from other threads while restricting unrelated events.
     1967External scheduling allows waiting for events from other threads while restricting unrelated events, that would otherwise have to wait on conditions in the monitor.
    19691968The mechnaism can be done in terms of control flow, \eg Ada @accept@ or \uC @_Accept@, or in terms of data, \eg Go @select@ on channels.
    19701969While both mechanisms have strengths and weaknesses, this project uses the control-flow mechanism to be consistent with other language features.
     
    19811980Furthermore, barging corrupts the dating service during an exchange because a barger may also match and change the phone numbers, invalidating the previous exchange phone number.
    19821981Putting loops around the @wait@s does not correct the problem;
    1983 the solution must be restructured to account for barging.
     1982the simple solution must be restructured to account for barging.
    19841983
    19851984\begin{figure}
     
    20492048the signaller enters the monitor and changes state, detects a waiting threads that can use the state, performs a non-blocking signal on the condition queue for the waiting thread, and exits the monitor to run concurrently.
    20502049The waiter unblocks next from the urgent queue, uses/takes the state, and exits the monitor.
    2051 Blocking signalling is the reverse, where the waiter is providing the cooperation for the signalling thread;
     2050Blocking signal is the reverse, where the waiter is providing the cooperation for the signalling thread;
    20522051the signaller enters the monitor, detects a waiting thread providing the necessary state, performs a blocking signal to place it on the urgent queue and unblock the waiter.
    20532052The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to use/take the state.
     
    20802079While \CC supports bulk locking, @wait@ only accepts a single lock for a condition variable, so bulk locking with condition variables is asymmetric.
    20812080Finally, a signaller,
    2082 \newpage
    20832081\begin{cfa}
    20842082void baz( M & mutex m1, M & mutex m2 ) {
     
    20862084}
    20872085\end{cfa}
    2088 must have acquired at least the same locks as the waiting thread signalled from the condition queue.
     2086must have acquired at least the same locks as the waiting thread signalled from a condition queue to allow the locks to be passed, and hence, prevent barging.
    20892087
    20902088Similarly, for @waitfor( rtn )@, the default semantics is to atomically block the acceptor and release all acquired mutex parameters, \ie @waitfor( rtn, m1, m2 )@.
     
    21192117The \emph{conditional-expression} of a @when@ may call a function, but the function must not block or context switch.
    21202118If there are multiple acceptable mutex calls, selection occurs top-to-bottom (prioritized) among the @waitfor@ clauses, whereas some programming languages with similar mechanisms accept nondeterministically for this case, \eg Go \lstinline[morekeywords=select]@select@.
    2121 If some accept guards are true and there are no outstanding calls to these members, the acceptor is accept-blocked until a call to one of these members is made.
     2119If some accept guards are true and there are no outstanding calls to these members, the acceptor is blocked until a call to one of these members is made.
    21222120If there is a @timeout@ clause, it provides an upper bound on waiting.
    21232121If all the accept guards are false, the statement does nothing, unless there is a terminating @else@ clause with a true guard, which is executed instead.
     
    21622160However, the basic @waitfor@ semantics do not support this functionality, since using an object after its destructor is called is undefined.
    21632161Therefore, to make this useful capability work, the semantics for accepting the destructor is the same as @signal@, \ie the call to the destructor is placed on the urgent queue and the acceptor continues execution, which throws an exception to the acceptor and then the caller is unblocked from the urgent queue to deallocate the object.
    2164 Accepting the destructor is an idiomatic way to terminate a thread in \CFA.
     2162Accepting the destructor is the idiomatic way to terminate a thread in \CFA.
    21652163
    21662164
     
    22562254In the object-oriented scenario, the type and all its operators are always present at compilation (even separate compilation), so it is possible to number the operations in a bit mask and use an $O(1)$ compare with a similar bit mask created for the operations specified in a @waitfor@.
    22572255
    2258 In \CFA, monitor functions can be statically added/removed in translation units, so it is impossible to apply an $O(1)$ approach.
     2256However, in \CFA, monitor functions can be statically added/removed in translation units, making a fast subset check difficult.
    22592257\begin{cfa}
    22602258        monitor M { ... }; // common type, included in .h file
     
    22632261        void g( M & mutex m ) { waitfor( `f`, m ); }
    22642262translation unit 2
    2265         void `f`( M & mutex m );
     2263        void `f`( M & mutex m ); $\C{// replacing f and g for type M in this translation unit}$
    22662264        void `g`( M & mutex m );
    2267         void h( M & mutex m ) { waitfor( `f`, m ) or waitfor( `g`, m ); }
     2265        void h( M & mutex m ) { waitfor( `f`, m ) or waitfor( `g`, m ); } $\C{// extending type M in this translation unit}$
    22682266\end{cfa}
    22692267The @waitfor@ statements in each translation unit cannot form a unique bit-mask because the monitor type does not carry that information.
    2270 Hence, function pointers are used to identify the functions listed in the @waitfor@ statement, stored in a variable-sized array,
     2268Hence, function pointers are used to identify the functions listed in the @waitfor@ statement, stored in a variable-sized array.
    22712269Then, the same implementation approach used for the urgent stack is used for the calling queue.
    22722270Each caller has a list of monitors acquired, and the @waitfor@ statement performs a (usually short) linear search matching functions in the @waitfor@ list with called functions, and then verifying the associated mutex locks can be transfers.
     
    22782276
    22792277External scheduling, like internal scheduling, becomes significantly more complex for multi-monitor semantics.
    2280 Even in the simplest case, new semantics needs to be established.
     2278Even in the simplest case, new semantics need to be established.
    22812279\begin{cfa}
    22822280monitor M { ... };
     
    25102508
    25112509For completeness and efficiency, \CFA provides a standard set of low-level locks: recursive mutex, condition, semaphore, barrier, \etc, and atomic instructions: @fetchAssign@, @fetchAdd@, @testSet@, @compareSet@, \etc.
    2512 However, we strongly advocate using high-level concurrency mechanisms whenever possible.
     2510Some of these low-level mechanism are used in the \CFA runtime, but we strongly advocate using high-level mechanisms whenever possible.
    25132511
    25142512
     
    25662564\label{s:RuntimeStructureCluster}
    25672565
    2568 A \newterm{cluster} is a collection of threads and virtual processors (abstract kernel-thread) that execute the threads from its own ready queue (like an OS).
     2566A \newterm{cluster} is a collection of threads and virtual processors (abstract kernel-thread) that execute the (user) threads from its own ready queue (like an OS executing kernel threads).
    25692567The purpose of a cluster is to control the amount of parallelism that is possible among threads, plus scheduling and other execution defaults.
    25702568The default cluster-scheduler is single-queue multi-server, which provides automatic load-balancing of threads on processors.
    2571 However, the scheduler is pluggable, supporting alternative schedulers, such as multi-queue multi-server, with work-stealing/sharing.
     2569However, the scheduler is pluggable, supporting alternative schedulers, such as multi-queue multi-server, with work-stealing/sharing across the virtual processors.
    25722570If several clusters exist, both threads and virtual processors, can be explicitly migrated from one cluster to another.
    25732571No automatic load balancing among clusters is performed by \CFA.
     
    25822580\label{s:RuntimeStructureProcessor}
    25832581
    2584 A virtual processor is implemented by a kernel thread (\eg UNIX process), which is subsequently scheduled for execution on a hardware processor by the underlying operating system.
     2582A virtual processor is implemented by a kernel thread (\eg UNIX process), which are scheduled for execution on a hardware processor by the underlying operating system.
    25852583Programs may use more virtual processors than hardware processors.
    25862584On a multiprocessor, kernel threads are distributed across the hardware processors resulting in virtual processors executing in parallel.
    25872585(It is possible to use affinity to lock a virtual processor onto a particular hardware processor~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which is used when caching issues occur or for heterogeneous hardware processors.)
    25882586The \CFA runtime attempts to block unused processors and unblock processors as the system load increases;
    2589 balancing the workload with processors is difficult.
     2587balancing the workload with processors is difficult because it requires future knowledge, \ie what will the applicaton workload do next.
    25902588Preemption occurs on virtual processors rather than user threads, via operating-system interrupts.
    25912589Thus virtual processors execute user threads, where preemption frequency applies to a virtual processor, so preemption occurs randomly across the executed user threads.
     
    26202618\subsection{Preemption}
    26212619
    2622 Nondeterministic preemption provides fairness from long running threads, and forces concurrent programmers to write more robust programs, rather than relying on section of code between cooperative scheduling to be atomic,
     2620Nondeterministic preemption provides fairness from long running threads, and forces concurrent programmers to write more robust programs, rather than relying on section of code between cooperative scheduling to be atomic.
    26232621A separate reason for not supporting preemption is that it significantly complicates the runtime system.
    26242622Preemption is normally handled by setting a count-down timer on each virtual processor.
     
    26472645There are two versions of the \CFA runtime kernel: debug and non-debug.
    26482646The debugging version has many runtime checks and internal assertions, \eg stack (non-writable) guard page, and checks for stack overflow whenever context switches occur among coroutines and threads, which catches most stack overflows.
    2649 After a program is debugged, the non-debugging version can be used to decrease space and increase performance.
     2647After a program is debugged, the non-debugging version can be used to significantly decrease space and increase performance.
    26502648
    26512649
     
    27062704The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine to force stack creation, the creation cost is artificially low.
    27072705
    2708 \newpage
    27092706\begin{multicols}{2}
    27102707\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
     
    29572954One solution is to offer various tuning options, allowing the scheduler to be adjusted to the requirements of the workload.
    29582955However, to be truly flexible, a pluggable scheduler is necessary.
    2959 Currently, the \CFA pluggable scheduler is too simple to handle complex scheduling, \eg quality of service and real-time, where the scheduler must interact with mutex objects to deal with issues like priority inversion.
     2956Currently, the \CFA pluggable scheduler is too simple to handle complex scheduling, \eg quality of service and real-time, where the scheduler must interact with mutex objects to deal with issues like priority inversion~\cite{Buhr00b}.
    29602957
    29612958\paragraph{Non-Blocking I/O}
     
    29902987\section{Acknowledgements}
    29912988
    2992 The authors would like to recognize the design assistance of Aaron Moss, Rob Schluntz and Andrew Beach on the features described in this paper.
     2989The authors would like to recognize the design assistance of Aaron Moss, Rob Schluntz, Andrew Beach and Michael Brooks on the features described in this paper.
    29932990Funding for this project has been provided by Huawei Ltd.\ (\url{http://www.huawei.com}). %, and Peter Buhr is partially funded by the Natural Sciences and Engineering Research Council of Canada.
    29942991
Note: See TracChangeset for help on using the changeset viewer.