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