Changeset 1f39a28

Timestamp:

Jul 4, 2023, 4:57:48 PM (10 months ago)

Author:

caparsons <caparson@…>

Branches:

master

Children:

3883609

Parents:

3430ce8

Message:

reworked later part of actor stealing section

File:

• doc/theses/colby_parsons_MMAth/text/actors.tex (modified) (2 diffs)

doc/theses/colby_parsons_MMAth/text/actors.tex

@@ -630 +630 @@
 \end{enumerate}
 
-As mentioned, there is a race between a victim gulping and a thief stealing because gulping partitions a mailbox queue making it ineligible for stealing.
-Furthermore, after a thief steals, there is moment when victim gulps but the queue no longer 
+There is one last piece to the stealing puzzle.
+There are two steps to gulping a queue.
+First the victim must dereference its current queue pointer from @worker_queues@; then it calls @transfer@ which gulps the queue.
+If a thief steals the queue pointer after the victim dereferences it and before the victim calls @transfer@ (between the two steps), this poses a problem.
+The thief could potentially gulp from the queue and process it at the same time as the victim.
+This would violate both the mutual exclusion and the message ordering guarantees.
+Preventing this race from happening would require either a lock acquire or an atomic operation on the victim's fast-path.
+Either a lock or atomic operation here would be costly and would create contention between the thief and the victim; instead the implementation allows the race to occur and resolves the race lazily.
+% As mentioned, there is a race between a victim gulping and a thief stealing because gulping partitions a mailbox queue making it ineligible for stealing.
+% Furthermore, after a thief steals, there is moment when victim gulps but the queue no longer 
 % This algorithm largely eliminates contention among thieves and victims except for the rare moment when a victim/thief concurrently attempt to gulp/steal the same queue.
 % Restating, when a victim operates on a queue, it first copies the queue pointer from @worker_queues@ to a local variable (gulp).
@@ -640 +648 @@
 % These two gulps cannot be allowed to happen concurrently.
 % 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 avoid this race, each mailbox header stores a @being_processed@ flag that is atomically set to @true@ when a queue is gulped.
+To resolve the race, each mailbox header stores a @being_processed@ flag that is atomically set to @true@ when a queue is gulped.
 The flag indicates that a queue is being processed by a worker and is set back to @false@ once the local processing is finished.
 If a worker, either victim or thief, attempts to gulp a queue and finds that the @being_processed@ flag is @true@, it does not gulp the queue and moves on to the next queue in its range.
-This is a source of contention between victims and thieves since a thief may steal a queue and set @being_processed@ to @true@ between a victim saving a pointer to a queue and gulping it.
+This resolves the race no matter the winner.
+If the thief manages to steal a queue and gulp it first, the victim may see the flag up and skip gulping the queue.
+Alternatively, if the victim wins the race, the thief may see the flag up and skip gulping the queue.
+There is a final case where the race occurs and is resolved with no gulps skipped if the winner of the race finishes processing the queue before the loser attempts to gulp!
+This race consolidation is a source of contention between victims and thieves as they both may try to acquire a lock on the same queue.
 However, the window for this race is very small, making this contention rare.
 This is why this mechanism is zero-victim-cost in practice but not in theory.