scheduler: Maintain a constant enqueue order for every task (issue 2786083005 by skyostil@chromium.org)

2 views

Skip to first unread message

skyostil@chromium.org via codereview.chromium.org

unread,

Apr 12, 2017, 11:50:58 AM4/12/17

to alexc...@chromium.org, chromium...@chromium.org, j...@chromium.org, dari...@chromium.org, devtools...@chromium.org, blink-...@chromium.org, kinuko...@chromium.org, schedul...@chromium.org, pfel...@chromium.org

Reviewers: alex clarke
CL: https://codereview.chromium.org/2786083005/

Message:
I'm still chasing a couple of layout test failures but I think this is ready for
review. Alex, PTAL.

Description:
scheduler: Maintain a constant enqueue order for every task

The scheduler uses a monotonically increasing counter called enqueue
order for sorting tasks. This value was previously assigned at post
time for immediate tasks and at delay expiration time for delayed tasks.

Because expired delayed tasks get processed in a consistent order
(i.e., sorted by their delay) within a single task queue, but in
a random order between task queues, delayed tasks for the exact
same point in time posted two distinct task queues will run in a
random order w.r.t. each other. This in turn causes a problem in
virtual time scenarios where delayed tasks should behave
deterministically.

This patch fixes the problem by eliminating the two-phase assignment
of enqueue orders to delayed tasks. This was originally added to avoid
a flood of expired delayed tasks starving immediate work, but because
the selector now makes sure delayed work doesn't starve immediate work
and vice versa, this mechanism can be removed.

A side effect of this removal is that there is no longer a guarantee
that expired delayed tasks won't run before immediate tasks that were
posted later. Note that the base::TaskRunner doesn't offer this
guarantee either so it shouldn't be relied on.

BUG=696001,701223

Affected files (+254, -250 lines):
M content/browser/devtools/protocol/devtools_protocol_browsertest.cc
M third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h
M third_party/WebKit/Source/platform/scheduler/base/enqueue_order.cc
M third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h
M third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc
M third_party/WebKit/Source/platform/scheduler/base/task_queue_manager.h
M third_party/WebKit/Source/platform/scheduler/base/task_queue_manager.cc
M third_party/WebKit/Source/platform/scheduler/base/task_queue_manager_unittest.cc
M third_party/WebKit/Source/platform/scheduler/base/task_queue_selector.cc
M third_party/WebKit/Source/platform/scheduler/base/task_queue_selector_unittest.cc
M third_party/WebKit/Source/platform/scheduler/base/work_queue.h
M third_party/WebKit/Source/platform/scheduler/base/work_queue.cc
M third_party/WebKit/Source/platform/scheduler/base/work_queue_sets_unittest.cc
M third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc
M third_party/WebKit/Source/platform/scheduler/renderer/task_queue_throttler_unittest.cc

alexc...@chromium.org

unread,

Apr 13, 2017, 3:46:01 AM4/13/17

to skyo...@chromium.org, chromium...@chromium.org, j...@chromium.org, dari...@chromium.org, devtools...@chromium.org, blink-...@chromium.org, kinuko...@chromium.org, schedul...@chromium.org, pfel...@chromium.org

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h
File third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h
(left):

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h#oldcode28
third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h:28: //
A 64bit integer used to provide ordering of tasks. NOTE The scheduler
assumes
We should keep the comment about not overflowing.

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h
File third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h
(right):

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h#newcode22
third_party/WebKit/Source/platform/scheduler/base/enqueue_order.h:22:
uint64_t sequence_num;
I wonder if we should have

using SequenceNum = uint64_t;

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc
File
third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc
(left):

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc#oldcode305
third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc:305:
int thread_hop_task_sequence_number =
Oh wow that's a nasty bug fixed here.

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc#oldcode451
third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc:451:
main_thread_only().delayed_work_queue->Push(std::move(task));
Something for a future patch, but I wonder if we actually need the
delayed_work_queue anymore.

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/work_queue.cc
File third_party/WebKit/Source/platform/scheduler/base/work_queue.cc
(right):

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/work_queue.cc#newcode164
third_party/WebKit/Source/platform/scheduler/base/work_queue.cc:164:
EnqueueOrder enqueue_order = {base::TimeTicks(), 0};
Can we have a default constructor?

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc
File
third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc
(right):

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc#newcode40
third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc:40:
TaskQueueImpl::Task FakeTaskWithEnqueueOrder(int enqueue_order) {
s/int/uint65_t

https://codereview.chromium.org/2786083005/

skyostil@chromium.org via codereview.chromium.org

unread,

Apr 18, 2017, 6:47:49 AM4/18/17

Thanks, all addressed!

On 2017/04/13 07:46:00, alex clarke wrote:
> We should keep the comment about not overflowing.

Yep, it's now further up the file where the enqueue order is defined.

On 2017/04/13 07:46:00, alex clarke wrote:
> I wonder if we should have
>
> using SequenceNum = uint64_t;

Good idea, done.

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc
File
third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc
(left):

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc#oldcode305
third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc:305:
int thread_hop_task_sequence_number =

On 2017/04/13 07:46:00, alex clarke wrote:
> Oh wow that's a nasty bug fixed here.

You mean the overflow? Yeah :)

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc#oldcode451
third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.cc:451:
main_thread_only().delayed_work_queue->Push(std::move(task));

On 2017/04/13 07:46:00, alex clarke wrote:
> Something for a future patch, but I wonder if we actually need the
> delayed_work_queue anymore.

Interesting point. We'd still need some way to round-robin immediate and
delayed work. Let's revisit this.

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/work_queue.cc
File third_party/WebKit/Source/platform/scheduler/base/work_queue.cc
(right):

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/work_queue.cc#newcode164
third_party/WebKit/Source/platform/scheduler/base/work_queue.cc:164:
EnqueueOrder enqueue_order = {base::TimeTicks(), 0};

On 2017/04/13 07:46:00, alex clarke wrote:
> Can we have a default constructor?

Done.

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc
File
third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc
(right):

https://codereview.chromium.org/2786083005/diff/280001/third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc#newcode40
third_party/WebKit/Source/platform/scheduler/base/work_queue_unittest.cc:40:
TaskQueueImpl::Task FakeTaskWithEnqueueOrder(int enqueue_order) {

On 2017/04/13 07:46:00, alex clarke wrote:
> s/int/uint65_t

Done.

https://codereview.chromium.org/2786083005/

alexc...@chromium.org

unread,

Apr 18, 2017, 6:58:37 AM4/18/17

lgtm

https://codereview.chromium.org/2786083005/

skyostil@chromium.org via codereview.chromium.org

unread,

Apr 26, 2017, 9:11:22 AM4/26/17

For posterity: we decided against offering this ordering guarantee across task
queue since it would basically tie our hands when wanting to schedule distinct
task queues more freely. The specific virtual time issue is addressed by
https://codereview.chromium.org/2841463003/.

https://codereview.chromium.org/2786083005/

Reply all

Reply to author

Forward

0 new messages