Changeset 41ca6fa for doc/user/user.tex

Timestamp:

Mar 12, 2021, 11:14:36 PM (3 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

5f39135, b0d5c0c

Parents:

2d019af (diff), df65c0c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

• doc/user/user.tex (modified) (5 diffs)

doc/user/user.tex

@@ -11 +11 @@
 %% 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 +4076 @@
 
 
+\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 +4267 @@
 process((int) s); // type is converted, no function is called
 \end{cfa}
+\end{comment}
 
 
@@ -4369 +4483 @@
 \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{?-?}                                        \\
+©?<<?©  & left shift \impl{?<<?}                                        \\
+©?>>?©  & right shift \impl{?>>?}                                       \\
+©?<?©   & less than \impl{?<?}                                          \\
+©?<=?©  & less than or equal \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 +6670 @@
 \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}