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 #include "dfx/trace/ffrt_trace.h" 25 26 namespace ffrt { 27 template<typename T> 28 class QueueStrategy { 29 public: 30 using DequeFunc = T*(*)(const uint32_t, const uint64_t, std::multimap<uint64_t, T*>*, void*); 31 DequeBatch(const uint32_t queueId,const uint64_t now,std::multimap<uint64_t,T * > * whenMapIn,void * args)32 static T* DequeBatch(const uint32_t queueId, const uint64_t now, 33 std::multimap<uint64_t, T*>* whenMapIn, void* args) 34 { 35 (void)args; 36 auto& whenMap = *whenMapIn; 37 // dequeue due tasks in batch 38 T* head = whenMap.begin()->second; 39 whenMap.erase(whenMap.begin()); 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 node = next; 50 } 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 * > * whenMapIn,void * args)57 static T* DequeSingleByPriority(const uint32_t queueId, 58 const uint64_t now, std::multimap<uint64_t, T*>* whenMapIn, void* args) 59 { 60 (void)args; 61 auto& whenMap = *whenMapIn; 62 // dequeue next expired task by priority 63 auto iterTarget = whenMap.begin(); 64 for (auto ite = whenMap.begin(); ite != whenMap.end() && ite->first < now; ite++) { 65 if (iterTarget->second->GetPriority() == ffrt_queue_priority_immediate) { 66 break; 67 } 68 if (ite->second->GetPriority() < iterTarget->second->GetPriority()) { 69 iterTarget = ite; 70 } 71 } 72 73 T* head = iterTarget->second; 74 whenMap.erase(iterTarget); 75 76 FFRT_LOGD("dequeue [gid=%llu], %u other tasks in [queueId=%u] ", head->gid, whenMap.size(), queueId); 77 return head; 78 } 79 DequeSingleAgainstStarvation(const uint32_t queueId,const uint64_t now,std::multimap<uint64_t,T * > * whenMapVec,void * args)80 static T* DequeSingleAgainstStarvation(const uint32_t queueId, 81 const uint64_t now, std::multimap<uint64_t, T*>* whenMapVec, void* args) 82 { 83 // dequeue in descending order of priority 84 // a low-priority task is dequeued every time five high-priority tasks are dequeued 85 constexpr int maxPullTaskCount = 5; 86 std::vector<int>* pulledTaskCount = static_cast<std::vector<int>*>(args); 87 88 int iterIndex = ffrt_inner_queue_priority_idle; 89 auto iterTarget = whenMapVec[iterIndex].cbegin(); 90 for (int idx = 0; idx < ffrt_inner_queue_priority_idle; idx++) { 91 const auto& currentMap = whenMapVec[idx]; 92 if (currentMap.empty()) { 93 continue; 94 } 95 if (whenMapVec[iterIndex].empty() || iterTarget->first > currentMap.cbegin()->first) { 96 iterIndex = idx; 97 iterTarget = currentMap.cbegin(); 98 } 99 } 100 101 for (int idx = 0; idx < ffrt_inner_queue_priority_idle; idx++) { 102 if ((*pulledTaskCount)[idx] >= maxPullTaskCount) { 103 continue; 104 } 105 106 const auto& currentMap = whenMapVec[idx]; 107 if (!currentMap.empty() && currentMap.cbegin()->first < now) { 108 iterTarget = currentMap.cbegin(); 109 iterIndex = idx; 110 break; 111 } 112 } 113 114 T* head = iterTarget->second; 115 (*pulledTaskCount)[iterIndex]++; 116 117 for (int idx = 0; idx < iterIndex; idx++) { 118 (*pulledTaskCount)[idx] = 0; 119 } 120 whenMapVec[iterIndex].erase(iterTarget); 121 122 size_t mapCount = 0; 123 for (int idx = 0; idx <= ffrt_inner_queue_priority_idle; idx++) { 124 auto& currentMap = whenMapVec[idx]; 125 mapCount += currentMap.size(); 126 } 127 FFRT_LOGD("dequeue [gid=%llu], prio %d, %u other tasks in [queueId=%u] ", 128 head->gid, head->GetPriority(), mapCount, queueId); 129 130 return head; 131 } 132 }; 133 } // namespace ffrt 134 135 #endif // FFRT_QUEUE_STRATEGY_H