1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
// Copyright (c) 2012 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.
#ifndef NET_BASE_PRIORITIZED_DISPATCHER_H_
#define NET_BASE_PRIORITIZED_DISPATCHER_H_
#include <stddef.h>
#include <vector>
#include "base/macros.h"
#include "net/base/net_export.h"
#include "net/base/priority_queue.h"
namespace net {
// A priority-based dispatcher of jobs. Dispatch order is by priority (highest
// first) and then FIFO. The dispatcher enforces limits on the number of running
// jobs. It never revokes a job once started. The job must call OnJobFinished
// once it finishes in order to dispatch further jobs.
//
// This class is NOT thread-safe which is enforced by the underlying
// non-thread-safe PriorityQueue. All operations are O(p) time for p priority
// levels. It is safe to execute any method, including destructor, from within
// Job::Start.
//
class NET_EXPORT_PRIVATE PrioritizedDispatcher {
public:
class Job;
typedef PriorityQueue<Job*>::Priority Priority;
// Describes the limits for the number of jobs started by the dispatcher.
// For example, |total_jobs| = 30 and |reserved_slots| = { 0, 5, 10, 5 } allow
// for at most 30 running jobs in total. Jobs at priority 0 can't use slots
// reserved for higher priorities, so they are limited to 10.
// If there are already 24 jobs running, then only 6 more jobs can start. No
// jobs at priority 1 or below can start. After one more job starts, no jobs
// at priority 2 or below can start, since the remaining 5 slots are reserved
// for priority 3 or above.
struct NET_EXPORT_PRIVATE Limits {
Limits(Priority num_priorities, size_t total_jobs);
Limits(const Limits& other);
~Limits();
// Total allowed running jobs.
size_t total_jobs;
// Number of slots reserved for each priority and higher.
// Sum of |reserved_slots| must be no greater than |total_jobs|.
std::vector<size_t> reserved_slots;
};
// An interface to the job dispatched by PrioritizedDispatcher. The dispatcher
// does not own the Job but expects it to live as long as the Job is queued.
// Use Cancel to remove Job from queue before it is dispatched. The Job can be
// deleted after it is dispatched or canceled, or the dispatcher is destroyed.
class Job {
public:
// Note: PrioritizedDispatcher will never delete a Job.
virtual ~Job() {}
// Called when the dispatcher starts the job. Once the job finishes, it must
// call OnJobFinished.
virtual void Start() = 0;
};
// A handle to the enqueued job. The handle becomes invalid when the job is
// canceled, updated, or started.
typedef PriorityQueue<Job*>::Pointer Handle;
// Creates a dispatcher enforcing |limits| on number of running jobs.
explicit PrioritizedDispatcher(const Limits& limits);
~PrioritizedDispatcher();
size_t num_running_jobs() const { return num_running_jobs_; }
size_t num_queued_jobs() const { return queue_.size(); }
size_t num_priorities() const { return max_running_jobs_.size(); }
// Adds |job| with |priority| to the dispatcher. If limits permit, |job| is
// started immediately. Returns handle to the job or null-handle if the job is
// started. The dispatcher does not own |job|, but |job| must live as long as
// it is queued in the dispatcher.
Handle Add(Job* job, Priority priority);
// Just like Add, except that it adds Job at the font of queue of jobs with
// priorities of |priority|.
Handle AddAtHead(Job* job, Priority priority);
// Removes the job with |handle| from the queue. Invalidates |handle|.
// Note: a Handle is valid iff the job is in the queue, i.e. has not Started.
void Cancel(const Handle& handle);
// Cancels and returns the oldest-lowest-priority Job invalidating any
// handles to it. Returns NULL if the queue is empty.
Job* EvictOldestLowest();
// Moves the queued job with |handle| to the end of all values with priority
// |priority| and returns the updated handle, or null-handle if it starts the
// job. Invalidates |handle|. No-op if priority did not change.
Handle ChangePriority(const Handle& handle, Priority priority);
// Notifies the dispatcher that a running job has finished. Could start a job.
void OnJobFinished();
// Retrieves the Limits that |this| is currently using. This may not exactly
// match the Limits this was created with. In particular, the number of slots
// reserved for the lowest priority will always be 0, even if it was non-zero
// in the Limits passed to the constructor or to SetLimits.
Limits GetLimits() const;
// Updates |max_running_jobs_| to match |limits|. Starts jobs if new limit
// allows. Does not stop jobs if the new limits are lower than the old ones.
void SetLimits(const Limits& limits);
// Set the limits to zero for all priorities, allowing no new jobs to start.
void SetLimitsToZero();
private:
// Attempts to dispatch the job with |handle| at priority |priority| (might be
// different than |handle.priority()|. Returns true if successful. If so
// the |handle| becomes invalid.
bool MaybeDispatchJob(const Handle& handle, Priority priority);
// Attempts to dispatch the next highest priority job in the queue. Returns
// true if successful, and all handles to that job become invalid.
bool MaybeDispatchNextJob();
// Queue for jobs that need to wait for a spare slot.
PriorityQueue<Job*> queue_;
// Maximum total number of running jobs allowed after a job at a particular
// priority is started. If a greater or equal number of jobs are running, then
// another job cannot be started.
std::vector<size_t> max_running_jobs_;
// Total number of running jobs.
size_t num_running_jobs_;
DISALLOW_COPY_AND_ASSIGN(PrioritizedDispatcher);
};
} // namespace net
#endif // NET_BASE_PRIORITIZED_DISPATCHER_H_
|
