Changeset 4487667 for doc/papers/concurrency/Paper.tex
- Timestamp:
- Jun 19, 2019, 9:07:55 AM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- f52ce6e
- Parents:
- a2a85658
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/concurrency/Paper.tex
ra2a85658 r4487667 1636 1636 For 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@. 1637 1637 1638 \newpage1639 1638 The next semantic decision is establishing which parameter \emph{types} may be qualified with @mutex@. 1640 1639 The following has monitor parameter types that are composed of multiple objects. … … 1735 1734 1736 1735 Users can still force the acquiring order by using @mutex@/\lstinline[morekeywords=nomutex]@nomutex@. 1737 \newpage1738 1736 \begin{cfa} 1739 1737 void foo( M & mutex m1, M & mutex m2 ); $\C{// acquire m1 and m2}$ … … 1746 1744 \end{cfa} 1747 1745 The 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 acquiredin opposite order, possibly resulting in deadlock.1746 The calls to @bar@ and @baz@ acquired the monitors in opposite order, possibly resulting in deadlock. 1749 1747 However, this case is the simplest instance of the \emph{nested-monitor problem}~\cite{Lister77}, where monitors are acquired in sequence versus bulk. 1750 1748 Detecting the nested-monitor problem requires dynamic tracking of monitor calls, and dealing with it requires rollback semantics~\cite{Dice10}. … … 1797 1795 % 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} 1798 1796 % \end{cquote} 1799 Furthermore, \CFA concurrency has no spurious wakeup~\cite[\S~9]{Buhr05a}, which eliminates an implicit form of barging.1797 Furthermore, \CFA concurrency has no spurious wakeup~\cite[\S~9]{Buhr05a}, which eliminates an implicit form of self barging. 1800 1798 Hence, a \CFA @wait@ statement is not enclosed in a @while@ loop retesting a blocking predicate, which can cause thread starvation due to barging. 1801 1799 1802 Figure~\ref{f:MonitorScheduling} shows internal/external scheduling (for the bounded-buffer example in Figure~\ref{f:InternalExternalScheduling}).1800 Figure~\ref{f:MonitorScheduling} shows general internal/external scheduling (for the bounded-buffer example in Figure~\ref{f:InternalExternalScheduling}). 1803 1801 External 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 .1802 Internal 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. 1805 1803 1806 1804 There 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.1805 Note, signalling cannot have the signaller and signalled thread in the monitor simultaneously because of the mutual exclusion so only one can proceed. 1808 1806 For internal scheduling, threads are unblocked from condition queues using @signal@, where the signallee is moved to urgent and the signaller continues (solid line). 1809 1807 Multiple signals move multiple signallees to urgent, until the condition is empty. … … 1818 1816 Executing multiple @waitfor@s from different signalled functions causes the calling threads to move to urgent. 1819 1817 External 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. 1818 Internal 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. 1819 If 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. 1820 We tried both a stack for @waitfor@ and queue for signalling, but that resulted in complex semantics about which thread enters next. 1821 Hence, \CFA uses a single urgent stack to correctly handle @waitfor@ and adequately support both forms of signalling. 1823 1822 1824 1823 \begin{figure} … … 1838 1837 \end{figure} 1839 1838 1840 Figure~\ref{f:BBInt} shows a \CFA generic bounded-buffer with internal scheduling, where producers/consumers enter the monitor, seethe buffer is full/empty, and block on an appropriate condition variable, @full@/@empty@.1839 Figure~\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@. 1841 1840 The @wait@ function atomically blocks the calling thread and implicitly releases the monitor lock(s) for all monitors in the function's parameter list. 1842 1841 The appropriate condition variable is signalled to unblock an opposite kind of thread after an element is inserted/removed from the buffer. … … 1962 1961 External 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. 1963 1962 If 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.1963 Calls 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. 1965 1964 Figure~\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@. 1966 1965 The writer does a similar action for each reader or writer using the resource. 1967 1966 Note, 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 .1967 External scheduling allows waiting for events from other threads while restricting unrelated events, that would otherwise have to wait on conditions in the monitor. 1969 1968 The 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. 1970 1969 While both mechanisms have strengths and weaknesses, this project uses the control-flow mechanism to be consistent with other language features. … … 1981 1980 Furthermore, 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. 1982 1981 Putting loops around the @wait@s does not correct the problem; 1983 the s olution must be restructured to account for barging.1982 the simple solution must be restructured to account for barging. 1984 1983 1985 1984 \begin{figure} … … 2049 2048 the 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. 2050 2049 The waiter unblocks next from the urgent queue, uses/takes the state, and exits the monitor. 2051 Blocking signal lingis the reverse, where the waiter is providing the cooperation for the signalling thread;2050 Blocking signal is the reverse, where the waiter is providing the cooperation for the signalling thread; 2052 2051 the 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. 2053 2052 The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to use/take the state. … … 2080 2079 While \CC supports bulk locking, @wait@ only accepts a single lock for a condition variable, so bulk locking with condition variables is asymmetric. 2081 2080 Finally, a signaller, 2082 \newpage2083 2081 \begin{cfa} 2084 2082 void baz( M & mutex m1, M & mutex m2 ) { … … 2086 2084 } 2087 2085 \end{cfa} 2088 must have acquired at least the same locks as the waiting thread signalled from the condition queue.2086 must 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. 2089 2087 2090 2088 Similarly, for @waitfor( rtn )@, the default semantics is to atomically block the acceptor and release all acquired mutex parameters, \ie @waitfor( rtn, m1, m2 )@. … … 2119 2117 The \emph{conditional-expression} of a @when@ may call a function, but the function must not block or context switch. 2120 2118 If 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.2119 If 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. 2122 2120 If there is a @timeout@ clause, it provides an upper bound on waiting. 2123 2121 If 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. … … 2162 2160 However, the basic @waitfor@ semantics do not support this functionality, since using an object after its destructor is called is undefined. 2163 2161 Therefore, 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 anidiomatic way to terminate a thread in \CFA.2162 Accepting the destructor is the idiomatic way to terminate a thread in \CFA. 2165 2163 2166 2164 … … 2256 2254 In 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@. 2257 2255 2258 In \CFA, monitor functions can be statically added/removed in translation units, so it is impossible to apply an $O(1)$ approach.2256 However, in \CFA, monitor functions can be statically added/removed in translation units, making a fast subset check difficult. 2259 2257 \begin{cfa} 2260 2258 monitor M { ... }; // common type, included in .h file … … 2263 2261 void g( M & mutex m ) { waitfor( `f`, m ); } 2264 2262 translation 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}$ 2266 2264 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}$ 2268 2266 \end{cfa} 2269 2267 The @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 ,2268 Hence, function pointers are used to identify the functions listed in the @waitfor@ statement, stored in a variable-sized array. 2271 2269 Then, the same implementation approach used for the urgent stack is used for the calling queue. 2272 2270 Each 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. … … 2278 2276 2279 2277 External scheduling, like internal scheduling, becomes significantly more complex for multi-monitor semantics. 2280 Even in the simplest case, new semantics need sto be established.2278 Even in the simplest case, new semantics need to be established. 2281 2279 \begin{cfa} 2282 2280 monitor M { ... }; … … 2510 2508 2511 2509 For 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 concurrencymechanisms whenever possible.2510 Some of these low-level mechanism are used in the \CFA runtime, but we strongly advocate using high-level mechanisms whenever possible. 2513 2511 2514 2512 … … 2566 2564 \label{s:RuntimeStructureCluster} 2567 2565 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).2566 A \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). 2569 2567 The purpose of a cluster is to control the amount of parallelism that is possible among threads, plus scheduling and other execution defaults. 2570 2568 The 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 .2569 However, the scheduler is pluggable, supporting alternative schedulers, such as multi-queue multi-server, with work-stealing/sharing across the virtual processors. 2572 2570 If several clusters exist, both threads and virtual processors, can be explicitly migrated from one cluster to another. 2573 2571 No automatic load balancing among clusters is performed by \CFA. … … 2582 2580 \label{s:RuntimeStructureProcessor} 2583 2581 2584 A virtual processor is implemented by a kernel thread (\eg UNIX process), which is subsequentlyscheduled for execution on a hardware processor by the underlying operating system.2582 A 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. 2585 2583 Programs may use more virtual processors than hardware processors. 2586 2584 On a multiprocessor, kernel threads are distributed across the hardware processors resulting in virtual processors executing in parallel. 2587 2585 (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.) 2588 2586 The \CFA runtime attempts to block unused processors and unblock processors as the system load increases; 2589 balancing the workload with processors is difficult .2587 balancing the workload with processors is difficult because it requires future knowledge, \ie what will the applicaton workload do next. 2590 2588 Preemption occurs on virtual processors rather than user threads, via operating-system interrupts. 2591 2589 Thus virtual processors execute user threads, where preemption frequency applies to a virtual processor, so preemption occurs randomly across the executed user threads. … … 2620 2618 \subsection{Preemption} 2621 2619 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 ,2620 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. 2623 2621 A separate reason for not supporting preemption is that it significantly complicates the runtime system. 2624 2622 Preemption is normally handled by setting a count-down timer on each virtual processor. … … 2647 2645 There are two versions of the \CFA runtime kernel: debug and non-debug. 2648 2646 The 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.2647 After a program is debugged, the non-debugging version can be used to significantly decrease space and increase performance. 2650 2648 2651 2649 … … 2706 2704 The 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. 2707 2705 2708 \newpage2709 2706 \begin{multicols}{2} 2710 2707 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} … … 2957 2954 One solution is to offer various tuning options, allowing the scheduler to be adjusted to the requirements of the workload. 2958 2955 However, 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 .2956 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~\cite{Buhr00b}. 2960 2957 2961 2958 \paragraph{Non-Blocking I/O} … … 2990 2987 \section{Acknowledgements} 2991 2988 2992 The authors would like to recognize the design assistance of Aaron Moss, Rob Schluntz and Andrew Beachon the features described in this paper.2989 The 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. 2993 2990 Funding 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. 2994 2991
Note: See TracChangeset
for help on using the changeset viewer.