Changeset 9a8dfcc

Timestamp:

Nov 2, 2016, 3:55:08 PM (8 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, 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:

• concurrency.tex (modified) (4 diffs)
• glossary.tex (modified) (1 diff)
• version (modified) (1 diff)

doc/proposals/concurrency/concurrency.tex

@@ -192 +192 @@
 
         int ++?(counter_t & mutex this) {
-                return ++this->value;
-        }
-
-        void ?{}(int * this, counter_t & mutex cnt) {
+                return ++this.value;
+        }
+
+        void ?{}(int * this, counter_t & mutex cnt) { //need for mutex is platform dependent here
                 *this = (int)cnt;
         }
 \end{lstlisting}
-\begin{tabular}{ c c }
-Thread 1 & Thread 2 \\
-\begin{lstlisting}
-        void f(counter_t & mutex c) {
-                for(;;) {
-                        sout | (int)c | endl;
-                }
-        }
-\end{lstlisting} &\begin{lstlisting}
-        void g(counter_t & mutex c) {
-                for(;;) {
-                        ++c;
-                }
-        }
-
+
+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 :
+\begin{center}
+\begin{tabular}{c @{\hskip 0.35in} c @{\hskip 0.35in} c}
+\begin{lstlisting}
+        counter_t cnt;
+
+        thread 1 : cnt++;
+        thread 2 : cnt++;
+        thread 3 : cnt++;
+          ...
+        thread N : cnt++;
 \end{lstlisting}
 \end{tabular}
-\\
-
-
-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. \\
+\end{center}
 
 These simple mutual exclusion semantics also naturally expand to multi-monitor calls.
@@ -230 +224 @@
 \end{lstlisting}
 
-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 :
+This 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 :
 \begin{lstlisting}
         void foo(A & mutex a, B & mutex a) {
@@ -249 +243 @@
 \end{lstlisting}
 
-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.
+Such 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 :
+\begin{enumerate}
+        \item Dynamically track the monitor call order.
+        \item Implement rollback semantics.
+\end{enumerate}
+
+While 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.
 
 % ######  ####### #######    #    ### #        #####
@@ -268 +268 @@
 
 \subsubsection{Implementation Details: Interaction with polymorphism}
-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.
-
-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.
+At 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.
+
+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. 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.
+\footnotetext{See glossary for a definition of \gls{callsite-locking} and \gls{entry-point-locking}}
 
 % ### #     # #######         #####   #####  #     # ####### ######

doc/proposals/concurrency/glossary.tex

@@ -1 +1 @@
 \makeglossaries
+
+\longnewglossaryentry{callsite-locking}
+{name={callsite-locking}}
+{
+Locking 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.
+}
+
+\longnewglossaryentry{entry-point-locking}
+{name={entry-point-locking}}
+{
+Locking 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.
+}
+
+
 \longnewglossaryentry{uthread}
 {name={user-level thread}}

doc/proposals/concurrency/version

@@ -1 @@
-0.5.104
+0.5.116