Changeset 1f39a28
- Timestamp:
- Jul 4, 2023, 4:57:48 PM (20 months ago)
- Branches:
- master
- Children:
- 3883609
- Parents:
- 3430ce8
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/colby_parsons_MMAth/text/actors.tex
r3430ce8 r1f39a28 630 630 \end{enumerate} 631 631 632 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. 633 Furthermore, after a thief steals, there is moment when victim gulps but the queue no longer 632 There is one last piece to the stealing puzzle. 633 There are two steps to gulping a queue. 634 First the victim must dereference its current queue pointer from @worker_queues@; then it calls @transfer@ which gulps the queue. 635 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. 636 The thief could potentially gulp from the queue and process it at the same time as the victim. 637 This would violate both the mutual exclusion and the message ordering guarantees. 638 Preventing this race from happening would require either a lock acquire or an atomic operation on the victim's fast-path. 639 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. 640 % 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. 641 % Furthermore, after a thief steals, there is moment when victim gulps but the queue no longer 634 642 % 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. 635 643 % 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. 641 649 % If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees. 642 To avoid thisrace, each mailbox header stores a @being_processed@ flag that is atomically set to @true@ when a queue is gulped.650 To resolve the race, each mailbox header stores a @being_processed@ flag that is atomically set to @true@ when a queue is gulped. 643 651 The flag indicates that a queue is being processed by a worker and is set back to @false@ once the local processing is finished. 644 652 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. 645 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. 653 This resolves the race no matter the winner. 654 If the thief manages to steal a queue and gulp it first, the victim may see the flag up and skip gulping the queue. 655 Alternatively, if the victim wins the race, the thief may see the flag up and skip gulping the queue. 656 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! 657 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. 646 658 However, the window for this race is very small, making this contention rare. 647 659 This is why this mechanism is zero-victim-cost in practice but not in theory.
Note: See TracChangeset
for help on using the changeset viewer.