1 // Copyright 2015 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 #ifndef BASE_TASK_SEQUENCE_MANAGER_TASK_QUEUE_SELECTOR_H_
6 #define BASE_TASK_SEQUENCE_MANAGER_TASK_QUEUE_SELECTOR_H_
7 
8 #include <stddef.h>
9 
10 #include "base/base_export.h"
11 #include "base/macros.h"
12 #include "base/pending_task.h"
13 #include "base/task/sequence_manager/task_queue_selector_logic.h"
14 #include "base/task/sequence_manager/work_queue_sets.h"
15 #include "base/threading/thread_checker.h"
16 
17 namespace base {
18 namespace sequence_manager {
19 namespace internal {
20 
21 // TaskQueueSelector is used by the SchedulerHelper to enable prioritization
22 // of particular task queues.
23 class BASE_EXPORT TaskQueueSelector {
24  public:
25   TaskQueueSelector();
26   ~TaskQueueSelector();
27 
28   // Called to register a queue that can be selected. This function is called
29   // on the main thread.
30   void AddQueue(internal::TaskQueueImpl* queue);
31 
32   // The specified work will no longer be considered for selection. This
33   // function is called on the main thread.
34   void RemoveQueue(internal::TaskQueueImpl* queue);
35 
36   // Make |queue| eligible for selection. This function is called on the main
37   // thread. Must only be called if |queue| is disabled.
38   void EnableQueue(internal::TaskQueueImpl* queue);
39 
40   // Disable selection from |queue|. Must only be called if |queue| is enabled.
41   void DisableQueue(internal::TaskQueueImpl* queue);
42 
43   // Called get or set the priority of |queue|.
44   void SetQueuePriority(internal::TaskQueueImpl* queue,
45                         TaskQueue::QueuePriority priority);
46 
47   // Called to choose the work queue from which the next task should be taken
48   // and run. Return true if |out_work_queue| indicates the queue to service or
49   // false to avoid running any task.
50   //
51   // This function is called on the main thread.
52   bool SelectWorkQueueToService(WorkQueue** out_work_queue);
53 
54   // Serialize the selector state for tracing.
55   void AsValueInto(trace_event::TracedValue* state) const;
56 
57   class BASE_EXPORT Observer {
58    public:
59     virtual ~Observer() = default;
60 
61     // Called when |queue| transitions from disabled to enabled.
62     virtual void OnTaskQueueEnabled(internal::TaskQueueImpl* queue) = 0;
63   };
64 
65   // Called once to set the Observer. This function is called
66   // on the main thread. If |observer| is null, then no callbacks will occur.
67   void SetTaskQueueSelectorObserver(Observer* observer);
68 
69   // Returns true if all the enabled work queues are empty. Returns false
70   // otherwise.
71   bool AllEnabledWorkQueuesAreEmpty() const;
72 
73  protected:
74   class BASE_EXPORT PrioritizingSelector {
75    public:
76     PrioritizingSelector(TaskQueueSelector* task_queue_selector,
77                          const char* name);
78 
79     void ChangeSetIndex(internal::TaskQueueImpl* queue,
80                         TaskQueue::QueuePriority priority);
81     void AddQueue(internal::TaskQueueImpl* queue,
82                   TaskQueue::QueuePriority priority);
83     void RemoveQueue(internal::TaskQueueImpl* queue);
84 
85     bool SelectWorkQueueToService(TaskQueue::QueuePriority max_priority,
86                                   WorkQueue** out_work_queue,
87                                   bool* out_chose_delayed_over_immediate);
88 
delayed_work_queue_sets()89     WorkQueueSets* delayed_work_queue_sets() {
90       return &delayed_work_queue_sets_;
91     }
immediate_work_queue_sets()92     WorkQueueSets* immediate_work_queue_sets() {
93       return &immediate_work_queue_sets_;
94     }
95 
delayed_work_queue_sets()96     const WorkQueueSets* delayed_work_queue_sets() const {
97       return &delayed_work_queue_sets_;
98     }
immediate_work_queue_sets()99     const WorkQueueSets* immediate_work_queue_sets() const {
100       return &immediate_work_queue_sets_;
101     }
102 
103     bool ChooseOldestWithPriority(TaskQueue::QueuePriority priority,
104                                   bool* out_chose_delayed_over_immediate,
105                                   WorkQueue** out_work_queue) const;
106 
107 #if DCHECK_IS_ON() || !defined(NDEBUG)
108     bool CheckContainsQueueForTest(const internal::TaskQueueImpl* queue) const;
109 #endif
110 
111    private:
112     bool ChooseOldestImmediateTaskWithPriority(
113         TaskQueue::QueuePriority priority,
114         WorkQueue** out_work_queue) const;
115 
116     bool ChooseOldestDelayedTaskWithPriority(TaskQueue::QueuePriority priority,
117                                              WorkQueue** out_work_queue) const;
118 
119     // Return true if |out_queue| contains the queue with the oldest pending
120     // task from the set of queues of |priority|, or false if all queues of that
121     // priority are empty. In addition |out_chose_delayed_over_immediate| is set
122     // to true iff we chose a delayed work queue in favour of an immediate work
123     // queue.
124     bool ChooseOldestImmediateOrDelayedTaskWithPriority(
125         TaskQueue::QueuePriority priority,
126         bool* out_chose_delayed_over_immediate,
127         WorkQueue** out_work_queue) const;
128 
129     const TaskQueueSelector* task_queue_selector_;
130     WorkQueueSets delayed_work_queue_sets_;
131     WorkQueueSets immediate_work_queue_sets_;
132 
133     DISALLOW_COPY_AND_ASSIGN(PrioritizingSelector);
134   };
135 
136   // Return true if |out_queue| contains the queue with the oldest pending task
137   // from the set of queues of |priority|, or false if all queues of that
138   // priority are empty. In addition |out_chose_delayed_over_immediate| is set
139   // to true iff we chose a delayed work queue in favour of an immediate work
140   // queue.  This method will force select an immediate task if those are being
141   // starved by delayed tasks.
142   void SetImmediateStarvationCountForTest(size_t immediate_starvation_count);
143 
prioritizing_selector_for_test()144   PrioritizingSelector* prioritizing_selector_for_test() {
145     return &prioritizing_selector_;
146   }
147 
148   // Maximum score to accumulate before high priority tasks are run even in
149   // the presence of highest priority tasks.
150   static const size_t kMaxHighPriorityStarvationScore = 3;
151 
152   // Increment to be applied to the high priority starvation score when a task
153   // should have only a small effect on the score. E.g. A number of highest
154   // priority tasks must run before the high priority queue is considered
155   // starved.
156   static const size_t kSmallScoreIncrementForHighPriorityStarvation = 1;
157 
158   // Maximum score to accumulate before normal priority tasks are run even in
159   // the presence of higher priority tasks i.e. highest and high priority tasks.
160   static const size_t kMaxNormalPriorityStarvationScore = 5;
161 
162   // Increment to be applied to the normal priority starvation score when a task
163   // should have a large effect on the score. E.g Only a few high priority
164   // priority tasks must run before the normal priority queue is considered
165   // starved.
166   static const size_t kLargeScoreIncrementForNormalPriorityStarvation = 2;
167 
168   // Increment to be applied to the normal priority starvation score when a task
169   // should have only a small effect on the score. E.g. A number of highest
170   // priority tasks must run before the normal priority queue is considered
171   // starved.
172   static const size_t kSmallScoreIncrementForNormalPriorityStarvation = 1;
173 
174   // Maximum score to accumulate before low priority tasks are run even in the
175   // presence of highest, high, or normal priority tasks.
176   static const size_t kMaxLowPriorityStarvationScore = 25;
177 
178   // Increment to be applied to the low priority starvation score when a task
179   // should have a large effect on the score. E.g. Only a few normal/high
180   // priority tasks must run before the low priority queue is considered
181   // starved.
182   static const size_t kLargeScoreIncrementForLowPriorityStarvation = 5;
183 
184   // Increment to be applied to the low priority starvation score when a task
185   // should have only a small effect on the score. E.g. A lot of highest
186   // priority tasks must run before the low priority queue is considered
187   // starved.
188   static const size_t kSmallScoreIncrementForLowPriorityStarvation = 1;
189 
190   // Maximum number of delayed tasks tasks which can be run while there's a
191   // waiting non-delayed task.
192   static const size_t kMaxDelayedStarvationTasks = 3;
193 
194  private:
195   // Returns the priority which is next after |priority|.
196   static TaskQueue::QueuePriority NextPriority(
197       TaskQueue::QueuePriority priority);
198 
199   bool SelectWorkQueueToServiceInternal(WorkQueue** out_work_queue);
200 
201   // Called whenever the selector chooses a task queue for execution with the
202   // priority |priority|.
203   void DidSelectQueueWithPriority(TaskQueue::QueuePriority priority,
204                                   bool chose_delayed_over_immediate);
205 
206   // Returns true if there are pending tasks with priority |priority|.
207   bool HasTasksWithPriority(TaskQueue::QueuePriority priority);
208 
209   ThreadChecker main_thread_checker_;
210 
211   PrioritizingSelector prioritizing_selector_;
212   size_t immediate_starvation_count_;
213   size_t high_priority_starvation_score_;
214   size_t normal_priority_starvation_score_;
215   size_t low_priority_starvation_score_;
216 
217   Observer* task_queue_selector_observer_;  // Not owned.
218   DISALLOW_COPY_AND_ASSIGN(TaskQueueSelector);
219 };
220 
221 }  // namespace internal
222 }  // namespace sequence_manager
223 }  // namespace base
224 
225 #endif  // BASE_TASK_SEQUENCE_MANAGER_TASK_QUEUE_SELECTOR_H_
226