Changeset 9a8dfcc for doc/proposals


Ignore:
Timestamp:
Nov 2, 2016, 3:55:08 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
fe84230
Parents:
955d9e43
Message:

updated concurrency proposal based on peter's review, up-to but not including internal scheduling

Location:
doc/proposals/concurrency
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • doc/proposals/concurrency/concurrency.tex

    r955d9e43 r9a8dfcc  
    192192
    193193        int ++?(counter_t & mutex this) {
    194                 return ++this->value;
    195         }
    196 
    197         void ?{}(int * this, counter_t & mutex cnt) {
     194                return ++this.value;
     195        }
     196
     197        void ?{}(int * this, counter_t & mutex cnt) { //need for mutex is platform dependent here
    198198                *this = (int)cnt;
    199199        }
    200200\end{lstlisting}
    201 \begin{tabular}{ c c }
    202 Thread 1 & Thread 2 \\
    203 \begin{lstlisting}
    204         void f(counter_t & mutex c) {
    205                 for(;;) {
    206                         sout | (int)c | endl;
    207                 }
    208         }
    209 \end{lstlisting} &\begin{lstlisting}
    210         void g(counter_t & mutex c) {
    211                 for(;;) {
    212                         ++c;
    213                 }
    214         }
    215 
     201
     202This simple counter offers an example of monitor usage. Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting :
     203\begin{center}
     204\begin{tabular}{c @{\hskip 0.35in} c @{\hskip 0.35in} c}
     205\begin{lstlisting}
     206        counter_t cnt;
     207
     208        thread 1 : cnt++;
     209        thread 2 : cnt++;
     210        thread 3 : cnt++;
     211          ...
     212        thread N : cnt++;
    216213\end{lstlisting}
    217214\end{tabular}
    218 \\
    219 
    220 
    221 This simple counter offers an example of monitor usage. Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting. \\
     215\end{center}
    222216
    223217These simple mutual exclusion semantics also naturally expand to multi-monitor calls.
     
    230224\end{lstlisting}
    231225
    232 This code acquires both locks before entering the critical section. In practice, writing multi-locking routines that can not lead to deadlocks can be very tricky. Having language level support for such feature is therefore a significant asset for \CFA. However, this does have significant repercussions relating to scheduling (see \ref{insched} and \ref{extsched}). Furthermore, the ability to acquire multiple monitors at the same time does incur a significant pitfall even without looking into scheduling. For example :
     226This code acquires both locks before entering the critical section. In practice, writing multi-locking routines that can not lead to deadlocks can be tricky. Having language support for such a feature is therefore a significant asset for \CFA. In the case presented above, \CFA guarantees that the order of aquisition will be consistent across calls to routines using the same monitors as arguments. However, since \CFA monitors use multi-acquiring locks users can effectively force the acquiring order. For example, notice which routines use \code{mutex}/\code{nomutex} and how this affects aquiring order :
    233227\begin{lstlisting}
    234228        void foo(A & mutex a, B & mutex a) {
     
    249243\end{lstlisting}
    250244
    251 Recursive mutex routine calls are allowed in \CFA but if not done carefully it can lead to nested monitor call problems~\cite{Lister77}. These problems which are a specific  implementation of the lock acquiring order problem. In the example above, the user uses implicit ordering in the case of function \code{bar} but explicit ordering in the case of \code{baz}. This subtle mistake can mean that calling these two functions concurrently will lead to deadlocks, depending on the implicit ordering matching the explicit ordering. As shown on several occasion\cit, there isn't really any solutions to this problem, users simply need to be carefull when acquiring multiple monitors at the same time.
     245Such a use will lead to nested monitor call problems~\cite{Lister77}, which are a specific implementation of the lock acquiring order problem. In the example above, the user uses implicit ordering in the case of function \code{foo} but explicit ordering in the case of \code{bar} and \code{baz}. This subtle mistake means that calling these routines concurrently may lead to deadlocks, depending on the implicit ordering matching the explicit ordering. As shown on several occasion\cit, solving this problems requires to :
     246\begin{enumerate}
     247        \item Dynamically track the monitor call order.
     248        \item Implement rollback semantics.
     249\end{enumerate}
     250
     251While the first requirement is already a significant constraint on the system, implementing a general rollback semantics in a C-like language is prohibitively complex \cit. In \CFA users simply need to be carefull when acquiring multiple monitors at the same time.
    252252
    253253% ######  ####### #######    #    ### #        #####
     
    268268
    269269\subsubsection{Implementation Details: Interaction with polymorphism}
    270 At first glance, interaction between monitors and \CFA's concept of polymorphism seem complexe to support. However, it can be reasoned that entry-point locking can solve most of the issues that could be present with polymorphism.
    271 
    272 First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore the main question is how to support \code{dtype} polymorphism. We must remember that monitors' main purpose is to ensure mutual exclusion when accessing shared data. This implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handle incomplete types (by definition) no \code{dtype} polymorphic routine can access shared data since the data would require knowledge about the type. Therefore the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines. With callsite-locking, this would require significant amount of work since any \code{dtype} routine could have to obtain some lock before calling a routine. However, with entry-point-locking calling a monitor routine becomes exactly the same as calling it from anywhere else.
     270At first glance, interaction between monitors and \CFA's concept of polymorphism seem complex to support. However, it can be reasoned that entry-point locking can solve most of the issues that could be present with polymorphism.
     271
     272First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines. \Gls{callsite-locking}\footnotemark would require a significant amount of work, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking}\footnotemark[\value{footnote}] calling a monitor routine becomes exactly the same as calling it from anywhere else.
     273\footnotetext{See glossary for a definition of \gls{callsite-locking} and \gls{entry-point-locking}}
    273274
    274275% ### #     # #######         #####   #####  #     # ####### ######
  • doc/proposals/concurrency/glossary.tex

    r955d9e43 r9a8dfcc  
    11\makeglossaries
     2
     3\longnewglossaryentry{callsite-locking}
     4{name={callsite-locking}}
     5{
     6Locking done by the calling routine. With this technique, a routine calling a monitor routine will aquire the monitor \emph{before} making the call to the actuall routine.
     7}
     8
     9\longnewglossaryentry{entry-point-locking}
     10{name={entry-point-locking}}
     11{
     12Locking done by the called routine. With this technique, a monitor routine called by another routine will aquire the monitor \emph{after} entering the routine body but prior to any other code.
     13}
     14
     15
    216\longnewglossaryentry{uthread}
    317{name={user-level thread}}
  • doc/proposals/concurrency/version

    r955d9e43 r9a8dfcc  
    1 0.5.104
     10.5.116
Note: See TracChangeset for help on using the changeset viewer.