OLD | NEW |
(Empty) | |
| 1 // Copyright 2016 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 #include "components/scheduler/base/queueing_time_estimator.h" |
| 6 |
| 7 #include "base/time/default_tick_clock.h" |
| 8 |
| 9 namespace scheduler { |
| 10 |
| 11 namespace { |
| 12 |
| 13 // This method computes the expected queueing time of a randomly distributed |
| 14 // task R within a window containing a single task T. Let T' be the time range |
| 15 // for which T overlaps the window. We first compute the probability that R will |
| 16 // start within T'. We then compute the expected queueing duration if R does |
| 17 // start within this range. Since the start time of R is uniformly distributed |
| 18 // within the window, this is equal to the average of the queueing times if R |
| 19 // started at the beginning or end of T'. The expected queueing time of T is the |
| 20 // probability that R will start within T', multiplied by the expected queueing |
| 21 // duration if R does fall in this range. |
| 22 base::TimeDelta ExpectedQueueingTimeFromTask(base::TimeTicks task_start, |
| 23 base::TimeTicks task_end, |
| 24 base::TimeTicks window_start, |
| 25 base::TimeTicks window_end) { |
| 26 DCHECK(task_start <= task_end); |
| 27 DCHECK(task_start <= window_end); |
| 28 DCHECK(window_start < window_end); |
| 29 DCHECK(task_end >= window_start); |
| 30 base::TimeTicks task_in_window_start_time = |
| 31 std::max(task_start, window_start); |
| 32 base::TimeTicks task_in_window_end_time = |
| 33 std::min(task_end, window_end); |
| 34 DCHECK(task_in_window_end_time <= task_in_window_end_time); |
| 35 |
| 36 double probability_of_this_task = |
| 37 static_cast<double>((task_in_window_end_time - task_in_window_start_time) |
| 38 .InMicroseconds()) / |
| 39 (window_end - window_start).InMicroseconds(); |
| 40 |
| 41 base::TimeDelta expected_queueing_duration_within_task = |
| 42 ((task_end - task_in_window_start_time) + |
| 43 (task_end - task_in_window_end_time)) / |
| 44 2; |
| 45 |
| 46 return base::TimeDelta::FromMillisecondsD( |
| 47 probability_of_this_task * |
| 48 expected_queueing_duration_within_task.InMillisecondsF()); |
| 49 } |
| 50 |
| 51 } // namespace |
| 52 |
| 53 QueueingTimeEstimator::QueueingTimeEstimator( |
| 54 QueueingTimeEstimator::Client* client, |
| 55 base::TimeDelta window_duration) |
| 56 : client_(client), |
| 57 window_duration_(window_duration), |
| 58 window_start_time_() {} |
| 59 |
| 60 void QueueingTimeEstimator::OnToplevelTaskCompleted( |
| 61 base::TimeTicks task_start_time, |
| 62 base::TimeTicks task_end_time) { |
| 63 if (window_start_time_.is_null()) |
| 64 window_start_time_ = task_start_time; |
| 65 |
| 66 while (TimePastWindowEnd(task_end_time)) { |
| 67 if (!TimePastWindowEnd(task_start_time)) { |
| 68 // Include the current task in this window. |
| 69 current_expected_queueing_time_ += ExpectedQueueingTimeFromTask( |
| 70 task_start_time, task_end_time, window_start_time_, |
| 71 window_start_time_ + window_duration_); |
| 72 } |
| 73 client_->OnQueueingTimeForWindowEstimated(current_expected_queueing_time_); |
| 74 window_start_time_ += window_duration_; |
| 75 current_expected_queueing_time_ = base::TimeDelta(); |
| 76 } |
| 77 |
| 78 current_expected_queueing_time_ += ExpectedQueueingTimeFromTask( |
| 79 task_start_time, task_end_time, window_start_time_, |
| 80 window_start_time_ + window_duration_); |
| 81 } |
| 82 |
| 83 bool QueueingTimeEstimator::TimePastWindowEnd(base::TimeTicks time) { |
| 84 return time > window_start_time_ + window_duration_; |
| 85 } |
| 86 |
| 87 } // namespace scheduler |
OLD | NEW |