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
|
// Copyright 2013 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 COMPONENTS_DRIVE_JOB_QUEUE_H_
#define COMPONENTS_DRIVE_JOB_QUEUE_H_
#include <stddef.h>
#include <stdint.h>
#include <deque>
#include <set>
#include <vector>
#include "base/macros.h"
#include "components/drive/job_list.h"
namespace drive {
// Priority queue for managing jobs in JobScheduler.
class JobQueue {
public:
// Creates a queue that allows |num_max_concurrent_jobs| concurrent job
// execution and has |num_priority_levels| levels of priority.
JobQueue(size_t num_max_concurrent_jobs,
size_t num_priority_levels,
size_t num_max_batch_jobs,
size_t max_batch_size);
~JobQueue();
// Pushes a job |id| of |priority|. The job with the smallest priority value
// is popped first (lower values are higher priority). In the same priority,
// the queue is "first-in first-out". If multiple jobs with |batchable| = true
// are pushed continuously, there will be popped at the same time unless the
// number of jobs exceeds |num_max_batch_jobs_| or the sum of |job_size|
// exceeds or |max_batch_size_|.
void Push(JobID id, int priority, bool batchable, uint64_t job_size);
// Pops the first job which meets |accepted_priority| (i.e. the first job in
// the queue with equal or higher priority (lower value)), and the limit of
// concurrent job count is satisfied.
//
// For instance, if |accepted_priority| is 1, the first job with priority 0
// (higher priority) in the queue is picked even if a job with priority 1 was
// pushed earlier. If there is no job with priority 0, the first job with
// priority 1 in the queue is picked.
//
// If the first found job and following jobs are batchable, these jobs are
// popped out at the same time unless the total size of jobs exceeds
// |max_batch_size_|.
void PopForRun(int accepted_priority, std::vector<JobID>* jobs);
// Gets queued jobs with the given priority.
void GetQueuedJobs(int priority, std::vector<JobID>* jobs) const;
// Marks a running job |id| as finished running. This decreases the count
// of running parallel jobs and makes room for other jobs to be popped.
void MarkFinished(JobID id);
// Generates a string representing the internal state for logging.
std::string ToString() const;
// Gets the total number of jobs in the queue.
size_t GetNumberOfJobs() const;
// Removes the job from the queue.
void Remove(JobID id);
private:
// JobID and additional properties that are needed to determine which tasks it
// runs next.
struct Item {
Item();
Item(JobID id, bool batchable, uint64_t size);
~Item();
JobID id;
bool batchable;
uint64_t size;
};
const size_t num_max_concurrent_jobs_;
std::vector<std::deque<Item>> queue_;
const size_t num_max_batch_jobs_;
const size_t max_batch_size_;
std::set<JobID> running_;
DISALLOW_COPY_AND_ASSIGN(JobQueue);
};
} // namespace drive
#endif // COMPONENTS_DRIVE_JOB_QUEUE_H_
|
