Skip to content
Snippets Groups Projects
  • Florian Fischer's avatar
    1c538024
    Introduce waitfree workstealing · 1c538024
    Florian Fischer authored
    Waitfree work stealing is configured with the meson option
    'waitfree_work_stealing'.
    
    The retry logic is intentionally left in the Queues and not lifted to
    the scheduler to reuse the load of an unsuccessful CAS.
    
    Consider the following pseudo code examples:
    
    steal() -> bool:                       steal() -> res
      load                                   load
    loop:                                    if empty return EMPTY
      if empty return EMPTY                  cas
      cas                                    return cas ? STOLEN : LOST_RACE
      if not WAITFREE and not cas:
        goto loop                          outer():
      return cas ? STOLEN : LOST_RACE      loop:
                                             res = steal()
    outer():                                 if not WAITFREE and res == LOST_RACE:
      steal()                                  goto loop
    
    In the right example the value loaded by a possible unsuccessful CAS
    can not be reused. And a loop of unsuccessful CAS' will result in
    double loads.
    
    The retries are configurable through a template variable maxRetries.
    * maxRetries < 0: indefinitely retries
    * maxRetries >= 0: maxRetries
    1c538024
    History
    Introduce waitfree workstealing
    Florian Fischer authored
    Waitfree work stealing is configured with the meson option
    'waitfree_work_stealing'.
    
    The retry logic is intentionally left in the Queues and not lifted to
    the scheduler to reuse the load of an unsuccessful CAS.
    
    Consider the following pseudo code examples:
    
    steal() -> bool:                       steal() -> res
      load                                   load
    loop:                                    if empty return EMPTY
      if empty return EMPTY                  cas
      cas                                    return cas ? STOLEN : LOST_RACE
      if not WAITFREE and not cas:
        goto loop                          outer():
      return cas ? STOLEN : LOST_RACE      loop:
                                             res = steal()
    outer():                                 if not WAITFREE and res == LOST_RACE:
      steal()                                  goto loop
    
    In the right example the value loaded by a possible unsuccessful CAS
    can not be reused. And a loop of unsuccessful CAS' will result in
    double loads.
    
    The retries are configurable through a template variable maxRetries.
    * maxRetries < 0: indefinitely retries
    * maxRetries >= 0: maxRetries