condition_variable.h revision 72a454cd3513ac24fbdd0e0cb9ad70b86a99b801
1// Copyright (c) 2011 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5// ConditionVariable wraps pthreads condition variable synchronization or, on 6// Windows, simulates it. This functionality is very helpful for having 7// several threads wait for an event, as is common with a thread pool managed 8// by a master. The meaning of such an event in the (worker) thread pool 9// scenario is that additional tasks are now available for processing. It is 10// used in Chrome in the DNS prefetching system to notify worker threads that 11// a queue now has items (tasks) which need to be tended to. A related use 12// would have a pool manager waiting on a ConditionVariable, waiting for a 13// thread in the pool to announce (signal) that there is now more room in a 14// (bounded size) communications queue for the manager to deposit tasks, or, 15// as a second example, that the queue of tasks is completely empty and all 16// workers are waiting. 17// 18// USAGE NOTE 1: spurious signal events are possible with this and 19// most implementations of condition variables. As a result, be 20// *sure* to retest your condition before proceeding. The following 21// is a good example of doing this correctly: 22// 23// while (!work_to_be_done()) Wait(...); 24// 25// In contrast do NOT do the following: 26// 27// if (!work_to_be_done()) Wait(...); // Don't do this. 28// 29// Especially avoid the above if you are relying on some other thread only 30// issuing a signal up *if* there is work-to-do. There can/will 31// be spurious signals. Recheck state on waiting thread before 32// assuming the signal was intentional. Caveat caller ;-). 33// 34// USAGE NOTE 2: Broadcast() frees up all waiting threads at once, 35// which leads to contention for the locks they all held when they 36// called Wait(). This results in POOR performance. A much better 37// approach to getting a lot of threads out of Wait() is to have each 38// thread (upon exiting Wait()) call Signal() to free up another 39// Wait'ing thread. Look at condition_variable_unittest.cc for 40// both examples. 41// 42// Broadcast() can be used nicely during teardown, as it gets the job 43// done, and leaves no sleeping threads... and performance is less 44// critical at that point. 45// 46// The semantics of Broadcast() are carefully crafted so that *all* 47// threads that were waiting when the request was made will indeed 48// get signaled. Some implementations mess up, and don't signal them 49// all, while others allow the wait to be effectively turned off (for 50// a while while waiting threads come around). This implementation 51// appears correct, as it will not "lose" any signals, and will guarantee 52// that all threads get signaled by Broadcast(). 53// 54// This implementation offers support for "performance" in its selection of 55// which thread to revive. Performance, in direct contrast with "fairness," 56// assures that the thread that most recently began to Wait() is selected by 57// Signal to revive. Fairness would (if publicly supported) assure that the 58// thread that has Wait()ed the longest is selected. The default policy 59// may improve performance, as the selected thread may have a greater chance of 60// having some of its stack data in various CPU caches. 61// 62// For a discussion of the many very subtle implementation details, see the FAQ 63// at the end of condition_variable_win.cc. 64 65#ifndef BASE_SYNCHRONIZATION_CONDITION_VARIABLE_H_ 66#define BASE_SYNCHRONIZATION_CONDITION_VARIABLE_H_ 67#pragma once 68 69#include "build/build_config.h" 70 71#if defined(OS_WIN) 72#include <windows.h> 73#elif defined(OS_POSIX) 74#include <pthread.h> 75#endif 76 77#include "base/basictypes.h" 78#include "base/synchronization/lock.h" 79 80namespace base { 81 82class TimeDelta; 83 84class ConditionVariable { 85 public: 86 // Construct a cv for use with ONLY one user lock. 87 explicit ConditionVariable(Lock* user_lock); 88 89 ~ConditionVariable(); 90 91 // Wait() releases the caller's critical section atomically as it starts to 92 // sleep, and the reacquires it when it is signaled. 93 void Wait(); 94 void TimedWait(const TimeDelta& max_time); 95 96 // Broadcast() revives all waiting threads. 97 void Broadcast(); 98 // Signal() revives one waiting thread. 99 void Signal(); 100 101 private: 102 103#if defined(OS_WIN) 104 105 // Define Event class that is used to form circularly linked lists. 106 // The list container is an element with NULL as its handle_ value. 107 // The actual list elements have a non-zero handle_ value. 108 // All calls to methods MUST be done under protection of a lock so that links 109 // can be validated. Without the lock, some links might asynchronously 110 // change, and the assertions would fail (as would list change operations). 111 class Event { 112 public: 113 // Default constructor with no arguments creates a list container. 114 Event(); 115 ~Event(); 116 117 // InitListElement transitions an instance from a container, to an element. 118 void InitListElement(); 119 120 // Methods for use on lists. 121 bool IsEmpty() const; 122 void PushBack(Event* other); 123 Event* PopFront(); 124 Event* PopBack(); 125 126 // Methods for use on list elements. 127 // Accessor method. 128 HANDLE handle() const; 129 // Pull an element from a list (if it's in one). 130 Event* Extract(); 131 132 // Method for use on a list element or on a list. 133 bool IsSingleton() const; 134 135 private: 136 // Provide pre/post conditions to validate correct manipulations. 137 bool ValidateAsDistinct(Event* other) const; 138 bool ValidateAsItem() const; 139 bool ValidateAsList() const; 140 bool ValidateLinks() const; 141 142 HANDLE handle_; 143 Event* next_; 144 Event* prev_; 145 DISALLOW_COPY_AND_ASSIGN(Event); 146 }; 147 148 // Note that RUNNING is an unlikely number to have in RAM by accident. 149 // This helps with defensive destructor coding in the face of user error. 150 enum RunState { SHUTDOWN = 0, RUNNING = 64213 }; 151 152 // Internal implementation methods supporting Wait(). 153 Event* GetEventForWaiting(); 154 void RecycleEvent(Event* used_event); 155 156 RunState run_state_; 157 158 // Private critical section for access to member data. 159 base::Lock internal_lock_; 160 161 // Lock that is acquired before calling Wait(). 162 base::Lock& user_lock_; 163 164 // Events that threads are blocked on. 165 Event waiting_list_; 166 167 // Free list for old events. 168 Event recycling_list_; 169 int recycling_list_size_; 170 171 // The number of allocated, but not yet deleted events. 172 int allocation_counter_; 173 174#elif defined(OS_POSIX) 175 176 pthread_cond_t condition_; 177 pthread_mutex_t* user_mutex_; 178#if !defined(NDEBUG) 179 base::Lock* user_lock_; // Needed to adjust shadow lock state on wait. 180#endif 181 182#endif 183 184 DISALLOW_COPY_AND_ASSIGN(ConditionVariable); 185}; 186 187} // namespace base 188 189#endif // BASE_SYNCHRONIZATION_CONDITION_VARIABLE_H_ 190