Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision c4e3419c913cc3e198161a6921a1d91890265c0b) +++ doc/user/user.tex (revision 223ee0d8a1da9f8ea5c23bbe761b951ef4746e04) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Mon Feb 15 13:48:53 2021 -%% Update Count : 4452 +%% Last Modified On : Sun Mar 7 21:50:24 2021 +%% Update Count : 4574 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -4076,4 +4076,117 @@ +\subsection{Concurrent Stream Access} + +When a stream is shared by multiple threads, input or output characters can be intermixed or cause failure. +For example, if two threads execute the following: +\begin{cfa} +$\emph{thread\(_1\)}$ : sout | "abc " | "def "; +$\emph{thread\(_2\)}$ : sout | "uvw " | "xyz "; +\end{cfa} +possible outputs are: +\begin{cquote} +\begin{tabular}{@{}l|l|l|l|l@{}} +\begin{cfa} +abc def +uvw xyz +\end{cfa} +& +\begin{cfa} +abc uvw xyz +def +\end{cfa} +& +\begin{cfa} +uvw abc xyz def + +\end{cfa} +& +\begin{cfa} +abuvwc dexf +yz +\end{cfa} +& +\begin{cfa} +uvw abc def +xyz +\end{cfa} +\end{tabular} +\end{cquote} +Concurrent operations can even corrupt the internal state of the stream resulting in failure. +As a result, some form of mutual exclusion is required for concurrent stream access. + +A coarse-grained solution is to perform all stream operations via a single thread or within a monitor providing the necessary mutual exclusion for the stream. +A fine-grained solution is to have a lock for each stream, which is acquired and released around stream operations by each thread. +\CFA provides a fine-grained solution where a \Index{recursive lock} is acquired and released indirectly via a manipulator ©acquire© or instantiating an \Index{RAII} type specific for the kind of stream: ©osacquire©\index{ostream@©ostream©!osacquire@©osacquire©} for output streams and ©isacquire©\index{isacquire@©isacquire©}\index{istream@©istream©!isacquire@©isacquire©} for input streams. + +The common usage is manipulator ©acquire©\index{ostream@©ostream©!acquire@©acquire©} to lock a stream during a single cascaded I/O expression, where it should appear as the first item in a cascade list, \eg: +\begin{cfa} +$\emph{thread\(_1\)}$ : sout | @acquire@ | "abc " | "def "; // manipulator +$\emph{thread\(_2\)}$ : sout | @acquire@ | "uvw " | "xyz "; +\end{cfa} +Now, the order of the thread execution is still non-deterministic, but the output is constrained to two possible lines in either order. +\begin{cquote} +\def\VRfont{\fontfamily{pcr}\upshape\selectfont} +\begin{tabular}{@{}l|l@{}} +\begin{cfa} +abc def +uvw xyz +\end{cfa} +& +\begin{cfa} +uvw xyz +abc def +\end{cfa} +\end{tabular} +\end{cquote} +In summary, the stream lock is acquired by the ©acquire© manipulator and implicitly released at the end of the cascaded I/O expression ensuring all operations in the expression occur atomically. + +To lock a stream across multiple I/O operations, declare an instance of the appropriate ©osacquire© or ©isacquire© type to implicitly acquire and release the stream lock for the object's duration, \eg: +\begin{cfa} +{ // acquire sout for block duration + @osacquire@ acq = { sout }; $\C{// named stream locker}$ + sout | 1; + sout | @acquire@ | 2 | 3; $\C{// unnecessary, but ok to acquire and release again}$ + sout | 4; +} // implicitly release the lock when "acq" is deallocated +\end{cfa} +Note, the unnecessary ©acquire© manipulator works because the recursive stream-lock can be acquired/released multiple times by the owner thread. +Hence, calls to functions that also acquire a stream lock for their output do not result in \Index{deadlock}. + +The previous values written by threads 1 and 2 can be read in concurrently: +\begin{cfa} +{ // acquire sin lock for block duration + @isacquire acq = { sin };@ $\C{// named stream locker}$ + int x, y, z, w; + sin | x; + sin | @acquire@ | y | z; $\C{// unnecessary, but ok to acquire and release again}$ + sin | w; +} // implicitly release the lock when "acq" is deallocated +\end{cfa} +Again, the order of the reading threads is non-deterministic. +Note, non-deterministic reading is rare. + +\Textbf{WARNING:} The general problem of \Index{nested locking} can occur if routines are called in an I/O sequence that block, \eg: +\begin{cfa} +sout | @acquire@ | "data:" | rtn( mon ); $\C{// mutex call on monitor}$ +\end{cfa} +If the thread executing the I/O expression blocks in the monitor with the ©sout© lock, other threads writing to ©sout© also block until the thread holding the lock is unblocked and releases it. +This scenario can lead to \Index{deadlock}, if the thread that is going to unblock the thread waiting in the monitor first writes to ©sout© (deadly embrace). +To prevent nested locking, a simple precaution is to factor out the blocking call from the expression, \eg: +\begin{cfa} +int @data@ = rtn( mon ); +sout | acquire | "data:" | @data@; +\end{cfa} + +\Textbf{WARNING:} ©printf©\index{printf@©printf©}, ©scanf©\index{scanf@©scanf©} and their derivatives are unsafe when used with user-level threading, as in \CFA. +These stream routines use kernel-thread locking (©futex©\index{futex@©futex©}), which block kernel threads, to prevent interleaving of I/O. +However, the following simple example illustrates how a deadlock can occur (other complex scenarios are possible). +Assume a single kernel thread and two user-level threads calling ©printf©. +One user-level thread acquires the I/O lock and is time-sliced while performing ©printf©. +The other user-level thread then starts execution, calls ©printf©, and blocks the only kernel thread because it cannot acquire the I/O lock. +It does not help if the kernel lock is multiple acquisition, \ie, the lock owner can acquire it multiple times, because it then results in two user threads in the ©printf© critical section, corrupting the stream. + + +\begin{comment} \section{Types} @@ -4154,4 +4267,5 @@ process((int) s); // type is converted, no function is called \end{cfa} +\end{comment} @@ -4369,5 +4483,59 @@ \begin{table}[hbt] \centering -\input{../refrat/operidents} +\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}} +\begin{tabular}{@{}ll@{}} +©?[?]© & subscripting \impl{?[?]} \\ +©?()© & function call \impl{?()} \\ +©?++© & postfix increment \impl{?++} \\ +©?--© & postfix decrement \impl{?--} \\ +©++?© & prefix increment \impl{++?} \\ +©--?© & prefix decrement \impl{--?} \\ +©*?© & dereference \impl{*?} \\ +©+?© & unary plus \impl{+?} \\ +©-?© & arithmetic negation \impl{-?} \\ +©~?© & bitwise negation \impl{~?} \\ +©!?© & logical complement \impl{"!?} \\ +©?\?© & exponentiation \impl{?\?} \\ +©?*?© & multiplication \impl{?*?} \\ +©?/?© & division \impl{?/?} \\ +©?%?© & remainder \impl{?%?} \\ +\end{tabular} +& +\begin{tabular}{@{}ll@{}} +©?+?© & addition \impl{?+?} \\ +©?-?© & subtraction \impl{?-?} \\ +©?<>?© & right shift \impl{?>>?} \\ +©?=?© & greater than or equal \impl{?>=?} \\ +©?>?© & greater than \impl{?>?} \\ +©?==?© & equality \impl{?==?} \\ +©?!=?© & inequality \impl{?"!=?} \\ +©?&?© & bitwise AND \impl{?&?} \\ +©?^?© & exclusive OR \impl{?^?} \\ +©?|?© & inclusive OR \impl{?"|?} \\ + \\ + \\ +\end{tabular} +& +\begin{tabular}{@{}ll@{}} +©?=?© & simple assignment \impl{?=?} \\ +©?\=?© & exponentiation assignment \impl{?\=?} \\ +©?*=?© & multiplication assignment \impl{?*=?} \\ +©?/=?© & division assignment \impl{?/=?} \\ +©?%=?© & remainder assignment \impl{?%=?} \\ +©?+=?© & addition assignment \impl{?+=?} \\ +©?-=?© & subtraction assignment \impl{?-=?} \\ +©?<<=?© & left-shift assignment \impl{?<<=?} \\ +©?>>=?© & right-shift assignment \impl{?>>=?} \\ +©?&=?© & bitwise AND assignment \impl{?&=?} \\ +©?^=?© & exclusive OR assignment \impl{?^=?} \\ +©?|=?© & inclusive OR assignment \impl{?"|=?} \\ + \\ + \\ + \\ +\end{tabular} +\end{tabular} \caption{Operator Identifiers} \label{opids} @@ -6502,10 +6670,74 @@ \label{s:CFAKeywords} -\CFA introduces the following new keywords. +\CFA introduces the following new \Index{keyword}s, which cannot be used as identifiers. \begin{cquote} -\input{../refrat/keywords} +\begin{tabular}{@{}lllllll@{}} +\begin{tabular}{@{}l@{}} +\Indexc{basetypeof} \\ +\Indexc{choose} \\ +\Indexc{coroutine} \\ +\Indexc{disable} \\ +\end{tabular} +& +\begin{tabular}{@{}l@{}} +\Indexc{enable} \\ +\Indexc{exception} \\ +\Indexc{fallthrough} \\ +\Indexc{fallthru} \\ +\end{tabular} +& +\begin{tabular}{@{}l@{}} +\Indexc{finally} \\ +\Indexc{fixup} \\ +\Indexc{forall} \\ +\Indexc{generator} \\ +\end{tabular} +& +\begin{tabular}{@{}l@{}} +\Indexc{int128} \\ +\Indexc{monitor} \\ +\Indexc{mutex} \\ +\Indexc{one_t} \\ +\end{tabular} +& +\begin{tabular}{@{}l@{}} +\Indexc{report} \\ +\Indexc{suspend} \\ +\Indexc{throw} \\ +\Indexc{throwResume} \\ +\end{tabular} +& +\begin{tabular}{@{}l@{}} +\Indexc{trait} \\ +\Indexc{try} \\ +\Indexc{virtual} \\ +\Indexc{waitfor} \\ +\end{tabular} +& +\begin{tabular}{@{}l@{}} +\Indexc{when} \\ +\Indexc{with} \\ +\Indexc{zero_t} \\ + \\ +\end{tabular} +\end{tabular} \end{cquote} - +\CFA introduces the following new \Index{quasi-keyword}s, which can be used as identifiers. +\begin{cquote} +\begin{tabular}{@{}ll@{}} +\begin{tabular}{@{}l@{}} +\Indexc{catch} \\ +\Indexc{catchResume} \\ +\Indexc{finally} \\ +\end{tabular} +& +\begin{tabular}{@{}l@{}} +\Indexc{fixup} \\ +\Indexc{or} \\ +\Indexc{timeout} \\ +\end{tabular} +\end{tabular} +\end{cquote} \section{Standard Headers}