Index: doc/theses/colby_parsons_MMAth/text/actors.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/actors.tex (revision 218685eb9d42b0280301c35db2a6b821bf042bc7) +++ doc/theses/colby_parsons_MMAth/text/actors.tex (revision 7ce70e2bb9fd3ca221c6984a10a1060acdf9cb7e) @@ -480,5 +480,5 @@ Each executor thread iterates over its own message queues until it finds one with messages. -At this point, the executor thread atomically \gls{gulp}s the queue, meaning it moves the contents of message queue to a local queue of the executor thread using a single atomic instruction. +At this point, the executor thread atomically \gls{gulp}s the queue, meaning it moves the contents of message queue to a local queue of the executor thread. An example of the queue gulping operation is shown in the right side of Figure \ref{f:gulp}, where a executor threads gulps queue 0 and begins to process it locally. This step allows an executor thread to process the local queue without any atomics until the next gulp. @@ -563,5 +563,5 @@ The outline for lazy-stealing by a thief is: select a victim, scan its queues once, and return immediately if a queue is stolen. The thief then returns to normal operation and conducts a regular scan over its own queues looking for work, where stolen work is placed at the end of the scan. -Hence, only one victim is affected and there is a reasonable delay between stealing events by scanning all the thief's ready queue looking for its own work. +Hence, only one victim is affected and there is a reasonable delay between stealing events as the thief will scan its ready queue looking for its own work before potentially stealing again. This lazy examination by the thief has a low perturbation cost for victims, while still finding work in a moderately loaded system. In all work-stealing algorithms, there is the pathological case where there is too little work and too many workers; @@ -572,7 +572,7 @@ 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. The complexity in the implementation is that victim gulping does not take the mailbox queue; -rather it atomically transfers the mailbox nodes to another list leaving the mailbox empty, \ie it unlinks the queue nodes from the top pointer leaving the original list empty. +rather it atomically transfers the mailbox nodes to another queue leaving the mailbox empty, as discussed in Section~\ref{s:executor}. Hence, the original mailbox is always available for new message deliveries. -However, this transfer logically subdivides the mailbox, and during this period, the mailbox cannot be stolen; +However, this transfer logically subdivides the mailbox into two separate queues, and during this period, the mailbox cannot be stolen; otherwise there are two threads simultaneously running messages on actors in the two parts of the mailbox queue. To solve this problem, an atomic gulp also marks the mailbox queue as subdivided, making it ineligible for stealing. @@ -592,12 +592,12 @@ work_queue ** worker_queues; $\C{// secondary array of work queues to allow for swapping}\CRT$ \end{cfa} -A send inserts a request at the end of a @mailboxes@. +A send inserts a request at the end of one of @mailboxes@. A steal swaps two pointers in @worker_queues@. Conceptually, @worker_queues@ represents the ownership relation between mailboxes and workers. Given $M$ workers and $N$ mailboxes, each worker owns a contiguous $M$/$N$ block of pointers in @worker_queues@. -When a worker gulps, it dereferences one of the pointers in its section of @worker_queues@ and then gulps from the queue it points at. +When a worker gulps, it dereferences one of the pointers in its section of @worker_queues@ and then gulps the queue from the mailbox it points at. To transfer ownership of a mailbox from one worker to another, a pointer from each of the workers' ranges are swapped. This structure provides near-complete separation of stealing and gulping/send operations. -As such, operations can happen on the queues independent of stealing, which avoids almost all contention between thief threads and victim threads. +As such, operations can happen on @mailboxes@ independent of stealing, which avoids almost all contention between thief threads and victim threads. \begin{figure} @@ -616,6 +616,6 @@ \item -scan the victim's $M$/$N$ range of @worker_queues@ and non-atomically checks each mail queue to see if it is eligible and non-empty. -If a match is found, the thief attempts to steal the queue by swapping the appropriate victim worker-queue pointer with an empty thief's pointer, where the pointers come from the victim's and thief's ranges, respectively. +scan the victim's $M$/$N$ range of @worker_queues@ and non-atomically checks each mailbox to see if it is eligible and non-empty. +If a match is found, the thief attempts to steal the mailbox by swapping the appropriate victim worker-queue pointer with an empty thief's pointer, where the pointers come from the victim's and thief's ranges, respectively. % The swap races to interchange the appropriate victim's mail-queue pointer with an empty mail-queue pointer in the thief's @worker_queues@ range. This swap can fail if another thief steals the queue, which is discussed further in Section~\ref{s:swap}. @@ -624,5 +624,5 @@ \item -stops searching after a successful queue steal, a failed queue steal, or all queues in the victim's range are examined. +stops searching after a successful mailbox steal, a failed mailbox steal, or all mailboxes in the victim's range are examined. The thief then resumes normal execution and ceases being a thief. Hence, it iterates over its own worker queues because new messages may have arrived during stealing, including ones in the potentially stolen queue. @@ -631,26 +631,25 @@ \subsection{Stealing Problem} - -Each queue access involving a thief is protected using spinlock @mutex_lock@ and contention among thieves should be low. -However, to achieve the goal of almost zero contention for the victim, it is necessary to remove this lock around the only critical section involving the victim. +Each queue access (send or gulp) involving any worker (thief or victim) is protected using spinlock @mutex_lock@. +However, to achieve the goal of almost zero contention for the victim, it is necessary that the thief does not acquire any queue spinlocks in the stealing protocol. The victim critical-section is gulping a queue, which involves two steps: \begin{cfa} temp = worker_queues[x]; // preemption and steal -transfer( temp->owned_queuem, temp->c_queue ); // @being_processed@ set in transfer with mutual exclusion -\end{cfa} -where @transfer@ moves the top point from @c_queue@ to @owned_queuem@ and sets the top pointer of @c_queue@ to @0p@ (null) to partition the mailbox. +transfer( local_queue, temp->c_queue ); // @being_processed@ set in transfer with mutual exclusion +\end{cfa} +where @transfer@ gulps the work from @c_queue@ to the victim's @local_queue@ and leaves @c_queue@ empty, partitioning the mailbox. Specifically, \begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt] \item -The victim must dereference its current queue pointer from @worker_queues@. -\item -The victim calls @transfer@ to gulp the queue. +The victim must dereference its current mailbox pointer from @worker_queues@. +\item +The victim calls @transfer@ to gulp from the mailbox. \end{enumerate} -If the victim is preempted after the dereference, a thief can steal the queue pointer before the victim calls @transfer@. -The thief then races ahead, transitions back to a victim, searches its mailbox queues, finds the stolen non-empty queue, and gulps it. -The original victim now restarts and gulps from the stolen queue pointed to by its dereference, even though the thief put an empty mailbox queue in place for the victim. -At this point, the victim and thief are possibly processing the same messages, which violates mutual exclusion and the message-ordering guarantee. -Preventing this race requires either a lock acquire or an atomic operation on the victim's fast-path to guarantee the victim's gulp retrieves the empty mailbox queue installed by the thief. +If the victim is preempted after the dereference, a thief can steal the mailbox pointer before the victim calls @transfer@. +The thief then races ahead, transitions back to a victim, searches its mailboxes, finds the stolen non-empty mailbox, and gulps its queue. +The original victim now continues and gulps from the stolen mailbox pointed to by its dereference, even though the thief has logically subdivided this mailbox by gulping it. +At this point, the mailbox has been subdivided a second time, and the victim and thief are possibly processing messages sent to the same actor, which violates mutual exclusion and the message-ordering guarantee. +Preventing this race requires either a lock acquire or an atomic operation on the victim's fast-path to guarantee the victim's mailbox dereferenced pointer is not stale. However, any form of locking here creates contention between thief and victim. @@ -667,19 +666,20 @@ % If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees. To resolve the race, each mailbox header stores a @being_processed@ flag that is atomically set when a queue is transferred. -The flag indicates that a queue is being processed by a worker and is reset once the local processing is finished. -If a worker, either victim or thief turned victim, attempts to gulp a queue and finds that the @being_processed@ flag is set, it does not gulp the queue and moves on to the next queue in its range. +The flag indicates that a mailbox has been gulped (logically subdivided) by a worker and the gulped queue is being processed locally. +The @being_processed@ flag is reset once the local processing is finished. +If a worker, either victim or thief turned victim, attempts to gulp from a mailbox and find the @being_processed@ flag set, it does not gulp and moves on to the next mailbox in its range. This resolves the race no matter the winner. -If the thief wins the race, it steals and gulps the queue, and the victim sees the flag set and skips gulping the queue. -If the victim wins the race, it gulps the queue, and the thief sees the flag set and skips gulping the queue. - -There is a final pathological case where the race occurs and is resolved with \emph{both} gulps occurring. +If the thief wins the race, it steals the mailbox and gulps, and the victim sees the flag set and skips gulping from the mailbox. +If the victim wins the race, it gulps from the mailbox, and the thief sees the flag set and does not gulp from the mailbox. + +There is a final case where the race occurs and is resolved with \emph{both} gulps occurring. Here, the winner of the race finishes processing the queue and resets the @being_processed@ flag. -Then the loser unblocks and completes its gulp by transferring a \emph{stolen queue} and atomically setting the @being_processed@ flag. -The loser is now processing messages from the winner's queue, which is safe because the winner ignores this queue as @being_processed@ is set. -The loser never attempts to process this stolen queue again because its next queue cycle sees the swapped queue from the thief (which may or may not be empty at this point). -This race is now the only source of contention between victim and thieve as they both try to acquire a lock on the same queue during a transfer. -In theory, this scenario can cascade across multiple workers all performing this sequence across multiple queues. +Then the loser unblocks and completes its gulp from the same mailbox and atomically sets the @being_processed@ flag. +The loser is now processing messages from a temporarily shared mailbox, which is safe because the winner will ignore this mailbox if it attempts another gulp, since @being_processed@ is set. +The victim never attempts to gulp from the stolen mailbox again because its next cycle sees the swapped mailbox from the thief (which may or may not be empty at this point). +This race is now the only source of contention between victim and thief as they both try to acquire a lock on the same queue during a transfer. However, the window for this race is extremely small, making this contention rare. -Furthermore, the chance of a cascading scenario across multiple workers is even rarer. +In theory, if this race occurs multiple times consecutively \ie a thief steals, dereferences stolen mailbox pointer, is interrupted and stolen from, etc., this scenario can cascade across multiple workers all attempting to gulp from one mailbox. +The @being_processed@ flag ensures correctness even in this case, and the chance of a cascading scenario across multiple workers is even rarer. % The rarity is why this mechanism is zero-victim-cost in practice but not in theory. By collecting statistics on failed gulps due to the @being_processed@ flag, this contention occurs $\approx$0.05\% of the time when a gulp occurs (1 in every 2000 gulps).