HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_TaskExclusive.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_TaskExclusive.h (UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_TaskExclusive__
12 #define __UT_TaskExclusive__
13 
14 #include "UT_TaskState.h"
15 #include "UT_TaskArena.h"
16 
17 /// This is a lock-free implementation for exclusive task execution. That is,
18 /// a task which needs to be performed once (i.e. std::once). However, this
19 /// construct will allow TBB to recycle blocked tasks so they can be used for
20 /// other processing.
21 ///
22 /// This can be used as an alternate to a lock. If code underneath a lock
23 /// calls into TBB, this can lead to a deadlock since TBB can steal a child
24 /// task to complete a parent task outside the lock. This typically requires a
25 /// separate task arena. A lock will also block a thread, preventing it from
26 /// participating in other tasks.
27 ///
28 /// UT_TaskExclusive provides a good alternative, ensuring that only one thread
29 /// will execute the functor, and all other threads which wait for the functor
30 /// to finish will be allowed to participate in other computation (even to help
31 /// computing parallel tasks in the functor).
32 ///
33 /// The class is templated on a functor which is used to actually perform the
34 /// execution. The template functor needs to have a operator()() method.
35 ///
36 /// For example, given a single Object which has a deferredInitialize() method
37 /// that may get called from multiple threads: @code
38 /// class Object
39 /// {
40 /// UT_TaskExclusive<Object> myExclusive;
41 ///
42 /// public:
43 /// // Users call deferredInitialize when they want the object to be
44 /// // initialized. However, it's possible the object may need to be
45 /// // initialized by multiple threads. The object uses UT_TaskExclusive
46 /// // to ensure doInitialization() is only executed one time.
47 /// void deferredInitialize()
48 /// {
49 /// myExclusive.execute(*this);
50 /// }
51 /// void operator()()
52 /// {
53 /// // This method will only be called once, even if
54 /// // multiple threads invoke the deferredInitialize() method
55 /// // simultaneously.
56 /// doInitialization();
57 /// }
58 /// }
59 /// @endcode
60 /// If you have multiple methods that should only be called one time, you can
61 /// always create a nested object functor.
62 ///
63 /// If the functor is likely to create further tbb tasks, you can ensure these
64 /// tasks are run in their own task arena by setting @c run_in_task_arena to
65 /// true (the default).
66 ///
67 /// There's currently a race condition that can occur if two parents that are
68 /// in separate task arenas try to evaluate the task exclusive at the same
69 /// time. Until this issue gets properly resolved, in cases where this can
70 /// happen, please set @c use_spinlock to true. This will cause the blocked
71 /// parent tasks to spin, instead of trying to participate in other tasks.
72 template <class T>
74 {
75 public:
77  : myState()
78  {
79  }
80 
81  /// Execute the compute task. This will guarantee the function has been
82  /// run before the execute() function returns. However, no locking will be
83  /// done.
84  ///
85  /// If multiple threads try to call the function simultaneously, only one
86  /// function will run, while the other will yield its cycles to other
87  /// parallel tasks. When the first task completes, both threads will
88  /// return.
89  ///
90  /// If the functor is likely to create further tbb tasks, you can ensure
91  /// these tasks are run in their own task arena by setting @c
92  /// run_in_task_arena to true (the default). The primary reason for having
93  /// a separate task arena is that the if the functor creates further tasks,
94  /// and one of these tasks is also dependent on the task exclusive, this
95  /// can lead to a tbb deadlock (a tbb stack lock).
96  ///
97  /// There's currently a race condition that can occur if two parents that
98  /// are in separate task arenas try to evaluate the task exclusive at the
99  /// same time. Until this issue gets properly resolved, in cases where
100  /// this can happen, please set @c use_spinlock to true. This will cause
101  /// the blocked parent tasks to spin, instead of trying to participate in
102  /// other tasks.
103  void execute(T &func,
104  bool run_in_task_arena = true,
105  bool use_spinlock = false)
106  {
107  UT_TaskState::TaskStatus status = myState.tryMarkAsBusy();
108  if (status == UT_TaskState::DONE)
109  {
110  // The task has been run, so just return
111  return;
112  }
113 
114  // There may be several tasks that get started. Only one of them will
115  // call the functor.
116  Task *root = Task::createRoot(myState, func,
117  status == UT_TaskState::FREE,
118  run_in_task_arena,
119  use_spinlock);
120  Task::spawnRootAndWait(*root);
121  }
122 
123  /// Executes the compute task in this thread without any locking
124  /// or protection. Useful if the caller has already setup the
125  /// appropriate lock.
127  {
128  if (!hasRun())
129  {
130  func();
131  myState.markAsDoneNoThread();
132  }
133  }
134 
135  /// Resetting the exclusive task should only be done when there's no
136  /// possibility that any threads are trying to execute or relying on the
137  /// results of the computation.
138  void reset() { myState.reset(); }
139 
140  /// Test whether the function has been executed. This is thread-safe, but
141  /// doesn't count on other threads which may be in the process of running
142  /// it.
143  bool hasRun() const { return myState.isDone(); }
144 
145 private:
146  class Task : public UT_Task
147  {
148  public:
149  Task(UT_TaskState &state, T &func,
150  bool do_compute, bool use_arena, bool do_spinlock)
151  : myState(state)
152  , myFunc(func)
153  , myCompute(do_compute)
154  , myUseArena(use_arena)
155  , myEnableSpinLock(do_spinlock)
156  {
157  }
158  static Task *createRoot(UT_TaskState &state, T &func,
159  bool do_compute, bool use_arena,
160  bool do_spinlock)
161  {
162  return new (allocate_root()) Task(state, func,
163  do_compute, use_arena, do_spinlock);
164  }
165 
166  virtual UT_Task *run()
167  {
168  if (myCompute)
169  {
170  // I win and I get to run the compute function
171  if (myUseArena)
172  {
173  UT_TaskArena arena;
174  arena.execute(myFunc);
175  }
176  else
177  {
178  myFunc();
179  }
180  myState.markAsDone(*this);
181  }
182  else if (myState.relaxedLoadStatus() == UT_TaskState::BUSY)
183  {
184  if (myEnableSpinLock)
185  {
186  while (myState.relaxedLoadStatus() == UT_TaskState::BUSY)
188  return nullptr;
189  }
190  // Someone else is performing the computation, so
191  // a) Add a child task to this task (introducing a dependency)
192  // b) Add the child task to myState so it can be run when the
193  // compute is done... The child (wait task) isn't run
194  // until the compute is complete.
195  // c) Recycle my task so that it's put back on the TBB
196  // scheduler. When the child task is complete, this task
197  // will be run again, but the state will be marked as
198  // done, so we can return.
199 
200  // Increment the reference count 2 times
201  // - Once since I have a child
202  // - Once since I'm recycling myself
205  myState.addWaitingTask(*this);
207  return nullptr;
208  }
209  return nullptr;
210  }
211  UT_TaskState &myState;
212  T &myFunc;
213  bool myCompute;
214  bool myUseArena;
215  bool myEnableSpinLock;
216  };
217 
218  UT_TaskState myState;
219 };
220 
221 #endif
222 
void markAsDoneNoThread()
Non-threaded version of marking as done.
Definition: UT_TaskState.h:156
void execute(F &functor)
Definition: UT_TaskArena.h:35
Another thread is busy evaluating the node.
Definition: UT_TaskState.h:52
void reset()
Definition: UT_TaskState.h:63
void recycleAsSafeContinuation()
Definition: UT_Task.h:53
Thread has acquired responsibility to evaluate node.
Definition: UT_TaskState.h:51
void incrementRefCount()
Definition: UT_Task.h:40
bool isDone() const
Test whether the task state is marked as DONE.
Definition: UT_TaskState.h:70
void executeNoThread(T &func)
GLenum func
Definition: glcorearb.h:782
TaskStatus tryMarkAsBusy()
Definition: UT_TaskState.h:78
static void yield(bool higher_only=false)
bool hasRun() const
void execute(T &func, bool run_in_task_arena=true, bool use_spinlock=false)