# source:doc/proposals/concurrency/text/internals.tex@3364962

Last change on this file since 3364962 was 3364962, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

Updated concurrency draft and added new section for implementation.

• Property mode set to 100644
File size: 9.1 KB
Line
1
2\chapter{Behind the scene}
3
4
5% ======================================================================
6% ======================================================================
7\section{Implementation Details: Interaction with polymorphism}
8% ======================================================================
9% ======================================================================
10Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be complex to support. However, it is shown that entry-point locking solves most of the issues.
11
12First 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.
13
14Before looking into complex control-flow, it is important to present the difference between the two acquiring options : callsite and entry-point locking, i.e. acquiring the monitors before making a mutex routine call or as the first operation of the mutex routine-call. For example:
15\begin{figure}
16\label{fig:locking-site}
17\begin{center}
18\setlength\tabcolsep{1.5pt}
19\begin{tabular}{|c|c|c|}
20Mutex & \gls{callsite-locking} & \gls{entry-point-locking} \\
21call & pseudo-code & pseudo-code \\
22\hline
23\begin{cfacode}[tabsize=3]
24void foo(monitor& mutex a){
25
26        //Do Work
27        //...
28
29}
30
31void main() {
32        monitor a;
33
34        foo(a);
35
36}
37\end{cfacode} & \begin{pseudo}[tabsize=3]
38foo(& a) {
39
40        //Do Work
41        //...
42
43}
44
45main() {
46        monitor a;
47        acquire(a);
48        foo(a);
49        release(a);
50}
51\end{pseudo} & \begin{pseudo}[tabsize=3]
52foo(& a) {
53        acquire(a);
54        //Do Work
55        //...
56        release(a);
57}
58
59main() {
60        monitor a;
61
62        foo(a);
63
64}
65\end{pseudo}
66\end{tabular}
67\end{center}
68\caption{Callsite vs entry-point locking for mutex calls}
69\end{figure}
70
71
72Note the \code{mutex} keyword relies on the type system, which means that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait, which is possible because monitors are designed in terms a trait. For example:
73\begin{cfacode}
74//Incorrect: T is not a monitor
75forall(dtype T)
76void foo(T * mutex t);
77
78//Correct: this function only works on monitors (any monitor)
79forall(dtype T | is_monitor(T))
80void bar(T * mutex t));
81\end{cfacode}
82
83
84% ======================================================================
85% ======================================================================
86\section{Internal scheduling: Implementation} \label{inschedimpl}
87% ======================================================================
88% ======================================================================
89There are several challenges specific to \CFA when implementing internal scheduling. These challenges are direct results of \gls{bulk-acq} and loose object definitions. These two constraints are to root cause of most design decisions in the implementation of internal scheduling. Furthermore, to avoid the head-aches of dynamically allocating memory in a concurrent environment, the internal-scheduling design is entirely free of mallocs and other dynamic memory allocation scheme. This is to avoid the chicken and egg problem \cite{Chicken} of having a memory allocator that relies on the threading system and a threading system that relies on the runtime. This extra goal, means that memory management is a constant concern in the design of the system.
90
91The main memory concern for concurrency is queues. All blocking operations are made by parking threads onto queues. These queues need to be intrinsic\cit to avoid the need memory allocation. This entails that all the fields needed to keep track of all needed information. Since internal scheduling can use an unbound amount of memory (depending on \gls{bulk-acq}) statically defining information information in the intrusive fields of threads is insufficient. The only variable sized container that does not require memory allocation is the callstack, which is heavily used in the implementation of internal scheduling. Particularly the GCC extension variable length arrays which is used extensively.
92
93Since stack allocation is based around scope, the first step of the implementation is to identify the scopes that are available to store the information, and which of these can have a variable length. In the case of external scheduling, the threads and the condition both allow a fixed amount of memory to be stored, while mutex-routines and the actual blocking call allow for an unbound amount (though adding too much to the mutex routine stack size can become expansive faster).
94
95The following figure is the traditionnal illustration of a monitor :
96
97\begin{center}
98{\resizebox{0.4\textwidth}{!}{\input{monitor}}}
99\end{center}
100
101For \CFA, the previous picture does not have support for blocking multiple monitors on a single condition. To support \gls{bulk-acq} two changes to this picture are required. First, it doesn't make sense to tie the condition to a single monitor since blocking two monitors as one would require arbitrarily picking a monitor to hold the condition. Secondly, the object waiting on the conditions and AS-stack cannot simply contain the waiting thread since a single thread can potentially wait on multiple monitors. As mentionned in section \ref{inschedimpl}, the handling in multiple monitors is done by partially passing, which entails that each concerned monitor needs to have a node object. However, for waiting on the condition, since all threads need to wait together, a single object needs to be queued in the condition. Moving out the condition and updating the node types yields :
102
103\begin{center}
104{\resizebox{0.8\textwidth}{!}{\input{int_monitor}}}
105\end{center}
106
107\newpage
108
109This picture and the proper entry and leave algorithms is the fundamental implementation of internal scheduling.
110
111\begin{multicols}{2}
112Entry
113\begin{pseudo}[numbers=left]
114if monitor is free
115        enter
116elif I already own the monitor
117        continue
118else
119        block
120increment recursion
121
122\end{pseudo}
123\columnbreak
124Exit
125\begin{pseudo}[numbers=left, firstnumber=8]
126decrement recursion
127if recursion == 0
128        if signal_stack not empty
132
133        if entry queue not empty
135\end{pseudo}
136\end{multicols}
137
138Some important things to notice about the exit routine. The solution discussed in \ref{inschedimpl} can be seen on line 11 of the previous pseudo code. Basically, the solution boils down to having a seperate data structure for the condition queue and the AS-stack, and unconditionally transferring ownership of the monitors but only unblocking the thread when the last monitor has trasnferred ownership. This solution is safe as well as preventing any potential barging.
139
140% ======================================================================
141% ======================================================================
142\section{Implementation Details: External scheduling queues}
143% ======================================================================
144% ======================================================================
145To support multi-monitor external scheduling means that some kind of entry-queues must be used that is aware of both monitors. However, acceptable routines must be aware of the entry queues which means they must be stored inside at least one of the monitors that will be acquired. This in turn adds the requirement a systematic algorithm of disambiguating which queue is relavant regardless of user ordering. The proposed algorithm is to fall back on monitors lock ordering and specify that the monitor that is acquired first is the lock with the relevant entry queue. This assumes that the lock acquiring order is static for the lifetime of all concerned objects but that is a reasonable constraint. This algorithm choice has two consequences, the entry queue of the highest priority monitor is no longer a true FIFO queue and the queue of the lowest priority monitor is both required and probably unused. The queue can no longer be a FIFO queue because instead of simply containing the waiting threads in order arrival, they also contain the second mutex. Therefore, another thread with the same highest priority monitor but a different lowest priority monitor may arrive first but enter the critical section after a thread with the correct pairing. Secondly, since it may not be known at compile time which monitor will be the lowest priority monitor, every monitor needs to have the correct queues even though it is probable that half the multi-monitor queues will go unused for the entire duration of the program.
146
147
148\section{Internals}
149The complete mask can be pushed to any one, we are in a context where we already have full ownership of (at least) every concerned monitor and therefore monitors will refuse all calls no matter what.
Note: See TracBrowser for help on using the repository browser.