Changeset 6d43cc57 for doc/papers


Ignore:
Timestamp:
Jun 22, 2018, 1:51:56 PM (6 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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, with_gc
Children:
3d56d15b
Parents:
999c700
Message:

more updates

Location:
doc/papers/concurrency
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/concurrency/Makefile

    r999c700 r6d43cc57  
    2020
    2121FIGURES = ${addsuffix .tex, \
    22 monitor \
    23 ext_monitor \
    2422int_monitor \
    2523dependency \
    … …  
    2725
    2826PICTURES = ${addsuffix .pstex, \
     27monitor \
     28ext_monitor \
    2929system \
    3030monitor_structs \
    … …  
    5959        dvips ${Build}/$< -o $@
    6060
    61 ${BASE}.dvi : Makefile ${Build} ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
    62                 annex/local.bib ../../bibliography/pl.bib
     61${BASE}.dvi : Makefile ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     62                annex/local.bib ../../bibliography/pl.bib | ${Build}
    6363        # Must have *.aux file containing citations for bibtex
    6464        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    65         ${BibTeX} ${Build}/${basename $@}
     65        -${BibTeX} ${Build}/${basename $@}
    6666        # Some citations reference others so run again to resolve these citations
    6767        ${LaTeX} ${basename $@}.tex
    68         ${BibTeX} ${Build}/${basename $@}
     68        -${BibTeX} ${Build}/${basename $@}
    6969        # Run again to finish citations
    7070        ${LaTeX} ${basename $@}.tex
    … …  
    7272## Define the default recipes.
    7373
    74 ${Build}:
     74${Build} :
    7575        mkdir -p ${Build}
    7676
    77 ${BASE}.out.ps: ${Build}
     77${BASE}.out.ps : | ${Build}
    7878        ln -fs ${Build}/Paper.out.ps .
    7979
    80 WileyNJD-AMA.bst:
     80WileyNJD-AMA.bst :
    8181        ln -fs ../AMA/AMA-stix/ama/WileyNJD-AMA.bst .
    8282
    83 %.tex : %.fig ${Build}
     83%.tex : %.fig | ${Build}
    8484        fig2dev -L eepic $< > ${Build}/$@
    8585
    86 %.ps : %.fig ${Build}
     86%.ps : %.fig | ${Build}
    8787        fig2dev -L ps $< > ${Build}/$@
    8888
    89 %.pstex : %.fig ${Build}
     89%.pstex : %.fig | ${Build}
    9090        fig2dev -L pstex $< > ${Build}/$@
    9191        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t

  • doc/papers/concurrency/Paper.tex

    r999c700 r6d43cc57  
    15371537External scheduling allows users to wait for events from other threads without concern of unrelated events occurring.
    15381538The mechnaism can be done in terms of control flow, \eg Ada @accept@ or \uC @_Accept@, or in terms of data, \eg Go channels.
    1539 Of course, both of these paradigms have their own strengths and weaknesses, but for this project, control-flow semantics was chosen to stay consistent with the rest of the languages semantics.
    1540 Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multiple-monitor routines.
    1541 The previous example shows a simple use @_Accept@ versus @wait@/@signal@ and its advantages.
    1542 Note that while other languages often use @accept@/@select@ as the core external scheduling keyword, \CFA uses @waitfor@ to prevent name collisions with existing socket \textbf{api}s.
     1539While both mechanisms have strengths and weaknesses, this project uses a control-flow mechanism to stay consistent with other language semantics.
     1540Two challenges specific to \CFA for external scheduling are loose object-definitions (see Section~\ref{s:LooseObjectDefinitions}) and multiple-monitor routines (see Section~\ref{s:Multi-MonitorScheduling}).
    15431541
    15441542For internal scheduling, non-blocking signalling (as in the producer/consumer example) is used when the signaller is providing the cooperation for a waiting thread;
    … …  
    16541652\end{cfa}
    16551653must have acquired monitor locks that are greater than or equal to the number of locks for the waiting thread signalled from the condition queue.
    1656 {\color{red}In general, the signaller does not know the order of waiting threads, so in general, it must acquire the maximum number of mutex locks for the worst-case waiting thread.}
    16571654
    16581655Similarly, for @waitfor( rtn )@, the default semantics is to atomically block the acceptor and release all acquired mutex types in the parameter list, \ie @waitfor( rtn, m1, m2 )@.
    … …  
    18541851The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.
    18551852Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.
    1856 
    1857 \subsubsection{Partial Signalling} \label{partial-sig}
    18581853\end{comment}
    18591854
    … …  
    19321927
    19331928\subsection{Loose Object Definitions}
    1934 
    1935 In \uC, a monitor class declaration includes an exhaustive list of monitor operations.
    1936 Since \CFA is not object oriented, monitors become both more difficult to implement and less clear for a user:
    1937 
    1938 \begin{cfa}
    1939 monitor A {};
    1940 
    1941 void f(A & mutex a);
    1942 void g(A & mutex a) {
    1943         waitfor(f); // Obvious which f() to wait for
    1944 }
    1945 
    1946 void f(A & mutex a, int); // New different F added in scope
    1947 void h(A & mutex a) {
    1948         waitfor(f); // Less obvious which f() to wait for
    1949 }
    1950 \end{cfa}
    1951 
    1952 Furthermore, external scheduling is an example where implementation constraints become visible from the interface.
    1953 Here is the cfa-code for the entering phase of a monitor:
    1954 \begin{center}
    1955 \begin{tabular}{l}
    1956 \begin{cfa}
    1957         if monitor is free
    1958                 enter
    1959         elif already own the monitor
    1960                 continue
    1961         elif monitor accepts me
    1962                 enter
    1963         else
    1964                 block
    1965 \end{cfa}
    1966 \end{tabular}
    1967 \end{center}
     1929\label{s:LooseObjectDefinitions}
     1930
     1931In an object-oriented programming-language, a class includes an exhaustive list of operations.
     1932However, new members can be added via static inheritance or dynaic members, \eg JavaScript~\cite{JavaScript}.
     1933Similarly, monitor routines can be added at any time in \CFA, making it less clear for programmers and more difficult to implement.
     1934\begin{cfa}
     1935monitor M {};
     1936void `f`( M & mutex m );
     1937void g( M & mutex m ) { waitfor( `f` ); }       $\C{// clear which f}$
     1938void `f`( M & mutex m, int );                           $\C{// different f}$
     1939void h( M & mutex m ) { waitfor( `f` ); }       $\C{// unclear which f}$
     1940\end{cfa}
     1941Hence, the cfa-code for the entering a monitor looks like:
     1942\begin{cfa}
     1943if ( $\textrm{\textit{monitor is free}}$ ) $\LstCommentStyle{// \color{red}enter}$
     1944else if ( $\textrm{\textit{already own monitor}}$ ) $\LstCommentStyle{// \color{red}continue}$
     1945else if ( $\textrm{\textit{monitor accepts me}}$ ) $\LstCommentStyle{// \color{red}enter}$
     1946else $\LstCommentStyle{// \color{red}block}$
     1947\end{cfa}
    19681948For the first two conditions, it is easy to implement a check that can evaluate the condition in a few instructions.
    1969 However, a fast check for @monitor accepts me@ is much harder to implement depending on the constraints put on the monitors.
    1970 Indeed, monitors are often expressed as an entry queue and some acceptor queue as in Figure~\ref{fig:ClassicalMonitor}.
     1949However, a fast check for \emph{monitor accepts me} is much harder to implement depending on the constraints put on the monitors.
     1950Figure~\ref{fig:ClassicalMonitor} shows monitors are often expressed as an entry (calling) queue, some acceptor queues, and an urgent stack/queue.
    19711951
    19721952\begin{figure}
    19731953\centering
    1974 \subfloat[Classical Monitor] {
     1954\subfloat[Classical monitor] {
    19751955\label{fig:ClassicalMonitor}
    1976 {\resizebox{0.45\textwidth}{!}{\input{monitor}}}
     1956{\resizebox{0.45\textwidth}{!}{\input{monitor.pstex_t}}}
    19771957}% subfloat
    1978 \qquad
    1979 \subfloat[bulk acquire Monitor] {
     1958\quad
     1959\subfloat[Bulk acquire monitor] {
    19801960\label{fig:BulkMonitor}
    1981 {\resizebox{0.45\textwidth}{!}{\input{ext_monitor}}}
     1961{\resizebox{0.45\textwidth}{!}{\input{ext_monitor.pstex_t}}}
    19821962}% subfloat
    1983 \caption{External Scheduling Monitor}
     1963\caption{Monitor Implementation}
     1964\label{f:MonitorImplementation}
    19841965\end{figure}
    19851966
    1986 There are other alternatives to these pictures, but in the case of the left picture, implementing a fast accept check is relatively easy.
    1987 Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (\eg 128) of mutex members.
    1988 This approach requires a unique dense ordering of routines with an upper-bound and that ordering must be consistent across translation units.
    1989 For OO languages these constraints are common, since objects only offer adding member routines consistently across translation units via inheritance.
    1990 However, in \CFA users can extend objects with mutex routines that are only visible in certain translation unit.
    1991 This means that establishing a program-wide dense-ordering among mutex routines can only be done in the program linking phase, and still could have issues when using dynamically shared objects.
    1992 
    1993 The alternative is to alter the implementation as in Figure~\ref{fig:BulkMonitor}.
    1994 Here, the mutex routine called is associated with a thread on the entry queue while a list of acceptable routines is kept separate.
    1995 Generating a mask dynamically means that the storage for the mask information can vary between calls to @waitfor@, allowing for more flexibility and extensions.
    1996 Storing an array of accepted routine pointers replaces the single instruction bitmask comparison with dereferencing a pointer followed by a linear search.
    1997 Furthermore, supporting nested external scheduling (\eg listing \ref{f:nest-ext}) may now require additional searches for the @waitfor@ statement to check if a routine is already queued.
    1998 
     1967For a fixed (small) number of mutex routines (\eg 128), the accept check reduces to a bitmask of allowed callers, which can be checked with a single instruction.
     1968This approach requires a unique dense ordering of routines with a small upper-bound and the ordering must be consistent across translation units.
     1969For object-oriented languages these constraints are common, but \CFA mutex routines can be added in any scope and are only visible in certain translation unit, precluding program-wide dense-ordering among mutex routines.
     1970
     1971Figure~\ref{fig:BulkMonitor} shows the \CFA monitor implementation.
     1972The mutex routine called is associated with each thread on the entry queue, while a list of acceptable routines is kept separately.
     1973The accepted list is a variable-sized array of accepted routine pointers, so the single instruction bitmask comparison is replaced by dereferencing a pointer followed by a linear search.
     1974
     1975\begin{comment}
    19991976\begin{figure}
    20001977\begin{cfa}[caption={Example of nested external scheduling},label={f:nest-ext}]
    … …  
    20201997In the end, the most flexible approach has been chosen since it allows users to write programs that would otherwise be  hard to write.
    20211998This decision is based on the assumption that writing fast but inflexible locks is closer to a solved problem than writing locks that are as flexible as external scheduling in \CFA.
    2022 
    2023 % ======================================================================
    2024 % ======================================================================
     1999\end{comment}
     2000
     2001
    20252002\subsection{Multi-Monitor Scheduling}
    2026 % ======================================================================
    2027 % ======================================================================
     2003\label{s:Multi-MonitorScheduling}
    20282004
    20292005External scheduling, like internal scheduling, becomes significantly more complex when introducing multi-monitor syntax.
    2030 Even in the simplest possible case, some new semantics needs to be established:
     2006Even in the simplest possible case, new semantics needs to be established:
    20312007\begin{cfa}
    20322008monitor M {};
    2033 
    2034 void f(M & mutex a);
    2035 
    2036 void g(M & mutex b, M & mutex c) {
    2037         waitfor(f); // two monitors M => unknown which to pass to f(M & mutex)
    2038 }
    2039 \end{cfa}
    2040 The obvious solution is to specify the correct monitor as follows:
    2041 
     2009void f( M & mutex m1 );
     2010void g( M & mutex m1, M & mutex m2 ) {
     2011        waitfor( f );                                                   $\C{// pass m1 or m2 to f?}$
     2012}
     2013\end{cfa}
     2014The solution is for the programmer to disambiguate:
     2015\begin{cfa}
     2016        waitfor( f, m2 );                                               $\C{// wait for call to f with argument m2}$
     2017\end{cfa}
     2018Routine @g@ has acquired both locks, so when routine @f@ is called, the lock for monitor @m2@ is passed from @g@ to @f@ (while @g@ still holds lock @m1@).
     2019This behaviour can be extended to the multi-monitor @waitfor@ statement.
    20422020\begin{cfa}
    20432021monitor M {};
    2044 
    2045 void f(M & mutex a);
    2046 
    2047 void g(M & mutex a, M & mutex b) {
    2048         // wait for call to f with argument b
    2049         waitfor(f, b);
    2050 }
    2051 \end{cfa}
    2052 This syntax is unambiguous.
    2053 Both locks are acquired and kept by @g@.
    2054 When routine @f@ is called, the lock for monitor @b@ is temporarily transferred from @g@ to @f@ (while @g@ still holds lock @a@).
    2055 This behaviour can be extended to the multi-monitor @waitfor@ statement as follows.
    2056 
    2057 \begin{cfa}
    2058 monitor M {};
    2059 
    2060 void f(M & mutex a, M & mutex b);
    2061 
    2062 void g(M & mutex a, M & mutex b) {
    2063         // wait for call to f with arguments a and b
    2064         waitfor(f, a, b);
    2065 }
    2066 \end{cfa}
    2067 
    2068 Note that the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired in the routine. @waitfor@ used in any other context is undefined behaviour.
     2022void f( M & mutex m1, M & mutex m2 );
     2023void g( M & mutex m1, M & mutex m2 ) {
     2024        waitfor( f, m1, m2 );                                   $\C{// wait for call to f with arguments m1 and m2}$
     2025}
     2026\end{cfa}
     2027Again, the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired by accepting routine.
    20692028
    20702029An important behaviour to note is when a set of monitors only match partially:
    2071 
    20722030\begin{cfa}
    20732031mutex struct A {};
    2074 
    20752032mutex struct B {};
    2076 
    2077 void g(A & mutex a, B & mutex b) {
    2078         waitfor(f, a, b);
    2079 }
    2080 
     2033void g( A & mutex m1, B & mutex m2 ) {
     2034        waitfor( f, m1, m2 );
     2035}
    20812036A a1, a2;
    20822037B b;
    2083 
    20842038void foo() {
    2085         g(a1, b); // block on accept
    2086 }
    2087 
     2039        g( a1, b ); // block on accept
     2040}
    20882041void bar() {
    2089         f(a2, b); // fulfill cooperation
     2042        f( a2, b ); // fulfill cooperation
    20902043}
    20912044\end{cfa}
    … …  
    20942047It is also important to note that in the case of external scheduling the order of parameters is irrelevant; @waitfor(f,a,b)@ and @waitfor(f,b,a)@ are indistinguishable waiting condition.
    20952048
    2096 % ======================================================================
    2097 % ======================================================================
     2049
    20982050\subsection{\protect\lstinline|waitfor| Semantics}
    2099 % ======================================================================
    2100 % ======================================================================
    21012051
    21022052Syntactically, the @waitfor@ statement takes a routine identifier and a set of monitors.
    … …  
    21972147\end{figure}
    21982148
    2199 % ======================================================================
    2200 % ======================================================================
     2149
    22012150\subsection{Waiting For The Destructor}
    2202 % ======================================================================
    2203 % ======================================================================
     2151
    22042152An interesting use for the @waitfor@ statement is destructor semantics.
    22052153Indeed, the @waitfor@ statement can accept any @mutex@ routine, which includes the destructor (see section \ref{data}).
    … …  
    22282176
    22292177
    2230 % ######     #    ######     #    #       #       ####### #       ###  #####  #     #
    2231 % #     #   # #   #     #   # #   #       #       #       #        #  #     # ##   ##
    2232 % #     #  #   #  #     #  #   #  #       #       #       #        #  #       # # # #
    2233 % ######  #     # ######  #     # #       #       #####   #        #   #####  #  #  #
    2234 % #       ####### #   #   ####### #       #       #       #        #        # #     #
    2235 % #       #     # #    #  #     # #       #       #       #        #  #     # #     #
    2236 % #       #     # #     # #     # ####### ####### ####### ####### ###  #####  #     #
    22372178\section{Parallelism}
     2179
    22382180Historically, computer performance was about processor speeds and instruction counts.
    22392181However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}.
    … …  
    22452187While there are many variations of the presented paradigms, most of these variations do not actually change the guarantees or the semantics, they simply move costs in order to achieve better performance for certain workloads.
    22462188
     2189
    22472190\section{Paradigms}
     2191
     2192
    22482193\subsection{User-Level Threads}
     2194
    22492195A direct improvement on the \textbf{kthread} approach is to use \textbf{uthread}.
    22502196These threads offer most of the same features that the operating system already provides but can be used on a much larger scale.
    … …  
    22552201Examples of languages that support \textbf{uthread} are Erlang~\cite{Erlang} and \uC~\cite{uC++book}.
    22562202
     2203
    22572204\subsection{Fibers : User-Level Threads Without Preemption} \label{fibers}
     2205
    22582206A popular variant of \textbf{uthread} is what is often referred to as \textbf{fiber}.
    22592207However, \textbf{fiber} do not present meaningful semantic differences with \textbf{uthread}.
    … …  
    22642212An example of a language that uses fibers is Go~\cite{Go}
    22652213
     2214
    22662215\subsection{Jobs and Thread Pools}
     2216
    22672217An approach on the opposite end of the spectrum is to base parallelism on \textbf{pool}.
    22682218Indeed, \textbf{pool} offer limited flexibility but at the benefit of a simpler user interface.
    … …  
    22752225The gold standard of this implementation is Intel's TBB library~\cite{TBB}.
    22762226
     2227
    22772228\subsection{Paradigm Performance}
     2229
    22782230While the choice between the three paradigms listed above may have significant performance implications, it is difficult to pin down the performance implications of choosing a model at the language level.
    22792231Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload.
    … …  
    22832235Finally, if the units of uninterrupted work are large, enough the paradigm choice is largely amortized by the actual work done.
    22842236
     2237
    22852238\section{The \protect\CFA\ Kernel : Processors, Clusters and Threads}\label{kernel}
     2239
    22862240A \textbf{cfacluster} is a group of \textbf{kthread} executed in isolation. \textbf{uthread} are scheduled on the \textbf{kthread} of a given \textbf{cfacluster}, allowing organization between \textbf{uthread} and \textbf{kthread}.
    22872241It is important that \textbf{kthread} belonging to a same \textbf{cfacluster} have homogeneous settings, otherwise migrating a \textbf{uthread} from one \textbf{kthread} to the other can cause issues.
    … …  
    22912245Currently \CFA only supports one \textbf{cfacluster}, the initial one.
    22922246
     2247
    22932248\subsection{Future Work: Machine Setup}\label{machine}
     2249
    22942250While this was not done in the context of this paper, another important aspect of clusters is affinity.
    22952251While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heterogeneous setups.
    … …  
    22972253OS support for CPU affinity is now common~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity.
    22982254
     2255
    22992256\subsection{Paradigms}\label{cfaparadigms}
     2257
    23002258Given these building blocks, it is possible to reproduce all three of the popular paradigms.
    23012259Indeed, \textbf{uthread} is the default paradigm in \CFA.
    … …  
    23052263
    23062264
    2307 
    23082265\section{Behind the Scenes}
     2266
    23092267There are several challenges specific to \CFA when implementing concurrency.
    23102268These challenges are a direct result of bulk acquire and loose object definitions.
    … …  
    23232281Note that since the major contributions of this paper are extending monitor semantics to bulk acquire and loose object definitions, any challenges that are not resulting of these characteristics of \CFA are considered as solved problems and therefore not discussed.
    23242282
    2325 % ======================================================================
    2326 % ======================================================================
     2283
    23272284\section{Mutex Routines}
    2328 % ======================================================================
    2329 % ======================================================================
    23302285
    23312286The first step towards the monitor implementation is simple @mutex@ routines.
    … …  
    23622317\end{figure}
    23632318
     2319
    23642320\subsection{Details: Interaction with polymorphism}
     2321
    23652322Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be more complex to support.
    23662323However, it is shown that entry-point locking solves most of the issues.
    … …  
    24422399Furthermore, entry-point locking requires less code generation since any useful routine is called multiple times but there is only one entry point for many call sites.
    24432400
    2444 % ======================================================================
    2445 % ======================================================================
     2401
    24462402\section{Threading} \label{impl:thread}
    2447 % ======================================================================
    2448 % ======================================================================
    24492403
    24502404Figure \ref{fig:system1} shows a high-level picture if the \CFA runtime system in regards to concurrency.
    … …  
    24592413\end{figure}
    24602414
     2415
    24612416\subsection{Processors}
     2417
    24622418Parallelism in \CFA is built around using processors to specify how much parallelism is desired. \CFA processors are object wrappers around kernel threads, specifically @pthread@s in the current implementation of \CFA.
    24632419Indeed, any parallelism must go through operating-system libraries.
    … …  
    24672423Processors internally use coroutines to take advantage of the existing context-switching semantics.
    24682424
     2425
    24692426\subsection{Stack Management}
     2427
    24702428One of the challenges of this system is to reduce the footprint as much as possible.
    24712429Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible.
    … …  
    24742432In order to respect C user expectations, the stack of the initial kernel thread, the main stack of the program, is used by the main user thread rather than the main processor, which can grow very large.
    24752433
     2434
    24762435\subsection{Context Switching}
     2436
    24772437As mentioned in section \ref{coroutine}, coroutines are a stepping stone for implementing threading, because they share the same mechanism for context-switching between different stacks.
    24782438To improve performance and simplicity, context-switching is implemented using the following assumption: all context-switches happen inside a specific routine call.
    … …  
    24882448This option is not currently present in \CFA, but the changes required to add it are strictly additive.
    24892449
     2450
    24902451\subsection{Preemption} \label{preemption}
     2452
    24912453Finally, an important aspect for any complete threading system is preemption.
    24922454As mentioned in section \ref{basics}, preemption introduces an extra degree of uncertainty, which enables users to have multiple threads interleave transparently, rather than having to cooperate among threads for proper scheduling and CPU distribution.
    … …  
    25222484Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel.
    25232485
     2486
    25242487\subsection{Scheduler}
    25252488Finally, an aspect that was not mentioned yet is the scheduling algorithm.
    … …  
    25272490Further discussion on scheduling is present in section \ref{futur:sched}.
    25282491
    2529 % ======================================================================
    2530 % ======================================================================
     2492
    25312493\section{Internal Scheduling} \label{impl:intsched}
    2532 % ======================================================================
    2533 % ======================================================================
     2494
    25342495The following figure is the traditional illustration of a monitor (repeated from page~\pageref{fig:ClassicalMonitor} for convenience):
    25352496
    25362497\begin{figure}
    25372498\begin{center}
    2538 {\resizebox{0.4\textwidth}{!}{\input{monitor}}}
     2499{\resizebox{0.4\textwidth}{!}{\input{monitor.pstex_t}}}
    25392500\end{center}
    25402501\caption{Traditional illustration of a monitor}

  • doc/papers/concurrency/figures/ext_monitor.fig

    r999c700 r6d43cc57  
    88-2
    991200 2
    10 5 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 3150.000 3450.000 3150 3150 2850 3450 3150 3750
    11 5 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 3150.000 4350.000 3150 4050 2850 4350 3150 4650
    12 6 5850 1950 6150 2250
    13 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2100 105 105 6000 2100 6105 2205
    14 4 1 -1 0 0 0 10 0.0000 2 105 90 6000 2160 d\001
     105 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 1575.000 3450.000 1575 3150 1275 3450 1575 3750
     115 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 1575.000 4350.000 1575 4050 1275 4350 1575 4650
     126 4275 1950 4575 2250
     131 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2100 105 105 4425 2100 4530 2205
     144 1 -1 0 0 0 10 0.0000 2 105 90 4425 2160 d\001
    1515-6
    16 6 5100 2100 5400 2400
    17 1 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 5250 2250 105 105 5250 2250 5355 2250
    18 4 1 -1 0 0 0 10 0.0000 2 105 120 5250 2295 X\001
     166 4275 1650 4575 1950
     171 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 1800 105 105 4425 1800 4530 1905
     184 1 -1 0 0 0 10 0.0000 2 105 90 4425 1860 b\001
    1919-6
    20 6 5100 1800 5400 2100
    21 1 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 5250 1950 105 105 5250 1950 5355 1950
    22 4 1 -1 0 0 0 10 0.0000 2 105 120 5250 2010 Y\001
     206 1495 5445 5700 5655
     211 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 1575 5550 80 80 1575 5550 1655 5630
     221 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 2925 5550 105 105 2925 5550 3030 5655
     231 3 0 1 -1 -1 0 0 4 0.000 1 0.0000 4425 5550 105 105 4425 5550 4530 5655
     244 0 -1 0 0 0 12 0.0000 2 135 1035 3150 5625 blocked task\001
     254 0 -1 0 0 0 12 0.0000 2 135 870 1725 5625 active task\001
     264 0 -1 0 0 0 12 0.0000 2 135 1050 4650 5625 routine mask\001
    2327-6
    24 6 5850 1650 6150 1950
    25 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 1800 105 105 6000 1800 6105 1905
    26 4 1 -1 0 0 0 10 0.0000 2 105 90 6000 1860 b\001
     286 3525 1800 3825 2400
     291 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 3675 1950 105 105 3675 1950 3780 1950
     302 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
     31         3525 1800 3825 1800 3825 2400 3525 2400 3525 1800
     324 1 4 0 0 0 10 0.0000 2 105 120 3675 2010 Y\001
    2733-6
    28 6 3070 5445 7275 5655
    29 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3150 5550 80 80 3150 5550 3230 5630
    30 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4500 5550 105 105 4500 5550 4605 5655
    31 1 3 0 1 -1 -1 0 0 4 0.000 1 0.0000 6000 5550 105 105 6000 5550 6105 5655
    32 4 0 -1 0 0 0 12 0.0000 2 135 1035 4725 5625 blocked task\001
    33 4 0 -1 0 0 0 12 0.0000 2 135 870 3300 5625 active task\001
    34 4 0 -1 0 0 0 12 0.0000 2 135 1050 6225 5625 routine mask\001
     346 3525 2100 3825 2400
     351 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 3675 2250 105 105 3675 2250 3780 2250
     364 1 4 0 0 0 10 0.0000 2 105 120 3675 2295 X\001
    3537-6
    36 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3300 3600 105 105 3300 3600 3405 3705
    37 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3600 3600 105 105 3600 3600 3705 3705
    38 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6600 3900 105 105 6600 3900 6705 4005
    39 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6900 3900 105 105 6900 3900 7005 4005
    40 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2700 105 105 6000 2700 6105 2805
    41 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2400 105 105 6000 2400 6105 2505
    42 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 5100 4575 80 80 5100 4575 5180 4655
     381 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 1725 3600 105 105 1725 3600 1830 3705
     391 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 2025 3600 105 105 2025 3600 2130 3705
     401 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5025 3900 105 105 5025 3900 5130 4005
     411 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5325 3900 105 105 5325 3900 5430 4005
     421 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2700 105 105 4425 2700 4530 2805
     431 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2400 105 105 4425 2400 4530 2505
     441 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3525 4575 80 80 3525 4575 3605 4655
    43452 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    44          4050 2925 5475 2925 5475 3225 4050 3225 4050 2925
     46         2475 2925 3900 2925 3900 3225 2475 3225 2475 2925
    45472 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
    46          3150 3750 3750 3750 3750 4050 3150 4050
     48         1575 3750 2175 3750 2175 4050 1575 4050
    47492 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 3
    48          3150 3450 3750 3450 3900 3675
     50         1575 3450 2175 3450 2325 3675
    49512 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2
    50          3750 3150 3600 3375
     52         2175 3150 2025 3375
    51532 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 3
    52          3150 4350 3750 4350 3900 4575
     54         1575 4350 2175 4350 2325 4575
    53552 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2
    54          3750 4050 3600 4275
     56         2175 4050 2025 4275
    55572 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
    56          3150 4650 3750 4650 3750 4950 4950 4950
     58         1575 4650 2175 4650 2175 4950 3375 4950
    57592 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2
    58          6450 3750 6300 3975
     60         4875 3750 4725 3975
    59612 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2
    60          4950 4950 5175 5100
     62         3375 4950 3600 5100
    61632 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 9
    62          5250 4950 6450 4950 6450 4050 7050 4050 7050 3750 6450 3750
    63          6450 2850 6150 2850 6150 1650
     64         3675 4950 4875 4950 4875 4050 5475 4050 5475 3750 4875 3750
     65         4875 2850 4575 2850 4575 1650
    64662 2 1 1 -1 -1 0 0 -1 4.000 0 0 0 0 0 5
    65          5850 4200 5850 3300 4350 3300 4350 4200 5850 4200
    66 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
     67         4275 4200 4275 3300 2775 3300 2775 4200 4275 4200
     682 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6769        1 1 1.00 60.00 120.00
    68         7 1 1.00 60.00 120.00
    69          5250 3150 5250 2400
     70         3675 3075 3675 2400
     712 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     72         4125 2850 4575 3000
    70732 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    71          3150 3150 3750 3150 3750 2850 5700 2850 5700 1650
    72 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    73          5700 2850 6150 3000
    74 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    75          5100 1800 5400 1800 5400 2400 5100 2400 5100 1800
    76 4 1 -1 0 0 0 10 0.0000 2 75 75 6000 2745 a\001
    77 4 1 -1 0 0 0 10 0.0000 2 75 75 6000 2445 c\001
    78 4 1 -1 0 0 0 12 0.0000 2 135 315 5100 5325 exit\001
    79 4 1 -1 0 0 0 12 0.0000 2 135 135 3300 3075 A\001
    80 4 1 -1 0 0 0 12 0.0000 2 135 795 3300 4875 condition\001
    81 4 1 -1 0 0 0 12 0.0000 2 135 135 3300 5100 B\001
    82 4 0 -1 0 0 0 12 0.0000 2 135 420 6600 3675 stack\001
    83 4 0 -1 0 0 0 12 0.0000 2 180 750 6600 3225 acceptor/\001
    84 4 0 -1 0 0 0 12 0.0000 2 180 750 6600 3450 signalled\001
    85 4 1 -1 0 0 0 12 0.0000 2 135 795 3300 2850 condition\001
    86 4 1 -1 0 0 0 12 0.0000 2 165 420 6000 1350 entry\001
    87 4 1 -1 0 0 0 12 0.0000 2 135 495 6000 1575 queue\001
    88 4 0 -1 0 0 0 12 0.0000 2 135 525 6300 2400 arrival\001
    89 4 0 -1 0 0 0 12 0.0000 2 135 630 6300 2175 order of\001
    90 4 1 -1 0 0 0 12 0.0000 2 135 525 5100 3675 shared\001
    91 4 1 -1 0 0 0 12 0.0000 2 135 735 5100 3975 variables\001
    92 4 0 0 50 -1 0 11 0.0000 2 165 855 4275 3150 Acceptables\001
    93 4 0 0 50 -1 0 11 0.0000 2 120 165 5775 2700 W\001
    94 4 0 0 50 -1 0 11 0.0000 2 120 135 5775 2400 X\001
    95 4 0 0 50 -1 0 11 0.0000 2 120 105 5775 2100 Z\001
    96 4 0 0 50 -1 0 11 0.0000 2 120 135 5775 1800 Y\001
     74         1575 3150 2175 3150 2175 2850 4125 2850 4125 1650
     754 1 -1 0 0 0 10 0.0000 2 75 75 4425 2745 a\001
     764 1 -1 0 0 0 10 0.0000 2 75 75 4425 2445 c\001
     774 1 -1 0 0 0 12 0.0000 2 135 315 3525 5325 exit\001
     784 1 -1 0 0 0 12 0.0000 2 135 135 1725 3075 A\001
     794 1 -1 0 0 0 12 0.0000 2 135 795 1725 4875 condition\001
     804 1 -1 0 0 0 12 0.0000 2 135 135 1725 5100 B\001
     814 0 -1 0 0 0 12 0.0000 2 135 420 5025 3675 stack\001
     824 0 -1 0 0 0 12 0.0000 2 180 750 5025 3225 acceptor/\001
     834 0 -1 0 0 0 12 0.0000 2 180 750 5025 3450 signalled\001
     844 1 -1 0 0 0 12 0.0000 2 135 795 1725 2850 condition\001
     854 1 -1 0 0 0 12 0.0000 2 165 420 4425 1350 entry\001
     864 1 -1 0 0 0 12 0.0000 2 135 495 4425 1575 queue\001
     874 0 -1 0 0 0 12 0.0000 2 135 525 4725 2400 arrival\001
     884 0 -1 0 0 0 12 0.0000 2 135 630 4725 2175 order of\001
     894 1 -1 0 0 0 12 0.0000 2 135 525 3525 3675 shared\001
     904 1 -1 0 0 0 12 0.0000 2 135 735 3525 3975 variables\001
     914 0 4 50 -1 0 11 0.0000 2 120 135 4150 1875 Y\001
     924 0 4 50 -1 0 11 0.0000 2 120 105 4150 2175 Z\001
     934 0 4 50 -1 0 11 0.0000 2 120 135 4150 2475 X\001
     944 0 4 50 -1 0 11 0.0000 2 120 165 4150 2775 W\001
     954 0 -1 0 0 3 12 0.0000 2 150 540 5025 4275 urgent\001
     964 1 0 50 -1 0 11 0.0000 2 165 600 3150 3150 accepted\001

  • doc/papers/concurrency/figures/monitor.fig

    r999c700 r6d43cc57  
    72722 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
    7373         3600 1500 3600 2100 4200 2100 4200 900
    74 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
    75          2700 1500 2700 2100 3300 2100 3300 1500
    76742 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 9
    7775         3600 4200 4800 4200 4800 3300 5400 3300 5400 3000 4800 3000
    … …  
    79772 2 1 1 -1 -1 0 0 -1 4.000 0 0 0 0 0 5
    8078         4200 3450 4200 2550 2700 2550 2700 3450 4200 3450
     792 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
     80         2700 1500 2700 2100 3300 2100 3300 1500
    81814 1 -1 0 0 0 10 0.0000 2 75 75 4350 1995 a\001
    82824 1 -1 0 0 0 10 0.0000 2 75 75 4350 1695 c\001
    … …  
    89894 0 -1 0 0 0 12 0.0000 2 180 750 4950 2700 signalled\001
    90904 1 -1 0 0 0 12 0.0000 2 135 795 1650 2100 condition\001
    91 4 1 -1 0 0 0 12 0.0000 2 135 135 2550 1425 X\001
    92 4 1 -1 0 0 0 12 0.0000 2 135 135 3450 1425 Y\001
     914 1 4 0 0 0 12 0.0000 2 135 135 2550 1425 X\001
     924 1 4 0 0 0 12 0.0000 2 135 135 3450 1425 Y\001
    93934 1 -1 0 0 0 12 0.0000 2 165 420 4350 600 entry\001
    94944 1 -1 0 0 0 12 0.0000 2 135 495 4350 825 queue\001
    … …  
    1001004 1 -1 0 0 0 10 0.0000 2 75 75 3450 1995 c\001
    1011014 1 -1 0 0 0 12 0.0000 2 135 570 3000 1200 queues\001
     1024 0 -1 0 0 3 12 0.0000 2 150 540 4950 3525 urgent\001
Note: See TracChangeset for help on using the changeset viewer.