1// Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_THREAD_BARRIER_H_
6#define RUNTIME_VM_THREAD_BARRIER_H_
7
8#include "vm/globals.h"
9#include "vm/lockers.h"
10#include "vm/os_thread.h"
11
12namespace dart {
13
14// Thread barrier with:
15// * fixed (at construction) number n of participating threads {T1,T2,T3,...,Tn}
16// * unknown number of rounds.
17// Requirements:
18// * there is some R such that each participating thread makes
19// R calls to Sync() followed by its one and only call to Exit().
20// Guarantees:
21// * for any two threads Ti and Tj and round number r <= R,
22// everything done by Ti before its r'th call to Sync() happens before
23// everything done by Tj after its r'th call to Sync().
24// Note:
25// * it's not required that the thread that constructs the barrier participates.
26//
27// Example usage with 3 threads (1 controller + 2 workers) and 3 rounds:
28//
29// T1:
30// ThreadBarrier barrier(3);
31// Dart::thread_pool()->Run( T2:
32// new FooTask(&barrier)); fooSetup();
33// Dart::thread_pool()->Run( ... T3:
34// new BarTask(&barrier)); ... barSetup();
35// barrier.Sync(); barrier_->Sync(); barrier_->Sync();
36// /* Both tasks have finished setup */ ... ...
37// prepareWorkForTasks(); ... ...
38// barrier.Sync(); barrier_->Sync(); barrier_->Sync();
39// /* Idle while tasks are working */ fooWork(); barWork();
40// barrier.Sync(); barrier_->Sync(); barrier_->Sync();
41// collectResultsFromTasks(); barrier_->Exit(); barrier_->Exit();
42// barrier.Exit();
43//
44// Note that the calls to Sync() "line up" in time, but there is no such
45// guarantee for Exit().
46//
47class ThreadBarrier {
48 public:
49 explicit ThreadBarrier(intptr_t num_threads,
50 Monitor* monitor,
51 Monitor* done_monitor)
52 : num_threads_(num_threads),
53 monitor_(monitor),
54 remaining_(num_threads),
55 parity_(false),
56 done_monitor_(done_monitor),
57 done_(false) {
58 ASSERT(remaining_ > 0);
59 }
60
61 void Sync() {
62 MonitorLocker ml(monitor_);
63 ASSERT(remaining_ > 0);
64 if (--remaining_ > 0) {
65 // I'm not last to arrive; wait until next round.
66 bool old_parity = parity_;
67 while (parity_ == old_parity) {
68 ml.Wait();
69 }
70 } else {
71 // Last one to arrive initiates the next round.
72 remaining_ = num_threads_;
73 parity_ = !parity_;
74 // Tell everyone else about the new round.
75 ml.NotifyAll();
76 }
77 }
78
79 void Exit() {
80 bool last = false;
81 {
82 MonitorLocker ml(monitor_);
83 ASSERT(remaining_ > 0);
84 last = (--remaining_ == 0);
85 }
86 if (last) {
87 // Last one to exit sets done_.
88 MonitorLocker ml(done_monitor_);
89 ASSERT(!done_);
90 done_ = true;
91 // Tell the destructor in case it's already waiting.
92 ml.Notify();
93 }
94 }
95
96 ~ThreadBarrier() {
97 MonitorLocker ml(done_monitor_);
98 // Wait for everyone to exit before destroying the monitors.
99 while (!done_) {
100 ml.Wait();
101 }
102 ASSERT(remaining_ == 0);
103 }
104
105 private:
106 const intptr_t num_threads_;
107
108 Monitor* monitor_;
109 intptr_t remaining_;
110 bool parity_;
111
112 Monitor* done_monitor_; // TODO(koda): Try to optimize this away.
113 bool done_;
114
115 DISALLOW_COPY_AND_ASSIGN(ThreadBarrier);
116};
117
118} // namespace dart
119
120#endif // RUNTIME_VM_THREAD_BARRIER_H_
121