prioritized_dispatcher.h 5.9 KB

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