thread_pool.cc revision 2775ee4f82dff260663ca16adddc0b15327aaa42
11aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes/* 21aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * Copyright (C) 2012 The Android Open Source Project 31aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * 41aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * Licensed under the Apache License, Version 2.0 (the "License"); 51aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * you may not use this file except in compliance with the License. 61aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * You may obtain a copy of the License at 71aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * 81aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * http://www.apache.org/licenses/LICENSE-2.0 91aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * 101aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * Unless required by applicable law or agreed to in writing, software 111aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * distributed under the License is distributed on an "AS IS" BASIS, 121aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * See the License for the specific language governing permissions and 141aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * limitations under the License. 151aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes */ 161aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes 171aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes#include "thread_pool.h" 181aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes 191aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes#include "base/casts.h" 201aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes#include "base/stl_util.h" 210e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier#include "runtime.h" 220e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier#include "thread.h" 230e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 240e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiernamespace art { 250e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 26720ef7680573c1afd12f99f02eee3045daee5168Mathieu Chartierstatic constexpr bool kMeasureWaitTime = false; 2794c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier 280e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu ChartierThreadPoolWorker::ThreadPoolWorker(ThreadPool* thread_pool, const std::string& name, 290e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier size_t stack_size) 300e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier : thread_pool_(thread_pool), 310e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier name_(name), 320e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier stack_size_(stack_size) { 330e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier const char* reason = "new thread pool worker thread"; 34bcc2926b9721f94c17ed98fae5264cc98f0e066fBrian Carlstrom pthread_attr_t attr; 350e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier CHECK_PTHREAD_CALL(pthread_attr_init, (&attr), reason); 360e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier CHECK_PTHREAD_CALL(pthread_attr_setstacksize, (&attr, stack_size), reason); 370e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier CHECK_PTHREAD_CALL(pthread_create, (&pthread_, &attr, &Callback, this), reason); 380e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier CHECK_PTHREAD_CALL(pthread_attr_destroy, (&attr), reason); 390e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 400e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 410e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu ChartierThreadPoolWorker::~ThreadPoolWorker() { 420e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier CHECK_PTHREAD_CALL(pthread_join, (pthread_, NULL), "thread pool worker shutdown"); 430e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 440e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 450e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiervoid ThreadPoolWorker::Run() { 460e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier Thread* self = Thread::Current(); 4702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Task* task = NULL; 4835883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier thread_pool_->creation_barier_.Wait(self); 490e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier while ((task = thread_pool_->GetTask(self)) != NULL) { 500e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task->Run(self); 5102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier task->Finalize(); 520e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 530e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 540e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 550e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiervoid* ThreadPoolWorker::Callback(void* arg) { 560e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier ThreadPoolWorker* worker = reinterpret_cast<ThreadPoolWorker*>(arg); 570e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier Runtime* runtime = Runtime::Current(); 58664bebf92eb2151b9b570ccd42ac4b6056c3ea9cMathieu Chartier CHECK(runtime->AttachCurrentThread(worker->name_.c_str(), true, NULL, false)); 590e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // Do work until its time to shut down. 600e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier worker->Run(); 610e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier runtime->DetachCurrentThread(); 620e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier return NULL; 630e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 640e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 652ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid ThreadPool::AddTask(Thread* self, Task* task) { 660e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 670e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier tasks_.push_back(task); 680e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // If we have any waiters, signal one. 6994c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier if (started_ && waiting_count_ != 0) { 700e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task_queue_condition_.Signal(self); 710e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 720e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 730e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 740e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu ChartierThreadPool::ThreadPool(size_t num_threads) 750e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier : task_queue_lock_("task queue lock"), 760e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task_queue_condition_("task queue condition", task_queue_lock_), 770e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier completion_condition_("task completion condition", task_queue_lock_), 780e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier started_(false), 790e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier shutting_down_(false), 8035883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier waiting_count_(0), 81d914eb2a839f7b40156ff0299a60e5cb80080b73Ian Rogers start_time_(0), 82d914eb2a839f7b40156ff0299a60e5cb80080b73Ian Rogers total_wait_time_(0), 8335883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier // Add one since the caller of constructor waits on the barrier too. 842775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier creation_barier_(num_threads + 1), 852775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier max_active_workers_(num_threads) { 8635883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier Thread* self = Thread::Current(); 870e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier while (GetThreadCount() < num_threads) { 8802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const std::string name = StringPrintf("Thread pool worker %zu", GetThreadCount()); 8902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier threads_.push_back(new ThreadPoolWorker(this, name, ThreadPoolWorker::kDefaultStackSize)); 900e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 9135883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier // Wait for all of the threads to attach. 9235883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier creation_barier_.Wait(self); 930e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 940e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 952775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartiervoid ThreadPool::SetMaxActiveWorkers(size_t threads) { 962775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier MutexLock mu(Thread::Current(), task_queue_lock_); 972775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier CHECK_LE(threads, GetThreadCount()); 982775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier max_active_workers_ = threads; 992775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier} 1002775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier 1010e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu ChartierThreadPool::~ThreadPool() { 102e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier { 103e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier Thread* self = Thread::Current(); 104e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier MutexLock mu(self, task_queue_lock_); 105e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier // Tell any remaining workers to shut down. 106e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier shutting_down_ = true; 107e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier // Broadcast to everyone waiting. 108e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier task_queue_condition_.Broadcast(self); 10902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier completion_condition_.Broadcast(self); 110e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier } 1110e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // Wait for the threads to finish. 1120e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier STLDeleteElements(&threads_); 1130e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1140e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1150e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiervoid ThreadPool::StartWorkers(Thread* self) { 1160e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 1170e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier started_ = true; 1180e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task_queue_condition_.Broadcast(self); 11902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier start_time_ = NanoTime(); 12002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier total_wait_time_ = 0; 1210e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1220e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1230e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiervoid ThreadPool::StopWorkers(Thread* self) { 1240e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 1250e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier started_ = false; 1260e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1270e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 12802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierTask* ThreadPool::GetTask(Thread* self) { 1290e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 13002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while (!IsShuttingDown()) { 1312775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier const size_t thread_count = GetThreadCount(); 1322775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier // Ensure that we don't use more threads than the maximum active workers. 1332775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier const size_t active_threads = thread_count - waiting_count_; 1342775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier // <= since self is considered an active worker. 1352775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier if (active_threads <= max_active_workers_) { 1362775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier Task* task = TryGetTaskLocked(self); 1372775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier if (task != NULL) { 1382775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier return task; 1392775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier } 1400e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 1410e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1422775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier ++waiting_count_; 1430e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier if (waiting_count_ == GetThreadCount() && tasks_.empty()) { 1440e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // We may be done, lets broadcast to the completion condition. 1450e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier completion_condition_.Broadcast(self); 1460e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 14794c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier const uint64_t wait_start = kMeasureWaitTime ? NanoTime() : 0; 1480e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task_queue_condition_.Wait(self); 14994c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier if (kMeasureWaitTime) { 15094c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier const uint64_t wait_end = NanoTime(); 15194c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier total_wait_time_ += wait_end - std::max(wait_start, start_time_); 15294c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier } 15394c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier --waiting_count_; 1540e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 1550e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1560e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // We are shutting down, return NULL to tell the worker thread to stop looping. 1570e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier return NULL; 1580e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1590e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 16002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierTask* ThreadPool::TryGetTask(Thread* self) { 1610e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 16202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return TryGetTaskLocked(self); 16302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 16402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 16502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierTask* ThreadPool::TryGetTaskLocked(Thread* self) { 16602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (started_ && !tasks_.empty()) { 16702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Task* task = tasks_.front(); 16802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier tasks_.pop_front(); 16902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return task; 17002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 17102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return NULL; 17202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 17302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 1741d54e73444e017d3a65234e0f193846f3e27472bIan Rogersvoid ThreadPool::Wait(Thread* self, bool do_work, bool may_hold_locks) { 1751d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (do_work) { 1761d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Task* task = NULL; 1771d54e73444e017d3a65234e0f193846f3e27472bIan Rogers while ((task = TryGetTask(self)) != NULL) { 1781d54e73444e017d3a65234e0f193846f3e27472bIan Rogers task->Run(self); 1791d54e73444e017d3a65234e0f193846f3e27472bIan Rogers task->Finalize(); 1801d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 18102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 1820e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // Wait until each thread is waiting and the task list is empty. 18302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, task_queue_lock_); 18402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while (!shutting_down_ && (waiting_count_ != GetThreadCount() || !tasks_.empty())) { 1851d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (!may_hold_locks) { 1861d54e73444e017d3a65234e0f193846f3e27472bIan Rogers completion_condition_.Wait(self); 1871d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } else { 1881d54e73444e017d3a65234e0f193846f3e27472bIan Rogers completion_condition_.WaitHoldingLocks(self); 1891d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 1900e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 1910e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1920e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1932ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromsize_t ThreadPool::GetTaskCount(Thread* self) { 19402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, task_queue_lock_); 19502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return tasks_.size(); 19602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 19702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 19802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierWorkStealingWorker::WorkStealingWorker(ThreadPool* thread_pool, const std::string& name, 19902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t stack_size) 2000cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom : ThreadPoolWorker(thread_pool, name, stack_size), task_(NULL) {} 20102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 20202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartiervoid WorkStealingWorker::Run() { 20302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Thread* self = Thread::Current(); 20402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Task* task = NULL; 20502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingThreadPool* thread_pool = down_cast<WorkStealingThreadPool*>(thread_pool_); 20602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while ((task = thread_pool_->GetTask(self)) != NULL) { 20702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingTask* stealing_task = down_cast<WorkStealingTask*>(task); 20802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 20902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier { 21002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK(task_ == NULL); 21102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, thread_pool->work_steal_lock_); 21202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Register that we are running the task 21302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++stealing_task->ref_count_; 21402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier task_ = stealing_task; 21502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 21602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier stealing_task->Run(self); 21702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Mark ourselves as not running a task so that nobody tries to steal from us. 21802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // There is a race condition that someone starts stealing from us at this point. This is okay 21902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // due to the reference counting. 22002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier task_ = NULL; 22102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 22202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier bool finalize; 22302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 22402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Steal work from tasks until there is none left to steal. Note: There is a race, but 22502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // all that happens when the race occurs is that we steal some work instead of processing a 22602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // task from the queue. 22702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while (thread_pool->GetTaskCount(self) == 0) { 22802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingTask* steal_from_task = NULL; 22902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 23002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier { 23102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, thread_pool->work_steal_lock_); 23202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Try finding a task to steal from. 23302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_from_task = thread_pool->FindTaskToStealFrom(self); 23402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (steal_from_task != NULL) { 23502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK_NE(stealing_task, steal_from_task) 23602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier << "Attempting to steal from completed self task"; 23702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_from_task->ref_count_++; 23802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else { 23902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier break; 24002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 24102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 24202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 24302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (steal_from_task != NULL) { 24402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Task which completed earlier is going to steal some work. 24502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier stealing_task->StealFrom(self, steal_from_task); 24602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 24702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier { 24802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // We are done stealing from the task, lets decrement its reference count. 24902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, thread_pool->work_steal_lock_); 25002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier finalize = !--steal_from_task->ref_count_; 25102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 25202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 25302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (finalize) { 25402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_from_task->Finalize(); 25502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 25602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 25702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 25802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 25902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier { 26002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, thread_pool->work_steal_lock_); 26102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // If nobody is still referencing task_ we can finalize it. 26202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier finalize = !--stealing_task->ref_count_; 26302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 26402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 26502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (finalize) { 26602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier stealing_task->Finalize(); 26702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 26802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 26902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 27002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 2710cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian CarlstromWorkStealingWorker::~WorkStealingWorker() {} 27202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 27302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierWorkStealingThreadPool::WorkStealingThreadPool(size_t num_threads) 27402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier : ThreadPool(0), 27502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier work_steal_lock_("work stealing lock"), 27602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_index_(0) { 27702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while (GetThreadCount() < num_threads) { 27802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const std::string name = StringPrintf("Work stealing worker %zu", GetThreadCount()); 27902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier threads_.push_back(new WorkStealingWorker(this, name, ThreadPoolWorker::kDefaultStackSize)); 28002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 28102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 28202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 28302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierWorkStealingTask* WorkStealingThreadPool::FindTaskToStealFrom(Thread* self) { 28402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const size_t thread_count = GetThreadCount(); 28502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier for (size_t i = 0; i < thread_count; ++i) { 28602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: Use CAS instead of lock. 28702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++steal_index_; 28802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (steal_index_ >= thread_count) { 28902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_index_-= thread_count; 29002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 29102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 29202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingWorker* worker = down_cast<WorkStealingWorker*>(threads_[steal_index_]); 29302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingTask* task = worker->task_; 29402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (task) { 29502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Not null, we can probably steal from this worker. 29602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return task; 29702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 29802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 29902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Couldn't find something to steal. 30002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return NULL; 30102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 30202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 3030cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian CarlstromWorkStealingThreadPool::~WorkStealingThreadPool() {} 30402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 3050e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} // namespace art 306