Index: doc/proposals/concurrency/concurrency.tex =================================================================== --- doc/proposals/concurrency/concurrency.tex (revision 955d9e436566fa359c379c3c89bde7042f54f089) +++ doc/proposals/concurrency/concurrency.tex (revision 9a8dfcc22a0cb55b65ad97ee728cfe06c2b62751) @@ -192,32 +192,26 @@ 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,5 +224,5 @@ \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,5 +243,11 @@ \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,7 +268,8 @@ \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}} % ### # # ####### ##### ##### # # ####### ###### Index: doc/proposals/concurrency/glossary.tex =================================================================== --- doc/proposals/concurrency/glossary.tex (revision 955d9e436566fa359c379c3c89bde7042f54f089) +++ doc/proposals/concurrency/glossary.tex (revision 9a8dfcc22a0cb55b65ad97ee728cfe06c2b62751) @@ -1,3 +1,17 @@ \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}} Index: doc/proposals/concurrency/version =================================================================== --- doc/proposals/concurrency/version (revision 955d9e436566fa359c379c3c89bde7042f54f089) +++ doc/proposals/concurrency/version (revision 9a8dfcc22a0cb55b65ad97ee728cfe06c2b62751) @@ -1,1 +1,1 @@ -0.5.104 +0.5.116