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