components/drive/job_queue.h

   1 // Copyright 2013 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 COMPONENTS_DRIVE_JOB_QUEUE_H_
   6 #define COMPONENTS_DRIVE_JOB_QUEUE_H_
   7
   8 #include <deque>
   9 #include <set>
  10 #include <vector>
  11
  12 #include "components/drive/job_list.h"
  13
  14 namespace drive {
  15
  16 // Priority queue for managing jobs in JobScheduler.
  17 class JobQueue {
  18  public:
  19   // Creates a queue that allows |num_max_concurrent_jobs| concurrent job
  20   // execution and has |num_priority_levels| levels of priority.
  21   JobQueue(size_t num_max_concurrent_jobs,
  22            size_t num_priority_levels,
  23            size_t num_max_batch_jobs,
  24            size_t max_batch_size);
  25   ~JobQueue();
  26
  27   // Pushes a job |id| of |priority|. The job with the smallest priority value
  28   // is popped first (lower values are higher priority). In the same priority,
  29   // the queue is "first-in first-out". If multiple jobs with |batchable| = true
  30   // are pushed continuously, there will be popped at the same time unless the
  31   // number of jobs exceeds |num_max_batch_jobs_| or the sum of |job_size|
  32   // exceeds or |max_batch_size_|.
  33   void Push(JobID id, int priority, bool batchable, uint64 job_size);
  34
  35   // Pops the first job which meets |accepted_priority| (i.e. the first job in
  36   // the queue with equal or higher priority (lower value)), and the limit of
  37   // concurrent job count is satisfied.
  38   //
  39   // For instance, if |accepted_priority| is 1, the first job with priority 0
  40   // (higher priority) in the queue is picked even if a job with priority 1 was
  41   // pushed earlier. If there is no job with priority 0, the first job with
  42   // priority 1 in the queue is picked.
  43   //
  44   // If the first found job and following jobs are batchable, these jobs are
  45   // popped out at the same time unless the total size of jobs exceeds
  46   // |max_batch_size_|.
  47   void PopForRun(int accepted_priority, std::vector<JobID>* jobs);
  48
  49   // Gets queued jobs with the given priority.
  50   void GetQueuedJobs(int priority, std::vector<JobID>* jobs) const;
  51
  52   // Marks a running job |id| as finished running. This decreases the count
  53   // of running parallel jobs and makes room for other jobs to be popped.
  54   void MarkFinished(JobID id);
  55
  56   // Generates a string representing the internal state for logging.
  57   std::string ToString() const;
  58
  59   // Gets the total number of jobs in the queue.
  60   size_t GetNumberOfJobs() const;
  61
  62   // Removes the job from the queue.
  63   void Remove(JobID id);
  64
  65  private:
  66   // JobID and additional properties that are needed to determine which tasks it
  67   // runs next.
  68   struct Item {
  69     Item();
  70     Item(JobID id, bool batchable, uint64 size);
  71     ~Item();
  72     JobID id;
  73     bool batchable;
  74     uint64 size;
  75   };
  76
  77   const size_t num_max_concurrent_jobs_;
  78   std::vector<std::deque<Item>> queue_;
  79   const size_t num_max_batch_jobs_;
  80   const size_t max_batch_size_;
  81   std::set<JobID> running_;
  82
  83   DISALLOW_COPY_AND_ASSIGN(JobQueue);
  84 };
  85
  86 }  // namespace drive
  87
  88 #endif  // COMPONENTS_DRIVE_JOB_QUEUE_H_