1 /*
2  * Copyright (c) 2023 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 #ifndef FFRT_QUEUE_STRATEGY_H
16 #define FFRT_QUEUE_STRATEGY_H
17 
18 #include <map>
19 #include <vector>
20 #include <algorithm>
21 #include "c/type_def.h"
22 #include "c/queue_ext.h"
23 #include "dfx/log/ffrt_log_api.h"
24 
25 namespace ffrt {
26 template<typename T>
27 class QueueStrategy {
28 public:
29     using DequeFunc = T*(*)(const uint32_t, const uint64_t, std::multimap<uint64_t, T*>&, void*);
30 
DequeBatch(const uint32_t queueId,const uint64_t now,std::multimap<uint64_t,T * > & whenMap,void * args)31     static T* DequeBatch(const uint32_t queueId, const uint64_t now,
32         std::multimap<uint64_t, T*>& whenMap, void* args)
33     {
34         (void)args;
35         // dequeue due tasks in batch
36         T* head = whenMap.begin()->second;
37         whenMap.erase(whenMap.begin());
38 
39         T* node = head;
40         while (!whenMap.empty() && whenMap.begin()->first < now) {
41             auto next = whenMap.begin()->second;
42             if (next->GetQos() != head->GetQos()) {
43                 break;
44             }
45             node->SetNextTask(next);
46             whenMap.erase(whenMap.begin());
47             node = next;
48         }
49 
50         FFRT_LOGD("dequeue [gid=%llu -> gid=%llu], %u other tasks in [queueId=%u] ",
51             head->gid, node->gid, whenMap.size(), queueId);
52         return head;
53     }
54 
DequeSingleByPriority(const uint32_t queueId,const uint64_t now,std::multimap<uint64_t,T * > & whenMap,void * args)55     static T* DequeSingleByPriority(const uint32_t queueId,
56         const uint64_t now, std::multimap<uint64_t, T*>& whenMap, void* args)
57     {
58         (void)args;
59         // dequeue next expired task by priority
60         auto iterTarget = whenMap.begin();
61         for (auto ite = whenMap.begin(); ite != whenMap.end() && ite->first < now; ite++) {
62             if (iterTarget->second->GetPriority() == ffrt_queue_priority_immediate) {
63                 break;
64             }
65             if (ite->second->GetPriority() < iterTarget->second->GetPriority()) {
66                 iterTarget = ite;
67             }
68         }
69 
70         T* head = iterTarget->second;
71         whenMap.erase(iterTarget);
72 
73         FFRT_LOGD("dequeue [gid=%llu], %u other tasks in [queueId=%u] ", head->gid, whenMap.size(), queueId);
74         return head;
75     }
76 
DequeSingleAgainstStarvation(const uint32_t queueId,const uint64_t now,std::multimap<uint64_t,T * > & whenMap,void * args)77     static T* DequeSingleAgainstStarvation(const uint32_t queueId,
78         const uint64_t now, std::multimap<uint64_t, T*>& whenMap, void* args)
79     {
80         // dequeue in descending order of priority
81         // a low-priority task is dequeued every time five high-priority tasks are dequeued
82         constexpr int maxPullTaskCount = 5;
83         std::vector<int>* pulledTaskCount = static_cast<std::vector<int>*>(args);
84 
85         auto iterTarget = whenMap.begin();
86         for (int idx = 0; idx < ffrt_inner_queue_priority_idle; idx++) {
87             if ((*pulledTaskCount)[idx] >= maxPullTaskCount) {
88                 continue;
89             }
90 
91             auto iter = std::find_if(whenMap.begin(), whenMap.end(),
92                 [idx, now](const auto& pair) { return (pair.first < now) && (pair.second->GetPriority() == idx); });
93             if (iter != whenMap.end()) {
94                 iterTarget = iter;
95                 break;
96             }
97         }
98 
99         T* head = iterTarget->second;
100         (*pulledTaskCount)[head->GetPriority()]++;
101         for (int idx = 0; idx < head->GetPriority(); idx++) {
102             (*pulledTaskCount)[idx] = 0;
103         }
104 
105         whenMap.erase(iterTarget);
106         FFRT_LOGD("dequeue [gid=%llu], %u other tasks in [queueId=%u] ", head->gid, whenMap.size(), queueId);
107 
108         return head;
109     }
110 };
111 } // namespace ffrt
112 
113 #endif // FFRT_QUEUE_STRATEGY_H