Changeset 6e1e2d0 for doc/theses/colby_parsons_MMAth/code

Timestamp:

May 1, 2023, 4:19:09 PM (22 months ago)

Author:

caparsons <caparson@…>

Branches:

ADT, ast-experimental, master

Children:

c083c3d

Parents:

a50fdfb (diff), 985b624 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

resolved merge conflicts

File:

• doc/theses/colby_parsons_MMAth/code/swap_queues.cfa (modified) (3 diffs)

doc/theses/colby_parsons_MMAth/code/swap_queues.cfa ¶

@@ -1 @@
-// this is a code stub and will not compile
-
-// tries to atomically swap two queues and returns 0p if the swap failed
-// returns ptr to newly owned queue if swap succeeds
-static inline work_queue * try_swap_queues( worker & this, unsigned int victim_idx, unsigned int my_idx ) with(this) {
+// sequential equivalent swap
+void swap( uint victim_idx, uint my_idx  ) {
+    // Step 0:
     work_queue * my_queue = request_queues[my_idx];
-    work_queue * other_queue = request_queues[victim_idx];
-
-    // if either queue is 0p then they are in the process of being stolen
-    if ( other_queue == 0p || my_queue == 0p ) return 0p;
-
-    // try to set our queue ptr to be 0p. If it fails someone moved our queue so return false
-    if ( !__atomic_compare_exchange_n( &request_queues[my_idx], &my_queue, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) )
-        return 0p;
-
-    // try to set other queue ptr to be our queue ptr. If it fails someone moved the other queue so fix up then return false
-    if ( !__atomic_compare_exchange_n( &request_queues[victim_idx], &other_queue, my_queue, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) {
-        /* paranoid */ verify( request_queues[my_idx] == 0p );
-        request_queues[my_idx] = my_queue; // reset my queue ptr back to appropriate val
-        return 0p;
-    }
-
-    // we have successfully swapped and since our queue is 0p no one will touch it so write back new queue ptr non atomically
-    request_queues[my_idx] = other_queue; // last write does not need to be atomic
-    return other_queue;
+    work_queue * vic_queue = request_queues[victim_idx];
+    // Step 2:
+    request_queues[my_idx] = 0p;
+    // Step 3:
+    request_queues[victim_idx] = my_queue;
+    // Step 4:
+    request_queues[my_idx] = vic_queue;
 }
 
@@ -35 +21 @@
 
 bool try_swap_queues( worker & this, uint victim_idx, uint my_idx ) with(this) {
+    // Step 0:
+    // request_queues is the shared array of all sharded queues
     work_queue * my_queue = request_queues[my_idx];
     work_queue * vic_queue = request_queues[victim_idx];
 
+    // Step 1:
     // If either queue is 0p then they are in the process of being stolen
     // 0p is CForAll's equivalent of C++'s nullptr
-    if ( vic_queue == 0p || my_queue == 0p ) return false;
+    if ( vic_queue == 0p ) return false;
 
-    // Try to set our queue ptr to be 0p.
-    // If this CAS fails someone moved our queue so return false
+    // Step 2:
+    // Try to set thief's queue ptr to be 0p.
+    // If this CAS fails someone stole thief's queue so return false
     if ( !CAS( &request_queues[my_idx], &my_queue, 0p ) )
         return false;
-
-    // Try to set other queue ptr to be our queue ptr.
-    // If it fails someone moved the other queue, so fix up then return false
+    
+    // Step 3:
+    // Try to set victim queue ptr to be thief's queue ptr.
+    // If it fails someone stole the other queue, so fix up then return false
     if ( !CAS( &request_queues[victim_idx], &vic_queue, my_queue ) ) {
         request_queues[my_idx] = my_queue; // reset queue ptr back to prev val
@@ -54 +45 @@
     }
 
+    // Step 4:
     // Successfully swapped.
-    // Our queue is 0p so no one will touch it so write back without CAS is safe
+    // Thief's ptr is 0p so no one will touch it
+    // Write back without CAS is safe
     request_queues[my_idx] = vic_queue;
     return true;