Context Navigation

-                      r14c0f7b
+                      rf496046
 In more detail, the \CFA work-stealing algorithm begins by iterating over its message queues twice without finding any work before it tries to steal a queue from another worker.
 Stealing a queue is done wait-free (\ie no busy waiting) with a few atomic instructions that only create contention with other stealing workers not the victim.
+Stealing a queue is done atomically with a few atomic instructions that only create contention with other stealing workers not the victim.
 The complexity in the implementation is that victim gulping does not take the mailbox queue;
 rather it atomically transfers the mailbox nodes to another queue leaving the mailbox empty, as discussed in Section~\ref{s:executor}.
 …
 \subsection{Queue Pointer Swap}\label{s:swap}
 To atomically swap the two @worker_queues@ pointers during work stealing, a novel wait-free swap-algorithm is needed.
+To atomically swap the two @worker_queues@ pointers during work stealing, a novel atomic swap-algorithm is needed.
 The \gls{cas} is a read-modify-write instruction available on most modern architectures.
 It atomically compares two memory locations, and if the values are equal, it writes a new value into the first memory location.
 …
+}
 \end{cfa}
 and can swap two values, where the comparisons are superfluous.
+\gls{dcas} can be used to swap two values; for this use case the comparisons are superfluous.
 \begin{cfa}
 DCAS( x, y, x, y, y, x );
 \end{cfa}
 A restrictive form of \gls{dcas} can be simulated using \gls{ll}/\gls{sc}~\cite{Brown13} or more expensive transactional memory with the same progress property problems as LL/SC.
 (There is waning interest in transactional memory and it seems to be fading away.)
+% (There is waning interest in transactional memory and it seems to be fading away.)
 Similarly, very few architectures have a true memory/memory swap instruction (Motorola M68K, SPARC 32-bit).
 …
 Either a true memory/memory swap instruction or a \gls{dcas} would provide the ability to atomically swap two memory locations, but unfortunately neither of these instructions are supported on the architectures used in this work.
 Hence, a novel atomic swap for this use case is simulated, called \gls{dcasw}.
 The \gls{dcasw} is effectively a \gls{dcas} special cased in two ways:
+Hence, a novel atomic swap specific to the actor use case is simulated, called \gls{qpcas}.
+The \gls{qpcas} is effectively a \gls{dcas} special cased in a few ways:
 \begin{enumerate}
 \item
 It works on two separate memory locations, and hence, is logically the same as.
 \begin{cfa}
 bool DCASW( T * dst, T * src ) {
+bool QPCAS( T * dst, T * src ) {
         return DCAS( dest, src, *dest, *src, *src, *dest );
+}
 …
 The values swapped are never null pointers, so a null pointer can be used as an intermediate value during the swap.
 \end{enumerate}
 Figure~\ref{f:dcaswImpl} shows the \CFA pseudocode for the \gls{dcasw}.
+Figure~\ref{f:qpcasImpl} shows the \CFA pseudocode for the \gls{qpcas}.
 In detail, a thief performs the following steps to swap two pointers:
 \begin{enumerate}[start=0]
 …
 verifies the stored copy of the victim queue pointer, @vic_queue@, is valid.
 If @vic_queue@ is null, then the victim queue is part of another swap so the operation fails.
+No state has changed at this point so no fixup is needed.
+Note, @my_queue@ can never be equal to null at this point since thieves only set their own queues pointers to null when stealing.
+At no other point is a queue pointer set to null.
+Since each worker owns a disjoint range of the queue array, it is impossible for @my_queue@ to be null.
+Note, this algorithm is simplified due to each worker owning a disjoint range, allowing only the @vic_queue@ to be checked for null.
+This was not listed as a special case of this algorithm, since this requirement can be avoided by modifying Step 1 of Figure~\ref{f:dcaswImpl} to also check @my_queue@ for null.
+Further discussion of this generalization is omitted since it is not needed for the presented application.
+No state has changed at this point so the thief just returns.
+Note, thieves only set their own queues pointers to null when stealing, and queue pointers are not set to null anywhere else.
+As such, it is impossible for @my_queue@ to be null since each worker owns a disjoint range of the queue array.
+Hence, only @vic_queue@ is checked for null.
 \item
 attempts to atomically set the thief's queue pointer to null.
 …
 At this point, the thief-turned-victim fails, and since it has not changed any state, it just returns false.
 If the @CAS@ succeeds, the thief's queue pointer is now null.
+Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer, it is checked for null.
+Only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer, it is checked for null.
+A thief can only see the null queue pointer when looking for queues to steal or attempting a queue swap.
+If looking for queues, the thief will skip the null pointer, thus only the queue swap case needs to be considered for correctness.
 \item
 attempts to atomically set the victim's queue pointer to @my_queue@.
 …
 If the @CAS@ fails, the thief's queue pointer must be restored to its previous value before returning.
 \item
 set the thief's queue pointer to @vic_queue@ completing the swap.
+sets the thief's queue pointer to @vic_queue@ completing the swap.
 \end{enumerate}
 …
+}
 \end{cfa}
 \caption{DCASW Concurrent}
 \label{f:dcaswImpl}
+\caption{QPCAS Concurrent}
+\label{f:qpcasImpl}
 \end{figure}
 \begin{theorem}
 \gls{dcasw} is correct in both the success and failure cases.
+\gls{qpcas} is correct in both the success and failure cases.
 \end{theorem}
 To verify sequential correctness, Figure~\ref{f:seqSwap} shows a simplified \gls{dcasw}.
+To verify sequential correctness, Figure~\ref{f:seqSwap} shows a simplified \gls{qpcas}.
 Step 1 is missing in the sequential example since it only matters in the concurrent context.
 By inspection, the sequential swap copies each pointer being swapped, and then the original values of each pointer are reset using the copy of the other pointer.
 …
+}
 \end{cfa}
 \caption{DCASW Sequential}
+\caption{QPCAS Sequential}
 \label{f:seqSwap}
 \end{figure}
 To verify concurrent correctness, it is necessary to show \gls{dcasw} is wait-free, \ie all thieves fail or succeed in swapping the queues in a finite number of steps.
 This property is straightforward, because there are no locks or looping.
 As well, there is no retry mechanism in the case of a failed swap, since a failed swap either means the work is already stolen or that work is stolen from the thief.
 In both cases, it is apropos for a thief to give up stealing.
 The proof of correctness is shown through the existence of an invariant.
+% All thieves fail or succeed in swapping the queues in a finite number of steps.
+% This is straightforward, because there are no locks or looping.
+% As well, there is no retry mechanism in the case of a failed swap, since a failed swap either means the work is already stolen or that work is stolen from the thief.
+% In both cases, it is apropos for a thief to give up stealing.
+The concurrent proof of correctness is shown through the existence of an invariant.
 The invariant states when a queue pointer is set to @0p@ by a thief, then the next write to the pointer can only be performed by the same thief.
 To show that this invariant holds, it is shown that it is true at each step of the swap.
 …
 Once a thief atomically sets their queue pointer to be @0p@ in step 2, the invariant guarantees that that pointer does not change.
 In the success case of step 3, it is known the value of the victim's queue-pointer, which is not overwritten, must be @vic_queue@ due to the use of @CAS@.
 Given that the pointers all have unique memory locations, this first write of the successful swap is correct since it can only occur when the pointer has not changed.
+Given that the pointers all have unique memory locations (a pointer is never swapped with itself), this first write of the successful swap is correct since it can only occur when the pointer has not changed.
 By the invariant, the write back in the successful case is correct since no other worker can write to the @0p@ pointer.
 In the failed case of step 3, the outcome is correct in steps 1 and 2 since no writes have occurred so the program state is unchanged.
 Therefore, the program state is safely restored to the state it had prior to the @0p@ write in step 2, because the invariant makes the write back to the @0p@ pointer safe.
 Note that the assumption of the pointers having unique memory locations prevents the ABA problem in this usage of \gls{dcasw}, but it is not needed for correctness of the general \gls{dcasw} operation.
+Note that the pointers having unique memory locations prevents the ABA problem.
 \begin{comment}
 …
 First it is important to state that a thief does not attempt to steal from themselves.
 As such, the victim here is not also a thief.
 Stepping through the code in \ref{f:dcaswImpl}, for all thieves, steps 0-1 succeed since the victim is not stealing and has no queue pointers set to be @0p@.
+Stepping through the code in \ref{f:qpcasImpl}, for all thieves, steps 0-1 succeed since the victim is not stealing and has no queue pointers set to be @0p@.
 Similarly, for all thieves, step 2 succeed since no one is stealing from any of the thieves.
 In step 3, the first thief to @CAS@ wins the race and successfully swaps the queue pointer.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset f496046 for doc/theses/colby_parsons_MMAth/text/actors.tex

Legend:

doc/theses/colby_parsons_MMAth/text/actors.tex

Download in other formats: