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 * > * whenMapIn,void * args)31 static T* DequeBatch(const uint32_t queueId, const uint64_t now, 32 std::multimap<uint64_t, T*>* whenMapIn, void* args) 33 { 34 (void)args; 35 auto& whenMap = *whenMapIn; 36 // dequeue due tasks in batch 37 T* head = whenMap.begin()->second; 38 whenMap.erase(whenMap.begin()); 39 head->Dequeue(); 40 41 T* node = head; 42 while (!whenMap.empty() && whenMap.begin()->first < now) { 43 auto next = whenMap.begin()->second; 44 if (next->GetQos() != head->GetQos()) { 45 break; 46 } 47 node->SetNextTask(next); 48 whenMap.erase(whenMap.begin()); 49 next->Dequeue(); 50 node = next; 51 } 52 FFRT_LOGD("dequeue [gid=%llu -> gid=%llu], %u other tasks in [queueId=%u] ", 53 head->gid, node->gid, whenMap.size(), queueId); 54 return head; 55 } 56 DequeSingleByPriority(const uint32_t queueId,const uint64_t now,std::multimap<uint64_t,T * > * whenMapVec,void * args)57 static T* DequeSingleByPriority(const uint32_t queueId, 58 const uint64_t now, std::multimap<uint64_t, T*>* whenMapVec, void* args) 59 { 60 (void)args; 61 // dequeue next expired task by priority 62 int iterIndex = ffrt_queue_priority_idle; 63 auto iterTarget = whenMapVec[iterIndex].cbegin(); 64 for (int idx = ffrt_queue_priority_immediate; idx <= ffrt_queue_priority_idle; idx++) { 65 const auto& currentMap = whenMapVec[idx]; 66 if (currentMap.empty()) { 67 continue; 68 } 69 if (whenMapVec[iterIndex].empty() || iterTarget->first > currentMap.cbegin()->first) { 70 iterIndex = idx; 71 iterTarget = currentMap.cbegin(); 72 } 73 } 74 75 for (int idx = ffrt_queue_priority_immediate; idx <= ffrt_queue_priority_idle; idx++) { 76 const auto& currentMap = whenMapVec[idx]; 77 if (!currentMap.empty() && currentMap.cbegin()->first < now) { 78 iterTarget = currentMap.cbegin(); 79 iterIndex = idx; 80 break; 81 } 82 } 83 T* head = iterTarget->second; 84 whenMapVec[iterIndex].erase(iterTarget); 85 head->Dequeue(); 86 87 size_t mapCount = 0; 88 for (int idx = ffrt_queue_priority_immediate; idx <= ffrt_queue_priority_idle; idx++) { 89 auto& currentMap = whenMapVec[idx]; 90 mapCount += currentMap.size(); 91 } 92 FFRT_LOGD("dequeue [gid=%llu], %u other tasks in [queueId=%u] ", head->gid, mapCount, queueId); 93 return head; 94 } 95 DequeSingleAgainstStarvation(const uint32_t queueId,const uint64_t now,std::multimap<uint64_t,T * > * whenMapVec,void * args)96 static T* DequeSingleAgainstStarvation(const uint32_t queueId, 97 const uint64_t now, std::multimap<uint64_t, T*>* whenMapVec, void* args) 98 { 99 // dequeue in descending order of priority 100 // a low-priority task is dequeued every time five high-priority tasks are dequeued 101 constexpr int maxPullTaskCount = 5; 102 std::vector<int>* pulledTaskCount = static_cast<std::vector<int>*>(args); 103 104 int iterIndex = ffrt_inner_queue_priority_idle; 105 auto iterTarget = whenMapVec[iterIndex].cbegin(); 106 for (int idx = 0; idx < ffrt_inner_queue_priority_idle; idx++) { 107 const auto& currentMap = whenMapVec[idx]; 108 if (currentMap.empty()) { 109 continue; 110 } 111 if (whenMapVec[iterIndex].empty() || iterTarget->first > currentMap.cbegin()->first) { 112 iterIndex = idx; 113 iterTarget = currentMap.cbegin(); 114 } 115 } 116 117 for (int idx = 0; idx < ffrt_inner_queue_priority_idle; idx++) { 118 if ((*pulledTaskCount)[idx] >= maxPullTaskCount) { 119 continue; 120 } 121 122 const auto& currentMap = whenMapVec[idx]; 123 if (!currentMap.empty() && currentMap.cbegin()->first < now) { 124 iterTarget = currentMap.cbegin(); 125 iterIndex = idx; 126 break; 127 } 128 } 129 130 T* head = iterTarget->second; 131 (*pulledTaskCount)[iterIndex]++; 132 133 for (int idx = 0; idx < iterIndex; idx++) { 134 (*pulledTaskCount)[idx] = 0; 135 } 136 whenMapVec[iterIndex].erase(iterTarget); 137 head->Dequeue(); 138 139 size_t mapCount = 0; 140 for (int idx = 0; idx <= ffrt_inner_queue_priority_idle; idx++) { 141 auto& currentMap = whenMapVec[idx]; 142 mapCount += currentMap.size(); 143 } 144 FFRT_LOGD("dequeue [gid=%llu], prio %d, %u other tasks in [queueId=%u] ", 145 head->gid, head->GetPriority(), mapCount, queueId); 146 147 return head; 148 } 149 }; 150 } // namespace ffrt 151 152 #endif // FFRT_QUEUE_STRATEGY_H