Changeset 223ee0d for doc/user


Ignore:
Timestamp:
Mar 7, 2021, 11:04:27 PM (7 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
a67279a
Parents:
67c6a47
Message:

add Concurrent Stream Access section, copy operator and keyword sections from refrat

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/user/user.tex

    r67c6a47 r223ee0d  
    1111%% Created On       : Wed Apr  6 14:53:29 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Mon Feb 15 13:48:53 2021
    14 %% Update Count     : 4452
     13%% Last Modified On : Sun Mar  7 21:50:24 2021
     14%% Update Count     : 4574
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
     
    40764076
    40774077
     4078\subsection{Concurrent Stream Access}
     4079
     4080When a stream is shared by multiple threads, input or output characters can be intermixed or cause failure.
     4081For example, if two threads execute the following:
     4082\begin{cfa}
     4083$\emph{thread\(_1\)}$ : sout | "abc " | "def ";
     4084$\emph{thread\(_2\)}$ : sout | "uvw " | "xyz ";
     4085\end{cfa}
     4086possible outputs are:
     4087\begin{cquote}
     4088\begin{tabular}{@{}l|l|l|l|l@{}}
     4089\begin{cfa}
     4090abc def
     4091uvw xyz
     4092\end{cfa}
     4093&
     4094\begin{cfa}
     4095abc uvw xyz
     4096def
     4097\end{cfa}
     4098&
     4099\begin{cfa}
     4100uvw abc xyz def
     4101
     4102\end{cfa}
     4103&
     4104\begin{cfa}
     4105abuvwc dexf
     4106yz
     4107\end{cfa}
     4108&
     4109\begin{cfa}
     4110uvw abc def
     4111xyz
     4112\end{cfa}
     4113\end{tabular}
     4114\end{cquote}
     4115Concurrent operations can even corrupt the internal state of the stream resulting in failure.
     4116As a result, some form of mutual exclusion is required for concurrent stream access.
     4117
     4118A 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.
     4119A fine-grained solution is to have a lock for each stream, which is acquired and released around stream operations by each thread.
     4120\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.
     4121
     4122The 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:
     4123\begin{cfa}
     4124$\emph{thread\(_1\)}$ : sout | @acquire@ | "abc " | "def ";   // manipulator
     4125$\emph{thread\(_2\)}$ : sout | @acquire@ | "uvw " | "xyz ";
     4126\end{cfa}
     4127Now, the order of the thread execution is still non-deterministic, but the output is constrained to two possible lines in either order.
     4128\begin{cquote}
     4129\def\VRfont{\fontfamily{pcr}\upshape\selectfont}
     4130\begin{tabular}{@{}l|l@{}}
     4131\begin{cfa}
     4132abc def
     4133uvw xyz
     4134\end{cfa}
     4135&
     4136\begin{cfa}
     4137uvw xyz
     4138abc def
     4139\end{cfa}
     4140\end{tabular}
     4141\end{cquote}
     4142In 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.
     4143
     4144To 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:
     4145\begin{cfa}
     4146{       // acquire sout for block duration
     4147        @osacquire@ acq = { sout };                             $\C{// named stream locker}$
     4148        sout | 1;
     4149        sout | @acquire@ | 2 | 3;                               $\C{// unnecessary, but ok to acquire and release again}$
     4150        sout | 4;
     4151}       // implicitly release the lock when "acq" is deallocated
     4152\end{cfa}
     4153Note, the unnecessary ©acquire© manipulator works because the recursive stream-lock can be acquired/released multiple times by the owner thread.
     4154Hence, calls to functions that also acquire a stream lock for their output do not result in \Index{deadlock}.
     4155
     4156The previous values written by threads 1 and 2 can be read in concurrently:
     4157\begin{cfa}
     4158{       // acquire sin lock for block duration
     4159        @isacquire acq = { sin };@                              $\C{// named stream locker}$
     4160        int x, y, z, w;
     4161        sin | x;
     4162        sin | @acquire@ | y | z;                                $\C{// unnecessary, but ok to acquire and release again}$
     4163        sin | w;
     4164}       // implicitly release the lock when "acq" is deallocated
     4165\end{cfa}
     4166Again, the order of the reading threads is non-deterministic.
     4167Note, non-deterministic reading is rare.
     4168
     4169\Textbf{WARNING:} The general problem of \Index{nested locking} can occur if routines are called in an I/O sequence that block, \eg:
     4170\begin{cfa}
     4171sout | @acquire@ | "data:" | rtn( mon );        $\C{// mutex call on monitor}$
     4172\end{cfa}
     4173If 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.
     4174This 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).
     4175To prevent nested locking, a simple precaution is to factor out the blocking call from the expression, \eg:
     4176\begin{cfa}
     4177int @data@ = rtn( mon );
     4178sout | acquire | "data:" | @data@;
     4179\end{cfa}
     4180
     4181\Textbf{WARNING:} ©printf©\index{printf@©printf©}, ©scanf©\index{scanf@©scanf©} and their derivatives are unsafe when used with user-level threading, as in \CFA.
     4182These stream routines use kernel-thread locking (©futex©\index{futex@©futex©}), which block kernel threads, to prevent interleaving of I/O.
     4183However, the following simple example illustrates how a deadlock can occur (other complex scenarios are possible).
     4184Assume a single kernel thread and two user-level threads calling ©printf©.
     4185One user-level thread acquires the I/O lock and is time-sliced while performing ©printf©.
     4186The other user-level thread then starts execution, calls ©printf©, and blocks the only kernel thread because it cannot acquire the I/O lock.
     4187It 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.
     4188
     4189
     4190\begin{comment}
    40784191\section{Types}
    40794192
     
    41544267process((int) s); // type is converted, no function is called
    41554268\end{cfa}
     4269\end{comment}
    41564270
    41574271
     
    43694483\begin{table}[hbt]
    43704484\centering
    4371 \input{../refrat/operidents}
     4485\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
     4486\begin{tabular}{@{}ll@{}}
     4487©?[?]©  & subscripting \impl{?[?]}                                      \\
     4488©?()©   & function call \impl{?()}                                      \\
     4489©?++©   & postfix increment \impl{?++}                          \\
     4490©?--©   & postfix decrement \impl{?--}                          \\
     4491©++?©   & prefix increment \impl{++?}                           \\
     4492©--?©   & prefix decrement \impl{--?}                           \\
     4493©*?©    & dereference \impl{*?}                                         \\
     4494©+?©    & unary plus \impl{+?}                                          \\
     4495©-?©    & arithmetic negation \impl{-?}                         \\
     4496©~?©    & bitwise negation \impl{~?}                            \\
     4497©!?©    & logical complement \impl{"!?}                         \\
     4498©?\?©   & exponentiation \impl{?\?}                                     \\
     4499©?*?©   & multiplication \impl{?*?}                                     \\
     4500©?/?©   & division \impl{?/?}                                           \\
     4501©?%?©   & remainder \impl{?%?}                                          \\
     4502\end{tabular}
     4503&
     4504\begin{tabular}{@{}ll@{}}
     4505©?+?©   & addition \impl{?+?}                                           \\
     4506©?-?©   & subtraction \impl{?-?}                                        \\
     4507©?<<?©  & left shift \impl{?<<?}                                        \\
     4508©?>>?©  & right shift \impl{?>>?}                                       \\
     4509©?<?©   & less than \impl{?<?}                                          \\
     4510©?<=?©  & less than or equal \impl{?<=?}                        \\
     4511©?>=?©  & greater than or equal \impl{?>=?}                     \\
     4512©?>?©   & greater than \impl{?>?}                                       \\
     4513©?==?©  & equality \impl{?==?}                                          \\
     4514©?!=?©  & inequality \impl{?"!=?}                                       \\
     4515©?&?©   & bitwise AND \impl{?&?}                                        \\
     4516©?^?©   & exclusive OR \impl{?^?}                                       \\
     4517©?|?©   & inclusive OR \impl{?"|?}                                      \\
     4518                                                                                                        \\
     4519                                                                                                        \\
     4520\end{tabular}
     4521&
     4522\begin{tabular}{@{}ll@{}}
     4523©?=?©   & simple assignment \impl{?=?}                          \\
     4524©?\=?©  & exponentiation assignment \impl{?\=?}         \\
     4525©?*=?©  & multiplication assignment \impl{?*=?}         \\
     4526©?/=?©  & division assignment \impl{?/=?}                       \\
     4527©?%=?©  & remainder assignment \impl{?%=?}                      \\
     4528©?+=?©  & addition assignment \impl{?+=?}                       \\
     4529©?-=?©  & subtraction assignment \impl{?-=?}            \\
     4530©?<<=?© & left-shift assignment \impl{?<<=?}            \\
     4531©?>>=?© & right-shift assignment \impl{?>>=?}           \\
     4532©?&=?©  & bitwise AND assignment \impl{?&=?}            \\
     4533©?^=?©  & exclusive OR assignment \impl{?^=?}           \\
     4534©?|=?©  & inclusive OR assignment \impl{?"|=?}          \\
     4535                                                                                                        \\
     4536                                                                                                        \\
     4537                                                                                                        \\
     4538\end{tabular}
     4539\end{tabular}
    43724540\caption{Operator Identifiers}
    43734541\label{opids}
     
    65026670\label{s:CFAKeywords}
    65036671
    6504 \CFA introduces the following new keywords.
     6672\CFA introduces the following new \Index{keyword}s, which cannot be used as identifiers.
    65056673
    65066674\begin{cquote}
    6507 \input{../refrat/keywords}
     6675\begin{tabular}{@{}lllllll@{}}
     6676\begin{tabular}{@{}l@{}}
     6677\Indexc{basetypeof}             \\
     6678\Indexc{choose}                 \\
     6679\Indexc{coroutine}              \\
     6680\Indexc{disable}                \\
     6681\end{tabular}
     6682&
     6683\begin{tabular}{@{}l@{}}
     6684\Indexc{enable}                 \\
     6685\Indexc{exception}              \\
     6686\Indexc{fallthrough}    \\
     6687\Indexc{fallthru}               \\
     6688\end{tabular}
     6689&
     6690\begin{tabular}{@{}l@{}}
     6691\Indexc{finally}                \\
     6692\Indexc{fixup}                  \\
     6693\Indexc{forall}                 \\
     6694\Indexc{generator}              \\
     6695\end{tabular}
     6696&
     6697\begin{tabular}{@{}l@{}}
     6698\Indexc{int128}                 \\
     6699\Indexc{monitor}                \\
     6700\Indexc{mutex}                  \\
     6701\Indexc{one_t}                  \\
     6702\end{tabular}
     6703&
     6704\begin{tabular}{@{}l@{}}
     6705\Indexc{report}                 \\
     6706\Indexc{suspend}                \\
     6707\Indexc{throw}                  \\
     6708\Indexc{throwResume}    \\
     6709\end{tabular}
     6710&
     6711\begin{tabular}{@{}l@{}}
     6712\Indexc{trait}                  \\
     6713\Indexc{try}                    \\
     6714\Indexc{virtual}                \\
     6715\Indexc{waitfor}                \\
     6716\end{tabular}
     6717&
     6718\begin{tabular}{@{}l@{}}
     6719\Indexc{when}                   \\
     6720\Indexc{with}                   \\
     6721\Indexc{zero_t}                 \\
     6722                                                \\
     6723\end{tabular}
     6724\end{tabular}
    65086725\end{cquote}
    6509 
     6726\CFA introduces the following new \Index{quasi-keyword}s, which can be used as identifiers.
     6727\begin{cquote}
     6728\begin{tabular}{@{}ll@{}}
     6729\begin{tabular}{@{}l@{}}
     6730\Indexc{catch}                  \\
     6731\Indexc{catchResume}    \\
     6732\Indexc{finally}                \\
     6733\end{tabular}
     6734&
     6735\begin{tabular}{@{}l@{}}
     6736\Indexc{fixup}                  \\
     6737\Indexc{or}                             \\
     6738\Indexc{timeout}                \\
     6739\end{tabular}
     6740\end{tabular}
     6741\end{cquote}
    65106742
    65116743\section{Standard Headers}
Note: See TracChangeset for help on using the changeset viewer.