Adopt a less severe anti-starvation policy for immediate tasks

components/scheduler/base/task_queue_manager_unittest.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "components/scheduler/base/task_queue_manager.h"
 
 #include "base/location.h"
 #include "base/run_loop.h"
 #include "base/single_thread_task_runner.h"
 #include "base/test/simple_test_tick_clock.h"
 #include "base/threading/thread.h"
 #include "cc/test/ordered_simple_task_runner.h"
 #include "components/scheduler/base/real_time_domain.h"
 #include "components/scheduler/base/task_queue_impl.h"
 #include "components/scheduler/base/task_queue_manager_delegate_for_test.h"
 #include "components/scheduler/base/task_queue_selector.h"
 #include "components/scheduler/base/test_always_fail_time_source.h"
 #include "components/scheduler/base/test_time_source.h"
 #include "components/scheduler/base/virtual_time_domain.h"
 #include "components/scheduler/base/work_queue.h"
 #include "components/scheduler/base/work_queue_sets.h"
 #include "testing/gmock/include/gmock/gmock.h"
 
 using testing::ElementsAre;
+using testing::ElementsAreArray;
 using testing::_;
 
 namespace scheduler {
 
 class MessageLoopTaskRunner : public TaskQueueManagerDelegateForTest {
  public:
   static scoped_refptr<MessageLoopTaskRunner> Create(
       scoped_ptr<base::TickClock> tick_clock) {
     return make_scoped_refptr(new MessageLoopTaskRunner(tick_clock.Pass()));
   }
@@ skipping 1045 matching lines @@
   EXPECT_FALSE(queue1->NeedsPumping());
 }
 
 void ExpensiveTestTask(int value,
                        base::SimpleTestTickClock* clock,
                        std::vector<int>* out_result) {
   out_result->push_back(value);
   clock->Advance(base::TimeDelta::FromMilliseconds(1));
 }
 
-TEST_F(TaskQueueManagerTest, ImmediateAndDelayedTaskRoundRobbin) {
+TEST_F(TaskQueueManagerTest, ImmediateAndDelayedTaskInterleaving) {
   Initialize(1u);
 
   std::vector<int> run_order;
   base::TimeDelta delay = base::TimeDelta::FromMilliseconds(10);
-  runners_[0]->PostDelayedTask(
-      FROM_HERE, base::Bind(&ExpensiveTestTask, 10, now_src_.get(), &run_order),
-      delay);
-  runners_[0]->PostDelayedTask(
-      FROM_HERE, base::Bind(&ExpensiveTestTask, 11, now_src_.get(), &run_order),
-      delay);
-  runners_[0]->PostDelayedTask(
-      FROM_HERE, base::Bind(&ExpensiveTestTask, 12, now_src_.get(), &run_order),
-      delay);
-  runners_[0]->PostDelayedTask(
-      FROM_HERE, base::Bind(&ExpensiveTestTask, 13, now_src_.get(), &run_order),
-      delay);
+  for (int i = 10; i < 19; i++) {
+    runners_[0]->PostDelayedTask(
+        FROM_HERE,
+        base::Bind(&ExpensiveTestTask, i, now_src_.get(), &run_order),
+        delay);
+  }
 
   test_task_runner_->RunForPeriod(delay);
 
-  runners_[0]->PostTask(
-      FROM_HERE, base::Bind(&ExpensiveTestTask, 0, now_src_.get(), &run_order));
-  runners_[0]->PostTask(
-      FROM_HERE, base::Bind(&ExpensiveTestTask, 1, now_src_.get(), &run_order));
-  runners_[0]->PostTask(
-      FROM_HERE, base::Bind(&ExpensiveTestTask, 2, now_src_.get(), &run_order));
-  runners_[0]->PostTask(
-      FROM_HERE, base::Bind(&ExpensiveTestTask, 3, now_src_.get(), &run_order));
+  for (int i = 0; i < 9; i++) {
+    runners_[0]->PostTask(
+        FROM_HERE,
+        base::Bind(&ExpensiveTestTask, i, now_src_.get(), &run_order));
+  }
 
   test_task_runner_->SetAutoAdvanceNowToPendingTasks(true);
   test_task_runner_->RunUntilIdle();
 
-  EXPECT_THAT(run_order, ElementsAre(10, 0, 11, 1, 12, 2, 13, 3));
+  // Delayed tasks are not allowed to starve out immediate work which is why
+  // some of the immediate tasks run out of order.
+  int expected_run_order[] = {
+    10, 11, 12, 13, 0, 14, 15, 16, 1, 17, 18, 2, 3, 4, 5, 6, 7, 8
+  };
+  EXPECT_THAT(run_order, ElementsAreArray(expected_run_order));
 }
 
 TEST_F(TaskQueueManagerTest,
        DelayedTaskDoesNotSkipAHeadOfNonDelayedTask_SameQueue) {
   Initialize(1u);
 
   std::vector<int> run_order;
   base::TimeDelta delay = base::TimeDelta::FromMilliseconds(10);
   runners_[0]->PostTask(FROM_HERE, base::Bind(&TestTask, 2, &run_order));
   runners_[0]->PostTask(FROM_HERE, base::Bind(&TestTask, 3, &run_order));
@@ skipping 453 matching lines @@
   base::Callback<bool()> should_exit_;
   base::SimpleTestTickClock* now_src_;
 };
 
 bool ShouldExit(QuadraticTask* quadratic_task, LinearTask* linear_task) {
   return quadratic_task->count() == 1000 || linear_task->count() == 1000;
 }
 
 }  // namespace
 
-TEST_F(TaskQueueManagerTest, DelayedTasksDontStarveNonDelayedWork_SameQueue) {
+TEST_F(TaskQueueManagerTest,
+       DelayedTasksDontBadlyStarveNonDelayedWork_SameQueue) {
   Initialize(1u);
 
   QuadraticTask quadratic_delayed_task(
       runners_[0], base::TimeDelta::FromMilliseconds(10), now_src_.get());
   LinearTask linear_immediate_task(runners_[0], base::TimeDelta(),
                                    now_src_.get());
   base::Callback<bool()> should_exit =
       base::Bind(ShouldExit, &quadratic_delayed_task, &linear_immediate_task);
   quadratic_delayed_task.SetShouldExit(should_exit);
   linear_immediate_task.SetShouldExit(should_exit);
 
   quadratic_delayed_task.Run();
   linear_immediate_task.Run();
 
   test_task_runner_->SetAutoAdvanceNowToPendingTasks(true);
   test_task_runner_->RunUntilIdle();
 
   double ratio = static_cast<double>(linear_immediate_task.count()) /
                  static_cast<double>(quadratic_delayed_task.count());
 
-  EXPECT_GT(ratio, 0.9);
+  EXPECT_GT(ratio, 0.333);
   EXPECT_LT(ratio, 1.1);
 }
 
 TEST_F(TaskQueueManagerTest, ImmediateWorkCanStarveDelayedTasks_SameQueue) {
   Initialize(1u);
 
   QuadraticTask quadratic_immediate_task(runners_[0], base::TimeDelta(),
                                          now_src_.get());
   LinearTask linear_delayed_task(
       runners_[0], base::TimeDelta::FromMilliseconds(10), now_src_.get());
@@ skipping 12 matching lines @@
   double ratio = static_cast<double>(linear_delayed_task.count()) /
                  static_cast<double>(quadratic_immediate_task.count());
 
   // This is by design, we want to enforce a strict ordering in task execution
   // where by delayed tasks can not skip ahead of non-delayed work.
   EXPECT_GT(ratio, 0.0);
   EXPECT_LT(ratio, 0.1);
 }
 
 TEST_F(TaskQueueManagerTest,
-       DelayedTasksDontStarveNonDelayedWork_DifferentQueue) {
+       DelayedTasksDontBadlyStarveNonDelayedWork_DifferentQueue) {
   Initialize(2u);
 
   QuadraticTask quadratic_delayed_task(
       runners_[0], base::TimeDelta::FromMilliseconds(10), now_src_.get());
   LinearTask linear_immediate_task(runners_[1], base::TimeDelta(),
                                    now_src_.get());
   base::Callback<bool()> should_exit =
       base::Bind(ShouldExit, &quadratic_delayed_task, &linear_immediate_task);
   quadratic_delayed_task.SetShouldExit(should_exit);
   linear_immediate_task.SetShouldExit(should_exit);
 
   quadratic_delayed_task.Run();
   linear_immediate_task.Run();
 
   test_task_runner_->SetAutoAdvanceNowToPendingTasks(true);
   test_task_runner_->RunUntilIdle();
 
   double ratio = static_cast<double>(linear_immediate_task.count()) /
                  static_cast<double>(quadratic_delayed_task.count());
 
-  EXPECT_GT(ratio, 0.9);
+  EXPECT_GT(ratio, 0.333);
   EXPECT_LT(ratio, 1.1);
 }
 
 TEST_F(TaskQueueManagerTest,
        ImmediateWorkCanStarveDelayedTasks_DifferentQueue) {
   Initialize(2u);
 
   QuadraticTask quadratic_immediate_task(runners_[0], base::TimeDelta(),
                                          now_src_.get());
   LinearTask linear_delayed_task(
@@ skipping 13 matching lines @@
   double ratio = static_cast<double>(linear_delayed_task.count()) /
                  static_cast<double>(quadratic_immediate_task.count());
 
   // This is by design, we want to enforce a strict ordering in task execution
   // where by delayed tasks can not skip ahead of non-delayed work.
   EXPECT_GT(ratio, 0.0);
   EXPECT_LT(ratio, 0.1);
 }
 
 }  // namespace scheduler